一个新的线索KD树并行算法

焦良葆， 陈 瑞， 张 健

（南京工程学院通信工程学院，江苏 南京 211167）

作为在光线跟踪广泛使用的一种层次树结构，KD树(K-Dimensional Tree)得到了诸多研究者的关注[1]。作为一种基于空间剖分的加速结构，它采用轴对齐的分割面对场景空间进行剖分，递归地生成空间单元间的组织结构。光线跟踪算法中，当光线穿越空间单元时，就借助空间单元间的这种组织关系，跨越空单元来直接找到包含物体的单元，并进行光线与物体的求交测试，然后计算光强进行场景渲染。算法中计算量最大的部分就是光线与物体的求交运算。为提高光线和物体的求交速度，除了KD树外，常用的加速结构还有 Grids（网格）和 BVH（Bounding Volume Hierarchies，层次包围体）等[2-3]。文献[4]对基于CPU的光线跟踪算法的加速结构进行比较，认为对于不同类型的测试场景平均而言，KD树是最快的。同时由于光线跟踪有着天然的并行性，为了利用基于 SIMD（Single Instruction Multiple Data，单指令多数据）计算平台的GPU（Graphic Process Unit，图形处理单元）协处理器在并行计算上的优势，将KD树算法移植到GPU上已成为目前的研究热点[5-6]。

KD树算法包括创建和遍历两个过程。好的KD树构建方法能够生成优化的树结构，从而提高遍历速度。传统上KD树的实现一般基于递归过程或者栈数据结构，但 GPU缺少对递归过程的支持且堆栈存取效率低下。因此，Foley等人[5]提出了基于GPU的无栈遍历算法KD-restart。算法中为省去堆栈结构，每次遍历都退回到根节点处重新开始，因此遍历效率低下。斯坦福大学Daniel Reiter Horn等人[6]在此基础上提出了short-stack遍历算法，采用push-down结构降低额外的节点访问次数，效率高于 KD-restart，但仍然需要使用少量堆栈。

本文提出一种新的线索KD树算法，在创建KD树时加以线索化，保存叶节点的六个方向的后继节点索引。在GPU上实现KD树遍历时，根据光线在当前叶节点的穿出平面沿着线索直接得到后继节点，避免了从根节点（或中间节点）到叶节点过程中的“远”子节点压栈操作；计算中利用高效纹理内存操作替代低效的递归堆栈操作，不仅避免了栈的使用，而且遍历时根据索引值能快速找到后继节点，无需退回到根节点处，从而减少无效遍历的次数，显著地提高遍历效率。

1 相关工作

传统的KD树的构建和遍历过程是对节点空间进行自上而下划分和操作的递归过程。其中，在构建KD树时的初始输入是整个场景的图元集合T（通常采用三角片图元）及空间V（通常采用AABB轴对称绑定盒）；最佳分割平面P一般通过SAH(Surface Area Heuristic，表面积启发)[6]的方法计算得到。在光线跟踪应用中，通过 KD树的遍历进行光线与图元的求交测试，输出第一个与光线相交的图元及交点。遍历KD树的初始输入是光线ray、场景空间节点（即KD树的根节点root）和光线在节点中的起止参数（tmin和tmax）。进行节点遍历时，如果光线横跨分割平面的两侧，说明该光线同时穿过该节点的两个孩子节点 lchild/rchild，则先与第一个子节点求交（这个节点记为“近”节点 nearNode），并将第二个子节点压入堆栈（这个以后可能会访问到的节点记为“远”节点farNode）；否则直接遍历光线经过的孩子节点。因此，光线遍历KD树时需从根节点开始，直到叶节点然后求交，是一个递归过程。

由于 GPU不支持递归操作，只有使用栈数据结构来替代。在SIMD计算架构的GPU中栈空间必须使用全局存储空间，访问效率非常低，访问时间接近于高效寄存器内存的100倍，因此标准的KD树遍历算法不适合在SIMD计算架构上运行。基于此，研究人员提出了基于SIMD的KD树遍历改进算法。Foley[5]提出了一种无栈的遍历算法kd-restart。在该算法中，光线总是访问“近”节点而舍弃“远”节点；当光线在叶节点中没有找到相交的图元，则把光线的起点前移到叶节点的出口处（即tmax处），重新从根节点开始遍历，直到找到与之相交的三角片或遍历完整棵树。算法的输入是光线、根节点及光线在场景中的起止点参数 sceneMin和 sceneMax。在kd-restart遍历算法中，虽然避免了使用堆栈结构，但算法中的每次遍历，光线都是从根节点开始，直至找到叶子节点，大量重复查询导致该算法的效率不高。Daniel Reiter Horn[6]等人在kd-restart算法和标准遍历算法的基础上，提出了short-stack算法；引入了push-down结构，用于记录从根节点下溯到叶子的过程中的分叉状态，如未发生分叉（即光线未与分割平面相交），则根节点可以下压。通过采用根节点下压和固定大小的栈结构，该算法相对于kd-restart显著减少了无效回溯，相对于传统的全栈遍历显著减小了栈结构。

综上所述，基于SIMD架构的GPU实现KD树的遍历时，算法效率的关键在于减少堆栈结构的使用，同时减少无效回溯。而之所以需使用栈结构就在于需要保存并获取光线穿越节点后所要到达的后继空间节点，类似于二叉树遍历中的线索树中的线索。

而在 KD树的创建和遍历算法的实现过程中，可以发现光线从某个叶节点穿过后，一定与相邻的节点相交。由于KD树中的分割面都是轴对齐的，每个子节点都是一个轴对齐的包围盒，因此每个节点共有上、下、左、右、前、后六个面。在KD树建立完成后，从任意一个面穿出后的后继空间节点是确定的。这样，就可以建立一个三维空间的线索KD树，用来保存并获取光线穿越节点后所要到达的后继空间节点。基于这样的考虑，作者提出了一个新的线索KD树算法。

2 线索KD树

为了保存线索信息，在建立KD树时，在节点信息中增加一个数据结构 nodebox，用来保存与每个叶子节点六个面相邻的节点（此节点可能是叶节点，也有可能是中间节点），即为每个叶节点保存六个线索。可以先将父亲节点的线索值继承给孩子节点，然后根据父亲节点的分割方式修正孩子节点的两个线索，即左孩子的右线索就是右孩子，如此类推。线索的继承和更新过程可采用二维图解，如图1所示。

图1 节点二维结构和层次关系

图1中，以节点8为例来说明子节点如何继承父节点的nodebox并进行更新的。根节点1的nodebox={-1，-1，-1，-1}，其分割平面垂直于X轴，子节点2和3首先继承了根节点1的nodebox，然后在X轴方向上更新子节点2和3的nodebox。节点2的nodebox更新为{-1，3，-1，-1}，节点3的nodebox更新为{2，-1，-1，-1}。此时，将节点3压入栈中。继续对节点2进行分割，其分割平面垂直于Y轴，分为4和5两个子节点。节点4继承节点2的nodebox，并更新为{-1，3，-1，5}；节点5也继承了节点2的nodebox，并更新为{-1，3，4，-1}。然后，将节点 5压栈，继续对节点4进行分割，其分割平面垂直于Y轴，得到子节点8和9。节点8的nodebox先继承节点4的nodebox{-1，3，-1，5}，然后更新为{-1，3，-1，9}，节点 9的 nodebox也继承节点 4的nodebox，并更新为{-1，3，8，5}。

光线跟踪中，遍历时如果光线经过了某个叶节点且和此叶节点中的图元无交点，可根据光线的穿出平面及该面的线索值得到下一个需遍历的节点。由于建树时线索的获得采用了继承的方式，因此此节点与KD树标准遍历算法中的栈顶节点完全相同。

现在的关键就是需得到穿出平面，而穿出平面的实质就是最近一次导致分叉状态的分割平面。由于每个节点有六个穿出平面，可用一个三比特的索引值来表示。因此，作者定义了一个长整型变量SplitStack来保存每次分叉状态所导致的分割平面，最低三个比特就是最近一次分割平面。这样当光线在KD树中遍历时，如光线横跨当前节点的分割面，就不再需要将“远”子节点和 t_split，t_max压入堆栈，只需要将分割平面更新存入SplitStack变量即可。

下面详细介绍索引 KD树的创建和遍历算法。

2.1 线索KD树的建立

线索KD树与普通KD树相比，为叶节点增加了一个用于记录与该叶节点的六个穿出平面线索的数组 nodebox。nodebox中的元素类型为int clue[6]。线索KD树的创建过程也是一个自顶向下的递归的过程，在 CPU上实现的具体算法见图2左。

2.2 线索KD树的遍历

标准遍历算法中的栈操作不适合在 GPU上运行，因为栈操作会大幅度地降低 GPU的并行效率，作者线索操作代替栈操作，从而提高GPU的并行效率。在剔除了标准遍历算法中大幅降低GPU并行效率的栈操作，使用线索操作来替代的基础上，作者得到了基于GPU的线索KD树的遍历算法，具体遍历算法参见图2右。

图2 线索KD树的构建(左)和遍历(右)算法

3 算法的实现及实验结果分析

实验的硬件环境是：CPU为Intel CoreTM2，1.86GHz；GPU为NVIDIA Geforce 260 GTX。实验场景包括Cornel box、Robots和Kitchen三个典型场景。原始的场景数据来源于BART项目，主要由AFF格式的场景描述文件和ppm格式的纹理图片文件组成。这些文件，由主文件kitchen.aff通过i(include)命令，逐级包含，形成对于场景的整体描述[10]。渲染结果如图3所示。

作者将线索KD树算法与Foley和Horn等人提出的算法进行了比较，各算法的效率比较如表1，push-down、kd-restart和short-stack算法的效率来自文献[6]。从表1中可以看出，为节点增加了索引后，能大幅度提高算法的效率。例如，kitchen场景中，采用push-down算法、kd-restart算法及short-stack算法，每秒计算的光线数为分别为 21.4×106、17.1×106和 27.3×106，而索引 KD树算法每秒计算的光线数为 139.8×106，分别提高了6.5、8.1和5.1倍；对于Robots场景，索引KD树算法的效率比这三种算法又分别提高了3.1、4.2和2.5倍。

图3 线索KD树重建和光线跟踪的实验场景

表1 算法效率比较

4 结束语

本文在Foley，Daniel Reiter Horn等人提出的KD树算法的基础上，通过对各种KD树遍历算法的分析，提出了基于索引值的KD树算法，不仅省去了堆栈的使用，而且遍历算法更高效。通过对Kitchen和Robots两个场景的渲染结果比较，作者的算法每秒计算的光线数比 push-down算法提高了3～6倍，比kd-restart算法提高了4～8倍，比short-stack算法提高了3～5倍。

目前，KD树的创建工作还是在 CPU上完成，然后将数据结构导入 GPU中。为了能将实现动态场景的光线跟踪，需要将KD树的创建速度和遍历速度进一步提高。作者下一步的工作是将KD树的创建移植到GPU上执行，进而实现动态场景的光线跟踪算法。

[1]Artur L dos Santos, et al. KD-Tree traversal implementations for ray tracing on massive multiprocessors: a comparative Study [C]//21st International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2009,2009: 41-48.

[2]Wald I, Boulos S, Shirley P. Ray tracing deformable scenes using dynamic bounding volume hierarchies [J].ACM Transactions on Graphics, 2007, 26(1): 1-18.

[3]李 静, 吴恩华. 基于空盒自适应生成的动态场景光线跟踪计算[J]. 计算机学报, 2009, (6):1172-1182.

[4]Wald I, Ize T, Kensler A, et al. Ray tracing animated scenes using coherent grid traversal [J]. ACM Transactions on Graphics, 2006, 25(3): 485-493.

[5]Foley T, Sugerman J. KD-tree acceleration structures,for a GPU ray tracer [C]//SIGGRAPH/EUROGRAPHICS Workshop on Graphics Hardware:Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware. New York: ACM Press, 2005: 15-22.

[6]Daniel Reiter Horn, Jeremy Sugerman, Mike Houston,et al. Interactive k-d tree GPU raytracing [C]//Proceedings of the 2007 Symposium on Interactive 3D Graphics and Games. 2007, Seattle, Washington, 2007:167-174.

[7]BART: A benchmark for animated ray tracing [EB/OL].http://www.ce.chalmers.se/research/group/graphics/BART/