SAH-Optimized k-DOP Hierarchies for Ray Tracing
Article No.: 32, Pages 1 - 16
Abstract
We revisit the idea of using hierarchies of k-sided discrete orientation polytopes (k-DOPs) for ray tracing. We propose a method for building a k-DOP-based bounding volume hierarchy while optimizing its topology using the surface area heuristic. The key component of our method is a fast and exact algorithm for evaluating the surface area of a 14-DOP combined with the parallel locally ordered clustering algorithm (PLOC). Our k-DOP PLOC builder has about 40% longer build times than AABB PLOC, but for scenes with oblong slanted objects, the resulting BVH provides up to 2.5x ray tracing speedup over AABB BVH. We also show that k-DOPs can be used in combination with other techniques, such as oriented bounding boxes (OBBs). Transforming k-DOP BVH into OBB BVH is straightforward and provides up to 12% better trace times than the transformation from AABB to OBB BVH.
References
[1]
Timo Aila, Tero Karras, and Samuli Laine. 2013. On Quality Metrics of Bounding Volume Hierarchies. In Proceedings of the 5th High-Performance Graphics Conference (Anaheim, California) (HPG '13). Association for Computing Machinery, New York, NY, USA, 101--107. https://doi.org/10.1145/2492045.2492056
[2]
Timo Aila and Samuli Laine. 2009. Understanding the Efficiency of Ray Traversal on GPUs. In Proceedings of the Conference on High Performance Graphics 2009 (New Orleans, Louisiana) (HPG '09). Association for Computing Machinery, New York, NY, USA, 145--149. https://doi.org/10.1145/1572769.1572792
[3]
David Avis and Komei Fukuda. 1996. Reverse search for enumeration. Discrete Applied Mathematics 65, 1 (1996), 21--46. https://doi.org/10.1016/0166-218X(95)00026-N First International Colloquium on Graphs and Optimization.
[4]
Carsten Benthin, Radoslaw Drabinski, Lorenzo Tessari, and Addis Dittebrandt. 2022. PLOC++: Parallel Locally-Ordered Clustering for Bounding Volume Hierarchy Construction Revisited. Proc. ACM Comput. Graph. Interact. Tech. 5, 3, Article 31 (jul 2022), 13 pages. https://doi.org/10.1145/3543867
[5]
Brian C Budge, Daniel Coming, Derek Norpchen, and Kenneth I Joy. 2008. Accelerated building and ray tracing of restricted BSP trees. In 2008 IEEE Symposium on Interactive Ray Tracing. IEEE, 167--174.
[6]
Chia-Tche Chang, Bastien Gorissen, and Samuel Melchior. 2011. Fast oriented bounding box optimization on the rotation group SO (3, R). ACM Transactions on Graphics (TOG) 30, 5 (2011), 1--16.
[7]
Daniel S. Coming and Oliver G. Staadt. 2008. Velocity-Aligned Discrete Oriented Polytopes for Dynamic Collision Detection. IEEE Transactions on Visualization and Computer Graphics 14, 1 (2008), 1--12. https://doi.org/10.1109/TVCG.2007.70405
[8]
V. Fuetterling, C. Lojewski, F.-J. Pfreundt, and A. Ebert. 2016. Parallel spatial splits in bounding volume hierarchies. In Proceedings of the 16th Eurographics Symposium on Parallel Graphics and Visualization (Groningen, The Netherlands) (EGPGV '16). Eurographics Association, Goslar, DEU, 21--30.
[9]
Komei Fukuda. 2018. cddlib. Retrieved January 21, 2024 from https://github.com/cddlib/cddlib
[10]
Jeffrey Goldsmith and John Salmon. 1987. Automatic Creation of Object Hierarchies for Ray Tracing. IEEE Computer Graphics and Applications 7, 5 (May 1987), 14--20. https://doi.org/10.1109/MCG.1987.276983
[11]
Google. 2021. RadixSort/VK. Retrieved January 21, 2024 from https://fuchsia.googlesource.com/fuchsia/+/refs/heads/main/src/graphics/lib/compute/radix_sort/
[12]
Stefan Aric Gottschalk. 2000. Collision queries using oriented bounding boxes. The University of North Carolina at Chapel Hill.
[13]
Ravi P Kammaje and Benjamin Mora. 2007. A study of restricted BSP trees for ray tracing. In 2007 IEEE Symposium on interactive ray tracing. IEEE, 55--62.
[14]
Tero Karras and Timo Aila. 2013. Fast parallel construction of high-quality bounding volume hierarchies (HPG '13). Association for Computing Machinery, New York, NY, USA, 89--99. https://doi.org/10.1145/2492045.2492055
[15]
James T Klosowski, Martin Held, Joseph SB Mitchell, Henry Sowizral, and Karel Zikan. 1998. Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE transactions on Visualization and Computer Graphics 4, 1 (1998), 21--36.
[16]
Petr Konečný and Karel Zikan. 1997. Lower bound of distance in 3d. Proceedings Winter School of Computer Graphics(WCSG '97) 3 (1997), 640--649.
[17]
Thomas Larsson and Linus Källberg. 2011. Fast computation of tight-fitting oriented bounding boxes. Game Engine Gems 2 (2011), 1.
[18]
Morgan McGuire. 2017. Computer Graphics Archive. https://casual-effects.com/data
[19]
Daniel Meister and Jiří Bittner. 2017. Parallel locally-ordered clustering for bounding volume hierarchy construction. IEEE transactions on visualization and computer graphics 24, 3 (2017), 1345--1353.
[20]
Daniel Meister, Shinji Ogaki, Carsten Benthin, Michael J Doyle, Michael Guthe, and Jiří Bittner. 2021. A survey on bounding volume hierarchies for ray tracing. In Computer Graphics Forum, Vol. 40. Wiley Online Library, 683--712.
[21]
Theodore S Motzkin, Howard Raiffa, Gerald L Thompson, and Robert M Thrall. 1953. The double description method. Contributions to the Theory of Games 2, 28 (1953), 51--73.
[22]
Joseph O'Rourke. 1985. Finding minimal enclosing boxes. International journal of computer & information sciences 14 (1985), 183--199.
[23]
Rodolfo Sabino, Creto Augusto Vidal, Joaquim Bento Cavalcante-Neto, and José Gilvan Rodrigues Maia. 2023. Building Oriented Bounding Boxes by the intermediate use of ODOPs. Computers & Graphics 116 (2023), 251--261. https://doi.org/10.1016/j.cag.2023.08.028
[24]
Nick Vitsas, Iordanis Evangelou, Georgios Papaioannou, and Anastasios Gkaravelis. 2023. Parallel Transformation of Bounding Volume Hierarchies into Oriented Bounding Box Trees. Computer Graphics Forum 42, 2 (2023), 245--25410 pages. https://doi.org/10.1111/cgf.14758
[25]
Ingo Wald, Nate Morrical, Stefan Zellmann, Lei Ma, Will Usher, Tiejun Huang, and Valerio Pascucci. 2020. Using Hardware Ray Transforms to Accelerate Ray/Primitive Intersections for Long, Thin Primitive Types. Proc. ACM Comput. Graph. Interact. Tech. 3, 2, Article 17 (aug 2020), 16 pages. https://doi.org/10.1145/3406179
[26]
Zhepei Wang. 2020. VertexEnumeration3D. Retrieved January 21, 2024 from https://github.com/ZJU-FAST-Lab/VertexEnumeration3D
[27]
Gabriel Zachmann. 1998. Rapid collision detection by dynamically aligned DOP-trees. In Proceedings. IEEE 1998 Virtual Reality Annual International Symposium (Cat. No.98CB36180). 90--97. https://doi.org/10.1109/VRAIS.1998.658428
Index Terms
- SAH-Optimized k-DOP Hierarchies for Ray Tracing
Recommendations
GPU Ray Tracing Based on Reduced Bounding Volume Hierarchies
CGIV '12: Proceedings of the 2012 Ninth International Conference on Computer Graphics, Imaging and VisualizationWe 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 ...
Ray tracing-based interactive diffuse indirect illumination
Despite great efforts in recent years to accelerate global illumination computation, the real-time ray tracing of fully dynamic scenes to support photorealistic indirect illumination effects has yet to be achieved in computer graphics. In this paper, we ...
Ray Specialized Contraction on Bounding Volume Hierarchies
In this paper we propose a simple but effective method to modify a BVH based on ray distribution for improved ray tracing performance. Our method starts with an initial BVH generated by any state-of-the-art offline algorithm. Then by traversing a small ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2024 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].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 09 August 2024
Published in PACMCGIT Volume 7, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Funding Sources
- Grant Agency of the Czech Technical University in Prague
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 303Total Downloads
- Downloads (Last 12 months)303
- Downloads (Last 6 weeks)92
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in