第 8 章 多边形网格

摘要：本章讲解计算机图形学与几何处理的核心数据表示——多边形网格。内容涵盖：为什么 GPU 只画三角形、网格的数学定义（单纯复形）、关键拓扑公式（欧拉特征、平均顶点度、Poincaré–Hopf 约束）、离散高斯曲率（角亏）的推导、网格质量度量，以及半边结构、生成 → 修复 → 简化 → 法向一致化的完整实现流水线，最后给出 FreeCAD 导出 STL 的实战示例与常见避坑清单。

一、背景与动机

我们先问一个最实际的问题：为什么 GPU 永远只在画三角形？ 无论你用 NURBS 曲面还是 CSG 实体建模，最后送到显卡里的，一定是一堆三角形。原因很朴素——光栅化硬件只对“三个顶点定义一个平面片”这种最简单的图元高效。于是整个产业形成了一个事实链条：

精确模型（B-Rep / CSG）→ 离散化（tessellation）→ 多边形网格 → 光栅化渲染 / 切片打印

多边形网格（polygon mesh） 就是用平面多边形（绝大多数是三角形或四边形）的集合去逼近一张曲面。它是计算机图形学的通用货币——一切最终都要变成网格。

那么痛点在哪里？精确表示（参见 01-BRep边界表示.md）虽然无损、可参数化修改，但不能直接被 GPU 渲染，也不能被 3D 打印切片器直接消费。我们要的不是“数学上精确”，而是“能被机器快速吃进去的离散近似”。网格正是这座桥梁，但它带来一个根本矛盾：用有限个平面片逼近曲面，误差永远存在，只能靠增加面数来换精度。
理解了这一点，后面所有的数学（拓扑、曲率、质量度量）和工程（数据结构、流水线、修复）就都有了方向：它们全是为“如何用尽量少的面、把误差控制在可接受范围”服务的。

下面这张示意图展示了一个由 4 个三角形组成的简单三角网格，以及半边结构中 twin、next、prev 三种指针的关系。图中实心圆点 v0~v4 是顶点，实线是边，虚线箭头表示半边指针的指向：

        v1
       /|\
      / | \
     /  |  \
    /   |   \
   /    |    \
  /     |     \
 v2-----v3-----v4
  \     |     /
   \    |    /
    \   |   /
     \  |  /
      \ | /
       \|/
        v0

面 F0 = (v1, v3, v2)    面 F1 = (v1, v4, v3)
面 F2 = (v2, v3, v0)    面 F3 = (v3, v4, v0)

以面 F0 与 F1 的公共边 (v1, v3) 为例，半边结构把这条无向边拆成两条有向半边：

• h1：从 v1 指向 v3，属于面 F0；
• h2：从 v3 指向 v1，属于面 F1。

它们互为 twin。沿面 F0 逆时针绕行，h1.next 指向 v3 → v2 的半边，h1.prev 指向 v2 → v1 的半边；同理，沿面 F1 逆时针绕行，h2.next 指向 v1 → v4 的半边，h2.prev 指向 v4 → v3 的半边。于是：

• twin 让跨面邻接（找一条边的两个邻面）变成 $O(1)$；
• next / prev 让面内绕行（遍历一个面的所有顶点）变成 $O(1)$。

这正是 4.1 节半边结构 C++ 实现中 faceVertices 函数沿 next 走一圈的原理。

二、核心概念与原理

我们先给网格一个最朴素的数学定义。一张网格就是三个集合：
M=(V,E,F),V={pi∈E3}i=1n,F⊆{(i1,…,ik)} \mathcal{M} = (V, E, F),\qquad V = \{\mathbf{p}_i\in\mathbb{E}^3\}_{i=1}^{n},\quad F \subseteq \{(i_1,\dots,i_k)\} M=(V,E,F),V={pi​∈E3}i=1n​,F⊆{(i1​,…,ik​)}

• $V$ 是顶点位置集合；
• $E$ 是边；
• $F$ 是面，每个面记成一组顶点下标。

定义（抽象单纯复形）：三角网格的严格定义是抽象单纯复形（abstract simplicial complex） $K$——一个有限集族，对子集封闭，即 $\sigma \in K,\tau \subseteq \sigma \Rightarrow \tau \in K$。几何实现还要求单形只在公共面处相交（无自交）。

换句话说，“三角形”是最基本的单形（simplex）：点（0-单形）、边（1-单形）、三角形（2-单形）层层构成，且任意两个单形要么不相交、要么共享一个完整低维单形。这就是为什么三角网在数学上如此干净。
接下来看网格的几个分类维度，它们决定了后面用什么算法：

• 面元类型：三角形（渲染友好）/ 四边形（建模与细分友好，影视行业用 quad-dominant）；
• 流形性：每边恰 2 面（流形）vs 允许 T 接头（非流形）；
• 水密性：封闭（watertight，3D 打印必须）vs 带边界；
• 定向性：法向可定向且一致 vs 不一致；
• 属性：位置、法向、UV、颜色、骨骼权重，可挂在顶点、面或**角（corner，用于硬边与 UV 缝）**上。

一个类比：把网格想成一张渔网。顶点是网结，边是网线，面是网眼。流形性就是“每条网线只连接两块网布”，水密性就是“整张网没有破洞”。

还有一个关键区分：四边形主导网格（quad mesh） 在影视/游戏建模里比三角形更受青睐——（a）细分曲面（Catmull-Clark，参见 10-细分曲面.md）要求四边形；（b）四边形边流（edge flow）对应形变主方向，骨骼动画不会塌陷；（c）UV 展开更规则。

三、关键公式与推导

3.1 单纯复形与欧拉特征

对一张封闭三角网，每条边属于 2 个面、每个面有 3 条边，立刻得到两个恒等式：

$$3F=2E⟹F\approx 2V,E\approx 3V$$

把顶点、边、面数代入含边界与亏格的欧拉公式：

$$\chi (\mathcal{M})=V-E+F=2-2g-b$$

其中 $g$ 是亏格（手柄数），$b$ 是边界环数。对球面（$g=0,b=0$）有 $\chi =2$；对环面（$g=1$）有 $\chi =0$。

推一步：把 $E\approx 3V$ 代入，得到封闭三角网的平均顶点度：

$$\bar{d}=\frac{2E}{V}=6-\frac{6\chi }{V}\stackrel{V\to \infty }{\to }6$$

结论很直观——“理想三角网每个点连 6 个邻居”。四边网格则是 4 个。偏离该值的点叫奇异点（irregular vertex），是细分曲面与四边网格生成质量的核心指标。更有意思的是四边网格奇异点受 Poincaré–Hopf 定理 约束：

$$\sum _i\mathrm{ind}(v_i)=\chi (\mathcal{M}),\mathrm{ind}(v)=1-\frac{d(v)}{4}$$

即在球面（$\chi =2$）上四边网格必然含奇异点（如立方体的 8 个 3 度点），不可能全正则——这是四边重网格化的根本约束。

3.2 离散高斯曲率：角度缺损公式的由来

经典微分几何的曲率定义在分段线性的网格上失效了，我们需要把它重新定义。核心结论是——离散高斯曲率 = 角亏（angle deficit），这是离散 Gauss–Bonnet 定理的精确形式，不是近似：

$$K_i=\frac{1}{A_i}(2\pi -\sum _{f\ni i}{\theta }_i^f)$$

下面一步一步推导它为什么长这样。

1. 连续情形的直觉：在光滑曲面上，绕一个顶点画一个小测地圆盘，沿边界走一圈，切线转过的总角度是 $2\pi$（闭合回路）。高斯-博内定理告诉我们，圆盘内"累计的曲率"加上边界的测地曲率积分等于 $2\pi \chi$（此处是局部小圆盘，$\chi =1$）。

2. 离散化处的关键观察：网格上每个三角形内部都是完全平的，内蕴高斯曲率为 0。曲率不会平摊在面上，而是全部集中在顶点。

3. 绕顶点走一圈：从顶点 $v$ 出发，依次穿过它周围的三角形。在每一个三角形内部，曲面是平面，切线转角"本该"累计到 $2\pi$ 才闭合。但每个三角形在顶点处只贡献一个内角 ${\theta }_i^f$。把所有相邻面的内角加起来得 ${\sum }_f{\theta }_i^f$，它小于 $2\pi$ 的部分，就是这块"被折起来的角度"——这就是角亏：

$$\text{角亏}(v)=2\pi -\sum _{f\ni i}{\theta }_i^f$$

4. 它正好等于该顶点的积分高斯曲率。把每个顶点的角亏加起来，离散 Gauss–Bonnet 给出全局恒等式：

$$\sum _i{K}_i{A}_i=\sum _i(2\pi -\sum _{f\ni i}{\theta }_i^f)=2\pi \chi (\mathcal{M})$$

注意：等式除以面积 $A_i$ 得到的 $K_i$ 是曲率密度（每单位面积）；若只关心"顶点处累计了多少曲率"，直接用角亏本身即可。这就是 $\kappa (v)=2\pi -{\sum }_i{\alpha }_i$ 的完整由来——${\alpha }_i$ 即各相邻面在顶点处的内角。

3.3 网格质量度量

对有限元仿真（FEA），网格质量直接决定刚度矩阵的条件数。常用度量：

• 纵横比（aspect ratio）：$AR=\frac{{\ell }_{\max }}{{\ell }_{\min }}$，即最长边与最短边之比。等边三角形最优（$=1$），细长三角形最差。
• 径比（radius ratio）：$\rho =\frac{r_{\text{in}}}{r_{\text{circ}}}$（内切圆/外接圆半径比），等边三角形归一化后为 1。
• 最小角 ${\theta }_{\min }$：Delaunay 三角化最大化最小角，因为 FEM 收敛性对最小角极敏感（条件数 $\sim 1/\sin {\theta }_{\min }$）。
• 雅可比行列式（Jacobian ratio）：高阶单元在高斯点处映射的雅可比 $\det J$ 必须处处 $>0$ 才是有效单元；雅可比比定义为

$$\frac{{\min }_{\xi }\det J}{{\max }_{\xi }\det J}$$

它衡量单元从参考空间到物理空间的映射是否退化/翻转——小于 0 意味着单元自交，仿真必崩。

四、具体实现步骤

4.1 数据结构选择——半边结构（half-edge）

面-顶点表（indexed face set，OBJ/STL 用）查询邻接要 $O(n)$ 重建，做几何处理太慢。半边结构是几何处理的标准答案，它把每条无向边拆成两条有向半边：

每个半边（half-edge）记录：
  origin      → 起点顶点
  twin        → 对偶半边（反向那条）
  next        → 同面内下一条半边
  prev        → 同面内上一条半边
  face        → 所属面
  edge        → 所属无向边

有了这个组织，所有邻接查询都是 $O(1)$：一个面的三个顶点（沿 next 走）、一个顶点的出边（origin 是该点的半边）、一条边的邻边（twin 的 next）。OpenMesh、CGAL、libigl 都用它。

下面给出一个最小但完整的 C++ 实现，包含 HalfEdge、Vertex、Face 三个类的字段定义，以及沿 next 遍历一个面所有顶点的函数：

#include <vector>

// 前向声明：三个类互相引用，必须用指针/索引
struct HalfEdge;
struct Vertex;
struct Face;

// 顶点：只存位置与一条出边
struct Vertex {
    double x, y, z;        // 三维坐标
    HalfEdge* out;         // 以该顶点为起点的任意一条半边（用于遍历邻域）
};

// 面：只存一条半边，其余半边沿 next 可达
struct Face {
    HalfEdge* halfEdge;    // 该面的任意一条半边（入口）
};

// 半边：核心拓扑单元
struct HalfEdge {
    Vertex*   origin;      // 起点顶点
    HalfEdge* twin;        // 对偶半边（反向那条，同一条无向边的另一侧）
    HalfEdge* next;        // 同面内下一条半边（逆时针）
    HalfEdge* prev;        // 同面内上一条半边（顺时针）
    Face*     face;        // 所属面
    int       edgeId;      // 所属无向边的编号（可选，用于边属性）
};

// 沿 next 遍历一个面的所有顶点（逆时针）
std::vector<Vertex*> faceVertices(Face* f) {
    std::vector<Vertex*> verts;
    HalfEdge* h = f->halfEdge;   // 从入口半边出发
    do {
        verts.push_back(h->origin);  // 收集起点顶点
        h = h->next;                 // 沿 next 走到下一条半边
    } while (h != f->halfEdge);      // 回到入口即绕完一圈
    return verts;
}

要点：twin 让跨面邻接（如找一条边的两个邻面）变成 $O(1)$；next/prev 让面内绕行变成 $O(1)$；origin 让顶点到出边的映射变成 $O(1)$。上面 faceVertices 正是“一个面的三个顶点（沿 next 走）”的直接实现。

FreeCAD 的 Mod/Mesh/App/Core/MeshKernel 用的是面邻接方案（点数组 + 面数组 + 每面 3 个邻居面索引 _aulNeighbours），比半边省内存、三角网够用，但拓扑编辑灵活性不如半边。

4.2 核心算法流水线

① 导入 / 从 B-Rep 生成网格（tessellation）
OCCT 的 BRepMesh_IncrementalMesh 流程：逐面在参数域按曲率自适应采样（弦高准则 + 角度偏差准则）→ 约束 Delaunay 三角化 → 映射回三维 $p=S(u,v)$ → 边一致性 stitching（共享边必须用同一套采样点，否则漏水的第一原因）→ 校验流形/定向/水密。调 FreeCAD 的 Deflection（弦高）与 AngularDeflection（角度）就是在调采样密度。

② 网格修复（逆向/扫描/打印必备）

缺陷	检测	修复
孔洞	边界环提取（边只属 1 面）	环填充 / 平滑填充
非流形边	边面数 > 2	切开复制顶点
法向不一致	BFS 传播 + 一致性检查	翻转；全局用体积符号或射线投票
自交	BVH 三角-三角求交	局部重网格 / 绕数重构
重复顶点	空间哈希（容差网格）	焊接 weld

现代终极方案：体素化/绕数场 → 重提等值面（TetWild、Manifold、Blender Voxel Remesh），用一次有损重建换绝对水密，已成 3D 打印预处理主流。

③ 法向一致化 + 简化
法向 BFS 只能做到局部一致，全局朝内/朝外要靠体积符号或射线投票（非水密模型用绕数）。简化常用 QEM（Garland–Heckbert）：每个顶点关联一个 $4\times 4$ 二次误差矩阵 $Q_v={\sum }_{f\ni v}{\mathbf{q}}_f{\mathbf{q}}_f^{\top }$（${\mathbf{q}}_f$ 为面平面 $(a,b,c,d)$），边折叠代价 $\mathrm{cost}(u,v)={\bar{\mathbf{v}}}^{\top }(Q_u+Q_v)\bar{\mathbf{v}}$，用优先队列按 cost 依次折叠，复杂度 $O(n\log n)$。

下面用 Python 伪代码展示 QEM 边折叠的主循环：

import heapq

# 1) 初始化：每个顶点关联一个 4x4 二次误差矩阵 Q
Q = {v: sum(plane_quadric(f) for f in faces_around(v)) for v in vertices}

# 2) 计算每条边的折叠代价，并放入最小堆
heap = []
for (u, v) in edges:
    cost, pos = edge_collapse_cost(u, v, Q[u] + Q[v])  # 最优位置 + 代价
    heapq.heappush(heap, (cost, u, v, pos))

# 3) 主循环：按代价从小到大折叠
while heap and target_faces_not_reached():
    cost, u, v, pos = heapq.heappop(heap)
    if not is_valid(u, v):          # 跳过已失效的边
        continue
    collapse(u, v, pos)             # 折叠：u 移到 pos，删除 v
    Q[u] = Q[u] + Q[v]              # 4) 更新受影响顶点的 Q 矩阵
    for w in neighbors(u):          # 重新计算邻边代价并入堆
        heapq.heappush(heap, (edge_collapse_cost(u, w, Q[u] + Q[w])[0], u, w, ...))

4.3 避坑清单

• 顶点焊接容差：过大粘连薄壁，过小留缝——按局部特征尺寸自适应。
• STL 先天缺陷：无索引（顶点重复 3 倍）、可能法向与绕序矛盾——导入时先焊接再校验法向，以绕序为准而非存储法向。
• 浮点精度：$10^7$ 面网格 float32 远离原点时相邻点会重合，需局部坐标系或 double。
• 简化保护特征：QEM 需给边界边、大二面角边加权重、UV 缝不可折叠。

五、实际应用示例

用一个最小但完整的例子串起流水线——在 FreeCAD 里把一个实体导出为 STL 并降面：

输入：一个 FreeCAD Part::Feature（如立方体或导入的 STEP）。

过程（Python 控制台）：

import Mesh
# 1) 从 B-Rep 离散化生成网格：弦高 0.1，角度偏差 0.5°
doc = App.activeDocument()
mesh = Mesh.Mesh()
mesh.harmonize([(doc.Box.Shape, 0.1, 0.5)])  # (shape, deflection, angular)
# 2) 修复：焊接重复顶点、统一法向
mesh.removeDuplicatedPoints()
mesh.harmonizeNormals()      # 法向一致化
# 3) 简化（QEM 思路）：导出前降低面密度
mesh.optimizeTopology()      # 拓扑优化
# 4) 写出
mesh.write("D:/out/model.stl")

输出：一个水密、法向一致、面数适中的 model.stl，可直接进切片器。若想进一步降面，可在 MeshLab 里用 Quadratic Edge Collapse Decimation（即 QEM）设目标面数。

检查清单：导入后验证 mesh.isSolid()（水密）、mesh.hasNonManifolds()（流形）、法向朝外。这正好对应第四节流水线的“生成→修复→简化→法向一致”。

六、小结与要点

记住什么

• 网格是 $(V,E,F)$ 的单纯复形，曲率集中在顶点，离散高斯曲率就是角亏 $K_i=2\pi -\sum {\theta }_i^f$。
• 欧拉特征 $\chi =2-2g-b$ 给出拓扑约束；理想三角网平均度 6。
• 半边结构让邻接查询 $O(1)$；FreeCAD 用面邻接的 MeshKernel。

适用场景：实时渲染、3D 打印（STL/3DML/AMF 事实标准）、CAE 前处理、逆向工程中间产物、医学/地理 TIN。

常见坑：

1. 网格是有损近似，面数 $\propto 1/\epsilon$——精度提 10 倍面数增 10 倍；
2. 无法逆向为精确 B-Rep，“STL 转实体”本质是重新建模；
3. 法向精度比位置低一阶，造成 Mach 带/光照瑕疵，需 Phong 着色遮掩；
4. 非流形、自交、孔洞极易破坏有效性，且无自动保证。

练习与思考

1. 取一个 $\chi =0$ 的环面三角网，验证 ${\sum }_i(2\pi -{\sum }_f{\theta }_i^f)=0$。若把其中一个顶点的内角都改成接近 $2\pi$，该处曲率会怎样变化？这说明角亏对哪种几何特征最敏感？
2. 为什么球面四边网格必有奇异点？若强行要求所有顶点度为 4，根据 Poincaré–Hopf，它的欧拉特征会被“逼”成多少？
3. 用 QEM 简化一个带圆孔的平板时，若不保护边界边，孔的形状会发生什么？如何用“给边界边加权”在数学上表达这个约束？

七、参考资料

• Botsch, M., Kobbelt, L., Pauly, M., Alliez, P., & Lévy, B. (2010). Polygon Mesh Processing. A K Peters/CRC Press. ——本书系统讲解网格的数学基础（单纯复形、欧拉特征、离散曲率）与半边结构、网格修复、简化等算法，与本文第二、三、四节内容一一对应，是深入理解多边形网格处理的权威教材。
• Garland, M., & Heckbert, P. S. (1997). Surface Simplification Using Quadric Error Metrics. SIGGRAPH '97. ——QEM 边折叠算法的原始论文，定义了二次误差矩阵 $Q_v$ 与折叠代价公式，正是本文 4.2 节「③ 法向一致化 + 简化」所采用的简化方法出处。
• CGAL 官方文档：Polygonal Mesh Processing（https://doc.cgal.org/latest/Polygon_mesh_processing/index.html） ——提供半边结构（HalfedgeDS）、网格修复、简化（surface_mesh_simplification）等工业级实现，对应本文 4.1 节半边结构与 4.2 节流水线的工程落地参考。
• OpenMesh 官方文档（https://www.graphics.rwth-aachen.de/software/openmesh/） ——开源半边结构网格库，其 Halfedge、Vertex、Face 设计与本文 4.1 节给出的 C++ 实现同源，适合作为动手实践与扩展阅读的起点。