轴对齐边界框和三角形的分离轴测试产生不正确的结果（3D）
我正在对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）
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”。
体素2：类别2
体素3：类别3
体素4：类别3
体素5：类别3
更新3：另一种实施，更好的结果
好的，所以在阅读了William 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：是的
（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：真实< – 应该是假的
三角形4：真实< – 应该是假的
三角5：是的
您可以在我前一段时间制作的游戏中检查我的c＃（在这种情况下几乎与java相同……）植入。 http://code.google.com/p/gotcha/source/browse/trunk/Gotcha/trunk/Gotcha/Gotcha/GameEnteties/GameEntity.cs#171
寻找方法：IsSATCollision
考虑它接受的参数只是为了简单而具有顶点的东西。
我在测试中得到误报的原因与三角测试有关。
要测试三角形（三维空间中的平面），您必须测试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; }
此外，无需计算轴对齐边界框轴。因为它们是轴对齐的，所以轴将如下：
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 ) };