{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T16:00:48Z","timestamp":1774540848141,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"10-12","license":[{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005714","name":"Technische Universit\u00e4t Darmstadt","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005714","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Vis Comput"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a novel bounding volume hierarchy for GPU-accelerated direct volume rendering (DVR) as well as volumetric mesh slicing and inside-outside intersection testing. Our novel octree-based data structure is laid out linearly in memory using space filling Morton curves. As our new data structure results in tightly fitting bounding volumes, boundary markers can be associated with nodes in the hierarchy. These markers can be used to speed up all three use cases that we examine. In addition, our data structure is memory-efficient, reducing memory consumption by up to 75%. Tree depth and memory consumption can be controlled using a parameterized heuristic during construction. This allows for significantly shorter construction times compared to the state of the art. For GPU-accelerated DVR, we achieve performance gain of 8.4<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\times $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mo>\u00d7<\/mml:mo>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u201313<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\times $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mo>\u00d7<\/mml:mo>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For 3D printing, we present an efficient conservative slicing method that results in a 3<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\times $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mo>\u00d7<\/mml:mo>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u201325<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\times $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mo>\u00d7<\/mml:mo>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> speedup when using our data structure. Furthermore, we improve volumetric mesh intersection testing speed by 5<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\times $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mo>\u00d7<\/mml:mo>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u201352<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\times $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mo>\u00d7<\/mml:mo>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00371-020-01886-6","type":"journal-article","created":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T07:02:25Z","timestamp":1594018945000},"page":"2327-2340","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["OLBVH: octree linear bounding volume hierarchy for volumetric meshes"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2672-7377","authenticated-orcid":false,"given":"Daniel","family":"Str\u00f6ter","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0712-0457","authenticated-orcid":false,"given":"Johannes S.","family":"Mueller-Roemer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Stork","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7756-0901","authenticated-orcid":false,"given":"Dieter W.","family":"Fellner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,6]]},"reference":[{"issue":"3","key":"1886_CR1","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1145\/1073204.1073238","volume":"24","author":"P Alliez","year":"2005","unstructured":"Alliez, P., Cohen-Steiner, D., Yvinec, M., Desbrun, M.: Variational tetrahedral meshing. ACM Trans. Graph. 24(3), 617 (2005). https:\/\/doi.org\/10.1145\/1073204.1073238","journal-title":"ACM Trans. Graph."},{"key":"1886_CR2","unstructured":"Altenhofen, C., Luu, T.H., Grasser, T., Dennst\u00e4dt, M., Mueller-Roemer, J.S., Weber, D., Stork, A.: Continuous property gradation for multi-material 3D-printed objects. In: Proceedings of the 29th Annual International Solid Freeform Fabrication Symposium\u2014An Additive Manufacturing Conference, SFF \u201918, pp. 1675\u20131685 (2018)"},{"key":"1886_CR3","doi-asserted-by":"publisher","unstructured":"Apetrei, C.: Fast and simple agglomerative LBVH construction. In: Computer Graphics and Visual Computing (CGVC), pp. 41\u201344 (2014). https:\/\/doi.org\/10.2312\/cgvc.20141206","DOI":"10.2312\/cgvc.20141206"},{"key":"1886_CR4","unstructured":"Bell, N., Hoberock, J.: Thrust 1.8.1 (2015). https:\/\/thrust.github.io\/"},{"key":"1886_CR5","doi-asserted-by":"publisher","DOI":"10.2312\/hpg.20161191","volume-title":"Eurographics\/ACM SIGGRAPH Symposium on High Performance Graphics","author":"N Binder","year":"2016","unstructured":"Binder, N., Keller, A.: Efficient stackless hierarchy traversal on GPUs with backtracking in constant time. In: Assarsson, U., Hunt, W. (eds.) Eurographics\/ACM SIGGRAPH Symposium on High Performance Graphics. The Eurographics Association, Aire-la-Ville (2016). https:\/\/doi.org\/10.2312\/hpg.20161191"},{"key":"1886_CR6","volume-title":"Delaunay Mesh Generation","author":"SW Cheng","year":"2012","unstructured":"Cheng, S.W., Dey, T.K., Shewchuk, J.: Delaunay Mesh Generation. CRC Press, Boca Raton (2012)"},{"issue":"1","key":"1886_CR7","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1109\/tmscs.2017.2695338","volume":"4","author":"MJ Doyle","year":"2017","unstructured":"Doyle, M.J., Tuohy, C., Manzke, M.: Evaluation of a BVH construction accelerator architecture for high-quality visualization. IEEE Trans. Multi Scale Comput. Syst. 4(1), 83\u201394 (2017). https:\/\/doi.org\/10.1109\/tmscs.2017.2695338","journal-title":"IEEE Trans. Multi Scale Comput. Syst."},{"key":"1886_CR8","doi-asserted-by":"publisher","unstructured":"Garanzha, K., Pantaleoni, J., McAllister, D.: Simpler and faster HLBVH with work queues. In: Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics, HPG \u201911, pp. 59\u201364 (2011). https:\/\/doi.org\/10.1145\/2018323.2018333","DOI":"10.1145\/2018323.2018333"},{"key":"1886_CR9","doi-asserted-by":"publisher","unstructured":"Garc\u00eda, A., Murguia, S., Olivares, U., Ramos, F.F.: Fast parallel construction of stack-less complete LBVH trees with efficient bit-trail traversal for ray tracing. In: Proceedings of the 13th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and its Applications in Industry, pp. 151\u2013158. ACM (2014). https:\/\/doi.org\/10.1145\/2670473.2670488","DOI":"10.1145\/2670473.2670488"},{"key":"1886_CR10","doi-asserted-by":"publisher","unstructured":"Gu, F., Jendersie, J., Grosch, T.: Fast and dynamic construction of bounding volume hierarchies based on loose octrees. In: Vision, Modeling and Visualization (2018). https:\/\/doi.org\/10.2312\/vmv.20181257","DOI":"10.2312\/vmv.20181257"},{"key":"1886_CR11","doi-asserted-by":"publisher","unstructured":"Karras, T.: Maximizing parallelism in the construction of BVHs, octrees, and $$k$$-d trees. In: Proceedings of the Fourth ACM SIGGRAPH\/Eurographics conference on High-Performance Graphics, HPG \u201912, pp. 33\u201337 (2012). https:\/\/doi.org\/10.2312\/EGGH\/HPG12\/033-037","DOI":"10.2312\/EGGH\/HPG12\/033-037"},{"issue":"2","key":"1886_CR12","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1111\/j.1467-8659.2009.01377.x","volume":"28","author":"C Lauterbach","year":"2009","unstructured":"Lauterbach, C., Garland, M., Sengupta, S., Luebke, D., Manocha, D.: Fast BVH construction on GPUs. Comput. Graph. Forum 28(2), 375\u2013384 (2009). https:\/\/doi.org\/10.1111\/j.1467-8659.2009.01377.x","journal-title":"Comput. Graph. Forum"},{"key":"1886_CR13","unstructured":"Merill, D.: CUB 1.8.0 (2018). https:\/\/nvlabs.github.io\/cub\/"},{"key":"1886_CR14","doi-asserted-by":"publisher","unstructured":"Morrical, N., Usher, W., Wald, I., Pascucci, V.: Efficient space skipping and adaptive sampling of unstructured volumes using hardware accelerated ray tracing. In: IEEE Visualization Conference (VIS) (2019). https:\/\/doi.org\/10.1109\/visual.2019.8933539","DOI":"10.1109\/visual.2019.8933539"},{"key":"1886_CR15","unstructured":"Morton, G.M.: A computer oriented geodetic data base; and a new technique in file sequencing. IBM Corporation (1966)"},{"issue":"5","key":"1886_CR16","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1111\/cgf.13245","volume":"36","author":"JS Mueller-Roemer","year":"2017","unstructured":"Mueller-Roemer, J.S., Altenhofen, C., Stork, A.: Ternary sparse matrix representation for volumetric mesh subdivision and processing on GPUs. Comput. Graph. Forum 36(5), 59\u201369 (2017). https:\/\/doi.org\/10.1111\/cgf.13245","journal-title":"Comput. Graph. Forum"},{"issue":"7","key":"1886_CR17","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1111\/cgf.13581","volume":"37","author":"JS Mueller-Roemer","year":"2018","unstructured":"Mueller-Roemer, J.S., Stork, A.: GPU-based polynomial finite element matrix assembly for simplex meshes. Comput. Graph. Forum 37(7), 443\u2013454 (2018). https:\/\/doi.org\/10.1111\/cgf.13581","journal-title":"Comput. Graph. Forum"},{"key":"1886_CR18","unstructured":"Murguia, S., Avila, F., Reyes, L., Garcia, A.: GPU Pro 4: Advanced Rendering Techniques, chap. Bit-trail traversal for stackless LBVH on DirectCompute, pp. 319\u2013336. CRC Press (2013)"},{"key":"1886_CR19","unstructured":"NVIDIA: NVIDIA OptiX Ray Tracing Engine (2020). https:\/\/developer.nvidia.com\/optix"},{"key":"1886_CR20","unstructured":"Pantaleoni, J., Luebke, D.: HLBVH: Hierarchical LBVH construction for real-time ray tracing of dynamic geometry. In: Proceedings of the Conference on High Performance Graphics, HPG \u201910, pp. 87\u201395 (2010)"},{"key":"1886_CR21","unstructured":"Stich, M.: Introduction to NVIDIA RTX and DirectX ray tracing (2018). https:\/\/devblogs.nvidia.com\/introduction-nvidia-rtx-directx-ray-tracing\/"},{"key":"1886_CR22","doi-asserted-by":"publisher","unstructured":"Vaidyanathan, K., Woop, S., Benthin, C.: Wide BVH traversal with a short stack. In: Proceedings of the Conference on High-Performance Graphics (2019). https:\/\/doi.org\/10.2312\/hpg.20191190","DOI":"10.2312\/hpg.20191190"},{"issue":"5","key":"1886_CR23","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1145\/3132702","volume":"36","author":"T Viitanen","year":"2017","unstructured":"Viitanen, T., Koskela, M., J\u00e4\u00e4skel\u00e4inen, P., Kultala, H., Takala, J.: MergeTree: a fast hardware HLBVH constructor for animated ray tracing. ACM Trans. Graph. 36(5), 169 (2017). https:\/\/doi.org\/10.1145\/3132702","journal-title":"ACM Trans. Graph."},{"issue":"2","key":"1886_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3233309","volume":"1","author":"T Viitanen","year":"2018","unstructured":"Viitanen, T., Koskela, M., J\u00e4\u00e4skel\u00e4inen, P., Tervo, A., Takala, J.: PLOCTree. Proc. ACM Comput. Graph. Interact. Tech. 1(2), 1\u201319 (2018). https:\/\/doi.org\/10.1145\/3233309","journal-title":"Proc. ACM Comput. Graph. Interact. Tech."},{"key":"1886_CR25","doi-asserted-by":"publisher","unstructured":"Vinkler, M., Bittner, J., Havran, V.: Extended Morton codes for high performance bounding volume hierarchy construction. In: Proceedings of High Performance Graphics, HPG \u201917, pp. 9:1\u20139:8 (2017). https:\/\/doi.org\/10.1145\/3105762.3105782","DOI":"10.1145\/3105762.3105782"},{"issue":"6","key":"1886_CR26","doi-asserted-by":"publisher","first-page":"1727","DOI":"10.1109\/tvcg.2007.70566","volume":"13","author":"I Wald","year":"2007","unstructured":"Wald, I., Friedrich, H., Knoll, A., Hansen, C.D.: Interactive isosurface ray tracing of time-varying tetrahedral volumes. IEEE Trans. Vis. Comput. Graph. 13(6), 1727\u20131734 (2007). https:\/\/doi.org\/10.1109\/tvcg.2007.70566","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"1886_CR27","doi-asserted-by":"publisher","DOI":"10.2312\/hpg.20191189","author":"I Wald","year":"2019","unstructured":"Wald, I., Usher, W., Morrical, N., Lediaev, L., Pascucci, V.: RTX beyond ray tracing: exploring the use of hardware ray tracing cores for tet-mesh point location. High Perform. Graph. Short Papers (2019). https:\/\/doi.org\/10.2312\/hpg.20191189","journal-title":"High Perform. Graph. Short Papers"},{"key":"1886_CR28","doi-asserted-by":"publisher","unstructured":"Zellmannn, S., Hellmann, M., Lang, U.: A linear time BVH construction algorithm for sparse volumes. In: 2019 IEEE Pacific Visualization Symposium (PacificVis), pp. 222\u2013226 (2019). https:\/\/doi.org\/10.1109\/pacificvis.2019.00033","DOI":"10.1109\/pacificvis.2019.00033"},{"issue":"5","key":"1886_CR29","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1109\/TVCG.2010.75","volume":"17","author":"K Zhou","year":"2011","unstructured":"Zhou, K., Gong, M., Huang, X., Guo, B.: Data-parallel octrees for surface reconstruction. IEEE Trans. Vis. Comput. Graph. 17(5), 669\u2013681 (2011). https:\/\/doi.org\/10.1109\/TVCG.2010.75","journal-title":"IEEE Trans. Vis. Comput. Graph."}],"container-title":["The Visual Computer"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00371-020-01886-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00371-020-01886-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00371-020-01886-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,5]],"date-time":"2021-07-05T23:36:36Z","timestamp":1625528196000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00371-020-01886-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,6]]},"references-count":29,"journal-issue":{"issue":"10-12","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["1886"],"URL":"https:\/\/doi.org\/10.1007\/s00371-020-01886-6","relation":{},"ISSN":["0178-2789","1432-2315"],"issn-type":[{"value":"0178-2789","type":"print"},{"value":"1432-2315","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,6]]},"assertion":[{"value":"6 July 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}