{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T19:55:43Z","timestamp":1758398143845,"version":"3.44.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T00:00:00Z","timestamp":1723161600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Grant Agency of the Czech Technical University in Prague","award":["SGS22\/173\/OHK3\/3T\/13"],"award-info":[{"award-number":["SGS22\/173\/OHK3\/3T\/13"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Comput. Graph. Interact. Tech."],"published-print":{"date-parts":[[2024,8,9]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3675391","type":"journal-article","created":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T15:53:18Z","timestamp":1723218798000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["SAH-Optimized k-DOP Hierarchies for Ray Tracing"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5221-3513","authenticated-orcid":false,"given":"Martin","family":"K\u00e1\u010derik","sequence":"first","affiliation":[{"name":"Czech Technical University in Prague, Prague, Czechia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5818-934X","authenticated-orcid":false,"given":"Ji\u0159\u00ed","family":"Bittner","sequence":"additional","affiliation":[{"name":"Czech Technical University in Prague, Prague, Czechia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492045.2492056"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1572769.1572792"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00026-N"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543867"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/RT.2008.4634638"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2019627.2019641"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.70405"},{"volume-title":"Proceedings of the 16th Eurographics Symposium on Parallel Graphics and Visualization","author":"Fuetterling V.","key":"e_1_2_1_8_1","unstructured":"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."},{"key":"e_1_2_1_9_1","volume-title":"Retrieved","author":"Fukuda Komei","year":"2018","unstructured":"Komei Fukuda. 2018. cddlib. Retrieved January 21, 2024 from https:\/\/github.com\/cddlib\/cddlib"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.1987.276983"},{"volume-title":"Retrieved","year":"2021","key":"e_1_2_1_11_1","unstructured":"Google. 2021. RadixSort\/VK. Retrieved January 21, 2024 from https:\/\/fuchsia.googlesource.com\/fuchsia\/+\/refs\/heads\/main\/src\/graphics\/lib\/compute\/radix_sort\/"},{"volume-title":"Collision queries using oriented bounding boxes","author":"Gottschalk Stefan Aric","key":"e_1_2_1_12_1","unstructured":"Stefan Aric Gottschalk. 2000. Collision queries using oriented bounding boxes. The University of North Carolina at Chapel Hill."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/RT.2007.4342591"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492045.2492055"},{"key":"e_1_2_1_15_1","volume-title":"Henry Sowizral, and Karel Zikan.","author":"Klosowski James T","year":"1998","unstructured":"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."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings Winter School of Computer Graphics(WCSG '97)","author":"Kone\u010dn\u00fd Petr","year":"1997","unstructured":"Petr Kone\u010dn\u00fd and Karel Zikan. 1997. Lower bound of distance in 3d. Proceedings Winter School of Computer Graphics(WCSG '97) 3 (1997), 640--649."},{"key":"e_1_2_1_17_1","first-page":"1","article-title":"Fast computation of tight-fitting oriented bounding boxes","volume":"2","author":"Larsson Thomas","year":"2011","unstructured":"Thomas Larsson and Linus K\u00e4llberg. 2011. Fast computation of tight-fitting oriented bounding boxes. Game Engine Gems 2 (2011), 1.","journal-title":"Game Engine Gems"},{"key":"e_1_2_1_18_1","unstructured":"Morgan McGuire. 2017. Computer Graphics Archive. https:\/\/casual-effects.com\/data"},{"key":"e_1_2_1_19_1","volume-title":"Parallel locally-ordered clustering for bounding","author":"Meister Daniel","year":"2017","unstructured":"Daniel Meister and Ji\u0159\u00ed Bittner. 2017. Parallel locally-ordered clustering for bounding volume hierarchy construction. IEEE transactions on visualization and computer graphics 24, 3 (2017), 1345--1353."},{"volume-title":"A survey on bounding","author":"Meister Daniel","key":"e_1_2_1_20_1","unstructured":"Daniel Meister, Shinji Ogaki, Carsten Benthin, Michael J Doyle, Michael Guthe, and Ji\u0159\u00ed Bittner. 2021. A survey on bounding volume hierarchies for ray tracing. In Computer Graphics Forum, Vol. 40. Wiley Online Library, 683--712."},{"key":"e_1_2_1_21_1","volume-title":"The double description method. Contributions to the Theory of Games 2, 28","author":"Motzkin Theodore S","year":"1953","unstructured":"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."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00991005"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2023.08.028"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14758"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406179"},{"key":"e_1_2_1_26_1","volume-title":"Retrieved","author":"Wang Zhepei","year":"2020","unstructured":"Zhepei Wang. 2020. VertexEnumeration3D. Retrieved January 21, 2024 from https:\/\/github.com\/ZJU-FAST-Lab\/VertexEnumeration3D"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/VRAIS.1998.658428"}],"container-title":["Proceedings of the ACM on Computer Graphics and Interactive Techniques"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3675391","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3675391","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T02:11:28Z","timestamp":1755915088000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3675391"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,9]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,8,9]]}},"alternative-id":["10.1145\/3675391"],"URL":"https:\/\/doi.org\/10.1145\/3675391","relation":{},"ISSN":["2577-6193"],"issn-type":[{"type":"electronic","value":"2577-6193"}],"subject":[],"published":{"date-parts":[[2024,8,9]]},"assertion":[{"value":"2024-08-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}