Fast and Accurate Hausdorff Distance Calculation between Meshes

Michael Guthe, Pavel Borodin, Reinhard KleinJ. WSCG 2005

Introduction

In computer graphics and geometric modeling, the process of "simplifying" complex 3D models—such as high-resolution laser scans—is essential for efficient rendering and storage. However, simplification must preserve the geometric integrity of the original shape. The Hausdorff distance serves as the gold standard for measuring this error, as it identifies the point on one mesh that is furthest from the other.

Despite its mathematical rigor, calculating the Hausdorff distance exactly is NP-hard. Traditional tools like Metro and MESH approximate this value by sampling points across the entire surface of both meshes. This approach is computationally expensive; doubling the accuracy typically requires quadrupling the number of samples, leading to processing times that can stretch into hours. This paper introduces a novel algorithm designed to make these checks fast enough to be used dynamically during the simplification process.

Methodology: Adaptive Sampling and Pruning

The authors’ primary innovation is a shift from uniform sampling to adaptive sampling. Rather than spreading computational resources evenly across the object, the algorithm "hunts" for regions where the two shapes deviate most significantly.

Spatial Data Structures and Traversal

The algorithm begins by sorting the triangles of both meshes into voxel grids and building an octree—a hierarchical tree structure—on top of them. The system then traverses the octrees of both meshes simultaneously. By utilizing a priority queue, the algorithm processes cells with the highest potential distance first, ensuring that the most likely candidates for the maximum deviation are checked early.

Tight Upper Bounds and Subdivision

To optimize the search, the algorithm calculates a mathematical "upper bound" for every triangle, representing the maximum possible distance any point on that triangle could be from the target mesh. If this upper bound is smaller than a distance already confirmed elsewhere, the algorithm skips that triangle entirely. If a triangle remains a candidate for the maximum distance, it is subdivided into smaller segments, and the process repeats until the desired precision is achieved.

The Quick-Reject Pipeline

When integrated into a mesh simplification workflow, the authors implement a multi-stage pipeline. They first utilize the Quadric Error Metric (a fast but loose approximation). If the error exceeds a threshold, the system performs two increasingly complex distance tests before finally resorting to the full, high-precision Hausdorff calculation.

Experimental Evaluation

The algorithm was evaluated using several iconic 3D models, including the Stanford Bunny, the Coffee Set, and large-scale scans like the Dragon, Buddha, and the 2mm David (containing over 7 million triangles).

Performance Results

The quantitative improvements are significant:

  • Speed: In a comparison using the Stanford Bunny at 0.01% accuracy, the proposed algorithm finished in 2.7 seconds. In contrast, MESH took 395 seconds and Metro took 1,406 seconds.
  • Scalability: On the massive 7-million-triangle David model, the algorithm performed error-controlled simplification in approximately 66 minutes, whereas competing high-quality methods were often limited by memory or significantly slower runtimes.
  • Efficiency: In the "Coffee Set" test (comparing a set with and without a lid), the algorithm correctly identified that only the gap where the lid used to be required dense sampling, effectively ignoring the identical table and cups.

Key Insights

  • Efficiency through Omission: The algorithm's speed stems from the realization that if the goal is to find the maximum distance, no time should be spent on areas where the meshes are clearly close together.
  • Accuracy Independence: Unlike traditional tools that slow down exponentially as precision requirements increase, this algorithm’s performance remains relatively flat because it only refines the sampling in high-error regions.
  • Robustness: While some specialized methods are faster for "perfect" (orientable manifold) meshes, this approach is designed to be robust for the "messy" real-world data found in raw scans.

Conclusion and Future Work

This research effectively transforms a computationally prohibitive task into a near-instantaneous one. By focusing on high-deviation regions and mathematically pruning unnecessary calculations, the authors have paved the way for more reliable and precise 3D model processing. Future work may involve moving from local region compaction to global empty space distribution to further improve the visual quality of simplified meshes.

Summary updated

BibTeX
@article{guthe2005fast,
  author = {Michael Guthe and Pavel Borodin and Reinhard Klein},
  title = {{Fast and Accurate Hausdorff Distance Calculation between Meshes}},
  journal = {J. WSCG},
  year = {2005},
}
Figure