CS Paper Radar

Pierce: GPU Ray Tracing for Spatial Joins over Complex 3D Data

Anton Hackl, Eleni Tzirita Zacharatou

cs.DB ·submitted 2026-09-21 12:52 UTC · v1
published

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.

Comment
Accepted at ACM SIGSPATIAL 2026
DOI
10.1145/3841645.3844195

Closest papers

Nearest neighbours by meaning across the whole index.

Delaunay-Based Nearest Neighbor Search with Grid-Accelerated Queries and Parallel Construction

cs.GR cs.CG ·2026-11-11 ·Pengfei Wang, Shiqing Xin, Changhe Tu
similarity 0.68
Abstract

Nearest-neighbor search is a fundamental primitive in computer graphics, with applications in distance field computation, surface reconstruction, and point cloud registration. In many graphics applications, data points lie on a surface manifold embedded in 3D space, whereas queries are distributed throughout the surrounding volume, a setting in which spatial partitioning structures such as k-d trees and grids can become inefficient. Dynamic-programming-based nearest-neighbor search (DP-NNS) offers an alternative: it traverses a successor DAG that records the history of incremental Delaunay construction and often outperforms spatial partitioning structures. However, its sequential construction is slow, and naive parallelization degrades query performance, limiting its practical adoption. We accelerate both queries and construction in DP-NNS. For queries, we introduce a grid-based initialization strategy that precomputes valid starting points on the successor DAG, shortening search paths while preserving exactness and enabling a twofold speedup. For construction, we analyze how parallel insertion affects query cost and develop a parallel algorithm that preserves logarithmic expected query cost under stated geometric assumptions. Our parallel construction algorithm achieves a 10x speedup over the sequential baseline while maintaining nearly the same query cost. We further reorder query points to improve cache locality. Extensive experiments demonstrate that our method outperforms widely used libraries in nearest-neighbor query performance.

0.14

RT-HiSS: Ray Tracing Accelerated High Dimensional Vector Similarity Searches

cs.DC cs.DB ·2026-09-02 ·Revanth Reddy Munugala, Michael Gowanlock
publishedtheory similarity 0.67
Abstract · To appear in the Proceedings of the 2026 International Conference for High Performance Computing, Networking, Storage and Analysis (SC'26)

Recent GPU generations include special-purpose ray tracing (RT) cores for graphics applications. While RT cores are primarily used for rendering, recent works show they can be leveraged for general-purpose tasks, including similarity searches. However, existing approaches do not support datasets exceeding three dimensions. In this work, we propose RT-HiSS, the first exact GPU RT-core-based similarity search algorithm for high-dimensional datasets. GPU similarity search often scales poorly for large datasets with substantial search distances. To address this, RT-HiSS uses RT cores for fast index construction and searches, followed by candidate refinement on CUDA cores. We introduce a two-pass approach to estimate an upper bound on result size, enabling efficient batching under GPU memory constraints with near-perfect load balancing. Additionally, we examine shared memory tiling and compressed result masks to improve GPU resource utilization. RT-HiSS yields speedups up to 8.37$\times$ over competitive state-of-the-art GPU algorithms across six real-world datasets.

0.31

A Gaussian Primitive Data Management Framework for Efficient 3DGS Trajectory Rendering

cs.DB cs.CVcs.GR ·2026-11-16 ·Haolun Ma, Ziyi Liu, Zizhuo Xu, Chuhan Hu, Lei Li
similarity 0.63
Abstract

Trajectory rendering, which renders novel views of a reconstructed 3D scene along a camera path, is a core operation in digital twins and autonomous inspection. Structured 3D Gaussian Splatting (3DGS) renders a single view in real time by decoding sparse anchors into Gaussians on demand, but it renders a trajectory view by view: every view projects all anchors to select them, re-decodes anchors already requested by neighboring views, and runs all steps on the GPU while the CPU idles. We treat this as a spatial data management problem, where anchors are spatial objects, views are range queries, and decoded Gaussians are shared derived data, and propose GDM-GS, which removes redundancy at three levels. Within a view, an anchor index and an occluder index answer each view as a holed-frustum range query, so out-of-view and provably hidden anchors are never decoded. Across views, shared materialization decodes each requested anchor once per group of consecutive views while preserving each view's selection. Across processors, a hybrid pipeline balances selections between the CPU and the GPU before grouped decoding under bounded memory. Experiments on large-scale public scenes show that GDM-GS substantially reduces trajectory rendering latency while preserving image quality.

0.17

GPUMAP: GPU-Accelerated Progressive Uniform Manifold Approximation and Projection

cs.LG cs.GRcs.HC ·2026-11-04 ·Myeongwon Jung, Jaemin Jo
hot direction similarity 0.62
Abstract

Dimensionality reduction (DR) techniques are fundamental to the analysis of high-dimensional data, yet their substantial computational cost limits their use in interactive settings. To address this limitation, we present GPU-accelerated Progressive Uniform Manifold Approximation and Projection (GPUMAP), an efficient progressive DR algorithm designed for interactive use. We identify three atomic operations within UMAP and restructure them into a progressive pipeline. As part of this adaptation, we introduce modifications to UMAP, including operation queues, instance-wise local join, and scheduling strategies. We further accelerate computation by leveraging GPU parallelism, enabling interactive analysis of million-scale datasets on commodity GPU hardware. Finally, we employ our implementation to systematically study the behavior of progressive DR, investigating how projections evolve over time relative to the ground-truth projection and how biased data streams influence the quality and stability of the resulting projections.

0.26

GPU-Native Real-Time Textured Mesh Reconstruction with Seam-Aware Multi-View Radiometric Correction

cs.CV cs.GR ·2026-11-02 ·Hiroyuki Sato
published similarity 0.62
Abstract · Accepted to WACV 2027. 20 pages including appendix

We present a GPU-native volumetric-video system for real-time reconstruction of graphics-compatible textured triangle meshes from multiple RGB-D sensors. Existing TSDF systems accelerate fusion and mesh extraction, but extending them to per-frame textured meshing adds CPU mesh processing, CPU-side texturing work, or extra CPU-GPU transfers between stages. After input staging, our method keeps the reconstruction and texturing stages (TSDF fusion, Marching Cubes, connected-component noise removal, view-based texture mapping, inpainting, and radiometric seam correction) resident on the GPU; no intermediate mesh or image data returns to the host between these stages. A fixed-size-array representation of mesh topology gives constant-time neighbor access on the GPU and makes the downstream mesh-level operations data-parallel. Because we texture each face from a single camera, exposure seams that vary smoothly across each image remain; we estimate a per-camera low-frequency gain field and bake it into the atlas on the GPU. On the CMU Panoptic dataset, our method is faster than the baselines at every tested voxel resolution and number of sensors, achieves peak speedups of more than an order of magnitude over CUDA-accelerated nvblox and CPU-based Open3D, and approaches an offline textured-meshing baseline in perceptual re-rendering quality.

0.46

FROG: Efficient Range-Filtering Approximate Nearest Neighbor Search on GPUs

cs.DB cs.IR ·2026-08-17 ·Xiaokun Cui, Pengbo Liu, Jiadong Xie, Yingfan Liu, Hui Li +2 more
similarity 0.61
Abstract

Range-filtering approximate nearest neighbor search (RFANNS) is a fundamental operation in modern vector databases. Given a query vector $q$ and a numerical range predicate, RFANNS returns the $k$-approximate nearest neighbors ($k$-ANN) of the query $q$ among the objects whose attributes satisfy the range predicate. However, existing RFANNS methods are not well suited to high-throughput GPU execution. CPU indexes offer limited parallel scalability, generic GPU filtering is highly selectivity-dependent, and GPU indexes built from locally optimized subgraphs can incur long search trajectories and redundant distance computations. To address these limitations, we present FROG, a GPU-oriented RFANNS index that replaces multiple locally optimal substructure building with a globally aware, vertex-centric design. It organizes diverse expansion neighbor candidates for each vertex in a GPU-friendly structure and rapidly identifies the expansion neighbors used for computation at query time. Moreover, GPU-oriented algorithms and implementations are developed for both index construction and query processing. Experiments on six datasets show that FROG improves mixed-selectivity query throughput by 14.7--37.7$\times$ over 44-core CPU baselines and 4.5--7.6$\times$ over the strongest GPU baseline. It also accelerates index construction by 2.4--14.8$\times$ over the GPU baseline.

0.41

CuACD: A Fully GPU-Resident Approximate Convex Decomposition

cs.CG cs.GR ·2026-09-23 ·Ruoxi Shi, Xinyue Wei, Fanbo Xiang, Zexiang Xu, Hao Su
top venuebenchmarkcode/data similarity 0.61
Abstract

Approximate convex decomposition (ACD) converts triangle meshes into small sets of convex parts and is a standard preprocessing step for physics simulation, collision detection, and large-scale robot learning. The majority of modern ACD methods produce high-quality decompositions through an expensive search over candidate cutting planes, with per-mesh runtimes of tens of seconds that force game pipelines into overnight bakes and keep articulated-object datasets on CPU clusters for days. Prior work has accelerated isolated stages, most recently VisACD's GPU-based visibility metric, yet the dominant costs -- search, mesh cutting, and convex hull construction -- have remained on the CPU because their natural decomposition into many small homogeneous phases trails off in a fading last wave at every kernel boundary, and the variable-sized output of each phase forces a host round trip simply to allocate the next launch's input. We address these obstacles by adopting the warp, rather than the thread or thread block, as the unit of algorithm design, an idea introduced in the graph-processing community for a different pathology and which we adapt here to fuse the many heterogeneous phases of a computational-geometry pipeline into single warp-resident kernels, paired with a device-side heap allocator that lets the buffers between fused phases be sized and allocated on the device. Building on this template, we present CuACD (CUDA ACD), the first fully GPU-resident ACD system, together with a suite of reusable GPU components, released as open-source standalone CUDA modules that drop into any search-based ACD pipeline. On the V-HACD benchmark, PartNet-Mobility, and an Objaverse subset, CuACD achieves more than an order of magnitude of speedup over CoACD at matched or better quality.

0.81

FOMOS: Feature-Oriented Meshing of SDFs

cs.GR ·2026-11-12 ·Stefan Ohrhallinger, Amal Dev Parakkat
similarity 0.61
Abstract

We introduce FOMOS, a purely geometric method for feature-oriented meshing of signed distance functions (SDFs) that addresses various challenges of the existing state-of-the-art methods. Our algorithm improves mesh quality and runtime, enabling the SDF meshing in a matter of seconds. While existing techniques such as Marching Cubes and Neural Dual Contouring either produce dense, low-quality triangulations or sacrifice details for sparsity, often requiring carefully chosen user parameters, our single-parameter FOMOS leverages feature sized sampling to dynamically adjust mesh resolution based on local feature size (LFS), which we compute efficiently by sampling a medial scaffold. The LFS considers not only curvature but also shape thickness and captures large features through non-local structure, omitting many redundant small triangles from existing methods. Through extensive comparisons, we demonstrate the distinct strengths of FOMOS in execution time, reconstructed result accuracy, and triangle quality in the output mesh. We also introduce a lightweight variant of FOMOS targeting huge ($10k^3$) sparse inputs, which, to the best of our knowledge, no existing method can handle except Marching Cubes. To demonstrate the usefulness of our method, we show that FOMOS enables instant previews using a sub-sampled medial scaffold and can accelerate volumetric simulations by orders of magnitude.

0.24