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