GJK simplex solving

[John McCutchan]

Hey, I just thought I would mention something I have noticed when playing around with different simplex solving methods.

I built a test program which fills the simplex with 1,2,3, or 4 points and then gets the closest point on the simplex to the origin. (The tetrahedron simplex isn't tiny or really oblong). I rotate the simplex around slowly. The program draws the simplex and the vector v found by different simplex solving methods.

I tested 6 solvers:

1,2,3) My three different implementations "Ginos" method.
4) Sold 3.5.4 implementation
5) My implementation of voronoi based simplex solver based on the book Real Time Collision Detection and some refinement found in bullet
6) Bullet's voronoi simplex solver.

1-4) fail - often - when it does fail v is a vertex of the simplex (new simplex is a point). I am not sure why this happens.
5-6) seem to work great, the vector v smoothly moves around the simplex.

So, from my experience the voronoi solver method is MUCH better. It could be argued that there is a bug in methods 1,2, or 3 but method 4 should be solid (no pun intended).

Can anyone reproduce this or am I missing something?

[Dirk Gregorius]

I just looked into this topic as well lately and it seems that the original GJK code (Johnson's Fortran code converted to C by Ruspini) already used the Voronoi simplex solver. Why did Gino actually prefered his method, even though the Voronoi stuff is around for such a long time and seems to work so much better?