collision detection - Finding the contact point with SAT

The Separating Axis Theorem (SAT) makes it simple to determine the Minimum Translation Vector, i.e., the shortest vector that can separate two colliding objects. However, what I need is the vector that separates the objects along the vector that the penetrating object is moving (i.e. the contact point).

I drew a picture to help clarify. There is one box, moving from the before to the after position. In its after position, it intersects the grey polygon. SAT can easily return the MTV, which is the red vector. I am looking to calculate the blue vector.

My current solution performs a binary search between the before and after positions until the length of the blue vector is known to a certain threshold. It works but it's a very expensive calculation since the collision between shapes needs to be recalculated every loop.

Is there a simpler and/or more efficient way to find the contact point vector?

Answer

What you're talking about is fairly difficult if you structure it as first moving an object, then testing for collision, then backing off until you're out of the object. It's probably better to think of this as a dynamic intersection test: a moving object against a stationary object.

Luckily, separating axis tests can help you here! Here's a description of the algorithm, courtesy of Ron Levine:

The algorithm goes like this. You work with the relative velocity vector of the two convex bodies. Projecting each of the two bodies and the relative velocity vector onto a particular separating axis at t₀ gives two 1-D intervals and a 1-D velocity, such that it is easy to tell whether the two intervals intersect, and if not, whether they are moving apart or moving together. If they are separated and moving apart on any of the separating axes (or, in fact, on any axis whatever), then you know that there is no future collision. If on any separating axis the two projected intervals intersect at t₀ or are separated and are moving together, then it is easy to compute (by two simple 1D linear expressions) the earliest future time at which the two intervals will first intersect and (assuming continuing rectilinear motion) the latest future time at which the two intervals will last intersect and begin moving apart. (If they are intersecting at t₀ then the earliest future intersection time is t₀). Do this for at most all the separating axes. If the maximum over all the axes of the earliest future intersection time is less than the minimum over all the axes of the latest future intersection time then that maximum earliest future intersection time is the exact time of first collision of the two 3D polyhedra, otherwise there is no collision in the future.

In other words, you loop through all the axes that you normally would in a static separating axis test. Instead of early-outing if you find no overlap, you keep going and check the projected velocity of the moving object. If it's moving away from the static object, then you early-out. Otherwise, you can solve for the earliest and latest time of contact fairly easily (it's one 1D interval moving towards another 1D interval). If you do that for all axes and keep the maximum of the earliest intersection time and the minimum of the latest intersection time, then you know if your moving object will hit the static object, as well as when. So you can advance your moving object exactly up to the point at which it will hit the static object.

Here's some rough and entirely unverified pseudocode for the algorithm:

t_min := +∞
t_max := -∞
foreach axis in potential_separating_axes
    a_min := +∞
    a_max := -∞
    foreach vertex in a.vertices
        a_min = min(a_min, vertex · axis)
        a_max = max(a_max, vertex · axis)

    b_min := +∞
    b_max := -∞
    foreach vertex in b.vertices
        b_min = min(b_min, vertex · axis)
        b_max = max(b_max, vertex · axis)
    v := b.velocity · axis
    if v > 0 then
        if a_max < b_min then
            return no_intersection
        else if (a_min < b_min < a_max) or (b_min < a_min < b_max) then

            t_min = min(t_min, (a_max - b_min) / v)
            t_max = max(t_max, 0)
        else
            t_min = min(t_min, (a_max - b_min) / v)
            t_max = max(t_max, (a_min - b_max) / v)
    else if v < 0 then
        // repeat the above case with a and b swapped
    else if v = 0 then
        if a_min < b_max and b_min < a_max then
            t_min = min(t_min, 0)

            t_max = max(t_max, 0)
        else
            return no_intersection
if t_max < t_min then
    // advance b by b.velocity * t_max
    return intersection
else
    return no_intersection

Here's a Gamasutra article talking about this implemented for a few different primitive tests. Note that just like SAT, this requires convex objects.

Also, this is a fair bit more complicated than a simple separating axis test. Be absolutely sure you need it before you try it. A very large number of games simply push the objects out of each other along the minimum translation vector, because they simply don't penetrate very far into each other on any given frame and it's pretty much unnoticeable visually.