V-CLIP - FAST AND ROBUST POLYHEDRAL COLLISION DETECTION

This article presents the Voronoi-clip, or V-Clip, collision detection algorithm for polyhedral objects specified by a boundary representati on. V-Clip tracks the closest pair of features between convex polyhedr a, using an approach reminiscent of the Lin-Canny closest features alg orithm. V-Clip is an improvement over the latter in several respects. Coding complexity is reduced, and robustness is significantly improved ; the implementation has no numerical tolerances and does not exhibit cycling problems. The algorithm also handles penetrating polyhedra, an d can therefore be used to detect collisions between nonconvex polyhed ra described as hierarchies of convex pieces. This article presents th e theoretical principles of V-Clip, and gives a pseudocode description of the algorithm. It also documents various tests that compare V-Clip , Lin-Canny, and the Enhanced GJK algorithm, a simplex-based algorithm that is widely used for the same application. The results show V-Clip to be a strong contender in this field, comparing favorably with the other algorithms in most of the tests, in terms of both performance an d robustness.