X-HD: Fast Hausdorff Distance Computation with Ray Tracing

The Hausdorff distance (HD) is a mathematical measure of the similarity (or dissimilarity) between two sets of points, typically used to compare geometric shapes, images, or spatial distributions. HD computation has a broad range of applications in large-scale data analysis across domains like medical imaging, geospatial information systems, and graphics. As the volume of spatial data continues to grow rapidly, HD computation has become increasingly time-consuming, demanding effective and scalable hardware acceleration. Recent research on utilizing Ray Tracing (RT) cores to accelerate k-nearest neighbor (k-NN) search shed light on this problem, as k-NN is the building block of the HD algorithm. However, naively using an RT-accelerated k-NN library yields poor performance due to the lack of domain-specific optimizations, leading to poor utilization of hardware resources. In this paper, we propose X-HD, a general-purpose HD algorithm with RT acceleration for large-scale datasets. X-HD has three core optimization techniques: (1) We use a grid to organize spatially proximal points, which reduces the traversal intensity of the Bounding Volume Hierarchy (BVH) tree. (2) We use HD estimators to prune non-contributing points for faster processing. (3) Introducing the grid also results in severe load imbalance in RT shaders. Our solution addresses this by selectively offloading the distance computation from RT shaders to a dedicated CUDA kernel to improve load balance. X-HD outperforms the state-of-the-art industrial software ITK by 5.3 × on average. Compared to a GPU-optimized HD solution, X-HD achieves a speedup of up to 6.4 ×.