I've been implementing the SAT based on:
On page 7, in the table, it refers the 15 axis to test so we can find a collision, but with just Ax, Ay and Az, I'm already getting collisions.
Why do i need to test all the other cases? Is there any situation where just Ax, Ay and Az are not enough?
You may be geting false positives. Collisions detected but not really colliding.
The number 15 comes from
The 9 axes are made up of cross products of edges of A and edges of B
The first 6 axes (from the face normals) are used to check if there a corner of one object is intersecting a face of the other object. (or more correctly to eliminate these kinds of collisions)
The set of 9 axes formed by the cross products of edges are used to consider edge on edge collision detection, where there is not a vertex penetrating the other object. Like the 'almost' collision in the photo below. Lets assume for the rest of this answer that the two boxes in the picture are not actually colliding, but are separated by a tiny distance.
Lets look at what happens if we just use the 6 face normals for SAT. The first image below shows one axis from the blue box and 2 axes from the yellow box. If we project both objects on to these axes, we will get an overlap on all three. The second image below shows the remaining two axes of the blue box and the remaining axis of the yellow box. Again projecting on these axes will show overlaps on all 3.
So just only checking the 6 face normals will show overlaps on all 6 axes, which, according to the SAT, means that the objects are colliding, because we have not been able to find a separation. But of course, these object are not colliding. The reason we have not found a separation is because we have not looked hard enough!
So how are we to find this gap? The image below show an axis on which projection of both objects will reveal a separation.
Where do we get this axis from?
If you imagine sliding a piece of stiff card into the gap, that card will be part of the separating plane. If we project on to the normal of that plane (black arrow in picture above), we will see the separation. We know what that plane is because we have two vectors which lie on that plane) One vector is aligned with the edge of blue and the other vector is aligned with the edge of yellow and as we all know the normal to a plane is simply the cross product of two vectors lying on the plane.
So for OOBBs we need to check every combination(9 of them) of cross products of the edges of the two objects to make sure we are not missing any edge-edge separations.
Ken's answer notes:
The 9 axes are made up of cross products of edges of A and edges of B
It's somewhat confusing to refer to the edges, as there are 12 edges compared to 6 normals, when you might as well use the three main normals for the very same output - the edges are all aligned with the normals, so I recommend using them instead!
Also note that normals pointing along the same axis, but in a different direction, are ignored, and thus we're left with three unique axes.
Another thing I'd like to add, is that you can optimize this calculation by exiting early if you find a separating axis, before you calculate all the axes you want to test. So, no, you don't need to test all axes in every case, but you do need to be ready to test them all :)
Here's a complete list of axes to test, given two OBBs, A and B, where x, y and z refer to the basis vectors / three unique normals. 0 = x axis, 1 = y axis, 2 = z axis
There's also a little caveat, that you should be aware of.
The cross product will give you a zero vector {0,0,0} when any two axes between the objects point in the same direction.
Also, since this part was left out, here's my implementation to check whether or not the projection is overlapping. There's probably a better way, but this worked for me! (Using Unity and its C# API)
// aCorn and bCorn are arrays containing all corners (vertices) of the two OBBs
private static bool IntersectsWhenProjected( Vector3[] aCorn, Vector3[] bCorn, Vector3 axis ) {
// Handles the cross product = {0,0,0} case
if( axis == Vector3.zero )
return true;
float aMin = float.MaxValue;
float aMax = float.MinValue;
float bMin = float.MaxValue;
float bMax = float.MinValue;
// Define two intervals, a and b. Calculate their min and max values
for( int i = 0; i < 8; i++ ) {
float aDist = Vector3.Dot( aCorn[i], axis );
aMin = ( aDist < aMin ) ? aDist : aMin;
aMax = ( aDist > aMax ) ? aDist : aMax;
float bDist = Vector3.Dot( bCorn[i], axis );
bMin = ( bDist < bMin ) ? bDist : bMin;
bMax = ( bDist > bMax ) ? bDist : bMax;
}
// One-dimensional intersection test between a and b
float longSpan = Mathf.Max( aMax, bMax ) - Mathf.Min( aMin, bMin );
float sumSpan = aMax - aMin + bMax - bMin;
return longSpan < sumSpan; // Change this to <= if you want the case were they are touching but not overlapping, to count as an intersection
}
working c# example based on Acegikmo's answer (using some unity api's):
using UnityEngine;
public class ObbTest : MonoBehaviour
{
public Transform A;
public Transform B;
void Start()
{
Debug.Log(Intersects(ToObb(A), ToObb(B)));
}
static Obb ToObb(Transform t)
{
return new Obb(t.position, t.localScale, t.rotation);
}
class Obb
{
public readonly Vector3[] Vertices;
public readonly Vector3 Right;
public readonly Vector3 Up;
public readonly Vector3 Forward;
public Obb(Vector3 center, Vector3 size, Quaternion rotation)
{
var max = size / 2;
var min = -max;
Vertices = new[]
{
center + rotation * min,
center + rotation * new Vector3(max.x, min.y, min.z),
center + rotation * new Vector3(min.x, max.y, min.z),
center + rotation * new Vector3(max.x, max.y, min.z),
center + rotation * new Vector3(min.x, min.y, max.z),
center + rotation * new Vector3(max.x, min.y, max.z),
center + rotation * new Vector3(min.x, max.y, max.z),
center + rotation * max,
};
Right = rotation * Vector3.right;
Up = rotation * Vector3.up;
Forward = rotation * Vector3.forward;
}
}
static bool Intersects(Obb a, Obb b)
{
if (Separated(a.Vertices, b.Vertices, a.Right))
return false;
if (Separated(a.Vertices, b.Vertices, a.Up))
return false;
if (Separated(a.Vertices, b.Vertices, a.Forward))
return false;
if (Separated(a.Vertices, b.Vertices, b.Right))
return false;
if (Separated(a.Vertices, b.Vertices, b.Up))
return false;
if (Separated(a.Vertices, b.Vertices, b.Forward))
return false;
if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Right, b.Right)))
return false;
if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Right, b.Up)))
return false;
if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Right, b.Forward)))
return false;
if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Up, b.Right)))
return false;
if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Up, b.Up)))
return false;
if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Up, b.Forward)))
return false;
if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Forward, b.Right)))
return false;
if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Forward, b.Up)))
return false;
if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Forward, b.Forward)))
return false;
return true;
}
static bool Separated(Vector3[] vertsA, Vector3[] vertsB, Vector3 axis)
{
// Handles the cross product = {0,0,0} case
if (axis == Vector3.zero)
return false;
var aMin = float.MaxValue;
var aMax = float.MinValue;
var bMin = float.MaxValue;
var bMax = float.MinValue;
// Define two intervals, a and b. Calculate their min and max values
for (var i = 0; i < 8; i++)
{
var aDist = Vector3.Dot(vertsA[i], axis);
aMin = aDist < aMin ? aDist : aMin;
aMax = aDist > aMax ? aDist : aMax;
var bDist = Vector3.Dot(vertsB[i], axis);
bMin = bDist < bMin ? bDist : bMin;
bMax = bDist > bMax ? bDist : bMax;
}
// One-dimensional intersection test between a and b
var longSpan = Mathf.Max(aMax, bMax) - Mathf.Min(aMin, bMin);
var sumSpan = aMax - aMin + bMax - bMin;
return longSpan >= sumSpan; // > to treat touching as intersection
}
}
