Finding the contact point with SAT

Question

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 1

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.

Answer 2

You want to use polygon clipping. This is best explained with pictures, which I don't have, but this guy did, so I'll let him explain it.

https://dyn4j.org/2011/11/contact-points-using-clipping/

The contact manifold will return a point on one of the objects that is "most responsible" for the collision, not the direct point of collision. However, you don't really need that direct collision point. You can simply push the objects apart using the penetration depth and normal you already have, and use the contact manifold to apply other physical affects (make the box tumble/roll down the slope, for instance).

Note that your picture illustrates a small problem: the point on the blue vector you're asking for will not be found in any physical simulation, because that isn't actually where the box would hit. The box would hit with it's bottom-left corner somewhere further up the slope as just a small bit of the corner penetrates.

The penetration depth will be relatively small, and simply pushing the box out of the slope along the penetration normal will put the box close enough to the "correct" position to be almost unnoticeable in practice, especially if the box is going to bounce, tumble, or slide afterward anyway.

Answer 3

Just project the MAT Vector onto the direction Vector. The resulting Vector can be added to the Direction Vector to compensate the penetration. Project it the same way, as you do on the Axis when doing the SAT. This sets the Object exactly on the position that it touches the other object. Add a small epsilon to fight floating point problems.

Answer 4

There are a couple of caveats to my answer, that I will get out of the way first: It only deals with non-rotating bounding boxes. It assumes that you are trying to deal with tunneling issues, i.e. issues caused by objects moving at high speed.

Once you have identified the MTV, you know the edge/surface normal you need to test against. You also know the linear velocity vector of the interpenetrating object.

Once you have established that at some point during the frame, an intersection occurred, you can then perform binary half step operations, based on the following starting points: Identify the vertex that penetrated first during the frame:

vec3 vertex;
float mindot = FLT_MAX;
for ( vert : vertices )
{
    if (dot(vert, MTV) < mindot)
    {
         mindot = dot(vert, MTV);
         vertex = vert;
    }
}

Once you have have the vertex identified, the binary half step becomes far less expensive:

//mindistance is the where the reference edge/plane intersects it's own normal. 
//The max dot product of all vertices in B along the MTV will get you this value.
halfstep = 1.0f;
vec3 cp = vertex;
vec3 v = A.velocity*framedurationSeconds;
float errorThreshold = 0.01f; //choose meaningful value here
//alternatively, set the while condition to be while halfstep > some minimum value
while (abs(dot(cp,normal)) > errorThreshold)
{            
    halfstep*=0.5f;
    if (dot(cp,normal) < mindistance) //cp is inside the object, move backward
    {
        cp += v*(-1*halfstep);
    }
    else if ( dot(cp,normal) > mindistance) //cp is outside, move it forward
    {
        cp += v*(halfstep);
    }
}

return cp;

This is reasonably accurate, but will only provide a single collision point, in a single case.

The thing is, it's usually possible to tell in advance if an object will move fast enough per frame to be able to tunnel like this, so the best advice is to identify the leading vertices along velocity and do a ray test along the velocity vector. In the case of rotating objects, you will have to do some kind of binary halfstep slerp in order to assertain the correct contact point.

In most cases, though, it can be safely assumed that most objects in your scene will not move fast enough to penetrate that far in a single frame, so no half stepping is necessary, and discrete collision detection will suffice. High speed objects like bullets, which move too fast to see, can be raytraced for contact points.

Interestingly, this halfstep method can also give you the (almost) exact time that the object occurred during the frame:

float collisionTime = frametimeSeconds * halfstep;

If you are doing some kind of physics collision resolution, you can then correct the position of A by:

v - (v*halfstep)

then you can do your physics normally from there. The downside is that if the object moves reasonably fast, you will see it teleporting back along it's velocity vector.

Answer 5

Let:

• cpv = Contact Point Vector
• mtv = Minimum Translation Vector
• vel = a unit vector for direction of velocity
• k = how long cpv is

Mathematically:

• (cpv - mtv) * mtv = 0
• cpv = k * vel

So we know:

• k = (mtv * mtv) / (vel * mtv)

Complexity should be O(1).