Efficient Contact Determination in Dynamic Environments

Abstract

The problem of contact determination among multiple objects is fundamental in computer simulated environments and robotics. Most of the earlier work is restricted to either polyhedral models or static environments. In this paper, we present efficient algorithms for contact determination and inference between geometric models in dynamic environments. The set of models include polyhedra and surfaces described by algebraic sets or piecewise algebraic functions. 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; their performance on many applications indicates their potential for real-time simulations.