Parallel SAH k-D Tree Construction
Loading...
Date
2010
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
Abstract
The k-D tree is a well-studied acceleration data structure for ray tracing. It is used to organize primitives in a scene to allow efficient execution of intersection operations between rays and the primitives. The highest quality k-D tree can be obtained using greedy cost optimization based on a surface area heuristc (SAH). While the high quality enables very fast ray tracing times, a key drawback is that the k-D tree construction time remains prohibitively expensive. This cost is unreasonable for rendering dynamic scenes for future visual computing applications on emerging multicore systems. Much work has therefore been focused on faster parallel k-D tree construction performance at the expense of approximating or ignoring SAH computation, which produces k-D trees that degrade rendering time. In this paper, we present two new parallel algorithms for building precise SAH-optimized k-D trees, with different tradeoffs between the total work done and parallel scalability. The algorithms achieve up to 8x speedup on 32 cores, without degrading tree quality and rendering time, yielding the best reported speedups so far for precise-SAH k-D tree construction.
Description
@inproceedings{:10.2312/EGGH/HPG10/077-086,
booktitle = {High Performance Graphics},
editor = {Michael Doggett and Samuli Laine and Warren Hunt},
title = {{Parallel SAH k-D Tree Construction}},
author = {Choi, Byn and Komuravelli, Rakesh and Lu, Victor and Sung, Hyojin and Bocchino, Robert L. and Adve, Sarita V. and Hart, John C.},
year = {2010},
publisher = {The Eurographics Association},
ISSN = {2079-8687},
ISBN = {978-3-905674-26-2},
DOI = {/10.2312/EGGH/HPG10/077-086}
}