Lin-Canny Closest Features Algorithm
One way to perform very fast collision detection in applications
is by using
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:
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.
- 1. Grab this gzipped tar file
- 2. Uncompress the archive with gunzip
- 3. Do a tar -xf cf.tar
Have fun, and please send
any questions or comments.
Now Available: I-Collide
The Lin-Canny algorithm forms the underlying core of
a complete library for interactive and exact collision detection in
large environments composed of convex polyhedra.
Brian Mirtich /
31 January 1996