GJKSourceCode
所属分类:人工智能/神经网络/深度学习
开发工具:C/C++
文件大小:32KB
下载次数:38
上传日期:2010-11-01 09:04:07
上 传 者:
2008405
说明: 用C语言开发的一个GJK算法源代码。希望对大家研究机器人路径规划有所帮助。
(Developed using C language source code of a GJK algorithm. Research we want to help the robot path planning.)
文件列表:
Source Code (0, 2009-11-28)
Source Code\gjk.c (33939, 2009-11-28)
Source Code\gjk.h (14997, 2009-11-28)
Source Code\gjkdemo.c (32459, 2009-11-28)
Source Code\Makefile.txt (481, 2009-11-28)
Source Code\sac.c (8173, 2009-11-28)
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
1***8 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 change the relative translations used between instances
-r change the repeat count
-i change the number of instances
-s 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 19***.
近期下载者:
相关文件:
收藏者: