4.4 多面体边界的表示方法
(Polyhedral Boundary Representations)

表示多面体及更一般物体的边界已发展成为计算机图形学、几何建模和计算几何领域的一个重要分支。在本节中，我将概述三种比 4.3.1 节更复杂的表示方法。这些表示方法并不要求面是三角形。 这立即引出了一个问题: 如何表示面? 可以使用固定长度的记录吗? 还是必须使用可变长度的列表?

本节的目标仅仅是指出几个问题，不会试图进行全面的阐述。

4.4.1. 翼状边数据结构 (Winged-Edge Data Structure)

Baumgart 的翼状边表示法 winged-edge representation(Baumgart 1975) 是最早开发且至今仍然流行的表示方法之一。 该数据结构的重点在于边。每个顶点指向其关联边中的任意一条，每个面指向其边界边中的任意一条。一条边 \(e\) 的记录由八个指针组成， 指向 \(e\) 的两个端点 \(v_0, v_1\)；指向与 \(e\) 相邻的两个面 \(f_0, f_1\)，这两个面分别位于 \(v_0v_1\) 的左侧和右侧； 以及指向四条边，即 \(e\) 的"翅膀(wings)"，\(e_0^-, e_0^+\)，分别是与 \(v_0\) 关联且位于 \(e\) 顺时针和逆时针方向的边； 以及 \(e_1^-, e_1^+\)，关联到 \(v_1\) 的边。见图 4.17。注意，这三种结构的大小都是固定的，这是一个有用的特性。

作为该数据结构的一个示例，包围面 \(f\) 的边可以通过检索存储在 \(f\) 记录中的唯一边 \(e\)，然后沿着 \(f\) 周围的 \(e^+\) 边追踪，直到再次遇到 \(e\) 为止。 但是，由于 \(e\) 的方向是任意的，必须检查 \(f\) 是在 \(e\) 的左侧还是右侧，以决定应该追踪 \(e_1^+\) 还是 \(e_0^+\) 边。

4.4.2. 双生边数据结构 (Twin-Edge Data Structure)

在某些数据结构中，如果边的方向是任意的，那么在进行某些操作时，就需要额外的工作来确定其局部方向。我们在代码 MakeCcw， Code4.18中就看到了这一点，而且上述的翼状边结构也存在这个问题。 一个简洁的解决方案是将每条边表示为两条方向相反的"半边(half edge)"，有时也称为"孪生边(twin edge)"。每个面指向其任意一条边界的半边，这些半边链接成一个循环列表。 每个顶点指向任意一条关联的半边。每条半边指向它所包围的唯一面，和面边界上的前后两条边，以及它的孪生边*与相邻面共享的另一半边)。 给定面 \(f_0\) 和它边界的一条半边 \(e\)，可以通过面指针 \(\text{twin}(e)\) 的找到相邻的面 \(f_1\)。 虽然将每条边表示两次会增加一些空间占用和更新复杂度，但对于某些函数来说，这些增加通常也是值得的。比如，使用这种数据结构遍历一个面的边就非常简单。

4.4.3. 四边数据结构 (Quad-Edge Data Structure)

Guibas 和 Stolfi 发明了一种高明的数据结构，他们称之为四边(quad-edge)结构(Guibas & Stolfi 1985)。这种数据结构虽然更抽象，但实际上它简化了许多操作和算法。 它的优势在于极其通用，能够表示 2-流形的任意细分(2-manifolds，见 4.1.1 节)，可以区分曲面的两侧， 允许边的两个端点为同一个顶点，也能兼容悬挂边(dangling edges)等。

每条边都被记录在四个循环链表中: 两个端点各一个，两个相邻面各一个，因此它包含四个指针。根据应用的不同，可以包含额外的信息，如 above/below bit、几何信息等。 图 4.18 和图 4.19 给出了一个示例。其中图 4.18(a) 是一个平面图(plane graph)，它不是多面体图(Polyhedral graph)，即从多面体导出的图，而是更一般的情况。 它有三个内部面 \(A, B, C\)，以及外部面 \(D\)。图中八条边分别被标记为 \(a, \dots, h\)，六个顶点标记为 \(0, \dots, 5\)。

图 4.19 显示了对应的四边结构，每个边记录由一个十字表示，四个臂对应四个指针。面循环(face cycles)用深色线绘制，顶点循环(vertex cycles)用浅色线绘制。 例如，面 \(A\) 是边 \((b, c, d, e)\) 组成的环，顶点 3 是环 \((c, g, d)\)。注意，空悬边 \(a\) 也得以一种一致的方式建模，它在外部面 \(D\) 的循环上出现了两次。

与翼状边数据结构一样，顶点和面是最基础的表示。每个顶点或面都被分配其环上的任意一条边。顶点或面的真实表示就是这个环，而边指针只是提供了访问该环的入口。

该结构最优美的方面之一是，它自动编码了对偶细分(dual subdivision)。我们在第 1 章(1.2.3 节)讨论了三角分割的对偶。 一般平面图(plane graph) \(G\) 的对偶为，每个面分配一个节点，并为相邻面之间的每条边分配一条弧。"外部面"也被分配一个节点，并连接到每个具有外部边界边的面。 这就导致，\(G\) 中的每个顶点在对偶中都被一圈面节点包围，如图 4.18(b) 所示。在四边结构中，只需将图 4.19 中的浅色循环解释为面，将深色循环解释为顶点，即可实现对偶细分——不需要任何计算！ 我们将在下一章再次遇到对偶图(5.2.2 节)。

4.4.4. 练习 (Exercises)