Physics Simulation Forum

 

All times are UTC




Post new topic Reply to topic  [ 3 posts ] 
Author Message
PostPosted: Wed Apr 19, 2017 5:23 pm 
Offline

Joined: Thu Jan 21, 2010 7:07 pm
Posts: 10
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:
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:
[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?


Top
 Profile  
 
PostPosted: Wed Apr 19, 2017 10:26 pm 
Offline
Site Admin
User avatar

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 4054
Location: California, USA
Adrian Lopez wrote:
What should a non-theoretical implementation of GJK do to address such behavior?


If you cycle vertices, it looks like you didn't make any progress. You should check if you get any closer to the origin at each iteration, or abort.
There are plenty of other issues with GJK, not the least a degenerate (near-zero volume) 4-vertex simplex (tetrahedron).

Each new termination condition you add will likely cause other issues (fail to find a solution while there is one, false positives) etc.


Top
 Profile  
 
PostPosted: Thu Apr 20, 2017 1:31 am 
Offline

Joined: Thu Jan 21, 2010 7:07 pm
Posts: 10
I'm not checking for progress toward the origin right now, but I'm doing everything suggested by Gino in his "numerical GJK" example. Also, I'm doing this in 2D so I exit as soon as the reduced simplex becomes a triangle.

Here's what my GJK function looks like right now, including all termination conditions provided in Gino's pseudocode:
Code:
float GJK::Distance(Vector2D &closest_point_a, Vector2D &closest_point_b, CollisionShape &a, const Vector2D &a_position, CollisionShape &b, const Vector2D &b_position)
{
   const float error_tolerance = std::numeric_limits<float>::epsilon() * 100.0;
   const float relative_error = std::numeric_limits<float>::epsilon() * 100.0;

   Simplex simplex;
   Simplex expanded_simplex;
   
   Vector2D v = a.arbitraryPoint(a_position) - b.arbitraryPoint(b_position);

   do {
      Vector2D sa = a.supportPoint(-v, a_position);
      Vector2D sb = b.supportPoint(v, b_position);

      Vector2D support = sa - sb;

      if (expanded_simplex.includesVertex(support) || v.magnitudeSquared() - v.dotProduct(support) <= relative_error * v.magnitudeSquared())
         return v.magnitude();
      
      expanded_simplex = simplex.Union(SimplexVertex(support, sa, sb));

      simplex = expanded_simplex.reducedSet(v, closest_point_a, closest_point_b, 0);

      if (simplex.length() == 0)
         return v.magnitude();
   } while (simplex.length() != 3 && v.magnitudeSquared() > error_tolerance * simplex.maximumVectorMagnitudeSquared());

   return 0;
}


When I started testing my code I was using only polytopes, so I've been operating under the assumption that the support function will always return a vertex from a fixed set (namely, the set of vertex differences between the two polytopes). This is true when both objects are polytopes, but in my latest test case I've been dealing with sphere vs polytope collisions, at which point the assumption no longer holds. I've only just realized this.

So, as it turns out, for objects like spheres and other continuous shapes there's really no choice but to add an epsilon when checking for repeated vertices in the simplex.


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

All times are UTC


Who is online

Users browsing this forum: No registered users and 3 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