Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I've been implementing the SAT based on: http://www.geometrictools.com/Documentation/DynamicCollisionDetection.pdf for 3D collisions

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?

share|improve this question

2 Answers 2

up vote 25 down vote accepted

You may be geting false positives. Collisions detected but not really colliding.

The number 15 comes from

  • 3 axes from object A (face normals)
  • 3 axes from object B (face normals)
  • 9 axes from all the pairs of edges of A and edges of B (3x3)
  • =15 in total

The 9 axes are made up of cross products of edges of A and edges of B

  1. Ae1 x Be1 (Edge 1 of A cross edge 1 of B)
  2. Ae1 x Be2
  3. Ae1 x Be3
  4. Ae2 x Be1
  5. ... and so on

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.

enter image description here

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!

enter image description here enter image description here

So how are we to find this gap? The image below show an axis on which projection of both objects will reveal a separation.

enter image description here

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.

share|improve this answer
2  
+1 just for the pictures :P –  GriffinHeart Nov 26 '12 at 19:32

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

  1. a0
  2. a1
  3. a2
  4. b0
  5. b1
  6. b2
  7. cross( a0, b0 )
  8. cross( a0, b1 )
  9. cross( a0, b2 )
  10. cross( a1, b0 )
  11. cross( a1, b1 )
  12. cross( a1, b2 )
  13. cross( a2, b0 )
  14. cross( a2, b1 )
  15. cross( a2, b2 )

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
}
share|improve this answer
    
Welcome to the site. Please check out the help center, and note in particular that this site isn't a forum and that "replying" to other answers is not a good idea (because your "reply" may not appear before the post you are replying to). It's better to write your answers in a way that stand alone, and use comments if you specifically want to clarify an existing post. –  Josh Petrie Jan 11 at 17:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.