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
LinCanny algorithm, as used in
ICOLLIDE,
and Brian Mirtich's
VClip.
The Code
The 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 testbed 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 semiregular 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 zerodistance answers is only done if Qhull is linked.
Terms and Conditions
gjk.c and gjk.h are copyright
(c) Stephen Cameron 1996, 1997, 1998,
but may be freely copied and used for nonprofit 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 email 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.
References

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):915920, 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 NURBSdefined Convex Objects
(with Colin Turnbull),
ICRA98.
[icra98.ps.gz:
88615 bytes compressed postscript].

ICOLLIDE: 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 189196, 1995.

A Fast Algorithm for Incremental Distance Calculation by
Ming Lin and John Canny,
IEEE Int. Conf. Robotics and Automation pages 10081014, April 1991.

Vclip: Fast and Robust Polyhedral Collision Detection by
Brian Mirtich,
Mitsubishi Electric Research Laboratory
TR9705,
July 1997.

A Fast Procedure for Computing the Distance between
Complex Objects in ThreeDimensional Space by
E. G. Gilbert, D. W. Johnson and S. S. Keerthi,
IEEE Trans. Robotics and Automation 4(2):193203,
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].
