University of Oxford Logo University of OxfordDepartment of Computer Science - Home
Linked in
Linked in
Follow us on twitter
Twitter
On Facebook
Facebook
Instagram
Instagram

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 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 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 Conditions

gjk.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.

References