2D game collision response: SAT & minimum displacement along a given axis?

Question

I'm trying to implement a collision system in a 2D game I'm making. The separating axis theorem (as described by metanet's collision tutorial) seems like an efficient and robust way of handling collision detection, but I don't quite like the collision response method they use. By blindly displacing along the axis of least overlap, the algorithm simply ignores the previous position of the moving object, which means that it doesn't collide with the stationary object so much as it enters it and then bounces out.

Here's an example of a situation where this would matter:

According to the SAT method described above, the rectangle would simply pop out of the triangle perpendicular to its hypotenuse:

However, realistically, the rectangle should stop at the lower right corner of the triangle, as that would be the point of first collision if it were moving continuously along its displacement vector:

Now, this might not actually matter during gameplay, but I'd love to know if there's a way of efficiently and generally attaining accurate displacements in this manner. I've been racking my brains over it for the past few days, and I don't want to give up yet!

(Cross-posted from StackOverflow, hope that's not against the rules!)

Answer 1

Here's the method I found. It might be flawed, but I haven't found any problems with it yet in my cursory analysis. It also works for arbitrary polygons with a few minor modifications.

In the illustrations below, the blue object is moving and the red object is stationary. Step 1: For each polygon, find the two farthest points along the projection of that polygon onto the line perpendicular to the motion vector. Step 2: Divide each polygon along the line connecting these points. The half of the polygon that faces the other polygon along the motion vector is the "forward hull". This is the only part of the polygon that can possibly collide. Step 3: Project a vector from each point on each polygon's "forward hull" along the motion vector towards the opposite polygon, and check it for intersection with each edge of the opposite polygon's "forward hull". (Possibly slow, but computers are pretty fast nowadays -- right?) (Sorry about the tilted arrow. All the arrows should be parallel.) Step 4: Take the shortest vector. This is the exact collision distance. Step 5: Voila!

Answer 2

Check out this similar question: Collision Resolution

And also, from http://www.metanetsoftware.com/technique/tutorialA.html#section5 (which you posted a link to :) )

SECTION 5: Fast-Moving Objects

As mentioned above, small and/or fast-moving objects can produce problems when using a static collision test. There are several approaches that can be taken to handle such objects -- the simplest is to constrain your game design so that such objects aren't needed.

If you absolutely must have them, there are two common methods to deal with small and/or fast-moving objects: swept-collision tests, and multisampling.

--= sweep tests =--

Instead of testing for intersection between two static shapes, we can instead create new shapes by sweeping the original shapes along their trajectory, and testing for overlap between these swept shapes.

The basic idea is described in [Gomez], for circle-circle and AABB-AABB sweep tests.

--= multisampling =--

A much simpler alternative to swept tests is to multisample; instead of performing a single static test at the object's new position, perform several tests at several positions located between the object's previous and new position. This technique was used to collide the ragdoll in N.

If you make sure that the samples are always spaced at distances less than the object's radius, this will produce excellent results. In our implementation, we limit the maximum number of samples, so very high speeds will sometimes result in problems; this is something that can be tweaked based on your specific application.

EDIT

In summary and AFAIK, there are a few solutions

1. Limit your game to never have a small and/or fast moving object that can even cause this
2. Implement a system that stops collisions from actually happening, as described in the first link I posted
3. Increase your sampling rate for fast and/or small moving objects
4. ... possibly more, but I'm not an expert.

Answer 3

It depends if you only want linear movement, or if you need to cope with angular movement as well.

An alternative to using SAT:

In the case of linear only you can ray-cast against the Minkowski Difference of the two polygons from the origin in the direction of the delta linear velocity of the objects.

If the ray hits the MD, the two objects will collide and the hit point will tell you the time t at which they collided.

Now, if the objects are moving and rotating it gets more difficult, but you can still use a similar technique. Conservative Advancement will allow you to deal with this case. This technique is iterative; each iteration will generate a new MD and bring you closer to the time of intersection.

Here is the original draft paper on Conservative Advancement:

Continuous Collision Detection and Physics

I wrote an article explaining the technique in some detail here:

Collision detection for dummies

Hope these help!