Я делаю тесты пересечения треугольника с AABB, и я беру этот пример кода изReal-Time Collision Detection Кристер Эриксон. То, что автор говорит в книге перед тем, как привести пример, отличается от примера, поэтому я не уверен, как проверить оставшиеся оси .. a01-a22.

Test: Девять осей, заданных перекрестными произведениями комбинации ребер из обоих.

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

LEGEND: u = вектор-центр, f = вектор ребра треугольника. p = расстояния от начала координат до проекций вершин треугольника на нормаль. V = точка треугольника.

Как будут рассчитываться последующие испытания осей? Возможно, если бы кто-то мог сделать это, у меня было бы лучшее представление об остальном, но только с одним примером я застрял ... Спасибо!

EDIT: Я попробовал следующее .. для 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

UPDATE: Все еще не в состоянии получить правильные результаты пересечения. Просматривал код Eli, но, похоже, он относится к 2d-данным, и термины отличаются, поэтому я не нахожу связь между моим кодом и его.

UPDATE 2: Дополнительные попытки были попыткиэтот код, который похож на стандарт де-факто. Я получаю одно пересечение, когда должно быть 4 пересечения, причем 2 из них содержат точки треугольника, 3 содержат ребра, а 1 - только плоскость.

Захваченное пересечение имеет одну точку и два ребра (плюс плоскость). Есть еще один объект, имеющий те же характеристики, но другое местоположение, который не считается пересекающимся. Это данные, с которыми я работаю, и выделенный «воксель». тот, который возвращается как пересекающий треугольник.

Результат пересечения возвращается по следующим категориям испытаний:

Voxel1: Нет, пропущено все, возвращено по умолчанию & quot; true & quot ;.
Voxel2: категория 2
Voxel3: категория 3
Voxel4: категория 3
Voxel5: категория 3

UPDATE 3: Another implementation, better results

Итак, после прочтения Уильяма Биттластатья на 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 & lt; - должно быть false
Треугольник 3: ложь
Треугольник 4: ложь
Треугольник 5: правда

(true = пересекающийся ..)

Это мой набор данных, который помечен в соответствии с результатами.

Поэтому я думаю, что я не получаю правильные данные, потому что я тестирую неправильные оси / нормали. Поэтому я попробовал следующее для 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 & lt; - должно быть false
Треугольник 4: true & lt; - должно быть false
Треугольник 5: правда