I'm having a problem in my GJK implementation where support points reappear periodically in an endless loop, a situation described in pages 143 - 145 of Gino's book,
Collision Detection in Interactive 3D Environments. I have added the check for duplicate vertices described in page 145 of the book, but the code isn't catching all instances of such periodic behavior. The call looks like this:
Code: Select all
if (Y.includesVertex(support_point) || ...)
return v.magnitude();
As it currently stands, the call only checks for existing vertices with values exactly identical to the given support point. This is causing me problems, as I'm seeing periodic behavior involving close but not exactly equal support points. The values shown here are the vertices for the simplex
Y = union(W, support_point) through several iterations of the GJK loop:
Code: Select all
[0] {x = -245.196655, y = -4.026371}
[1] {x = 675.000366, y = -4.02598572}
[2] {x = 675, y = -4.02598572}
...
[0] {x = -245.196655, y = -4.026371}
[1] {x = 675, y = -4.02598572}
[2] {x = 675.000183, y = -4.02598572}
...
[0] {x = -245.196655, y = -4.026371}
[1] {x = 675.000183, y = -4.02598572}
[2] {x = 675.000366, y = -4.02598572}
...
[0] {x = -245.196655, y = -4.026371}
[1] {x = 675.000366, y = -4.02598572}
[2] {x = 675, y = -4.02598572}
... etc
It looks like this could be solved by checking for close values instead of identical values, but I don't know if that's the correct approach or whether I'm trying to compensate for a source of imprecision I'm not supposed to have. Is checking for close values a necessary part of a floating-point precision implementation of GJK, or is there something in my code I should be looking at as a source of precision issues?
What should a non-theoretical implementation of GJK do to address such behavior?