ccdGJKPenetration can hang forever

[erwincoumans]

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.

[danfis]

Hi Erwin, thanks for the bug report. The issue should be solved in next version (1.5).

The problem was in insufficient stopping criteria in cycle where is built a polytope around the origin (core of EPA algorithm). The algorithm generated support points that does not improve the polytope, but continued to do so. The change I did should solve the problem. However, I think my implementation of the whole EPA thing should be revisited -- it seems too much complicated to me. I was thinking of getting some inspiration in Bullet, but I'm not sure when I will get to it...

I also prepared a patch for ODE (svn rev 1954) that incorporates libccd v1.5 (now there is 1.0): http://www.danfis.cz/files/0001-Ported-libccd-v1.5.patch

Are you in contact with ODE upstream regarding the bug or should I push the patch through their mailing list?

[erwincoumans]

Hi Daniel,

I just took a quick look at libccd, mainly to use your MPR file in Bullet 3 on GPU, using OpenCL: https://github.com/erwincoumans/bullet3/blob/master/src/Bullet3Collision/NarrowPhaseCollision/shared/b3MprPenetration.h I mainly use SAT and contact clipping on GPU, but for objects with many edges, I needed a faster edge-edge test.

I ran into that GJK/EPA issue when doing a quick test out of curiosity. I'm not using your GJK/EPA or ODE.

It was easy to move MPR to OpenCL, especially because your implementation can easily switch math library, did you intentionally write vec.h for that purpose? Thanks, Erwin

On 12 January 2014 07:52, Daniel Fiser notifications@github.com wrote:

Hi Erwin, thanks for the bug report. The issue should be solved in next version (1.5).

The problem was in insufficient stopping criteria in cycle where is built a polytope around the origin (core of EPA algorithm). The algorithm generated support points that does not improve the polytope, but continued to do so. The change I did should solve the problem. However, I think my implementation of the whole EPA thing should be revisited -- it seems too much complicated to me. I was thinking of getting some inspiration in Bullet, but I'm not sure when I will get to it...

I also prepared a patch for ODE (svn rev 1954) that incorporates libccd v1.5 (now there is 1.0): http://www.danfis.cz/files/0001-Ported-libccd-v1.5.patch

Are you in contact with ODE upstream regarding the bug or should I push the patch through their mailing list?

— Reply to this email directly or view it on GitHubhttps://github.com/danfis/libccd/issues/7#issuecomment-32125448 .

[danfis]

Ok, I will deal with ODE myself. I realized that maybe they don't need any changes because MPR is there hard-coded as default option and I'm not sure there were any changes since version they have. But I will send the patch anyway to keep them up-date and for the case you just experienced.

Originaly vec.h is from my other project where I wanted to be able to switch to other implementations of math routines (e.g., SSE implemented directly by gcc intristics). So, it comes natural that it can be switched to other implementations, I guess. I'm glad it made your work easier. Maybe if I find some time I will port you OpenCL implementation back to libccd ;).

Cheers, Dan