두 직육면이 교차하는지 여부를 결정하는 방법 (포함 포함)

Question

직사각형이 항상 축과 정렬되지는 않습니다. 서로 교차하는지 확인하는 방법?

Answer 1

먼저 입방체 중 하나의 방향을 결정해야합니다. 그런 다음 다른 좌표의 좌표를 좌표 시스템으로 변환하십시오. 또한 각 축에 직육면체의 왼쪽/안쪽/오른쪽 점에 대한 조건을 쉽게 설정할 수있는 첫 번째 직육면 측정을 사용합니다.

이제 모든 입체적 좌표 즉, 정점은 입방체 내부

• 여부를 쉽게 확인할 수있을 것이다 안에있는 => 교차하거나 (두 정점으로 표시)
• 에지를 포함 직육면체의면과 교차합니다. 두 개의 정점이 입방체의 같은면 (왼쪽 및 왼쪽 또는 오른쪽 및 오른쪽)에있을 때이를 확인하지 않아도됩니다.

각 꼭지점 쌍의 모든 좌표 쌍 (각 왼쪽 및 오른쪽 또는 왼쪽)이 직육면체 인 경우 (포함하지 않고) 입방체가 포함됩니다.

Answer 2

분리 축 정리 (http://en.wikipedia.org/wiki/Separating_axis_theorem)는 교차하지 않을 경우 분리형 플랜지가 있음을 보증합니다 (http://en.wikipedia.org/wiki/Separating_axis_theorem) 따라서 잘 알려진 접근법은 입방체 정점 (심지어 정육면체라고 가정하지 않고 방향 경계 상자 정점)을 모든 가능한 분리 축에 투영하는 것입니다. 큐브의 얼굴과 쌍 방향 십자가에 법선이 있습니다.

N1, N2, N3을 첫 번째 큐브면의 법선이라고하고 M1, M2, M3을 두 번째 큐브의면의 법선이라고합시다. A와 B를 을 각각 첫 번째와 두 번째 큐브의 중심으로 놓자.

는 그러면

그 다음 투영 점과 다른 입방체의 중심 사이의 거리를 확인 등 N1, N2, N3, M1, M2, M3, N1xM1, N1xM2 내지 제 정육면체의 각 점을 투영 할 .

(VEC3 유형 과부하 일부 명백한 연산자) ++ C의 전체 코드 :

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; 
}