The files in this directory form v2.1 of Stephen Cameron's enhanced
implementation of the routine of Gilbert, Johnson and Keerthi to compute
the distance between two convex polytopes (gjk.c and gjk.h), and v1.1 of
a test harness that demonstrates their use (gjkdemo.c, sac.c, and Makefile).
See http://www.comlab.ox.ac.uk/~cameron/distances.html for more details of
the background to this code.

** The current public release is version 2.4. **

There are just two external routines defined in gjk.c, and declared in gjk.h.
gjk_distance() is the main routine for computing the distance between the
polytopes (actually, it returns the square of the distance).  In many cases
the witness points (between which the minimum distance is realised) are not
needed by the calling routine, and need not be implicitly computed by
gjk_distance().  However they can always be obtained from the simplex
data-structure by calling the other exported routine, gjk_extract_point().

gjkdemo.c is the test-harness, that generates pairs of convex polyhedra in
three dimensions, calls gjk_distance() for them, and checks the result
if the objects do not interfere.  By default the makefile creates an
executable program called gjkdemo, in which the objects generated have
a semi-regular structure.  The program also attempts to time the calls
to gjk_distance by repeating each call many (>>100) times, and by default
prints out a report for each pair of polytopes tested.  The distance problem
can be solved more quickly if we are looking at pairs of moving objects,
and by default the program uses 10 instance pairs for each pair of polyhedra
created.

By linking the University of Minnesota's Qhull code into the test harness,
together with the glue code in sac.c, we can create the program gjkqhull
that, as well as doing everything that gjkdemo does, can also use polyhedra
generated by taking random point sets on spheres.  gjkqhull also checks
whether polyhedra reported by gjk_distance() as interfering are actually
interfering.

Options for gjkdemo/gjkqhull:
   Arguments take the form of a list of general optional arguments,
followed by the number of runs, followed by an optional integer giving the
number of points per polyhedra (20 by default). General optional arguments
are:
	-h		gives a help message
	-H		disables hill-climbing (original GJK algorithm)
	-q[N]		quiet mode, suppresses the per-run report unless
			an error occurs (producing a dot every N runs if
			N supplied)
	-Q		use random hulls (gjkqhull only)
	-x		disable the use of transformation matrices; pre-compute
			all vertex coordinates instead (as in v2.0 of GJK)
	-R[value]	use relative rotations between instances, with
			the optional value scaling the amount of rotation
	-T<value>	change the relative translations used between instances
	-r<num>		change the repeat count
	-i<num>		change the number of instances
	-s<hex>		define the initial seed for the random-number generator

Notes
1. Although gjk.c has been extensively tested for polyhedra only, it should
   also work for polytopes in other dimensions.  Change DIM in gjk.h.
2. The glue code for Qhull in sac.c is not efficient, but was rather
   designed to check the output coming from Qhull.  I'd be happy to
   see a less paranoid version!

Stephen Cameron
Oxford University Computing Laboratory
April 1997.