计算机图形学基础-12-图形学中的数据结构

《Fundamentals of Computer Graphics》5th（计算机图形学基础/虎书），中文翻译。

第 12 章 Data Structures for Graphics 图形学中的数据结构

在图形应用中，某些数据结构似乎会反复出现，可能是因为它们涉及到基础的概念，如表面、空间和场景结构。本章讨论了几种基本且不相关的数据结构类别，这些结构在图形应用程序中最常见且最有用：网格结构、空间数据结构、场景图和平铺多维数组。

网格结构 mesh structures
空间数据结构 spatial data structures
场景图 scene graphs
平铺多维数组 tiled multidimensional arrays

对于网格 (mesh)，我们讨论了用于存储静态网格和将网格传输到图形 API 的基本存储方案。我们还讨论了翼边 (winged-edge) 数据结构（Baumgart，1974）及其相关的半边结构，这些结构对于管理模型中的镶嵌变化（例如在细分或模型简化中）非常有用。虽然这些方法可以推广到任意多边形网格，但我们在这里重点讨论三角形网格的情况。

紧接着是介绍场景图数据结构。因为它们在管理三维对象和变换方面非常有用，所以各种形式的这种数据结构在图形应用程序中随处可见。所有新的图形 API 都能够很好地支持场景图。

对于空间数据结构，我们讨论了在 3D 空间中组织模型的三种方法 —— 包围体层次结构、分层空间细分和均匀空间细分 —— 以及使用分层空间细分（BSP 树）进行隐藏表面删除。同样的方法也用于其他目的，包括几何剔除和碰撞检测。

最后，介绍了平铺多维数组。最初是为了帮助在需要从磁盘交换图形数据的应用程序中提高分页性能而开发的，这些结构现在对于内存局部性在任何情况下都非常重要，无论数组是否适合主内存。

12.1 三角形网格 Triangular Meshes

大多数实际模型由共享顶点的三角形复合物组成。这些通常被称为三角形网格、三角形网或三角不规则网络（TINs），有效处理它们对许多图形程序的性能至关重要。所需的效率取决于应用程序。网格存储在磁盘和内存中，我们希望尽量减少所消耗的存储空间。当网格从网络传输或从 CPU 传输到图形系统时，它们会占用带宽，而带宽通常比存储空间更珍贵。在执行网格操作的应用程序中，除了简单地存储和绘制网格之外，例如细分、网格编辑、网格压缩或其他操作，高效访问邻接信息至关重要。

三角形网格通常用于表示表面，因此网格不仅仅是一组不相关的三角形，而是通过共享顶点和边连接在一起形成一个连续的表面三角形网络。这是关于网格的一个关键见解：网格比同样数量的不相关三角形更容易处理。

三角形网格所需的最小信息是一组三角形（由顶点构成的三元组）及其顶点在 3D 空间中的位置。但是，许多（如果不是大多数）程序需要能够在顶点、边缘或面部存储附加数据，以支持纹理映射、着色、动画和其他操作。顶点数据最常见：每个顶点可以有材料参数、纹理坐标和辐照度等参数，这些参数的值在表面上发生变化。然后，在每个三角形上进行线性插值，定义整个网格表面上的连续函数。但是，偶尔还有重要的需求希望能够按边或面存储数据。

12.1.1 网格拓扑结构 (Mesh Topology)

“网格类似于表面”这个想法可以通过对网格拓扑结构 (mesh topology) 的约束来形式化 —— 三角形如何连接在一起，而不考虑顶点位置。许多算法仅适用于具有可预测连通性的网格，或者在此类网格上更容易实现。对网格拓扑结构最简单且最严格的要求是表面应该是流形的 (manifold)。流形网格是“无缝 (watertight)”的 —— 它没有间隙，并将表面内部的空间与外部空间分开。整个网格看起来就像是一个表面。

我们将精确定义留给数学家；请参见本章注释。

译者注：什么是“流形”

在欧几里得空间中，我们可以想象有一个平面或者三维空间，这些空间中的点可以用坐标轴表示，也就是 (x,y,z) 这样的形式。这些空间都是平直的，没有弯曲或者扭曲的形状。

但是在我们生活的现实中，很多东西都是弯曲、曲折或者卷曲的，例如山脉、河流、云彩甚至脑海中的想法，这些都是一些具有弯曲曲率的物体或者概念。

在数学中，我们可以利用“流形”这个概念来描述这些具有弯曲形状的东西。一个流形在不同的位置上可以看做欧几里得空间中的局部部分，也就是说，在局部上它们可以用普通的几何学方法描述。但是在全局上，它们的形状是弯曲的、蜿蜒的，不再是我们熟悉的平直形状。

流形 (manifold) 这个术语来自拓扑学领域：粗略地说，流形（特别是二维流形或 2-流形）是一个表面，在其上任意点的小邻域都可以平滑成一片平坦的表面。这个想法最清楚地通过反例解释：如果网格上的一条边连接了三个三角形，则该边上的一个点的邻域与一个三角形内部的点的邻域不同，因为它有一个额外的“鳍”（图 12.1）。如果该边恰好连接了两个三角形，则边上的点的邻域与内部点的邻域相同，只是中间有一个折痕。同样，如果共享一个顶点的三角形的配置如图 12.2 左侧所示，则该邻域就像两个表面在中心处粘合在一起，无法打平而不重复。右侧显示的具有简单邻域的顶点则没有问题。

图 12.1：非流形（a）和流形（b）内部边缘。

图 12.2：非流形（a）和流形（b）内部顶点。

许多算法假定网格是流形的，因此在输入异常网格时，验证这个属性是有必要的，以防止程序崩溃或无限循环。这个验证可以归结为检查所有边是否流形和检查所有顶点是否流形，通过验证以下条件来进行：

1. 每条边被恰好两个三角形共享。
2. 每个顶点周围有一个完整的三角形环。

图 12.1 示意了不符合第一条规律的情况，一个点具有太多三角形的边缘；图 12.2 示意了不符合第二条规律的情况，一个定点连接着两个不同的三角形环。

流形网格很方便，但有时需要允许网格具有边缘或边界。这样的网格并非流形 —— 边界上的点周围的邻域在一侧被截断。它们不一定是无缝的。然而，我们可以放松流形网格的要求，转而满足带边界流形的要求，而大多数网格处理算法不会出现问题。宽松一点的条件为：

1. 每条边最多被两个三角形共享。
2. 每个顶点周围有一个三角形环，但有些顶点可能位于边界上，只有一个三角形环绕它们。

图 12.3 说明了这些条件，从左到右依次为：一条边，只连接一个三角形；一个顶点，周围的三角形都是通过边相连接；一个顶点，连接两个不相连三角形集合。

图 12.3：带边界流形的边缘条件。

最后，在许多应用中，区分表面的“前/后”（内/外）很重要，这就是表面的定向。对于单个三角形，我们根据列出顶点的顺序定义方向：三角形中三个顶点按逆时针顺序排列的那一面是正面。如果网格中所有三角形都同意哪一面是正面，则连接网格的方向是一致的，当且仅当每对相邻三角形的方向一致时才成立。

在一对方向一致的三角形中，两个共享的顶点在两个三角形的顶点列表中以相反的顺序出现（图 12.4）。重要的是定向的一致性 —— 某些系统使用顺时针而不是逆时针来定义正面。

图 12.4：三角形 $(B,A,C)$ 和 $(D,C,A)$ 是定向一致的，而 $(B,A,C)$ 和 $(A,C,D)$ 是定向不一致的。

任何具有非流形边缘的网格都无法一致地定向。但是，一个有效的带边界流形网格（甚至是流形），却可能没有一种一致的方式来定向三角形 —— 它们不是可定向表面。一个例子是图 12.5 中所示的莫比乌斯带。然而，在实践中，这很少是一个问题。

图 12.5：一个三角化的莫比乌斯带，它是不可定向的。

12.1.2 索引网格存储

图 12.6 展示了一个简单的三角形网格。你可以将这三个三角形作为独立的实体存储，每个实体采用以下形式：

Triangle {
  vector3 vertexPosition[3]
}

图 12.6：一个由三个三角形组成的网格，包含四个顶点，分别用独立的三角形（左）和共享的顶点（右）表示。

这会导致存储顶点 b 三次以及每个其他顶点两次，总共存储九个点（每个三角形需要三个顶点）。或者，您可以安排共享公共顶点，仅存储四个顶点，从而得到共享顶点网格。逻辑上，此数据结构具有指向包含顶点数据的顶点的三角形（图 12.7）：

Triangle {
  Vertex v[3]
}
 
Vertex {
  vector3 position   // or other vertex data
}

图 12.7：共享顶点网格中的三角形对顶点的引用。

请注意，v 数组中的条目是对顶点对象的引用或指针；顶点不包含在三角形中。

在实现中，通常使用数组存储顶点和三角形，并通过存储数组索引来处理三角形对顶点的引用：

IndexedMesh {
  int tInd[nt][3]
  vector3 verts[nv]
 }

第 $i$ 个三角形的第 k 个顶点的索引可以在 $\bold{tInd}[i][k]$ 中找到，该顶点的位置存储在 verts 数组的相应行中；参见图 12.8 的示例。这种存储共享顶点网格的方法称为索引三角形网格。

图 12.8：一个更大的三角网格，其中一部分表示为索引三角网格。

独立的三角形或共享顶点都可以很好地工作。共享顶点是否有空间优势？如果我们的网格具有 nv 个顶点和 nt 个三角形，并且假设浮点数、指针和整数的数据需要相同的存储（这是一个可疑的假设），则空间需求如下：

• Triangle。每个三角形三个向量，对于 $9_{n_t}$ 个存储单位；
• IndexedMesh。每个顶点一个向量和每个三角形三个整数，对于 $3_{n_v}+3_{n_t}$ 个存储单位。

相对存储要求取决于 $n_t$ 与 $n_v$ 的比率。

这个因素的双倍大小是否值得复杂化呢？我认为答案是肯定的，并且当您开始为顶点添加“属性”时，它会变得更加重要。

作为一个经验法则，在大型网格中，每个顶点通常连接到约 6 个三角形（尽管极端情况下可能有任意数量）。由于每个三角形连接到三个顶点，这意味着在大型网格中通常有两倍的三角形比顶点多：$n_t ≈ 2_{n_v}$。通过进行这种替换，我们可以得出结论，Triangle 结构的存储需求为 $18_{n_v}$，而 IndexedMesh 的存储需求为 $9_{n_v}$。使用共享顶点可以将存储要求减少约一半，并且在大多数实现中这似乎都成立。

12.1.3 三角形带和扇形

索引网格是三角形网格的最常见内存表示，因为它们在简单性、方便性和紧凑性之间取得了良好的平衡。它们也经常用于在应用程序和图形管道之间以及通过网络传输网格。在需要更高的紧凑性的应用中，可以使用三角形带和三角形扇形更有效地表达三角形顶点索引（在只有顶点位置的索引网格中，它们占据了三分之二的空间）。

图 12.9 展示了一个三角形扇形。在索引网格中，三角形数组将包含 $[(0,1,2),(0,2,3),(0,3,4),(0,4,5)]$。我们存储了 12 个顶点索引，尽管只有六个不同的顶点。在三角形扇形中，所有三角形共享一个公共的顶点，而其他顶点会生成一组如可折叠风扇的叶片一样的三角形。图中的扇形可以使用序列 $[0,1,2,3,4,5]$ 指定：第一个顶点确定了中心，在随后的每一对相邻的顶点（$1-2$，$2-3$ 等）创建一个三角形。

图 12.9：三角形扇形示例。

三角形带是一个类似的概念，但它对更广泛的网格有用。此时，顶点交替从上到下添加成线性带状，如图 12.10 所示。图中的三角形带可以由序列 $[0 1 2 3 4 5 6 7]$ 指定，每个连续的三个相邻顶点（$0-1-2$、$1-2-3$ 等）创建一个三角形。为了保持一致的方向，需要每隔一个三角形反转其顺序。在该示例中，这导致了三角形 $(0, 1, 2)，(2, 1, 3)，(2, 3, 4)，(4, 3, 5)$ 等。对于每个进入的新顶点，最老的顶点被遗忘，并且两个剩余顶点的顺序被交换。请参见图 12.11 以获取一个更大的示例。

图 12.10：三角形带示例。

图 12.11：两个三角形带在更大网格的上下文中。请注意，没有一个带可以扩展以包括用星号标记的三角形。

在三角形带和扇形中，$n+2$ 个顶点足以描述 $n$ 个三角形——相对于需要标准索引网格的 $3n$ 个顶点而言，这节省了很多空间。如果程序受到顶点限制，则长三角形带将节省大约三倍的时间。

可能看起来只有当带非常长时三角形带才有用，但是即使是相对较短的带也已经获得了大部分的好处。仅对顶点索引的存储空间节约如下：

纸带长度	1	2	3	4	5	6	7	8	16	100	∞
相对尺寸	1.00	0.67	0.56	0.50	0.47	0.44	0.43	0.42	0.38	0.34	0.33

因此，事实上随着带变得更长，收益会迅速递减。因此，即使是对于非结构化网格，使用一些贪心算法将它们收集到短带中也是值得的。

12.1.4 网格连通性的数据结构

索引网格、带和扇形都是静态网格的良好、紧凑的表示形式。但是，它们不容易允许网格进行修改。为了有效地编辑网格，需要更复杂的数据结构以有效地回答查询，例如：

• 给定一个三角形，它相邻的三个三角形是哪几个？
• 给定一条边，哪两个三角形共享它？
• 给定一个顶点，哪些面共享它？
• 给定一个顶点，哪些边共享它？

有许多用于三角形网格、多边形网格和带孔的多边形网格的数据结构（请参见本章末尾的注释以获取参考文献）。在许多应用程序中，网格非常大，因此使用一种高效的表示形式至关重要。

最直接、但庞大的实现方法是有三种类型：Vertex、Edge 和 Triangle，并直接存储所有关系：

这种表示形式可以很方便地回答上述问题，但它需要很多空间并且缺乏紧凑性。为了实现更高效的查询，需要更复杂但更紧凑的数据结构。

Triangle {
  Vertex v[3]
  Edge e[3]
}
 
Edge {
  Vertex v[2]
  Triangle t[2]
}
 
Vertex {
  Triangle t[]
  Edge e[]
}

这让我们能够直接查找上述连接性问题的答案，但因为这些信息都是相互关联的，所以它会存储比实际需要更多的信息。此外，在顶点中存储连接性会产生可变长度的数据结构（因为顶点可能具有任意数量的邻居），通常不如实现效率高。而不是承诺显式地存储所有这些关系，最好定义一个类接口来回答这些问题，在其后面隐藏一个更高效的数据结构。事实证明，我们只能存储一部分连接性，并在需要时高效地恢复其他信息。

Edge 和 Triangle 类中的固定大小数组表明，在那里存储连接性信息将更有效率。实际上，对于具有任意数量边和顶点的多边形网格，仅边具有固定大小的连接性信息，这导致许多传统网格数据结构基于边。但对于仅包含三角形的网格，将连接性存储在（数量较少的）面中很有吸引力。

良好的网格数据结构应该是相当紧凑的，并允许有效地回答所有邻近查询。高效意味着常数时间：查找邻居的时间不应取决于网格的大小。我们将介绍三种网格数据结构，一种基于三角形，另外两种基于边。

三角形邻接关系结构 (Triangle-Neighbor Structure)

通过在基本的共享顶点网格中增加指向三个相邻三角形的指针，并为每个顶点添加到其中一个相邻三角形的指针（哪个并不重要），我们可以创建一个基于三角形的紧凑网格数据结构；参见图 12.12:

Triangle {
   Triangle nbr[3];
   Vertex v[3];
}
   
Vertex {
   // ... per-vertex data ...
   Triangle t; // any adjacent tri
}

图 12.12：三角形邻接关系结构中三角形和顶点之间的引用。

在数组 Triangle.nbr 中，第 $k$ 个条目指向共享顶点 $k$ 和 $k + 1$ 的相邻三角形。我们称这种结构为三角形邻接关系结构。从标准索引网格数组开始，可以使用两个额外的数组来实现它：一个存储每个三角形的三个邻居，另一个为每个顶点存储一个相邻的三角形（请参见图 12.13 以获取示例）：

Mesh {
   // ... per-vertex data ...
   int tInd[nt][3]; // vertex indices
   int tNbr[nt][3]; // indices of neighbor triangles
   int vTri[nv]; // index of any adjacent triangle
}

图 12.13：编码在数组中的三角形邻接关系结构，以及遍历顶点 2 的相邻三角形所遵循的序列。

显然，可以直接在数据结构中找到三角形和三角形的相邻顶点，但通过仔细使用这种三角形邻接信息，也可以以常数时间回答与顶点相关的连接性查询。想法是从三角形到三角形移动，仅访问与相关顶点相邻的三角形。如果三角形 $t$ 将顶点 $v$ 作为其第 $k$ 个顶点，则三角形 $\bold{t.nbr}[k]$ 是顺时针方向上围绕 $v$ 的下一个三角形。以下算法用于遍历与给定顶点相邻的所有三角形：

当然，实际程序需要在找到它们时对三角形执行某些操作。

TrianglesOfVertex(v) {
   t = v.t
   do {
      find i such that (t.v[i] == v)
      t = t.nbr[i]
   } while (t != v.t)
}

此操作在常数时间内找到每个后续三角形 —— 即使需要搜索每个三角形的顶点列表以找到中心顶点的位置，但由于顶点列表具有常量大小，因此搜索需要常量时间。但是，该搜索很麻烦并且需要额外的分支。

一种小的改进可以避免这些搜索。问题在于，一旦我们从一个三角形跟随指针到达下一个三角形，我们就不知道我们是从哪边来的：我们必须搜索三角形的顶点以找到连接回前一个三角形的顶点。为了解决这个问题，我们可以将指向相邻三角形的指针存储为指向这些三角形的特定边缘的指针，通过在指针中存储索引来实现：

Triangle {
   Edge nbr[3];
   Vertex v[3];
}
   
Edge { // the i-th edge of triangle t
   Triangle t;
   int i; // in {0,1,2}
}
   
Vertex {
   // ... per-vertex data ...
   Edge e; // any edge leaving vertex
}

在实践中，边缘是通过从三角形索引 $t$ 中借用两个位来存储边缘索引 $i$ 来存储的，以便总存储要求保持不变。

在这个结构中，某个三角形的邻居数组告诉我们哪些相邻三角形的边与该三角形的三条边共享。有了这个额外的信息，我们总是知道如何找到原始的三角形，这导致数据结构的一个不变式：对于任何一个三角形 $t$ 的第 $j$ 条边，

t.nbr[j].t.nbr[t.nbr[j].i].t == t

知道我们通过哪个边进入，让我们立即知道要通过哪个边离开，以便继续遍历顶点，从而导致精简的算法：

TrianglesOfVertex(v) {
   {t, i} = v.e;
   do {
     {t, i} = t.nbr[i];
     i = (i+1) mod 3;
   } while (t != v.e.t);
}

三角形邻接关系结构相当紧凑。对于仅具有顶点位置的网格，每个顶点需要存储四个数字（三个坐标和一个边缘），每个面需要存储六个数字（三个顶点索引和三个边缘），总计约为 $4_{n_v} + 6_{n_t} ≈ 16_{n_v}$ 个存储单元，每个顶点比基本索引网格的 $9_{n_v}$ 少。

这里介绍的三角形邻接关系结构仅适用于流形网格，因为它依赖于返回起始三角形以终止遍历顶点的相邻元素，而在没有完整三角形循环的边界顶点上不会发生。然而，通过为边界三角形的邻居引入合适的哨兵值（例如-1）并确保边界顶点指向最逆时针的相邻三角形，而不是任意三角形，不难将其推广到带有边界的流形。

三角形邻接关系结构相当紧凑。对于仅具有顶点位置的网格，每个顶点需要存储四个数字（三个坐标和一个边缘），每个面需要存储六个数字（三个顶点索引和三个边缘），总计约为 $4_{n_v} + 6_{n_t} ≈ 16_{n_v}$ 个存储单元，每个顶点比基本索引网格的 $9_{n_v}$ 少。

这里介绍的三角形邻接关系结构仅适用于流形网格，因为它依赖于返回起始三角形以终止遍历顶点的相邻元素，而在没有完整三角形循环的边界顶点上不会发生。然而，通过为边界三角形的邻居引入合适的哨兵值（例如-1）并确保边界顶点指向最逆时针的相邻三角形，而不是任意三角形，不难将其推广到带有边界的流形。

翼边结构 (Winged-Edge Structure)

一种广泛使用的网格数据结构是翼边数据结构，它将连接信息存储在边缘而不是面上，如图 12.14 和 12.15 所示。该数据结构使边缘成为数据结构的一等公民。

图 12.14：存储在数组中的翼边网格结构示例。

图 12.15：四面体和翼边数据结构的相关元素。两个小表格不唯一；每个顶点和面存储与其关联的任何一个边缘之一。

在翼边网格中，每个边缘存储指向它连接的两个顶点（头部和尾部顶点）、它所属的两个面（左侧面和右侧面），以及最重要的是在左侧面和右侧面逆时针遍历的下一个和前一个边缘（如图 12.16 所示）。每个顶点和面还存储指向连接到它的单个任意边缘的指针：

Edge {
   Edge lprev, lnext, rprev, rnext;
   Vertex head, tail;
   Face left, right;
}
   
Face {
   // ... per-face data ...
   Edge e; // any adjacent edge
}
   
Vertex {
   // ... per-vertex data ...
   Edge e; // any incident edge
}

图 12.16：翼边结构中从边缘到相邻边缘、面和顶点的引用。

翼边数据结构支持常数时间访问面或顶点的边缘，从这些边缘可以找到相邻的顶点或面：

EdgesOfVertex(v) {
   e = v.e;
   do {
      if (e.tail == v)
         e = e.lprev;
      else
         e = e.rprev;
   } while (e != v.e);
}
   
EdgesOfFace(f) {
   e = f.e;
   do {
      if (e.left == f)
         e = e.lnext;
      else
         e = e.rnext;
  } while (e != f.e);
}

这些相同的算法和数据结构在不限于三角形的多边形网格中同样适用；这是基于边缘结构的一个重要优势。

与任何数据结构一样，翼边数据结构进行了各种时间/空间权衡。例如，我们可以消除 prev 引用。这使得在面或顶点周围顺时针遍历或逆时针遍历变得更加困难，但当我们需要知道前一个边缘时，我们总是可以按圆周方向跟随继任边缘，直到回到原始边缘。这节省了空间，但使一些操作变慢。（有关这些权衡的更多信息，请参见本章注释）。

半边结构 (Half-Edge Structure)

翼边结构非常优雅，但仍有一个尴尬之处 —— 不断检查边缘朝向以确定下一个边缘的方向。这个检查类比于我们在三角形邻接结构的基本版本中看到的搜索：我们想知道我们是从头部还是从尾部进入了当前边缘。解决方案也几乎是不可区分的：我们不是为每个边存储数据，而是为每个半边存储数据。每个边的两个三角形都有一个半边，两个半边的方向相反，每个半边都与自己的三角形保持一致地定向。

在两个半边之间分割通常存储在边缘中的数据。每个半边指向其边缘头部的顶点和它所在面的一侧，并且每个半边包含其面的边缘指针（如图 12.17 所示）。它还指向另一侧边缘上的邻居，从中可以找到其他一半信息。像翼边一样，半边可以包含指向其面周围先前和下一个半边的指针，或仅包含指向下一个半边的指针。我们将展示使用单个指针的示例。

图 12.17：半边到其相邻网格组件的引用。

HEdge {
   HEdge pair, next;
   Vertex v;
   Face f;
}
Face {
   // ... per-face data ...
   HEdge h; // any h-edge of this face
}
Vertex {
   // ... per-vertex data ...
   HEdge h; // any h-edge pointing toward this vertex
}

遍历半边结构就像遍历翼边结构一样，只是不再需要检查定向，并且跟随对指向相反面的边的指针进行访问。

EdgesOfVertex(v) {
   h = v.h;
   do {
      h = h.pair.next;
   } while (h != v.h);
}
EdgesOfFace(f) {

   h = f.h;
   do {
      h = h.next;
   } while (h != f.h);
}

这里的顶点遍历是顺时针遍历，这是因为省略了结构中的 prev 指针所必需的。

由于半边通常成对分配（至少在没有边界的网格中），因此许多实现可以省去对偶指针。例如，在基于数组索引的实现中（如图 12.18 所示），可以排列数组，使偶数边 $i$ 总是与边 $i + 1$ 配对，奇数编号边 $j$ 总是与边 $j-1$ 配对。

图 12.18：存储在数组中的半边网格结构示例。

除了本章展示的简单遍历算法之外，这三种网格拓扑结构都可以支持各种“网格手术”操作，例如分裂或折叠顶点、交换边缘、添加或删除三角形。

12.2 场景图

三角网格管理构成场景中对象的三角形集合，但是图形应用程序中的另一个通用问题是将对象排列在所需位置。正如我们在第 7 章中看到的那样，这可以使用变换来完成，但是复杂的场景可能包含大量的变换，良好组织它们使场景更容易操作。大多数场景都具有分层组织方式，并且可以根据此层次结构管理变换，使用场景图。

为了激发场景图数据结构的动机，我们将使用图 12.19 中显示的铰链摆。考虑如何绘制摆的上部：

图 12.19：铰链摆。左边是两个部件在它们的“本地”坐标系中。底部部件的铰链位于点 b 处，底部部件的附件位于其本地原点处。组装对象的自由度是顶部铰链的角度 $(θ,ϕ)$ 和位置 $\bold p$。

底部更加复杂，但我们可以利用它与上摆底部在本地坐标系中以点 $\bold b$ 相连接的事实。首先，我们旋转下摆，使其相对于初始位置成为一个角度 $ϕ$。然后，我们将其移动，使其顶部铰链位于点 $\bold b$ 处。现在它在上摆本地坐标系中的适当位置，并且可以随着该坐标系一起移动。下摆的组合变换为

因此，我们不仅看到下摆存在于其自己的本地坐标系中，而且该坐标系本身也随着上摆的坐标系一起移动。

我们可以使用数据结构对摆进行编码，从而使这些坐标系问题的管理更容易，如图 12.20 所示。应用于对象的适当矩阵仅是从对象到数据结构根部的所有矩阵链的乘积。例如，考虑具有可以在轮渡甲板上自由移动的汽车和每个相对于汽车移动的轮子的轮渡模型，如图 12.21 所示。

图 12.20：图 12.19 所示的铰链摆的场景图。

图 12.21：一个轮渡，上有一辆汽车和汽车的轮子（只显示两个），它们存储在场景图中。

与摆相同，每个对象应该通过从根到对象路径上的矩阵乘积进行变换：

• 使用 $M_0$ 对轮渡变换；
• 使用 $M_0M_1$ 对汽车主体进行变换；
• 使用 $M_0M_1M_2$ 对左轮进行变换；
• 使用 $M_0M_1M_3$ 对右轮进行变换。

12.2.1 在光栅化中

在栅格化情况下，可以使用矩阵堆栈，这是许多 API 支持的数据结构，来实现高效的实现。矩阵堆栈使用 push 和 pop 操作进行操作，从矩阵乘积的右侧添加和删除矩阵。例如，调用

创建活动矩阵 $M = M_0M_1M_2$。随后调用 pop() 会剥离最后添加的矩阵，使活动矩阵变为 $M = M_0M_1$。将矩阵堆栈与场景图的递归遍历相结合，得到：

场景图有许多变体，但都遵循上述基本思想。

12.2.2 在光线追踪中

光线追踪的一个优雅特性是，它允许非常自然地应用变换，而不会改变几何体的表示。实例化的基本思想是在对象显示之前通过变换矩阵扭曲所有点。例如，如果我们将单位圆（在 2D 中）按 $x$ 和 $y$ 分别缩放因子 $(2,1)$，然后旋转 $45°$，并向 $x$ 方向移动一单位，则结果是一个偏心率为 2 且长轴沿 $(x = −y)$ 方向的椭圆，其中心在 $(0,1)$（图 12.22）。使该实体成为“实例”的关键是我们存储了圆和组合变换矩阵。因此，椭圆的显式构造留待以后在渲染时进行操作。

图 12.22：通过一系列三次变换的圆的实例是一个椭圆。

在光线追踪中实例化的优点是可以选择交点所在的空间。如果基础对象由一组点组成，其中之一是 $\bold p$，则变换后的对象由该组点通过矩阵 $\bold M$ 进行变换组成，其中示例点被变换为 $\bold M_p$。如果我们有一个我们想要与变换后的对象相交的射线 $\bold a + t\bold b$，则可以改为使用逆变换的射线 (inverse-transformed ray) 与未变换的对象相交（图 12.23）。在未变换的空间中计算的潜在优点有两个（即图 12.23 右侧）：

1. 未变换的对象可能具有更简单的交点例程，例如球体与椭球。
2. 许多变换后的对象可以共享同一个未变换的对象，从而减少存储量，例如汽车堵塞，其中单个汽车只是几个基本（未变换）模型的变换。

图 12.23：两个空间中的射线交点问题只是彼此的简单变换。对象由球体加矩阵 $\bold M$ 指定。射线在变换后的（世界）空间中由位置 $\bold a$ 和方向 $\bold b$ 指定。

如 7.2.2 节所讨论的，表面法向量的变换方式不同。考虑到这一点，并使用图 12.23 中说明的概念，我们可以确定射线和通过矩阵 $\bold M$ 进行变换的对象之间的交点。如果我们创建一个类型为 surface 的实例类，则需要创建一个 $hit$ 函数：

该函数的一个优雅之处在于参数 rec.t 无需更改，因为在任何空间中它都是相同的。还要注意，我们无需计算或存储矩阵 $\bold M$。

这带来了一个非常重要的问题：射线方向 $\bold b$ 不能限制为单位长度向量，否则上述任何基础结构都不起作用。因此，不将射线方向限制为单位向量很有用。

12.3 空间数据结构

在许多（如果不是所有）图形应用程序中，快速定位特定空间区域内的几何对象的能力非常重要。光线追踪器需要查找与射线相交的对象；导航环境的交互式应用程序需要查找从任何给定视点可见的对象；游戏和物理模拟需要检测对象何时以及在哪里发生碰撞。所有这些需求都可以通过各种空间数据结构来支持，这些结构旨在将对象组织在空间中，以便可以高效地查找它们。

在本节中，我们将讨论三类空间数据结构的示例。将对象分组到层次结构中的结构是对象分割方案：对象被分成不相交的组，但组可能在空间中重叠。将空间划分为不相交区域的结构是空间分割方案：空间被划分为单独的分区，但一个对象可能必须与多个分区相交。空间分割方案可以是规则的，在此空间被均匀地划分为各种形状的部分，也可以是不规则的，在此空间被自适应地划分为不规则的部分，在其中有更多和更小的对象的地方有更小的部分。

在讨论这些结构时，我们将以光线追踪为主要动机，尽管它们也可以用于视图剔除或碰撞检测。在第 4 章中，所有对象都在检查相交时进行了循环遍历。对于 N 个对象，这是一个 O(N) 复杂度的线性搜索，因此对于大型场景而言速度较慢。像大多数搜索问题一样，如果我们可以创建一个有序数据结构作为预处理，就可以使用“分而治之”的技术在次线性时间内计算射线-对象相交。有许多技术可以做到这一点。

本节详细讨论了其中三种技术：包围体层次结构（Rubin＆Whitted，1980；Whitted，1980；Goldsmith＆Salmon，1987），均匀空间子划分（Cleary，Wyvill，Birtwistle＆Vatti，1983；Fujimoto，Tanaka，Iwata，1986；Amanatides＆Woo，1987）和二进制空间分割（Glassner，1984；Jansen，1986；Havran，2000）。第一和第二种策略的示例如图 12.24 所示。

图 12.24：（a）空间的均匀分割。 （b）自适应边界框层次结构。图片由 David DeMarle 提供。

12.3.1 包围盒

大多数相交加速方案中的关键操作是计算射线与包围盒的相交（图 12.25）。这与传统的相交测试不同，因为我们不需要知道射线在哪里碰到了盒子；我们只需要知道它是否与盒子相交。

图 12.25。仅当射线与包围盒相交时才会对表面进行相交测试。

为了建立射线-盒相交算法，我们首先考虑一个二维射线，其方向向量具有正的 $x$ 和 $y$ 分量。稍后我们可以将其推广到任意三维射线。2D 边界框由两条水平线和两条垂直线定义：

$$x=x_{min}, \\ x=x_{max}, \\ y=y_{min}, \\ y=y_{max}$$

这些线所限制的点可以用区间表示法描述：

$$\begin{array}{c} (x, y) \in\left[x_{\min }, x_{\max }\right] \times\left[y_{\min }, y_{\max }\right] \end{array}$$

如图 12.26 所示，相交测试可以根据这些区间来表述。首先，我们计算射线在 $x = x_{min}$ 处撞击线的射线参数：

$$t_{xmin}={x_{min}−x_e \over x_d}$$

图 12.26。射线将在其参数空间 $t∈[t_{xmin},t_{xmax}]$ 中的某个区间内，处于 $x∈[xmin,xmax]$ 的区间内。$y$ 区间也存在类似的区间。当且仅当射线同时位于 $x$ 区间和 $y$ 区间时（即，两个一维区间的交集不为空）射线与盒子相交。

然后我们对 $t_{xmax}$，$t_{ymin}$ 和 $t_{ymax}$ 进行类似的计算。当且仅当区间 $[t_{xmin}，t_{xmax}]$ 和 $[t_{ymin}，t_{ymax}]$ 重叠时，射线撞击盒子；即，它们的交集不为空。该算法的伪代码为：

if 语句可能看起来不太明显。为了理解它的逻辑，请注意，如果第一个区间整体在第二个区间的右侧或左侧，则不存在重叠。

我们必须解决的第一件事是 $x_d$ 或 $y_d$ 为负数的情况。如果 $x_d$ 为负，则射线会在撞击 $x_{min}$ 之前撞击 $x_{max}$。因此，计算 $t_{xmin}$ 和 $t_{xmax}$ 的代码扩展到

对于 $y$ 情况也需要进行类似的代码扩展。一个主要问题是水平和垂直射线分别具有 $y_d$ 和 $x_d$ 的零值。这将导致除以零，可能会成为问题。但是，在直接解决此问题之前，我们先检查 IEEE 浮点运算是否能优雅地处理这些情况。回顾第 1.5 节中除以零的规则：对于任何正实数 $a$，

$$+a/0=+∞ \\ −a/0=−∞$$

考虑 $x_d = 0$ 且 $y_d> 0$ 的垂直射线的情况。然后我们可以计算

$$t{xmin} ={x_{min}−x_e \over 0} \\ \space \\ t{xmax}={x_{max}−x_e \over 0}$$

有三种情况值得注意：

1. $x_e ≤ x{min} (no \space hit)$
2. $x_{min} < x_e < x_{max} (hit)$
3. $x_{max} ≤ x_e (no \space hit)$

对于第一种情况，我们有

$$t_{xmin} = {正数 \over 0} \\ \space \\ t_{xmax} = {正数 \over 0}$$

这导致区间 $(t_{xmin},t_{xmin}) = (∞,∞)$。该区间不会与任何区间重叠，因此不会发生碰撞，符合要求。对于第二种情况，我们有

$$t_{xmin} = {负数 \over 0} \\ \space \\ t_{xmax} = {正数 \over 0}$$

这产生区间 $(t_{xmin},t_{xmin}) = (-∞,∞)$，它将与所有区间重叠，因此将产生所需的碰撞。第三种情况的结果是区间 $(-∞,-∞)$，这不会发生碰撞，符合要求。由于这些情况按预期工作，因此我们不需要对它们进行特殊检查。通常情况下，IEEE 浮点约定是我们的盟友。但是，这种方法仍然存在问题。

考虑以下代码段：

当 $x_d = −0$ 时，这段代码会出现问题。可以通过对 $x_d$ 的倒数进行测试来克服这个问题（Williams、Barrus、Morley 和 Shirley，2005）：

12.3.2 分层包围盒

分层包围盒的基本思想可以通过将轴对齐的三维包围盒放置在所有对象周围来看到，如图 12.27 所示。与包围盒相交的射线实际上比暴力搜索更昂贵，因为测试是否与盒子相交不是免费的。然而，与未命中盒子的射线比暴力搜索更便宜。可以通过将一组对象分区并在每个分区周围放置一个盒子来使此类包围盒成为分层结构，如图 12.28 所示。图 12.29 中显示的层次结构的数据结构可能是具有根处大包围盒和两个较小包围盒作为左右子树的树。这又将各自指向三角形列表。射线与这种硬编码树的相交将是：

图 12.27. 2D 射线 $\bold e + \bold t_d$ 被测试是否与 2D 包围盒相交。

图 12.28。可以通过在模型的子集周围创建盒子来嵌套包围盒。

图 12.29。灰色框是指向三个灰色球体的树节点，厚黑色框指向三个黑色球体。请注意，不保证所有由框框住的球体都被相应的树节点指向。

一些与此算法相关的观察是，两个子树之间没有几何排序，射线可能同时击中两个子树，而且两个子树可能会重叠。

这种数据层次结构的关键点是，一个盒子保证包围其下层级的所有对象，但不能保证包含所有在空间上重叠它的对象，如图 12.29 所示。这使得这种几何搜索比严格有序的一维数据上的传统二分搜索要复杂一些。读者可以注意到几种可能的优化方法。我们将推迟优化，直到我们有完整的分层算法为止。

如果我们将树限制为二叉树，并要求树中的每个节点都具有边界框，则此遍历代码自然扩展。此外，假设树中的所有节点均为叶节点，并包含一个基元，或者它们包含一个或两个子树。

bvh-node 类应为 surface 类型，因此应实现 surface::hit。它包含的数据应该是简单的：

遍历代码可以以面向对象的方式递归调用：

请注意，由于左右 (left、right) 指向的是表面而不是特定的 bvh-node，因此我们可以让虚拟函数负责区分内部和叶节点；将调用适当的 hit 函数。请注意，如果树构建正确，我们可以消除对 left 是否为 NULL 的检查。如果要消除对 right 是否为 NULL 的检查，可以用一个冗余指向 left 的指针替换 NULL right 指针。这最终会检查两次左边，但会消除整个树中的检查。是否值得这样做取决于树构建的细节。

有很多方法可以为包围体层次结构构建树。方便起见，使树二进制、大致平衡，并且兄弟子树的盒子不重叠太多。一种实现此目标的启发式方法是在沿着轴将表面排序之前将其划分为两个子列表。如果轴由 $x = 0$、$y = 1$ 和 $z = 2$ 定义，则我们有

通过仔细选择每个轴（AXIS），可以改善树的质量。一种方法是选择该轴，使得两个子树的边界框体积之和最小化。与通过旋转轴相比，这种改变对由等向分布的小对象构成的场景几乎没有影响，但在行为不太好的场景中可能会有很大的帮助。这段代码也可以通过执行分区而不是完整排序来更高效地实现。

另一种建立树的方法，可能更好的方法是让子树包含大致相同数量的空间而不是相同数量的对象。

为此，我们基于空间对列表进行划分：

虽然这会导致一个不平衡的树，但它允许轻松遍历空间，并且构建成本更低，因为分区比排序更便宜。

12.3.3 均匀空间细分

减少相交测试的另一种策略是划分空间。这与使用分层边界体对对象进行划分 fundamentally 不同：

在分层边界体中，每个对象属于两个兄弟节点之一，而空间中的一个点可能在两个兄弟节点内。

在空间细分中，空间中的每个点都属于恰好一个节点，而对象可能属于多个节点。

在均匀空间细分中，场景被划分为轴对齐的盒子。虽然这些盒子不一定是立方体，但它们的大小都相同。如图 12.30 所示，射线穿过这些盒子。当击中对象时，遍历结束。

图 12.30。在均匀空间细分中，射线前向跟踪通过单元格，直到击中其中一个单元格中的对象为止。在这个例子中，只检查了阴影单元格中的对象。

网格本身应该是 surface 的一个子类，并且应该实现为指向 surface 的 3D 数组指针。对于空单元格，这些指针为 NULL。对于只有一个对象的单元格，指针指向该对象。对于具有多个对象的单元格，指针可以指向列表、另一个网格或另一个数据结构，如包围盒层次结构。

这种遍历是以增量方式进行的。规则性来自射线如何击中每组平行的平面，如图 12.31 所示。要了解此遍历的工作原理，请先考虑 2D 情况，其中射线方向具有正 $x$ 和 $y$ 分量，并且从网格外部开始。假设网格由点 $(x_{min}, y_{min})$ 和 $(x_{max}, y_{max})$ 界定。网格具有 $n_x × n_y$ 个单元格。

图 12.31。尽管单元格命中模式似乎不规则（左图），但平行平面的命中非常均匀。

我们首先需要找到由射线 $e + t_d$ 击中的第一个单元格的索引 $(i, j)$。然后，我们需要以适当的顺序遍历单元格。此算法的关键部分是找到初始单元格 $(i, j)$ 并决定是否增加 $i$ 或 $j$（如图 12.32 所示）。请注意，当我们检查单元格中对象的相交时，我们限制 $t$ 的范围在单元格内（如图 12.33 所示）。大多数实现将 3D 数组类型设置为“指向 surface 的指针”。为提高遍历的局部性，可以按照第 12.5 节中讨论的方式对数组进行平铺。

图 12.32。为了决定我们是向右还是向上前进，我们跟踪与单元格的下一个垂直和水平边界的相交点。

图 12.33。只应报告单元格内的命中。否则，上面的情况会导致我们报告击中对象 b 而不是对象 a。

12.3.4 轴对齐二进制空间划分

我们还可以在层次数据结构（例如二进制空间划分树（BSP 树））中划分空间。这类似于第 12.4 节中用于可见性排序的 BSP 树，但最常用的是轴对齐切割平面而不是多边形对齐切割平面进行射线相交。

此结构中的节点包含单个切割平面和左右子树。每个子树包含切割平面一侧的所有对象。通过平面的对象存储在两个子树中。如果我们假设切割平面与 $x = D$ 的 $y_z$ 平面平行，则节点类为

我们稍后将其推广到 $y$ 和 $z$ 切割平面。然后以面向对象的方式递归调用交点代码。该代码考虑了图 12.34 中显示的四种情况。对于我们的目的，这些光线的起点是参数 $t_0$ 处的一个点：

$$\bold p = \bold a + t_0 \bold b$$

图 12.34。光线与 BSP 切割平面 $x = D$ 的四种情况。

这四种情况是：

1. 光线仅与左子树交互，并且我们不需要对其进行与切割平面的相交测试。当 $x_p < D$ 且 $x_b < 0$ 时发生。
2. 射线针对左子树进行测试，如果没有命中，则继续对右子树进行测试。我们需要找到 $x = D$ 处的射线参数，以便确保我们只测试子树内的相交点。当 $x_p < D$ 且 $x_b > 0$ 时会出现这种情况。
3. 此情况类似于第 1 种情况，当 $x_p > D$ 且 $x_b > 0$ 时发生。
4. 此情况类似于第 2 种情况，当 $x_p > D$ 且 $x_b < 0$ 时发生。

处理这些情况的遍历代码如下：

这是非常干净的代码。然而，为了开始遍历，我们需要击中包含边界框的根对象，以便初始化遍历 t0 和 t1。我们需要解决的一个问题是切割平面可能沿任何轴。我们可以在 bsp-node 类中添加整数索引 axis。如果我们允许点的索引运算符，那么这将导致代码上述部分的一些简单修改，例如：

$$x_p = x_a + t_0x_b$$

将成为

$$u_p = a[\bold {axis}] + t_0b[\bold {axis}]$$

这将导致一些额外的数组索引，但不会生成更多的分支。

虽然处理单个 bsp-node 比处理 bvh-node 更快，但一个表面可能存在于多个子树中，这意味着有更多的节点，潜在地使用更多的内存。“树”建造得“好坏”决定哪个更快。构建树与构建 BVH 树类似。我们可以选择循环拆分轴，并且每次可以等分拆分，或者我们可以尝试更复杂地进行分割。

12.4 用于可见性的 BSP 树

另一个空间数据结构可以用于的几何问题是确定具有不同视点的场景中对象的可见性排序。

如果我们需要从不同的视点制作由平面多边形组成的固定场景的多个图像（如游戏等应用程序中经常出现的情况），我们可以使用与前面部分讨论射线相交方法密切相关的二叉空间分割 (binary space partitioning) 方案。不同之处在于，在可见性排序中，我们使用非轴对齐的分裂平面，使平面可以与多边形重合。这导致一种优雅的算法称为 BSP 树算法，用于将表面从前到后排序。BSP 树的关键方面在于它使用预处理来创建对任何视点都有用的数据结构。因此，随着视点的变化，同样的数据结构在不发生改变的情况下被使用。

12.4.1 BSP 树算法概述

BSP 树算法是绘制算法的一个例子。绘制算法从后向前绘制每个对象，每个新多边形都可能覆盖以前的多边形，如图 12.35 所示。可以按照以下方式实现：

sort objects back to front relative to viewpoint
for each object do
     draw object on screen

第一步（排序）的问题在于即使每对对象的顺序都已确定，多个对象的相对顺序并不总是明确定义的。这个问题在图 12.36 中进行了说明，其中三角形形成一个循环。

图 12.36。如果特定的眼睛位置不可能进行全局从后向前排序，则会出现循环。

BSP 树算法适用于由多边形组成的任何场景，其中没有多边形穿过由其他多边形定义的平面。然后通过预处理步骤放宽这个限制。在本讨论的其余部分，三角形被假定为唯一的基元，但这些想法可以推广到任意多边形。

BSP 树的基本思想可以用两个三角形 $T_1$ 和 $T_2$ 来说明。我们首先回忆一下（参见第 2.7.3 节）包含 $T_1$ 的平面的隐式方程：$f_1(\bold p)_ = 0$。我们希望利用隐式平面的关键属性，即对于一个位于平面一侧的点 $\bold p+$，有 $f_1(\bold p+) > 0$; 对于另一侧的点 $\bold p-$，有 $f_1(\bold p-) < 0$。利用这个属性，我们可以找出 $T_2$ 在平面的哪一侧。同样地，这需要假设 $T2$ 的所有三个顶点都在平面的相同侧。对于讨论，假设 $T_2$ 位于平面的 $f_1(\bold p) <0$ 侧。那么，我们可以为任何眼点 $\bold e$ 正确绘制 $T_1$ 和 $T_2$：

这种方法有效的原因在于，如果 $T_2$ 和 $\bold e$ 位于包含 $T_1$ 的平面的同一侧，那么从 $\bold e$ 的视角看，$T_2$ 不可能被 $T_1$ 完全或部分遮挡，因此可以先安全地绘制 $T_1$。如果 $\bold e$ 和 $T_2$ 位于包含 $T1$ 的平面的相反侧，则 $T_2$ 无法完全或部分遮挡 $T_1$，而另一种绘制顺序是安全的（图 12.37）。

图 12.37。当 $\bold e$ 和 $T_2$ 位于包含 $T_1$ 的平面的相反侧时，先绘制 $T_2$ 然后再绘制 $T_1$ 是安全的。如果 $\bold e$ 和 $T_2$ 位于同一侧，则应该先绘制 $T_1$，然后再绘制 $T_2$。这是 BSP 树算法的核心思想。

只要没有任何对象跨越由 $T_1$ 定义的平面，我们就可以将这个观察推广到许多物体。如果我们使用以 $T_1$ 为根的二叉树数据结构，负分支包含所有顶点 $f_i(\bold p) < 0$ 的三角形，正分支包含所有顶点 $f_i(\bold p) > 0$ 的三角形。我们可以按正确的顺序绘制如下：

这段代码的好处在于它适用于任何视点 $\bold e$，因此可以预计算树。请注意，如果每个子树本身都是一个树，其中根三角形将其他三角形相对于包含它的平面分成两组，则代码将按原样工作。通过在更高的层次终止递归调用，可以使其稍微更有效率，但代码仍然简单。图 12.38 显示了说明此代码的树。如第 2.7.5 节所讨论的，包含三个非共线点 $a$、$b$ 和 $c$ 的平面上的点 $p$ 的隐式方程是

$$f(\bold p)=((\bold b− \bold a)×(\bold c− \bold a))⋅(\bold p− \bold a)=0. \tag{12.1}$$

图 12.38。三角形和适用于它们的 BSP 树。“正”和“负”由右子树和左子树位置编码，分别表示。

存储形式为

$$f(x,y,z) = Ax + By + Cz + D = 0 \tag{12.2}$$

的隐式方程（A、B、C、D）可能更快。当您回忆到隐式方程的梯度是三角形的法向量时，方程（12.1）和（12.2）是等价的。方程（12.2）的梯度是 $n = (A,B,C)$，它就是法向量

$$\bold n=(\bold b− \bold a)×(\bold c− \bold a)$$

我们可以通过插入平面上任意一点（例如 a）来解决 $D$：

$$D=−Axa−Bya−Cza=−\bold n⋅\bold a$$

这表明形式为

$$f(\bold p)=\bold n⋅\bold p−\bold n⋅\bold a=\bold n⋅(\bold −\bold a)=0$$

的方程与方程（12.1）相同，当您记住使用叉乘计算 $\bold n$ 时。您使用哪种形式的平面方程以及是否仅存储顶点、$\bold n$ 和顶点或 $\bold n$、$D$ 和顶点，可能只是品味问题 —— 经典的时间-空间权衡，最好通过性能监测来解决。对于调试，使用公式（12.1）可能是最好的。

唯一阻止上述代码一般工作的问题是不能保证三角形可以唯一地分类为平面的一侧或另一侧。它可以在平面的一侧具有两个顶点，而在另一侧具有第三个顶点。或者它可以在平面上具有顶点。这通过使用平面将三角形“切割”成较小的三角形来处理。

12.4.2 构建 BSP 树

如果数据集中的三角形都没有跨越彼此的平面，使得所有三角形都在其他三角形的一侧，则可以使用以下算法构建可以使用上面的代码遍历的 BSP 树：

唯一需要修正的是三角形穿过分割平面的情况，如图 12.39 所示。为简单起见，假设三角形有顶点 a 和 b 在平面的一侧，顶点 c 在另一侧。在这种情况下，我们可以找到交点 A 和 B，并将三角形切成具有顶点的三个新三角形

$$T_1= (\bold a, \bold b, \bold A), \\ T_2= (\bold b, \bold B, \bold A), \\ T_3= (\bold A, \bold B, \bold c)$$

图 12.39。当三角形跨越平面时，将有一个顶点在一侧，两个顶点在另一侧。

如图 12.40 所示。这些顶点的顺序很重要，以使法线方向与原始三角形相同。如果我们假设 $f(\bold c) < 0$，则以下代码可以将这三个三角形添加到树中，假定正子树和负子树不为空：

• positive-subtree = node ($T_1$)
• positive-subtree = node ($T_2$)
• negative-subtree = node ($T_3$)

图 12.40。当一个三角形被切割时，我们将它分成三个三角形，没有一个跨越切割平面。

一个粗糙的实现可能会遇到的一个精度问题是当顶点非常靠近切割平面时。例如，如果我们在切割平面的一侧有两个顶点，而另一个顶点仅仅在另一侧一个极小的距离上，我们将创建一个几乎与旧三角形相同的新三角形，即一个极度细长（sliver）的三角形，以及一个几乎为零大小的三角形。更好的方案是将其检测为特殊情况并不分裂成三个新三角形。这种情况可能会很少发生，但由于许多模型具有细分平面和共享顶点的三角形，因此经常发生，因此必须小心处理。一些简单的操作包括：

这需要任何 $f$ 值在平面上的 $ϵ$ 范围内的顶点，并将其视为正或负。常量 $ϵ$ 是由用户选择的小正实数。上述技术是测试浮点相等性很少有用且有效的罕见例子，因为零值是设置而不是计算得出的。与计算的浮点值进行相等性比较几乎从来不可取，但我们没有这样做。

12.4.3 切割三角形

填充最后一种情况“将三角形分成三个三角形并添加到每一侧”细节很直接，但很繁琐。我们应该利用 BSP 树构造作为预处理，其中最高效性不是关键。相反，我们应该尝试拥有一个干净简洁的代码。一个好的技巧是通过确保 $\bold c$ 在平面的一侧，而另外两个顶点在另一侧，将许多情况强制合并为一个情况。这很容易通过交换完成。填充 else 语句中的细节（为简单起见，假设子树非空）给出

该代码利用了如果 $\bold a$ 和 $\bold b$ 的符号相同，则它们的乘积为正的事实，因此使用了第一个 if 语句。如果顶点被交换，我们必须执行两次交换以保持顶点逆时针排序。请注意，恰好有一个顶点可能完全位于平面上，在这种情况下，上面的代码将起作用，但生成的三角形中将有一个零面积的三角形。这可以通过忽略可能性来处理，这不是太危险，因为光栅化代码必须在屏幕空间（即边缘三角形）处理零面积三角形。也可以添加检查，不将零面积三角形添加到树中。最后，您可以针对 $fa$，$fb$ 和 $fc$ 中恰好有一个为零的特殊情况，将三角形切成两个三角形。

要计算 A 和 B，需要进行线段和隐式平面交点的计算。例如，连接 a 和 c 的参数线为

$$\bold p(t) = \bold a + t(\bold c - \bold a)$$

通过将 $\bold p(t)$ 插入平面方程，可以找到与平面 $\bold n⋅\bold p+ D= 0$ 相交的点：

$$\bold n⋅( \bold a+t(\bold c− \bold a))+D=0$$

并解出 $t$：

$$t = {−\bold n⋅ \bold a+D \over \bold n⋅(\bold c− \bold a)}$$

称此解为 $t_A$，我们可以写出 A 的表达式：

$$\bold A = \bold a +t_A(\bold c - \bold a)$$

类似的计算将给出 B。

12.4.4 优化树

与树的遍历相比，树的创建效率要低得多，因为它是预处理。BSP 树的遍历时间与树中节点数成正比。（树的平衡程度并不重要。）每个三角形将有一个节点，包括由于分割而创建的三角形。这个数字可能取决于将三角形添加到树中的顺序。例如，在图 12.41 中，如果 $T_1$ 是根，则树中将有两个节点，但如果 $T_2$ 是根，则将有更多的节点，因为 $T_1$ 将被分割。

图 12.41。使用 $T_1$ 作为 BSP 树的根将导致具有两个节点的树。如果使用 $T_2$ 作为根，则需要进行切割，从而使树更大。

很难找到添加到树中的三角形的“最佳”顺序。对于 N 个三角形，可能有 N! 种可能的排序方式。因此，通常无法尝试所有排列。或者，可以从随机收集的排列中尝试一些预定数目的排列，并将最佳排序保留为最终树。

上面描述的分割算法将一个三角形分成三个三角形。将一个三角形分成三角形和凸四边形可能更有效。如果所有输入模型仅包含三角形，则这可能不值得，但对于支持任意多边形的实现来说，这将很容易支持。

12.5 平铺多维数组

在设计适用于现代体系结构的算法时，有效利用内存层次结构是关键任务。通过平铺（有时也称为砖块化）确保多维数组具有“不错”的排列。传统 2D 数组将存储为与索引机制一起的 1D 数组；例如，Nx \times Ny 数组存储在长度为 NxNy 的 1D 数组中，而 2D 索引 $(x,y)$ （范围从 $(0,0)$ 到 $(N_x-1,N_y-1)$ ）将映射到 1D 索引（范围从 0 到 $N_xN_y-1$），使用公式

$$\bold {index}=x+N_xy$$

如图 12.42 所示，内存的布局示例。这种布局的问题是，虽然在同一行中的两个相邻数组元素在内存中是相邻的，但在同一列中的两个相邻元素将在内存中由 $N_x$ 个元素隔开。对于大的 $N_x$，这可能会导致内存局部性较差。解决此问题的标准方法是使用平铺使得行和列的内存局部性更加均衡。例如，在图 12.43 中使用 $2×2$ 瓷砖。有关索引此类数组的详细信息将在下一节讨论。在此之后，将介绍具有三维阵列的两个平铺级别的更复杂的示例。

图 12.42。具有 $Nx = 4$ 和 $Ny = 3$ 的未平铺 2D 数组的内存布局。

图 12.43。使用 $N_x = 4$ 和 $N_y = 3$ 以及 $2×2$ 瓷砖的平铺 2D 数组的内存布局。请注意，需要在阵列顶部进行填充，因为 $N_y$ 不是瓷砖大小 2 的倍数。

一个关键问题是要将瓷砖的大小设置为多少。在实践中，它们应该与机器上的内存单元大小相似。例如，如果我们正在使用 128 字节缓存行的 16 位（2 字节）数据值，那么 $8×8$ 瓷砖恰好适合缓存行。但是，对于适合 32 个元素的高速缓存线的 32 位浮点数，$5×5$ 瓷砖有点太小，而 6×6 瓷砖有点太大。由于还有较粗的内存单元，例如页面，因此具有类似逻辑的分层平铺可能很有用。

12.5.1 二维数组的单级平铺

如果我们假设一个 $N_x$ \times $N_y$ 数组被分解成正方形 $n \times n$ 瓷砖（图 12.44），那么所需的瓷砖数量为

图 12.44。由大小为 $n \times n$ 的瓷砖组成的 $B_x \times B_y$ 瓷砖的平铺 2D 数组。

$$B_x = N_x / n, \\ B_y = N_y / n$$

在这里，我们假设 $n$ 恰好整除 $N_x$ 和 $N_y$。如果不是这样，则应填充阵列。例如，如果 $N_x = 15$ 且 $n = 4$，则 $N_x$ 应更改为 16。要计算此类阵列的索引公式，我们首先找到为瓷砖提供行/列的瓷砖索引 $(b_x, b_y)$ （瓷砖本身形成 2D 数组）：

$$b_x = x÷n, \\ b_y = y÷n$$

其中÷是整数除法，例如 $12÷5 = 2$。如果我们按行对瓷砖进行排序，如图 12.42 所示，则瓷砖 $(b_x, b_y)$ 的第一个元素的索引为

$$\bold {index} = n^2(B_xb_y + b_x)$$

该瓷砖中的内存像图 12.43 所示的传统 2D 数组一样排列。瓷砖内的部分偏移量 $(x', y')$ 为

$$x' = x \space \bold{mod} \space n, \\ y' = y \space \bold{mod} \space n$$

其中 mod 是余数运算符，例如 12 mod 5 = 2。因此，在瓷砖内的偏移量为

$$\bold{offset} = y'n + x'$$

因此，找到具有 $n$ \times $n$ 瓷砖的 $N_x$ \times $N_y$ 阵列中元素 $(x,y)$ 的 1D 索引的完整公式为

$$\begin{array}{c} \text { index } & =n^{2}\left(B_{x} b_{y}+b_{x}\right)+y^{\prime} n+x^{\prime} \\ & =n^{2}\left(\left(N_{x} \div n\right)(y \div n)+x \div n\right)+(y \bmod n) n+(x \bmod n) \end{array}$$

该表达式包含许多整数乘法、除法和模数运算，在某些处理器上成本很高。当 $n$ 是 $2$ 的幂时，这些操作可以转换为位移和按位逻辑操作。然而，如上所述，理想大小并不总是 $2$ 的幂。一些乘法可以转换为移位/加法操作，但除法和模数运算更为棘手。指标可以逐步计算，但这将需要跟踪计数器，涉及许多比较和性能差的分支预测。

然而，有一个简单的解决方案；注意到索引表达式可以写成

$$\bold{index} = F_x(x) + F_y(y)$$

其中

$$F_x(x) = n^2(x÷n) + (x \space \bold{mod} \space n), \\ F_y(y) = n^2(N_x÷n)(y÷n) +(y \space \bold{mod} \space n)n$$

我们制表 $F_x$ 和 $F_y$，并使用 $x$ 和 $y$ 找到数据阵列的索引。这些表分别由 $N_x$ 和 $N_y$ 个元素组成。即使对于非常大的数据集大小，表的总大小也适合处理器的主要数据缓存中。

12.5.2 示例：三维数组的双层平铺

有效的 TLB 利用率也成为算法性能的关键因素。相同的技术可以通过创建 $n \times n \times n$ 单元的 $m \times m \times m$ 砖块来改善 3D 数组中的 TLB 命中率。例如，$40 \times 20 \times 19$ 的体积可以分解为 $2 \times 2 \times 2$ 的 $5 \times 5 \times 5$ 单元的 $4 \times 2 \times 2$ 宏砖块。这对应于 $m = 2$ 和 $n = 5$。由于 $19$ 不能被 $mn = 10$ 分解，需要一级填充。$16$ 位数据集的经验有用大小为 $m = 5$，浮点数数据集的经验有用大小为 $m = 6$。

TLB：转换查找缓存，是虚拟内存系统的一部分。

任何 $(x,y,z)$ 三元组的数据阵列索引可以使用以下表达式计算：

$$\begin{aligned} \text { index }= & ((x \div n) \div m) n^{3} m^{3}\left(\left(N_{z} \div n\right) \div m\right)\left(\left(N_{y} \div n\right) \div m\right) \\ & +((y \div n) \div m) n^{3} m^{3}\left(\left(N_{z} \div n\right) \div m\right) \\ & +((z \div n) \div m) n^{3} m^{3} \\ & +((x \div n) \bmod m) n^{3} m^{2} \\ & +((y \div n) \bmod m) n^{3} m \\ & +((z \div n) \bmod m) n^{3} \\ & +\left(x \bmod \left(n^{2}\right)\right) n^{2} \\ & +(y \bmod n) n \\ & +(z \bmod n), \end{aligned}$$

其中 $N_x$、$N_y$ 和 $N_z$ 分别是数据集的大小。

注意，正如在更简单的二维单级情况下，此表达式可以写成

$$\text { index }=F_{x}(x)+F_{y}(y)+F_{z}(z),$$

其中

$$\begin{aligned} F_{x}(x)= & ((x \div n) \div m) n^{3} m^{3}\left(\left(N_{z} \div n\right) \div m\right)\left(\left(N_{y} \div n\right) \div m\right) \\ & +((x \div n) \bmod m) n^{3} m^{2} \\ & +(x \bmod n) n^{2} \\ F_{y}(y)= & ((y \div n) \div m) n^{3} m^{3}\left(\left(N_{z} \div n\right) \div m\right) \\ & +((y \div n) \bmod m) n^{3} m+ \\ & +(y \bmod n) n, \\ F_{z}(z)= & ((z \div n) \div m) n^{3} m^{3} \\ & +((z \div n) \bmod m) n^{3} \\ & +(z \bmod n) . \end{aligned}$$

常见问题

平铺真的会对性能产生那么大的影响吗？

在某些体绘制应用程序中，双层平铺策略可以提高 10 倍的性能。当数组不适合主内存时，它可以有效地防止一些应用程序如图像编辑中的抖动。

如何在有翼边结构中存储列表？

对于大多数应用程序，使用数组和索引引用是可行的。但是，如果要执行许多删除操作，则最好使用链接列表和指针。

注释

有翼边数据结构的讨论基于 Ching-Kuang Shene（2003）的课程笔记。有比有翼边更小的网格数据结构。使用这种结构的权衡在 Directed Edges—A 可伸缩表示法 for Triangle Meshes（Campagna, Kobbelt 和 Seidel，1998）中进行了讨论。平铺数组的讨论基于 Interactive Ray Tracing for Volume Visualization（Parker 等人，1999）。类似于三角形邻居结构的结构在 Charles Loop（Loop，2000）的技术报告中进行了讨论。拓扑学入门文本（Munkres，2000）中讨论了流形的问题。

练习

1. 将简单四面体分别存储为四个独立三角形和一个有翼边数据结构的内存差异是什么？
2. 为自行车设计一个场景图。
3. 对于 $n$ 维数组的单层平铺，需要多少个查找表？
4. 给定 $N$ 个三角形，能够添加到结果 BSP 树中的最小三角形数量是多少？最大数量是多少？