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

KD树是三维场景渲染中常用的空间加速算法。由于SIMD计算平台不支持递归操作,导致KD树在GPU上的应用受到限制,因此提出了一个新的基于SIMD架构的并行KD树算法。通过创建时对KD树线索化,不仅省去堆栈使用,且因无需回溯到根节点而减少大量无效遍历操作,实现了基于GPU的高效并行加速。实验结果表明,线索KD树算法每秒计算的光线数与传统算法相比,提高3~8倍不等,最终显著提高光线跟踪渲染速度。

A Novel Algorithm of Clued KD-tree on SIMD Architecture

KD-tree is a traditional accelerating algorithm in 3D scene rendering,and its parallel processing performance is restricted to the unsupported recursion operations on SIMD architecture.A novel parallel algorithm is proposed to speed up KD-tree traversal on GPU.Clues pointing to six-direction subsequent nodes are inserted into the KD-tree structure.Thus,the algorithm efficiency is improved by avoiding stack data structure and reducing the worthless operations.The experiment results verify that the clued KD-tree algorithm increases the rendering speed by 3 to 8 times than the traditional algorithms.