Is this 3D GJK intersection test code correct?

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
ConvexHull
Posts: 9
Joined: Sun Mar 10, 2013 5:03 pm

Is this 3D GJK intersection test code correct?

Post by ConvexHull »

Hi there,
Here's the link:
https://github.com/ChrisLundquist/CS143 ... mplex.java
I've recoded it in my application, but sometimes I'm getting false positives, while the other GJK implementation seem to be working fine.
What might be wrong with code from link? Is it my fault or it's there a bug?
Any help is welcomed
John Nagle
Posts: 12
Joined: Tue Aug 16, 2005 7:38 pm
Contact:

Re: Is this 3D GJK intersection test code correct?

Post by John Nagle »

The termination condition looks questionable. Termination for GJK is hard to get right. Back in the 1990s, Steven Cameron at Oxford and I struggled with this. See his web site for the code.

It's possible to get into states where the solver is moving through a sequence of adjacent supports. Are you exiting at

Code: Select all

if(loopCounter > MAX_ITTERATIONS)
                break;
If so, collision is undecided. Note when you exit there.

Objects for GJK need to be really convex. Coplanar triangles are a no-no, because they create ambiguity over which face belongs in the simplex. So you can't just use triangle meshes; you have to handle arbitrary polygons. In my Falling Bodies system, I used QHull to construct convex hulls, and required that there be at least a 1 degree angle across each edge. This guarantees convexity.

Single precision GJK is flaky. Use 64-bit floats. If you're using GJK in a physics engine, some objects will settle into the face-parallel condition, which results in small differences between large numbers and can lead to total loss of significance in 32-bit.
Post Reply