GJK算法的c程序实现

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.