2.2 基于边的数据结构

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

2.1 基于面的数据结构 说明：只用 face 或 indexed face set 存网格，虽然简单省内存，但局部邻接访问不够直接；即使给 face 加邻居引用，也仍然不显式存 edge。

2.2 的思路是反过来：把 edge 作为连接关系的核心。

本节核心

对于一般 polygon mesh，连接关系主要围绕边发生。

一条边连接：

• 两个端点 vertex。
• 左右两个 incident faces。
• 每个 incident face 内的前后相邻 edge。

因此，基于边的数据结构更自然地支持任意多边形网格，而不局限于三角网格。

典型 edge-based structures 包括：

• winged-edge。
• quad-edge。

本节重点介绍 winged-edge 的存储思想。

为什么从 face-based 转向 edge-based

Face-based structure 对三角网格很方便，因为每个 face 固定有 3 个顶点、3 条边、3 个邻居。

但如果是一般 polygon mesh：

triangle: 3 edges
quad:     4 edges
n-gon:    n edges

face 的大小不再固定。

此时，把 connectivity 放在 edge 上更合理，因为每条 edge 的局部关系相对稳定：

edge -> endpoints
edge -> incident faces
edge -> next / previous edges around each face

Winged-edge 的直觉

Winged-edge 这个名字可以理解为：一条边像中轴，两侧有两个面，沿每个面又能找到前后边。

对于一条 edge $e$，它通常存储：

• 两个端点：

v0, v1

• 两个 incident faces：

left face, right face

• 在 left face 中的前一条边和后一条边。
• 在 right face 中的前一条边和后一条边。

也就是：

edge e:
  vertices: v0, v1
  faces:    f_left, f_right
  left:     prev_left, next_left
  right:    prev_right, next_right

同时：

• 每个 vertex 存一个 incident edge。
• 每个 face 存一个 incident edge。

这样就能从任意顶点或面进入局部连接结构。

Winged-edge 能支持什么遍历

沿一个面遍历边界

给定一个 face，只要拿到它的一条 incident edge，就可以通过 next / previous 指针绕着 face 走一圈：

edge_0 -> edge_1 -> edge_2 -> ... -> edge_0

这适合一般多边形面，不要求面一定是三角形。

找一条边的左右面

给定 edge，可以直接访问：

left face
right face

这比 indexed face set 中临时搜索相邻面高效得多。

找一条边的两个端点

给定 edge，可以直接得到：

v0, v1

这对边长、边折叠、边翻转、边权重等操作都重要。

从顶点进入一环邻域

每个 vertex 存一个 incident edge。

从这条 edge 出发，可以沿连接关系绕顶点遍历，枚举它的一环邻域。

不过，这一步仍然不如 halfedge 直接，因为要判断当前顶点是 edge 的第一个端点还是第二个端点。

内存估算

书中给出 winged-edge 结构的大致内存：

16 bytes/vertex + 32 bytes/edge + 4 bytes/face

对大多数三角网格，有近似关系：

$$F\approx2V$$ $$E\approx3V$$

所以平均每个顶点的存储量为：

$$16V + 32E + 4F$$

代入：

$$16V + 32(3V) + 4(2V)$$ $$=16V+96V+8V$$ $$=120V$$

因此约为：

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

这比 2.1 中的 indexed face set 和 face-based adjacency 都更占内存：

结构	约内存
indexed face set	$36$ bytes/vertex
face-based with adjacency	$64$ bytes/vertex
winged-edge	$120$ bytes/vertex

代价换来的是更通用的 edge-centric connectivity。

为什么边结构更适合 polygon mesh

对于任意 polygon mesh，face 的边数不固定。

如果以 face 为中心存储，就需要变长数组或复杂的面结构。

而 edge-based structure 把连接关系拆到边上：

• 每条 edge 都有两个端点。
• manifold 情况下，每条内部 edge 有两个 incident faces。
• 每个 face 边界由 edge 的 next / previous 串起来。

这使得它能更自然地表示三角形、四边形和一般多边形。

仍然存在的问题

Edge-based structure 虽然更通用，但仍有一个重要缺点：one-ring 遍历需要 case distinctions。

原因是 edge 本身没有方向。

给定一条 edge：

edge = (v0, v1)

如果当前要围绕中心顶点 $v$ 遍历，就必须判断：

v == v0 ?
v == v1 ?

也就是书中说的：

is the center vertex the first or second vertex of an edge?

这个判断在一环遍历中会反复出现。

结果是：

• 实现更复杂。
• 遍历逻辑不够统一。
• 代码里有较多分支。

这正是 2.3 halfedge data structure 要解决的问题。

提示

Edge-based structure 把“边”作为中心，但 edge 没有方向；halfedge structure 进一步把一条无向边拆成两个有向半边，从而让遍历方向统一。

和 2.1 的关系

2.1 中的 face-based structure 适合三角网格，因为三角面大小固定。

2.2 的 edge-based structure 更适合一般多边形网格，因为连接关系主要沿 edge 组织。

但从算法遍历角度看，edge-based 仍然不够干净。

于是自然过渡到：

face-based
-> edge-based
-> halfedge-based

这个顺序可以理解为：连接信息越来越显式，遍历越来越方便，但内存和结构复杂度也会上升。

本节记忆点

• 一般 polygon mesh 的连接关系更适合围绕 edge 组织。
• Winged-edge 是典型 edge-based structure。
• 每条 edge 存：
  • 两个 endpoint vertices。
  • 两个 incident faces。
  • left face 中的 next / previous edge。
  • right face 中的 next / previous edge。
• vertex 和 face 各自存一个 incident edge，作为进入局部结构的入口。
• Winged-edge 可以支持任意多边形面的边界遍历。
• 内存约为：

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

• Edge-based structure 的缺点是 one-ring traversal 仍需要判断中心顶点是边的第一个端点还是第二个端点。
• Halfedge structure 通过把 edge 拆成两个有向 halfedges 来解决这个问题。

后续问题

进入 2.3 时可以重点关注：

1. halfedge 为什么要把一条 edge 拆成两个方向？
2. 一个 halfedge 需要存哪些引用？
3. halfedge 如何让 one-ring traversal 变得统一？
4. 为什么 halfedge 要求网格是 orientable 2-manifold 的子集？