Search code examples
javacollision-detection

Separating Axis Test for Axis-Aligned Bounding Box and Triangle produces incorrect results (3D)

I'm doing triangle to AABB intersection tests, and I'm taking this sample code from Real-Time Collision Detection by Christer Ericson. What the author says in the book before he gives the example is different from the example so I'm not sure how to test the remaining axes.. a01-a22.

Test: Nine axes given by the cross products of combination of edges from both.

// Test axes a00..a22 ( category 3 )
// Test axis a00
originDistance0 = triangle.point0.z * triangle.point1.y 
        - triangle.point0.y * triangle.point1.z;
originDistance2 = triangle.point1.z *( triangle.point1.y - triangle.point0.y ) 
        - triangle.point1.z * ( triangle.point1.z - triangle.point0.z );
projectionRadius = extent1 * Math.abs( edge0.z ) + extent2 * Math.abs( edge0.y );
if ( Math.max( -Math.max( originDistance0, originDistance2 ), Math.min( originDistance0, originDistance2 ) ) > projectionRadius ) {
    return false; // Axis is a separating axis
}

// Repeat similar tests for remaining axes a01..a22

So this is the test for the first axes. According to the book, these are the axes:

a00 = u0 × f0 = (1, 0, 0) × f0 = (0, -f0z, f0y)

a01 = u0 × f1 = (1, 0, 0) × f1 = (0, -f1z, f1y)

a02 = u0 × f2 = (1, 0, 0) × f2 = (0, -f2z, f2y)

a10 = u1 × f0 = (0, 1, 0) × f0 = (f0z, 0, -f0x)

a11 = u1 × f1 = (0, 1, 0) × f1 = (f1z, 0, -f1x)

a12 = u1 × f2 = (0, 1, 0) × f2 = (f2z, 0, -f2x)

a20 = u2 × f0 = (0, 0, 1) × f0 = (-f0y, f0x, 0)

a21 = u2 × f1 = (0, 0, 1) × f1 = (-f1y, f1x, 0)

a22 = u2 × f2 = (0, 0, 1) × f2 = (-f2y, f2x, 0)

============

p0 = V0 · a00

p1 = V1 · a00 = V1 = p0

p2 = V2 · a00 = V2

LEGEND: u = center vector, f = triangle edge vector. p = distances from the origin to the projections of the triangle vertices onto normal. V = triangle point.

How would the subsequent axes tests be calculated? Maybe if someone could do one I could have a better idea of the rest, but with only one example, I'm stuck.. Thanks!

EDIT: I tried the following.. for a00-a22 with no luck, the test still passes. First I added this code, and replace a00, and added a01-a22.

// Test axes a00..a22 ( category 3 )
Vector3d a00 = new Vector3d();
Vector3d a01 = new Vector3d();
Vector3d a02 = new Vector3d();
Vector3d a10 = new Vector3d();
Vector3d a11 = new Vector3d();
Vector3d a12 = new Vector3d();
Vector3d a20 = new Vector3d();
Vector3d a21 = new Vector3d();
Vector3d a22 = new Vector3d();
a00.cross( u0, edge0 );
a01.cross( u0, edge1 );
a02.cross( u0, edge2 );
a10.cross( u1, edge0 );
a11.cross( u1, edge1 );
a12.cross( u1, edge2 );
a20.cross( u2, edge0 );
a21.cross( u2, edge1 );
a22.cross( u2, edge2 );


// Test axes a00-a22
originDistance0 = triangle.point0.dot( a00 );
originDistance2 = triangle.point2.dot( a00 );
projectionRadius = extent1 * Math.abs( edge0.z ) + extent2 * Math.abs( edge0.y );
if ( Math.max( -Math.max( originDistance0, originDistance2 ), Math.min( originDistance0, originDistance2 ) ) > projectionRadius ) {
    return false; // Axis is a separating axis
}
...

EDIT 2: I also tried the following, which got me closer, but still did not get all intersections and got ones that shouldn't have. https://gist.github.com/3558420

UPDATE: Still not able to get correct intersection results. Looked over Eli's code, but it seems to be for 2d data and the terms are different so I'm not finding a connection between my code and his.

UPDATE 2: Additional attempts have been trying this code, which is like the defacto standard. I'm getting one intersection, when there should be 4 intersections, with 2 of those containing the points of the triangle, 3 containing the edges, and 1 just the plane.

The intersection that is caught has one point and two edges (plus plane). There is one other object that has the same characteristics, but different location, which does not get counted as intersecting. This is the data I'm working with, and the highlighted "voxel" is the one that gets returned as intersecting the triangle.

Intersection Data Image

Intersection result returned on following test categories:

Voxel1: None, passed all, returned with default "true".
Voxel2: Category 2
Voxel3: Category 3
Voxel4: Category 3
Voxel5: Category 3

UPDATE 3: Another implementation, better results

Ok, so after reading William Bittle's article at codezealot.org, I implemented the following:

public static boolean testTriangleAABB( Triangle triangle, BoundingBox boundingBox, double size ) {
    Vector3d[] triangleAxes = getAxes( triangle.getPoints() );
    Vector3d[] aabbVertices = getVertices( boundingBox, size );
    Vector3d[] aabbAxes = getAxes( aabbVertices );

    // loop over the triangleAxes
    for( int i = 0; i < triangleAxes.length; i++ ) {
      Vector3d axis = triangleAxes[ i ];
      // project both shapes onto the axis
      Projection p1 = project( triangle.getPoints(), axis );
      Projection p2 = project( aabbVertices, axis );
      // do the projections overlap?
      if ( !p1.overlap( p2 ) ) {
        // then we can guarantee that the shapes do not overlap
        return false;
      }
    }

    // loop over the aabbAxes
    for( int i = 0; i < aabbAxes.length; i++ ) {
      Vector3d axis = aabbAxes[ i ];
      axis.normalize();
      // project both shapes onto the axis
      Projection p1 = project( triangle.getPoints(), axis );
      Projection p2 = project( aabbVertices, axis );
      // do the projections overlap?
      if ( !p1.overlap( p2 ) ) {
        // then we can guarantee that the shapes do not overlap
        return false;
      }
    }
    // if we get here then we know that every axis had overlap on it
    // so we can guarantee an intersection
    return true;
}

The axes code:

public static Vector3d[] getAxes( Vector3d[] vertices ) {
    Vector3d[] axes = new Vector3d[ vertices.length ];
    // loop over the vertices
    for ( int i = 0; i < vertices.length; i++ ) {
        // get the current vertex
        Vector3d p1 = vertices[ i ];
        // get the next vertex
        Vector3d p2 = vertices[ i + 1 == vertices.length ? 0 : i + 1 ];
        // subtract the two to get the edge vector
        // edge vector can be skipped since we can get the normal by cross product.
        // get either perpendicular vector
        Vector3d normal = new Vector3d();
        normal.cross( p1, p2 );
        axes[ i ] = normal;
    }
    return axes;
}

And the overlap method from the projection class is as follows:

public boolean overlap( Projection projection ) {
    double test1;
    double test2;

    // and test if they are touching 
    test1 = min - projection.max;   // test min1 and max2 
    test2 = projection.min - max;   // test min2 and max1

    if( ( ( test1 > 0 ) || ( test2 > 0 ) ) ) {      // if they are greater than 0, there is a gap 
        return false;                               // just quit } 
    }
    return true;
}

Now I'm using another dataset, to fully test the intersection, since I got some false positives from my last dataset.

Triangle 0: true
Triangle 1: true
Triangle 2: true <-- should be false
Triangle 3: false
Triangle 4: false
Triangle 5: true

(true = intersecting..)

This is my dataset, which is labeled according to the results.

new aabb/triangle dataset

So my thought is that I'm not getting the right data because I'm testing the wrong axes/normals.. So I tried the following for the AABB and a slightly altered version for the triangles:

public static Vector3d[] getAABBAxes( Vector3d[] vertices ) {
    Vector3d[] axes = new Vector3d[ 6 ];
    // loop over the vertices
    for ( int i = 0; i < 6; i++ ) {
        // get the current vertex
        Vector3d p1 = vertices[ i ];
        // get the next vertex
        Vector3d p2 = vertices[ i + 1 == vertices.length ? 0 : i + 1 ];
        Vector3d p4 = vertices[ i + 3 == vertices.length ? 0 : i + 3 ];
        Vector3d edge1 = new Vector3d();
        Vector3d edge2 = new Vector3d();
        edge1.sub( p2, p1 );
        edge2.sub( p4, p1 );
        // subtract the two to get the edge vector
        // edge vector can be skipped since we can get the normal by cross product.
        // get either perpendicular vector
        Vector3d normal = new Vector3d();
        normal.cross( edge2, edge1 );
        normal.normalize();
        axes[ i ] = normal;
    }
    return axes;
}

I get this:

Triangle 0: true
Triangle 1: true
Triangle 2: false
Triangle 3: true <-- should be false
Triangle 4: true <-- should be false
Triangle 5: true

Solution

  • The reason that I was getting false positives for my tests was related to the triangle test.

    To test a triangle, which is a plane in 3D space, you have to test against 4 axes(aka normals).

    1. Surface Normal
      • The cross-product between two edges of the triangle.
    2. Edge Normal 1
      • The cross product between the surface normal and edge 1.
    3. Edge Normal 2
      • The cross product between the surface normal and edge 2.
    4. Edge Normal 3
      • The cross product between the surface normal and edge 3.

    So in the end, to get a proper (at least it is working correctly so far) collision test between a cube and a triangle, you have to perform 7 axes tests.

    Each test consists of checking the triangle and box vertices against the axis (normal). This can be broken down into a triangle and box test, and if one has a separating axis, then you don't have to do the other.

    Note: This test will only give you true/false results. No other data is provided.

    public static boolean testTriangleAABB( Triangle triangle, 
        Vector3d origin, double size ) {
    setTriangleNormal( triangle.getNormal( true ) );
    Vector3d[] aabbVertices = calculateAABBVertices( origin, size );

    // Triangle Normal axis test, false = No Collision.
    if( !testTriangleNormal( triangle, aabbVertices ) ) {
        return false;
    }

    // Triangle Edge Normals axis test, false = No Collision.
    if( !testTriangleEdgeNormals( triangle, aabbVertices ) ) {
        return false;
    }

    // Axis-Aligned Bounding Box X, Y, Z axis test, false = No Collision.
    if( !testAABBAxis( triangle, aabbVertices ) ) {
        return false;
    }     

    // if we get here then we know that every axis had overlap on it
    // so we can guarantee an intersection
    return true;
}

...

private static boolean testTriangleEdgeNormals( Triangle triangle, Vector3d[] aabbVertices ) {
    Vector3d edge = new Vector3d();
    Vector3d edgeNormal = new Vector3d();

    // loop over the triangle edge normals
    Vector3d[] points = triangle.getPoints();
    for( int i = 0; i < points.length; i++ ) {
        int iOverflow = i + 1 == points.length ? 0 : i + 1;
        edge.sub( points[ i ], points[ iOverflow ] );
        edge.normalize();
        edgeNormal.cross( getTriangleNormal(), edge );

        // project both shapes onto the axis
        projectionAABB = project2D1D( aabbVertices, edgeNormal );
        projectionTriangle = project2D1D( triangle.getPoints(), edgeNormal );
        // do the projections overlap?
        if ( !projectionAABB.hasOverlap( projectionTriangle ) ) {
            // then we can guarantee that the shapes do not overlap
            return false;
        }
    }
    return true;
}

    Furthermore, there is no need to calculate Axis-Aligned Bounding Box axes..since they are axis aligned the axes will be like so:

    private static final Vector3d[] AABB_AXES = { 
    new Vector3d( -1.0, 0.0, 0.0 ), 
    new Vector3d( 0.0, -1.0, 0.0 ),
    new Vector3d( 0.0, 0.0, -1.0 ) };