我正在做三角形到 AABB 相交测试，我正在从Christer Ericson的Real-Time Collision Detection中获取这个示例代码。作者在给出示例之前在书中所说的内容与示例不同，所以我不确定如何测试剩余的轴.. 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
更新：仍然无法获得正确的交叉点结果。查看了 Eli 的代码，但它似乎是针对 2d 数据的，而且术语不同，所以我没有找到我的代码和他的代码之间的联系。
更新 2：其他尝试一直在尝试此代码，这就像事实上的标准。我得到一个交叉点，当应该有 4 个交叉点时，其中 2 个包含三角形的点，3 个包含边，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;
}
我明白了：
三角形 0：真
三角形 1：真
三角形 2：假
三角形 3：真 <-- 应该是假
三角形 4：真 <-- 应该是假
三角形 5：真