Теорема о разделяющей оси (http://en.wikipedia.org/wiki/Separating_axis_theorem) гарантирует, что в вашем случае (два кубоида)
существуют разделительные плоскости, если они не пересекаются. Итак, хорошо известный подход заключается в проецировании кубоидных вершин (или даже вершин Ориентированной ограничивающей рамки, не предполагая, что это куб)
на каждую возможную разделяющую ось. Есть нормали к граням куба и попарно поперечным произведениям.
Пусть N1, N2, N3 - нормали к граням первого куба, а M1, M2, M3 - нормали к граням второго куба. Пусть А и Б
быть центрами первого и второго куба соответственно.
Затем вы должны проецировать каждую точку первого куба на N1, N2, N3, M1, M2, M3, N1xM1, N1xM2 и т. Д.
Затем проверьте расстояние между спроецированной точкой и центром другого куба.
Полный код на C ++ (с некоторой очевидной перегрузкой операторов для типа vec3):
bool Intersection_BoxToBox( const Box& ABox, const Box& BBox )
{
float R, R0, R1;
eBoxSeparatingAxis SeparatingAxis = S_AXIS_NONE;
float AxisLen, TmpDepth;
/// Relative distance
LVector3 D = BBox.FCenter - ABox.FCenter;
SeparatingAxis = S_AXIS_NONE;
/// Test each separating plane with Axes A0..A2, B0..B2 (six cases)
#define TEST_SEP_PLANE( PARAM_AxisName, PARAM_RelativeVal, PARAM_R0, PARAM_R1, PARAM_Normal ) \
R = fabs(PARAM_RelativeVal); \
R0 = PARAM_R0; \
R1 = PARAM_R1; \
/* If (R>R0+R1) Then there is no intersection */\
TmpDepth = R0 + R1 - R; \
if (TmpDepth < 0) return false; \
\
if (MaxDepth > TmpDepth) { \
MaxDepth = TmpDepth; \
SeparatingAxis = PARAM_AxisName; \
}
float a0 = ABox.FExtent[0];
float a1 = ABox.FExtent[1];
float a2 = ABox.FExtent[2];
float b0 = BBox.FExtent[0];
float b1 = BBox.FExtent[1];
float b2 = BBox.FExtent[2];
/// 1. A0
float A0D = ABox.FAxis[0].Dot( D );
float c00 = ABox.FAxis[0].Dot( BBox.FAxis[0] );
float c01 = ABox.FAxis[0].Dot( BBox.FAxis[1] );
float c02 = ABox.FAxis[0].Dot( BBox.FAxis[2] );
TEST_SEP_PLANE( S_AXIS_A0, A0D, a0, b0 * fabs( c00 ) + b1 * fabs( c01 ) + b2 * fabs( c02 ), ABox.FAxis[0] )
/// 2. A1
float A1D = D.Dot( ABox.FAxis[1] );
float c10 = ABox.FAxis[1].Dot( BBox.FAxis[0] );
float c11 = ABox.FAxis[1].Dot( BBox.FAxis[1] );
float c12 = ABox.FAxis[1].Dot( BBox.FAxis[2] );
TEST_SEP_PLANE( S_AXIS_A1, A1D, a1, b0 * fabs( c10 ) + b1 * fabs( c11 ) + b2 * fabs( c12 ), ABox.FAxis[1] )
/// 3. A2
float A2D = ABox.FAxis[2].Dot( D );
float c20 = ABox.FAxis[2].Dot( BBox.FAxis[0] );
float c21 = ABox.FAxis[2].Dot( BBox.FAxis[1] );
float c22 = ABox.FAxis[2].Dot( BBox.FAxis[2] );
TEST_SEP_PLANE( S_AXIS_A2, A2D, a2, b0 * fabs( c20 ) + b1 * fabs( c21 ) + b2 * fabs( c22 ), ABox.FAxis[2] )
/// 4. B0
float B0D = BBox.FAxis[0].Dot( D );
TEST_SEP_PLANE( S_AXIS_B0, B0D, a0 * fabs( c00 ) + a1 * fabs( c01 ) + a2 * fabs( c02 ), b0, BBox.FAxis[0] )
/// 5. B1
float B1D = BBox.FAxis[1].Dot( D );
TEST_SEP_PLANE( S_AXIS_B1, B1D, a0 * fabs( c10 ) + a1 * fabs( c11 ) + a2 * fabs( c12 ), b1, BBox.FAxis[1] )
/// 6. B2
float B2D = BBox.FAxis[2].Dot( D );
TEST_SEP_PLANE( S_AXIS_B2, B2D, a0 * fabs( c20 ) + a1 * fabs( c21 ) + a2 * fabs( c22 ), b2, BBox.FAxis[2] )
#undef TEST_SEP_PLANE
/// Now we test the cross-product axes
#define TEST_SEP_AXIS( PARAM_AxisName, PARAM_DirA, PARAM_DirB, PARAM_RelativeVal, PARAM_R0, PARAM_R1) \
TempAxis = PARAM_DirA .Cross( PARAM_DirB ); \
AxisLen = TempAxis.SqrLength(); \
\
if ( AxisLen > ::Math::EPSILON) \
{ \
R = PARAM_RelativeVal; \
R0 = PARAM_R0; \
R1 = PARAM_R1; \
\
TmpDepth = R0 + R1 - fabs(R); \
if (TmpDepth < 0) return false; \
\
if (MaxDepth * AxisLen > TmpDepth ) \
{ \
MaxDepth = TmpDepth / AxisLen; \
SeparatingAxis = PARAM_AxisName; \
} \
}
/// 7.-15. Name DirA DirB RelVal R0 R1
TEST_SEP_AXIS( S_AXIS_A0B0, ABox.FAxis[0], BBox.FAxis[0] , c10 * A2D - c20 * A1D, a1 * fabs( c20 ) + a2 * fabs( c10 ), b1 * fabs( c02 ) + b2 * fabs( c01 ) )
TEST_SEP_AXIS( S_AXIS_A0B1, ABox.FAxis[0], BBox.FAxis[1] , c11 * A2D - c21 * A1D, a1 * fabs( c21 ) + a2 * fabs( c11 ), b0 * fabs( c02 ) + b2 * fabs( c00 ) )
TEST_SEP_AXIS( S_AXIS_A0B2, ABox.FAxis[0], BBox.FAxis[2] , c12 * A2D - c22 * A1D, a1 * fabs( c22 ) + a2 * fabs( c12 ), b0 * fabs( c01 ) + b1 * fabs( c00 ) )
TEST_SEP_AXIS( S_AXIS_A1B0, ABox.FAxis[1], BBox.FAxis[0] , c20 * A0D - c00 * A2D, a0 * fabs( c20 ) + a2 * fabs( c00 ), b1 * fabs( c12 ) + b2 * fabs( c11 ) )
TEST_SEP_AXIS( S_AXIS_A1B1, ABox.FAxis[1], BBox.FAxis[1] , c21 * A0D - c01 * A2D, a0 * fabs( c21 ) + a2 * fabs( c01 ), b0 * fabs( c12 ) + b2 * fabs( c10 ) )
TEST_SEP_AXIS( S_AXIS_A1B2, ABox.FAxis[1], BBox.FAxis[2] , c22 * A0D - c02 * A2D, a0 * fabs( c22 ) + a2 * fabs( c02 ), b0 * fabs( c11 ) + b1 * fabs( c10 ) )
TEST_SEP_AXIS( S_AXIS_A2B0, ABox.FAxis[2], BBox.FAxis[0] , c00 * A1D - c10 * A0D, a0 * fabs( c10 ) + a1 * fabs( c00 ), b1 * fabs( c22 ) + b2 * fabs( c21 ) )
TEST_SEP_AXIS( S_AXIS_A2B1, ABox.FAxis[2], BBox.FAxis[1] , c01 * A1D - c11 * A0D, a0 * fabs( c11 ) + a1 * fabs( c01 ), b0 * fabs( c22 ) + b2 * fabs( c20 ) )
TEST_SEP_AXIS( S_AXIS_A2B2, ABox.FAxis[2], BBox.FAxis[2] , c02 * A1D - c12 * A0D, a0 * fabs( c12 ) + a1 * fabs( c02 ), b0 * fabs( c21 ) + b1 * fabs( c20 ) )
if ( SeparatingAxis == S_AXIS_NONE ) { return false; }
#undef TEST_SEP_AXIS
return true;
}