Generating contacts with SAT

[hahanoob]

Hoping someone here might be able to give me some ideas I've been toying around with speculative contacts as described here. I'm using SAT to generate the contacts. The problem I'm running into is as follows:



The blue box is dynamic and the red and yellow boxes are static (my floor). The problem is that there's two possible speculative contacts to be found between the blue and red box. Using the X-axis as the separating axis gives me a contact with n = <1, 0, 0> and distance = 0. Using the Y-axis as a separating axis gives me a contact with n = <0, 1, 0> and distance = 0. The contact I choose comes down to the order I test the axis. If I test the Y-axis first then I'm fine. When I test the X-axis I see the distance is no further than my existing best contact and I ignore it. If it's the other way around I'll end up stuck on the seam between the red and yellow box. I can just always test the Y-axis first but then my problem becomes sliding along walls instead of the floor.

Here's a snippet from my SAT routine if it's not clear how I'm finding the contacts:

Code: Select all

				
ShapeUtils.GetProjectionInterval(shapeA, axis, out min1, out max1);
ShapeUtils.GetProjectionInterval(shapeB, axis, out min2, out max2);
float dist = ShapeUtils.GetIntervalDistance(min1, max1, min2, max2);
if (dist > bestContact.Distance)
{
	bestContact.Normal = (Vector3.Dot(displacement, axis) < 0) ? -axis : axis;
	bestContact.Distance = dist;
}

How does one handle this? If I were generating contacts only on intersection I don't think this would be a problem assuming I resolved contacts with the closest bodies first.

[Erwin Coumans]

It looks like you are hitting 'internal edges', this is a difficult problem. One solution/workaround is to adjust the contact normals afterwards, using additional information.

For triangle meshes, you can compute concave/convex internal edge information for this. For touching objects, you will need to perform some analysis, either manually or automatically, to recognize this case.

There are some slides in my GDC presentation that deal with this. Also see the 'internal edge utility' in Bullet, in Bullet/Demos/InternalEdgeDemo. Although it only deals with triangle meshes, the general idea can be applied to internal edges of neighboring objects.
Thanks,
Erwin