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 representation. V-Clip tracks the closest pair of features between convex polyhedra, using an approach reminiscent of the Lin-Canny closest features algorithm. 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, and can therefore be used to detect collisions between nonconvex polyhedra described as hierarchies of convex pieces. This article presents the 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 and robustness.