You could calculate the center of mass of both bodies and then calculate the collision between them.

As you're almost certainly aware, if two rigid bodies are overlapping then there is no single point of collision — there's an entire patch.

First of all, are you in 2d or 3d? For SAT to work you have to use convex bodies, so presumably that's exactly what you're doing?

My solution (as used by the little physics demonstration on my members.allegro.cc page, linked in my sig; check out the top entry on 'Directionless Pointers') was to calculate the minimum separation vector of the two bodies (i.e. the smallest amount that they can both be moved so as to no longer overlap), apply that and then use the final point at which the two are touching as a contact point. If the end result was that there was an edges of contact, I handled that by doing the calculations for a single contact point, located in the centre of the line.

The easiest way to get minimum separation is to work out the Minkowski sum of the two objects and find the quickest escape route. That's pretty trivial for convex shapes in 2d (as in my little physics thing), but relatively hard for non-convex and 3d shapes.

So, the exact solution from here depends on the type of shape you're dealing with. Any hints?

Yes, I'm in 2D and all my shapes are going to be convex.

Wow, that's a lot of stuff. My brain is too tired to read it. I think I'll go and check your demo first, then I'll return to read this.

Oh, I explicitly used the Minkowski Sum. The Minkowski Sum is the shape that would be formed if you took a stamp in the shape of one of the objects and printed it at every point contained in the other object. So, e.g. the Minkowski Sum of a rectangle and a circle is a bigger rectangle with rounded corners.

If you want to be formal then suppose A is made up of the collection of points {(x, y) s.t. (x, y) is inside object A} and B is made up of {(u, v) s.t. (u, v) is inside object B} then their Minkowski sum is made up of {(x+u, y+v} s.t. (x, y) is inside object A and (u, v) is inside object B}.

For objects A and B, what I actually use is the Minkowski Sum of A and -B. -B is the shape formed when you take every point (x, y) in B and reposition it at (-x, -y). Which, because of the way that basis vectors work, is the same thing as rotating B by a half circle. But thinking of it as (-x, -y) is more instructive.

If you calculate the sum of A and -B then you can use it to do an overlap test on A and B. Just check if the point (0, 0) is inside the sum. If it is then obviously there is at least one (x, y) that has the same value as at least one (u, v). So there is at least one place where the both the objects lie on top of each other.

If you move object A by (m, n) then the points (x+u, y+v) turn into (x+m+u, y+m+v). So movements on A directly move the sum by the same amount. Movements on B mov the sum of A and -B by the opposite amount.

Therefore, the shortest amount that you can move A to separate it from B is whatever the shortest vector is from (0, 0) to a point on the outside of the Minkowski Sum. Or you can move A by half the vector and B by half the vector in the other direction. Or whatever you want along those lines.

The "Convex Minkowski Sum Demo" on my page is possibly worth checking out here. It lets you manipulate the shape of two objects, shows you their sum and keeps them separated. Also, I think it's Allegro-based.

It uses a really simple winding algorithm. For each face of A, find the point of -B that is furthest in front of it when B is positioned on either endpoint of the face. Then move that face out by that much. That'll leave gaps where the corners of A were. Fill them in by using faces from B, with B positioned on the corner.

Specifically, if face 1 connects to face 2 at vertex q on object A, vertex n of object B is furthest in front of face 1 and vertem m is furthest in front of face 2 then add to the sum:

• a face that is equivalent to face 1, moved back or forth along its normal so that it crosses over vertex n when B is positioned on an endpoint of face 1

• the faces from B that run between vertices n and m, as they would appear if B was positioned at vertex q

• a face that is equivalent to face 2, moved back or forth along its normal so that it crosses over vertex m when B is positioned on an endpoint of face 2

It's maybe easier to think of graphically. Imagine taking object B and tracing round the outside of object A. Obviously the bit that sticks out furthest when going round the edges will print of the top of all the bits that are further inside. And at the corners you'll be left with whatever part of the outline of B normally falls between the sticky out bits.

Obviously if the shapes weren't convex then the answer would be more complicated.

Anyway, that gives you the sum without any difficult arithmetic — it's really just a sorting problem. Assuming the objects overlap then from that you can find the quickest escape vector from (0, 0) using normal 'distance to plane' stuff. Then you can push the objects apart.

A neat side effect is that when you're building the sum, each side is effectively the combination of a point from one object and a face from the other. When the objects are separted, that point will be in contact with that face.

Testing for face to face rubbing just means detecting when the sum has two faces in a row with the same normal. It's definitely not worth worrying about at first and can probably be ignored indefinitely.

EDIT: or use Stas B's approach for a pretty good approximation. This stuff gets harder in 3d, because it's harder to figure out what geometry to fill in at the corners. The best solution I've yet come up with is to duplicate lots of geometry at vertices and do a quickhull (minimum convex hull algorithm) on all that. This is partly related to the way that I've never managed to think of a better way to determine which faces of a convex 3d object are visible from a certain angle without testing every single one of them. Probably some people who are smarter, have read more or have thought about it for longer have some solutions to that sort of thing. I'm pretty sure it boils down to the fact that the faces of a convex 2d object are trivial to sort 'by normal', but the faces of a convex 3d object aren't. At least to me. So, waffle over, key point: approximations that map well to 3d are worth thinking about too.

I was confused by your suggestion to take points from both objects and idiotically incorporated the need to find a collision normal into my thoughts, because I'd started thinking about rigid body dynamics and not what the original author was asking.

I think our suggestions end up being pretty much the same thing if you add the fact that the axis of minimum overlap is actually a plane normal for one of the objects. Then the point you're looking for is the one from the other object that penetrates most deeply into that.

I'm not sure why you'd collect points from both objects. Probably I've misunderstood?

EDIT: oh, if you want to test for point to point collisions separately to point to edge collisions with the Minkowski Sum solution, just test whether the escape vector exists through a vertex of the sum. And then obviously use the escape vector itself as a collision normal, if you need one.

Surely whichever polygon owns the edge with the normal that provides the axis of minimum overlap is the one that supplies an edge, and specifically it supplies that edge?

EDIT:

Obviously you mean other than through the Minkowski Sum?

Hmm...I think I'm going to try using the Minkowski Sum. It seems interesting. I'll try to make a demo from it, so that I can understand how to use it. I think it's quite complicated, judging by the length of your post.

I've finally finished the demo, which I have already posted in the depot. I had problem understanding Thomas Harte's algorithm of calculating the minkowski sum polygon, so I just used the Monotone Chain algorithm to produce a convex polygon from the set of points produced from the minkowski sum of two polygons.