GPU ray tracing speeds up 3D mesh spatial joins by hundredfold
Pierce: GPU Ray Tracing for Spatial Joins over Complex 3D Data
Databases
Summary
Checking how two 3D shapes touch or overlap can be very slow when the shapes have many tiny flat parts. The authors changed this problem into one of tracing virtual rays to quickly find intersections using special GPU hardware built for ray tracing in graphics. This method speeds up the task by over 100 times on some data. It helps connect or compare complex 3D models faster than before.
What this means in practice
- •For urban planning teams: Run fast spatial analyses on 3D city models to detect where buildings or infrastructures intersect or overlap.
- •For computational biology researchers: Quickly identify intersections between complex biological 3D structures to support modeling and simulation workflows.
Authors
Anton Hackl, Eleni Tzirita Zacharatou
Abstract
Many emerging applications, from computational biology to digital twins and urban planning, rely heavily on three-dimensional spatial joins over polyhedral meshes. These joins comprise computationally-intensive triangle--triangle intersection tests that pairwise compare the faces of polyhedral meshes. Since each mesh may contain thousands of faces, the resulting cost challenges the responsiveness of spatial data management techniques. Existing techniques follow the filter-and-refine paradigm, accelerating either the filtering step through indexing or the refinement step through progressive mesh compression combined with GPU parallelization of triangle--triangle tests. However, the former neglects the high cost of intra-geometry refinements, whereas the latter lowers this cost but still relies on the same pairwise triangle--triangle tests. In this paper, we introduce Pierce, an approach that reformulates three-dimensional spatial joins over complex polyhedral meshes as ray-tracing operations and leverages the hardware ray-tracing units (RT cores) of modern GPUs to accelerate query execution. Our approach casts rays along the edges of one mesh against a spatial hierarchy built over the other, performing ray--node tests at the internal levels to prune distant geometries and ray--triangle tests at the leaves to identify intersecting meshes, both of which RT cores accelerate in hardware. We evaluated Pierce on real and synthetic data against multiple baselines, demonstrating more than two orders of magnitude speedup on digital pathology data compared to the state-of-the-art approach.