"Meshsweeper": dynamic point-to-polygonal mesh distance and applications

We introduce a new algorithm for computing the distance from a point to an arbitrary polygonal mesh. Our algorithm uses a multiresolution hierarchy of bounding volumes generated by geometric simplification. Our algorithm is dynamic, exploiting coherence between subsequent queries using a priority process and achieving constant time queries in some cases. It can be applied to meshes that transform rigidly or deform nonrigidly. We illustrate our algorithm with a simulation of particle dynamics and collisions with a deformable mesh, the computation of distance maps and offset surfaces, the computation of an approximation to the expensive Hausdorff distance between two shapes, and the detection of self-intersections. We also report comparison results between our algorithm and an alternative algorithm using an octree, upon which our method permits an order-of-magnitude speed-up.

1 Introduction

Computing the Euclidean distance from a point to a complex polygonal shape is a fundamental problem in computer graphics. There are numerous applications, both in interactive techniques (for collision prevention or tolerance verification) and in photo-realistic graphics (for accurate motion dynamics, 3D path planning, or self-intersection detection [1]). Distance carries more information than occurrence or nonoccurrence of collision because it permits prediction, use of coherence [2], and dynamic path modification.