개의 삼각형이 교차 여부를 찾거나 포인트 2 세트를 제공하지

Question

((X1, Y1, Z1), (X2, Y2, Z2), (X3, Y3, Z3)) 및

((p1, q1, r1), (p2, q2, r2), (p3, q3, r3)

이러한 삼각형이 교차하는지 여부를 어떻게 알 수 있습니까?

이 문제에 대한 한 가지 분명한 해결책은 각 삼각형에 의해 형성된 평면의 방정식을 찾는 것입니다. 비행기가 평행하다면 교차하지 않습니다.

그렇지 않으면이 평면들의 법선 벡터를 사용하여이 평면들의 교차에 의해 형성된 선 방정식을 찾으십시오.

이제이 선이 두 삼각형 영역에 놓이면이 두 삼각형이 교차하고 그렇지 않은 경우 교차합니다.

trianglesIntersect(Triangle T1, Triangle T2) 
{ 
    if(trianglesOnParallelPlanes(T1, T2)) 
    { 
     return false 
    } 
    Line L1 = lineFromPlanes(planeFromTriangle(T1), planeFromTriangle(T2)) 
    if(lineOnTriangle(T1, L1) AND lineOnTriangle(T2, L1)) 
    { 
     return true 
    } 
    return false 
} 

위의 함수를 작성하는 방법을 알고 있으면 triangleIntersect의 다른 구현을 고려해야합니까?

이 문제를 해결하는 알고리즘이 더 빠릅니까?

Answer 1

방문 this table of geometric intersection algorithms 예의 realtimerendering.com의 삼각형/삼각형 교차로에 대한 항목에서보고, 크리스 에릭슨, Real-Time Collision Detection, 172 페이지에 예를 들어, 참조에 따라 (내가보기 엔 추천 책.)

을 기본 아이디어는 간단합니다. 두 개의 삼각형이 교차하면 한 삼각형의 두 모서리가 다른 모서리와 교차하거나 (아래 다이어그램에서 왼쪽 구성) 각 삼각형의 한 모서리가 다른 모서리와 교차합니다 (오른쪽 구성).

그래서 여섯 개 선분 삼각형 교차 시험을 수행하고, 이러한 구성 중 하나가 발견되는지.

이제 선분/삼각형 교차 테스트를 어떻게 수행합니까? 쉽습니다. this table of geometric intersection algorithms을 방문하고 선분 (광선)/삼각형 교차점에 대한 항목을보고 참조를 따르십시오 ...

(위의 간단한 테스트는 동일 평면 삼각형을 올바르게 처리하지 못합니다. 이것은 중요하지 않습니다. 예를 들어, 삼각형의 메쉬 사이의 충돌을 감지하면 동일 평면의 경우가 모호하므로 어떤 결과가 반환되는지는 중요하지 않습니다. 그러나 응용 프로그램이 예외 중 하나 인 경우 해당 사항을 확인해야합니다 특수 사례로 사용하거나 에릭슨에서 separating-axis method 또는 Tomas Moller의 interval overlap method과 같은 다른 방법으로 읽으십시오.