Minimum Distance Computations

Goal

Our goal is to efficiently compute the minimum distance between complex models. This work was motivated by a collaborative Virtual Prototyping Project, where we need to predict possible contact between a virtual arm and mechanical assemblies. Most current work on minimum distance focuses on polyhedral and often convex models; we wish to extend this to include sculptured CAD models.

Approach

Our approach is based on a hierarchy of bounding volumes around the model. Portions of the hierarchy may be quickly pruned by establishing an upper bound on the minimum distance to the model and a lower bound on the minimum distance between the model geometries contained by the bounding volumes. We have investigated different bounding volumes, different tree traversal methods, as well as the efficiency of different model representations.

At a lower level, we are investigating ways of tracking the closest point on a sculptured surface at very high rates. These high speed methods are suitable for the 1000Hz rates needed for haptic interfaces. We show various means of obtaining these rates with speed-accuracy tradeoffs. In addition, we have analyzed the stability of these methods.

Participants

Publications

Johnson, David E., and Cohen, Elaine, "Bound Coherence for Minimum Distance Computations," 1999 International Conference on Robotics and Automation (ICRA'99), to appear
Johnson, David E., and Cohen, Elaine, "An improved method for haptic tracing of sculptured surfaces," Symp. Haptic Interfaces, Proc. ASME Dynamic Systems and Control Division, DSC-Vol. 64, Anaheim, CA, Nov. 15-20, 1998, pp. 243-248. [pdf]
Johnson, David E., and Cohen, Elaine, "A framework for efficient minimum distance computations," Proc. IEEE Intl. Conf. Robotics & Automation, Leuven, Belgium, May 16-21, 1998, pp. 3678-3684. [pdf]
Thompson II, T.V., Johnson, D.E., and Cohen, E., "Direct haptic rendering of sculptured models," Proc. Symposium on Interactive 3D Graphics, (Providence, RI), pp. 167-176, April 27-30, 1997. [pdf]

Support

Support for this research was provided by NSF Grant MIP-9420352, by DARPA grant F33615-96-C-5621, and by the NSF and DARPA Science and Technology Center for Computer Graphics and Scientific Visualization (ASC-89-20219).

gdc-web@cs.utah.edu

Last update: September 21, 2000