MeshSweeper: From Closest Point to Hausdorff Distance Between Meshes

Abstract

We introduce a new algorithm for computing the distance from a point to an arbitrary polygonal mesh. Our algorithm uses a multi-resolution hierarchy of bounding volumes generated by geometric simplification. Our algorithm is dynamic, exploiting coherence between subsequent queries using a priority process (without caching the closest point), and achieving constant time queries in some cases. The method also applies to a mesh that deforms nonrigidly. Achieving from about 500 to several thousand queries per second for a complex polygonal shape on a PC, our method has applications both for interactive and photo-realistic graphics. In particular, we study in this paper the application to computing the Hausdorff distance between two polygonal shapes, with an arbitrary precision.