Interactive Hausdorff distance computation for general polygonal models

Min Tang, Minkyoung Lee, Young J. Kim

Research output: Contribution to journalConference articlepeer-review

66 Scopus citations

Abstract

We present a simple algorithm to compute the Hausdorff distance between complicated, polygonal models at interactive rates. The algorithm requires no assumptions about the underlying topology and geometry. To avoid the high computational and implementation complexity of exact Hausdorff distance calculation, we approximate the Hausdorff distance within a user-specified error bound. The main ingredient of our approximation algorithm is a novel polygon subdivision scheme, called Voronoi subdivision, combined with culling between the models based on bounding volume hierarchy (BVH). This cross-culling method relies on tight yet simple computation of bounds on the Hausdorff distance, and it discards unnecessary polygon pairs from each of the input models alternatively based on the distance bounds. This algorithm can approximate the Hausdorff distance between polygonal models consisting of tens of thousands triangles with a small error bound in real-time, and outperforms the existing algorithm by more than an order of magnitude. We apply our Hausdorff distance algorithm to the measurement of shape similarity, and the computation of penetration depth for physically-based animation. In particular, the penetration depth computation using Hausdorff distance runs at highly interactive rates for complicated dynamics scene.

Original languageEnglish
Article number74
JournalACM Transactions on Graphics
Volume28
Issue number3
DOIs
StatePublished - 27 Jul 2009
EventACM SIGGRAPH 2009, SIGGRAPH '09 - New Orleans, LA, United States
Duration: 3 Aug 20097 Aug 2009

Keywords

  • Dynamics simulation
  • Hausdorff distance
  • Penetration depth
  • Shape similarity

Fingerprint

Dive into the research topics of 'Interactive Hausdorff distance computation for general polygonal models'. Together they form a unique fingerprint.

Cite this