Fast Collision Detection
Between Geometric Models
in Dynamic Environments

Ming C. Lin

Army Research Office / UNC Chapel Hill

Dinesh Manocha

UNC Chapel Hill

Abstract

The problems of collision or interference detection between two or more objects in dynamic environments are fundamental in computer graphics, robotics and computer simulated environments. These problems have been extensively studied in the literature. However, no efficient and accurate algorithms are known for large environments.

In this talk, we present efficient algorithms for contact determination and interference detection between geometric models undergoing rigid motion. The set of models include polyhedra and surfaces described by algebraic sets or NURBS. The algorithms make use of temporal and spatial coherence between successive instances and their running time is a function of the motion between successive instances. The main characteristics of these algorithms are their simplicity and efficiency. They have been implemented and we will demonstrate their application in architecture walkthroughs, multi-body simulation and physically-based modeling. A subset of these implementations are available as part of the I_COLLIDE collision detection package.

References

More information about these algorithms is available in the following papers/thesis:

  1. Incremental algorithms for collision detection between solid models, M. Ponamgi, D. Manocha and M. Lin, in the Proceedings of the ACM/Siggraph Symposium on Solid Modeling, pp. 293-304, 1995.
  2. Fast Contact Determination in Dynamic Environments, M. Lin and D. Manocha, in the International Journal of Computational Geometry and Applications, 1995.
  3. I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scaled Environments, J. Cohen, M. Lin, D. Manocha and K. Ponamgi, in the Proceedings of the ACM Symposium on Interactive 3D Graphics , pp. 189-196, 1995.
  4. Efficient Collision Detection for Animation and Robotics, Ph.D. thesis, University of California, Berkeley, M. C. Lin.

All these papers are also available on the WWW at Dinesh Manocha's collision detection page.

More information on I_COLLIDE is available at the I_COLLIDE Home Page.

Brook Conner