Ray und 3D-Gesicht Überschneidung

Question

Ich habe eine 3D-Fläche durch Punkte definiert n (v1, v2, v3, ..., vn), in 3D-Koordinaten, und ich habe einen Strahl der Gleichung:

P=P0+t(P1-P0).

wo 0<=t<=1.

Nun, wie finden Sie den Schnittpunkt (oder das Fehlen von) zwischen diesem Strahl und dem Gesicht?

Auch wäre es toll, wenn es eine bestehende C# Implementierung auf diesem gibt?

Bearbeiten: Die 3D-Fläche kann konkav sein oder konvex. Alle Punkte sind koplanar.

Answer 1

Ich nehme Ihr 3D-Polygon eben ist (sonst ist es nicht wirklich ein Polygon und es ist nicht gut definiert). Daher können Sie eine orthonormale 2D-Basis für diese Ebene finden. Das bedeutet, dass Sie jeden beliebigen 2D-Triangulationsalgorithmus verwenden können (Sie können viele C# -Implementierungen im Internet finden) und mit Ihrer orthonormalen Basis zu 3D zurückkehren. Auf diese Weise erhalten Sie 3D-Dreiecke und können problemlos Ihren Ray-Polygon-Schnitttest durchführen, indem Sie mehrere Ray-Triangle-Schnitttests ausführen.

Eine andere Möglichkeit besteht darin, eine Ray-Plane-Schnittpunktberechnung durchzuführen. Nimm den Schnittpunkt P, repräsentiere ihn mit 2D Koordinaten mit der obigen orthonormalen Basis. Stellen Sie außerdem wie in der vorherigen Lösung Ihr Polygon in 2D auf derselben Grundlage dar. Führen Sie dann einen 2D-Algorithmus "is point in polygon" aus und Sie erhalten Ihre Ergebnisse.

aktualisieren: Hier ist die Mathematik Sie zwei beliebige Punkte auf der Ebene p1 nehmen kann, p2 (zum Beispiel zwei der Punkte des Polygons) und nehmen Sie den Vektor u = p2 - p1. Normalisieren Sie es und es ist der erste Basisvektor. Dann nimmst du das normale N des Flugzeugs und berechne v = cross_product (u, N) und normalisierst v. Dies ist der zweite Basisvektor. Beachten Sie, dass beide Vektoren Einheitslänge haben und orthogonal zueinander sind. Sie bilden daher eine orthonormale Basis.

Definieren Sie nun p1 als Ursprung der Ebene. Dann wird die Übersetzung 2D von einem beliebigen Punkt Q auf dem Polygon (q einen der Eckpunkte des Polygons sein kann, oder jeder andere Punkt auf der Fläche des Polygons):

x = dot_product(q - p1, u) 
y = dot_product(q - p1, v) 

Hier x, y der Punkt des 2D-Koordinaten.

So, nachdem alles in 2D übersetzt und 2D-Algorithmen tun können Sie einen beliebigen 2D-Punkt (x, y) zurück in 3D wie folgt übersetzen:

q = p1 + x * u + y * v 

hier * ist der Skalar-Vektor-Produkt (x, y sind die Skalare und u, v sind die Vektoren).

Alex.

Answer 2

Sie sind nach einer Kreuzung Algorithmus ray-Polygon, hier ist ein Link auf die Graphics Gems Eintrag für sie: http://www-graphics.stanford.edu/courses/cs348b-98/gg/intersect.html

Answer 3

Wenn Ihre Punkte nicht koplanar sind (dh nicht alle auf einer Ebene liegen), müssen Sie die Fläche in eine Menge von Ebenen unterteilen und dann den Linienpolygonschnitt für jede Ebene durchführen .Besser noch, definieren Sie eine Liste von Dreiecken und suchen Sie dann nach den Schnittpunkten von Linie und Dreieck.

Sie sagen jedoch nicht, ob Ihre Punkte ein facettiertes Objekt (d. H. Aus Dreiecken) definieren oder eine Reihe von Kontrollpunkten für eine gekrümmte Fläche definieren. Ersteres wird von oben behandelt. Wenn es eine gekrümmte Oberfläche ist, halte ich das für ein unberechenbares Problem, das heißt, es gibt keine triviale Lösung für das Problem der Bestimmung des Schnittpunkts einer Linie und einer gekrümmten Fläche, die durch eine Reihe von Punkten definiert wird. Das Beste, was Sie tun können, ist, einen iterativen Prozess zum Auffinden des Schnittpunkts zu verwenden, aber selbst dies könnte zu instabilen Suchen führen (d. H. Suchen, die niemals abgeschlossen werden).

Ich denke, die Umwandlung in eine Reihe von Dreiecken ist die beste Antwort.