Ming C. Lin and Dinesh Manocha
University of North Carolina, Chapel Hill
Collision Detection and Distance Computation : Algorithms and Applications
The problems of distance computation and collision detection between
two or more objects in dynamic environments are fundamental issues in
robotics, computer graphics and simulated environments. These problems
have been extensively studied in the literature. However, no efficient
and accurate algorithms are known for general applications, especially
complex and large-scale environments. In this talk, we first present
efficient algorithms for interference detection and distance computation
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 applications in
simulation-based design, virtual environments, path-planning,
multi-body simulations and physically-based modeling. A subset
of these implementations are available as part of the I_COLLIDE
collision detection package.