1# libccd [](https://travis-ci.org/danfis/libccd) 2 3***libccd*** is library for a collision detection between two convex shapes. 4libccd implements variation on Gilbert–Johnson–Keerthi algorithm plus Expand 5Polytope Algorithm (EPA) and also implements algorithm Minkowski Portal 6Refinement (MPR, a.k.a. XenoCollide) as described in Game Programming Gems 7. 7 8libccd is the only available open source library of my knowledge that include 9MPR algorithm working in 3-D space. However, there is a library called 10[mpr2d](http://code.google.com/p/mpr2d/), implemented in D programming 11language, that works in 2-D space. 12 13libccd is currently part of: 14 151. [ODE](http://www.ode.org/) library (see ODE's *./configure --help* how to enable it), 162. [FCL](http://www.ros.org/wiki/fcl) library from [Willow Garage](http://www.willowgarage.com/), 173. [Bullet3](http://bulletphysics.org/) library (https://github.com/bulletphysics/bullet3). 18 19For implementation details on GJK algorithm, see 20http://www.win.tue.nl/~gino/solid/jgt98convex.pdf. 21 22 23## Dependencies 24 25This library is currently based only on standard libraries. 26The only exception are testsuites that are built on top of CU 27(https://github.com/danfis/cu) library licensed under LGPL, however only 28testing depends on it and libccd library itself can be distributed without it. 29 30 31## License 32 33libccd is licensed under OSI-approved 3-clause BSD License, text of license 34is distributed along with source code in BSD-LICENSE file. 35Each file should include license notice, the rest should be considered as 36licensed under 3-clause BSD License. 37 38 39## Compile And Install 40 41libccd contains several mechanisms for compiling and installing. Using a simple Makefile, using autotools, and using CMake. 42 43### 1. Using Makefile 44 45Directory src/ contains Makefile that should contain everything needed for compilation and installation: 46```sh 47 $ cd src/ 48 $ make 49 $ make install 50``` 51 52Library libccd is by default compiled in double precision of floating point numbers - you can change this by options *USE_SINGLE/USE_DOUBLE*, i.e.: 53```sh 54 $ make USE_SINGLE=yes 55``` 56will compile library in single precision. 57 58Installation directory can be changed by options PREFIX, INCLUDEDIR and LIBDIR. 59For more info type 'make help'. 60 61### 2. Using Autotools 62 63libccd also contains support for autotools: 64Generate configure script etc.: 65```sh 66 $ ./bootstrap 67``` 68 69Create new build/ directory: 70```sh 71 $ mkdir build && cd build 72``` 73 74Run configure script: 75```sh 76 $ ../configure 77``` 78 79Run make and make install: 80```sh 81 $ make && make install 82``` 83 84configure 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). 85 86### 3. Using CMake 87 88To build using `make`: 89```sh 90 $ mkdir build && cd build 91 $ cmake -G "Unix Makefiles" .. 92 $ make && make install 93``` 94 95To build using `ninja`: 96```sh 97 $ mkdir build && cd build 98 $ cmake -G Ninja .. 99 $ ninja && ninja install 100``` 101 102Other build tools may be using by specifying a different generator. For example: 103```sh 104 $ cmake -G Xcode .. 105``` 106 107```bat 108 > cmake -G "Visual Studio 14 2015" .. 109``` 110 111To compile using double precision, set the `ENABLE_DOUBLE_PRECISION` option: 112```sh 113 $ mkdir build && cd build 114 $ cmake -G "Unix Makefiles" -DENABLE_DOUBLE_PRECISION=ON .. 115 $ make && make install 116``` 117 118To build libccd as a shared library, set the `BUILD_SHARED_LIBS` option: 119```sh 120 $ mkdir build && cd build 121 $ cmake -G "Unix Makefiles" -DBUILD_SHARED_LIBS=ON .. 122 $ make && make install 123``` 124 125To build the test suite, set the `BUILD_TESTING` option: 126```sh 127 $ mkdir build && cd build 128 $ cmake -G "Unix Makefiles" -DBUILD_TESTING=ON .. 129 $ make && make test 130``` 131 132The installation directory may be changed using the `CMAKE_INSTALL_PREFIX` variable: 133```sh 134 $ mkdir build && cd build 135 $ cmake -G "Unix Makefiles" -DCMAKE_INSTALL_PREFIX=/path/to/install .. 136 $ make && make install 137``` 138 139## GJK - Intersection Test 140 141This section describes how to use libccd for testing if two convex objects intersects (i.e., 'yes/no' test) using Gilbert-Johnson-Keerthi (GJK) algorithm. 142 143Procedure is very simple (and is similar for usages of library): 144 1451. Include *<ccd/ccd.h>* file. 1462. Implement support function for specific shapes. Support function is function that returns furthest point from object (shape) in specified direction. 1473. Set up *ccd_t* structure. 1484. Run ccdGJKIntersect() function on desired objects. 149 150Here is skeleton of simple program: 151```cpp 152 #include <ccd/ccd.h> 153 #include <ccd/quat.h> // for work with quaternions 154 155 /** Support function for box */ 156 void support(const void *obj, const ccd_vec3_t *dir, ccd_vec3_t *vec) 157 { 158 // assume that obj_t is user-defined structure that holds info about 159 // object (in this case box: x, y, z, pos, quat - dimensions of box, 160 // position and rotation) 161 obj_t *obj = (obj_t *)_obj; 162 ccd_vec3_t dir; 163 ccd_quat_t qinv; 164 165 // apply rotation on direction vector 166 ccdVec3Copy(&dir, _dir); 167 ccdQuatInvert2(&qinv, &obj->quat); 168 ccdQuatRotVec(&dir, &qinv); 169 170 // compute support point in specified direction 171 ccdVec3Set(v, ccdSign(ccdVec3X(&dir)) * box->x * CCD_REAL(0.5), 172 ccdSign(ccdVec3Y(&dir)) * box->y * CCD_REAL(0.5), 173 ccdSign(ccdVec3Z(&dir)) * box->z * CCD_REAL(0.5)); 174 175 // transform support point according to position and rotation of object 176 ccdQuatRotVec(v, &obj->quat); 177 ccdVec3Add(v, &obj->pos); 178 } 179 180 int main(int argc, char *argv[]) 181 { 182 ... 183 184 ccd_t ccd; 185 CCD_INIT(&ccd); // initialize ccd_t struct 186 187 // set up ccd_t struct 188 ccd.support1 = support; // support function for first object 189 ccd.support2 = support; // support function for second object 190 ccd.max_iterations = 100; // maximal number of iterations 191 192 int intersect = ccdGJKIntersect(obj1, obj2, &ccd); 193 // now intersect holds true if obj1 and obj2 intersect, false otherwise 194 } 195``` 196 197## GJK + EPA - Penetration Of Two Objects 198 199If you want to obtain also penetration info about two intersection objects ccdGJKPenetration() function can be used. 200 201Procedure is almost same as for previous case: 202```cpp 203 #include <ccd/ccd.h> 204 #include <ccd/quat.h> // for work with quaternions 205 206 /** Support function is same as in previous case */ 207 208 int main(int argc, char *argv[]) 209 { 210 ... 211 ccd_t ccd; 212 CCD_INIT(&ccd); // initialize ccd_t struct 213 214 // set up ccd_t struct 215 ccd.support1 = support; // support function for first object 216 ccd.support2 = support; // support function for second object 217 ccd.max_iterations = 100; // maximal number of iterations 218 ccd.epa_tolerance = 0.0001; // maximal tolerance fro EPA part 219 220 ccd_real_t depth; 221 ccd_vec3_t dir, pos; 222 int intersect = ccdGJKPenetration(obj1, obj2, &ccd, &depth, &dir, &pos); 223 // now intersect holds 0 if obj1 and obj2 intersect, -1 otherwise 224 // in depth, dir and pos is stored penetration depth, direction of 225 // separation vector and position in global coordinate system 226 } 227``` 228 229## MPR - Intersection Test 230 231libccd also provides MPR - Minkowski Portal Refinement algorithm that can be used for testing if two objects intersects. 232 233Procedure 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: 234```cpp 235 #include <ccd/ccd.h> 236 #include <ccd/quat.h> // for work with quaternions 237 238 /** Support function is same as in previous case */ 239 240 /** Center function - returns center of object */ 241 void center(const void *_obj, ccd_vec3_t *center) 242 { 243 obj_t *obj = (obj_t *)_obj; 244 ccdVec3Copy(center, &obj->pos); 245 } 246 247 int main(int argc, char *argv[]) 248 { 249 ... 250 ccd_t ccd; 251 CCD_INIT(&ccd); // initialize ccd_t struct 252 253 // set up ccd_t struct 254 ccd.support1 = support; // support function for first object 255 ccd.support2 = support; // support function for second object 256 ccd.center1 = center; // center function for first object 257 ccd.center2 = center; // center function for second object 258 ccd.mpr_tolerance = 0.0001; // maximal tolerance 259 260 int intersect = ccdMPRIntersect(obj1, obj2, &ccd); 261 // now intersect holds true if obj1 and obj2 intersect, false otherwise 262 } 263``` 264 265 266## MPR - Penetration Of Two Objects 267 268Using MPR algorithm for obtaining penetration info about two intersection objects is equally easy as in previous case instead ccdMPRPenetration() function is used: 269```cpp 270 #include <ccd/ccd.h> 271 #include <ccd/quat.h> // for work with quaternions 272 273 /** Support function is same as in previous case */ 274 /** Center function is same as in prevous case */ 275 276 int main(int argc, char *argv[]) 277 { 278 ... 279 ccd_t ccd; 280 CCD_INIT(&ccd); // initialize ccd_t struct 281 282 // set up ccd_t struct 283 ccd.support1 = support; // support function for first object 284 ccd.support2 = support; // support function for second object 285 ccd.center1 = center; // center function for first object 286 ccd.center2 = center; // center function for second object 287 ccd.mpr_tolerance = 0.0001; // maximal tolerance 288 289 ccd_real_t depth; 290 ccd_vec3_t dir, pos; 291 int intersect = ccdMPRPenetration(obj1, obj2, &ccd, &depth, &dir, &pos); 292 // now intersect holds 0 if obj1 and obj2 intersect, -1 otherwise 293 // in depth, dir and pos is stored penetration depth, direction of 294 // separation vector and position in global coordinate system 295 } 296``` 297
){kind=link}