第05講-網(wǎng)格及網(wǎng)格壓縮-719整理279課件

計(jì)算機(jī)動(dòng)畫的算法與技術(shù)

ComputerAnimation:AlgorithmsandTechniques雍俊海清華大學(xué)軟件學(xué)院SchoolofSoftware,TsinghuaUniversityyongjunhai@6/6/20231TsinghuaUniversity,Jun-HaiYong第05講網(wǎng)格及網(wǎng)格壓縮雍俊海(Jun-HaiYong)清華大學(xué)軟件學(xué)院SchoolofSoftware,TsinghuaUniversity6/6/20232TsinghuaUniversity,Jun-HaiYong本講總體綱要網(wǎng)格(mesh)網(wǎng)格壓縮網(wǎng)格簡(jiǎn)化對(duì)連接關(guān)系的壓縮對(duì)幾何數(shù)據(jù)的壓縮6/6/20233TsinghuaUniversity,Jun-HaiYong網(wǎng)格(Mesh)的基本組成要素頂點(diǎn)(Vertex)邊(Edge)面(Face)不共平面的面6/6/20234TsinghuaUniversity,Jun-HaiYong退化情形邊?面?6/6/20235TsinghuaUniversity,Jun-HaiYong網(wǎng)格的基本數(shù)據(jù)結(jié)構(gòu)頂點(diǎn):vi=(x,y,z)T或(wx,wy,wz,w)T邊:ej=(vg,vh)面:fk=(vs1,vs2,…,vsn)或(es1,es2,…,esn)6/6/20236TsinghuaUniversity,Jun-HaiYong網(wǎng)格的附加屬性顏色信息材料信息紋理信息其他6/6/20237TsinghuaUniversity,Jun-HaiYong網(wǎng)格的固有信息法向量實(shí)例:V1處法向量的計(jì)算V1V2V3V4在面V1V3V2中，法向量為:N1,1=(V3-V1)×(V2-V1)在面V1V2V4中，法向量為:N1,2=(V2-V1)×(V4-V1)在面V1V4V3中，法向量為:N1,3=(V4-V1)×(V3-V1)平均法向量為:6/6/20238TsinghuaUniversity,Jun-HaiYong網(wǎng)格的固有信息頂點(diǎn)的度(Degree)又稱為頂點(diǎn)的化合價(jià)(valence)3333433226/6/20239TsinghuaUniversity,Jun-HaiYong網(wǎng)格的固有信息同構(gòu):一一映射關(guān)系拓?fù)鋵W(xué)上的同構(gòu)A和B同構(gòu)通過(guò)伸縮與扭曲變換A和B互相轉(zhuǎn)換網(wǎng)格連接關(guān)系上的同構(gòu):相同的連接關(guān)系6/6/202310TsinghuaUniversity,Jun-HaiYong網(wǎng)格的固有信息虧格(genus)柄(把手)的個(gè)數(shù)0126/6/202311TsinghuaUniversity,Jun-HaiYong網(wǎng)格的固有信息洞(Hole)6/6/202312TsinghuaUniversity,Jun-HaiYong網(wǎng)格的固有信息封閉非奇異網(wǎng)格的歐拉公式v–e+f=2(b+h–g)其中v是頂點(diǎn)數(shù)，e是邊數(shù)，f是面數(shù)，b是形體個(gè)數(shù)，h是洞數(shù)，g是虧格數(shù)v=8e=12f=6b=1h=0g=0v=8e=12f=8b=1h=1g=06/6/202313TsinghuaUniversity,Jun-HaiYong網(wǎng)格的固有信息對(duì)于封閉的簡(jiǎn)單三角形網(wǎng)格:

(設(shè):b=1,g=h=0,每條邊有且僅有兩個(gè)面共用)面數(shù)與頂點(diǎn)數(shù)的關(guān)系:邊數(shù)與頂點(diǎn)數(shù)的關(guān)系:頂點(diǎn)的平均度數(shù):f=2v-4e=3v-66-(12/v)≈6(當(dāng)v很大時(shí))6/6/202314TsinghuaUniversity,Jun-HaiYong網(wǎng)格的固有信息證明邊數(shù)與面數(shù)的關(guān)系每邊兩面,每面三邊:2e=3f面數(shù)與頂點(diǎn)數(shù)的關(guān)系將3f=2e代入v–e+f=22v-3f+2f=4f=2v-4邊數(shù)與頂點(diǎn)數(shù)的關(guān)系將3f=2e代入v–e+f=23v-3e+2e=6e=3v-6頂點(diǎn)的平均度數(shù)每邊兩個(gè)端點(diǎn):頂點(diǎn)的總度數(shù)=2e=6v-12頂點(diǎn)的平均度數(shù)=(6v-12)/v=6-(12/v)6/6/202315TsinghuaUniversity,Jun-HaiYong常用網(wǎng)格三角形網(wǎng)格四邊形網(wǎng)格有限元分析基于物理的動(dòng)畫模型6/6/202316TsinghuaUniversity,Jun-HaiYong本講總體綱要網(wǎng)格網(wǎng)格壓縮網(wǎng)格簡(jiǎn)化對(duì)連接關(guān)系的壓縮對(duì)幾何數(shù)據(jù)的壓縮6/6/202317TsinghuaUniversity,Jun-HaiYong網(wǎng)格壓縮為什么要壓縮網(wǎng)格?表示后繼處理控制6/6/202318TsinghuaUniversity,Jun-HaiYong本講總體綱要網(wǎng)格網(wǎng)格壓縮網(wǎng)格簡(jiǎn)化對(duì)連接關(guān)系的壓縮對(duì)幾何數(shù)據(jù)的壓縮6/6/202319TsinghuaUniversity,Jun-HaiYong應(yīng)用——3D激光掃描6/6/202320TsinghuaUniversity,Jun-HaiYong應(yīng)用——LOD(FordBroncoModel)Triangles:41,85527,97020,92212,9398,3854,7666/6/202321TsinghuaUniversity,Jun-HaiYong網(wǎng)格簡(jiǎn)化動(dòng)畫演示c10_HOPPE.MOV6/6/202322TsinghuaUniversity,Jun-HaiYong網(wǎng)格簡(jiǎn)化算法:參考文獻(xiàn)MichaelGarlandandPaulS.Heckbert.Surfacesimplificationusingquadricerrormetrics.InSIGGRAPH1997,209–216.6/6/202323TsinghuaUniversity,Jun-HaiYong應(yīng)用去掉不必要的細(xì)節(jié)加速后繼處理便于控制6/6/202324TsinghuaUniversity,Jun-HaiYong目標(biāo)效率網(wǎng)格質(zhì)量一般性聚合性:可以連接原始網(wǎng)格的不連接區(qū)域6/6/202325TsinghuaUniversity,Jun-HaiYong算法整體描述對(duì)每個(gè)頂點(diǎn)v，計(jì)算Q(v)選取所有的合法點(diǎn)對(duì)對(duì)所有合法點(diǎn)對(duì)(v1,v2)，計(jì)算點(diǎn)對(duì)的代價(jià)f(v1,v2)及V將所有的合法點(diǎn)對(duì)(v1,v2)放入一個(gè)堆中，并按f(v1,v2)值從小到大排序(最小的在最上面)依次收縮堆最上方的點(diǎn)對(duì)(v1,v2)V更新受影響的點(diǎn)對(duì)的代價(jià)值及堆中點(diǎn)對(duì)的順序6/6/202326TsinghuaUniversity,Jun-HaiYong點(diǎn)v處的收縮誤差?(v)點(diǎn)v對(duì)應(yīng)一系列的平面pplanes(v)平面表示:p=[a,b,c,d]T平面方程:ax+by+cz+d=0約束條件:a2+b2+c2=1收縮代價(jià)點(diǎn)v處的收縮誤差?(v)v6/6/202327TsinghuaUniversity,Jun-HaiYong計(jì)算Q(v)收縮代價(jià)點(diǎn)v處的誤差?(v)=vTQ(v)v6/6/202328TsinghuaUniversity,Jun-HaiYong合法點(diǎn)對(duì)的選取(PairSelection)合法點(diǎn)對(duì)(v1,v2)(v1,v2)是一條邊的兩個(gè)端點(diǎn),或者||v1–v2||2<t(給定域值)6/6/202329TsinghuaUniversity,Jun-HaiYong計(jì)算點(diǎn)對(duì)收縮代價(jià)f(v1,v2)及V令Q1=Q(v1)+Q(v2)計(jì)算f(v1,v2)=min{UTQ1U|U=[Ux,Uy,Uz,1]T}=VTQ1VV=[Vx,Vy,Vz,1]TV為最小值取得的值退化情況V取邊(v1,v2)上取得VTQ1V最小值的點(diǎn)退化情況V取v1或v2或(v1+v2)/26/6/202330TsinghuaUniversity,Jun-HaiYong點(diǎn)對(duì)收縮(PairContraction)6/6/202331TsinghuaUniversity,Jun-HaiYong算法結(jié)果實(shí)例牛5,804faces994faces532faces248faces64faces6/6/202332TsinghuaUniversity,Jun-HaiYong算法結(jié)果實(shí)例Bunny69,451triangles1,000triangles100triangles1.4%oforiginalsize0.14%oforiginalsize6/6/202333TsinghuaUniversity,Jun-HaiYong逼近誤差值兩個(gè)網(wǎng)格模型Mi和Mn之間的誤差計(jì)算Mn

例如可以取為原始模型.Xn

模型Mn上的采樣點(diǎn)集Xi

模型Mi上的采樣點(diǎn)集6/6/202334TsinghuaUniversity,Jun-HaiYong網(wǎng)格簡(jiǎn)化動(dòng)畫演示chopper.exeC10_demo2.rmvbC10_demo3.rmvb6/6/202335TsinghuaUniversity,Jun-HaiYong本講總體綱要網(wǎng)格網(wǎng)格壓縮網(wǎng)格簡(jiǎn)化對(duì)連接關(guān)系的壓縮對(duì)幾何數(shù)據(jù)的壓縮6/6/202336TsinghuaUniversity,Jun-HaiYong網(wǎng)格壓縮數(shù)據(jù)表示6/6/202337TsinghuaUniversity,Jun-HaiYong三角形網(wǎng)格的表示頂點(diǎn)：v1(x1,y1,z1)T

v2(x2,y2,z2)T

v3(x3,y3,z3)Tv4(x4,y4,z4)T面：f1(v1,v3,v2)f2(v1,v2,v4)f3(v2,v3,v4)f4(v1,v4,v3)v1v2v3v4f1f2f3f46/6/202338TsinghuaUniversity,Jun-HaiYong空間復(fù)雜度分析假設(shè)現(xiàn)在只討論封閉的簡(jiǎn)單三角形網(wǎng)格設(shè)v是頂點(diǎn)數(shù)，則頂點(diǎn)編號(hào)的表示至少需要log2v位頂點(diǎn)的平均度數(shù)為6-(12/v)，每個(gè)頂點(diǎn)編號(hào)出現(xiàn)的平均次數(shù)為6-(12/v)每個(gè)頂點(diǎn)編號(hào)所需的位數(shù)為(6-(12/v))b約6b(當(dāng)v很大時(shí))其中b為記錄1個(gè)頂點(diǎn)編號(hào)所需的位數(shù)6/6/202339TsinghuaUniversity,Jun-HaiYong三角形面片條表示方法f0(v0,v1,v2)f1(v1,v2,v3)f2(v2,v3,

v4)f3(v3,v4,

v5)f4(v4,v5,

v6)f5(v5,v6,

v7)v2v1v3v4f0f1f2f3v0f4f5v6v5v76/6/202340TsinghuaUniversity,Jun-HaiYong三角形面片條表示方法：壓縮原理相鄰兩個(gè)三角形共用兩個(gè)頂點(diǎn)除了第一個(gè)三角形外，其余三角形每個(gè)三角形只需要增加存儲(chǔ)一個(gè)頂點(diǎn)編號(hào)6/6/202341TsinghuaUniversity,Jun-HaiYong三角形面片條表示方法：空間復(fù)雜度分析面數(shù)與頂點(diǎn)數(shù)的關(guān)系:平均每個(gè)面記錄頂點(diǎn)編號(hào)的位數(shù):平均每個(gè)頂點(diǎn)記錄頂點(diǎn)編號(hào)的位數(shù):設(shè)b為記錄1個(gè)頂點(diǎn)編號(hào)所需的位數(shù)設(shè)f為總面數(shù)，v為總頂點(diǎn)數(shù)f=v-2(v/(v-2))b≈bb6/6/202342TsinghuaUniversity,Jun-HaiYong普通方法表示三角形面片條：空間復(fù)雜度分析面數(shù)與頂點(diǎn)數(shù)的關(guān)系:平均每個(gè)面記錄頂點(diǎn)編號(hào)的位數(shù):平均每個(gè)頂點(diǎn)記錄頂點(diǎn)編號(hào)的位數(shù):設(shè)b為記錄1個(gè)頂點(diǎn)編號(hào)所需的位數(shù)設(shè)f為總面數(shù)，v為總頂點(diǎn)數(shù)f=v-23b(3(v-2)/v)b≈3bv2v1v3v4f0f1f2f3v0f4f5v6v5v7f0(v0,v1,v2)f1(v1,v2,v3)f2(v2,v3,v4)f3(v3,v4,v5)f4(v4,v5,v6)f5(v5,v6,v7)6/6/202343TsinghuaUniversity,Jun-HaiYong空間復(fù)雜度分析:比較三角形面片條表示方法平均每個(gè)面記錄頂點(diǎn)編號(hào)的位數(shù)(v/(v-2))b≈b平均每個(gè)頂點(diǎn)記錄頂點(diǎn)編號(hào)的位數(shù)b普通方法表示三角形面片條平均每個(gè)面記錄頂點(diǎn)編號(hào)的位數(shù)3b平均每個(gè)頂點(diǎn)記錄頂點(diǎn)編號(hào)的位數(shù)(3(v-2)/v)b≈3b6/6/202344TsinghuaUniversity,Jun-HaiYong問(wèn)題如何將任意三角形網(wǎng)格分解成三角形面片條？如何使三角形面片條盡量長(zhǎng)?6/6/202345TsinghuaUniversity,Jun-HaiYong邊界法從邊界出發(fā)，逐層往內(nèi)形成并劃分三角形面片條封閉網(wǎng)格無(wú)邊界將網(wǎng)格一分為二6/6/202346TsinghuaUniversity,Jun-HaiYong邊界法:舉例實(shí)例6/6/202347TsinghuaUniversity,Jun-HaiYong邊界法:舉例從邊界出發(fā)形成三角形面片條v1v3v2v4v0v5v6v7v86/6/202348TsinghuaUniversity,Jun-HaiYong邊界法:舉例分離三角形面片條v1v3v2v4v0v5v6v7v86/6/202349TsinghuaUniversity,Jun-HaiYong邊界法:舉例從邊界出發(fā)形成三角形面片條v1v3v2v4v0v5v6v7v86/6/202350TsinghuaUniversity,Jun-HaiYong邊界法:舉例分離三角形面片條v1v3v2v4v0v5v6v7v86/6/202351TsinghuaUniversity,Jun-HaiYong邊界法:舉例從邊界出發(fā)形成三角形面片條v1v3v2v4v0v5v6v76/6/202352TsinghuaUniversity,Jun-HaiYong小結(jié)邊界法三角形面片條表示方法6/6/202353TsinghuaUniversity,Jun-HaiYong帶標(biāo)志位的三角形面片條表示方法從邊界出發(fā)，逐層往內(nèi)形成并劃分三角形面片條封閉網(wǎng)格取任意一個(gè)頂點(diǎn)作為邊界6/6/202354TsinghuaUniversity,Jun-HaiYong帶標(biāo)志位的三角形面片條表示方法R表示開始F表示去掉前一個(gè)三角形的第一個(gè)頂點(diǎn)，然后再加入一個(gè)新頂點(diǎn)M表示去掉前一個(gè)三角形的第二個(gè)頂點(diǎn)(即中間的頂點(diǎn))，然后再加入一個(gè)新頂點(diǎn)R0,F1,F2,F3v1v3v2v0R1,M0,M2,M3v1v3v2v06/6/202355TsinghuaUniversity,Jun-HaiYong帶標(biāo)志位的三角形面片條表示方法實(shí)例從這里開始v1v3v2v4v0v5v6v7v8v10v9v11v14v13v12v156/6/202356TsinghuaUniversity,Jun-HaiYong帶標(biāo)志位的三角形面片條表示方法結(jié)果:R0,F4,F5,M1,F6,F2,F7,F3,F8,M11,F15,F14,M10,F13,F9,F12,F4,M5,M10,F6,F11,F7從這里開始v1v3v2v4v0v5v6v7v8v10v9v11v14v13v12v156/6/202357TsinghuaUniversity,Jun-HaiYong本講總體綱要網(wǎng)格網(wǎng)格壓縮網(wǎng)格簡(jiǎn)化對(duì)連接關(guān)系的壓縮對(duì)幾何數(shù)據(jù)的壓縮6/6/202358TsinghuaUniversity,Jun-HaiYong對(duì)幾何數(shù)據(jù)的壓縮算法:參考文獻(xiàn)O.DevillersandP-M.Gandoin.GeometricCompressionforInteractiveTransmission.IEEEVisualizationConferenceProceedings,pages319-326,2000.6/6/202359TsinghuaUniversity,Jun-HaiYong三角形網(wǎng)格的表示頂點(diǎn)：v1(x1,y1,z1)T

v2(x2,y2,z2)T

v3(x3,y3,z3)Tv4(x4,y4,z4)T面：f1(v1,v3,v2)f2(v1,v2,v4)f3(v2,v3,v4)f4(v1,v4,v3)v1v2v3v4f1f2f3f46/6/202360TsinghuaUniversity,Jun-HaiYong頂點(diǎn)坐標(biāo)頂點(diǎn)坐標(biāo)IEEE64-double(64位)IEEE32-float(32位)16位8位示例v(1.442232,1.334423,0.897606)v(1.4422,1.3344,0.8976)6/6/202361TsinghuaUniversity,Jun-HaiYong空間分割法坐標(biāo)值*系數(shù)整數(shù)排序空間分割6/6/202362TsinghuaUniversity,Jun-HaiYong空間分割法:一維情形0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15881644441111111111111111222222226/6/202363TsinghuaUniversity,Jun-HaiYong空間分割法:復(fù)雜度分析0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15不用空間分割分:共需4位*16=64位881644441111111111111111222222226/6/202364TsinghuaUniversity,Jun-HaiYong空間分割法:復(fù)雜度分析共需:31位5位4位=4位*(2-1)6位=3位*(4-2)8位=2位*(8-4)8位=1位*(16-8)881644441111111111111111222222226/6/202365TsinghuaUniversity,Jun-HaiYong空間分割法:一維情形示例10,1,2,3,4,6,7,8,9,11空間分割法表示及其復(fù)雜度分析37104303111011110111221221空間復(fù)雜度分析:

不采用空間分割法:40位采用空間分割法:27位

5位

4位=4位*16位=3位*26位=2位*36位=1位*66/6/202366TsinghuaUniversity,Jun-HaiYong空間分割法:一維情形示例2結(jié)果?471134040111111111112122220,1,3,4,5,6,7,8,9,10,11空間復(fù)雜度分析:

不采用空間分割法:44位采用空間分割法:27位

5位

4位=4位*16位=3位*26位=2位*36位=1位*66/6/202367TsinghuaUniversity,Jun-HaiYong空間分割法:二維情形如何推廣?76/6/202368TsinghuaUniversity,Jun-HaiYong空間分割法:二維情形分割4376/6/202369TsinghuaUniversity,Jun-HaiYong空間分割法:二維情形分割43712406/6/202370TsinghuaUniversity,Jun-HaiYong空間分割法:二維情形分割01113143712406/6/202371TsinghuaUniversity,Jun-HaiYong空間分割法:二維情形分割01011021100111314371240