삼각형과 삼각형의 교차점 구하기

삼각형과 삼각형의 교차점을 구하기 위해 interval overlap 방식과 ERIT 방식을 사용한다.

다음과 같이 두 평면 π₁, π₂ 에 존재하는 삼각형 T₁, T₂  가 있다고 할 때 이들이 서로 교차하는지 검사해보자. 일반적으로 두 평면이 만나는 경우 교차선은 L 에 해당되는데, 삼각형이 서로 만난다면 직선 위의 빨간 구간이 서로 겹치게 될 것이다.

 

 

 

 

우선 삼각형 T₁ 의 각각의 정점과 평면 π₂ 사이의 부호 거리(signed distance) d_u0, d_u1, d_u2 및 삼각형 T₂ 의 각각의 정점과 평면 π₁사이의 부호 거리 d_v0, d_v1, d_v2 를 계산해본다.

 

 

• (1) 만약 d_u0, d_u1, d_u2 이 모두 0이 아니면서 같은 부호라면 즉, T₁ 의 세 점이 모두 π₂ 의 한쪽에만 있으므로 만나지 않는다.
• (1) 만약 d_v0, d_v1, d_v2 이 모두 0이 아니면서 같은 부호라면, 즉, T₂ 의 세 점이 모두 π₁ 의 한쪽에만 있으므로 만나지 않는다.
• (2) 만약 d_u0, d_u1, d_u2 이 모두 0이라면 두 삼각형이 같은 평면상에 존재하므로
  • 두 삼각형의 외접원이 교차하지 않으면 (두 외심사이의 거리가 두 외접원의 반지름의 합보다 크다면) 만나지 않는다.
  • T₁ 의 모든 에지에 대하여 T₂ 의 에지와 하나라도 교차한다면(직선과 직선의 교차점 계산을 총 9번 수행) 만난다.
  • T₁의 정점이 T₂에 하나라도 포함되거나 T₂의 정점이 T₁에 하나라도 포함된다면 (무게 중심 좌표가 모두 양수인지 총 6번 조사) 만난다.
  • 그 외의 경우에는 만나지 않는다.
• (3) 만약 d_u0, d_u1, d_u2 이 모두 0이 아니라면 즉, T₁ 어느 한 점도 π₂에 놓여있지 않다면
• T₁의 두 에지와 π₂ 의 교차점 p, q를 구하여(에지와 평면의 교차점 계산을 이용)
• p, q 모두 T₂ 의 내부에 있다면 만난다.
• p가 T₂  내부에 있다면 만난다. (이 때 q 위치를 수정해야 한다.)
• q가 T₂  내부에 있다면 만난다. (이 때 p 위치를 수정해야 한다.)  
• p, q 모두 T₂ 외부에 있다면 만난다. (이 때, p, q 위치를 수정해야 한다.)
• (4) 만약 d_u0, d_u1, d_u2 중 두 값만 0이라면 즉, T₁의 두 점이 π₂ 에 포함된다면
  • 교차점 p, q (삼각형의 두 정점에 해당됨)를 구하고
  • p, q 모두 T₂ 의 내부에 있다면 만난다.
  • p가 T₂  내부에 있다면 만난다. (이 때 q 위치를 수정해야 한다.)
  • q가 T₂  내부에 있다면 만난다. (이 때 p 위치를 수정해야 한다.)
  • p, q 모두 T₂ 외부에 있다면 만난다. (이 때, p, q 위치를 수정해야 한다.)
• (5) 만약 d_u0, d_u1, d_u2 중 한 값만 0이라면 즉, T₁의 한 점만 π₂ 에 포함된다면  
  • 나머지 두 값이 부호가 같다면 한 점 p를 구하고
    • T₂ 내부에 있다면 만난다.
    • T₂ 외부에 있다면 만나지 않는다.
  • 나머지 두 값이 부호가 다르다면 두 교차점 p(삼각형의 한 정점에 해당됨), q(에지와 평면의 교차점 계산 이용)를 구하고
    • p, q 모두 T₂ 의 내부에 있다면 만난다.
    • p가 T₂  내부에 있다면 만난다. (이 때 q 위치를 수정해야 한다.)
    • q가 T₂  내부에 있다면 만난다. (이 때 p 위치를 수정해야 한다.)
    • p, q 모두 T₂ 외부에 있다면 만난다. (이 때, p, q 위치를 수정해야 한다.)

 

 

각 경우을 아래 그림과 같이 나타냈다.

 

 

 

 

[참고] Real-time rendering. Akenine-Moller, Tomas, Eric Haines, and Naty Hoffman.