Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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 V2

SAT example 1

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 V1 and in another iteration by V2 (or something close to V2, as the shape would have moved by the amount of V1).

SAT example 2

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:

SAT example 3

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?

share|improve this question
    
Can you clarify what you want to use the vector for? –  Will Sep 12 '11 at 17:08
    
@Will The vector should be used to resolve the collision, so that the shapes no longer overlap. So I could move the yellow object by the resulting vector and the two objects would no longer collide. –  bummzack Sep 12 '11 at 17:23

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
I think I see what you mean. So in the "less realism" scenario I wouldn't just evaluate the (shortest) vectors given by SAT for the individual polygons but I would also have to consider the other (larger) overlaps, and in the worst case using the convex hull? –  bummzack Sep 12 '11 at 18:57
    
See (latest) edit. –  Nick Wiggill Sep 12 '11 at 19:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.