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