Files in this item



application/pdfparkd.pdf (1MB)
(no description provided)PDF


Title:Parallel SAH k-D Tree Construction for Fast Dynamic Scene Ray Tracing
Author(s):Choi, Byn; Komuravelli, Rakesh; Lu, Victor; Sung, Hyojin; Bocchino, Robert L., Jr.
Contributor(s):Adve, Sarita V.; Hart, John C.
Subject(s):Ray Tracing
Parallel Computing
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 new, faster multicore al- gorithms for building precise SAH-optimized kd-trees. Our best algorithm makes a tradeoff between worse cache performance and higher parallelism to provide up to 7X speedup on 16 cores, using two different kinds of parallelism models, without degrading tree quality and rendering time.
Issue Date:2009-09-22
Genre:Technical Report
Rights Information:This work was funded by the Universal Parallel Computing Research Center at the University of Illinois at Urbana-Champaign. The Center is sponsored by Intel Corporation and Microsoft Corporation.
Date Available in IDEALS:2009-09-22

This item appears in the following Collection(s)

Item Statistics