2.3 半边数据结构

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

2.2 基于边的数据结构 说明：edge-based structure 能更自然地表示一般多边形网格，但遍历 one-ring 时仍然需要判断当前顶点是边的第一个端点还是第二个端点。

Halfedge data structure 的核心改进是：把一条无向边拆成两条有方向的 halfedges。

本节核心

一条普通 edge 是无向的：

v0 ----- v1

Halfedge structure 把它拆成两个方向相反的 halfedges：

h:      v0 -> v1
h_opp:  v1 -> v0

这样，每次沿网格走的时候，方向都是明确的。

这能避免 winged-edge 中很多“当前顶点到底是 edge 的哪个端点”的分支判断。

信息

Halfedge 的关键不是“多存了一份边”，而是把无向连接变成有向连接，从而让局部遍历更统一。

Halfedge 能表示什么网格

书中指出，halfedge data structure 可以表示任意 polygonal meshes，只要它们是 orientable combinatorial 2-manifold 的子集。

也就是说，它通常要求：

• 没有 complex edges。
• 没有 singular / non-manifold vertices。
• 表面整体可定向。
• 每条内部边最多有两个 incident faces。

这和第 1 章的 manifold 概念对应。

如果网格中有多个面片团只在一个点粘在一起，或者一条边连接超过两个面，halfedge 的局部邻接假设就会失效。

Halfedge 的方向约定

在 halfedge data structure 中，halfedges 通常按一致方向围绕每个 face。

常见约定是：

counterclockwise around each face

如果一个 face 是三角形：

v0 -> v1 -> v2 -> v0

那么它的三个 halfedges 就按这个方向链接：

h0.next = h1
h1.next = h2
h2.next = h0

图源说明：根据 Botsch et al., Polygon Mesh Processing, Chapter 2 的 halfedge 数据结构概念重绘，非原书截图。

对于 boundary，也可以把边界看作一个“空 face”的边界环。

这样 boundary loop 也能用类似方式遍历。

一个 halfedge 存什么

书中列出，每个 halfedge 通常存 5 类引用。

1. 指向的 vertex

每条 halfedge 存它指向的目标顶点：

to_vertex(h)

如果：

h: v0 -> v1

那么：

vertex(h) = v1

2. 相邻 face

每条 halfedge 存它左侧或所属的 face：

face(h)

如果是 boundary halfedge，可以用空指针或特殊值表示没有 face。

3. next halfedge

在同一个 face 内，存下一条 halfedge：

next(h)

这样可以绕一个 face 的边界循环。

4. previous halfedge

在同一个 face 内，存上一条 halfedge：

prev(h)

这不是绝对必须的，因为可以沿 next 走一圈找到前一条，但显式存储会让反向访问更快。

5. opposite halfedge

存相反方向的 halfedge：

opposite(h)

如果：

h:      v0 -> v1
h_opp:  v1 -> v0

那么：

opposite(h) = h_opp
opposite(h_opp) = h

Vertex 和 Face 存什么

除了 halfedge 自身的引用，vertex 和 face 也需要入口。

每个 face 存：

one incident halfedge

这样可以进入 face 的边界环。

每个 vertex 存：

one outgoing halfedge

这样可以从 vertex 出发枚举 one-ring。

Corner 属性

Halfedge 还有一个实用副作用：每个 halfedge 可以代表一个 corner。

所谓 corner，是某个 face 内部的一个顶点实例。

同一个几何 vertex 可以在多个 face 中出现，但每个 face 中的 corner 属性可以不同。

这对下面这些属性很有用：

• texture coordinates。
• per-corner normals。
• UV seam。
• sharp edge 附近的分裂法向。

例如，一个 cube 的几何顶点只有一个位置，但不同面的法向不同。把法向存成 per-corner 属性，比强行存成 per-vertex 属性更合理。

One-ring traversal 为什么更简单

Halfedge 最重要的优势之一是：可以统一地枚举一个 vertex 的 one-ring neighborhood。

设中心顶点为：

center

从它的一条 outgoing halfedge 开始：

h = outgoing_halfedge(center)

然后反复执行：

h = next(opposite(h))

就可以绕着中心顶点旋转，枚举它周围的邻接顶点。

书中的伪代码思想是：

void enumerate_one_ring(VertexRef center, Function func) {
  HalfedgeRef h = outgoing_halfedge(center);
  HalfedgeRef hstop = h;
  do {
    VertexRef v = vertex(h);
    func(v);
    h = next_halfedge(opposite_halfedge(h));
  } while (h != hstop);
}

这个遍历在做什么

假设当前 halfedge 是：

h: center -> v

那么：

vertex(h)

就是当前访问到的邻居顶点 $v$。

接下来：

opposite(h)

会跳到反方向：

v -> center

然后：

next(opposite(h))

会沿着相邻 face 的边界走到下一条从 center 出发的 halfedge。

于是整个循环就像绕着中心顶点旋转一圈。

提示

Halfedge 的 one-ring 遍历之所以干净，是因为每一步都用固定操作 next(opposite(h))，不需要判断中心顶点是 edge 的哪个端点。

opposite 可以不显式存吗

书中提到，如果两个相反 halfedges 总是成对存储，并且在数组中相邻：

halfedges[i]
halfedges[i + 1]

那么 opposite 可以通过索引隐式得到。

例如，如果成对索引满足：

0 <-> 1
2 <-> 3
4 <-> 5

则：

opposite(h) = h ^ 1

或者用加减 1 的方式得到。

这样可以少存一个 opposite 引用。

同时，一对 halfedges 就对应一条 full edge，因此如果要给 edge 存属性，也可以把属性绑定到这一对 halfedges 上。

prev 可以不显式存吗

prev 也可以省略。

因为在一个 face 中，如果知道 next，总能沿着 next 走一圈找到前一条。

但这会让查询 prev 从 $O(1)$ 变成和 face 边数相关。

对三角网格还好，因为一个 face 只有 3 条边。

对一般 polygon mesh，如果 face 边数很多，省略 prev 会让某些操作变慢。

所以是否存 prev 是内存和访问速度之间的取舍。

内存估算

书中给出一般 halfedge structure 的内存：

16 bytes/vertex + 20 bytes/halfedge + 4 bytes/face

对三角网格，通常有：

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

每条 edge 有 2 条 halfedges，所以：

$$H=2E\approx6V$$

总内存约为：

$$16V + 20H + 4F$$

代入：

$$16V + 20(6V) + 4(2V)$$ $$=16V+120V+8V$$ $$=144V$$

所以约：

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

如果不显式存 previous 和 opposite，内存可降到约：

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

指针 vs 索引

Halfedge 中的引用可以用两种方式实现：

• pointers。
• indices。

书中指出，实际中 index representation 更灵活。

原因是：

• 数据可以存放在连续数组中。
• 便于内存重排。
• 便于序列化和保存文件。
• 顶点、边、半边、面的属性可以用相同 index 关联。
• 内存管理更紧凑。

缺点是访问需要一次间接索引，不像指针那样直接。

但在实际工程中，索引数组通常更容易维护。

Halfedge 支持哪些访问

Halfedge structure 可以从任意元素访问相邻元素。

例如：

从 face 出发

face -> one halfedge
     -> next -> next -> ...
     -> all boundary vertices / edges

从 vertex 出发

vertex -> outgoing halfedge
       -> next(opposite(h))
       -> one-ring neighbors

从 edge / halfedge 出发

halfedge -> vertex
halfedge -> face
halfedge -> opposite
halfedge -> next / prev

这使得它成为很多 mesh processing library 的核心数据结构。

和前两节的对比

结构	优点	缺点
indexed face set	简单、省内存、适合渲染	邻接查询昂贵
face-based adjacency	支持三角网格局部遍历	不显式存 edge，不适合一般 polygon mesh
winged-edge	以 edge 为中心，支持 polygon mesh	one-ring 遍历仍有分支判断
halfedge	有向遍历统一，邻接访问强	内存更高，要求 orientable 2-manifold

工程直觉

如果只是读 OBJ 并渲染，indexed face set 通常足够。

如果要做几何处理，例如：

• smoothing。
• remeshing。
• simplification。
• edge collapse。
• local neighborhood query。
• boundary traversal。
• per-corner UV / normal。

halfedge structure 会更顺手。

它用更多内存换来了清晰的局部拓扑操作。

本节记忆点

• Halfedge 把每条无向 edge 拆成两个有向 halfedges。
• 每个 halfedge 通常存：
  • 指向的 vertex。
  • adjacent face。
  • next halfedge。
  • previous halfedge。
  • opposite halfedge。
• 每个 face 存一条 incident halfedge。
• 每个 vertex 存一条 outgoing halfedge。
• one-ring traversal 可以用固定模式：

h = next(opposite(h))

• Halfedge 能自然表示 per-corner attributes。
• 一般 halfedge 内存约：

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

• 省略 prev 和显式 opposite 后可降到约：

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

• Halfedge 通常要求网格是 orientable 2-manifold 的子集。
• 工程中常用 indices 而不是 pointers 来实现引用。

后续问题

进入 2.4 时可以重点关注：

1. Directed-edge 如何进一步压缩 halfedge 的内存？
2. 为什么 directed-edge 特别适合纯三角网格？
3. 哪些连接关系可以通过索引规则隐式计算？
4. 它相比一般 halfedge 牺牲了哪些通用性？