How to resolve collisions of compound shapes using SAT?

Question

SAT is a decent way to determine collisions between arbitrary convex polygons. You'll even get the vector that is needed to resolve a collision.

To resolve collisions between complex (non-convex) shapes, I was thinking about some sort of compound-shape which consists of several convex polygons. If a collision occurs in the broad-phase (eg. circle vs. circle or AABB vs AABB), the collision would be resolved by checking each polygon in the compound shape vs. each polygon in the other compound shape.

I wonder what's the best way to actually separate the objects though? A naive approach would be to just take the vector with the highest magnitude and use that for separation. In the following picture, this would be V₂

However if the separating vectors point into different directions, the collision cannot be resolved right away and might require several iterations. So in the next picture we would separate using V₁ and in another iteration by V₂ (or something close to V₂, as the shape would have moved by the amount of V₁).

This approach will fail with separating vectors that point into the opposite direction of each other or in a case like shown in the following picture:

Here we would iterate endlessly between the state on the left and the state on the right.

So to ask an actual question here: What's a reasonable approach to this problem? I guess using compound polygons for complex shapes is a reasonable idea but I really wonder how collisions should be resolved in that case? How do I detect a dead-end as shown in the third image?

Answer 1

I think you may be trying to fit a square key into a round hole by applying SAT in the way you are, here. Obviously, it's not designed for concave-concave collisions, and though I commend your effort to adapt it for that purpose, there are considerations that make this unlikely to work.

Realism

Angular impulse and it's knock-on effects are the name of the game here.

The order of contact points is important for realistic collision resolution. In the real world, one of those points is always going to strike before another. And it's only in emulating that contact order and the results of each "subcollision" represented by that, that you can expect to get a realistic result in simulation. This is one of the very reasons why you are breaking down your concave into convex, in the first place -- it allows piecewise detection of which part has struck first. Of course, this can also be emulated as per my comment under the "Less realism" heading.

Your convex fixtures combine to give the object both it's outline and its centroid (and of course in more complex simulations, each fixture can affect the density differently, as well). The reason I mention this is that in resolving collisions realistically, you are going to have to calculate not only linear but also angular impulse, following each "sub collision" of your contact points. It is not as simple as the basic "push apart" you apply with SAT.

This then completely changes the nature of your problem, because as you can see, it is pointless getting and trying to use 2 or more contact points, because really it is only the first one that matters. Once you have then resolved the first in terms of linear and angular impulse, you will need to recalculate for further collisions, because the orientations of each object will have changed. Further to that, detecting each individual contact in the step then may or may not need to be done within that same step -- depending on the timing between contacts as the objects' first contact point touches, subsequent linear and angular impulse is applied, second contact point touches, and so on.

Less realism

Of course, assuming you are not at all interested in resolving for angular impulse, then the best you can do with SAT becomes essentially exactly what you would do if you wrapped these polygons as convex using something like Graham's Scan: Pushing apart by the single separating vector. In other words, it makes little sense to be trying to resolve three vectors in tandem, as you've demonstrated. It's the biggest in the bunch that counts.

EDIT in response to your question

What you need to do if you want a simplistic approach is as follows:

• Determine the correct direction of displacement. This is most easily done by convex hulling each, and determining the normals to the separating axis.

• Now you need to determine the displacement magnitude. Why can't we just use the magnitude as given by SAT? Because if you think about it, the interpenetration depths are going to be potentially greater for convex hulls, than they will be for their matched concave hulls -- think of two E's with their teeth in each other! As you've done above, find all contact points for a given step, but find them parallel to the axis normals, because this is the correct direction of displacement. Now determine which one of these parallel overlap vectors is longest. Displace by that one, discard the rest and proceed to next physics step.