title: Separating Axis Test for Axis-Aligned Bounding Box and Triangle produces incorrect results (3D)
body: <p>I'm doing triangle to AABB intersection tests, and I'm taking this sample code from <em>Real-Time Collision Detection</em> 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.</p>
  
  <p><strong>Test:</strong> Nine axes given by the cross products of combination of edges from both.</p>
  
  <pre><code>// 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 ) ) &gt; projectionRadius ) {
      return false; // Axis is a separating axis
  }
  
  // Repeat similar tests for remaining axes a01..a22
  </code></pre>
  
  <p>So this is the test for the first axes. According to the book, these are the axes:</p>
  
  <p>a00 
   =
   u0 × f0 
   =
   (1, 0, 0) × f0 
   =
   (0, -f0z, f0y)</p>
  
  <p>a01 
   =
   u0 × f1 
   =
   (1, 0, 0) × f1 
   =
   (0, -f1z, f1y)</p>
  
  <p>a02 
   =
   u0 × f2 
   =
   (1, 0, 0) × f2 
   =
   (0, -f2z, f2y)</p>
  
  <p>a10 
   =
   u1 × f0 
   =
   (0, 1, 0) × f0 
   =
   (f0z, 0, -f0x)</p>
  
  <p>a11 
   =
   u1 × f1 
   =
   (0, 1, 0) × f1 
   =
   (f1z, 0, -f1x)</p>
  
  <p>a12 
   =
   u1 × f2 
   =
   (0, 1, 0) × f2 
   =
   (f2z, 0, -f2x)</p>
  
  <p>a20 
   =
   u2 × f0 
   =
   (0, 0, 1) × f0 
   =
   (-f0y, f0x, 0)</p>
  
  <p>a21 
   =
   u2 × f1 
   =
   (0, 0, 1) × f1 
   =
   (-f1y, f1x, 0)</p>
  
  <p>a22 
   =
   u2 × f2 
   =
   (0, 0, 1) × f2 
   =
   (-f2y, f2x, 0)</p>
  
  <p>============</p>
  
  <p>p0 
   =
   V0 · a00 </p>
  
  <p>p1
   =
   V1 · a00 = V1 = p0 </p>
  
  <p>p2
   =
   V2 · a00 = V2 </p>
  
  <p><strong>LEGEND</strong>:  u = center vector, f = triangle edge vector. p = distances from the origin to the projections of the triangle vertices onto normal. V = triangle point.</p>
  
  <p>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!</p>
  
  <p><strong>EDIT:</strong> 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.</p>
  
  <pre><code>// 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 ) ) &gt; projectionRadius ) {
      return false; // Axis is a separating axis
  }
  ...
  </code></pre>
  
  <p><strong>EDIT 2:</strong> I also tried the following, which got me closer, but still did not get all intersections and got ones that shouldn't have. <a href="https://gist.github.com/3558420" rel="nofollow noreferrer">https://gist.github.com/3558420</a></p>
  
  <p><strong>UPDATE:</strong> 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. </p>
  
  <p><strong>UPDATE 2:</strong> Additional attempts have been trying <a href="http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/tribox3.txt" rel="nofollow noreferrer">this</a> 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. </p>
  
  <p>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.</p>
  
  <p><img src="https://i.stack.imgur.com/dDPMZ.jpg" alt="Intersection Data Image"></p>
  
  <p>Intersection result returned on following test categories:</p>
  
  <p>Voxel1: None, passed all, returned with default "true".<br>
  Voxel2: Category 2<br>
  Voxel3: Category 3<br>
  Voxel4: Category 3<br>
  Voxel5: Category 3   </p>
  
  <p><strong>UPDATE 3: Another implementation, better results</strong></p>
  
  <p>Ok, so after reading William Bittle's <a href="http://www.codezealot.org/archives/55#sat-proj" rel="nofollow noreferrer">article</a> at codezealot.org, I implemented the following:</p>
  
  <pre><code>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 &lt; 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 &lt; 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;
  }
  </code></pre>
  
  <p>The axes code:</p>
  
  <pre><code>public static Vector3d[] getAxes( Vector3d[] vertices ) {
      Vector3d[] axes = new Vector3d[ vertices.length ];
      // loop over the vertices
      for ( int i = 0; i &lt; 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;
  }
  </code></pre>
  
  <p>And the overlap method from the projection class is as follows:</p>
  
  <pre><code>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 &gt; 0 ) || ( test2 &gt; 0 ) ) ) {      // if they are greater than 0, there is a gap 
          return false;                               // just quit } 
      }
      return true;
  }    
  </code></pre>
  
  <p>Now I'm using another dataset, to fully test the intersection, since I got some false positives from my last dataset.</p>
  
  <p>Triangle 0: true<br>
  Triangle 1: true<br>
  Triangle 2: true &lt;-- should be false<br>
  Triangle 3: false<br>
  Triangle 4: false<br>
  Triangle 5: true  </p>
  
  <p>(true = intersecting..)</p>
  
  <p>This is my dataset, which is labeled according to the results.</p>
  
  <p><img src="https://i.stack.imgur.com/miPT7.jpg" alt="new aabb/triangle dataset"></p>
  
  <p>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:</p>
  
  <pre><code>public static Vector3d[] getAABBAxes( Vector3d[] vertices ) {
      Vector3d[] axes = new Vector3d[ 6 ];
      // loop over the vertices
      for ( int i = 0; i &lt; 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;
  }
  </code></pre>
  
  <p>I get this:</p>
  
  <p>Triangle 0: true<br>
  Triangle 1: true<br>
  Triangle 2: false<br>
  Triangle 3: true  &lt;-- should be false<br>
  Triangle 4: true  &lt;-- should be false<br>
  Triangle 5: true  </p>