轴对齐边界框和三角形的分离轴测试产生不正确的结果（3D） [英] Separating Axis Test for Axis-Aligned Bounding Box and Triangle produces incorrect results (3D)
问题描述
我正在为AABB交叉测试做三角形，我正在从Christer Ericson的实时碰撞检测中获取此示例代码。在给出示例之前，作者在书中所说的与示例不同，所以我不确定如何测试剩余的轴.. a01-a22。
测试：由两个边缘组合的叉积给出的九个轴。
//测试轴a00..a22（类别3）
//测试轴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是一个分离轴
}
//对剩余的轴重复类似的测试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，f2 x，0）
============
p0
=
V0·a00
p1
=
V1·a00 = V1 = p0
p2
=
V2·a00 = V2
LEGEND ：u =中心向量， f =三角形边缘矢量。 p =从原点到三角形顶点投影到法线的距离。 V =三角点。
如何计算后续轴测试？也许如果有人可以做一个我可以更好地了解其余部分，但只有一个例子，我被卡住了...谢谢！
编辑： 我尝试了以下..对于没有运气的a00-a22，测试仍然通过。
首先，我添加了此代码，并替换了a00，并添加了a01-a22。
//测试轴a00。 .a22（类别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）;
//测试轴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; //轴是分离轴
}
...
编辑2：我也试过以下，让我更接近，但仍然没有得到所有的交叉点，并得到了不应该有的。 在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）;
//遍及triangleAxes
for（int i = 0; i< triangleAxes.length; i ++）{
Vector3d axis = triangleAxes [i];
//将两个形状投影到轴上
投影p1 =项目（triangle.getPoints（），轴）;
投影p2 =项目（aabbVertices，轴）;
//投影重叠吗？
if（！p1.overlap（p2））{
//然后我们可以保证形状不重叠
返回false;
}
}
//循环aabbAxes
for（int i = 0; i< aabbAxes.length; i ++）{
Vector3d axis = aabbAxes [i];
axis.normalize（）;
//将两个形状投影到轴上
投影p1 =项目（triangle.getPoints（），轴）;
投影p2 =项目（aabbVertices，轴）;
//投影重叠吗？
if（！p1.overlap（p2））{
//然后我们可以保证形状不重叠
返回false;
}
}
//如果我们到达这里，那么我们知道每个轴都有重叠
//所以我们可以保证一个交叉点
返回true;
}
轴代码：
public static Vector3d [] getAxes（Vector3d [] vertices）{
Vector3d [] axes = new Vector3d [vertices.length];
//循环顶点
for（int i = 0; i< vertices.length; i ++）{
//获取当前顶点
Vector3d p1 = vertices [一世 ];
//获取下一个顶点
Vector3d p2 =顶点[i + 1 == vertices.length？ 0：i + 1];
//减去两个以获得边向量
//可以跳过边向量，因为我们可以通过交叉乘积得到正常值。
//得到垂直向量
Vector3d normal = new Vector3d（）;
normal.cross（p1，p2）;
轴[i] =正常;
}
返回轴;
}
投影类的重叠方法如下：
公共布尔重叠（投影投影）{
double test1;
double test2;
//并测试他们是否触及
test1 = min - projection.max; // test min1和max2
test2 = projection.min - max; // test min2和max1
if（（（test1> 0）||（test2> 0）））{//如果它们大于0，则有一个缺口
返回false; //刚退出}
}
返回true;
}
现在我正在使用另一个数据集来完全测试交叉路口，因为我从我上一个数据集得到一些误报。
三角形0：真实
三角形1：真实 -
三角形2：真< - 应为false
Triangle 3：false
Triangle 4：false
Triangle 5：true
（true =相交..）
这是我的数据集，根据结果标记。
所以我的想法是我没有得到正确的数据，因为我正在测试错误的轴/法线。所以我尝试了以下AABB以及三角形的略微修改版本：
public static Vector3d [] getAABBAxes（Vector3d [] vertices）{
Vector3d [] axes = new Vector3d [6];
//循环顶点
for（int i = 0; i< 6; i ++）{
//获取当前顶点
Vector3d p1 = vertices [i] ;
//获取下一个顶点
Vector3d p2 =顶点[i + 1 == vertices.length？ 0：i + 1];
Vector3d p4 =顶点[i + 3 == vertices.length？ 0：i + 3];
Vector3d edge1 = new Vector3d（）;
Vector3d edge2 = new Vector3d（）;
edge1.sub（p2，p1）;
edge2.sub（p4，p1）;
//减去两个以获得边向量
//可以跳过边向量，因为我们可以通过交叉乘积得到正常值。
//得到垂直向量
Vector3d normal = new Vector3d（）;
normal.cross（edge2，edge1）;
normal.normalize（）;
轴[i] =正常;
}
返回轴;
}
我明白了：
Triangle 0：true
Triangle 1：true
Triangle 2：false
Triangle 3：true< - 应该为false
Triangle 4：true< - 应为false
Triangle 5：true
我的测试误报的原因与三角测试有关。
要测试三角形，这是3D空间中的一个平面，你必须测试4轴（aka法线）。
- 表面正常
- 三角形两条边之间的交叉积。
- 边缘法线1
- 曲面法线与边缘之间的叉积1.
- 边缘法线2
- 曲面法线与边缘2之间的叉积。
- 边缘法线3
- 表面之间的交叉积正常和边缘3。
所以到最后，为了得到一个合适的（至少到目前为止工作正常）立方体和三角形之间的碰撞测试，你必须进行7轴测试。
每个测试包括检查三角形和方框相对于轴的顶点（正常）。这可以分解为三角形和盒子测试，如果有一个分离轴，那么你不必另外做。
注意：这个测试只会给你真假结果。没有提供其他数据。
public static boolean testTriangleAABB（三角形三角形，
Vector3d原点，双倍大小）{
setTriangleNormal（triangle.getNormal（true））;
Vector3d [] aabbVertices = calculateAABBVertices（origin，size）;
//三角形法线轴测试，false =无碰撞。
if（！testTriangleNormal（triangle，aabbVertices））{
return false;
}
//三角形边缘法线轴测试，假=无碰撞。
if（！testTriangleEdgeNormals（triangle，aabbVertices））{
return false;
}
//轴对齐边界框X，Y，Z轴测试，false =无碰撞。
if（！testAABBAxis（triangle，aabbVertices））{
return false;
}
//如果我们到达这里，那么我们知道每个轴都有重叠
//所以我们可以保证一个交叉点
返回true;
}
...
private static boolean testTriangleEdgeNormals（Triangle triangle，Vector3d [] aabbVertices）{
Vector3d edge = new Vector3d（）;
Vector3d edgeNormal = new Vector3d（）;
//循环三角形边缘法线
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）;
//将两个形状投影到轴上
projectionAABB = project2D1D（aabbVertices，edgeNormal）;
projectionTriangle = project2D1D（triangle.getPoints（），edgeNormal）;
//投影重叠吗？
if（！projectionAABB.hasOverlap（projectionTriangle））{
//然后我们可以保证形状不重叠
返回false;
}
}
返回true;
}
此外，无需计算Axis-Aligned Bounding Box轴。因为它们是轴对齐的轴，所以轴是这样的：
私有静态最终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）};
I'm doing triangle to AABB intersection tests, and I'm taking this sample code from Real-Time Collision Detection by Christer Ericson. What the author says in the book before he gives the example is different from the example so I'm not sure how to test the remaining axes.. a01-a22.
Test: Nine axes given by the cross products of combination of edges from both.
// 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
So this is the test for the first axes. According to the book, these are the axes:
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 = center vector, f = triangle edge vector. p = distances from the origin to the projections of the triangle vertices onto normal. V = triangle point.
How would the subsequent axes tests be calculated? Maybe if someone could do one I could have a better idea of the rest, but with only one example, I'm stuck.. Thanks!
EDIT: I tried the following.. for a00-a22 with no luck, the test still passes. First I added this code, and replace a00, and added 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: I also tried the following, which got me closer, but still did not get all intersections and got ones that shouldn't have. https://gist.github.com/3558420
UPDATE: Still not able to get correct intersection results. Looked over Eli's code, but it seems to be for 2d data and the terms are different so I'm not finding a connection between my code and his.
UPDATE 2: Additional attempts have been trying this code, which is like the defacto standard. I'm getting one intersection, when there should be 4 intersections, with 2 of those containing the points of the triangle, 3 containing the edges, and 1 just the plane.
The intersection that is caught has one point and two edges (plus plane). There is one other object that has the same characteristics, but different location, which does not get counted as intersecting. This is the data I'm working with, and the highlighted "voxel" is the one that gets returned as intersecting the triangle.
Intersection result returned on following test categories:
Voxel1: None, passed all, returned with default "true".
Voxel2: Category 2
Voxel3: Category 3
Voxel4: Category 3
Voxel5: Category 3
UPDATE 3: Another implementation, better results
Ok, so after reading William Bittle's article at codezealot.org, I implemented the following:
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;
}
The axes code:
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;
}
And the overlap method from the projection class is as follows:
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;
}
Now I'm using another dataset, to fully test the intersection, since I got some false positives from my last dataset.
Triangle 0: true
Triangle 1: true
Triangle 2: true <-- should be false
Triangle 3: false
Triangle 4: false
Triangle 5: true
(true = intersecting..)
This is my dataset, which is labeled according to the results.
So my thought is that I'm not getting the right data because I'm testing the wrong axes/normals.. So I tried the following for the AABB and a slightly altered version for the triangles:
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;
}
I get this:
Triangle 0: true
Triangle 1: true
Triangle 2: false
Triangle 3: true <-- should be false
Triangle 4: true <-- should be false
Triangle 5: true
The reason that I was getting false positives for my tests was related to the triangle test.
To test a triangle, which is a plane in 3D space, you have to test against 4 axes(aka normals).
- Surface Normal
- The cross-product between two edges of the triangle.
- Edge Normal 1
- The cross product between the surface normal and edge 1.
- Edge Normal 2
- The cross product between the surface normal and edge 2.
- Edge Normal 3
- The cross product between the surface normal and edge 3.
So in the end, to get a proper (at least it is working correctly so far) collision test between a cube and a triangle, you have to perform 7 axes tests.
Each test consists of checking the triangle and box vertices against the axis (normal). This can be broken down into a triangle and box test, and if one has a separating axis, then you don't have to do the other.
Note: This test will only give you true/false results. No other data is provided.
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;
}
Furthermore, there is no need to calculate Axis-Aligned Bounding Box axes..since they are axis aligned the axes will be like so:
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 ) };
这篇关于轴对齐边界框和三角形的分离轴测试产生不正确的结果（3D）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
