Top

Journal of Visualization

Published in:

12-05-2022 | Regular Paper

Compact tetrahedralization-based acceleration structures for ray tracing

Authors: Aytek Aman, Serkan Demirci, Uğur Güdükbay

Published in: Journal of Visualization | Issue 5/2022

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We propose compact and efficient tetrahedral mesh representations to improve the ray-tracing performance. We reorder tetrahedral mesh data using a space-filling curve to improve cache locality. Most importantly, we propose efficient ray-traversal algorithms. We provide details of the regular ray-tracing operations on tetrahedral meshes and the GPU implementation of our traversal method. We demonstrate our findings through a set of comprehensive experiments. Our method outperforms existing tetrahedral mesh-based traversal methods and yields comparable results to the traversal methods based on the state-of-the-art acceleration structures such as k-dimensional (k-d) tree and Bounding Volume Hierarchy (BVH) in terms of speed. Storage-wise, our method uses less memory than its tetrahedral mesh-based counterparts, thus allowing larger scenes to be rendered on the GPU.

Graphic Abstract

previous article Visual analysis of eye movements during micro-stories reading

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Aman A, Demirci S, Güdükbay U, Wald I (2021) Multi-level tetrahedralization-based accelerator for ray-tracing animated scenes. Comput Anim Virtual World 32(3–4):e2024

Berk H, Aykanat C, Gudukbay U (2003) Direct volume rendering of unstructured grids. Comp & Graph 27:387–406CrossRef

Bowyer A (1981) Computing dirichlet tessellations. Comput J 24(2):162–166MathSciNetCrossRef

Duff T, Burgess J, Christensen P, Hery C, Kensler A, Liani M, Villemin R (2017) Building an orthonormal basis, revisited. J Comp Graph Tech 6(1):1–8

Edelsbrunner H, Shah NR (1992) Incremental topological flipping works for regular triangulations. In: Proc. Eighth Ann. Symp. Comp. Geom., ACM, New York, NY, USA, SCG ’92, pp 43–52

Fellegara R, Floriani LD, Magillo P, Weiss K (2020) Tetrahedral trees: A family of hierarchical spatial indexes for tetrahedral meshes. ACM Trans Spat Algo Syst 6(4):23, 34 p

Fujimoto A, Tanaka T, Iwata K (1988) ARTS: accelerated ray-tracing system. In: Joy KI, Grant CW, Max NL, Hatfield L (eds) Tutorial: Computer Graphics. Image Synthesis, Computer Science Press Inc, New York, NY, USA, pp 148–159

Garrity MP (1990) Raytracing irregular volume data. In Proc. Eighth Joint Eurographics/IEEE VGTC Conf. Vis., ACM, New York, NY, USA, VVS ’90, pp 35–40

Garth C, Joy KI (2010) Fast, memory-efficient cell location in unstructured grids for visualization. IEEE Trans Vis Comput Graph 16(6):1541–1550CrossRef

Glassner AS (1984) Space subdivision for fast ray tracing. IEEE Comp Graph App 4(10):15–24CrossRef

Goldsmith J, Salmon J (1987) Automatic creation of object hierarchies for ray tracing. IEEE Comp Graph App 7(5):14–20CrossRef

Gunther J, Popov S, Seidel HP, Slusallek P (2007) Realtime ray tracing on GPU with BVH-based packet traversal. In Proc. IEEE Symp. Interactive Ray Tracing, IEEE Computer Society, Washington, DC, USA, RT ’07, pp 113–118

Haines E, Greenberg D (1986) The light buffer: a shadow-testing accelerator. IEEE Comp Graph App 6(9):6–16CrossRef

Havran V, Bittner J (2002) On improving kd tree for ray shooting. J WSCG 10:209–216

Hu Y, Zhou Q, Gao X, Jacobson A, Zorin D, Panozzo D (2018) Tetrahedral meshing in the wild. ACM Trans Graph 37(4):60

Hu Y, Schneider T, Gao X, Zhou Q, Jacobson A, Zorin D, Panozzo D (2019) TriWild: Robust triangulation with curve constraints. ACM Trans Graph 38(4):52CrossRef

Hunt W, Mark W (2008) Adaptive acceleration structures in perspective space. In: Proc. IEEE Symp. Interactive Ray Tracing, RT ’08, pp 11–17

Koyamada K (1992) Fast traverse of irregular volumes. In: Kunii TL (ed) Vis Comput. Springer Japan, Tokyo, pp 295–311CrossRef

Lagae A, Dutré P (2008) Accelerating ray tracing using constrained tetrahedralizations. Comp Graph Forum 27(4):1303–1312CrossRef

Lagae A, Dutré P (2008) Compact, fast and robust grids for ray tracing. Comput Graph Forum 27(4):1235–1244CrossRef

MacDonald DJ, Booth KS (1990) Heuristics for ray tracing using space subdivision. Vis Comput 6(3):153–166CrossRef

Maria M, Horna S, Aveneau L (2014) Topological space partition for fast ray tracing in architectural models. In: Proc. Int. Conf. Comp. Graph. Theory App., GRAPP ’14, pp 1–11

Maria M, Horna S, Aveneau L (2017) Constrained convex space partition for ray tracing in architectural environments. Comput Graph Forum 36(1):288–300CrossRef

Maria M, Horna S, Aveneau L (2017b) Efficient ray traversal of constrained Delaunay tetrahedralization. In: Proc. Int. Joint Conf. Comp. Vis., Imag. Comp. Graph. Theory Appl., VISIGRAPP ’17, vol 1, pp 236–243

Marmitt G, Slusallek P (2006) Fast ray traversal of tetrahedral and hexahedral meshes for direct volume rendering. In: Proc. Eighth Joint Eurographics/IEEE VGTC Conf. Vis., Eurographics Assoc., Aire-la-Ville, Switzerland, EUROVIS ’06, pp 235–242

Maximo A, Ribeiro S, Bentes C, Oliveira A, Farias R (2008) Memory efficient GPU-based ray casting for unstructured volume rendering. In: Proc. Fifth Eurographics / IEEE VGTC Symp. Point-Based Graphics, Eurographics Assoc., Goslar, DEU, SPBG’08, pp 155–162

Mebarki A (2018) XOR-based compact triangulations. Comp & Inform 37:367–384CrossRef

Miller GL, Talmor D, Teng SH, Walkington N, Wang H (1996) Control volume meshes using sphere packing: Generation, refinement and coarsening. In: Proc. 5th Int. Meshing Roundtable, pp 47–61

Pharr M, Jakob W, Humphreys G (2016) Physically based rendering: from theory to implementation, 3rd edn. Morgan Kaufmann Publishers Inc, San Francisco, CA, USA

Platis N, Theoharis T (2003) Fast ray-tetrahedron intersection using Plücker coordinates. J Graph Tool 8(4):37–48CrossRef

Ribeiro S, Maximo A, Bentes C, Oliveira A, Farias R (2007) Memory-aware and efficient ray-casting algorithm. In: Proc. XX Brazilian Symp. Comp. Graph. Img. Process., SIBGRAPI ’07, pp 147–154

Sahistan A, Demirci S, Morrical N, Zellmann S, Aman A, Wald I, Güdükbay U (2021) Ray-traced shell traversal of tetrahedral meshes for direct volume visualization. In: Proc. IEEE Vis. Conf.-Short Papers, VIS ’21, pp 91–95

Shewchuk JR (1996) Adaptive precision floating-point arithmetic and fast robust geometric predicates. Disc & Comp Geom 18:305–363MathSciNetCrossRef

Si H (2015) TetGen, a Delaunay-based quality tetrahedral mesh generator. ACM Trans Math Soft 41(2):11, 36 pMathSciNetCrossRef

Silva CT, Mitchell JSB (1997) The lazy sweep ray casting algorithm for rendering irregular grids. IEEE Trans Vis Comp Graph 3(2):142–157CrossRef

Silva CT, Mitchell JSB, Kaufman AE (1996) Fast rendering of irregular grids, Proc. Symp. Vol. Vis., VIS '96, 1996, pp. 15–22

Sinha P (2004) A memory-efficient doubly linked list. Linux J, Available at https://www.linuxjournal.com/article/6828. Accessed 5 May 2022

Stich M, Friedrich H, Dietrich A (2009) Spatial Splits in Bounding Volume Hierarchies. In: Proc. Conf. High Perf. Graph., ACM, New York, NY, USA, HPG ’09, pp 7–13

Wald I (2007) On fast construction of SAH-based bounding volume hierarchies. In: Proc. IEEE Symp. Interactive Ray Tracing, IEEE Computer Society, Washington, DC, USA, RT ’07, pp 33–40

Wald I, Havran V (2006) On building fast kd-trees for ray tracing, and on doing that in O(N log N). In: Proc. IEEE Symp. Interactive Ray Tracing, IEEE Computer Society, Washington, DC, USA, RT '06, pp 61–69

Watson DF (1981) Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. Comput J 24(2):167–172MathSciNetCrossRef

Wodniok D, Goesele M (2017) Construction of bounding volume hierarchies with SAH cost approximation on temporary subtrees. Comp & Graph 62:41–52CrossRef

Title: Compact tetrahedralization-based acceleration structures for ray tracing
Authors: Aytek Aman
Serkan Demirci
Uğur Güdükbay
Publication date: 12-05-2022
Publisher: Springer Berlin Heidelberg
Published in: Journal of Visualization / Issue 5/2022
Print ISSN: 1343-8875
Electronic ISSN: 1875-8975
DOI: https://doi.org/10.1007/s12650-022-00842-x

Springer Professional

Abstract

Graphic Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 5/2022

Monte Carlo-based a posteriori uncertainty quantification for background-oriented schlieren measurements

Application of computational fluid dynamics for the analysis of postoperative airway changes in oral cancer patients

Sediment movement over a triangular weir with an upstream ramp using a high-speed camera

Identification of wake vortices in a simplified car model during significant aerodynamic drag increase under crosswind conditions

Instability phenomena of lean hydrogen/oxygen/inert-gas premixed flames on a flat burner

Visual analysis of eye movements during micro-stories reading

Premium Partner