Dreieck Dreieck Schnittpunkt in 3D-Raum

Question

Ich arbeite mit etwas 3D-Geometrie. Ich muss den Schnittpunkt eines Dreiecks mit einem anderen Dreieck finden.

Welchen Algorithmus könnte ich verwenden?

Answer 1

Googling revelad this. Ich denke, es erklärt dies im Detail!

Answer 2

Dieses Papier beschreibt eine Implementierung:

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

Beachten Sie, dass es verschiedene Techniken sind je nachdem, ob Sie den Punkt/Segment wissen, wo die Kreuzung aufgetreten ist, oder einfach nur sagen, ob ein Schnittpunkt passiert ist. Dieses Papier gibt Ihnen das Liniensegment, das die Kreuzung darstellt.

Answer 3

Es gibt eine gute paper von Devillers et al mit dem Titel „Faster Dreieck-Dreieck Überschneidung Tests“ - (ja, hat eine Google-Suche, aber die Suche Schlüsselwörter sind wichtig ...)

Wie auch immer, ihre Punkt (verglichen mit dem Moeller-Papier in der Antwort von MichaelM) ist, dass Sie wirklich Ihre kombinatorischen Informationen erhalten sollten, indem Sie Determinanten ausgewählter Gruppen von 4 Punkten machen (das Papier beschreibt, wie). Dies vermeidet die Berechnung von Zwischenwerten, die problematisch inkonsistent sein können, und die wahrscheinlich nicht schneller sein werden ...

Sie können diese Determinanten betrachten, um herauszufinden, ob das von den 4 Punkten gebildete Tetraeder rechtshändig ist. linkshändig oder degeneriert (dh planar). Dieser Wert bestimmt auch, ob irgendeiner der 4 Punkte auf der einen oder der anderen Seite der durch die anderen drei gebildeten Ebene liegt und ob die von zweien der 4 gebildete (gerichtete) Linie auf der einen oder der anderen Seite liegt Linie von den beiden anderen gebildet.

Um eine lange Geschichte kurz zu machen, machen die Determinante macht Ihre Mathematik robuster, und wenn Sie darauf achten, können Sie in der Regel Algorithmen, die nicht die determinante Sache in diejenigen tun, die tun. Oder Sie könnten einfach die Zeitung lesen.

Answer 4

Viele Menschen verlassen sich offenbar auf eine Implementierung (link to source code) des Verfahrens im Jahr 2006 in der folgenden Veröffentlichung beschrieben (link to PDF):

Tropp, Oren, Ayellet Tal, und Ilan SHIMSHONI. "Ein schnelles Dreieck nach Dreieckskreuzungstest zur Kollisionserkennung." Computer Animation und virtuelle Welten 17.5 (2006): 527-535.

Es gibt jedoch ein Problem mit diesem Code (mit Ausnahme eines alten Programmierstil Annahme, mit unkonventionellen Notationen und die zugrunde liegende geometrische Interpretation zu verlieren): „Determinante Sache“ nicht unbedingt Ihre mathematischen robuster machen, wenn getan der falsche Weg.

Ich schlage vor, entweder Moeller-Methode (link to PDF) oder einen Blick auf Delliver das Papier zu verwenden (link to PDF), in der Bibliothek CGAL implementiert (link "Triangle_3_Triangle_3_do_intersect.h").

Ein Beispiel: die sagt oben umgesetzt Schnitt Routine, die die Dreiecke (p0, p1, p2) und (q0, q1, q2) der folgenden Punkte definiert

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

nicht schneiden, sind . Hier ist ein Bild der Dreiecke:

Und hier ist der Code-Schnipsel (anhängen zu Original-Code):

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

} 

Eine letzte Bemerkung über die Anzahl der Rechenoperationen: da das Verfahren Eingabe vorberechneter Kantenvektoren, 12 +/- Operationen sollten zu Tabelle I des Papiers hinzugefügt werden.

Last but not least: Bitte überprüfen Sie, was ich schreibe, und geben Sie mir Feedback, wenn Sie denken, dass ich etwas falsch verstanden habe!