Abstract:

This paper 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, making it useful for nonconvex polyhedral collision detection. This paper 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 Gilbert-Johnson-Keerthi 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.