Trójkątne przecięcie trójkąta w przestrzeni 3D

Question

Pracuję z geometrią 3d. Muszę znaleźć przecięcie trójkąta z innym trójkątem.

Jakiego algorytmu mogę użyć?

Answer 1

Googling revelead this. Myślę, że wyjaśnia to szczegółowo!

Answer 2

Dokument ten opisuje jedną realizacji:

http://knight.temple.edu/~lakaemper/courses/cis350_2004/etc/moeller_triangle.pdf

pamiętać, że istnieją różne techniki w zależności od tego, czy chcesz poznać punktu/segmentu, w którym wystąpił skrzyżowanie, albo po prostu powiedzieć, czy przecinają się. W tym artykule otrzymasz segment linii reprezentujący skrzyżowanie.

Answer 3

Jest dobry paper przez Devillers et al tytułem "Faster Testy Triangle-Triangle Przecięcie" - (tak, nie szukaj google, ale słowa kluczowe wyszukiwania są ważne ...)

Zresztą ich punkt (w porównaniu do artykułu Moellera w odpowiedzi Michaela) jest to, że naprawdę powinieneś uzyskać swoje kombinatoryczne informacje, wykonując wyznaczniki wybranych grup 4 punktów (w artykule opisano sposób). Pozwala to uniknąć obliczania pośrednich wartości, które mogą być problematyczne niespójne, a które prawdopodobnie nie będą już szybsze ...

Możesz spojrzeć na te determinanty, aby dowiedzieć się, czy czworościan utworzony przez 4 punkty jest praworęczny, leworęczny lub zdegenerowany (tj. planarny). Wartość ta określa również, czy którykolwiek z 4 punktów znajduje się po jednej stronie, czy po drugiej stronie płaszczyzny utworzonej przez pozostałe trzy, oraz czy (ukierunkowana) linia utworzona przez dowolne dwa z czterech jest na jednej lub drugiej stronie linia utworzona przez dwa pozostałe.

W dużym skrócie, robienie decydującej rzeczy sprawia, że ​​twoja matematyka jest bardziej niezawodna, a jeśli zwracasz uwagę, zwykle możesz przekonwertować algorytmy, które początkowo nie wprowadzały wyznacznika w te, które to robią. Lub, możesz po prostu przeczytać gazetę.

Answer 4

Wiele osób pozornie polegać na realizacji (link to source code) sposobu opisanego w 2006 roku w następującym papieru (link to PDF):

Tropp, Oren, Ayellet Tal i Ilan Shimshoni. "Szybki trójkąt z testem przecięcia trójkąta dla wykrywania kolizji." Komputer Animacja i wirtualne światy 17.5 (2006): 527-535.

Istnieje jednak problem z tym kodem (oprócz przyjęcia starego stylu programowania, używając niekonwencjonalnych notacje i utraty podstawowych interpretację geometryczną): „wyznacznik rzeczą” nie muszą dokonać matematyka bardziej wytrzymałe, jeśli zrobione zły kierunek.

Proponuję użyć metody Moeller (link to PDF) lub spojrzeć na papierze Delliver'S (link to PDF), zrealizowaną w bibliotece CGAL (link "Triangle_3_Triangle_3_do_intersect.h").

Przykład: Procedura przecięcia wprowadzone powyżej mówi trójkąty (P0, P1, P2) i (Q0, Q1, Q2), określony przez następujące punkty

p0 = (-21, -72, 63) 
p1 = (-78, 99, 40) 
p2 = (-19, -78, -83) 
q0 = (96, 77, -51) 
q1 = (-95, -1, -16) 
q2 = (9, 5, -21) 

są nie przecinających . Oto zdjęcie z trójkątów:

A oto fragment kodu (dołączyć do oryginalnego kodu):

#include <iostream> 

inline void setPoint(double p[3], const double x, const double y, const double z) 
{ 
    p[0] = x; p[1] = y; p[2] = z; 
} 

inline void computeEdges(double v0[3], double v1[3], const double p0[3], const double p1[3], const double p2[3]) 
{ 
    v0[0] = p1[0]-p0[0]; 
    v0[1] = p1[1]-p0[1]; 
    v0[2] = p1[2]-p0[2]; 
    v1[0] = p2[0]-p0[0]; 
    v1[1] = p2[1]-p0[1]; 
    v1[2] = p2[2]-p0[2]; 
} 

void main() 
{ 
    unsigned int numErrors(0), count(0); 
    double p0[3], p1[3], p2[3], q0[3], q1[3], q2[3]; 
    double v0[3], v1[3], w0[3], w1[3]; 
    bool res, answer; 
    int ret; 

    std::cout << "Testing the correctness of tr_tri_intersect3D" << std::endl; 

    { 
     // Non excluding triangles in generic positions, big determinants, intersecting 
     ++count; 
     setPoint(p0, -21, -72, 63); 
     setPoint(p1, -78, 99, 40); 
     setPoint(p2, -19, -78, -83); 
     setPoint(q0, 96, 77, -51); 
     setPoint(q1, -95, -1, -16); 
     setPoint(q2, 9, 5, -21); 
     answer = true; 

     computeEdges(v0, v1, p0, p1, p2); 
     computeEdges(w0, w1, q0, q1, q2); 
     int ret = tr_tri_intersect3D(p0, v0, v1, q0, w0, w1); 
     bool res = (ret != 0); 

     if(res != answer) 
     { 
      std::cout << "# wrong answer on test " << count << "!\n"; 
      ++numErrors; 
     } 
    } 

} 

Ostatnia uwaga na temat liczby operacji arytmetycznych: od sposobu pobiera wektory wejściowe z wstępnie obliczonymi krawędziami, należy dodać 12 +/- operacji do Tabeli I. artykułu.

Last but not least: proszę sprawdź, co piszę na własną rękę, i daj mi znać, jeśli uważasz, że coś źle zrozumiałem!