Efficient collision detection for animation and robotics

We present efficient algorithms for collision detection and contact determination between geometric models, described by linear or curved boundaries, undergoing rigid motion. The heart of our collision detection algorithm is a simple and fast incremental method to compute the distance between two convex polyhedra. It utilizes convexity to establish some local applicability criteria for verifying the closest features. A preprocessing procedure is used to subdivide each feature's neighboring features to a constant size and thus guarantee expected constant running time for each test. The expected constant time performance is an attribute from exploiting the geometric coherence and locality. Let n be the total number of features, the expected run time is between O( p n) and O(n) ...