如何确定两个长方体是否相交（包含包含）

Question

长方体并不总是与轴对齐。如何确定它们是否相互交叉？

Answer 1

您将首先确定其中一个长方体的方向。然后将其他坐标转换为该坐标系。您还可以测量第一个长方体，以方便地为每个轴上的长方体左/内/右点设置条件。

现在将很容易检查顶点是否

• 是长方体的内部，即，坐标在所有三个维度是内部=>相交或含有
• 的边缘（由两个顶点表示）与长方体的一个面相交。当两个相关顶点位于长方体的同一侧（左侧和右侧或右侧）时，您不必检查。

如果每个顶点对的每个坐标对（在每个维度上）都包含（而不是包含）长方体的左边（左和右或左和右）。

Answer 2

分离轴定理（http://en.wikipedia.org/wiki/Separating_axis_theorem）确保在你的情况下（两个长方体） 如果它们不相交，则存在分离坩埚。因此，众所周知的方法是将立方体顶点（或者甚至是定向包围盒顶点，而不假定它是立方体）投影到每个可能的分离轴。立方体的面和法向交叉产物都有法线。

设N1，N2，N3为第一个立方体面的法线，M1，M2，M3为第二个立方体面的法线。设A和B分别为第一个和第二个立方体的中心。

然后，你必须对项目第一立方体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; 
}