多边形网格表示与数据结构:几何被组织的方式
图形学里绝大多数"物体"最终都变成一堆三角形。为什么是三角形?三点必共面、面积总非负、光栅化硬件天然支持。可如何存这些三角形——每个顶点的位置、哪些顶点组成面、面与面怎样相邻——决定了一个网格库的性能天花板和 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 二进制的一部分变种,全是这个模型。空间从 降到 ,通常 (欧拉公式的推论),能省一半以上。
索引表已经能画图,但对几何处理(细分、简化、参数化、曲面细分)远远不够。原因是它单向:给一个面能找它的顶点,给一个顶点却难以找到"所有相邻面"或者"所有相邻顶点"。这些查询在索引表上都要遍历整个 F,。
2. 拓扑操作要求 什么
看几个几何算法就明白单向表示的痛点:
- 法线计算(顶点法线 = 相邻面法线平均):需要"顶点 → 邻面"
- 网格简化(边坍缩):删一条边,两端顶点合并,周围面重连——需要"边 → 两侧面 → 相邻边"
- 细分:一个面的新顶点位置依赖邻面的顶点,需要"面 → 邻面"
- 测地距离:从一个顶点向外 BFS,需要"顶点 → 一环邻居"
这些查询都要求 或 时间, 是顶点度数。索引表做不到。
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。加上 和 各一根指针,就能在 内完成所有邻接查询。
问题是:边没有方向。判断"左"和"右"必须先算法向 —— 你走这条边时哪边是左?如果一个算法从 走到 ,左右是一套;从 走到 ,左右反过来。代码里到处是 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),总共 个指针。对于闭合三角网格 ,也就是 个指针,24 字节/顶点乘 8 字节 = 192 字节 / 顶点。位置本身只有 12 字节。所以半边只用于需要拓扑操作的中间表示,最终存盘/上 GPU 还是索引数组。
5. 边界与非流形
半边默认假设网格是流形(manifold)——每条边恰好被两个面共享,每个顶点周围的面构成一个盘(顶点邻域同胚于圆盘)。真实模型不一定如此:
- 有边界:布片、地形,边界边只有一个面。约定"边界半边"的
twin存在但face是null - 非流形边:一条边被三个及以上面共享,比如两个立方体沿一条棱粘起来。半边直接崩溃——
twin没有唯一选择 - 非流形顶点:两个锥形共享一个顶点,一环邻域不是一个盘而是两个盘。绕一环走不完
工业界的应对:
- 建模阶段禁止非流形(Maya、Blender 默认 flag 提示)
- 用更一般的结构,比如 Radial Edge(Weiler 提出,一条边挂一串面)
- 修复:切开非流形处,复制顶点让每个"盘"独立
6. 面片方向一致性
三角形的三个顶点排列顺序 通过右手法则定义法向:
顺时针(CW)和逆时针(CCW)的选择本身无所谓,但整个网格必须一致。相邻两个面沿共享边遍历时,若面 A 上是 ,那么面 B 上应该是 ——共享边被两个面用相反方向使用。半边结构里,一条边的两条半边天然反向,这个一致性自动成立。
如果一个网格的方向不一致(比如某个面被翻转了),会出现:
- 光照突然从背面照亮,或者片段处理里背面剔除误伤
- 体积计算得到负值
- 半边结构无法从索引表正确重建 ——
twin匹配失败
修复方法:从一个种子面出发 BFS,每一步用共享边判断邻面方向,不一致就翻转。对每个连通分量各做一次。Möbius 带这种不可定向曲面无法一致定向,但工程模型里几乎不出现。
7. Euler 公式与网格合法性
闭合三角网格满足 Euler 公式:
是亏格(genus,"洞"的数量)。球面 、环面 。三角形每面 3 条边、每边被 2 面共享,所以 ,代入得 (球面情形)。用来做廉价合法性检查:读入 OBJ 后一算 ,不是偶数直接报错。
8. 网格上的基本编辑操作
半边结构让下面这些操作都变得优雅。以三角网格为例:
| 操作 | 说明 | 影响 |
|---|---|---|
| Edge Split | 在一条边中点插入新顶点,把两侧三角形各切成两个 | |
| Edge Collapse | 把一条边缩成一个点,两个顶点合并 | |
| Edge Flip | 沿一条边把两个三角形组成的四边形翻另一条对角线 | 拓扑不变 |
| Vertex Split | Edge Collapse 的逆操作,一个点裂成两个 | Progressive Mesh 的基础 |
Edge Collapse 是网格简化(Garland-Heckbert QEM)的核心动作:每次坍缩一条误差最小的边,逐步降低面 数。Edge Flip 是 Delaunay 三角化优化的基础:不满足空圆性质时翻边。这些都需要 邻接查询,索引表做不到,半边做得到。
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 见 参数曲线与曲面。