2.1 基于面的数据结构

• https://gemini.google.com/app/a650df2c238d3e22?hl=zh

来源：Mario Botsch 等人的 Polygon Mesh Processing，第 2 章 Mesh Data Structures，2.1 小节 Face-Based Data Structures。

第 2 章开始讨论 mesh data structures。几何算法的效率和内存占用，很大程度取决于网格底层如何存储顶点、边、面以及它们的邻接关系。

这一节先从最简单的 face-based data structures 讲起。

第 2 章的问题

选择网格数据结构时，要同时考虑两类需求。

拓扑需求

需要表示什么类型的网格？

• 是否只处理 2-manifold？
• 是否要支持 non-manifold edges / vertices？
• 是否只处理三角网格？
• 是否要支持任意多边形网格？
• 网格是 regular、semi-regular，还是 irregular？
• 是否需要层级细分结构？

算法需求

算法会怎样访问网格？

• 只是渲染？
• 需要频繁访问顶点的一环邻域？
• 需要访问边的左右面？
• 网格拓扑会不会动态变化？
• 是否要给顶点、边、面附加属性？
• 是否需要极低内存占用？

信息

没有一种网格数据结构在所有任务上都最好。静态渲染、局部编辑、拓扑修改、邻域遍历，对数据结构的要求完全不同。

数据结构要支持哪些基本操作

书中列出了一组几何处理中常用的最小操作。

访问基本元素

需要能访问：

• vertices。
• edges。
• faces。

并能枚举所有元素。

遍历一个面的边

给定一个 face，需要能按方向访问它的边：

edge -> next edge -> next edge

这对渲染、计算法向、遍历 polygon boundary 都很重要。

访问一条边的 incident faces

给定一条 edge，需要知道它相邻的面。

对于 manifold mesh，一条内部边通常有两个 incident faces：

left face / right face

这能支持相邻面访问。

访问一条边的两个端点

给定一条 edge，需要知道：

start vertex / end vertex

这对几何计算、边长计算、局部拓扑操作都很基础。

访问一个顶点的一环邻域

给定一个 vertex，至少要能找到一个 incident face 或 incident edge。

然后沿着邻接关系枚举：

• incident faces。
• incident edges。
• neighboring vertices。

这些元素构成 vertex 的 one-ring neighborhood。

提示

很多网格算法的核心操作都是“一环邻域遍历”：平滑、曲率估计、法向平均、Laplace operator、局部重网格等都离不开它。

Face-set：最简单的表示

最简单的表面网格表示是 face-set。

对于三角网格来说，就是每个三角形直接存三个顶点位置：

triangle_0: p0, p1, p2
triangle_1: p3, p4, p5
triangle_2: p6, p7, p8
...

每个顶点位置包含三个坐标：

$$(x,y,z)$$

如果每个坐标用 32-bit float，也就是 4 bytes，那么一个顶点位置需要：

$$3\times4=12\text{ bytes}$$

一个三角形有 3 个顶点位置，所以需要：

$$3\times12=36\text{ bytes/triangle}$$

因为三角网格中通常近似：

$$F\approx2V$$

所以平均到每个原始顶点上，存储约为：

$$36\times2=72\text{ bytes/vertex}$$

triangle soup / polygon soup

face-set 不存储显式连接关系。

每个三角形只知道自己的三个点坐标，不知道：

• 哪些三角形共享顶点。
• 哪些三角形相邻。
• 哪条边属于哪些面。
• 一个顶点周围有哪些面。

因此它常被称为：

triangle soup / polygon soup

也就是“一锅三角形”。

这种格式适合作为最低共同表示，STL 等文件格式就常使用类似结构。

face-set 的问题

face-set 最大的问题是冗余和缺少连接关系。

假设一个顶点被 6 个三角形共享。

在真实网格中，它是同一个顶点。

但在 face-set 中，这个顶点位置会在 6 个三角形中重复存 6 次。

这带来两个后果：

1. 存储冗余。
2. 很难知道这些重复坐标到底是不是同一个拓扑顶点。

如果要恢复连接关系，就需要搜索相同或近似相同的坐标，代价高且容易受浮点误差影响。

注意

triangle soup 可以渲染，但不适合大多数几何处理算法。因为几何处理通常需要局部邻接，而 triangle soup 没有显式拓扑。

Indexed Face Set

为了避免顶点重复，可以使用 indexed face set，也叫 shared-vertex data structure。

它分成两部分存储：

顶点数组

vertices:
0 -> p0
1 -> p1
2 -> p2
3 -> p3
...

每个顶点位置只存一次。

面索引数组

每个三角形不再直接存坐标，而是存顶点索引：

faces:
0 -> (0, 1, 2)
1 -> (0, 2, 3)
2 -> (0, 3, 4)
...

这样，共享顶点只需要在 faces 中重复出现索引，而不是重复存储完整三维坐标。

Indexed Face Set 的内存估算

如果顶点坐标使用 32-bit float：

$$3\times4=12\text{ bytes/vertex}$$

如果三角形索引使用 32-bit integer：

$$3\times4=12\text{ bytes/face}$$

由于：

$$F\approx2V$$

平均到每个顶点：

$$12\text{ bytes/vertex} +12\times2\text{ bytes/vertex} = 36\text{ bytes/vertex}$$

这正好约为 face-set 的一半：

$$72\rightarrow36\text{ bytes/vertex}$$

所以 indexed face set 更省内存。

Indexed Face Set 的优点

这种结构简单、高效、文件格式友好。

常见格式如：

• OFF。
• OBJ。
• VRML。

都可以使用类似思想。

对于静态渲染也很合适，例如 OpenGL vertex arrays。

因为 GPU 很擅长处理：

vertex buffer + index buffer

Indexed Face Set 的不足

indexed face set 虽然避免了重复顶点，但仍然没有显式邻接关系。

它知道：

face -> vertices

但不知道：

edge -> adjacent faces
vertex -> incident faces
face -> neighboring faces

如果想知道某个顶点的一环邻域，需要在所有 faces 中搜索包含该顶点的面。

假设：

$$F=1,000,000$$

每次查询一个顶点邻域都扫描全部 faces，显然不可接受。

因此 indexed face set 适合存储和渲染，但对许多网格处理算法不够高效。

带连接信息的 face-based structure

为了支持快速遍历，可以在 face-based structure 中加入连接信息。

对三角网格来说，典型做法是：

每个 face 存：

• 三个 vertex references。
• 三个 neighboring triangle references。

每个 vertex 存：

• 3D position。
• 一个 incident face reference。

这样就能从一个顶点出发，借助相邻面引用绕着顶点循环，枚举它的一环邻域。

内存估算

书中给出这种结构的内存量级：

24 bytes/face + 16 bytes/vertex

因为：

$$F\approx2V$$

所以平均每个顶点：

$$24\times2+16=64\text{ bytes/vertex}$$

它比 indexed face set 更占内存：

$$36\rightarrow64\text{ bytes/vertex}$$

但换来了快速局部遍历。

为什么邻接信息值得存

很多算法宁愿多花内存，也要快速邻接访问。

例如计算一个顶点的平均法向，需要枚举 incident faces。

如果没有邻接结构，可能要扫描全部 faces。

如果有邻接结构，只需要访问该顶点附近的一小圈 faces。

假设网格有：

$$F=1,000,000$$

平均 valence 约为：

$$6$$

那么一次 one-ring 查询：

• 没有邻接：可能扫描 1,000,000 个 face。
• 有邻接：访问约 6 个 incident faces。

这就是数据结构对算法效率的巨大影响。

face-based structure 的缺点

带邻接的 face-based structure 也不是完美的。

不显式存 edge

它没有独立的 edge 对象。

因此，如果算法需要在 edge 上存数据，例如：

• edge length。
• edge weight。
• sharp / crease flag。
• collapse cost。
• boundary marker。

就不方便。

one-ring 遍历有分支判断

在三角形里，一个顶点可能是第 1、2、3 个顶点。

绕顶点遍历时，需要不断判断当前中心顶点在当前 face 的哪个位置。

这会让实现变复杂，也可能影响效率。

不适合一般多边形网格

对三角网格，每个 face 固定有 3 个顶点和 3 个邻居。

但如果是任意 polygon mesh，每个 face 的顶点数不固定。

这会让 face 结构变成变长数据，内存布局和实现都更复杂。

信息

face-based structure 对三角网格很自然，但如果要优雅支持任意多边形网格和边属性，后面的 edge-based / halfedge structure 会更合适。

三种 face-based 表示对比

结构	存什么	约内存	优点	缺点
face-set	每个三角形直接存 3 个点坐标	72 bytes/vertex	极简单，适合交换格式	顶点重复，无连接关系
indexed face set	顶点数组 + 面索引数组	36 bytes/vertex	省内存，适合渲染和文件格式	邻接查询昂贵
face-based with adjacency	face 存顶点和邻居，vertex 存 incident face	64 bytes/vertex	支持局部遍历	不显式存 edge，遍历有分支

和第 1 章的关系

第 1 章说明三角网格包含：

$$V,E,F$$

以及几何嵌入：

$$P=\{\mathbf{p}_1,\ldots,\mathbf{p}_V\}$$

第 2 章的问题是：这些东西在计算机里到底怎么存。

2.1 的结论是：

• 只存 face 很简单，但不够用。
• 加 index 可以省内存。
• 加邻接可以加速遍历。
• 真正复杂的局部编辑和通用 polygon mesh，还需要 edge-based 或 halfedge-based 数据结构。

本节记忆点

• face-set 直接存每个面的顶点坐标，也叫 triangle soup / polygon soup。
• face-set 对三角网格需要约：

$$36\text{ bytes/triangle}$$

平均约：

$$72\text{ bytes/vertex}$$

• indexed face set 用顶点数组和面索引数组避免顶点重复，约：

$$36\text{ bytes/vertex}$$

• indexed face set 简单省内存，但不显式存邻接。
• 几何处理常需要访问 one-ring neighborhood，因此需要更强的连接结构。
• 带邻接的 face-based structure 每个 face 存顶点引用和邻居引用，每个 vertex 存一个 incident face，可支持局部遍历。
• 这种结构约：

$$64\text{ bytes/vertex}$$

• 它的不足是不显式存 edge，无法方便附加 edge data，也不太适合任意 polygon mesh。

后续问题

进入 2.2 时可以重点关注：

1. 为什么 general polygon meshes 更适合 edge-based structure？
2. winged-edge 为什么要在 edge 上存左右 face 和前后 edge？
3. edge-based structure 如何支持更通用的拓扑遍历？
4. 为什么 halfedge structure 能减少 one-ring 遍历中的分支判断？