danfis / libccd Goto Github PK

should be -std=gnu99 so that libccd also compiles with icc. This should not be an issue fur g++ so if this could be fixed, it would be nice.

Cheers,
Arno

Hello,
first of all, I want to say a big thank you to danfis for the library.
I am completely new to the library and want to start to use it. I already installed it and I am trying to compile the example GJK - Intersection Test. However, I am encountering a linking problem with the lines:
CCD_INIT(&ccd); // initialize ccd_t struct
int intersect = ccdGJKIntersect(obj1, obj2, &ccd);
in the main function and the compiler is giving me the following error messages:
undefined reference to _imp__ccdFirstDirDefault' undefined reference to _imp__ccdGJKIntersect'

I did add the library libccd in my compiler so I don't understand why the compiler can't find those functions.
My questions may be trivial and maybe it is not right place to post it, but I couldn't find any help anywhere else.

I am using windows 7 and Mingw
Any help would be much appreciated.
Thank you in advance

I used the first method of compiling, i.e. cd src && make but this fails because CCD_EXPORT is not set. In detail:

$ make USE_DOUBLE=yes cc -Wall -pedantic --std=gnu99 -I. -fvisibility=hidden -c -o support.o support.c In file included from support.c:18:0: support.h:40:12: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘void’ CCD_EXPORT void __ccdSupport(const void *obj1, const void *obj2, ^ Makefile:35: recipe for target 'support.o' failed make: *** [support.o] Error 1

with

$ make --version GNU Make 4.1 Built for x86_64-pc-linux-gnu Copyright (C) 1988-2014 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html> This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law.
and
$ gcc --version gcc (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609 Copyright (C) 2015 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Build libccd as static library by Cmake 3.16.4.
Link library to my programm and got errors Fatal error: LNK1120 unresolved externals.
Visual Studio 2019
I tryed CCD_HIDE_ALL_SIMBOLS, but it did not help.

Could you please use CMAKE_INSTALL_DOCDIR instead of "${CMAKE_INSTALL_DATAROOTDIR}/doc/ccd" for documentation installation? This makes it easier to change the location when an other location is desired, e.g. in Gentoo.

See CMake documentation

#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
  }

so some issues.

• v is never defined. vec is never used (I assume v was supposed to be vec)
• cube is never defined. i believe obj was intended.
• why is a cube called obj_t? that makes reading harder.
• the ... in the main function should be removed and replaced with the code that initializes the cubes.

Hello:

At OSRF and GATech we are working into releasing DART software for different ubuntu platforms. DART depends on libccd so we need to package it as well. Let me ask some questions:

• Is libccd actively developed or at least maintained?
• Is there any previous work for releasing libccd into a .deb package format? If so, please could you point me to it.
• I'm happy to take care of setup the proper debian metadata for the package but I would like to know if the pull request will be merged in a reasonable time if I submit it.

Thanks very much.

Not building.

I am trying to use libccd for my QP-based physics simulator, because libccd is very clean and compact. Thank you very much for such a nice library.
(Previously, I used btGjkEpaSolver in bullet-2.68.)
In my tests, everything seemed to work perfectly, unless a box (or any other convex objects) is large.
When a box is large, box-box collision test works fine, but ccdGJKPeneration provides incorrect contact location. The contact normal and depth are accurate, and only the location is off.
This is so only when a box is much larger than the other box. For example, when one box is 5 meters big while the other box is 0.2 meter big, the results are always inconsistent and inaccurate.
I wonder if this is a known problem, or am I doing something wrong?
I wrote my code based on testsuites/boxbox.c, and used the ccdSupport function in testsuites/support.c.
I am using a Ubuntu machine. libccd was pulled from here a few days ago. (HASH:842646...)
But my code has other dependencies so I did not post here.

[UPDATE]
This issue has gone when I switched to ccdMPRPenetration. MPRPenetration seems to be less accurate about idepth though.

I am getting a segmentation fault when trying to implement ccdGJKPenetration. I think it is most probably because of the variable (nearest) that has been defined as a pointer but not allocated any memory. I am a beginner, so I would like you to provide your opinion on the same.

Hi,

I'm trying to build libccd in Windows using MSVC++. Everything seems to work fine except the MS compiler doesn't have any C99 features and is thus missing fmin/fminf/fmax/fmaxf. If I just change CCD_FMIN and CCD_FMAX to inline functions:

__inline ccd_real_t CCD_FMAX(ccd_real_t x, ccd_real_t y) { return x < y ? y : x; }
__inline ccd_real_t CCD_FMIN(ccd_real_t x, ccd_real_t y) { return x < y ? x : y; }

then the library compiles fine (please ignore the weird __inline syntax, I'm still trying to figure out a portable way to specify inline). I'm not suggesting this is the ideal solution, but I think a similar change is worthwhile to get the library to compile on Windows without modification.

The friends of debian are asking about the sources of the PDF file jgt98convex.pdf. They should be included in the tarball.

The last release v2.0 was made in March 2014. We recently realized that the wrong cmake parameter is being used in the libccd homebrew formulae ( flexible-collision-library/fcl#291 and Homebrew/homebrew-core#28434 ). The new parameter ENABLE_DOUBLE_PRECISION was being used, which is in the documentation and on the master branch, but is not yet released. I'm just checking to see if you are open to making another release so that released code will match the documentation.

Thanks!

In some cases, findPenetr() can cause a division by zero, generating NaN.

In mpr.c:331
If *depth is zero, then the ccdVec3Normalize() will divide by zero.

It should report "No Penetration" if the penetration depth is zero, or alternatively, generate a proper direction instead of dividing by zero.

>>> where
#0  0x0000555555607b59 in ccdVec3Normalize (d=0x7fffffffc500) at /home/bram/src/libccd/src/ccd/vec3.h:315
#1  findPenetr (obj1=0x7fffffffc550, obj2=0x7fffffffc590, ccd=0x7fffffffc4c0, portal=0x7fffffffc400, depth=0x7fffffffc4bc, pdir=0x7fffffffc500, pos=0x7fffffffc50c) at /home/bram/src/libccd/src/mpr.c:331
#2  0x00005555556033eb in ccdMPRPenetration (obj1=0x7fffffffc550, obj2=0x7fffffffc590, ccd=0x7fffffffc4c0, depth=0x7fffffffc4bc, dir=0x7fffffffc500, pos=0x7fffffffc50c) at /home/bram/src/libccd/src/mpr.c:144
#3  0x000055555559ca8c in ccdCollide (o1=o1@entry=0x555555873a90, o2=o2@entry=0x555555870550, flags=flags@entry=32, contact=contact@entry=0x7fffffffc650, obj1=obj1@entry=0x7fffffffc550, supp1=supp1@entry=0x55555559b390 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, obj2=0x7fffffffc590, supp2=0x55555559b390 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, skip=<optimized out>, cen2=0x55555559b5d0 <ccdCenter(void const*, ccd_vec3_t*)>, cen1=0x55555559b5d0 <ccdCenter(void const*, ccd_vec3_t*)>) at collision_libccd.cpp:339
#4  0x000055555559d1bb in ccdCollide (skip=<optimized out>, cen2=0x55555559b5d0 <ccdCenter(void const*, ccd_vec3_t*)>, supp2=0x55555559b390 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, obj2=0x7fffffffc590, cen1=0x55555559b5d0 <ccdCenter(void const*, ccd_vec3_t*)>, supp1=0x55555559b390 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, obj1=0x7fffffffc550, contact=0x7fffffffc650, flags=32, o2=0x555555870550, o1=0x555555873a90) at collision_libccd.cpp:319
#5  dCollideConvexConvexCCD (o1=0x555555873a90, o2=0x555555870550, flags=32, contact=0x7fffffffc650, skip=<optimized out>) at collision_libccd.cpp:457
#6  0x000055555555e3a9 in nearCallback (o1=<optimized out>, o2=<optimized out>, data=<optimized out>) at demo_convex.cpp:88
#7  0x0000555555569829 in collideAABBs (callback=<optimized out>, data=0x0, g2=0x555555870550, g1=0x555555873a90) at collision_space_internal.h:77
#8  dxHashSpace::collide (this=0x55555585e9e0, data=0x0, callback=0x55555555e490 <nearCallback(void*, dGeomID, dGeomID)>) at collision_space.cpp:569
#9  0x000055555555de2e in simLoop (pause=<optimized out>) at demo_convex.cpp:230
#10 0x0000555555562a26 in processDrawFrame (frame=0x7fffffffdc00, fn=<optimized out>) at x11.cpp:337
#11 0x00005555555630ab in dsPlatformSimLoop (window_width=window_width@entry=1920, window_height=window_height@entry=1080, fn=fn@entry=0x7fffffffde90, initial_pause=initial_pause@entry=0) at x11.cpp:416
#12 0x000055555556159f in dsSimulationLoop (argc=1, argv=0x7fffffffe038, window_width=1920, window_height=1080, fn=0x7fffffffde90) at drawstuff.cpp:1291
#13 0x000055555555d9b0 in main (argc=1, argv=0x7fffffffe038) at demo_convex.cpp:429

Hello.
Visual Studio 2019, Windows 10x64
In Cmake when I uncheck BUILD_SHARED_LIBS, I got many warnings C4273"inconsistent dll linkage" for all ccd functions.
Help me please...

Is it possible to get a contact manifold and not just a single point if two bodies are colliding in a line or patch contact?

On Windows fminf does not exist.

#ifdef WIN32 /* HACK Windows math.h may not define fminf so pretend it does */
#define CCD_FMIN(a,b) (a) < (b) ? (a) : (b)
#else
# define CCD_FMIN(x, y) (fminf((x), (y))) /*!< minimum of two floats */
#endif

Is there any example for collision detection between two convex polytopes?

GJKPenetration only gives information when in collision. Is there another function that would give the shortest distance between objects?

For windows/VC++ there is no need to explicitly link against the math library.
And find_library(MATH m) does not even work on this platform

I modified the CMakeList.txt as follows

if(NOT WIN32)
find_library(MATH m)
else()
set(MATH "")
endif()

The dist field in ccd_pt_el_t https://github.com/danfis/libccd/blob/master/src/polytope.h#L37 is actually the squared distance. To avoid confusion, would it be better to rename this variable as dist_squared?

Hello.

How upgrade MPRPenetration function so that it returns the depth of penetration in my vector?

The markdown page says return values are true/false when contact/not-contact, but several tests show the return values are 0/-1 respectively, so 0 corresponds to true and -1 correspond to false?
This is contradictory to the common C/C++ practice.

Hello, I found bug.

Unhandled exception at 0x00007FF6342D9F26 in Game.exe: 0xC0000005: Access violation reading location 0x0000000000000000.

https://i111.fastpic.ru/big/2020/0320/20/ea4db037dd71bda21188807856fb7d20.jpg

Visual Studio 2019, x64, Windows 10

In freak occurrences, ccdVec3PointTriDist2() can divide by zero.

If you collide often enough, at some point wv will equal rr as it was caught in the wild in my debugger, below:

Program received signal SIGFPE, Arithmetic exception.
─── Assembly ───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
0x000055555560cf39 ccdVec3PointTriDist2+1589 movss  -0x7f0(%rbp),%xmm2
0x000055555560cf41 ccdVec3PointTriDist2+1597 mulss  -0x7f0(%rbp),%xmm2
0x000055555560cf49 ccdVec3PointTriDist2+1605 subss  %xmm2,%xmm1
0x000055555560cf4d ccdVec3PointTriDist2+1609 divss  %xmm1,%xmm0
0x000055555560cf51 ccdVec3PointTriDist2+1613 movss  %xmm0,-0x7ec(%rbp)
0x000055555560cf59 ccdVec3PointTriDist2+1621 movss  -0x7ec(%rbp),%xmm1
0x000055555560cf61 ccdVec3PointTriDist2+1629 movss  0x20957(%rip),%xmm0        # 0x55555562d8c0
─── Expressions ────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
─── History ────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
─── Memory ─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
─── Registers ──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
   rax 0x00007fffffffbf70     rbx 0x00007fffffffc650     rcx 0x00007fffffffc46c     rdx 0x00007fffffffc448     rsi 0x00007fffffffc424     rdi 0x000055555584bc68     rbp 0x00007fffffffbfc0     rsp 0x00007fffffffb780      r8 0x00007fffffffc500 
    r9 0x00007fffffffc500     r10 0x0000555555866f10     r11 0x0000000000000000     r12 0x0000555555866d50     r13 0x00007fffffffc550     r14 0x00007fffffffc590     r15 0x00007fffffffc650     rip 0x000055555560cf4d  eflags [ PF ZF IF RF ]    
    cs 0x00000033              ss 0x0000002b              ds 0x00000000              es 0x00000000              fs 0x00000000              gs 0x00000000         
─── Source ─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
162     w = ccdVec3Dot(&d2, &d2);
163     p = ccdVec3Dot(&a, &d1);
164     q = ccdVec3Dot(&a, &d2);
165     r = ccdVec3Dot(&d1, &d2);
166 
167     s = (q * r - w * p) / (w * v - r * r);
168     t = (-s * r - q) / w;
169 
170     if ((ccdIsZero(s) || s > CCD_ZERO)
171             && (ccdEq(s, CCD_ONE) || s < CCD_ONE)
172             && (ccdIsZero(t) || t > CCD_ZERO)
─── Stack ──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
[0] from 0x000055555560cf4d in ccdVec3PointTriDist2+1609 at /home/bram/src/libccd/src/vec3.c:167
arg P = 0x55555584bc68 <__ccd_vec3_origin>
arg x0 = 0x7fffffffc424
arg B = 0x7fffffffc448
arg C = 0x7fffffffc46c
arg witness = 0x7fffffffc500
[1] from 0x0000555555607a45 in findPenetr+2858 at /home/bram/src/libccd/src/mpr.c:325
arg obj1 = 0x7fffffffc550
arg obj2 = 0x7fffffffc590
arg ccd = 0x7fffffffc4c0
arg portal = 0x7fffffffc400
arg depth = 0x7fffffffc4bc
arg pdir = 0x7fffffffc500
arg pos = 0x7fffffffc50c
[+]
─── Threads ────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
[1] id 8455 name demo_convex from 0x000055555560cf4d in ccdVec3PointTriDist2+1609 at /home/bram/src/libccd/src/vec3.c:167
────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
0x000055555560cf4d in ccdVec3PointTriDist2 (P=0x55555584bc68 <__ccd_vec3_origin>, x0=0x7fffffffc424, B=0x7fffffffc448, C=0x7fffffffc46c, witness=0x7fffffffc500) at /home/bram/src/libccd/src/vec3.c:167
167	    s = (q * r - w * p) / (w * v - r * r);
>>> where
#0  0x000055555560cf4d in ccdVec3PointTriDist2 (P=0x55555584bc68 <__ccd_vec3_origin>, x0=0x7fffffffc424, B=0x7fffffffc448, C=0x7fffffffc46c, witness=0x7fffffffc500) at /home/bram/src/libccd/src/vec3.c:167
#1  0x0000555555607a45 in findPenetr (obj1=0x7fffffffc550, obj2=0x7fffffffc590, ccd=0x7fffffffc4c0, portal=0x7fffffffc400, depth=0x7fffffffc4bc, pdir=0x7fffffffc500, pos=0x7fffffffc50c) at /home/bram/src/libccd/src/mpr.c:325
#2  0x00005555556033eb in ccdMPRPenetration (obj1=0x7fffffffc550, obj2=0x7fffffffc590, ccd=0x7fffffffc4c0, depth=0x7fffffffc4bc, dir=0x7fffffffc500, pos=0x7fffffffc50c) at /home/bram/src/libccd/src/mpr.c:144
#3  0x000055555559ca8c in ccdCollide (o1=o1@entry=0x555555866d50, o2=o2@entry=0x555555877160, flags=flags@entry=32, contact=contact@entry=0x7fffffffc650, obj1=obj1@entry=0x7fffffffc550, supp1=supp1@entry=0x55555559b390 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, obj2=0x7fffffffc590, supp2=0x55555559b390 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, skip=<optimized out>, cen2=0x55555559b5d0 <ccdCenter(void const*, ccd_vec3_t*)>, cen1=0x55555559b5d0 <ccdCenter(void const*, ccd_vec3_t*)>) at collision_libccd.cpp:339
#4  0x000055555559d1bb in ccdCollide (skip=<optimized out>, cen2=0x55555559b5d0 <ccdCenter(void const*, ccd_vec3_t*)>, supp2=0x55555559b390 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, obj2=0x7fffffffc590, cen1=0x55555559b5d0 <ccdCenter(void const*, ccd_vec3_t*)>, supp1=0x55555559b390 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, obj1=0x7fffffffc550, contact=0x7fffffffc650, flags=32, o2=0x555555877160, o1=0x555555866d50) at collision_libccd.cpp:319
#5  dCollideConvexConvexCCD (o1=0x555555866d50, o2=0x555555877160, flags=32, contact=0x7fffffffc650, skip=<optimized out>) at collision_libccd.cpp:457
#6  0x000055555555e3a9 in nearCallback (o1=<optimized out>, o2=<optimized out>, data=<optimized out>) at demo_convex.cpp:88
#7  0x0000555555569829 in collideAABBs (callback=<optimized out>, data=0x0, g2=0x555555877160, g1=0x555555866d50) at collision_space_internal.h:77
#8  dxHashSpace::collide (this=0x55555585e9e0, data=0x0, callback=0x55555555e490 <nearCallback(void*, dGeomID, dGeomID)>) at collision_space.cpp:569
#9  0x000055555555de2e in simLoop (pause=<optimized out>) at demo_convex.cpp:230
#10 0x0000555555562a26 in processDrawFrame (frame=0x7fffffffdc00, fn=<optimized out>) at x11.cpp:337
#11 0x00005555555630ab in dsPlatformSimLoop (window_width=window_width@entry=1920, window_height=window_height@entry=1080, fn=fn@entry=0x7fffffffde90, initial_pause=initial_pause@entry=0) at x11.cpp:416
#12 0x000055555556159f in dsSimulationLoop (argc=1, argv=0x7fffffffe038, window_width=1920, window_height=1080, fn=0x7fffffffde90) at drawstuff.cpp:1291
#13 0x000055555555d9b0 in main (argc=1, argv=0x7fffffffe038) at demo_convex.cpp:429
>>> l
162	    w = ccdVec3Dot(&d2, &d2);
163	    p = ccdVec3Dot(&a, &d1);
164	    q = ccdVec3Dot(&a, &d2);
165	    r = ccdVec3Dot(&d1, &d2);
166	
167	    s = (q * r - w * p) / (w * v - r * r);
168	    t = (-s * r - q) / w;
169	
170	    if ((ccdIsZero(s) || s > CCD_ZERO)
171	            && (ccdEq(s, CCD_ONE) || s < CCD_ONE)
>>> print w
$1 = 1.19620562
>>> print v
$2 = 0.0274525639
>>> print w*v
$3 = 0.0328389108
>>> print r
$4 = 0.181215093
>>> print r*r
$5 = 0.0328389108
>>> print w*v
$6 = 0.0328389108
>>> print r*r
$7 = 0.0328389108

Hi,

I am getting the following error:

cd src/
make 

cc -Wall -pedantic --std=gnu99 -I. -fvisibility=hidden  -c -o ccd.o ccd.c
In file included from ./ccd/ccd.h:21:0,
                 from ccd.c:20:
./ccd/vec3.h:35:4: error: #error You must define CCD_SINGLE or CCD_DOUBLE
 #  error You must define CCD_SINGLE or CCD_DOUBLE
    ^
./ccd/vec3.h:89:5: error: unknown type name ‘ccd_real_t’
     ccd_real_t v[3];
     ^
./ccd/vec3.h:106:25: error: unknown type name ‘ccd_real_t’
 _ccd_inline int ccdSign(ccd_real_t val);

... # More errors

ccd.c:133:12: warning: ‘penEPAPos’ defined but not used [-Wunused-function]
 static int penEPAPos(const ccd_pt_t *pt, const ccd_pt_el_t *nearest,
            ^
Makefile:37: recipe for target 'ccd.o' failed
make: *** [ccd.o] Error 1

Why is this happening? I am looking at whether the headers are being used but I am not familier with Makefile syntax enough to debug this. The thing is,for example: 'unknown type name ‘ccd_real_t’' should not be happening since ccd/vec3.h defines that type.

I think it has to do with the first line: # error You must define CCD_SINGLE or CCD_DOUBLE
but aren't these supposed to have defaults???? I tried make USE_SINGLE=yes but nothing changed. I am not sure where CCD_SINGLE is supposed to be defined.

This was from the git clone https://github.com/danfis/libccd.git file.

I believe there are problems in nextSupport function. What this function does is a part of the EPA algorithm. The EPA algorithm can be summarized as follows

1. Given two convex objects A and B, and we know that Minkowski difference A⊖B contains the origin, we want to find the smallest distance from the boundary of A⊖B to the origin. We start with an upper bound of the distance μ₀ = +∞, and a polytope whose vertices are on the boundary of A⊖B. This polytope also contains the origin.
2. At iteration i, find the point on the boundary of the polytope that is closest to the origin, denote this point as vᵢ.
3. Find the support point of the Minkowski difference A⊖B, along the direction of vᵢ. We denote this support point as wᵢ.
4. Update the distance upper bound μᵢ₊₁ = min(μᵢ, wᵢᵀvᵢ/|vᵢ|), and the lower bound as |vᵢ|.
5. Terminate until μᵢ - |vᵢ| ≤ ε. Then we are guaranteed that the distance we found is within ε to the true distance.

Given this is what EPA algorithm does, there are a few issues that confuse me in libccd's nextSupport function

1. The "touch contact" is detected in https://github.com/danfis/libccd/blob/master/src/ccd.c#L964~L966, that if el (which is the point on the boundary of the polytope that is nearest to the origin) is the origin. I do not think this is the right assertion. The condition for touch contact should be that the origin is on the boundary of the Minkowski difference A⊖B, not on the boundary of the polytope. The polytope is inside the Minkowski difference. When the origin is on the boundary of the polytope, it only means that the object A and B is in contact (or penetrating). We should continue to expand the polytope, until the difference between the distance upper bound and the lower bound is sufficiently small, instead of returning -1 here.
2. The dist is computed in https://github.com/danfis/libccd/blob/master/src/ccd.c#L973 as

    dist = ccdVec3Dot(&out->v, &el->witness);
   

   where out->v is wᵢ in the documentation above, and el->witness is vᵢ. I do not think the computation of dist is right. To compute the distance, I think el->witness should be normalized.
3. The termination condition in https://github.com/danfis/libccd/blob/master/src/ccd.c#L975 and https://github.com/danfis/libccd/blob/master/src/ccd.c#L992 have different meanings. In https://github.com/danfis/libccd/blob/master/src/ccd.c#L975, el->dist is the squared distance of the witness, while dist should be a non-squared distance. And even if we use squared distance for both dist and el->dist, I still do not think it is a good termination condition, since μᵢ² - |vᵢ|² ≤ ε says nothing about the difference between the upper bound μᵢ and the lower bound |vᵢ| (because both μᵢ and |vᵢ| can be arbitrarily large or arbitrarily small, thus making the difference μᵢ - |vᵢ| arbitrary.). On the other hand, the termination condition in https://github.com/danfis/libccd/blob/master/src/ccd.c#L992 is reasonable, as it means (μᵢ - |vᵢ|)² ≤ ε

$ CC=clang-10 CXX=clang++-10 ./configure --prefix=/opt/libccd
$ make
...
$ sudo make install
...
$ ls -R /opt/libccd
/opt/libccd:
lib

/opt/libccd/lib:
libccd.a  libccd.la

I expect both the library and the header files to get installed.

Hi everyone,

first of all thanks for this brilliant library! I am looking into the problem of collision detection for a project I am working on, specifically focusing on EPA. After looking up the original papers in which EPA was proposed, I still am a bit puzzled about the computation of the contact position, as it was not described in the seminal paper [1] and I also couldn't find any precise description of what is the principle behind this computation.

Looking into the code, it seems like an average over the support points from both objects is computed for the half of the vertices in the polytope closest to the origin:

Without explicitly knowing what's going on, this sounds like it computes some average between the two object boundaries. For what I have in mind it would be interesting to compute two individual points where each point is on the boundary of one object. If I understand the EPA algorithm correctly, these two points should then be joined by the direction return by EPA times the computed penetration depth (obviously with some approximation error).

My gut feeling (and one plot I investigated for some simple shapes) told me that I would need to compute

p_1 = pos + 0.5 * depth * dir
p_2 = pos - 0.5 * depth * dir

where pos, depth and dir are the values returned by ccdGJKPenetration.

Is this gut feeling correct? If so, can you enlighten me what's going on in the computation of the contact position in EPA? If there is some mathematical formulation of the idea I would be more than happy to read it.

Best regards
Pascal

[1] Van Den Bergen, Gino. "Proximity queries and penetration depth computation on 3d game objects." Game developers conference. Vol. 170. 2001.

In ccdVec3PointTriDist2

P: 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000
A: 0.06999979436939574029 -0.00000001708219171670 1.02781464659664711903
B: 0.06999979436939574029 -0.00000001708219171670 -0.81718535340335285433
C: -0.40000020563060423306 -0.00000002075754440556 1.02781464312938330963

the returned distance is different when we pass the witness points, versus setting witness=null.

When we set witness to null, the returned squared distance is 0. When we ask it to compute the witness point, the returned squared distance is 0.00000000000000031080. As we can see, all three points A, B and C have negative y value, hence the point P (origin) cannot have 0 distance to the triangle. ccdVec3PointTriDist2 computes the wrong value when the witness point is not passed in.

Inside the implementation of ccdVec3PointTriDist2, it wants to compute the distance from a point P to a triangle ABC. The way it does that is first to write the projection of point P on the plane coinciding with ABC as Q = A + s * AB + t * AC. In this test example, the point Q is inside the triangle ABC, so we only need to compute |PQ|² as the distance from P to ABC. The implementation takes different cod path to compute |PQ|².

1. When we ask the code to compute the witness point Q, the code first compute Q as Q = A + s * AB + t * AC, and then compute the squared norm of the vector PQ, as implemented in

   libccd/src/vec3.c

   Lines 182 to 189 in 7931e76

   	if (witness){
   	ccdVec3Scale(&d1, s);
   	ccdVec3Scale(&d2, t);
   	ccdVec3Copy(witness, x0);
   	ccdVec3Add(witness, &d1);
   	ccdVec3Add(witness, &d2);
   	dist = ccdVec3Dist2(witness, P);

2. When we don't ask the code to compute the witness point Q, the code expands the expression |PQ|² as |PQ|² = |PA + s * AB + t * AC|² = |PA|² + s²|AB|² + t² |AC|² + 2 st AB.dot(AC) + 2s * AB.dot(PA) + 2t * AC.dot(PA), it evaluates the summation of the quantities |PA|², s²|AB|², etc, as in the code

   libccd/src/vec3.c

   Lines 190 to 197 in 7931e76

   	}else{
   	dist = s * s * v;
   	dist += t * t * w;
   	dist += CCD_REAL(2.) * s * t * r;
   	dist += CCD_REAL(2.) * s * p;
   	dist += CCD_REAL(2.) * t * q;
   	dist += u;
   	}

   . This summation can cause numerical errors up to epsilon, when some of the quantities (like |PA|²) could be in the order of 1. The summation result end up being inaccurate. Hence although the squared distance should be non-zero, the summation result is 0.

The code path 1 (when computing the witness point Q) is numerically more robust. I think this is a bug as the distance result should be the same, with or without computing the witness point.

Hi,
I need to write a support function for convex meshes. Is there any sample code or implementation for this?. Can somebody give me some direction on this?. Thanks.

Hi,

I have just experimented a bit with your library and found a corner case in which gjk breaks. You can find the test case here:
https://github.com/Azrael3000/ccd-gjk-issue

The case is simply two cubes (sidelength 2) on top of each other (one with pos 0,0,0 the other with 0,0,1.9).

Output is:
GJK: intersect: 0 depth: 0.000000e+00
GJK: dir: -nan -nan -nan
GJK: pos: 0.000000e+00 0.000000e+00 9.500000e-01
MPR: intersect: 0 depth: 1.000000e-01
MPR: dir: 0.000000e+00 0.000000e+00 1.000000e+00
MPR: pos: 0.000000e+00 0.000000e+00 9.500000e-01

As can be seen MPR works without a problem but GJK yields the wrong depth and dir. Note that ccd was compiled with double precision accuracy. Have a look if you can reproduce it, otherwise I might try and find some time to actually run it with a fpe trap.

Cheers,
Azrael3000

Hi,
When I make it, it happens the errors:

/ccd/vec3.h:34:4: error: #error You must define CCD_SINGLE or CCD_DOUBLE
 #  error You must define CCD_SINGLE or CCD_DOUBLE
    ^
./ccd/vec3.h:88:5: error: unknown type name ‘ccd_real_t’
     ccd_real_t v[3];
...........

bellow are almost the ccd_real_t problem.
So how to fix it?

Hello.

ccdMPRPenetration() return wrong dir penetration depth.

Please, see this video, bright green stick - it's dir penetration:
https://youtu.be/vN_u3Ig1C2c

I think this is due to this problem: ccdVec3PointTriDist2 computes different distance with / without witness points. #55

Really need help.. I hope the project is not abandoned.

Hello,
I'm getting a lot of inconsistent dll linkage warnings during build master branch (pulled from repo today). Additionaly there are some locally defined symbol ... imported in function ... warnings too.
Is this normal?
I'm using Visual Studio 2015.

Here is build log:

1>------ Build started: Project: ZERO_CHECK, Configuration: Debug Win32 ------
1>  Checking Build System
1>  CMake does not need to re-run because D:/WORK/Projects/libccd-master/_BUILD/CMakeFiles/generate.stamp is up-to-date.
1>  CMake does not need to re-run because D:/WORK/Projects/libccd-master/_BUILD/src/CMakeFiles/generate.stamp is up-to-date.
2>------ Build started: Project: ccd, Configuration: Debug Win32 ------
2>  Building Custom Rule D:/WORK/Projects/libccd-master/src/CMakeLists.txt
2>  CMake does not need to re-run because D:\WORK\Projects\libccd-master\_BUILD\src\CMakeFiles\generate.stamp is up-to-date.
2>  ccd.c
2>D:\WORK\Projects\libccd-master\src\ccd.c(87): warning C4273: 'ccdFirstDirDefault': inconsistent dll linkage
2>  D:\WORK\Projects\libccd-master\src\ccd/ccd.h(75): note: see previous definition of 'ccdFirstDirDefault'
2>D:\WORK\Projects\libccd-master\src\ccd.c(92): warning C4273: 'ccdGJKIntersect': inconsistent dll linkage
2>  D:\WORK\Projects\libccd-master\src\ccd/ccd.h(96): note: see previous definition of 'ccdGJKIntersect'
2>D:\WORK\Projects\libccd-master\src\ccd.c(99): warning C4273: 'ccdGJKSeparate': inconsistent dll linkage
2>  D:\WORK\Projects\libccd-master\src\ccd/ccd.h(107): note: see previous definition of 'ccdGJKSeparate'
2>D:\WORK\Projects\libccd-master\src\ccd.c(177): warning C4273: 'ccdGJKPenetration': inconsistent dll linkage
2>  D:\WORK\Projects\libccd-master\src\ccd/ccd.h(124): note: see previous definition of 'ccdGJKPenetration'
2>  mpr.c
2>D:\WORK\Projects\libccd-master\src\mpr.c(100): warning C4273: 'ccdMPRIntersect': inconsistent dll linkage
2>  D:\WORK\Projects\libccd-master\src\ccd/ccd.h(131): note: see previous definition of 'ccdMPRIntersect'
2>D:\WORK\Projects\libccd-master\src\mpr.c(119): warning C4273: 'ccdMPRPenetration': inconsistent dll linkage
2>  D:\WORK\Projects\libccd-master\src\ccd/ccd.h(146): note: see previous definition of 'ccdMPRPenetration'
2>  polytope.c
2>D:\WORK\Projects\libccd-master\src\polytope.c(257): warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
2>  C:\Program Files (x86)\Windows Kits\10\Include\10.0.10586.0\ucrt\stdio.h(205): note: see declaration of 'fopen'
2>  support.c
2>  vec3.c
2>D:\WORK\Projects\libccd-master\src\vec3.c(133): warning C4273: 'ccdVec3PointSegmentDist2': inconsistent dll linkage
2>  D:\WORK\Projects\libccd-master\src\ccd/vec3.h(187): note: see previous definition of 'ccdVec3PointSegmentDist2'
2>D:\WORK\Projects\libccd-master\src\vec3.c(141): warning C4273: 'ccdVec3PointTriDist2': inconsistent dll linkage
2>  D:\WORK\Projects\libccd-master\src\ccd/vec3.h(197): note: see previous definition of 'ccdVec3PointTriDist2'
2>  Generating Code...
2>     Creating library D:/WORK/Projects/libccd-master/_BUILD/src/Debug/ccd.lib and object D:/WORK/Projects/libccd-master/_BUILD/src/Debug/ccd.exp
2>ccd.obj : warning LNK4217: locally defined symbol _ccdVec3PointSegmentDist2 imported in function _nextSupport
2>polytope.obj : warning LNK4217: locally defined symbol _ccdVec3PointSegmentDist2 imported in function _ccdPtDumpSVT2
2>ccd.obj : warning LNK4217: locally defined symbol _ccdVec3PointTriDist2 imported in function _doSimplex3
2>mpr.obj : warning LNK4049: locally defined symbol _ccdVec3PointTriDist2 imported
2>polytope.obj : warning LNK4217: locally defined symbol _ccdVec3PointTriDist2 imported in function _ccdPtDelVertex
2>  ccd.vcxproj -> D:\WORK\Projects\libccd-master\_BUILD\src\Debug\ccd.dll
2>  ccd.vcxproj -> D:/WORK/Projects/libccd-master/_BUILD/src/Debug/ccd.pdb (Full PDB)
3>------ Build started: Project: ALL_BUILD, Configuration: Debug Win32 ------
3>  Building Custom Rule D:/WORK/Projects/libccd-master/CMakeLists.txt
3>  CMake does not need to re-run because D:\WORK\Projects\libccd-master\_BUILD\CMakeFiles\generate.stamp is up-to-date.
========== Build: 3 succeeded, 0 failed, 0 up-to-date, 0 skipped ==========

Projects build report:
  Status    | Project [Config|platform]
 -----------|---------------------------------------------------------------------------------------------------
  Succeeded | ZERO_CHECK.vcxproj [Debug|Win32]
  Succeeded | src\ccd.vcxproj [Debug|Win32]
  Succeeded | ALL_BUILD.vcxproj [Debug|Win32]

Time Elapsed 00:00:01.455

EDIT
I think I've found what's the problem.
In compiler.h, line 33:
# ifdef libccd_EXPORTS
but if you look into preprocessor definitions in Visual Studio configuration properties you will find:
ccd_EXPORTS
I've changed manually ccd_EXPORTS to libccd_EXPORTS and compiler is no more complaining about inconsistent dll linkage 👍

$ pkg-config --cflags --libs ccd
-I/usr/local/include -L/usr/local/lib -lccd -lm 

libccd.so is already linked to libm.so:

$ ldd -a /usr/local/lib/libccd.so
/usr/local/lib/libccd.so:
	libm.so.5 => /lib/libm.so.5 (0x801208000)
	libc.so.7 => /lib/libc.so.7 (0x800823000)
/lib/libm.so.5:
	libc.so.7 => /lib/libc.so.7 (0x800823000)

There is no need to make the user program to also link with libm.so.

In src/ccd.c:323 it is likely to happen that the direction that is passed as the 3rd argument is not properly normalized. From the rest of the code it seems as if this not intended.

Adding a

      ccdVec3dNormalize(&dir);

in line 323 fixes it.

Hi,

This is a question rather than an issue.

I am trying to improve the performance of libccd support functions in ODE a bit by removing the unneeded transformations between world space and local space. While making these changes I noticed that in some cases the direction vector passed to support functions was normalized in ODE and in some cases it was not. I believe there is no need to normalize it as long as MPR is used at least it seems to be already normalized in portalDir(). Would you please confirm? Is it also the case for GJK? Should it be always expected to be a unit vector.

The full PR along with some discussions is available here - https://bitbucket.org/odedevs/ode/pull-requests/7/optimize-libccd-support-functions/diff#comment-13296486

Thanks,
Piotr

In the struct ccd_pt_vertex_t, it has a field edges. I assume this field means all the edges connecting to this vertex.

The edges of a vertex is changed in function
ccdPtAddEdge(ccd_pt_t* p, ccd_pt_vertex_t* v1, ccd_pt_vertex* v2).
Here edge->vertex_list[0] is appended to v1->edges, and edge->vertex_list[1] is appended to v2->edges.

I am confused by these two lines, for two reasons

1. I think we should append the newly created edge to v1->edges and v2->edges.
2. Neither edge->vertex_list[0] nor edge->vertex_list[1] were properly initialized, since the creation of edge , so edge->vertex_list[0] and edge->vertex_list[1] just contain garbage values. Why we want to append garbage values to v1->edges and v2->edges?

It is worth noting that ccd_pt_vertex_t.edges is not really used in the code, so it doesn't cause any damage, but still I think it is better to assign meaningful values to these variables.

I can submit a PR for this issue.

libccd is a nice collision detection library for convex shapes. Thanks to @danfis for this great work! I've been using libccd for many years through FCL for the collision detection of our multibody dynamics library DART.

Recently I'm interested in boosting the computational efficiency using SIMD, and would like to apply it to libccd as well. It would be done by replacing the built-in math codes of libccd with Eigen, which is a SIMD-enabled C++ linear algebra library. However, it is unable to switch the built-in math of libccd to Eigen as of now since libccd is written in C. That being said, to use Eigen, libccd needs to be ported to C++, then switch to Eigen. It wouldn't affect on this repository and would be placed in an another repository.

I wonder if @danfis or anyone would be interested in this work, but I'm willing to do it if @danfis don't mind. Please let me know how do you think.

Thanks in advance for any comment.

Get the following error:

[ 22%] Built target ccd
[ 29%] Built target cu
[ 33%] Linking C executable bench2
cu/libcu.a(cu.c.o): In function cuTimerStop': cu.c:(.text+0x73f): undefined reference to clock_gettime'
cu/libcu.a(cu.c.o): In function cuTimerStart': cu.c:(.text+0x72b): undefined reference to clock_gettime'
collect2: ld returned 1 exit status

I tried the boxstack demo in OpenDE and created cylinders (press 'y' key) and it was using libccd. After a while, libccd got stuck in a loop inside __ccdGJKEPA,
when enabling

One change I made to OpenDE to enable ccdGJKPenetration in collision_libccd:

res = ccdGJKPenetration(obj1, obj2, &ccd, &depth, &dir, &pos);
//res = ccdMPRPenetration(obj1, obj2, &ccd, &depth, &dir, &pos);

In the boxstackdemo, I enabled creation of one cylinder each simulation frame, and forced a fixed randseed of 2 (to make it reproducable on my machine).

static void simLoop (int pause)
{
dsSetColor (0,0,2);
dSpaceCollide (space,0,&nearCallback);
if (!pause) dWorldQuickStep (world,0.02);

static int frameCount = 0;
if (frameCount++<100)
command ('y');

if (write_world) {
FILE *f = fopen ("state.dif","wt");
if (f) {
dWorldExportDIF (world,f,"X");
fclose (f);
}
write_world = 0;
}

int main (int argc, char **argv)
{
dRandSetSeed(2);

OpenDE svn revision 1954, using its own libccd, and also using github libccd.

https://github.com/danfis/libccd/blob/master/doc/examples.rst

$ cc -o example example.c `pkg-config --cflags --libs ccd`
ex.c:11:5: error: use of undeclared identifier 'obj_t'
    obj_t *obj = (obj_t *)_obj;
    ^
ex.c:11:26: error: expected expression
    obj_t *obj = (obj_t *)_obj;
                         ^

Is there any ordering on the three edges, stored in ccd_pt_face_t? I want to compute the normal of a face, pointing away from the polytope. I compute the normal as n = e₁.cross(e₂), but this normal n does not necessarily points away from the polytope.

If the edges are always stored in a specific order (counter clockwise order, for example), then we can always guarantee the cross product e₁.cross(e₂) points away from the polytope. Does libccd guarantee such ordering? Is there a good way to always get the normal vector pointing away from the polytope?

Hello,

Per the instructions, I cloned the directory, navigated to source, ran make. The error I am getting is the following:

m4 -DUSE_DOUBLE ccd/config.h.m4 >ccd/config.h
/bin/sh: 1: m4: not found
make: *** [ccd/config.h] Error 127

Looking at the ccd folder, there is no config.h, so it is not surprising that it can't be found.

Am I missing something? I am running Ubuntu 14.04.

Thanks,

Scott

error: #error You must define CCD_SINGLE or CCD_DOUBLE
error: unknown type name 'ccd_real_t'

Any help regarding this error is appreciated.

Thanks