SAH KD-Tree Construction on GPU

Simple item page
dc.contributor.authorWu, Zhefengen_US
dc.contributor.authorZhao, Fukaien_US
dc.contributor.authorLiu, Xinguoen_US
dc.contributor.editorCarsten Dachsbacher and William Mark and Jacopo Pantaleonien_US
dc.date.accessioned2016-02-18T11:01:48Z
dc.date.available2016-02-18T11:01:48Z
dc.date.issued2011en_US
dc.description.abstractKD-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.en_US
dc.description.sectionheadersAcceleration Structuresen_US
dc.description.seriesinformationEurographics/ ACM SIGGRAPH Symposium on High Performance Graphicsen_US
dc.identifier.doi10.1145/2018323.2018335en_US
dc.identifier.isbn978-1-4503-0896-0en_US
dc.identifier.issn2079-8687en_US
dc.identifier.pages71-78en_US
dc.identifier.urihttps://doi.org/10.1145/2018323.2018335en_US
dc.publisherACMen_US
dc.subjectGPUen_US
dc.subjectKDen_US
dc.subjectTreeen_US
dc.subjectSurface Area Heuristicen_US
dc.subjectRay Tracingen_US
dc.subjectParallel Computingen_US
dc.titleSAH KD-Tree Construction on GPUen_US
Files
Collections
High-Performance Graphics 2011