Finde heraus, ob zwei Dreiecke sich schneiden oder nicht
Erhält 2 Punkte,
((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)) und
((p1,q1,r1),(p2,q2,r2),(p3,q3,r3)) bilden jeweils ein Dreieck in 3D-Raum.
Wie findet man heraus, ob diese Dreiecke schneiden oder nicht?
Eine offensichtliche Lösung für dieses problem zu finden, ist die Gleichung der Ebene, gebildet durch jedes Dreieck. Wenn die Ebenen parallel sind, dann sind Sie nicht kreuzen.
Anderes, herauszufinden, die Gleichung der Linie gebildet durch die Schnittmenge dieser Ebenen mit Hilfe der normalen-Vektoren von diesen Ebenen.
Nun, wenn diese Linie liegt sowohl in der dreieckigen Regionen, dann sind diese beiden Dreiecke schneiden, sonst nicht.
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
}
Gegeben, dass ich weiß, wie man die oben genannten Funktionen, was andere Implementierungen von trianglesIntersect sollte ich beachten?
Gibt es schnellere algorithmen, die dieses problem lösen?
InformationsquelleAutor der Frage Atishay | 2011-08-18
Du musst angemeldet sein, um einen Kommentar abzugeben.
Besuchen diese Tabelle von der geometrischen Schnittpunkt algorithmen mit freundlicher Genehmigung von realtimerendering.comsuchen Sie den Eintrag für Dreieck/Dreieck-Kreuzungen, und Folgen Sie den Referenzen, zum Beispiel zu Christer Ericson, Real-Time Collision DetectionSeite 172. (Ein Buch, das ich Euch wärmstens empfehlen.)
Die grundlegende Idee ist einfach. Wenn zwei Dreiecke schneiden, dann entweder zwei Kanten eines Dreiecks schneiden sich die anderen (Links-Konfiguration in der Abbildung unten), oder mit einer Kante jedes Dreiecks schneidet die andere (richtige Konfiguration).
So führen sechs line-segment–Dreieck-Schnittpunkt-tests und sehen Sie, wenn eine dieser Konfigurationen zu finden ist.
Nun, Sie Fragen, wie Sie tun, ein Linien-segment/triangle intersection test? Naja, es ist einfach. Besuchen Sie diese Tabelle von der geometrischen Schnittpunkt algorithmensuchen Sie den Eintrag für line segment (ray)/Dreieck-Kreuzungen, und Folgen Sie den Referenzen...
(Es ist wichtig zu erwähnen, dass der einfache test oben beschrieben nicht handhaben koplanare Dreiecke richtig. Für viele Anwendungen ist dies unerheblich: zum Beispiel bei der Erkennung einer Kollision zwischen Netzen von Dreiecken, die koplanare Fällen sind nicht eindeutig, so ist es egal, welches Ergebnis zurückgegeben wird. Aber wenn Ihre Anwendung eine der Ausnahmen ist, werden Sie brauchen, um zu überprüfen, dass ein besonderer Fall, oder Lesen Sie weiter in Ericson für einige andere Methoden, zum Beispiel die separating-axis-Methodeoder Tomas Möller Intervall-overlap-Methode.)
InformationsquelleAutor der Antwort Gareth Rees