焦良葆， 陈 瑞， 张 健

（南京工程学院通信工程学院，江苏 南京 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，但仍然需要使用少量堆栈。……