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

图学学报

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

出版日期:2011-10-28 发布日期:2015-08-12

A Novel Algorithm of Clued KD-tree on SIMD Architecture

Online:2011-10-28 Published:2015-08-12

摘要/Abstract

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

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

Abstract: 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.

Key words: 3D scene rendering, clued KD-tree, parallel algorithm, single instruction multiple data platform

焦良葆，陈瑞，张健. 一个新的线索KD树并行算法[J]. 图学学报.

JIAO Liang-bao, CHEN Rui, ZHANG Jian. A Novel Algorithm of Clued KD-tree on SIMD Architecture[J]. Journal of Graphics.

[1]	杨淑云 1，刘永春 2 . 小场景交互式稠密三维重建系统[J]. 图学学报, 2019, 40(2): 364-372.
[2]	王结臣，蒲英霞，崔璨，陈刚，马劲松. 一种基于点集自适应分组构建Voronoi 图的并行算法[J]. 图学学报, 2012, 33(6): 7-13.