Znajdź czy dwa trójkąty przecinają się ani nie

Question

Biorąc 2 zbiór punktów

((x1, y1, z1), (x2, y2, z2), (x3, y3, z3)) i

((p1, q1, r1), (p2, q2, r2), (p3, q3, r3)), z których każdy tworzy trójkąt w przestrzeni 3D.

W jaki sposób dowiesz się, czy te trójkąty przecinają się, czy nie?

Jednym z oczywistych rozwiązań tego problemu jest znalezienie równania płaszczyzny utworzonej przez każdy trójkąt. Jeśli płaszczyzny są równoległe, nie przecinają się.

W innym przypadku, poznaj równanie linii utworzonej przez przecięcie tych płaszczyzn za pomocą normalnych wektorów tych płaszczyzn.

Teraz, jeśli linia ta leży w obu trójkątnych obszarach, to te dwa trójkąty przecinają się, w przeciwnym razie nie.

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 
} 

Biorąc pod uwagę, że wiem, jak napisać powyższe funkcje, jakie inne implementacje trianglesIntersect powinienem wziąć pod uwagę?

Czy są szybsze algorytmy, które rozwiązują ten problem?

Answer 1

Odwiedź this table of geometric intersection algorithms uprzejmości realtimerendering.com, spojrzeć na wejściu na skrzyżowaniach trójkąt/trójkąt, a następnie postępuj zgodnie odniesienia, na przykład do Christer Ericson, Real-Time Collision Detection, strona 172. (A książki, które ja bardzo polecam).

The podstawowy pomysł jest prosty. Jeśli dwa trójkąty przecinają się, to albo dwie krawędzie jednego trójkąta przecinają się z drugą (lewa konfiguracja na schemacie poniżej), albo jedna krawędź każdego trójkąta przecina się z drugą (prawą konfiguracją).

więc przeprowadzić testy przecięcia segmentu trójkąt sześć linii i sprawdzić, czy któryś z tych konfiguracjach znaleziono.

Teraz, pytasz, w jaki sposób wykonuje się test przecięcia linii/trójkąta? Cóż, to łatwe. Odwiedź stronę this table of geometric intersection algorithms, spójrz na wpis dotyczący skrzyżowań odcinków linii (promień)/trójkątów i postępuj zgodnie z odnośnikami ...

(Należy wspomnieć, że prosty test opisany powyżej nie obsługuje prawidłowo trójkątów koplanarnych. to nie ma znaczenia: na przykład, gdy wykryjesz kolizję między siatkami trójkątów, koplanarne przypadki są niejednoznaczne, więc nie ma znaczenia, który wynik zostanie zwrócony, ale jeśli twoja aplikacja jest jednym z wyjątków, musisz to sprawdzić jako specjalny przypadek lub przeczytaj w Ericson, aby zapoznać się z innymi metodami, na przykład: separating-axis method lub Tomas Möller's interval overlap method.)