Computing the Distance between Objects
This page references our work on one of the basic problems for planning and simulation, namely the fast calculation of the distance between two objects.
We have implemented an enhanced version of the distance routine of Gilbert, Johnson and Keerthi (GJK), which allows the tracking of the distance between a pair of convex polyhedra in time that is expected to be bounded by a constant. Experimental results confirm this result, at least for moderate relative velocities, and suggest that the enhanced algorithm is roughly the same speed as the Lin-Canny algorithm, as used in I-COLLIDE, and Brian Mirtich's V-Clip.
The CodeThe code for version 2.4 of GJK is now available. It consists of the core routines (gjk.c, with header file gjk.h), and a test-bed wrapper (gjkdemo.c). The enhanced algorithm requires a list of all the edges in each convex polyhedra, and without it the performance of the routine is the same as the original GJK.
The test bed program generates pairs of randomly placed hulls of a given size (size greater or equal to three), and calls the enhanced GJK routine to find their distance apart. It then checks the answer in an independent piece of code, and will report on any errors found.
By default the routine generates a semi-regular shape that I call a polyball, which it can do without using any routines for generating convex hulls. The program gjkdemo can only generate this form of polyhedra. However if the public domain package called Qhull is used, together with the glue code in sac.c, then the program created from gjkdemo.c can also test GJK using hulls of randomly generated point sets (-Q option). With the makefile given this is created as a program called gjkqhull, with the same options as gjkdemo but also supporting the -Q option. Also, the testing of zero-distance answers is only done if Qhull is linked.
Terms and Conditionsgjk.c and gjk.h are copyright (c) Stephen Cameron 1996, 1997, 1998, but may be freely copied and used for non-profit making applications and for evaluation. The code is also available for commercial use; please contact the author for details. gjkdemo.c and sac.c may be used and altered at will. In no way will either Stephen Cameron or the University of Oxford be responsible for loss or damages resulting from the use of this code. All of the code is written in ANSI C, and it may be obtained here.
Researchers may use the commented version of gjk.c for study: please e-mail me with your name, affiliation, and a brief desription of your research project so that I can compile a list of users. The current version of gjk.c is v2.4. This fixes an error in the termination condition from the last public release (2.1), and adds some cosmetic changes to make the code easier to integrate with existing geometric code. Version 2.4 was released in July 1998, and is thought to be robust, but in case of problems version 2.1 and version 2.0 are still available.
Qhull is available from the Geometry Center at the University of Minnesota (see above), under their standard terms and conditions.
- Towards Efficient Motion Planning for Manipulators with Complex Geometry, ISATP'95, August 1995. [isatp95.ps.gz: 131069 bytes compressed postscript].
- A Comparison of Two Fast Algorithms for Computing the Distance between Convex Polyhedra, IEEE Trans. Robotics and Automation 13(6):915-920, December 1997.
- Enhancing GJK: Computing Minimum and Penetration Distances between Convex Polyhedra. Int Conf Robotics and Automation, April 1997. [icra97.ps.gz: 56438 bytes compressed postscript].
- Computing Distances Between NURBS-defined Convex Objects (with Colin Turnbull), ICRA-98. [icra98.ps.gz: 88615 bytes compressed postscript].
- I-COLLIDE: An Interactive and Exact Collision Detection System for Large Scale Environments by J. Cohen, M. Lin, D. Manocha and K. Ponamgi, ACM Int. 3D Graphics Conference pages 189-196, 1995.
- A Fast Algorithm for Incremental Distance Calculation by Ming Lin and John Canny, IEEE Int. Conf. Robotics and Automation pages 1008-1014, April 1991.
- V-clip: Fast and Robust Polyhedral Collision Detection by Brian Mirtich, Mitsubishi Electric Research Laboratory TR-97-05, July 1997.
- A Fast Procedure for Computing the Distance between Complex Objects in Three-Dimensional Space by E. G. Gilbert, D. W. Johnson and S. S. Keerthi, IEEE Trans. Robotics and Automation 4(2):193-203, April 1988.
- Determining the Minimum Translational Distance between Two Convex Polyhedra (with Bob Culley). IEEE Conf. Robotics and Automation, San Francisco, April 1986. [mtd.ps.gz: 44314 bytes compressed postscript].