层次包围盒和均匀网格

虽然之前的简单的包围盒技术能够减少计算开销，但是对于整个光线跟踪算法来讲算法的效率还是没有显著地提高，究其原因主要在于，每一根被跟踪的光线都需要与场景的包围盒进行计算，算法的效率还是受到限制，其算法的复杂度为 O(N)，其中 N 为场景中物体的个数，即三角形数目。为了提高包围盒技术的效率，通过将包围盒组织成层次结构来改进简单的包诶和技术。其基本的思想为将整个场景按照场景的包围盒进行组织，根据物体在场景中的分布，相距很近的物体形成局部场景，然后这些局部场景又可组成更大的组，这样就形成了整个场景的树形层次结构。
如何分组时形成树形层次结构的关键步骤，理想的分组是建立在理想状况下物体间的相距距离，通过距离的远近对场景进行分组。层次结构的形状取决于场景中景物的空
间分布，通常越靠近树状结构的底层，包围盒则越小。建立层次结构常用的策略即“中分面”技术，该技术通过二叉剖分技术对场景进行从上到下的递归分组。

使用层次包围盒技术的光线跟踪算法，跟踪光线首先和场景包围盒求交，与场景包围盒相交后再和场景包围盒割分的包围盒求交，知道光线和最小包围盒相交后与最小包围盒内包含的物体面片求交，最终求得交点或是光线与物体无交。在建立场景的层次结构时最重要的步骤就是对整个场景中的物体进行合理的分组，一个理想的层次结构是基于物体之间距离的远近来进行分组的，层次结构的形状则依赖于场景中物体在空间的分布情况，一般来说，越靠近底层的结点，其包围盒会越小。在建立包围盒层次结构时常用的方法是——中分面（median-cut）技术，该技术使用二叉剖分技术对整个场景进行自上而下的递归划分。在每一结点处，首先将其所包含的景物按其 x 坐标轴的值进行大小排序，并将该结点的包围盒的 x 方向的中分面作为分割面对所含物体划分为两组而产生其两个子结点，再将两个子结点各自依次沿 y 轴和 z 轴两个方向依照 x 轴进行分组。将上述步骤递归进行，直至当前结点只包含一个物体为止。

可以看出，层次包围盒技术一方面利用包围盒技术避免了跟踪光线与不相交物体进行无效求交测试，同时又利用包围盒比较简单容易与光线进行求交测试，快速的确定于光线相交的物体。这与上小节中论述的内包围盒的改进算法有相似之处。本方法最终是只包含一个物体，光线只同一个物体进行求交测试，之前的大部分求交都是同包围盒的求交测试（比较简单）。

层次包围盒极大的降低了光线与景物求交测试的计算复杂度，但是计算量仍然很大，包围盒通常在空间是无序的，而光线跟踪需要找到离光线起始点最近的交点，而对于位
于光线后的物体求交计算式无用的。同时光线与物体的求交的效率通常与划分的层次结构有关，不同场景求交的效率可能大不相同。虽然包围体的形状可以是千奇百怪，可以
使球形也可以是立方体，但是要快速判断光线与包围盒的关系，那么轴对齐包围盒（AABB）是最简单的包围结构，所以通常都选用轴对齐包围盒作为结点类型 。

传统光线跟踪算法效率不高的主要原因在于光线与物体求交的盲目性、广泛性，跟踪光线必须和场景中的所有物体逐一进行求交测试，而且由于光线与物体求交测试的无序性，求交后还要对各交点进行远近排序以找到最近的交点。从提高光线跟踪算法效率的方面看，一方面一些物体和光线根本不相交还要作求交测试，另一方面在交点排序中排在后面的交点的求取是无用的。对每一条跟踪光线，我们所需要的仅仅是它在场景中最先相交的那个物体交点 [2] 。
考虑到场景中的各物体的空间位置是固定的，为了减少光线求交的盲目性，可以将场景空间进行剖分，剖分成很多位置固定的小方格。这些小方格在空间的位置是固定的，而且相互紧密连接着跟踪光线依次穿越小方格，光线只与它穿越的小方格中的物体面片求交，这就是空间剖分技术。这些小方格有序的被组织成了层次结构，其叶节点记录了它所包含的物体面片表，光线跟踪时只需要与它依次跨越的各网格空间内所含物体作求交测试；另一方面，由于网格空间排列的有序性，光线总会和它最先相遇的物体作求交测试，一旦有交则该光线的跟踪就结束，该交点即为最近交点，避免了对最近交点后面物体的求交测试计算及交点的排序。这也是空间剖分技术的优势之处。

1986 年，Fujimoto 等提出了一个基于空间均匀网格剖分技术的快速光线跟踪算法。该技术将场景空间剖分成一系列的大小均匀的三维网格，每个网格包含一系列的面片。

从而建立起一个称为 SEADS 的辅助数据结构（Spatially Enumerated Auxiliary Data structure）通过指针将包含在网格内的面片一一链接起来，在跟踪光线时，只需要计算跟光线经过空间的网格内的面片进行求交计算。如图 3.1 给出了包含 10 个面片二维场景的网格剖分及其 SEADS 结构。从图 3.1 中可以看出，光线 1 只需与面片 7 进行求交测试，而光线 2 则需要分别于面片 5、6、3、4 和 0 进行求交测试，最后得到的交点位于面片 4上。

在 SEADS 机构中，每一个剖分出的小立方体可用一个整数的三维空间坐标（i，j，k）来标示其位置，每个立方体中均含有其所包含的物体面片信息。光线只与其跟踪方向上的立方体相交，而且最先穿越的还是最近的，光线和它索穿越的立方体中的物体面片求交，一旦求得交点即为最近交点，这就是 3d-DDA 算法。

（1）若光线和垂直于 i、j 坐标轴的当前网格界面均相交，那么将距光线起点较近的交点所处界面相对应的坐标方向设为增量方向；若光线和这两个边界面无交，取主轴方向为增量方向；若和一个边界面相交，将和光线相交的边界面相对应的坐标方向设为增量方向。
（2）当前网格沿第(1)步确定的增量方向位移一格，即得到下一网格的坐标。
虽然均匀网格能够提高光线跟踪算法的效率，但是它仍然存在一定的弊端，它要求场景中的三角形面片分布比较均匀，这样在仿真时对场景要进行限制，如果场景中的面片分布不均匀，则均匀网格则不能达到很好的加速效果。特别是当场景中物体的三角形面片分布相当的稀疏时，对网格的划分会包含很多空白网格，这些网格不包含三角形面片，然而在光线在到达含有交点的网格之前，需要穿过很多这样的空白网格，这样会大大降低算法的效率。同时由于它在空间划分的特殊性，多个体素很可能包含相同三角形的多个引用，这就意味相同的光线与相同的三角形存在多次求交测试。

包围盒