某些数据结构似乎在图形应用程序中反复出现，也许是因为它们解决了表面、空间和场景结构等基本的潜在概念。本章讨论了几个基本的和不相关的数据结构类别，它们是最常见和最有用的：网格结构、空间数据结构、场景图结构和平铺多维数组。
对于网格，我们讨论了用于存储静态网格和将网格传输到图形 api 的基本存储方案。我们还讨论了翼边数据结构和相关的半边（half-edge）结构，这对于管理镶嵌变化的模型非常有用，例如在细分或模型简化中。 虽然这些方法可以推广到任意多边形网格，但我们在这里主要关注三角形网格的简单情况。
其次，给出了场景图的数据结构。这种数据结构的各种形式在图形应用程序中无处不在，因为它们在管理对象和转换方面非常有用。所有新的图形 api 都是为了支持场景图结构而设计的。
对于空间数据结构，我们讨论了在三维空间中组织模型的三种方法——边界体层次、层次空间细分和均匀空间细分——以及使用层次空间细分(BSP 树)去除隐藏表面。同样的方法也用于其他目的，包括几何剔除和碰撞检测。
最后，提出了平铺多维数组。这种结构最初是为了帮助需要从磁盘交换图形数据的应用程序中的分页性能而开发的。这种结构现在对机器上内存的局部性至关重要，不管数组是否适合主存。
大多数现实世界的模型都是由具有共享顶点的三角形的复合体组成的。这些通常被称为三角网格、三角形网格或三角形不规则网络 TIN，有效地处理它们对许多图形程序的性能至关重要。 重要的效率取决于应用程序。网格存储在磁盘和内存中，我们希望最小化所消耗的存储量。当网格通过网络或从 CPU 传输到图形系统时，它们会消耗带宽，这通常比存储更宝贵。 在对网格执行操作的应用程序中，除了简单地存储和绘制它们(如细分、网格编辑、网格压缩或其他操作)之外，对邻接信息的高效访问至关重要。
三角形网格通常用于表示表面，因此网格不仅仅是不相关三角形的集合，而是通过共享顶点和边线相互连接以形成单个连续表面的三角形网络。 一个网格可以比相同数量的不相关三角形集合更有效地处理。
三角形网格所需的最小信息是一组三角形(顶点的三元组)及其顶点的位置(在 3D 空间中)。但是，许多程序需要在顶点、边线或面上存储额外数据的能力，以支持纹理映射、阴影、动画和其他操作。 顶点数据是最常见的：每个顶点可以有材质参数、纹理坐标和辐照度——任何参数的值在表面上都是变化的。然后将这些参数在每个三角形上进行线性插值，以在整个网格表面上定义一个连续函数。 然而，能够按边或按面存储数据有时也很重要。
网格是类表面的，这种想法可以形式化为网格拓扑的约束——三角形连接在一起的方式，而不考虑顶点的位置。 许多算法只能在具有可预测连接的网格上工作，或者更容易实现。 对网格拓扑最简单和最严格的要求是曲面必须是流形。流形网格是“不透水的”——它没有缝隙，将表面内部的空间与外部的空间分开。它看起来也像网格上的一个表面。
流形这个术语来自拓扑学的数学领域：粗略地说，流形(特别是二维流形，或 2-流形)是一种曲面，其中任何顶点周围的一个小邻域都可以被平滑成一些平坦的曲面。
这个概念可以用反例来最清楚地解释：如果网格上的一条边有三个相连的三角形，那么边上点的邻域不同于其中一个三角形内部点的邻域，因为它有一个额外的‘鳍’伸出。
如果边上恰好有两个三角形，边上的点就有与内部点一样的邻域，只是中间有一个折痕。
类似地，如果共享一个顶点的三角形的配置类似于图 12.2 中左侧的三角形，则该邻域就像两块粘在顶点的曲面，如果不将其分开，则无法展平。
而在右侧显示较简单邻域的顶点就可以了。
许多算法都假设网格是流形的，如果你得到的是不规则网格作为输入，验证这一属性以防止崩溃或无限循环总是一个好主意。这种验证归结为检查所有边都是流形的，并通过验证以下条件来检查所有顶点都是流形的：
- 所有的边线都仅仅被两个三角面共享
- 所有的顶点，在它周围的三角形中，有且仅有一个完整的 loop。
流形网格很方便，但有时，有必要允许网格有边或边界。这样的网格不是流形，边界上的一点有一个在一侧被截断的邻域。它们不一定是水密的。 然而，我们可以将流形网格的要求放宽到对有边界的流形的要求，而不会对大多数网格处理算法造成问题：
- 每条边线被一个或两个三角形利用
- 每个顶点连接到一组边线相接的三角形集合
最后，在许多应用中，能够区分一个表面的'前'或'外部'与'后'或'内部'是很重要的——这就是所谓的表面的方向。
对于一个单个三角形，我们根据顶点的排列顺序来定义方向：”向前“是三角形的三个顶点按逆时针顺序的面。
当且仅当一个网格中所有的三角面遵循相同的内外判断时，称这个网格是一致定向的——即任意两个邻接的三角面遵循相同的判断标准。
在一致定向的一对三角面中，两个被共享的顶点以相反的顺序出现在两个三角面的顶点序列中。
一致定向的方向是非常重要的——在一些系统中使用顺时针作为正面。
任何有非流形边的网格都不能一致地定向。但是一个拥有边界的曲面也有可能是一个有效的流形，但是却没有一致的方法来确定方向——它们是不可定向曲面。一个例子是莫比乌斯带。
class Triangle{
vector3 vertexPosition[3];
}这种方法存储顶点 b 三次，其他顶点各存储两次，总共存储九个点，或者我们只存储 4 个共享顶点：
class Triangle{
Vertex v[3];
}
class Vertex{
vertor3 position;
}
注意到，v 数组中的条目是对 Vertex 对象的引用。顶点不包含在三角形中。
顶点和三角形通常存储在数组中。通过存储数组索引来处理三角形到顶点的引用：
class IndexedMesh{
int tInd[nt][3];
vertor3 verts[nv];
}第 i 个三角形的第 k 个顶点可以在 tInd[i][k]中找到，顶点的位置被存储在相应的数组中。这种方式用来存储共享顶点的三角面，称为索引三角形网格。
分离三角形或共享顶点都可以很好地工作。共享顶点是否有空间优势？如果我们的网格有 nv 个顶点和 nt 个三角形，假设浮点数、指针以及整数要求相同的存储空间，那么存储的要求是：
- 三角面：9nt 单位的存储
- 索引三角形：3nv+3nt
所以相对存储需求取决于 nt 和 nv 的比值。
作为一个经验法则，在大型网格上每个顶点连接到大约六个三角形（尽管极端情况下可以有任意数量的连接）。由于三角形连接到三个顶点，这意味着三角面的适量通常是顶点的两倍。通过这个替换，我们可以得出结论，三角形结构的存储需求为 18nv，索引网格的存储需求则为 9nv。使用共享顶点将存储需求减少了大约 2 倍。这在实践中似乎也是如此。
索引网格，因为它们实现了简单性和紧凑性的良好平衡。它们也通常用于在网络上以及在应用程序和图形流水线之间传输网格。
在需要更紧凑结构的应用程序中，三角形顶点索引(在索引网格中占据三分之二的空间，仅在顶点处有位置)可以使用三角条纹与扇叶来获得更高的效率。
三角形条带是一个类似的概念，但它对更大范围的网格很有用。在线性条带中交替添加顶点作为”顶“和”底“。图中的三角形条带可以由序列[01234567]来特定，然后每 3 个相邻的子序列创建一个三角面。为了表面的一致定向性，三角形需要交替逆转顺序。用一个队列实现，每当一个新顶点进入时，队首的顶点退出，并反转队列中顶点的顺序。
在条纹三角形和扇形三角形中，n +2 个顶点足以描述 n 个三角形——一个标准的索引三角形需要 3n 的存储量，三角形条带将节省大约三倍。
看起来三角形条带只有在条带很长的情况下才有用，但即使是相对较短的条带也已经获得了大部分的好处。
事实上，随着条带的增长，收益会迅速递减，因此即使是一个非结构化的网格也值得使用一些贪婪的算法将它们聚集成短条带。
索引网格、条纹三角形和扇形都是静态网格的良好的紧凑表示。然而，它们不允许网格被修改。为了有效地编辑网格，更复杂的数据结构来回答以下问题：
- 给定一个三角面，求它的 3 个邻接三角形？
- 给定一个边线，求哪两个三角形共享他？
- 给定一个顶点，哪些面共享他？
- 给定一个顶点，哪些边线共享他？
有许多适合三角形网格、多边形网格以及由孔洞的多边形网格的数据结构。在许多应用中，网格会非常大，因此高效的表示会是关键。
最直接的实现是拥有三种类型，Vertex, Edge 和 Triangle，并直接存储所有关系：
这让我们可以直接查找上述连接性问题的答案，但是由于这些信息都是相互关联的，因此它存储的信息比实际需要的要多。此外，在顶点中存储连接性会产生可变长度的数据结构(因为顶点可以有任意数量的邻居)，这通常会降低实现效率。
与其承诺显式地存储所有这些关系，不如定义一个类接口来回答这些问题，在这个接口后面隐藏着更有效的数据结构。
事实证明，我们只能存储部分连接信息，并在需要时有效地恢复其他信息。
Edge 和 Triangle 类中的固定大小的数组表明，将连接信息存储在那里会更有效。 实际上，对于多边形网格来说，多边形具有任意数量的边和顶点，只有边具有固定大小的连接信息，这导致许多传统的网格数据结构都是基于边的。但是对于只有三角形的网格，将连通性存储在(数量较少的)面是有吸引力的。
一个好的网格数据结构应该是相当紧凑的，并且允许对所有邻接查询进行有效的回答。高效意味着恒定的时间：寻找邻居的时间不应该取决于网格的大小。 我们将看到三种网格数据结构，一种基于三角形，两种基于边。
我们可以创建一个基于三角形的紧凑的网格数据结构，通过声明基本的共享顶点网格，并用指针指向它邻接的 3 个三角面。每个顶点还有一个按一定规则指向邻接三角形的指针。
在数组 Triangle. nbr 中，第 k 个条目指向共享顶点 k 和 k +1 的相邻三角形。我们称此结构为 三角形-邻居 结构。从标准索引网格数组开始，可以添加两个额外的数组来实现：一个存储邻接三角形的索引，另一个存储每个顶点的单个邻接三角形：
显然，一个三角形的邻接三角形和顶点可以直接在数据结构中找到。但是只要我们小心的使用这个数据结构，我们也可以在常数时间内回答关于顶点的连通性查询。
其思想是从一个三角形移动到另一个三角形，只访问与相关顶点相邻的三角形。如果三角形 t 的顶点 v 是它的第 k 个顶点，那么三角形 t.nbr[k]是沿顺时针方向围绕 v 的下一个三角形。下面的算法用来遍历与给定顶点相邻的所有三角形:
这个操作在恒定的时间内找到每个后续三角形——即使需要在每个三角形的顶点列表中查找中心顶点的位置，但顶点列表的大小是恒定的，因此搜索所需的时间是恒定的。然而，这种搜索很尴尬，需要额外的分支。
一个小的改进可以避免这些搜索。
问题是，一旦我们跟随一个指针从一个三角形到下一个三角形，我们不知道我们从哪个方向来:我们必须搜索三角形的顶点，找到连接回前一个三角形的顶点。为了解决这个问题，我们可以不存储指向相邻三角形的指针，而是通过存储指针的索引来存储指向这些三角形的特定边的指针:
实作上，Edge 借用三角形索引 t 中的两位（2bit）存储空间来存储边缘索引 i，因此总存储需求保持不变。
在这个结构中，三角形的邻接数组告诉我们邻接三角形的哪一条边与自己共享。有了这些额外的信息，我们总是知道在哪里找到原来的三角形，这就引出了数据结构的一个恒等式：对于任何三角形 t 的第 j 条边：
知道我们从哪条边进来，让我们立即知道要离开哪条边，以便继续遍历一个顶点，从而产生一个简化的算法:
三角形邻接结构非常紧凑。对于只有顶点位置的网格，我们每个顶点存储四个数字(三个坐标和一条边)，每个面存储六个数字(三个顶点索引和三条边)，总共存储 4nv + 6nt≈16nv，而基本索引网格的存储为 9nv。
一种广泛使用的网格数据结构是翼边数据结构，它将连接信息存储在边缘而不是面。这种数据结构使边成为数据结构的一等公民。
在翼边网格中，每个边存储指向它连接的两个顶点(头和尾顶点)的指针，它所属的两个面(左和右面)，最重要的是，它的左和右面逆时针遍历的下一个和前一个边(图 12.16)。每个顶点和面还存储一个指针，指向连接到它的任意边：
翼边数据结构支持对面或顶点的边线进行恒时访问，并且可以从这些边缘找到相邻的顶点或面：
这些相同的算法和数据结构同样适用于多边形网格(不局限于三角形)；这是基于边线的结构的一个重要优点。
与任何数据结构一样，翼边数据结构需要进行各种时间/空间权衡。 例如，我们可以消除”prev“引用。这使得沿面顺时针遍历或沿顶点逆时针遍历变得更加困难，但是当我们需要知道前面的边时，我们总是可以沿着一个圆圈中的后继边，直到我们回到原始边。这样可以节省空间，但会使某些操作变慢。
翼边结构相当优雅，但它有一个笨拙的地方——在移动到下一个边线之前，需要不断检查边线的方向。这种检查直接类比为我们在三角形邻居结构的基本版本中看到的搜索：寻找我们是从头部还是从尾部进入当前边线。这个解决方案几乎是不可区分的：我们不是为每条边存储数据，而是为每条半边存储数据。两个三角形共用一条边，每个三角形都有一条半边，这两条半边的方向相反，每一条都与自己的三角形方向一致。
通常存储在一条边中的数据被分成两条半边。每个半边都指向其边的面及其头部的顶点，并且每个半边都为它的面存储一个指向边线的边指针。它还指向边线的另一个半边，从那里可以找到另一半信息。
像翼边一样，半边可以包含指向其表面周围的前半边和下半边的指针，也可以只指向下半边。我们将展示使用单个指针的示例。
遍历半边结构就像遍历翼边结构一样，除了我们不再需要检查方向，我们遵循 pair 指针访问对面面的边缘。
这里的顶点遍历是顺时针的，这是必要的，因为省略了”prev“的指针。
因为半边通常成对分配，（至少在没有边界的网格中）。许多实现可以去掉指针”pair“。
例如，基于数组索引的实现。数组可以这样排列，使得偶数边 i 总是与边线 i+1 配对，奇数边 j 总是与边线 j-1 配对。
除了本章中介绍的简单遍历算法外，所有这三种网格拓扑结构都可以支持各种网格操作，如分割或折叠顶点、交换边、添加或删除三角形。
三角形网格管理一组三角形，这些三角形构成场景中的一个对象。但是图形应用程序中的另一个普遍问题是将对象安排在所需的位置上。这是通过转换来完成的，但是复杂的场景可以包含大量的转换，良好的组织它们才能使场景更容易操作。大多数场景都有一个层次的组织，并且这些变换可以根据这个层次结构，使用”场景图“来良好的管理。
考虑这样一个铰接摆，思考如何去绘制它？
下面的摆会比较复杂，但我们可以利用它在局部坐标系中的 b 点连接到上部摆的底部。首先，我们转动下部摆，使其与初始位置成一个角度。然后，我们移动它，使它的顶部铰链在 b 点。现在它在上部坐标系中的适当位置，然后它可以沿着该坐标系一起变换。
因此，我们不仅看到下摆位于自己的局部坐标系中，而且看到坐标系本身也随着上摆的坐标系一起移动。我们可以将钟摆编码到数据结构中，使这些坐标系问题的管理变得更容易。应用于对象的适当矩阵就是树形结构 chain 中所有矩阵的乘积。
在光栅化的情况下，使用许多 API 支持的矩阵栈数据结构可以实现一个有效的实现。矩阵栈是使用 push 和 pop 操作来实现的，这些操作从矩阵乘积的右侧添加和删除矩阵。
光线跟踪的一个优雅的特性是，它允许非常自然的应用变换，而不改变几何的表示。实例化的想法是在对象被显示之前通过变换矩阵变换对象上的所有点。使实体成为实例的关键是我们存储了圆和复合变换矩阵，因此，椭圆的显式构造留作渲染时的未来操作。
光线跟踪中实例化的优点是我们可以选择要在其中进行求交的空间。如果基本对象由一组点组成，其中一个点被变换，则变换对象由由矩阵 M 变换的那组点组成，点被变换为 Mp。如果我们有一条射线 a+Tb，我们想要与变换对象相交，我们可以使用逆变换的射线与未变换的物体求交。在未变换空间中进行计算有两个潜在的优点：
- 未变换对象可以具有更简单的交集算法，圆形求交要比椭圆简单得多。
- 许多变换的对象可以共享同一个未变换的对象，从而减少了存储。
使用这个想法，我们可以改进光线追踪得求交程序：
这个函数的一个优雅之处是参数 rec. t 不需要改变，因为它在两个空间中都是一样的。另外，我们不需要计算或存储矩阵 M（只用到了 M 逆）。
这就提出了一个非常重要的问题，即光线方向 b 不能被限制为单位长度矢量，或者上面的结构都不起作用（？？？）。出于这个原因，不把光线方向限制在单位长度是很有用的。
在许多图形应用中，快速定位特定空间区域中的几何对象的能力很重要。在交互式程序的 3D 场景中环游时，摄像机需要知道在它的位置可见的任何几何体。游戏和物理模拟中需要检测物体何时、何地发生了碰撞。所有这些需求都可以由各种空间数据结构来支持，它们旨在组织空间中的对象，以便它们能够高效地进行查找。
在这一节中，我们将讨论三种一般类型的空间数据结构的例子。
将物体组织成层级的结构是物体划分方案：对象被分成不连续的组，但组在空间中可能会重叠。
将空间划分为成不连续区域的是空间划分方案：空间被分成多个部分，但是一个物体可能与多个子空间相交。空间划分方案可以是规则的，其中空间被划分为均匀形状的碎片，也可以是不规则的，其中空间被自适应地划分为不规则小碎片，小碎片中有更多小型的物体。
在讨论这些结构时，我们将使用光线追踪作为主要背景，尽管它们也可以用于视图剔除或碰撞检测。
在第 4 章中，所有的对象在检查交点时都是循环的。对于 N 个物体，这是一个 O(N)线性搜索，因此对于大场景来说速度很慢。
像大多数搜索问题一样，如果我们可以创建一个有序的数据结构作为预处理，则可以使用“分治”技术在亚线性时间内计算光线与物体的交集。
有很多方法可以做到这一点，本节主要讨论 3 种：
- 边界体积层级
- 均匀空间细分
- 二元空间划分
在大多数相交加速方案中，一个关键操作是计算射线与边界框的相交。这与传统的相交测试不同，因为我们不需要知道光线击中盒子的位置，我们只需要知道它是否命中盒子。
为了构建射线盒相交的算法，我们首先考虑一条方向矢量有正 x 和正 y 分量的二维射线。稍后我们可以把它推广到任意的 3D 射线。二维边界框由两条水平线和两条垂直线定义：
我们可以计算出射线与 4 条直线的交点，例如$t_{xmin}=(x_{min-x_e} / x_d)$
如果上图中的交区间$[t_{xmin},t_{xmax}],and,[t_{ymin},t_{ymax}]$存在（有重叠部分），则说明有交点，程序如下：
如果射线斜率分量 xd 或 yd 为负数，那么射线会在到达 xmin 之前到达 xmax。程序会变成这样：
另一个问题是：水平和垂直射线的 yd 和 xd 值分别为零，这将导致除数为 0 异常。然而，在直接解决这个问题之前，让我们检查 IEEE 浮点计算是否为我们优雅地处理了这些情况。
考虑 xd=0 并且 yd>0，然后我们计算：
有三种我们感兴趣的情况：
针对第一种情况：txmin 和 txmax 都是正无穷，不可能有交区间。
第二种情况：txmin 负无穷而 txmax 正无穷，必定会相交
第三种：txmin 和 txmax 都是负无穷，不可能有交区间。
这些情形发生时，我们的代码都正常工作，所以我们不需要对它们进行特殊检查。
通常情况下，IEEE 浮点约定是我们的盟友。
然而，这种方法仍然存在一个问题，考虑以下代码：
这段代码当 xd=-0 时，无法工作。应该改为判断 1/xd：
-0 在 IEEE 标准中视为负的无穷小 在判断（xd>=0）时为 true，然后走上分支，实际上应该走下分支。 通过 1/xd，变成负的无穷大，则可以正常地在走下分支。
层次化边界框的基本思想可以通过在所有对象周围放置一个轴对齐的 3D 边界框。
击中边界框的光线实际上比蛮力搜索更昂贵，因为测试与框的交集不是免费的。然而未击中框的光线比蛮力搜索便宜。
这样的框可以通过将对象集划分在一个框中并在每个小框周围放置一个大框来实现层次化。
请注意，并不是框中包含的所有球体都保证由相应的树节点指向
层次结构的数据结构可能是一棵树，其中大的边界框位于根，两个较小的边界框分别作为左、右子树，这些子树依次指向三个三角形的列表。求交程序是：
注意到，在两个子树之间没有几何上的顺序，射线可能同时击中两个子树。事实上，两个子树也可能重叠。
关键点是，一个盒子保证包含层次结构中它下面的所有对象（child）。但它们不能保证包含盒子空间内的所有对象（和盒子内的物体可能不是它的 child） 这使得几何搜索比传统的严格有序一维数据的二分搜索更复杂。
如果我们限制树是二元的，并要求树中的每个节点都有边界盒。那么这个遍历代码可以自然地使用。
bvh-node 类的类型应该是 surface，所以它应该实现 surface::hit。它包含的数据应该很简单：
然后可以以面向对象的方式递归调用遍历代码：
这个算法。。。就算子树区域没有相交，射线与两个子树都相交的话，两个子树都要查啊，为什么返回最近的击中目标。。。
注意，因为左和右都指向曲面而不是 bvh 节点，我们可以让虚函数来区分内部节点和叶节点；将调用相应的 hit 函数（父级指针调用子类的函数）。 注意，如果树构建得正确，我们可以消除左指针为 NULL 的检查。如果我们想要消除对右指针是否为 NULL 的检查，我们可以用一个多余的左指针替换为 NULL 的右指针。这将左指针检查两次，但将消除整个树的检查。
有许多方法可以为边界卷层次结构构建树。使树成为二叉树，大致平衡，并使兄弟子树的盒子不重叠太多。
实现这一目标的一种启发式方法是，在将曲面分成两个子列表之前，沿着一个轴对它们进行排序。如果坐标轴是由 x = 0, y = 1, z = 2 的整数定义，我们有
(AXIS +1) mod 3 这个是啥？？？
通过每次精心选择轴向 AXIS，可以提高树的质量。 一种方法是选择使两个子树的边界框的体积总和最小的轴。这种变化与沿轴旋转相比，对于由各向同性分布的小物体组成的场景几乎没有什么不同，但它可能对不太正常的场景有很大帮助。 通过只执行一个划分而不是完整排序，还可以使此代码更高效（快排一趟）。
另一种可能更好的构建树的方法是让子树包含相同数量的空间，而不是相同数量的对象。为此，我们基于空间对列表进行划分：
尽管这会导致树的不平衡，但它允许轻松遍历“空”空间（？？？），并且构建成本更低，因为分区比排序更便宜。
另一个减少交叉测试的策略是划分空间。这从根本上不同于用分层边界卷划分对象：
- 在分层边界体积中，每个对象属于两个兄弟节点中的一个，而空间中的一个点可能同时位于两个兄弟节点的体积之中。
- 在空间细分中，空间中的每个点只属于一个节点，而对象可能属于多个节点。
在均匀的空间细分中，场景被划分为轴线对齐的盒子。这些盒子的大小都是一样的，尽管它们不一定是立方体。射线遍历这些框。当一个对象被击中时，遍历结束。
网格本身应该是 surface 的子类，并且应该作为指向 surface 的 3D 数组来实现。对于空单元格，这些指针指向 NULL。对于具有一个对象的单元格，指针指向该对象。对于具有多个对象的单元格，指针可以指向列表、另一个网格或另一个数据结构，例如边界体积层次结构。
这种遍历是以增量方式完成的。规律性来自于射线击中每一组平行平面的方式。
首先考虑 2D 情况，其中光线方向具有正的 x 和 y 分量，并且从网格外开始。假设网格由点(xmin, ymin)和(xmax, ymax)包围。网格有 nx × ny 个单元格。
我们的第一个任务是找到第一个被射线 e + td 击中的单元格的索引(i, j)。然后，我们需要以适当的顺序遍历单元格。算法的核心是找到初始的 cell，然后决定是否要增量 i 或 j。
注意到我们检查与在 cell 中物体的相交的情况，我们必须要把 t 限制在 cell 的范围内。
大多数算法的实现使用指向 surface 的 3D 指针数组，为了在遍历中提升算法的局部性性能。
我们也可以在分层数据结构中划分空间，例如二进制空间划分树（BSP 树）。但是最常见的是轴对齐（而非多边形对齐）。
该结构中的一个节点包含一个切割平面和左右两个指向子树的指针。每个子树包含切割平面一侧的所有几何体。那些穿过切割平面的几何体会被保存在两个子树中。那么节点类为：
我们稍后将其推广到其他切割平面上。然后，代码可以以面向对象的方式递归调用。
这是非常干净的代码。然而，为了启动它，我们需要访问一些包含边界框的根对象，这样我们就可以启动遍历。
我们必须解决的一个问题是，切割平面可以沿着任何轴。我们可以向 bsp-node 类添加一个整数索引轴。如果我们允许对点进行索引操作符，这将导致对上面代码进行一些简单的修改，例如：
这将导致一些额外的数组索引，但不会生成更多的判断分支。
虽然处理单个 bsp 节点比处理 bvh 节点要快，但是一个表面可能存在于多个子树中，意味着有更多的节点，并且可能会有更高的内存使用。 树建得有多好决定了哪个方法更快。构建树与构建 BVH 树类似。我们可以在循环中选定一个轴来划分，我们也可以每次都把几何体划分为两边，或者我们可以尝试更复杂的分裂方式。
BVH 边界体积层级：多叉树 BSP 二元空间划分：二叉树
另一个可以使用空间数据结构的几何问题是确定具有变化视点的场景中物体的可见性顺序问题。
如果我们要从不同的角度制作由平面多边形组成的固定场景的许多图像，就像游戏等应用程序经常出现的情况一样，我们可以使用与前一节中讨论的光线相交方法密切相关的二进制空间划分方案。
不同之处在于，对于可见性排序，我们使用非轴向对齐的的划分平面，这样可以使划分平面与多边形方向一致。 这导致了一种被称为 BSP 树算法的优雅算法，该算法从前到后对曲面进行排序。BSP 树的关键是，它使用预处理来创建对任何视点都有用的数据结构。因此，当视点改变时，使用相同的数据结构而不改变。
BSP 树算法是画家算法的一个例子。画家的算法从后到前绘制每个对象，每个新多边形都可能覆盖之前的多边形。它可以实现如下:
第一步(排序)的问题在于，多个对象的相对顺序并不总是定义得很好，即使每一对对象的顺序都定义得很好。图 12.36 说明了这个问题，其中三个三角形形成一个循环。下图的多边形无法确定出一个顺序。
BSP 树算法适用于任何由多边形组成的场景，其中没有多边形穿过任何由其他多边形定义的平面。这项限制被预处理过程放宽了。在接下来的讨论中，我们假设三角形是唯一的图元，但这些想法可以扩展到任意多边形。
BSP 树的基本思想可以用两个三角形 T1 和 t2 来表示。t1 三角形上平面的隐式方程：f1(p) = 0。
我们希望利用的隐式平面的关键性质——是对于平面一侧的所有点 p+， f1(p+) > 0；对于平面另一侧的所有点 p−，f1(p−)< 0。
利用这个性质，我们可以求出 T2 在平面的哪一边。
同样，这假设 T2 的三个顶点都在平面的同一边。为了讨论，假设 T2 在平面的 f1(p) < 0 一侧。然后，我们可以在任意视点 e 上按正确的顺序画 T1 和 T2:
算法起作用的原因是，如果 T2 和 e 在包含 T1 的平面的同一侧，T2 不可能完全或部分被 Tt 阻挡，首先绘制 T1 是安全的。
如果 e 和 Tb 位于含有 T 的平面的相对两侧，则 T2 不能完全或部分阻挡 Ti，相反的绘制顺序是安全的。
这种观察可以推广到许多对象，前提是它们都没有跨越 T1 定义的平面。
如果我们使用一个以 Ti 为根的二元树数据结构，树的负分支包含所有顶点为 f（p）<0 的三角形，树的正分支包含所有顶点为 f 的三角形 f(p)>0。我们可以按照适当的顺序绘制：
这个代码的优点是它可以对任何视点工作，因为树可以被预先计算。注意，子树本身就是一个树。其中根三角形将其他三角形划分为相对于其平面的两组。算法可以通过更高一级的终止递归调用而稍微更有效率，但是代码仍然是简单的。
唯一一个阻止代码运行的问题是：无法保证一个三角面可以被唯一的划分到平面的一侧。解决的办法是：沿着划分面切割三角形，将他切成更小的三角面。
如果数据集中没有三角形彼此的平面相交，那么所有三角形都在所有其他三角形的一侧，则可以使用以下算法构建一个可以使用上面代码遍历的 BSP 树：
我们唯一需要修正的是三角形与分割面相交的情况，如图 12.39 所示。为了简单起见，假设三角形在平面的一边有顶点 a 和 b，而顶点 c 在另一边。在这种情况下，我们可以找到交点 A 和 B，并将三角形切成三个新的三角形：
这种顶点顺序很重要，因此法线的方向与原始三角形的方向保持不变。如果我们假设 f(C)<o，下面的代码可以将这三个三角形添加到树中，假设正子树和负子树不为空：
当顶点非常靠近分割平面时，会出现困扰的精度问题。例如，如果我们在分割平面的一侧有两个顶点，而另一个顶点距离另一侧只有极短的距离，我们将创建一个新的与旧三角形几乎相同的三角形。
最好将其检测为特殊情况，而不是分成三个新三角形。
人们可能会认为这种情况是很少见的，但由于许多模型都有细分平面和具有共享顶点的三角形，因此它经常发生，因此必须小心处理。完成此操作的一些简单操作是
常数 e 是用户选择的一个小的正实数。
上面的技术是一个罕见的实例，其中测试浮点相等性非常有用并且有效，因为零值是设置的而不是计算的。将相等值与计算出的浮点值进行比较几乎是不可取的，但我们不这样做。
“将三角形切成三个三角形”的细节很简单，但很乏味。我们应该利用 BSP 树构建过程顺手处理他们，在这里最高效率不是关键。相反，我们应该尝试使用简洁的代码。
一个很好的技巧是，通过确保 c 在平面的一边，而其他两个顶点在另一边，将许多情况合并为一个。这很容易通过交换来实现：
这段代码利用了这样一个事实：即如果 a 和 b 的符号相同，它们的乘积是正的——因此，第一个 if 语句。如果交换顶点，我们必须进行两次交换以保持顶点的逆时针顺序。
请注意，一个顶点可能恰好位于平面上，在这种情况下，上面的代码能正常工作，但其中一个生成的三角形的面积将为零。这可以通过忽略这种可能性来处理，因为栅格化代码必须处理屏幕空间中的零面积三角形。您还可以添加一个不向树中添加零面积三角形的校验。 最后，你还可以设置一个特例，对于其中一个点为 0 以至于算法将其切割成两个三角形的情况。
为了计算 A 和 B，线段与隐式方程的求交算法式必须的：
与树遍历相比，树创建的效率不太受关注，因为它只是一个预处理。BSP 树的遍历所花费的时间与树中节点的数量成正比。树的平衡程度并不重要。 每个三角形都会有一个节点。包括由于分裂而创建的三角形。这个数字取决于三角形添加到树中的顺序。 例如，在图 12.41 中，如果 T1 是根，则在 树。但是如果 T2 是根。会有更多的节点。因为 T 会被分裂。
很难找到添加到树中的三角形的最佳顺序。对于 M 个三角形，有 N！种顺序。因此，尝试所有排序通常是不可行的。或者从随机排列集合中尝试排序。并且可以为最终树保留最好的排序。
上述分割算法将一个三角形分割成三个三角形。 将三角形分割成三角形和凸四边形可能会更有效。如果所有输入模型都只有三角形，这可能不值得，但很容易支持容纳任意多边形的实现。
有效利用内存层次结构是设计现代体系结构算法的一项关键任务。确保多维数组的数据排列良好是通过平铺（砖块化 bricking）来完成的。传统的 2 维数组以 1 维始祖的形式存储，使用索引的机制来读取。
图 12.42 显示了内存布局的一个示例。这种布局的一个问题是，虽然同一行中的两个相邻数组元素在内存中彼此相邻，但同一列中的两个相邻元素将被 Nx 个元素分隔开。 这可能会导致大 Nx 的内存局部性较差。
对此的标准解决方案是使用 平铺 使行和列的内存局部性更加平等。
关键问题是制作平铺的尺寸。 实际上，它们应该与机器上的内存单元大小相似。 例如，如果我们在具有 128 字节缓存块的机器上使用 16 位（2 字节）数据值，则 8X 8 个数据恰好适合缓存块。 然而，使用 32 位浮点数（适合 32 个元素到一个缓存行），5 X 5 块有点太小，6 X6 块有点太大。 因为还有更粗尺寸的内存单元，例如页面、分层结构 具有类似逻辑的平铺可能很有用。
我们假设$N_x\time N_y$大小的数组可以分解为$n\times n$大小的平铺块，那么块大小是：
这里我们假设它们整除。当他们无法整除的时候，数组需要被填充。
取索引这样一个数组，数据所在块的第一个索引值是（整数除法，取商的整数部分）：
在块中使用普通的 2D 索引：
完整公式：
该表达式包含许多整数乘法、除法和取模操作，这些操作在某些处理器上开销很大。
当 n 是 2 的幂时，这些运算可以转换为位移位和位逻辑运算。
然而，如上所述，理想的大小并不总是 2 的幂。有些乘法运算可以转换为移位/加法运算，但除法和取模运算更成问题。
可以增量地计算索引，但这将需要跟踪计数器，并且需要进行大量比较和较差的分支预测性能。
然而，有一个简单的解决方案：
我们将 Fx 和 Fy 制成表格，并使用 x 和 y 找到数据数组的索引。这些表将分别由 Nx 和 Ny 元素组成。表的总大小将适合处理器的主数据缓存，即使对于非常大的数据集也是如此。
TLB 的有效利用率也成为影响算法性能的关键因素。同样的技术可以通过创建包含 nnn 大小 cell 的 mmm 个砖块来提高 3D 阵列中的 TLB 命中率。经验上有用的大小对于 16 位数据集是 m = 5，对于浮点数据集是 m = 6。
TLB：暂存缓冲区，是虚拟内存系统的一部分。
可以使用表达式为任何(x, y, z)三元组计算数据数组的结果索引：
其中 Nx、Ny、Nz 是数据集的大小。
和单级 2D 平铺一样，表达式也可以写成：
