Parallel sah k-D tree construction

Byn Choi, Rakesh Komuravelli, Victor Lu, Hyojin Sung, Robert L. Bocchino, Sarita V Adve, John C Hart

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 8? 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.

Original languageEnglish (US)
Title of host publicationHigh-Performance Graphics 2010 - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG 2010
EditorsSamuli Laine, Warren Hunt, Michael Doggett
PublisherAssociation for Computing Machinery
Pages77-86
Number of pages10
ISBN (Print)9783905674262
StatePublished - Jun 25 2010
Event2nd ACM SIGGRAPH / Eurographics on High-Performance Graphics, HPG 2010 - Saarbrucken, Germany
Duration: Jun 25 2010Jun 27 2010

Publication series

NameHigh-Performance Graphics - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG
ISSN (Print)2079-8679
ISSN (Electronic)2079-8687

Other

Other2nd ACM SIGGRAPH / Eurographics on High-Performance Graphics, HPG 2010
CountryGermany
CitySaarbrucken
Period6/25/106/27/10

Fingerprint

Ray tracing
Parallel algorithms
Data structures
Scalability
Costs

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software
  • Computational Theory and Mathematics
  • Computer Graphics and Computer-Aided Design

Cite this

Choi, B., Komuravelli, R., Lu, V., Sung, H., Bocchino, R. L., Adve, S. V., & Hart, J. C. (2010). Parallel sah k-D tree construction. In S. Laine, W. Hunt, & M. Doggett (Eds.), High-Performance Graphics 2010 - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG 2010 (pp. 77-86). (High-Performance Graphics - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG). Association for Computing Machinery.

Parallel sah k-D tree construction. / Choi, Byn; Komuravelli, Rakesh; Lu, Victor; Sung, Hyojin; Bocchino, Robert L.; Adve, Sarita V; Hart, John C.

High-Performance Graphics 2010 - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG 2010. ed. / Samuli Laine; Warren Hunt; Michael Doggett. Association for Computing Machinery, 2010. p. 77-86 (High-Performance Graphics - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Choi, B, Komuravelli, R, Lu, V, Sung, H, Bocchino, RL, Adve, SV & Hart, JC 2010, Parallel sah k-D tree construction. in S Laine, W Hunt & M Doggett (eds), High-Performance Graphics 2010 - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG 2010. High-Performance Graphics - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG, Association for Computing Machinery, pp. 77-86, 2nd ACM SIGGRAPH / Eurographics on High-Performance Graphics, HPG 2010, Saarbrucken, Germany, 6/25/10.
Choi B, Komuravelli R, Lu V, Sung H, Bocchino RL, Adve SV et al. Parallel sah k-D tree construction. In Laine S, Hunt W, Doggett M, editors, High-Performance Graphics 2010 - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG 2010. Association for Computing Machinery. 2010. p. 77-86. (High-Performance Graphics - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG).
Choi, Byn ; Komuravelli, Rakesh ; Lu, Victor ; Sung, Hyojin ; Bocchino, Robert L. ; Adve, Sarita V ; Hart, John C. / Parallel sah k-D tree construction. High-Performance Graphics 2010 - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG 2010. editor / Samuli Laine ; Warren Hunt ; Michael Doggett. Association for Computing Machinery, 2010. pp. 77-86 (High-Performance Graphics - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG).
@inproceedings{6ec78bdf4b694e07a2bf9e640e86b633,
title = "Parallel sah k-D tree construction",
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 8? 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.",
author = "Byn Choi and Rakesh Komuravelli and Victor Lu and Hyojin Sung and Bocchino, {Robert L.} and Adve, {Sarita V} and Hart, {John C}",
year = "2010",
month = "6",
day = "25",
language = "English (US)",
isbn = "9783905674262",
series = "High-Performance Graphics - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG",
publisher = "Association for Computing Machinery",
pages = "77--86",
editor = "Samuli Laine and Warren Hunt and Michael Doggett",
booktitle = "High-Performance Graphics 2010 - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG 2010",

}

TY - GEN

T1 - Parallel sah k-D tree construction

AU - Choi, Byn

AU - Komuravelli, Rakesh

AU - Lu, Victor

AU - Sung, Hyojin

AU - Bocchino, Robert L.

AU - Adve, Sarita V

AU - Hart, John C

PY - 2010/6/25

Y1 - 2010/6/25

N2 - 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 8? 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.

AB - 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 8? 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.

UR - http://www.scopus.com/inward/record.url?scp=84995650305&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84995650305&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84995650305

SN - 9783905674262

T3 - High-Performance Graphics - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG

SP - 77

EP - 86

BT - High-Performance Graphics 2010 - ACM SIGGRAPH / Eurographics Symposium Proceedings, HPG 2010

A2 - Laine, Samuli

A2 - Hunt, Warren

A2 - Doggett, Michael

PB - Association for Computing Machinery

ER -