SAH KD-tree construction on GPU

Abstract

KD-tree is one of the most efficient acceleration data structures for ray tracing. In this paper, we present a kd-tree construction algorithm that is precisely SAH-optimized and runs entirely on GPU. We construct the tree nodes in breadth-first order. In order to precisely evaluate the SAH cost, we design a parallel scheme based on the standard parallel scan primitive to count the triangle numbers for all split candidates, and a bucket-based algorithm to sort the AABBs (axis-aligned bounding box) of the clipped triangles of the child nodes. The proposed parallel algorithms can be mapped well to GPU's streaming architecture. The experiments showed that our algorithm can produce the highest quality kd-tree as the off-line CPU algorithms, but runs faster than multi-core CPU algorithms and the GPU SAH BVH-Tree algorithm.