java - 軸に沿ったバウンディング ボックスと三角形の軸テストを分離すると、正しくない結果が生成される (3D)

Question

トライアングルと AABB の交差テストを行っています。このサンプル コードは、Christer Ericson によるReal-Time Collision Detectionから取得しています。例を示す前に著者が本で言っていることは例とは異なるため、残りの軸をテストする方法がわかりません.. a01-a22.

テスト:両方のエッジの組み合わせの外積によって与えられる 9 つの軸。

// 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 = 三角点。

後続の軸テストはどのように計算されますか? 誰かが 1 つを実行できれば、残りの部分をよりよく理解できるかもしれませんが、例が 1 つしかないので、行き詰まっています..ありがとう!

編集:私は次のことを試しました..運がない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
}
...

EDIT 2:次のことも試しましたが、これで近づきましたが、それでもすべての交差点を取得できず、必要のない交差点を取得しました。https://gist.github.com/3558420

更新:まだ正しい交差結果を取得できません。Eli のコードを調べましたが、2D データ用のようで、用語が異なるため、私のコードと彼のコードの間に関連性が見つかりません。

更新 2:事実上の標準のようなこのコードを試す追加の試みが行われています。交差点が 4 つあるはずなのに、交差点が 1 つ得られます。そのうちの 2 つには三角形の点が含まれ、3 つにはエッジが含まれ、1 つには平面のみが含まれます。

キャッチされる交点には、1 つの点と 2 つのエッジ (および平面) があります。同じ特性を持つ別のオブジェクトが 1 つありますが、交差としてカウントされません。これは私が扱っているデータで、強調表示された「ボクセル」は、三角形と交差するものとして返されるものです。

次のテスト カテゴリで返される交差結果:

Voxel1: なし、すべて通過、デフォルトの「true」で返されます。
Voxel2: カテゴリ 2
Voxel3: カテゴリ 3
Voxel4: カテゴリ 3
Voxel5: カテゴリ 3

更新 3: 別の実装、より良い結果

わかりました、codezealot.org で William Bittle の記事を読んだ後、私は以下を実装しました:

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

私はこれを得る：

Triangle 0: true
Triangle 1: true
Triangle 2: false
Triangle 3: true <-- false である必要があります
Triangle 4: true <-- false である必要があります
Triangle 5: true

Answer 1

少し前に作成したゲームでのc＃（この場合はjavaとほぼ同じです...）の埋め込みを確認できます。 http://code.google.com/p/gotcha/source/browse/trunk/Gotcha/trunk/Gotcha/Gotcha/GameEnteties/GameEntity.cs#171

メソッドを探す：IsSATCollision

単純化のために頂点を持つものとして受け入れるパラメーターについて考えてみてください。

Answer 2

テストで誤検知が発生した理由は、トライアングル テストに関連していました。

3D 空間の平面である三角形をテストするには、4 つの軸 (別名法線) に対してテストする必要があります。

1. 表面法線
   
   • 三角形の 2 つの辺の間の外積。
2. エッジ法線 1
   
   • サーフェス法線とエッジ 1 の間の外積。
3. エッジ法線 2
   
   • サーフェス法線とエッジ 2 の間の外積。
4. エッジ法線 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;
}

さらに、Axis-Aligned Bounding Box の軸を計算する必要はありません。軸が整列しているため、軸は次のようになります。

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