readme.txt

GJK距离计算算法实现

History
=======

The files in this directory form v2.4 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.4 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.

This release is the next public release after v2.1, which has been widely
used now since April 1997.  Only one user of v2.1 has reported any problems,
and this has manifested itself only under quite extreme conditions: it is
believed that that problem has been fixed in this release, and it should
be possible for general users of v2.1 to use this code without any
significant changes.  The other changes in this release are cosmetic,
and designed to make it easier to use the code. The major changes are:

 * Replaced my original termination condition by the one in the original
   1988 paper by GJK.  This seems to have fixed a problem with occasional
   cycling under extreme conditions, without increasing the computation
   times noticeably.

 * The routine can now return a confidence measure in the result, in the
   form of the value of GJK's `g-function'.  Now the function returns an
   upper bound on the square of the distance, and the g-function value
   can be used to compute a confidence interval.  (Details are given in
   the code comments.)  The routine will attempt (and normally succeeds)
   in reducing this value to less than a #define'd constant EPSILON, which
   can be set to zero (although setting this to zero doubles the
   computation time on my machine).

 * The geometric data-types that the code uses can now be altered by the
   user, who only has to supply appropriate access macros.  This applies
   to the types for objects, vertices, edge topology (if supplied), and
   transformations.

Acknowledgements
================

Many thanks to John Nagle for detecting the problem in the termination
condition in version 2.1 of this code, and to Gino van den Bergen for
suggesting the fix.


The Code
========

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.


Why is gjk.c so hard to read?
=============================

gjk.c is provided stripped of its comments.  This means that anybody who
wants to can still test the code, but if they want to go further they
might well want the commented version.  All I then ask is that they E-mail
me, explaining why they want it: I've never refused to provide such a copy
yet.  This is for several reasons.

  1)  My university bean-counters want to know how my research is being
      used.  Being able to say that `M people explicitly asked for copies
      of the code' has much more weight that saying `The web-page was hit
      N times'.
  2)  I can compile a list of serious users, and E-mail them when new
      versions are released.
  3)  This code has taken a lot of effort to develop and refine, and so
      we do ask that anybody who is going to make money from the code
      makes a contribution towards its development.


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
July 1998.