Wu, ZhefengZhao, FukaiLiu, XinguoCarsten Dachsbacher and William Mark and Jacopo Pantaleoni2016-02-182016-02-182011978-1-4503-0896-02079-8687https://doi.org/10.1145/2018323.2018335KD-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 theAABBs (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.GPUKDTreeSurface Area HeuristicRay TracingParallel Computing10.1145/2018323.201833571-78