Physics Simulation Forum

 

All times are UTC




Post new topic Reply to topic  [ 4 posts ] 
Author Message
PostPosted: Mon Jan 09, 2017 2:33 am 
Offline

Joined: Mon Jan 09, 2017 2:14 am
Posts: 3
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!


Top
 Profile  
 
PostPosted: Wed Jan 11, 2017 5:03 pm 
Offline

Joined: Sun Jul 03, 2005 4:06 pm
Posts: 871
Location: Kirkland, WA
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


Top
 Profile  
 
PostPosted: Wed Jan 11, 2017 11:12 pm 
Offline

Joined: Mon Jan 09, 2017 2:14 am
Posts: 3
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.


Top
 Profile  
 
PostPosted: Thu Jan 12, 2017 12:22 am 
Offline

Joined: Sun Jul 03, 2005 4:06 pm
Posts: 871
Location: Kirkland, WA
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 4 posts ] 

All times are UTC


Who is online

Users browsing this forum: Yahoo [Bot] and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group