IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

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

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/13798

Files in this item

File Description Format
PDF parkd.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.
Contributor(s): Adve, Sarita V.; Hart, John C.
Subject(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.
Issue Date: 2009-09-22
Genre: Technical Report
Type: Text
Language: English
URI: http://hdl.handle.net/2142/13798
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)

Show full item record

Item Statistics

  • Total Downloads: 1600
  • Downloads this Month: 24
  • Downloads Today: 0

Browse

My Account

Information

Access Key