Fast algorithms for penetration and contact determination between non-convex polyhedral models

We present fast algorithms for penetration detection and contact determination between polyhedral models in dynamic environments. They are based on a distance computation algorithm for convex polytopes and a hierarchical coherence-based algorithm to compute contacts. In particular, we extend an earlier expected constant time algorithm for distance computation between convex polytopes to detect penetrations. The algorithm computes all the contacts between the convex hulls of the polytopes. After identifying the contact regions it traverses the features lying beneath them to more precisely determine the contact regions. The traversal employs a dynamic technique, sweep and prune, to overcome the O(n²) pairwise feature checks. The complexity of the overall algorithm is output sensitive. We demonstrate its performance on the dynamic simulation of a threaded insertion