Wie kann ich einen Dreieck-Innentest in Polygonnetzen durchführen?

10

Geben Sie hier die Bildbeschreibung ein Ich habe 3 Eckpunkte, die (V1, V2, V3)zufällig auf einem regulären Dreiecksnetz ausgewählt wurden. Für diese 3 Eckpunkte habe ich die geodätische Entfernung und den Pfad (unter Verwendung von Dijkstra) zwischen ihnen berechnet und eine dreieckartige Oberfläche wie in der obigen Abbildung gebildet.

Jetzt habe ich die Scheitelpunkte, die in jedem Pfad liegen, und kann geodätische Entfernungen von einem bestimmten Scheitelpunkt berechnen.

Was ich tun möchte, ist, die Eckpunkte oder Dreiecke zu erhalten, die in einem dreieckartigen Bereich liegen. Wie kann ich das machen?

mesh triangulation mkocabas
quelle
2
Unter der Annahme, dass der baryzentrische Ansatz das tut, was ich denke, wäre er bei großen Mengen ziemlich langsam. Stellen Sie sich einen Satz von 9 Millionen Scheitelpunkten mit nur 9 Scheitelpunkten im gewünschten Satz vor. Warum den gesamten Satz iterieren, wenn v1, v2 und v3 Ihnen alle Informationen geben, die Sie benötigen? Die Antwort auf die Flutfüllung wäre die schnellste flexible Lösung. Obwohl unflexibel, wäre Scanline der schnellste Ansatz, wenn Sie davon ausgehen können, dass Sie Linien wie jetzt in der Geometrie haben.
Andrew Wilson
In Bezug auf Leistungsprobleme haben Sie absolut Recht. Ich möchte diesen Ansatz in großen Maschen verwenden. Ich suche also nach einer effizienten Methode. Eigentlich kenne ich weder Flood-Filling- noch Scan-Fill-Algorithmen, ich werde sie mir ansehen. Vielen Dank.
mkocabas
3
Eine Flutfüllung mit einem Diagramm würde an einem Knoten beginnen, jeden Nachbarknoten besuchen, wenn die Randbedingung erfüllt und nicht besucht ist, als besucht markieren und wiederholen (Rekursion). Änderung: Markieren Sie jeden Knoten auf dem Pfad als besucht und starten Sie von einem Knoten innerhalb des Sets. Verwenden Sie dann einfach die Besuchsprüfung als Randbedingung.
Andrew Wilson
Danke für die ausführliche Erklärung. Ich finde Hochwasserfüllung algo vernünftiger, aber ich möchte sowohl Hochwasserfüllung als auch Scanlinie implementieren und dann die Leistungen vergleichen.
Mkocabas

Antworten:

4

Es gibt eine alternative Methode, die auf der Flutfüllung beruht. Ordnen Sie zuerst Ihre Kantendaten in einer Schleife an, in der die Kanten eine Schleife gegen den Uhrzeigersinn bilden. Beginnen Sie dann an einem beliebigen Punkt in der Schleife und wählen Sie Kanten aus, die diesen Punkt verbinden. Verwenden Sie die ausgehende Begrenzungskante und kreuzen Sie sie mit der anderen ausgehenden Kante. Wenn sie in Richtung der Gesichtsnormalen zeigt, muss sie eingefügt werden, wenn nicht, verwerfen Sie sie. Von dieser Kante aus fahren Sie fort, bis Sie eine Grenzkante erreichen. An diesem Punkt beenden Sie die Füllung. Fahren Sie an einem noch zu besuchenden Randkantenscheitelpunkt fort.

joojaa
quelle
Ich bin nicht mit dem Algorithmus zum Füllen von Überschwemmungen vertraut. Ihre Erklärung erscheint mir etwas kompliziert. Könnten Sie bitte eine anständige Referenz zum Anschauen angeben? Vielen Dank.
Mkocabas
Ich habe die Lösung gefunden, indem ich einige gelesen habe. Vielen Dank.
Mkocabas
3

Ich habe bereits die Verwendung von Flood Fill kommentiert und erklärt, wie es besser wäre, da es flexibler ist, aber eine andere mögliche Lösung ist Scanline. (Ich sage möglich, weil es viele Annahmen über Ihre Geometrie macht, aber für den bestimmten gezeigten Satz und viele ähnliche würde es funktionieren.)

Für Ihr Beispiel mit 3 Punkten: Suchen Sie den Schnittpunkt aus dem Segment v1, v2 und der Linie, auf der v3 liegt. (Der Scheitelpunkt links oben in Version 2) Wir nennen diesen Scheitelpunkt v4.

For every vertex pair a,b down v1,v4 and v1,v3 
    For every vertex from a to b
        Mark as in the set
For every vertex pair a,b down v3,v2 and v4,v3
    For every vertex from a to b
        Mark as in the set

Geben Sie hier die Bildbeschreibung ein

Es wird Scanline genannt, weil Sie (im Bild oben) gleichzeitig die roten und grünen Linien und dann gleichzeitig die roten und blauen Linien nach unten scannen.

Diese Lösung wäre sehr schnell, wenn es ein Indexmuster gibt, was häufig der Fall ist. Andernfalls wäre eine Berechnung erforderlich, um festzustellen, welcher benachbarte Scheitelpunkt auf der Linie liegt.

Lustige Sache ist Scanline, Barycentric Testing (in Dreiecksbegrenzungsrahmen) und Flood Fill sind alle Möglichkeiten, Dreiecke in 3D-Rendering zu zeichnen.

Andrew Wilson
quelle
2

Ich denke, Sie können einige oberflächengebundene Schwerpunktkoordinaten für jeden Punkt auf der Oberfläche berechnen und sie dann verwenden, um nach innerhalb oder außerhalb des Dreiecks zu suchen.

Ich habe keinen genauen Algorithmus zur Hand, aber ich habe das folgende Papier gefunden, das genau diese Art von Koordinaten zu verarbeiten scheint.

Schwerpunktzentrierte Koordinaten auf Oberflächen

Dragonseel
quelle
Vielen Dank für die Antwort und das Nachschlagewerk. Ich werde versuchen, die vorgeschlagene Methode umzusetzen.
Mkocabas