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

Schreibe einen Kommentar