第 11 讲：多边形网格与几何处理

网格要同时回答两类问题：

• 几何：顶点在哪里。
• 连接关系：哪些顶点、边和面彼此相邻。

只为显示，顶点与三角形索引已经够用；一旦要编辑、细分或简化，邻接查询就成为核心。

1. 合法多边形网格

多边形面由有序顶点环构成，顺序定义朝向。网格中任意两个面的交集应为空、一个共享顶点或一条完整共享边，不能在面内部随意穿插。

三角网格的几何是顶点坐标，连接关系是每个三角形的三个顶点索引。统一绕序可让法线方向一致。

2. 流形、边界与亏格

二维流形的局部邻域像一个圆盘；边界点的邻域像半圆盘。对流形网格：

• 内部边恰好邻接两个面。
• 边界边只邻接一个面。
• 非流形边可能邻接三个或更多面。

闭合、无自交的可定向流形把空间分成内部和外部。亏格 $g$ 直观上是“洞的个数”，闭合多边形网格满足 Euler–Poincaré 公式

$$V-E+F=2-2g.$$

它既是理论性质，也是检查网格拓扑是否异常的快速工具。大规模闭合三角网格通常有 $F\approx2V$、$E\approx3V$。

3. 数据结构的取舍

Triangle List 为每个三角形重复存三份顶点，渲染简单但浪费空间。Indexed Face Set 把顶点位置和面索引分开，OBJ 等格式常用这种方式；然而“某顶点有哪些邻点”没有显式保存，直接搜索可能是线性时间。

面邻接、Winged Edge 等结构显式存更多关系。半边结构则把一条无向边拆成方向相反的两条半边：

一条半边通常保存：

• origin：起点顶点。
• twin：同一无向边的反向半边。
• next：同一面边界上的下一条半边。
• face：左侧所属面。

顶点和面各保存一条关联半边，就能沿 next 绕面，沿 twin 与 next 绕顶点 one-ring。在顶点度数有界时，大多数邻域查询可视为常数时间。

代价是结构更大，且 edge flip、split、collapse 必须完整更新一串指针；漏改一个关系会破坏整个拓扑。

4. 三种局部边操作

• Edge flip：两个相邻三角形共享边换成另一条对角线，顶点数和面数不变。
• Edge split：在边上插入新点，并拆分邻接三角形。
• Edge collapse：把一条边两端合成一个点，删除退化面。

细分、简化和重网格化都能用这些局部操作组合实现。

5. Loop 三角网格细分

Loop subdivision 每轮先把每个三角形拆成四个，再更新新旧顶点位置。

内部边 $(a,b)$ 的新顶点常用

$$\mathbf v_{new} =\frac38(\mathbf a+\mathbf b) +\frac18(\mathbf c+\mathbf d),$$

其中 $\mathbf c,\mathbf d$ 是相邻两个三角形的对顶点。旧顶点按其度数和 one-ring 邻点加权更新。规则反复执行后趋向光滑极限面；不同边界和异常度顶点需用专门权重。

从边操作看，可以先 split 原网格所有边，再 flip 连接一新一旧顶点的部分新边，最后更新位置。

6. Catmull–Clark 一般网格细分

Catmull–Clark 适用于任意多边形网格：

1. 每个面生成 face point。
2. 每条边生成 edge point。
3. 按邻接面、边与旧顶点更新 vertex point。
4. 每个原面重连为若干四边形。

规则反复执行后通常得到四边形主导的光滑曲面。尖锐折痕若不特别标记，会在细分中逐渐被抹平。

7. QEM 网格简化

简化希望减少面数，同时保留形状。边折叠后把两个端点替换成 $\mathbf v'$，几何误差可近似为它到邻接面平面的平方距离之和。

平面 $ax+by+cz+d=0$ 写成齐次向量 $\mathbf p=(a,b,c,d)^T$，点 $\bar{\mathbf v}=(x,y,z,1)^T$ 到该平面的平方代价是

$$(\mathbf p^T\bar{\mathbf v})^2 = \bar{\mathbf v}^T (\mathbf p\mathbf p^T) \bar{\mathbf v}.$$

把邻接面矩阵相加得到顶点 quadric $Q$。折叠一条边时令

$$Q'=Q_1+Q_2, \qquad \Delta(\mathbf v')=\bar{\mathbf v}'^TQ'\bar{\mathbf v}'.$$

若能解出最小值位置就用它，否则可在两端点和中点中选代价最小者。把所有候选边放入优先队列，反复折叠代价最小且不破坏拓扑的边。

8. 各向同性重网格化

简化改变面数，重网格化更关注采样质量。理想三角形尽量接近等边、边长接近目标值、内部顶点度数接近 $6$。

典型循环为：

1. split 过长边。
2. collapse 过短边。
3. flip 能改善度数或 Delaunay 性质的边。
4. 对顶点做切平面内的平滑移动，并投回原表面。

这说明网格处理不是“套一个公式”，而是几何误差、拓扑合法性和元素质量之间的持续折中。