SAH KD-Tree Construction on GPU
Loading...
Date
2011
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
ACM
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 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.
Description
@inproceedings{10.1145:2018323.2018335,
booktitle = {Eurographics/ ACM SIGGRAPH Symposium on High Performance Graphics},
editor = {Carsten Dachsbacher and William Mark and Jacopo Pantaleoni},
title = {{SAH KD-Tree Construction on GPU}},
author = {Wu, Zhefeng and Zhao, Fukai and Liu, Xinguo},
year = {2011},
publisher = {ACM},
ISSN = {2079-8687},
ISBN = {978-1-4503-0896-0},
DOI = {10.1145/2018323.2018335}
}