分离轴测试的轴对齐包围盒和三角形产生不正确的结果（3D）(Separating Axis Test

我在做三角形AABB相交测试，并且我被克里斯特埃里克森采取从实时碰撞检测此示例代码。所以我不知道如何测试其它轴.. A01-A22是作者说，在书中，他给出的例子是前从实例的不同。

测试：从两个边缘相结合的交叉产品给出的九轴。

// 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

所以这是第一个坐标轴测试。根据这本书，这些都是轴：

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

注：u =中心向量，F =三角形边矢量。 P =从原点到三角形顶点的凸起距离到正常。 V =三角形点。

如何将计算后续轴测试？也许有人可以做一个我能有其他更好的主意，但只是一个例子，我卡住了..谢谢！

编辑：我尝试以下。对于A00-A22没有运气，测试仍然通过。首先，我加入这个代码，并替换A00和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
}
...

编辑2：我也试过以下，这让我更接近，但还是没有得到所有的路口，并得到那些不应该有。 https://gist.github.com/3558420

更新：仍然没有能够得到正确的相交结果。看着伊莱的代码，但它似乎是2D数据和术语是不同的，所以我没有找到我的代码和他之间的连接。

更新2：其他尝试已经尝试这个代码，这是象的事实标准。我发现了一个交叉点，当存在应该是4个交叉点，与含三角形的点，3含有边缘的那些2，和1只的平面。

该被捕获的交点有一个点和两个边缘（加上平面）。还有另外一个对象具有相同的特点，但不同的位置，这不会被算作相交。这是我正在使用的数据，并突出显示的“体素”是获取返回相交的三角形之一。

路口结果在下面的测试类返回：

Voxel1：无，通过所有，使用默认“真”返回。
Voxel2：第2类
Voxel3：3类
Voxel4：3类
Voxel5：3类

更新3：另一种实现，效果更佳

好了，阅读威廉Bittle年代以后的文章在codezealot.org，我实现了以下内容：

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;
}

轴代码：

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;
}

和从投影类的重叠方法如下：

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;
}

现在，我在使用其他数据集，以全面测试的交集，因为我得到了一些误报从我的最后的数据集。

三角0：真
三角1：真
三角2：真正的< - 应该是假的
三角3：假
三角4：假
三角5：真

（真=相交..）

这是我的数据集，根据结果进行标记。

所以我的想法是，我没有得到正确的数据，因为我测试了错误的轴/法线..所以我想为AABB和三角形稍微修改过的版本如下：

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;
}

我得到这个：

三角0：真
三角1：真
三角2：假
三角3：真正的< - 应该是假的
三角4：真正的< - 应该是假的
三角5：真

Answer 1:

你可以检查我的C＃（在这种情况下，几乎等同于Java的...）在比赛中我犯了一个小会儿前植入。 http://code.google.com/p/gotcha/source/browse/trunk/Gotcha/trunk/Gotcha/Gotcha/GameEnteties/GameEntity.cs#171

寻找方法：IsSATCollision

想想它接受作为只是一些具有顶点简单的参数。

Answer 2:

我是越来越误报为我的测试的原因是相关的三角测试。

要测试的三角形，其在三维空间中的平面，则必须要测试的4轴（又名法线）。

表面法线
- 三角形的两个边缘之间的叉积。
边缘法线1
- 表面法线和边缘1之间的叉积。
边缘法线2
- 表面法线和边缘2之间的叉积。
边缘法线3
- 表面法线和边缘3之间的叉积。

所以，最后，得到一个立方体和一个三角形之间的正确（至少它工作正常至今）碰撞试验，你必须执行7次测试。

每个测试包括检查所述三角形和顶点盒相对于轴线（正常）的。这可以被分解成一个三角形，箱试验，如果一个人有一个分离轴，那么你就不必做其他的。

注意：此测试将只给你真/假结果。不提供其它数据。

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;
}

此外，也没有必要计算轴对齐包围盒axes..since它们是对准的轴将像这样轴：

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 ) };