RT-HDIST: Ray-Tracing Core-based Hausdorff Distance Computation

YoungWoo KIM, JaeHong Lee, Duksu Kim
Korea University of Technology and Education (KOREATECH), SPIN Lab
Pacific Graphics 2025
Paper Code arXiv

Abstract

The Hausdorff distance is a fundamental metric with widespread applications across various fields. However, its computation remains computationally expensive, especially for large-scale datasets. This work targets exact point-to-point Hausdorff distance on point sets. In this work, we present RT-HDIST, the first Hausdorff distance algorithm accelerated by ray-tracing cores (RT-cores). By reformulating the Hausdorff distance problem as a series of nearest-neighbor searches and introducing a novel quantized voxel-index space, RT-HDIST achieves significant reductions in computational overhead while maintaining exact results. Extensive benchmarks demonstrate up to a two-order-of-magnitude speedup over prior state-of-the-art methods, underscoring RT-HDIST's potential for real-time and large-scale applications.

Our approach

Figure 1. Overview of RT-HDIST algorithm


 We propose an RT-core-based method to compute the Hausdorff distance efficiently with 3 stage by transforming the problem into a ray-tracing-friendly form.

 Voxel-Index Space Construction:
  Target points are quantized into a voxel-index space, where each voxel holds a representative point and its associated AABB. Query points are also mapped to this space. This step runs on general GPU cores.

 RT-Accelerated Candidate Search:
  A BVH is built over the voxel AABBs, and RT-cores perform efficient candidate searches via ray tracing in the voxel-index space.

 Refined Distance Computation:
  Candidate pairs are mapped back to the original object space, and the final Hausdorff distance is computed on GPU cores.

Benchmark results

System environment

Intel Core i5-14600K • 32 GB RAM

System environment
Figure 2. Benchmark results

BibTeX

@article{10.1111:cgf.70229,
journal = {Computer Graphics Forum},
title = {{RT-HDIST: Ray-Tracing Core-based Hausdorff Distance Computation}},
author = {Kim, YoungWoo and Lee, Jaehong and Kim, Duksu},
year = {2025},
publisher = {The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {10.1111/cgf.70229}
}