Dreieck-Dreieck-Kreuzung im 3d-Raum
Arbeite ich mit einigen 3d-geometrie. Ich muss die Schnittpunkte des Dreiecks mit einem anderen Dreieck.
Welcher Algorithmus könnte ich verwenden?
InformationsquelleAutor Sakthikannan | 2009-09-30
Du musst angemeldet sein, um einen Kommentar abzugeben.
Dieses Papier beschreibt eine Implementierung:
http://knight.temple.edu/~lakaemper/Kurse/cis350_2004/etc/moeller_triangle.pdf
Beachten Sie, dass es gibt verschiedene Techniken, je nachdem, ob Sie wissen wollen, den Punkt/segment, wo die Kreuzung aufgetreten ist, oder einfach nur sagen, ob ein intersect passiert ist. Dieses Papier geben Sie die Zeile segment repräsentiert die Kreuzung.
InformationsquelleAutor MichaelM
Viele Menschen anscheinend verlassen Sie sich auf eine Implementierung (link zum source code) der beschriebenen Methode im Jahr 2006 in der folgenden Papier (link zu PDF):
Es gibt jedoch ein problem mit diesem code (außer für die Annahme einer alten Programmierung Stil, mit unkonventionellen Notationen zu verlieren und die zugrunde liegende geometrische interpretation): "Determinanten Sache" nicht unbedingt machen Sie Ihre Mathematik-robuster, wenn dies geschehen ist der falsche Weg.
Schlage ich vor, entweder Moeller-Methode (link zu PDF) oder werfen Sie einen Blick auf Delliver Papier (link zu PDF), implementiert in der CGAL-Bibliothek (link, "Triangle_3_Triangle_3_do_intersect.h").
Ein Beispiel: die Kreuzung routine implementiert, die oben erzählt, die den Dreiecken (p0,p1,p2) und (q0,q1,q2), definiert durch die folgenden Punkte
sind nicht schneiden. Hier ist ein Bild von den Dreiecken:
Und hier ist das code snippet anfügen", um die original-code):
Einen letzten Hinweis auf die Anzahl der arithmetischen Operationen: da die Methode nimmt in der Eingabe pre-computed-edge-Vektoren, 12 +/- Operationen Hinzugefügt werden soll Tabelle I. des Papiers.
Last but not least: überprüfen Sie bitte, was ich Schreibe, auf Ihrer eigenen und geben Sie mir feedback, wenn Sie denken, dass ich etwas falsch verstanden!
InformationsquelleAutor DoubleChain
Gibt es eine gute Papier von Devillers et al mit dem Titel "Schneller Triangle-Triangle Intersection Test") -- (ja, habe eine google-Suche, aber die Suchbegriffe sind wichtig...)
Sowieso, Ihre Nummer (im Vergleich zu den Moeller-Papier in MichaelM Antwort) ist, dass Sie sollten wirklich Ihre kombinatorischen Informationen durch tun Determinanten von ausgewählten Gruppen von 4 Punkte (das Papier beschreibt). Dies vermeidet computing Zwischenwerte werden kann, problematischer ist inkonsistent, und die wahrscheinlich nicht wirklich schneller...
Anschauen kann man sich diese Determinanten, wie herauszufinden, ob die Tetraeder gebildet durch die 4 Punkte ist Rechtshänder, Linkshänder, oder Entartete (d.h., planar). Dieser Wert bestimmt auch, ob einer der 4 Punkte auf der einen oder anderen Seite der Ebene, gebildet durch die drei anderen, und ob der (unter) der Linie gebildet, die von zwei beliebigen von den 4 ist auf der einen oder anderen Seite der Linie gebildet durch die beiden anderen.
Um eine lange Geschichte kurz, dabei wird die Determinante, was macht Ihr Mathe-robuster, und wenn Sie Aufmerksamkeit zahlen, können Sie in der Regel konvertieren algorithmen, die nicht ursprünglich über die Determinante Sache in diejenigen, die tun. Oder, man könnte einfach die Zeitung zu Lesen.
InformationsquelleAutor comingstorm