1、2022-6-9Tsinghua University, Jun-Hai Yong1计算机动画的算法与技术计算机动画的算法与技术Computer Animation: Algorithms and Techniques雍俊海雍俊海清华大学软件学院清华大学软件学院School of Software , Tsinghua U2022-6-9Tsinghua University, Jun-Hai Yong2第第05讲讲 网格及网格压缩网格及网格压缩雍俊海雍俊海( Jun-Hai Yong)清华大学软件学院清华大学软件学院School of Software , Tsinghua Universi
2、ty2022-6-9Tsinghua University, Jun-Hai Yong3本讲总体纲要本讲总体纲要 网格网格(mesh) 网格压缩网格压缩 网格简化网格简化 对连接关系的压缩对连接关系的压缩 对几何数据的压缩对几何数据的压缩2022-6-9Tsinghua University, Jun-Hai Yong4网格网格(Mesh)的基本组成要素的基本组成要素 顶点顶点(Vertex) 边边(Edge) 面面(Face)不共平面不共平面的面的面2022-6-9Tsinghua University, Jun-Hai Yong5退化情形退化情形 边边? 面面?2022-6-9Tsingh
3、ua University, Jun-Hai Yong6网格的基本数据结构网格的基本数据结构 顶点顶点: vi=(x, y, z)T或或(wx, wy, wz, w)T 边边: ej=(vg, vh) 面面: fk= (vs1, vs2, , vsn)或或(es1, es2, , esn)2022-6-9Tsinghua University, Jun-Hai Yong7网格的附加属性网格的附加属性 颜色信息颜色信息 材料信息材料信息 纹理信息纹理信息 其他其他2022-6-9Tsinghua University, Jun-Hai Yong8网格的固有信息网格的固有信息 法向量法向量 实例实
4、例: V1处法向量的计算处法向量的计算V1V2V3V4 在面在面V1V3V2中，法向量为中，法向量为:N1,1=(V3-V1) (V2-V1) 在面在面V1V2V4中，法向量为中，法向量为:N1,2=(V2-V1) (V4-V1) 在面在面V1V4V3中，法向量为中，法向量为:N1,3=(V4-V1) (V3-V1) 平均法向量为平均法向量为:323 , 13 , 122, 12, 121 , 11 , 11NNNNNNN2022-6-9Tsinghua University, Jun-Hai Yong9网格的固有信息网格的固有信息 顶点的度顶点的度(Degree) 又称为顶点的化合价又称为顶
5、点的化合价(valence)3333433222022-6-9Tsinghua University, Jun-Hai Yong10网格的固有信息网格的固有信息 同构同构: 一一映射关系一一映射关系 拓扑学上的同构拓扑学上的同构 A和和B同构同构 通过伸缩与扭曲变换通过伸缩与扭曲变换A和和B互相转换互相转换 网格连接关系上的同构网格连接关系上的同构: 相同的连接关系相同的连接关系2022-6-9Tsinghua University, Jun-Hai Yong11网格的固有信息网格的固有信息 亏格亏格(genus) 柄柄(把手把手)的个数的个数0122022-6-9Tsinghua Unive
6、rsity, Jun-Hai Yong12网格的固有信息网格的固有信息 洞洞(Hole)2022-6-9Tsinghua University, Jun-Hai Yong13网格的固有信息网格的固有信息 封闭非奇异网格的欧拉公式封闭非奇异网格的欧拉公式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 = 02022-6-9Tsinghua University,
7、 Jun-Hai Yong14网格的固有信息网格的固有信息 对于封闭的简单三角形网格对于封闭的简单三角形网格:(设设:b=1,g=h=0, 每条边有且仅有两个面共用每条边有且仅有两个面共用) 面数与顶点数的关系面数与顶点数的关系: 边数与顶点数的关系边数与顶点数的关系: 顶点的平均度数顶点的平均度数:f=2v-4e=3v-66-(12/v)6(当当v很大时很大时)2022-6-9Tsinghua University, Jun-Hai Yong15网格的固有信息网格的固有信息 证明证明 边数与面数的关系边数与面数的关系 每边每边两面两面, 每面每面三边三边: 2e=3f 面数与顶点数的关系面数
8、与顶点数的关系 将将3f=2e代入代入v e + f = 2 2v-3f+2f=4f=2v-4 边数与顶点数的关系边数与顶点数的关系 将将3f=2e代入代入v e + f = 2 3v-3e+2e=6e=3v-6 顶点的平均度数顶点的平均度数 每边每边两个端点两个端点: 顶点的总度数顶点的总度数=2e=6v-12 顶点的平均度数顶点的平均度数=(6v-12)/v=6-(12/v)2022-6-9Tsinghua University, Jun-Hai Yong16常用网格常用网格 三角形网格三角形网格 四边形网格四边形网格 有限元分析有限元分析 基于物理的动画模型基于物理的动画模型2022-6
9、-9Tsinghua University, Jun-Hai Yong17本讲总体纲要本讲总体纲要 网格网格 网格压缩网格压缩 网格简化网格简化 对连接关系的压缩对连接关系的压缩 对几何数据的压缩对几何数据的压缩2022-6-9Tsinghua University, Jun-Hai Yong18网格压缩网格压缩 为什么要压缩网格为什么要压缩网格? 表示表示 后继处理后继处理 控制控制2022-6-9Tsinghua University, Jun-Hai Yong19本讲总体纲要本讲总体纲要 网格网格 网格压缩网格压缩 网格简化网格简化 对连接关系的压缩对连接关系的压缩 对几何数据的压缩对几
10、何数据的压缩2022-6-9Tsinghua University, Jun-Hai Yong20应用应用3D激光扫描激光扫描2022-6-9Tsinghua University, Jun-Hai Yong21应用应用LOD(Ford Bronco Model) Triangles: 41,855 27,970 20,922 12,939 8,385 4,7662022-6-9Tsinghua University, Jun-Hai Yong22网格简化网格简化 动画演示动画演示 c10_HOPPE.MOV2022-6-9Tsinghua University, Jun-Hai Yong23
11、网格简化算法网格简化算法: 参考文献参考文献 Michael Garland and Paul S. Heckbert. Surface simplification using quadric error metrics. In SIGGRAPH 1997, 209216.2022-6-9Tsinghua University, Jun-Hai Yong24应用应用 去掉不必要的细节去掉不必要的细节 加速后继处理加速后继处理 便于控制便于控制2022-6-9Tsinghua University, Jun-Hai Yong25目标目标 效率效率 网格质量网格质量 一般性一般性 聚合性聚合性:
12、 可以连接原始网格的不连接区域可以连接原始网格的不连接区域2022-6-9Tsinghua University, Jun-Hai Yong26算法整体描述算法整体描述1. 对每个顶点对每个顶点v，计算，计算Q(v)2. 选取所有的合法点对选取所有的合法点对3. 对所有合法点对对所有合法点对(v1, v2)，计算，计算点对的代价点对的代价f (v1, v2)及及V4. 将所有的合法点对将所有的合法点对(v1, v2)放入一个堆中，并放入一个堆中，并按按f(v1, v2)值从小到大排序值从小到大排序(最小的在最上面最小的在最上面)5. 依次依次收缩堆最上方的点对收缩堆最上方的点对(v1, v2)
13、V更新受影响的点对的代价值及堆中点对的顺序更新受影响的点对的代价值及堆中点对的顺序2022-6-9Tsinghua University, Jun-Hai Yong27点点v处的收缩误差处的收缩误差(v) 点点v对应一系列的平面对应一系列的平面p planes(v) 平面表示平面表示: p=a, b, c, dT 平面方程平面方程: ax+by+cz+d=0 约束条件约束条件: a2+b2+c2=1 收缩代价收缩代价点点v处的收缩误差处的收缩误差(v) 2)(TT1,vplanespvvpvvvzyxv2022-6-9Tsinghua University, Jun-Hai Yong28计算计
14、算Q(v) 收缩代价收缩代价点点v处的误差处的误差(v) = vTQ(v)vvppvvvplanesp)(TT)()(T)(vplanespppvQ2222Tdcdbdadcdcbcacbdbcbabadacabapp2022-6-9Tsinghua University, Jun-Hai Yong29合法点对的选取合法点对的选取(Pair Selection) 合法点对合法点对(v1, v2) (v1, v2)是一条边的两个端点是一条边的两个端点, 或者或者 |v1 v2|2 t(给定域值给定域值)2022-6-9Tsinghua University, Jun-Hai Yong30计算点对
15、收缩代价计算点对收缩代价f (v1, v2)及及V 令令Q1=Q(v1)+Q(v2) 计算计算 f (v1, v2)=minUTQ1U | U=Ux, Uy, Uz, 1T= VTQ1V V=Vx, Vy, Vz, 1T V为最小值取得的值为最小值取得的值 退化情况退化情况 V取边取边(v1, v2)上取得上取得VTQ1V最小值的点最小值的点 退化情况退化情况 V取取v1或或v2或或(v1+v2)/22022-6-9Tsinghua University, Jun-Hai Yong31点对收缩点对收缩(Pair Contraction)2022-6-9Tsinghua University,
16、Jun-Hai Yong32算法结果实例算法结果实例 牛牛5,804 faces994 faces532 faces248 faces64 faces2022-6-9Tsinghua University, Jun-Hai Yong33算法结果实例算法结果实例 Bunny69,451 triangles1,000 triangles100 triangles1.4% of original size0.14% of original size2022-6-9Tsinghua University, Jun-Hai Yong34逼近误差值逼近误差值 两个网格模型两个网格模型Mi和和Mn之间的误差
17、计算之间的误差计算inniiniddEXvXvMvMvXX,122Mn - 例如可以取为原始模型例如可以取为原始模型. Xn - 模型模型Mn上的采样点集上的采样点集Xi - 模型模型Mi上的采样点集上的采样点集pvMvMpmin),(d2022-6-9Tsinghua University, Jun-Hai Yong35网格简化网格简化 动画演示动画演示 chopper.exe C10_demo2.rmvb C10_demo3.rmvb2022-6-9Tsinghua University, Jun-Hai Yong36本讲总体纲要本讲总体纲要 网格网格 网格压缩网格压缩 网格简化网格简化
18、对连接关系的压缩对连接关系的压缩 对几何数据的压缩对几何数据的压缩2022-6-9Tsinghua University, Jun-Hai Yong37网格压缩网格压缩 数据表示数据表示2022-6-9Tsinghua University, Jun-Hai Yong38三角形网格的表示三角形网格的表示 顶点：顶点： v1(x1, y1, z1)T v2(x2, y2, z2)T v3(x3, y3, z3)T v4(x4, y4, z4)T 面：面： f1(v1, v3, v2) f2(v1, v2, v4) f3(v2, v3, v4) f4(v1, v4, v3)v1v2v3v4f1f2
19、f3f42022-6-9Tsinghua University, Jun-Hai Yong39空间复杂度分析空间复杂度分析 假设现在只讨论封闭的简单三角形网格假设现在只讨论封闭的简单三角形网格 设设v是顶点数，则顶点编号的表示至少需要是顶点数，则顶点编号的表示至少需要log2v位位 顶点的平均度数为顶点的平均度数为6-(12/v)，每个顶点编号出现，每个顶点编号出现的平均次数为的平均次数为6-(12/v) 每个顶点编号所需的位数为每个顶点编号所需的位数为 (6-(12/v) ) b 约约6 b (当当v很大时很大时) 其中其中b为记录为记录1个顶点编号所需的位数个顶点编号所需的位数2022-6
20、-9Tsinghua University, Jun-Hai Yong40三角形面片条表示方法三角形面片条表示方法 f0(v0, v1, v2) f1(v1, v2, v3) f2(v2, v3, v4) f3(v3, v4, v5) f4(v4, v5, v6) f5(v5, v6, v7)v2v1v3v4f0f1f2f3v0f4f5v6v5v72022-6-9Tsinghua University, Jun-Hai Yong41三角形面片条表示方法：压缩原理三角形面片条表示方法：压缩原理 相邻两个三角形共用两个顶点相邻两个三角形共用两个顶点 除了第一个三角形外，其余三角形除了第一个三角形外
21、，其余三角形 每个三角形只需要增加存储一个顶点编号每个三角形只需要增加存储一个顶点编号2022-6-9Tsinghua University, Jun-Hai Yong42三角形面片条表示方法：空间复杂度分析三角形面片条表示方法：空间复杂度分析 面数与顶点数的关系面数与顶点数的关系: 平均每个面记录顶点编号的位数平均每个面记录顶点编号的位数: 平均每个顶点记录顶点编号的位数平均每个顶点记录顶点编号的位数: 设设b为记录为记录1个顶点编号所需的位数个顶点编号所需的位数 设设f为总面数，为总面数，v为总顶点数为总顶点数f=v-2(v/(v-2) b bb2022-6-9Tsinghua Unive
22、rsity, Jun-Hai Yong43普通方法表示三角形面片条：空间复杂度分析普通方法表示三角形面片条：空间复杂度分析 面数与顶点数的关系面数与顶点数的关系: 平均每个面记录顶点编号的位数平均每个面记录顶点编号的位数: 平均每个顶点记录顶点编号的位数平均每个顶点记录顶点编号的位数: 设设b为记录为记录1个顶点编号所需的位数个顶点编号所需的位数 设设f为总面数，为总面数，v为总顶点数为总顶点数f=v-23 b(3(v-2)/v)b 3bv2v1v3v4f0f1f2f3v0f4f5v6v5v7f0(v0, v1, v2) f1(v1, v2, v3) f2(v2, v3, v4) f3(v3,
23、 v4, v5) f4(v4, v5, v6) f5(v5, v6, v7)2022-6-9Tsinghua University, Jun-Hai Yong44空间复杂度分析空间复杂度分析: 比较比较 三角形面片条表示方法三角形面片条表示方法 平均每个面记录顶点编号的位数平均每个面记录顶点编号的位数 (v/(v-2) b b 平均每个顶点记录顶点编号的位数平均每个顶点记录顶点编号的位数 b 普通方法表示三角形面片条普通方法表示三角形面片条 平均每个面记录顶点编号的位数平均每个面记录顶点编号的位数 3 b 平均每个顶点记录顶点编号的位数平均每个顶点记录顶点编号的位数 (3(v-2)/v)b 3
24、b2022-6-9Tsinghua University, Jun-Hai Yong45问题问题 如何将任意三角形网格分解成三角形面如何将任意三角形网格分解成三角形面片条？片条？ 如何使三角形面片条尽量长如何使三角形面片条尽量长?2022-6-9Tsinghua University, Jun-Hai Yong46边界法边界法 从边界出发，逐层往内形成并划分三角从边界出发，逐层往内形成并划分三角形面片条形面片条 封闭网格无边界封闭网格无边界 将网格一分为二将网格一分为二2022-6-9Tsinghua University, Jun-Hai Yong47边界法边界法:举例举例 实例实例2022
25、-6-9Tsinghua University, Jun-Hai Yong48边界法边界法:举例举例 从边界出发从边界出发形成三角形面片条形成三角形面片条v1v3v2v4v0v5v6v7v82022-6-9Tsinghua University, Jun-Hai Yong49边界法边界法:举例举例 分离三角形面片条分离三角形面片条v1v3v2v4v0v5v6v7v82022-6-9Tsinghua University, Jun-Hai Yong50边界法边界法:举例举例 从从边界边界出发出发形成三角形面片条形成三角形面片条v1v3v2v4v0v5v6v7v82022-6-9Tsinghua
26、University, Jun-Hai Yong51边界法边界法:举例举例 分离三角形面片条分离三角形面片条v1v3v2v4v0v5v6v7v82022-6-9Tsinghua University, Jun-Hai Yong52边界法边界法:举例举例 从从边界边界出发出发形成三角形面片条形成三角形面片条v1v3v2v4v0v5v6v72022-6-9Tsinghua University, Jun-Hai Yong53小结小结 边界法边界法 三角形面片条表示方法三角形面片条表示方法2022-6-9Tsinghua University, Jun-Hai Yong54带标志位的三角形面片条表示
27、方法带标志位的三角形面片条表示方法 从边界出发，逐层往内形成并划分三角从边界出发，逐层往内形成并划分三角形面片条形面片条 封闭网格封闭网格 取任意一个顶点作为边界取任意一个顶点作为边界2022-6-9Tsinghua University, Jun-Hai Yong55带标志位的三角形面片条表示方法带标志位的三角形面片条表示方法 R表示开始表示开始 F表示去掉前一个三角形的第一个顶点，然后再加入一表示去掉前一个三角形的第一个顶点，然后再加入一个新顶点个新顶点 M表示去掉前一个三角形的第二个顶点表示去掉前一个三角形的第二个顶点(即中间的顶即中间的顶点点) ，然后再加入一个新顶点，然后再加入一个新
28、顶点R0, F1, F2, F3v1v3v2v0R1, M0, M2, M3v1v3v2v02022-6-9Tsinghua University, Jun-Hai Yong56带标志位的三角形面片条表示方法带标志位的三角形面片条表示方法 实例实例从这里开始从这里开始v1v3v2v4v0v5v6v7v8v10v9v11v14v13v12v152022-6-9Tsinghua University, Jun-Hai Yong57带标志位的三角形面片条表示方法带标志位的三角形面片条表示方法 结果结果: R0, F4, F5, M1, F6, F2, F7, F3, F8, M11, F15, F1
29、4, M10, F13, F9, F12, F4, M5, M10, F6, F11, F7从这里开始从这里开始v1v3v2v4v0v5v6v7v8v10v9v11v14v13v12v152022-6-9Tsinghua University, Jun-Hai Yong58本讲总体纲要本讲总体纲要 网格网格 网格压缩网格压缩 网格简化网格简化 对连接关系的压缩对连接关系的压缩 对几何数据的压缩对几何数据的压缩2022-6-9Tsinghua University, Jun-Hai Yong59对几何数据的压缩算法对几何数据的压缩算法: 参考文献参考文献 O. Devillers and P-M
30、. Gandoin. Geometric Compression for Interactive Transmission. IEEE Visualization Conference Proceedings, pages 319-326, 2000.2022-6-9Tsinghua University, Jun-Hai Yong60三角形网格的表示三角形网格的表示 顶点：顶点： v1(x1, y1, z1)T v2(x2, y2, z2)T v3(x3, y3, z3)T v4(x4, y4, z4)T 面：面： f1(v1, v3, v2) f2(v1, v2, v4) f3(v2, v
31、3, v4) f4(v1, v4, v3)v1v2v3v4f1f2f3f42022-6-9Tsinghua University, Jun-Hai Yong61顶点坐标顶点坐标 顶点坐标顶点坐标 IEEE 64-double (64位位) IEEE 32-float (32位位) 16位位 8 位位 示例示例 v(1.442232, 1.334423, 0.897606) v(1.4422, 1.3344, 0.8976)2022-6-9Tsinghua University, Jun-Hai Yong62空间分割法空间分割法 坐标值坐标值*系数系数整数整数 排序排序 空间分割空间分割2022
32、-6-9Tsinghua University, Jun-Hai Yong63空间分割法空间分割法: 一维情形一维情形 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15881644441111111111111111222222222022-6-9Tsinghua University, Jun-Hai Yong64空间分割法空间分割法: 复杂度分析复杂度分析 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 不用空间分割分不用空间分割分: 共需共需 4位位*16=64位位88164
33、4441111111111111111222222222022-6-9Tsinghua University, Jun-Hai Yong65空间分割法空间分割法: 复杂度分析复杂度分析 共需共需: 31位位5位位4位位=4位位*(2-1)6位位=3位位*(4-2)8位位=2位位*(8-4)8位位=1位位*(16-8)881644441111111111111111222222222022-6-9Tsinghua University, Jun-Hai Yong66空间分割法空间分割法: 一维情形示例一维情形示例1 0, 1, 2, 3, 4, 6, 7, 8, 9, 11 空间分割法表示及其复
34、杂度分析空间分割法表示及其复杂度分析37104303111011110111221221空间复杂度分析空间复杂度分析: 不采用空间分割法不采用空间分割法: 40位位 采用空间分割法采用空间分割法: 27位位 5位位 4位位=4位位*1 6位位=3位位*2 6位位=2位位*3 6位位=1位位*62022-6-9Tsinghua University, Jun-Hai Yong67空间分割法空间分割法: 一维情形示例一维情形示例2 结果结果?471134040111111111112122220, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11空间复杂度分析空间复杂度分析: 不采用空
35、间分割法不采用空间分割法: 44位位 采用空间分割法采用空间分割法: 27位位 5位位 4位位=4位位*1 6位位=3位位*2 6位位=2位位*3 6位位=1位位*62022-6-9Tsinghua University, Jun-Hai Yong68空间分割法空间分割法: 二维情形二维情形 如何推广如何推广?72022-6-9Tsinghua University, Jun-Hai Yong69空间分割法空间分割法: 二维情形二维情形 分割分割4372022-6-9Tsinghua University, Jun-Hai Yong70空间分割法空间分割法: 二维情形二维情形 分割分割4371
36、2402022-6-9Tsinghua University, Jun-Hai Yong71空间分割法空间分割法: 二维情形二维情形 分割分割01113143712402022-6-9Tsinghua University, Jun-Hai Yong72空间分割法空间分割法: 二维情形二维情形 分割分割010110211001113143712402022-6-9Tsinghua University, Jun-Hai Yong73练习练习 将空间分割法推广到三维情形将空间分割法推广到三维情形2022-6-9Tsinghua University, Jun-Hai Yong74Thank Yo
37、u Because of you and me,this world becomes so wonderful. 本课件包含了很多从网络上下载的资源本课件包含了很多从网络上下载的资源 这里向这些课件的作者表示深深的谢意这里向这些课件的作者表示深深的谢意 请记住他们的辛勤工作请记住他们的辛勤工作Have a good day.2022-6-9Tsinghua University, Jun-Hai Yong75雍俊海编写过的教材和教参雍俊海编写过的教材和教参1. 雍俊海雍俊海. 计算机动画算法与编程基础计算机动画算法与编程基础. 北京北京: 清华大学清华大学出版社出版社. 2008. 2. 雍俊
38、海雍俊海. Java程序设计程序设计. 北京北京: 清华大学出版社清华大学出版社. 2008. 3. 雍俊海雍俊海. Java程序设计教程程序设计教程(第第2版版). 北京北京: 清华大学出清华大学出版社版社. 2007. 4. 雍俊海雍俊海. Java程序设计习题集程序设计习题集(含参考答案含参考答案). 北京北京: 清华清华大学出版社大学出版社, 2006. 5. 雍俊海雍俊海. Java程序设计程序设计. 北京北京: 清华大学出版社清华大学出版社. 2004. 2022-6-9Tsinghua University, Jun-Hai Yong76雍俊海编写过的教材和教参雍俊海编写过的教材
39、和教参 雍俊海雍俊海. 计算机动画算法与编程基础计算机动画算法与编程基础. 北京北京: 清华大学清华大学出版社出版社. 2008.2022-6-9Tsinghua University, Jun-Hai Yong77雍俊海编写过的教材和教参雍俊海编写过的教材和教参 雍俊海雍俊海. Java程序设计程序设计. 北京北京: 清华大学出版社清华大学出版社, 2008.2022-6-9Tsinghua University, Jun-Hai Yong78雍俊海编写过的教材和教参雍俊海编写过的教材和教参雍俊海雍俊海. Java程序设计教程（第程序设计教程（第2版）版）. 北京北京: 清华大学出版社清华大学出版社, 2007.2022-6-9Tsinghua University, Jun-Hai Yong79雍俊海编写过的教材和教参雍俊海编写过的教材和教参 雍俊海雍俊海. Java程序设计习题程序设计习题集（含参考答案）集（含参考答案）.清华大学出版社清华大学出版社, 2006.2022-6-9Tsinghua University, Jun-Hai Yong80雍俊海编写过的教材和教参雍俊海编写过的教材和教参 雍俊海雍俊海. JAVA程序设计程序设计. 北京北京: 清华大学出版社清华大学出版社. 2004.
