Accelerating Hausdorff distance computation between triangle meshes via spatial locality

To address the efficiency issues in the Hausdorff distance computation between triangle meshes, this paper proposes an acceleration algorithm based on the principle of spatial locality, building upon the cascading upper bounds framework of Sacht et al. (2024). Existing methods often neglect the spatial correlation between parent and child vertices during iterative subdivision, leading to a large number of redundant global BVH queries. To decrease computational overhead, we introduce an approach with three steps: (1) a hierarchical spatial initialization method that directly inherits the nearest face information from the parent level; (2) a one-ring neighborhood search to transform complex global traversals into constant-time local scans; (3) a double pruning algorithm that skips massive global queries while ensuring a safe fallback to global search, thereby guaranteeing the accuracy of the results. Extensive experiments on over 1380 triangle mesh pairs, including models from the Thingi10K dataset, demonstrate that our algorithm achieves an initial guess hit rate of over 99.5% on more than 70% of the test data. While maintaining the accuracy consistent with Sacht et al. (ϵ=10⁻⁸), our method achieves an average performance speedup of approximately 2.27×, improving the efficiency of Hausdorff distance computation for complex triangle meshes, particularly under high-precision requirements.