need help with robustness issues of ISA-GJK

[lilo]

Hi

I have implemented ISA-GJK according to Bergen's paper and it seems to work, but not so very well. It seems to be some robustness problems I think.

The algorithm finds a separating axis even though it should be none. This happens very frequently when I have a cube (8 vertices) and one is intersecting the other one. The amount of intersection is around 1 octant of the 2 cubes. Sometimes the algorithm works fine when I change to other polyhedra, like Icosahedron it works better but in some cases it still returns a separating axis even tough none should exist. When I debug the code, the newly looked up support point is already in the set of support points (simplex set W in Bergen's book. w is in Y).

To tell the truth I cannot understand the illconditioned cases that Bergen mentions (if it has something to do with it) but he said that by adding the check to see if w <- Y will remove one of the degenerate cases. This is also checked in ISA-GJK. In my cases this gives me incorrect intersection results.

My implementation uses a voronoi simplex solver and hill-climbing. Support point finding is done by inverse transforming direction vector to object space for both polyhedra and finding support point there and then they are transformed back to world space.

Did anyone had similar problems, and has a solution or is my implementation not robust enough, considering I use a voronoi simplex solver instead of cramer's rule? Is there some way to make it more robust?

Thanks!

[Erwin Coumans]

Pierre Terdiman created a testbed back in 2006 that shows failures with SOLID GJK and EPA here:
http://www.bulletphysics.org/Bullet/php ... =&f=&t=638

We ran into similar issues and fixed several issues to make Bullet more robust, but haven't documented this. If you are interested, just check the Bullet source code.
If you have test cases that fail also in the latest Bullet implementation, please share them.
Thanks,
Erwin

[lilo]

Thanks for answering!

I have been reading some more and come to the conclusion that the ill-conditioned cases that Bergen mentions can be solved as he suggests: By checking if the newly looked up support point w is already i Y, if that is the case, the GJK distance algorithm should terminate.

This is also the case for ISA-GJK, but in the book I think the test of this is placed in the wrong place and thus the termination condition is wrong (termination happens when newly added support point already is in set Y and in pseudo code this if statement is for finding a separating axis, so this is incorrect even tough his explanation of a solution is correct).

Instead I just added a separate if statement to return intersection whenever a newly looked up support point w already exist in set and return with a intersection. This solves one of the degenerate cases as Bergen mentions. I ran the code with previously mentioned polyhedra and it seems to work pretty good. It did not find a separating axis when there is intersection.

So what I mean is His pseudo code in his book is somewhat incorrect I think.

I have looked briefly into the source code of Bullet's voronoi simplex solver and have some remarks worth mentioning. Do not know if this is brought up here already but anyway.

I think that the voronoi simplex solver do not need to check all voronoi regions of a triangle and tetrahedron. The reason is that the newly added support point w is closer to the origin and thus the smallest set of simplex points to contain the shortest distance will have support point w as one of its point. So in the case of a triangle BCA, where A is the latest added support point. we know that the smallest set must contain A so the needed regions to be tested are: AB, AC, and A. Test of regions: BC, B and C are not needed because the origin cannot be there.

This remark comes from Bergen's paper about enhancing GJK (theorem 2) and also mentioned by Casey Muratori (http://mollyrocket.com/) in his implementation.

I have implementated such a voronoi simplex solver. It seems there are less tests (compared to Bullet) but the cons is that there will be more code (if you to not refactor to functions of course).

Thanks