V-clip: Fast Distance Computation and Collision Detection for Polyhedra

This is a Java implementation of V-clip, which is a robust algorithm for computing distances and checking for collisions between convex polyhedra and collections of convex polyhedra. It addition to distances, V-clip also computes the closest points and features between polyhedra, which is particularly useful for calculations involving contact dynamics.

The original version of Vclip was written in C++ by Brian Mirtich at MERL, and is based on his algorithm described in ``V-Clip: Fast and Robust Polyhedral Collision Detection'', ACM Transactions on Graphics, July, 1997. The Java port was done by John E. Lloyd and Eddy Boxerman at the UBC Computer Science Department. The copyright is held by MERL.

Our java implementation fixes some bugs in the original V-clip, mostly related to edge-edge feature tests in degenerate situations. Polyhedra with co-planar faces can also cause problems in the orginal V-clip, since the Voronoi regions for the edges between such faces are degenerate. Our implementation should handle this case as well, although it is probably better to avoid co-planar faces if possible.

Our java implementation uses the javax.vecmath package, which was orginally designed to support Java 3D. A jar file of this package, along with documentation, is also availabled, in case you need it. V-clip also uses (and includes) my package quickhull3d, for computing 3D convex hulls.

Package downloading and documentation:

John Lloyd's home page