java - 轴对齐边界框和三角形的分离轴测试产生不正确的结果 (3D)

Question

我正在对 AABB 相交测试进行三角形测试，并且我正在从 Christer Ericson 的实时碰撞检测中获取此示例代码。作者在给出示例之前在书中所说的与示例不同，所以我不确定如何测试剩余的轴..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)

10
=
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 = 中心 vector ，f = 三角形边缘 vector 。 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

更新:仍然无法获得正确的交集结果。查看了 Eli 的代码，但它似乎是针对 2d 数据的，而且术语不同，所以我没有找到我的代码和他的代码之间的联系。

更新 2:其他尝试一直在尝试 this代码，这就像事实上的标准。我得到一个交点，当应该有 4 个交点时，其中 2 个包含三角形的点，3 个包含边缘，1 个只是平面。

捕捉到的交点有一个点和两条边(加平面)。还有一个具有相同特征但位置不同的对象，这不计为相交。这是我正在处理的数据，突出显示的“体素”是与三角形相交返回的数据。



在以下测试类别上返回的交集结果:

Voxel1:无，全部通过，默认返回“true”。
Voxel2:类别 2
Voxel3:类别 3
Voxel4:类别 3
Voxel5:类别 3

更新 3:另一个实现，更好的结果

好的，所以在阅读了 William Bittle 的 article 之后在 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: true <-- 应该是 false
三角形 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: true <-- 应该是 false
三角形 4: true <-- 应该是 false
三角形 5:真

Answer 1

您可以在我不久前制作的游戏中检查我的 c#(在这种情况下几乎与 java 相同...)植入。
http://code.google.com/p/gotcha/source/browse/trunk/Gotcha/trunk/Gotcha/Gotcha/GameEnteties/GameEntity.cs#171

寻找方法:IsSATCollision

为简单起见，将其接受的参数视为具有顶点的参数。