• 局部自适应的网格划分 网格简化
• 多边形面片的形状
• 目的2：三角网格四边形网格
重新网格化的方法
1. 在参数域上操作 2. 在曲面上操作
网格曲面的参数化
参数化-曲面上一点和平面上一点对应
参数化方法的选择:不同的映射函数
模型的区域片集(atlas)
基于参数化的重新网格化方法
1.划分成一些曲面区域 2. 在参数域内选取等参线 3.相邻区域边界处的拼接
2）曲率线采样，求出曲率线的交点，连成多 边形网格
• 曲率线采样准则
• 对一条极大（小）主曲率线，距离相邻的另一条 极大（小）主曲率线的距离为
（
极限情况下，得到的四边形片的长宽比
）
重新网格化的关键问题之一：采样
Centroidal Voronoi Tessellation
Voronoi 图
(Lmin, Lmax)
各向异性的多边形重新网格化方法举例
曲率：密切圆的半径
密切圆：极限意义下经过曲线上一点和旁边两个点的圆
法曲率
The curvature is taken to be positive if the curve turns in the same direction as the surface's chosen normal, and otherwise negative.
重新网格化的质量 • 顶点位置的摆放：与形状适应
顶点密度的控制： 均匀分布和局部自适应的分布
各向异性的多边形网格
各向同性的网格化方法举例
目标： 1. 边长尽量相等 去除短边 去除长边 2. 顶点的度相等 3. 顶点的分布均匀
算法
设定边长度Lmax, Lmin，循环执行以下操作 1. 2. 3. 4. 5. 对长度大于Lmax的边，做Edge split 对长度小于Lmin的边，做Edge Collapse 尝试Flip edge ，得到度为6的顶点 移动顶点的位置 顶点投影到原曲面上
• Catmull-Clark 细分曲面 • Doo-Sabin 细分曲面 • Loop 细分曲面
Doo-Sabin细分曲面
F-face
E-face
V-face
• 为每一个n个顶点的面， 计算出n个新的顶点
Doo and Sabin
Catmull and Clark
ቤተ መጻሕፍቲ ባይዱ
• 构造F-face
• 构造E-face
多边形网格建模
网格曲面
多边形网格（V,E） • V ： 顶点位置 • E: 顶点的连接关系
多边形网格
• 顶点（vertex） • 边 （edge） • 多边形面片(face)
网格的数据结构
查询操作
• • • • • 一个顶点相邻的面？ 一个顶点相邻的边？ 一条边相邻的面？ 一个面所有的边？ 一个面相邻的面？
• 给一些种子点 • 平面的区域划分
• 重心Voronoi 图：一个区域的重心是种子点
• Centroidal Voronoi Tesselation (CVT)
重心 Voronoi 图的生成
1. 2. 3. 4. 给出一些种子点 生成一般Voronoi 图（区域划分） 为每个区域计算重心 以重心为种子点重新生成 Voronoi图, goto step 3 5. 直到收敛
细分曲面
1. 用网格定义的光滑曲面 2. 用某种规则，不断细化多边形网格，在极 限时得到光滑曲面
细分曲面
细分曲面的特点
容易实现，计算效率高 能表达任意拓扑结构的形状 数值上稳定 能表达曲面特征 （尖角，折痕等） • 局部细化 • • • •
细分曲面的种类
• • • • 细分规则的不同 产生的网格类型（四边形，三角形） 逼近或插值 极限曲面的光滑性（C0,C1,C2…）
•新的边顶点
•新的顶点顶点
n=3 β＝ ３／１６ • ｎ＞３ β ＝1/n (5/8 - (3/8 + 1/4 cos(2π / n))2)
•
Loop 细分曲面
新的顶点顶点 新的边顶点
重新网格化
• 输入：网格M • 输出：网格N 目的1: 得到质量更好的网格
• 去噪音，提高网格的光滑性
• 曲面上的Voronoi图生成：测地距离
• 如果原顶点是边界点，构造的新顶点为
• V1，V2是跟S相邻的边界顶点
Catmull-clark 细分曲面
网格构造 1. 一个新的面顶点和与包围该面的新的边顶 点连接 2. 一个新的顶点顶点和与该顶点相邻的新的 边顶点连接
Loop 细分曲面
• 三角形网格 • 每一步，一个三角形面片分成4个三角形面 片
半边结构
• 顶点 • 面 • 半边
• 半边
//该半边指向的顶点 //相对的半边 //该半边的相邻面 //包围同一个面的下一个半 边
• 顶点
//从这个顶点出发的一 个半边
• 面
//包围这个面的一个半边
查询操作举例
一个半边edge相邻的顶点或者面?
访问一个面face 的左右半边？
访问一个顶点相邻的边和面？
• 构造V-face
Catmull-Clark 细分曲面
• 每个面构造一个新的顶点Pnew face， 组成这个面的顶点的平均
• 每条边构造一个新的顶点 ：边的顶点和相 邻面的新顶点的平均
• 每个顶点构造一个新的顶点: Q 2 R ( n − 3) S ；
n + n + n
Q 是该顶点相邻的面的新顶点的平均 R 是该顶点的相邻边的中点的平均 S 是原顶点 n 是该顶点相邻的边的数目
主曲率和主曲率方向
最大和最小的法曲率方向称为主曲率方向，对应的曲率 大小 (k1, k2) 为主曲率。
脐点：曲面上法曲率恒等的点
Gaussian 曲率: k1 * k2 可以衡量曲面局部的凹凸
曲率线
曲率线上点的切向与主曲率方向一致
基于曲率线的各向异性多边形网格化方法
1）计算网格顶点的主曲率方向