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.