ABSTRACT:

Calculation of the minimum distance to a geometric object or the
minimum separation between objects is a fundamental problem that has
application in a variety of arenas. Minimum separation queries for
sculptured surfaces are believed particularly difficult, yet are
increasingly important as modeling problems grow larger and
interactivity demands grow more stringent. We present a set of
algorithms based on easy to compute bounds that allows efficient
solution of minimum separation queries for many types of surface
representations. These algorithms have simple and robust
implementations and have average case performance matching the most
efficient theoretical algorithms. These algorithms are tested in an
interactive application designed to be the front-end of a haptic
display system for virtual prototyping of assemblies.