跳到主要内容

多边形网格表示与数据结构:几何被组织的方式

图形学里绝大多数"物体"最终都变成一堆三角形。为什么是三角形?三点必共面、面积总非负、光栅化硬件天然支持。可如何存这些三角形——每个顶点的位置、哪些顶点组成面、面与面怎样相邻——决定了一个网格库的性能天花板和 API 上限。这篇讲的就是从最朴素的三角形汤到现代半边结构之间的取舍。

1. 从三角形汤到索引数组​

最原始的表示是三角形汤(triangle soup):一个数组存所有三角形,每个三角形直接展开成三个顶点位置。

tri[0] = {(x0,y0,z0), (x1,y1,z1), (x2,y2,z2)}
tri[1] = {(x3,y3,z3), (x4,y4,z4), (x5,y5,z5)}
...

问题一望而知:一个立方体 12 个三角形有 36 个顶点副本,但真实几何顶点只有 8 个。空间浪费不说,"这两个面共享一条边"这种关系彻底丢失。移动一个顶点要遍历所有面找同位置的副本,浮点误差让"同位置"这个判断都不可靠。

索引三角形表(indexed face set, IFS)是最广泛使用的折中方案:

V = [(x0,y0,z0), (x1,y1,z1), ..., (xN,yN,zN)]        // 顶点数组
F = [(0,1,2), (0,2,3), (1,4,2), ...] // 每面三个顶点索引

顶点位置唯一,面通过索引引用。OBJ、glTF、OpenGL 的 VBO+EBO、STL 二进制的一部分变种,全是这个模型。空间从 9F9F 降到 3V+3F3V + 3F,通常 F≈2VF\approx 2V(欧拉公式的推论),能省一半以上。

索引表已经能画图,但对几何处理(细分、简化、参数化、曲面细分)远远不够。原因是它单向:给一个面能找它的顶点,给一个顶点却难以找到"所有相邻面"或者"所有相邻顶点"。这些查询在索引表上都要遍历整个 F,O(F)O(F)。

2. 拓扑操作要求什么​

看几个几何算法就明白单向表示的痛点:

  • 法线计算(顶点法线 = 相邻面法线平均):需要"顶点 → 邻面"
  • 网格简化(边坍缩):删一条边,两端顶点合并,周围面重连——需要"边 → 两侧面 → 相邻边"
  • 细分:一个面的新顶点位置依赖邻面的顶点,需要"面 → 邻面"
  • 测地距离:从一个顶点向外 BFS,需要"顶点 → 一环邻居"

这些查询都要求 O(1)O(1) 或 O(deg⁡)O(\deg) 时间,deg⁡\deg 是顶点度数。索引表做不到。

3. Winged-Edge:以边为中心​

Baumgart 1975 年博士论文里的 winged-edge 是第一个系统化的多向邻接结构。核心是以边为记录单位,每条边存 8 项:

struct Edge {
Vertex *v_start, *v_end; // 两端点
Face *f_left, *f_right; // 左右面
Edge *e_prev_left, *e_next_left; // 左面上前一条、后一条边
Edge *e_prev_right, *e_next_right; // 右面上前一条、后一条边
};

一条边知道自己所有的"翅膀"(wings,共四条相邻边),故名 winged-edge。加上 V→EV\to E 和 F→EF\to E 各一根指针,就能在 O(1)O(1) 内完成所有邻接查询。

问题是:边没有方向。判断"左"和"右"必须先算法向 —— 你走这条边时哪边是左?如果一个算法从 v1v_1 走到 v2v_2,左右是一套;从 v2v_2 走到 v1v_1,左右反过来。代码里到处是 if edge.v_start == v 的分支,容易写错。

4. 半边(Halfedge):把每条边拆成两个方向​

Mäntylä 在 1988 年的《An Introduction to Solid Modeling》里把 winged-edge 改进成了半边结构。核心思想:把每条无向边拆成两条有向的半边,每个半边只属于一个面。

        v_start ●─────────────────→ ● v_end     (halfedge)
●←───────────────── ● (twin / opposite)

数据布局:

struct Halfedge {
Vertex *vertex; // 指向哪个顶点(一般是终点,也有实现选起点)
Halfedge *twin; // 反向半边(另一侧面的那条)
Halfedge *next; // 同一面上的下一条半边
Halfedge *prev; // 同一面上的上一条半边(可省,从 next 递推)
Edge *edge; // 所属无向边(可省)
Face *face; // 所属面
};

struct Vertex { Halfedge *outgoing; ... }; // 从这个顶点出发的任一半边
struct Face { Halfedge *inner; ... }; // 环绕这个面的任一半边

半边表的漂亮之处在于所有操作都是有向的、无歧义的。想遍历一个面的所有顶点:

h = face.inner
do {
print(h.vertex)
h = h.next
} while (h != face.inner)

想遍历一个顶点的所有邻边(一环遍历,one-ring):

h = vertex.outgoing
do {
print(h) // 出边
h = h.twin.next // 转到下一条出边
} while (h != vertex.outgoing)

twin.next 这个组合就是"绕着顶点转一圈"的核心。理解了它,一切一环邻居的算法都变成 10 行以内的循环。

内存代价:每条无向边两条半边,如果每条半边 4 个指针(vertex, twin, next, face),总共 8E8E 个指针。对于闭合三角网格 E=3VE=3V,也就是 24V24V 个指针,24 字节/顶点乘 8 字节 = 192 字节 / 顶点。位置本身只有 12 字节。所以半边只用于需要拓扑操作的中间表示,最终存盘/上 GPU 还是索引数组。

5. 边界与非流形​

半边默认假设网格是流形(manifold)——每条边恰好被两个面共享,每个顶点周围的面构成一个盘(顶点邻域同胚于圆盘)。真实模型不一定如此:

  • 有边界:布片、地形,边界边只有一个面。约定"边界半边"的 twin 存在但 face 是 null
  • 非流形边:一条边被三个及以上面共享,比如两个立方体沿一条棱粘起来。半边直接崩溃——twin 没有唯一选择
  • 非流形顶点:两个锥形共享一个顶点,一环邻域不是一个盘而是两个盘。绕一环走不完

工业界的应对:

  1. 建模阶段禁止非流形(Maya、Blender 默认 flag 提示)
  2. 用更一般的结构,比如 Radial Edge(Weiler 提出,一条边挂一串面)
  3. 修复:切开非流形处,复制顶点让每个"盘"独立

6. 面片方向一致性​

三角形的三个顶点排列顺序 (v0,v1,v2)(v_0, v_1, v_2) 通过右手法则定义法向:

n⃗=(v1−v0)×(v2−v0)∥(v1−v0)×(v2−v0)∥\vec n = \frac{(v_1-v_0)\times(v_2-v_0)}{\|(v_1-v_0)\times(v_2-v_0)\|}

顺时针(CW)和逆时针(CCW)的选择本身无所谓,但整个网格必须一致。相邻两个面沿共享边遍历时,若面 A 上是 v1→v2v_1\to v_2,那么面 B 上应该是 v2→v1v_2\to v_1——共享边被两个面用相反方向使用。半边结构里,一条边的两条半边天然反向,这个一致性自动成立。

如果一个网格的方向不一致(比如某个面被翻转了),会出现:

  • 光照突然从背面照亮,或者片段处理里背面剔除误伤
  • 体积计算得到负值
  • 半边结构无法从索引表正确重建 —— twin 匹配失败

修复方法:从一个种子面出发 BFS,每一步用共享边判断邻面方向,不一致就翻转。对每个连通分量各做一次。Möbius 带这种不可定向曲面无法一致定向,但工程模型里几乎不出现。

7. Euler 公式与网格合法性​

闭合三角网格满足 Euler 公式:

V−E+F=2−2gV - E + F = 2 - 2g

gg 是亏格(genus,"洞"的数量)。球面 g=0g=0、环面 g=1g=1。三角形每面 3 条边、每边被 2 面共享,所以 E=3F/2E = 3F/2,代入得 F=2V−4F=2V-4(球面情形)。用来做廉价合法性检查:读入 OBJ 后一算 V−E+FV-E+F,不是偶数直接报错。

8. 网格上的基本编辑操作​

半边结构让下面这些操作都变得优雅。以三角网格为例:

操作说明影响
Edge Split在一条边中点插入新顶点,把两侧三角形各切成两个+1V,+3E,+2F+1V, +3E, +2F
Edge Collapse把一条边缩成一个点,两个顶点合并−1V,−3E,−2F-1V, -3E, -2F
Edge Flip沿一条边把两个三角形组成的四边形翻另一条对角线拓扑不变
Vertex SplitEdge Collapse 的逆操作,一个点裂成两个Progressive Mesh 的基础

Edge Collapse 是网格简化(Garland-Heckbert QEM)的核心动作:每次坍缩一条误差最小的边,逐步降低面数。Edge Flip 是 Delaunay 三角化优化的基础:不满足空圆性质时翻边。这些都需要 O(1)O(1) 邻接查询,索引表做不到,半边做得到。

9. 现代变体与工程实践​

半边不是唯一选择。几种常见变种:

  • Directed Edges / Corner Table(Rossignac 2001):为每个"角"(面上的一个顶点位置)存 opposite、next、previous 三个整数索引。比半边省一半空间,但只支持三角网格
  • Face-Vertex Mesh(OpenMesh、CGAL Surface_mesh):面存顶点索引 + 顶点存邻面数组,混合表示。工程库里更常见
  • OpenVDB / OpenMesh / libigl:C++ 库各自的选择。libigl 用纯 Eigen::MatrixXi 做面表 + 辅助函数按需算邻接,Julia 风格,简单粗暴,对 GPU 友好

上 GPU 的时候,一切都要展平回索引数组:一个 VertexBuffer 存位置/法线/UV,一个 IndexBuffer 存三角形。半边只存在 CPU 侧的建模、编辑、模拟阶段。顶点处理里 GPU 拿到的永远是索引三角形。

10. 选型建议​

一句话总结不同场景:

  • 只读渲染、导出:索引数组
  • 需要邻接查询的几何算法(细分、简化、参数化):半边
  • 三角形专用、追极致内存:Corner Table
  • 允许非流形、CAD 实体建模:Radial Edge 或 B-Rep
  • 隐式几何(SDF、体素):不用网格,见 隐式建模与体素

再进一步的参数化表示(不用离散面片而用连续控制点)是另一大类,Bézier / B 样条 / NURBS 见 参数曲线与曲面。