Parallel SAH k-D Tree Construction for Fast Dynamic Scene Ray Tracing

Choi, Byn; Komuravelli, Rakesh; Lu, Victor; Sung, Hyojin; Bocchino, Robert L., Jr.

Permalink

https://hdl.handle.net/2142/13798 Copy

Description

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.

Issue Date

2009-09-22

Keyword(s)

• Ray Tracing
• SAH
• Parallel Computing
• Multicore

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.

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/13798

Copyright and License 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.

Owning Collections