Chapter 13 On the Efficient Implementation of a Real-time Kd-tree Construction Algorithm 1
Byungjoon Chang, Woong Seo, Insung Ihm · 2013
The kd-tree is one of the most commonly used spatial data structures for a variety of graphics applications because of its reliably high acceleration perfor- mance. Several years ago, Zhou et al. devised an effective kd-tree construction al- gorithm that runs entirely on a GPU. In this chapter, we present improved GPU programming techniques for implementing the algorithm more efficiently on cur- rent GPUs. One of the major ideas is to reduce the number of necessary kernel functions by replacing the essential, segmented-scan, and reduction computations by simpler per-block atomic operations, thereby alleviating the overheads from multiple synchronous kernel calls. Combined with the efficient implementation of intrablock scan and reduction, using recently introduced intrinsic functions, these changes achieve remarkable performance enhancement to the kd-tree construction process. Through an example of real-time ray tracing for dynamic scenes of non- trivial complexity, we demonstrate that the proposed GPU techniques can be ex- ploited effectively for various real-time applications.