# Physics Simulation Forum

 Page 1 of 1 [ 3 posts ]
 Print view Previous topic | Next topic
Author Message
 Posted: Wed Apr 19, 2017 5:23 pm

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

 Posted: Wed Apr 19, 2017 10:26 pm

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 4054
Location: California, USA
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

 Posted: Thu Apr 20, 2017 1:31 am

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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 3 posts ]

#### Who is online

Users browsing this forum: No registered users and 3 guests

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

Search for:
 Jump to:  Select a forum ------------------ BULLET PHYSICS LIBRARY USERS    General Bullet Physics Support and Feedback    Release Announcements    Applications, Games, Demos or Movies using Bullet PHYSICS AUTHORING TOOLS, SERIALIZATION AND STANDARDS    Physics authoring tools, serialization, standards and related topics RESEARCH AND DEVELOPMENT IN COLLISION DETECTION & PHYSICS. Don't post Bullet support questions here!    Research and development discussion about Collision Detection and Physics Simulation    Links, Papers, Libraries, Demos, Movies, Comparisons       Non-technical forum and license/patent discussion    Career Opportunities