GJK: reappearing support points and termination condition

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
Adrian Lopez
Posts: 10
Joined: Thu Jan 21, 2010 7:07 pm

GJK: reappearing support points and termination condition

Post by Adrian Lopez »

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?
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: GJK: reappearing support points and termination conditio

Post by Erwin Coumans »

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.
Adrian Lopez
Posts: 10
Joined: Thu Jan 21, 2010 7:07 pm

Re: GJK: reappearing support points and termination conditio

Post by Adrian Lopez »

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: Select all

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.
Post Reply