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?

• Are you dead set on using SAT? Algorithms like MPR (Minkowski Portal Refinement) can find the contact manifold directly. With SAT and GJK, you need a separate algorithm to calculate the contact points. – Sean Middleditch Apr 6 '12 at 10:46
• – bobobobo Aug 20 '13 at 0:54

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.

• This is all very cool, but it didn't directly answer the question about calculating the contact manifold. Also, if I understand it correctly, this answer only works with linear velocity, and hence can't support rotating objects; not sure if the question asker wants that or not. – Sean Middleditch Apr 6 '12 at 10:39
• @seanmiddleditch That's true, it neglects rotations over the frame. You have to rotate instantaneously at the beginning. But no method that I know short of conservative advancement actually deals accurately with rotations. Given no rotation, though, it produces a better estimate of the contact point. – John Calsbeek Apr 6 '12 at 15:47

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.

http://www.codezealot.org/archives/394

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.

• Do you know if there's a way to calculate that "blue vector" (the one required to push the object back out of the shape along the velocity vector) using SAT? – Tara Jun 29 '15 at 3:22
• @Dudeson: not using SAT, no. That's not what SAT does. SAT gives you the edge of minimal penetration depth, not the first contact edge. You'd have to use swept shape collision detection to do what you're asking, I think. – Sean Middleditch Jun 29 '15 at 7:49
• I know what SAT does. I have implemented it before. But there's a problem I'm facing that would be solved if I could just use the SAT's output to compute the first contact edge. Also see "someguy"'s answer. It suggests it's possible but doesn't explain it very well. – Tara Jun 29 '15 at 12:00
• @Dudeson: The edge/axis of least penetration is not necessarily the edge of first contact, so I still don't see how SAT helps here. I'm by no means an expert in this topic so I admit that I could just be wrong. :) – Sean Middleditch Jun 30 '15 at 2:36
• Exactly. That's why I'm not sure if this is even possible. That would imply though, that someguy's answer is just wrong. But thanks for the help anyway! :D – Tara Jun 30 '15 at 6:09

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.

• "MAT Vector"? Do you mean "MTV"? – Tara Jun 27 '15 at 3:34

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.