Page 1 of 1

Johnson's distance subalgorithm

Posted: Mon Jan 09, 2017 2:33 am
by tbabb
I'm following Johnson's distance subalgorithm of GJK collision detection as described in Gino Van Den Bergen's book--

I'm noticing that the "nearest point" routine occasionally (~1 in 20 occurrences) fails to select a sensible position, and so far I have only noticed this when the nearest simplex is a subset of the original. The selected point seems to be much smaller than the real geometric distance (i.e. nearly zero). Selecting the vertexes having del_j^X parameter > 0 seems to give the correct sub-simplex, htough. Re-running the "nearest point" routine on the pruned sub-simplex seems to return the correct answer as well.

It's difficult for me to reason about what might be the problem, as the linear algebra-based formulation is pretty abstract and removed from the geometry. Can anyone offer insight? What should I check?

thanks!

Re: Johnson's distance subalgorithm

Posted: Wed Jan 11, 2017 5:03 pm
by Dirk Gregorius
Difficult to say without any code and debugger. I would guess it might be a precision issue. It depends on what shapes you are testing and what floating point precision you are using.

I personally use a geometric simplex solver using barycentric coordinates to determine the Voronoi region. From there I reduce to the active sub-simplex depending on what region I find myself in. Pretty much as Erin shows in his GJK presentation here: http://box2d.org/files/GDC2010/GDC2010_ ... in_GJK.pdf

I am running in 32bit and I don't support any quadric shapes since they introduce numerical issues because of the unstable support functions. Spheres and capsules are handled simply as 1 and 2 points and the radius is added later. Still in very rare occasions I can have the simplex solver fail. E.g. the volume (determinant) of a 4 point simplex becomes zero. This happens when I didn't catch the case where the origin was already contained in the triangle simplex one iteration earlier. This is a very common error case (and can actually also happen at lower degree simplexes). At each iteration I save the current simplex. Then I run the simplex solver. If I run into problems (e.g. as mentioned above) I return a failure from the simplex solver and reset to the saved simplex and then exit. This has removed most issues for me.

For more information I recommend looking into Gino's book. It has great coverage of numerical issues in GJK. Running GJK in 32bit is a numerical challenge and will require some fiddling. In general I don't understand why you use Johnson's sub-algorithm. It is not faster or numerically more robust then a geometric approach. It removes the geometric understanding of the problem which makes failure cases harder to understand and debug. In my opinion it is the wrong choice for this problem.

HTH,
-Dirk

Re: Johnson's distance subalgorithm

Posted: Wed Jan 11, 2017 11:12 pm
by tbabb
Yep, I have Gino's book and I'm referring to that for my implementation.

I'm using double precision and still seeing issues. I am hesitant to suspect precision both because of that, and because the failure cases are so far off, geometrically, especially when compared to the apparent precision of the successes. There doesn't seem to be an in-between. It almost seems like there is a fundamental bogus assumption in the algorithm itself, which would explain why people report problems with robustness-- but I'd of course have to rule out an error on my part first.

I'm already handling the zero-determinant case; in general it implies that GJK has failed to "escape" the previous simplex, and added another point (or duplicate vertex) on the same face. I've found in this case it is generally safe to terminate with a non-intersecting condition. In cases where a sub-simplex "contains" the origin, this can be detected if the distance-to-simplex is exactly zero, which allows us to exit before the degenerate case emerges. In cases where precision causes the distance to be not-quite-zero, then we would again revert to a degenerate simplex in the following step and decide no intersection-- technically consistent, since the distance is finite-- or intersecting, after we proceed toward the interior of the minkowski volume and just barely envelop the origin. In any case, these are not the cases where I'm seeing Johnson's algorithm fail. I'm seeing much more egregious failures, like a nearly-zero distance measurement (1e-30) to a simplex several units away.

I'm using Johnson's algorithm because the rest of my code is dimension-agnostic. Johnson's algorithm is appealing because it is (at least procedurally) extremely simple and coordinate-free. I agree that it's lack of a geometric abstraction is a big detriment, and it's certainly why I'm having trouble. :)

I'll post some code (and maybe some images) here a bit later as soon as I have access to them.

Re: Johnson's distance subalgorithm

Posted: Thu Jan 12, 2017 12:22 am
by Dirk Gregorius
Gino released the Solid 3.5 source code on Github. I would run the failure cases against his code and see if it repeats there as well: https://github.com/dtecta/solid3

Sorry, as I never implemented Johnson I will not be able to help much. I try to ping Gino if he can help.