Occasional missed collisions in GJK (fixed)

Post Reply
peterk
Posts: 14
Joined: Mon Dec 15, 2008 6:52 pm

Occasional missed collisions in GJK (fixed)

Post by peterk » Wed Jan 07, 2009 5:39 pm

Hi,

I'm using the GJK routine from Bullet to generate collisions between convex hulls. For my simulation, it's crucial for stability that even single collision events aren't missed. However what I'm seeing is that very occasionally, obviously penetrating shapes return no collision results. My question is, is this an inherent floating point accuracy issue with GJK/EPA, or possibly just a bug in the Bullet implementation? Does GJK struggle with degenerate cases such as coincident or nearly coincident objects?

Cheers.

User avatar
Erwin Coumans
Site Admin
Posts: 4223
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Occasional missed collisions in GJK

Post by Erwin Coumans » Wed Jan 07, 2009 7:36 pm

We recently fixed a bug that might cause your issue. Assuming you are using the latest Bullet 2.73 sp1 release, and not the SVN trunk, can you change the lines 151 in Bullet/src/BulletCollision/NarrowPhaseCollision/btGjkPairDetector.cpp into:

Code: Select all

                        // potential exit, they don't overlap
                        if ((delta > btScalar(0.0)) && (delta * delta > squaredDistance * input.m_maximumDistanceSquared)) 
                        {
                                checkSimplex=true;
                                //checkPenetration = false;
                                break;
                        }
peterk wrote: My question is, is this an inherent floating point accuracy issue with GJK/EPA, or possibly just a bug in the Bullet implementation? Does GJK struggle with degenerate cases such as coincident or nearly coincident objects?
Are you using the default collision margin? Setting it to zero might lead to failures. Also, the GJK algorithm struggles with large size ratios, over 1:1000 (testing a tiny convex shape against a huge convex shape).
If this doesn't help, can you please provide a reproduction case in one of the Bullet demos, such as EPAPenDepthDemo for example?
Thanks,
Erwin

peterk
Posts: 14
Joined: Mon Dec 15, 2008 6:52 pm

Re: Occasional missed collisions in GJK

Post by peterk » Thu Jan 08, 2009 3:49 pm

That patch seems to have completely fixed the problem for me Erwin, many thanks!

Incidentally, I am setting the margin to 0 as well although this doesn't seem to cause an obvious problem in my tests. What sort of issues would I experience with GJK if I have a zero margin? What is the significance of the 0.04 default value?

Thanks again,
Pete

Post Reply