2D-Kontur-Algorithmus für projizierten 3D-Netz

Question

Gegeben:. Ein 3D-Netz definiert mit einem Satz von Knoten und Dreiecke des Netzes mit diesen Punkten Aufbau

Problem: Finden Sie die 2d Umriss des projizierten willkürlich gedreht Masche auf einer beliebigen Ebene

.

Der Vorsprung ist einfach. Die Herausforderung liegt darin, die in der Ebene des „Rumpf“ der projizierten Dreieckskanten zu finden. Ich brauche Hilfe bei Eingabe / Zeiger auf diesen Algorithmus zu erforschen. Der Einfachheit halber können wir die 3D-Kanten projiziert werden gerade nach unten auf die xy-Ebene übernehmen.

Answer 1

• Starten Sie mit dem ganz rechten Punkt (der Punkt mit der größten x-Koordinate)
• Holen Sie sich alle Kanten von diesem Punkt
• Folgen Sie den Rand mit dem kleinsten Winkel zur positiven x-Achse, und fügen Sie es auch auf die Lösung gesetzt
• Von dem Punkt erreicht, folgen und die Kante mit dem kleinsten Winkel in dem Rande Sie kamen aus
• Wiederholen Sie, bis Sie den ursprünglichen Punkt
erreichen

Answer 2

Ich sehe nur Antworten für konvexe Lösungen, also hier ist mein für nicht-konvex. (Es war ein wenig verwirrend, was die Absicht war.)

Nehmen Sie alle Kanten von 2D-Dreiecke und gruppieren. Wenn zwei Kanten beiden Endpunkte teilen, sind sie in der gleichen Gruppe. Alle Gruppen, wobei nur eine Kante, ist dann ein Teil der Schale.

Schließlich können Sie die Shell-Kanten zu einem Ring verbinden, indem sie miteinander zu verbinden.

Answer 3

Die Alpha-Formen Technik in dieser Frage erwähnte behandelt eine allgemeine Reihe von Punkten, wo die Vertex-Verbindungen sind nicht bekannt:

Gibt es ein effizienter Algorithmus, um einen 2D-konkaven Rumpf?

zu erzeugen,

Da Sie jedoch bereits „Gesicht“ Informationen kennen, die durch die Projektion erhalten werden können, ist es wahrscheinlich nicht der beste Ansatz.

Ein Brute-Force-Algorithmus könnte machbar, vor allem, wenn räumliche Sortier Strukturen, in denen verwendet. zB für jede Facette:

1. Projekt Facette auf die Ebene
2. Überprüfen Sie, ob projizierte Facette wird durch vorhandene Geometrie vollständig geschlossen sind, wenn ja: done (keine Notwendigkeit, projizierte Silhouette zu erweitern)
3. Wenn die Punkte außerhalb der vorhandenen Geometrie fallen, sind dreieck Dreieck Kreuzungen, um zu bestimmen, welche Abschnitte außerhalb fallen, bauen eine beliebige n-Ecks (möglicherweise konkav) den fehlenden Raum zu füllen, dann hacken n-Ecks in Dreiecke

Eine weitere Idee, abhängig von der Treue Sie benötigen, ist nur schießt ein paar Strahlen Normal von Ihrer Projektionsebene zu Ihrer ursprünglichen Geometrie. Erstellen Sie eine 2D-Hit / Miss und verwendet, die Ihre Ausdehnungen zu bestimmen.

Answer 4

Die 2D-Kontur des Netzes Projektion ist eine Teilmenge des Vorsprungs seiner Kanten.

Mit dieser Beobachtung kann man unter Verwendung der 2D-Kontur mit dem folgenden Verfahren ermitteln:

• die Projektion von jeder Kante zu nur einer Seite gehörenden Teil der 2D-Kontur ist,
• für andere Kanten, bestimmen den Normalvektor der benachbarten Flächen
• Berechnung der Skalarprodukte dieser Normalen mit der Normalen der Ebene der Projektion
• gehört die Projektion dieser Kante in den 2D-Kontur, wenn alle Zeichen der Punktprodukte nicht gleich (was bedeutet, eine Fläche in Richtung auf die Projektionsebene zeigt, während zumindest einer anderen nicht der Fall ist, die den Rand identifiziert als Teil des Umrisses).

Beachten Sie, dass diese Methode berichten alle die Kanten, die auf der Projektionsebene orthogonal sind, auch solche, die nicht sichtbar von der Projektionsebene Sicht sind. Zum Beispiel mit einem Torus, wird es in das Innere und die Außenkonturen finden, auch wenn der Torus so gedreht wird, dass sein Inneres Loch nicht sichtbar von der Projektionsebene Sicht ist. Aussortieren, welche Kanten sichtbar sind, werden Sie irgendeine Art von Sichtbarkeit Test benötigen. Wenn die vorgesehene Verwendung für Benutzeranzeige ist, kann man einen Tiefenpuffer mit einer orthogonalen Projektionsmatrix berechnet verwenden, um die Geometrie von der Projektionsebene der Point-of-view zu machen und ein z-Tests durchführt, auf den Ränder von der Ebene sichtbar ist, zu bestimmen. Wenn Sie Präzision benötigen, müssen Sie ray / Dreieck Kreuzung führen Sichtbarkeit zu bestimmen.

Answer 5

Just hinzuzufügen: Eine sehr intuitive Art und Weise Kanten in einer Projektion zurück zu finden ist Face Culling! Jede Kante zwischen einem gekeult und nicht aussortierten Gesicht sollte eine Übersicht sein. Wenn Sie Innenkanten ausblenden möchten, verwenden Sie einfach den Z-Puffer. Zurück Face Culling ist einfach die Eckpunktreihenfolgeninformationen Post Projektion und sehr billig zu berechnen.

Answer 6

Ist es nur eine Frage der xyz Punkte in X'Y' Punkte auf der beliebigen Ebene vorsteht und dann nur eine konvexe Hülle in diesen Koordinaten zu tun?