第05讲-网格及网格压缩-719整理279课件

计算机动画的算法与技术

ComputerAnimation:AlgorithmsandTechniques雍俊海清华大学软件学院SchoolofSoftware,TsinghuaUniversityyongjunhai@6/6/20231TsinghuaUniversity,Jun-HaiYong第05讲网格及网格压缩雍俊海(Jun-HaiYong)清华大学软件学院SchoolofSoftware,TsinghuaUniversity6/6/20232TsinghuaUniversity,Jun-HaiYong本讲总体纲要网格(mesh)网格压缩网格简化对连接关系的压缩对几何数据的压缩6/6/20233TsinghuaUniversity,Jun-HaiYong网格(Mesh)的基本组成要素顶点(Vertex)边(Edge)面(Face)不共平面的面6/6/20234TsinghuaUniversity,Jun-HaiYong退化情形边?面?6/6/20235TsinghuaUniversity,Jun-HaiYong网格的基本数据结构顶点: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网格的附加属性颜色信息材料信息纹理信息其他6/6/20237TsinghuaUniversity,Jun-HaiYong网格的固有信息法向量实例:V1处法向量的计算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网格的固有信息顶点的度(Degree)又称为顶点的化合价(valence)3333433226/6/20239TsinghuaUniversity,Jun-HaiYong网格的固有信息同构:一一映射关系拓扑学上的同构A和B同构通过伸缩与扭曲变换A和B互相转换网格连接关系上的同构:相同的连接关系6/6/202310TsinghuaUniversity,Jun-HaiYong网格的固有信息亏格(genus)柄(把手)的个数0126/6/202311TsinghuaUniversity,Jun-HaiYong网格的固有信息洞(Hole)6/6/202312TsinghuaUniversity,Jun-HaiYong网格的固有信息封闭非奇异网格的欧拉公式v–e+f=2(b+h–g)其中v是顶点数，e是边数，f是面数，b是形体个数，h是洞数，g是亏格数v=8e=12f=6b=1h=0g=0v=8e=12f=8b=1h=1g=06/6/202313TsinghuaUniversity,Jun-HaiYong网格的固有信息对于封闭的简单三角形网格:

(设:b=1,g=h=0,每条边有且仅有两个面共用)面数与顶点数的关系:边数与顶点数的关系:顶点的平均度数:f=2v-4e=3v-66-(12/v)≈6(当v很大时)6/6/202314TsinghuaUniversity,Jun-HaiYong网格的固有信息证明边数与面数的关系每边两面,每面三边:2e=3f面数与顶点数的关系将3f=2e代入v–e+f=22v-3f+2f=4f=2v-4边数与顶点数的关系将3f=2e代入v–e+f=23v-3e+2e=6e=3v-6顶点的平均度数每边两个端点:顶点的总度数=2e=6v-12顶点的平均度数=(6v-12)/v=6-(12/v)6/6/202315TsinghuaUniversity,Jun-HaiYong常用网格三角形网格四边形网格有限元分析基于物理的动画模型6/6/202316TsinghuaUniversity,Jun-HaiYong本讲总体纲要网格网格压缩网格简化对连接关系的压缩对几何数据的压缩6/6/202317TsinghuaUniversity,Jun-HaiYong网格压缩为什么要压缩网格?表示后继处理控制6/6/202318TsinghuaUniversity,Jun-HaiYong本讲总体纲要网格网格压缩网格简化对连接关系的压缩对几何数据的压缩6/6/202319TsinghuaUniversity,Jun-HaiYong应用——3D激光扫描6/6/202320TsinghuaUniversity,Jun-HaiYong应用——LOD(FordBroncoModel)Triangles:41,85527,97020,92212,9398,3854,7666/6/202321TsinghuaUniversity,Jun-HaiYong网格简化动画演示c10_HOPPE.MOV6/6/202322TsinghuaUniversity,Jun-HaiYong网格简化算法:参考文献MichaelGarlandandPaulS.Heckbert.Surfacesimplificationusingquadricerrormetrics.InSIGGRAPH1997,209–216.6/6/202323TsinghuaUniversity,Jun-HaiYong应用去掉不必要的细节加速后继处理便于控制6/6/202324TsinghuaUniversity,Jun-HaiYong目标效率网格质量一般性聚合性:可以连接原始网格的不连接区域6/6/202325TsinghuaUniversity,Jun-HaiYong算法整体描述对每个顶点v，计算Q(v)选取所有的合法点对对所有合法点对(v1,v2)，计算点对的代价f(v1,v2)及V将所有的合法点对(v1,v2)放入一个堆中，并按f(v1,v2)值从小到大排序(最小的在最上面)依次收缩堆最上方的点对(v1,v2)V更新受影响的点对的代价值及堆中点对的顺序6/6/202326TsinghuaUniversity,Jun-HaiYong点v处的收缩误差∆(v)点v对应一系列的平面pplanes(v)平面表示:p=[a,b,c,d]T平面方程:ax+by+cz+d=0约束条件:a2+b2+c2=1收缩代价点v处的收缩误差∆(v)v6/6/202327TsinghuaUniversity,Jun-HaiYong计算Q(v)收缩代价点v处的误差∆(v)=vTQ(v)v6/6/202328TsinghuaUniversity,Jun-HaiYong合法点对的选取(PairSelection)合法点对(v1,v2)(v1,v2)是一条边的两个端点,或者||v1–v2||2<t(给定域值)6/6/202329TsinghuaUniversity,Jun-HaiYong计算点对收缩代价f(v1,v2)及V令Q1=Q(v1)+Q(v2)计算f(v1,v2)=min{UTQ1U|U=[Ux,Uy,Uz,1]T}=VTQ1VV=[Vx,Vy,Vz,1]TV为最小值取得的值退化情况V取边(v1,v2)上取得VTQ1V最小值的点退化情况V取v1或v2或(v1+v2)/26/6/202330TsinghuaUniversity,Jun-HaiYong点对收缩(PairContraction)6/6/202331TsinghuaUniversity,Jun-HaiYong算法结果实例牛5,804faces994faces532faces248faces64faces6/6/202332TsinghuaUniversity,Jun-HaiYong算法结果实例Bunny69,451triangles1,000triangles100triangles1.4%oforiginalsize0.14%oforiginalsize6/6/202333TsinghuaUniversity,Jun-HaiYong逼近误差值两个网格模型Mi和Mn之间的误差计算Mn

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

模型Mn上的采样点集Xi

模型Mi上的采样点集6/6/202334TsinghuaUniversity,Jun-HaiYong网格简化动画演示chopper.exeC10_demo2.rmvbC10_demo3.rmvb6/6/202335TsinghuaUniversity,Jun-HaiYong本讲总体纲要网格网格压缩网格简化对连接关系的压缩对几何数据的压缩6/6/202336TsinghuaUniversity,Jun-HaiYong网格压缩数据表示6/6/202337TsinghuaUniversity,Jun-HaiYong三角形网格的表示顶点：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空间复杂度分析假设现在只讨论封闭的简单三角形网格设v是顶点数，则顶点编号的表示至少需要log2v位顶点的平均度数为6-(12/v)，每个顶点编号出现的平均次数为6-(12/v)每个顶点编号所需的位数为(6-(12/v))b约6b(当v很大时)其中b为记录1个顶点编号所需的位数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三角形面片条表示方法：压缩原理相邻两个三角形共用两个顶点除了第一个三角形外，其余三角形每个三角形只需要增加存储一个顶点编号6/6/202341TsinghuaUniversity,Jun-HaiYong三角形面片条表示方法：空间复杂度分析面数与顶点数的关系:平均每个面记录顶点编号的位数:平均每个顶点记录顶点编号的位数:设b为记录1个顶点编号所需的位数设f为总面数，v为总顶点数f=v-2(v/(v-2))b≈bb6/6/202342TsinghuaUniversity,Jun-HaiYong普通方法表示三角形面片条：空间复杂度分析面数与顶点数的关系:平均每个面记录顶点编号的位数:平均每个顶点记录顶点编号的位数:设b为记录1个顶点编号所需的位数设f为总面数，v为总顶点数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空间复杂度分析:比较三角形面片条表示方法平均每个面记录顶点编号的位数(v/(v-2))b≈b平均每个顶点记录顶点编号的位数b普通方法表示三角形面片条平均每个面记录顶点编号的位数3b平均每个顶点记录顶点编号的位数(3(v-2)/v)b≈3b6/6/202344TsinghuaUniversity,Jun-HaiYong问题如何将任意三角形网格分解成三角形面片条？如何使三角形面片条尽量长?6/6/202345TsinghuaUniversity,Jun-HaiYong边界法从边界出发，逐层往内形成并划分三角形面片条封闭网格无边界将网格一分为二6/6/202346TsinghuaUniversity,Jun-HaiYong边界法:举例实例6/6/202347TsinghuaUniversity,Jun-HaiYong边界法:举例从边界出发形成三角形面片条v1v3v2v4v0v5v6v7v86/6/202348TsinghuaUniversity,Jun-HaiYong边界法:举例分离三角形面片条v1v3v2v4v0v5v6v7v86/6/202349TsinghuaUniversity,Jun-HaiYong边界法:举例从边界出发形成三角形面片条v1v3v2v4v0v5v6v7v86/6/202350TsinghuaUniversity,Jun-HaiYong边界法:举例分离三角形面片条v1v3v2v4v0v5v6v7v86/6/202351TsinghuaUniversity,Jun-HaiYong边界法:举例从边界出发形成三角形面片条v1v3v2v4v0v5v6v76/6/202352TsinghuaUniversity,Jun-HaiYong小结边界法三角形面片条表示方法6/6/202353TsinghuaUniversity,Jun-HaiYong带标志位的三角形面片条表示方法从边界出发，逐层往内形成并划分三角形面片条封闭网格取任意一个顶点作为边界6/6/202354TsinghuaUniversity,Jun-HaiYong带标志位的三角形面片条表示方法R表示开始F表示去掉前一个三角形的第一个顶点，然后再加入一个新顶点M表示去掉前一个三角形的第二个顶点(即中间的顶点)，然后再加入一个新顶点R0,F1,F2,F3v1v3v2v0R1,M0,M2,M3v1v3v2v06/6/202355TsinghuaUniversity,Jun-HaiYong带标志位的三角形面片条表示方法实例从这里开始v1v3v2v4v0v5v6v7v8v10v9v11v14v13v12v156/6/202356TsinghuaUniversity,Jun-HaiYong带标志位的三角形面片条表示方法结果: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本讲总体纲要网格网格压缩网格简化对连接关系的压缩对几何数据的压缩6/6/202358TsinghuaUniversity,Jun-HaiYong对几何数据的压缩算法:参考文献O.DevillersandP-M.Gandoin.GeometricCompressionforInteractiveTransmission.IEEEVisualizationConferenceProceedings,pages319-326,2000.6/6/202359TsinghuaUniversity,Jun-HaiYong三角形网格的表示顶点：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顶点坐标顶点坐标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空间分割法坐标值*系数整数排序空间分割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空间分割法:复杂度分析0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15不用空间分割分:共需4位*16=64位881644441111111111111111222222226/6/202364TsinghuaUniversity,Jun-HaiYong空间分割法:复杂度分析共需: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空间分割法表示及其复杂度分析37104303111011110111221221空间复杂度分析:

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

5位

4位=4位*16位=3位*26位=2位*36位=1位*66/6/202366TsinghuaUniversity,Jun-HaiYong空间分割法:一维情形示例2结果?471134040111111111112122220,1,3,4,5,6,7,8,9,10,11空间复杂度分析:

不采用空间分割法: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