Lin-Canny Closest Features Algorithm (original) (raw)

One way to perform very fast collision detection in applications such as Dynamic simulation is by using Ming Lin's and John Canny's closest features algorithm. In its basic form, this algorithm maintains the pair of closest features (vertices, edges, or faces) between two convex polyhedra moving through space. By exploiting the fact that the current closest features are probably near the previous closest features, near constant query time is achieved in practice.

The distance between two polyhedra is easily found, once the closest features are known; a collision is declared when this distance falls below some small epsilon.

I have coded a C version of the basic Lin-Canny closest features algorithm. This version is for research purposes only; a license must be obtained for commercial use in any form. To obtain the code:

• 1. Grab this gzipped tar file
• 2. Uncompress the archive with gunzip
• 3. Do a tar -xf cf.tar This will build a directory closestFeatures with all the relevant files. A README file and an example application are included. A make will build the executable for this example.

Have fun, and please send meany questions or comments.

Now Available: I-Collide

The Lin-Canny algorithm forms the underlying core of I_COLLIDE, a complete library for interactive and exact collision detection in large environments composed of convex polyhedra.

Brian Mirtich / mirtich@cs.berkeley.edu / 31 January 1996