Computing the Distance between Objects
One of the basic problems for planning and simulation, namely the fast calculation of the distance between two objects.
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.ccan 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.
Source: