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

A Novel Algorithm of Clued KD-tree on SIMD Architecture

作　　者：焦良葆[1] 陈瑞[1] 张健[1] 

机构地区：[1]南京工程学院通信工程学院,江苏南京211167

出　　处：《工程图学学报》2011年第5期46-50,共5页Journal of Engineering Graphics

基　　金：江苏省自然科学基金资助项目(BK2009351);西门子中国研究院资助项目

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

关 键 词：三维场景渲染 线索KD树 并行算法 SIMD平台 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]