research-article

Improved two-level BVHs using partial re-braiding

Authors:

Carsten Benthin,

Attila T. ÁfraAuthors Info & Claims

HPG '17: Proceedings of High Performance Graphics

Article No.: 7, Pages 1 - 8

https://doi.org/10.1145/3105762.3105776

Published: 28 July 2017 Publication History

Abstract

We propose a novel approach for improving the quality of two-level BVHs (i.e., a two-level data structure that uses a top-level BVH built over second-level object BVHs). After building an individual, high-quality BVH for each object, our new top-level BVH build approach selectively re-braids (opens and merges) object BVHs during the build process to reduce overlap and improve SAH quality. We demonstrate that compared to the two main state-of-the-art techniques---brute-force re-construction of a single, flat BVH; and building a traditional two-level BVH over objects, respectively---the proposed approach achieves build times significantly faster than the former, while simultaneously yielding traversal performance that is much higher than the latter.

References

[1]

O. Deussen, P. Hanrahan, B. Lintermann, R. Mech, M. Pharr, and P. Prusinkiewicz. 1998. Realistic Modeling and Rendering of Plant Ecosystems. In Computer Graphics (Proceedings of SIGGRAPH 98). 275--286.

Digital Library

[2]

Valentin Fuetterling, Carsten Lojewski, Franz-Josef Pfreundt, and Achim Ebert. 2016. Parallel Spatial Splits in Bounding Volume Hierarchies. Eurographics Symposium on Parallel Graphics and Visualization (2016).

Digital Library

[3]

P. Ganestam, R. Barringer, M. Doggett, and T. Akenine-Möller. 2015. Bonsai: Rapid Bounding Volume Hierarchy Generation using Mini Trees. Journal of Computer Graphics Techniques (JCGT) 4, 3 (2015), 23--42.

[4]

Per Ganestam and Michael Doggett. 2016. SAH Guided Spatial Split Partitioning for Fast BVH Construction. Comput. Graph. Forum 35, 2 (2016), 285--293.

[5]

Yan Gu, Yong He, Kayvon Fatahalian, and Guy Blelloch. 2013. Efficient BVH Construction via Approximate Agglomerative Clustering. (2013), 81--88.

Digital Library

[6]

Eric Haines, Pat Hanrahan, Robert L Cook, James Arvo, David Kirk, and Paul S Heckbert. 1989. An Introduction to Ray Tracing.

[7]

Jakub Hendrich, Daniel Meister, and Jiri Bittner. 2017. Parallel BVH Construction using Progressive Hierarchical Refinement, In Eurographics 2017. Computer Graphics Forum (2017).

Digital Library

[8]

Qiming Hou, Xin Sun, Kun Zhou, Christian Lauterbach, and Dinesh Manocha. 2010. Memory-Scalable GPU Spatial Hierarchy Construction. IEEE Transactions on Visualization & Computer Graphics (June 2010).

Digital Library

[9]

Warren Hunt, William R. Mark, and Don Fussell. 2007. Fast and Lazy Build of Acceleration Structures from Scene Hierarchies. In IEEE/EG Symposium on Interactive Ray Tracing 2007. IEEE/EG, 47--54.

Digital Library

[10]

Tero Karras and Timo Aila. 2013. Fast Parallel Construction of High-Quality Bounding Volume Hierarchies. In Proceedings of High Performance Graphics.

Digital Library

[11]

Andrew Kensler. 2008. Tree Rotations for Improving Bounding Volume Hierarchies. In Proceedings of the 2008 IEEE Symposium on Interactive Ray Tracing.

[12]

Christian Lauterbach, Michael Garland, Shubhabrata Sengupta, David Luebke, and Dinesh Manocha. 2009. Fast BVH Construction on GPUs. In Proceedings of Eurographics '09.

[13]

S.G. Parker, J. Bigler, A. Dietrich, H. Friedrich, J. Hoberock, D. Luebke, D. McAllister, M. McGuire, K. Morley, A. Robison, and others. 2010. OptiX: a general purpose ray tracing engine. ACM Transactions on Graphics (TOG) 29, 4 (2010).

Digital Library

[14]

Matt Pharr and Greg Humphreys. 2010. Physically Based Rendering: From Theory to Implementation (2nd ed.). Morgan Kaufman.

Digital Library

[15]

Marek Vinkler, Vlastimil Havran, and Jiri Bittner. 2016. Performance Comparison of Bounding Volume Hierarchies and Kd-Trees for GPU Ray Tracing. Computer Graphics Forum 35, 8 (2016), 68--79.

[16]

Ingo Wald, Carsten Benthin, and Philipp Slusallek. 2003. Distributed Interactive Ray Tracing of Dynamic Scenes. In Proceedings of the IEEE Symposium on Parallel and Large-Data Visualization and Graphics. 11--20.

Digital Library

[17]

Ingo Wald and Vlastimil Havran. 2006. On building fast kd-trees for ray tracing, and on doing that in O(N log N). In Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing. 61--69.

[18]

Ingo Wald, Sven Woop, Carsten Benthin, Gregory S. Johnson, and Manfred Ernst. 2014. Embree: A Kernel Framework for Efficient CPU Ray Tracing. ACM Transactions on Graphics 33, 4, Article 143 (2014), 8 pages.

Digital Library

[19]

Sung-Eui Yoon, Sean Curtis, and Dinesh Manocha. 2007. Ray Tracing Dynamic Scenes using Selective Restructuring. In Eurographics Symposium on Rendering.

Digital Library

Cited By

Meister DKulkarni PVasishta AHarada T(2024)HIPRT: A Ray Tracing Framework in HIPProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36753787:3(1-18)Online publication date: 9-Aug-2024
https://dl.acm.org/doi/10.1145/3675378
Sabino RVidal CCavalcante-Neto JMaia J(2024)Building Oriented Bounding Boxes by the intermediate use of ODOPsComputers and Graphics10.1016/j.cag.2023.08.028116:C(251-261)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1016/j.cag.2023.08.028
Liu LSaed MChou YGrigoryan DNowicki TAamodt T(2023)LumiBench: A Benchmark Suite for Hardware Ray Tracing2023 IEEE International Symposium on Workload Characterization (IISWC)10.1109/IISWC59245.2023.00011(1-14)Online publication date: 1-Oct-2023
https://doi.org/10.1109/IISWC59245.2023.00011
Show More Cited By

Index Terms

Improved two-level BVHs using partial re-braiding
1. Computing methodologies
  1. Computer graphics
    1. Rendering
      1. Ray tracing
      2. Visibility

Recommendations

Grid-based SAH BVH construction on a GPU
CGI'2011 Conference

We present an efficient algorithm for building an adaptive bounding volume hierarchy (BVH) in linear time on commodity graphics hardware using CUDA. BVHs are widely used as an acceleration data structure to quickly ray trace animated polygonal scenes. ...
GPU Ray Tracing Based on Reduced Bounding Volume Hierarchies
CGIV '12: Proceedings of the 2012 Ninth International Conference on Computer Graphics, Imaging and Visualization

We present a bounding volume hierarchy construction based on a culling technique for performing ray tracing on manycore GPUs. The objects are divided into view-sets of triangles with respect to a set of view targets (including the camera and the light ...
MergeTree: A Fast Hardware HLBVH Constructor for Animated Ray Tracing

Ray tracing is a computationally intensive rendering technique traditionally used in offline high-quality rendering. Powerful hardware accelerators have been recently developed that put real-time ray tracing even in the reach of mobile devices. However, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

HPG '17: Proceedings of High Performance Graphics

July 2017

180 pages

ISBN:9781450351010

DOI:10.1145/3105762

General Chairs:
Morgan McGuire
Williams College
,
Anjul Patney
NVIDIA

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

HPG '17

Sponsor:

SIGGRAPH
EUROGRAPHICS

HPG '17: High-Performance Graphics

July 28 - 30, 2017

California, Los Angeles

Acceptance Rates

Overall Acceptance Rate 15 of 44 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
314
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)2

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Meister DKulkarni PVasishta AHarada T(2024)HIPRT: A Ray Tracing Framework in HIPProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36753787:3(1-18)Online publication date: 9-Aug-2024
https://dl.acm.org/doi/10.1145/3675378
Sabino RVidal CCavalcante-Neto JMaia J(2024)Building Oriented Bounding Boxes by the intermediate use of ODOPsComputers and Graphics10.1016/j.cag.2023.08.028116:C(251-261)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1016/j.cag.2023.08.028
Liu LSaed MChou YGrigoryan DNowicki TAamodt T(2023)LumiBench: A Benchmark Suite for Hardware Ray Tracing2023 IEEE International Symposium on Workload Characterization (IISWC)10.1109/IISWC59245.2023.00011(1-14)Online publication date: 1-Oct-2023
https://doi.org/10.1109/IISWC59245.2023.00011
Benthin CDrabinski RTessari LDittebrandt A(2022)PLOC++Proceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/35438675:3(1-13)Online publication date: 27-Jul-2022
https://dl.acm.org/doi/10.1145/3543867
Wald IParker S(2022)Data Parallel Path Tracing with Object HierarchiesProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/35438615:3(1-16)Online publication date: 27-Jul-2022
https://dl.acm.org/doi/10.1145/3543861
Meister DOgaki SBenthin CDoyle MGuthe MBittner J(2021)A Survey on Bounding Volume Hierarchies for Ray TracingComputer Graphics Forum10.1111/cgf.14266240:2(683-712)Online publication date: 4-Jun-2021
https://doi.org/10.1111/cgf.142662
Lee WLiktor GVaidyanathan K(2019)Flexible Ray Traversal with an Extended Programming ModelSIGGRAPH Asia 2019 Technical Briefs10.1145/3355088.3365149(17-20)Online publication date: 17-Nov-2019
https://dl.acm.org/doi/10.1145/3355088.3365149
Fascione LHanika JLeone MDroske MSchwarzhaupt JDavidovič TWeidlich AMeng J(2018)ManukaACM Transactions on Graphics10.1145/318216137:3(1-18)Online publication date: 7-Aug-2018
https://dl.acm.org/doi/10.1145/3182161
Burley BAdler DChiang MDriskill HHabel RKelly PKutz PLi YTeece D(2018)The Design and Evolution of Disney’s Hyperion RendererACM Transactions on Graphics10.1145/318215937:3(1-22)Online publication date: 27-Jul-2018
https://dl.acm.org/doi/10.1145/3182159
Kulla CConty AStein CGritz L(2018)Sony Pictures Imageworks ArnoldACM Transactions on Graphics10.1145/318049537:3(1-18)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1145/3180495
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents