实现和比较加速结构。

3.1均匀格栅。

均匀网格是GPU上实现的第一个加速结构。Purcell给出了许多选择均匀网格作为加速结构的原因，但Purcell并没有详细解释为什么均匀网格比其他加速结构更容易实现硬件。在讨论均匀网格的一些主要特性时，我们更清楚地知道为什么均匀网格成为一个好的GPU速度结构。

首先，只有使用简单的算术操作，每个元素的常规时间才能定位和访问。这消除了对树木的常规需求和重复的纹理搜索工作，而纹理搜索相当耗时。

其次，体素的遍历是通过递增算术操作完成的。这消除了对堆栈的需求，使我们有可能从光线的起点和距离增加的顺序访问体素。

其次，由于对体素的访问是沿着光线通过距离增加的，一旦在被访问的体素中发现交叉点，就可以停止光对体素的全过程，从而提高全过程的速度。

最后，用于遍历的代码非常适合向量编写，而向量形式的编码风格非常适合GPU指令集。

然而，均匀格栅的缺点是它是空间细分结构的一种特殊情况，多个元素可能包含同一三角形的多个参考。由于不能使用mailbox技术，这意味着需要不止一次测试同一光线和三角形之间的交叉。

3.2KD-treee。

最近，Havran和其他人比较了基于CPU的光跟踪算法的加速结构。结论是，对于许多不同类型的测试场景，平均而言，KD-tree是最快的。因此，有必要检查基于KD-tree的GPU光跟踪算法是否会有类似的结论。

就像均匀网格一样，KD-tree也是一种空间细分结构。与均匀网格不同，KD-tree使用二叉树将场景表示为层次结构。

在二叉树中，我们将内部节点与叶片节点区分开来。叶节点用于表示保存在体素中的体素和三角形引用。一个内部节点用于表示空间区域的某个部分。因此，内部节点包括一个分裂面的两个子树的引用，而叶节点只包含一个三角形列表。

KD-tree的创建过程是从上到下的。根据评估函数，场景通过放置分离平面将递归分为两个元素。我们可以通过递归的方式遍历KD-tree，但由于GPU没有堆栈结构，递归策略无法应用。相反，我们可以记住我们沿着光线向上或向下穿越树木的距离。该策略消除了堆栈的限制，使用CPU完成KD-tree结构的全过程成为可能。

当使用GPU对KD-tree进行遍历时，KD-tree被表示为像均匀格栅一样的纹理集合。这意味着有一种保存树数据的纹理，一种保存三角形列表的纹理，以及保存实际三角形数据的纹理。GPU的遍历首先调用初始核，然后根据需要多次调用合并后的遍历并要求交付核。

3.3包围层(BVH)

给出一些随机光，通过计算包围层的平均成本，可以测量包围层的质量。到目前为止，还没有构建最佳的包围层算法，也就是说，如何准确测量包围层的平均包围时间并不明显。

Goldsmith和Salmon提出了一个评价函数，通常称为表面积启发函数。他们通过父节点和儿童节点的表面积之比来形式化这种关系，如下:

在这里，hit(n)是光线击中节点n的情况，Sn是节点n的表面积，c和p分别表示父子节点。

这个评价函数给出了成本估计，当用随机光线支付同级结构时。由于没有最好的方法来有效地构建最好的BVH，因此提出了不同的结构技能。下面将列出更常见的方法。

在实践中，最广泛应用于包围体的是轴对齐包围盒(AABB)。AABB容易实现，同光的求交测试非常快。在描述BVH的创建时，大多数关于BVH的论文通常基于Kay和Kajiya、Goldsmith和Salmon两个基本想法。Kay和Kajiaya建议自上而下创建BVH。

Goldsmith和Salmon提出了更复杂的自下而上的结构方法。Goldsmith和Salmon指出，BVH的质量与三角形作为输入传人的顺序有关。因此，他们建议在构建BVH之前随机扰乱三角形的顺序。以下算法是利用Kay/Kajiya的思想创建一个场景的包围层次：

本文成功地在GPU上实现了用于光跟踪算法的各种加速结构，并比较了这些加速结构在GPU上的加速效果。作为CPU上第一个光跟踪器的加速结构，也被证明是最慢的，除非它只包含一个单独的物体场景。均匀网格不适用于几何密度很高的场景。此外，对于均匀网格的CPU上的遍历，还需要大量的数据。Foley和Sugerman认为，对于大多数场景，KD-tree的效率高于均匀网格。然而，在KD-tree的遍历过程中，无论是重置阶段还是回归阶段，片元程序都非常复杂，但这种复杂性也使其在改变场景几何密度时能够做出适当的调整。本文实现的BVH是最快的加速结构。BVH加速结构在GPU上比其他加速结构更容易实现。