3.2 KD-tree
最近，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，提出了不同的构造技巧。下面，将列出比较通用的方法。
在实践中，对于包抄体应用的最广泛的就是轴对齐包抄盒(DDAA)。CCAA易于实现，并且同光线的求交测试非常快。大多数有关BVH的论文在描述BVH的创建的时候，通常分别以Kay和Kajiya，或者Goldsmith和Salmon这两种基本的想法主意为基础。Kay和Kajiaya建议以自上而下递回的方式入行BVH的创建。
Goldsmith和Salmon提出了一个更加复杂的自底向上的构造方式。Goldsmith和Salmon指出，BVH的质量同作为输进传人的三角形的顺序有关。因此，他们建议在构造BVH之前，随机打乱三角形的顺序。下述算法就是利用Kay/Kajiya的思惟创建某个场景的包抄体层次的方法：
4．结束语
本文成功的在GPU上实现了用于光线跟踪算法中的各种加速结构，并对这些加速结构在GPU上的加速效果入行了比较。平均栅格作为第一个在CPU上实现的光线跟踪器的加速结构，也被证实是最慢的，除非是只包含一个单独的物体的场景的情况。平均栅格不适合几何体的密度非常高的场景。另外，对于平均栅格的CPU上的遍历表示，也需要大量的数据。Foley和Sugerman以为，对于大多数场景，KD-tree的效率要比平均栅格高。但是，在KD-tree的遍历过程中，无论是重置阶段仍是归退阶段，片元程序都非常的复杂，但这种复杂性也使得其能够在场景的几何体的密度改变的时候做出适当的调整。本文实现的BVH被证其实加速效果上要超过平均栅格和KD-tree，在现阶段，BVH是在GPU上实现的最快的加速结构。并且在GPU上实现BVH加速结构要比实现其他加速结构更加的简朴。
参考文献：
