Incremental algorithms for collision detection between solid models
Madhav K. Ponamgi, Dinesh Manocha, Ming C. Lin · 1995
Fast and accurate collision detection between general solid models is a fundamental problem in solid modeling, robotics, animation and computer-simulated environments.Most of the earlier algorithms are either restricted to a class of solid models, say convex polytopes, or are not fast enough for practical applications.We present an incremental algorithm for collision detection between general B-rep solid models in dynamic environments.The algorithm combines a hierarchical representation with incremental frame to frame computation to rapidly detect collisions.It makes use of coherence between successive instances to efficiently determine the number of object features interacting.For each pair of objects, it localizes the interference regions on their convex hulls.The features associated with these regions are represented in a precomputed hierarchy,The algorithm uses a coherence based approach to quickly traverse the pre-computed hierarchy and check for collisions between the features.The algorithm works well in practice and its complexity is output sensitive.