libccd

Usage

Compile And Install

libccd contains two mechanisms how to compile and install it. Using simple Makefile and using autotools.

1. Using Makefile

Directory src/ contains Makefile that should contain everything needed for compilation and installation:

$ cd src/
$ make
$ make install

Library libccd is by default compiled in double precision of floating point numbers - you can change this by options USE_SINGLE/USE_DOUBLE, i.e.:

$ make USE_SINGLE=yes

will compile library in single precision.

Installation directory can be changed by options PREFIX, INCLUDEDIR and LIBDIR.
For more info type 'make help'.

2. Using Autotools

libccd also contains support for autotools:

1. Generate configure script etc.:

   $ ./bootstrap

2. Create new build/ directory:

   $ mkdir build && cd build

3. Run configure script:

   $ ../configure

4. Run make and make install:

   $ make && make install

configure script can change the way libccd is compiled and installed, most significant option is --enable-double-precision which enables double precision (single is default in this case).

GJK - Intersection Test

This section describes how to use libccd for testing if two convex objects intersects (i.e., 'yes/no' test) using Gilbert-Johnson-Keerthi (GJK) algorithm.

Procedure is very simple (and is similar for usages of library):

1. Include <ccd/ccd.h> file.
2. Implement support function for specific shapes. Support function is function that returns furthest point from object (shape) in specified direction.
3. Set up ccd_t structure.
4. Run ccdGJKIntersect() function on desired objects.

Here is skeleton of simple program:

  1  #include <ccd/ccd.h>
  2  #include <ccd/quat.h> // for work with quaternions
  3  
  4  /** Support function for box */
  5  void support(const void *obj, const ccd_vec3_t *dir,
  6               ccd_vec3_t *vec)
  7  {
  8      // assume that obj_t is user-defined structure that holds info about
  9      // object (in this case box: x, y, z, pos, quat - dimensions of box,
 10      // position and rotation)
 11      obj_t *obj = (obj_t *)_obj;
 12      ccd_vec3_t dir;
 13      ccd_quat_t qinv;
 14  
 15      // apply rotation on direction vector
 16      ccdVec3Copy(&dir, _dir);
 17      ccdQuatInvert2(&qinv, &obj->quat);
 18      ccdQuatRotVec(&dir, &qinv);
 19  
 20      // compute support point in specified direction
 21      ccdVec3Set(v, ccdSign(ccdVec3X(&dir)) * box->x * CCD_REAL(0.5),
 22                    ccdSign(ccdVec3Y(&dir)) * box->y * CCD_REAL(0.5),
 23                    ccdSign(ccdVec3Z(&dir)) * box->z * CCD_REAL(0.5));
 24  
 25      // transform support point according to position and rotation of object
 26      ccdQuatRotVec(v, &obj->quat);
 27      ccdVec3Add(v, &obj->pos);
 28  }
 29  
 30  
 31  int main(int argc, char *argv[])
 32  {
 33      ...
 34  
 35      ccd_t ccd;
 36      CCD_INIT(&ccd); // initialize ccd_t struct
 37  
 38      // set up ccd_t struct
 39      ccd.support1       = support; // support function for first object
 40      ccd.support2       = support; // support function for second object
 41      ccd.max_iterations = 100;     // maximal number of iterations
 42  
 43      int intersect = ccdGJKIntersect(obj1, obj2, &ccd);
 44      // now intersect holds true if obj1 and obj2 intersect, false otherwise
 45  }

GJK + EPA - Penetration Of Two Objects

If you want to obtain also penetration info about two intersection objects ccdGJKPenetration() function can be used.
Procedure is almost same as for previous case:

  1  #include <ccd/ccd.h>
  2  #include <ccd/quat.h> // for work with quaternions
  3  
  4  /** Support function is same as in previous case */
  5  
  6  int main(int argc, char *argv[])
  7  {
  8      ...
  9      ccd_t ccd;
 10      CCD_INIT(&ccd); // initialize ccd_t struct
 11  
 12      // set up ccd_t struct
 13      ccd.support1       = support; // support function for first object
 14      ccd.support2       = support; // support function for second object
 15      ccd.max_iterations = 100;     // maximal number of iterations
 16      ccd.epa_tolerance  = 0.0001;  // maximal tolerance fro EPA part
 17  
 18      ccd_real_t depth;
 19      ccd_vec3_t dir, pos;
 20      int intersect = ccdGJKPenetration(obj1, obj2, &ccd, &depth, &dir, &pos);
 21      // now intersect holds true if obj1 and obj2 intersect, false otherwise
 22      // in depth, dir and pos is stored penetration depth, direction of
 23      // separation vector and position in global coordinate system
 24  }

MPR - Intersection Test

libccd also provides MPR - Minkowski Portal Refinement algorithm that can be used for testing if two objects intersects.
Procedure is similar to the one used for GJK algorithm. Support function is same but also function that returns center (or any point near center) of given object must be implemented:

  1  #include <ccd/ccd.h>
  2  #include <ccd/quat.h> // for work with quaternions
  3  
  4  /** Support function is same as in previous case */
  5  
  6  /** Center function - returns center of object */
  7  void center(const void *_obj, ccd_vec3_t *center)
  8  {
  9      obj_t *obj = (obj_t *)_obj;
 10      ccdVec3Copy(center, &obj->pos);
 11  }
 12  
 13  int main(int argc, char *argv[])
 14  {
 15      ...
 16      ccd_t ccd;
 17      CCD_INIT(&ccd); // initialize ccd_t struct
 18  
 19      // set up ccd_t struct
 20      ccd.support1       = support; // support function for first object
 21      ccd.support2       = support; // support function for second object
 22      ccd.center1        = center;  // center function for first object
 23      ccd.center2        = center;  // center function for second object
 24      ccd.mpr_tolerance  = 0.0001;  // maximal tolerance
 25  
 26      int intersect = ccdMPRIntersect(obj1, obj2, &ccd);
 27      // now intersect holds true if obj1 and obj2 intersect, false otherwise
 28  }

MPR - Penetration Of Two Objects

Using MPR algorithm for obtaining penetration info about two intersection objects is equally easy as in previous case instead ccdMPRPenetration() function is used:

  1  #include <ccd/ccd.h>
  2  #include <ccd/quat.h> // for work with quaternions
  3  
  4  /** Support function is same as in previous case */
  5  /** Center function is same as in prevous case */
  6  
  7  int main(int argc, char *argv[])
  8  {
  9      ...
 10      ccd_t ccd;
 11      CCD_INIT(&ccd); // initialize ccd_t struct
 12  
 13      // set up ccd_t struct
 14      ccd.support1       = support; // support function for first object
 15      ccd.support2       = support; // support function for second object
 16      ccd.center1        = center;  // center function for first object
 17      ccd.center2        = center;  // center function for second object
 18      ccd.mpr_tolerance  = 0.0001;  // maximal tolerance
 19  
 20      ccd_real_t depth;
 21      ccd_vec3_t dir, pos;
 22      int intersect = ccdMPRPenetration(obj1, obj2, &ccd, &depth, &dir, &pos);
 23      // now intersect holds true if obj1 and obj2 intersect, false otherwise
 24      // in depth, dir and pos is stored penetration depth, direction of
 25      // separation vector and position in global coordinate system
 26  }