计算机图形学：Mesh
第七章：Mesh
0 基本描述
- 网格有一系列的三角面片组成
- 三角面片包含三个点的索引
- 点索引可以在点表中找到相应的点
1 Tessellation
1.1 基础网格化方法（低效）
- 检测多边形的任意两顶点连线是否与任意边相交
- 如果相交则无法切割，否则可以切割，继续用该方法进行三角化.
1.2 Ear clipping
- 取相邻三个顶点i,i+1,i+2，检查线段[i, i+2]是否与边相交
- 如果没有相交则将该耳朵从多边形中去除，继续三角化
Subdivision(细分)
2.1 Loop Subdivision
- 每个边都会添加一个新节点，连接后一个三角形转变为四个三角形，同时更新每个原始顶点的位置
2.1.1顶点更新
如图（a）所示，新的顶点根据相邻点及自己的权重得到，n为相邻点数
p_{}^{k+1} = (1 - n\beta)p_{}^{k} + \sum_{i=0}^{n-1}\beta p_{i}^{k}\\ \ \\ \beta = \frac{\frac{5}{8} - (\frac{3}{8} + \frac{1}{4}cos\frac{2\pi}{n})^2}{n}\\
2.1.2新节点
p_{}^{k},p_{i}^{k}是两个端点，p_{i - 1}^{k},p_{i + 1}^{k}是两个相对顶点，如图（b）所示
p_{i}^{k+1} = \frac{3}{8}(p_{}^{k} + p_{i}^{k}) + \frac{1}{8}(p_{i - 1}^{k} + p_{i + 1}^{k})
2.2 Catmull-Clark subdivision
- 设四边形的四个顶点为v0、v1、v2、v3，则新增加 的顶点位置为v = 1/4*(v0 + v1 + v2 + v3)
- 设内部边的两个端点为v0、v1，与该边相邻的两个四边形顶点分别为v0、v1、v2、v3和v0、v1、v4、v5，则新增加 的顶点位置为v = 3/8*(v0 + v1) + 1/16*(v2 + v3 + v4 + v5)。
- 设内部顶点v0的相邻点为v1、v2，…，v2n，则该顶点更新后位置为v = \alpha v_0 + \frac{\beta}{n}\sum_{i=1}^{n}v_{2i} + \frac{\gamma}{n}\sum_{i=1}^{n}v_{2i-1}，其中α、β、γ分别为α = 1 - β - γ。
- 设边界边的两个端点为v0、v1，则新增加 的顶点位置为v = 1/2*(v0 + v1)。
- 设边界顶点v0的两个相邻点为v1、v2，则该顶点更新后 位置为v = 3/4 v0 + 1/8(v1 + v2)。
2.3 \bm{\sqrt{3}}Subdivision
- Different from Loop’s scheme Kobbelt, Kobbelt’s \bm{\sqrt{3}} scheme 3 scheme creates only 3 new triangles per-step
- It creates a new vertex (called mid-vertex) in the middle of each triangle, instead of a new vertex per edge.
为了得到更均匀分布的三角形，每个原始三角形的边都被翻转，使之连接两个相邻中间顶点而不是连接两个已经存在的旧顶点
2.3.1顶点更新
第一个式子为中间点的计算，第二个式子是三角形顶点的位置更新，第三个式子是\beta的计算
p_{middle}^{k+1} = \frac{p_{a}^{k} + p_{b}^{k} + p_{c}^{k}}{3}\\ \ \\ p_{}^{k+1} = (1 - n\beta)p_{}^{k} + \beta \sum_{i=0}^{n-1} p_{i}^{k}\\ \ \\ \beta(n) = \frac{4 - 2cos(\frac{2\pi}{n})}{9n}\\
3 Simplification(简化)
Approximating a given input mesh with a less complex but geometrically faithful representation
- remove reddundant(多余的) geometry
- reduce model size
- improve run-time performance
3.1 levels of detail (LOD)
- Topology (拓扑结构)：多边形网格的连接结构
- Genus（亏格）：网格表面孔洞的数目。如球或立方体为0，圆环为1
3.2 简化的基本算法
3.2.1 Vertex Decimation顶点删除
3.2.2 Edge Contraction边坍塌（边变成点）
3.2.3 面收缩（面变成点）
3.3 简化算法
3.3.1 Schroeder的局部判别准则
对于网格内部顶点v，记其周围相邻面片集为S，则该点的平坦性准则由下述的距离来描述：
d = |N\cdot(v - C)|\\ \ \\ N = \frac{\sum_{f\in S}^{} n(f) A(f)}{\sum_{f\in S}^{}}\\ \ \\ C = \frac{\sum_{f\in S}^{} c(f) A(f)}{\sum_{f\in S}^{}}\\
这里A(f)，c(f)，n(f)分别为三角面片的面积、中心和法向量