2D-Kontur-Algorithmus für Projektions-3D-mesh

Gegeben: Ein 3D-mesh definiert, die mit einem Satz von vertices und Dreiecke, die den Aufbau des mesh mit diese Punkte.

Problem: hier Finden Sie die 2d-Kontur des projizierten beliebig gedreht Netz auf einer beliebigen Ebene.

Ist die Projektion einfach. Die Herausforderung liegt darin, die "Hülle" des projizierten Dreiecks-Kanten in der Ebene. Ich brauche etwas Hilfe mit ein/aus-Zeiger auf die Erforschung dieses Algorithmus. Für Einfachheit, können wir davon ausgehen das 3D-Kanten projiziert werden gerade nach unten auf die xy-Ebene.

  • Die Blaue Linie sieht nicht konvexe hier.
  • Ja, du hast Recht. Ich habe schnell geklaut, dass Bild von einer Website und zeichnen Sie ein paar rote Linien auf, die es zu illustrieren. Ich hoffe immer noch, dass die Idee kam durch 🙂
  • Ich brauche genau das zu tun. Welches Verfahren für Sie am besten geeignet in der end -?
  • Es hat sehr gut geklappt indem Sie z.B. Osten die meisten Knoten, Messen Winkel und gehen mit dem nächsten ein. Ein Wort der Warnung: Seien Sie vorsichtig mit floating point Genauigkeit auf die Winkel! Ich erinnere mich, ich hatte Probleme mit dieser und der Algorithmus nahm den falschen Weg in die Maschen.
  • Vielen Dank für Ihre Antwort und die Warnung über die FP Probleme. Ich fühle mich zuversichtlich, dies jetzt zu tun 🙂
InformationsquelleAutor ralphtheninja | 2009-06-18
  1. 10
    • Beginnen Sie mit dem rechten Punkt (der Punkt mit der größten x-Koordinate)
    • Bekommen Sie alle Kanten, die von diesem Punkt
    • Befolgen Sie die Kante mit dem kleinsten Winkel zur positiven x-Achse, und auch hinzufügen, um die Lösung
    • Aus der Punkt erreicht, Folgen Sie und fügen Sie die Kante mit dem kleinsten Winkel zu dem Rand, den Sie kam aus
    • Wiederholen Sie, bis Sie den ursprünglichen Punkt
    • Was passiert, wenn Sie das Projekt zu einem torus auf der x-y-Ebene? Wird nicht das innere "Loch".
    • Was ist, wenn es gibt zwei Kanten, beide gleich dem kleinsten Winkel?
    • Hmm... Nehmen Sie das kürzere der beiden.
    • Nein, Messen den Winkel nur in eine Richtung, z.B. gegen den Uhrzeigersinn.
    • vielen Dank für die schöne Lösung @Svante. Könnten Sie beraten, wie sollte das funktionieren, für andere Projektion Richtungen bitte?
    • Diese Lösung ist nur in 2D. Wie kommen Sie zu einer 2D-Eingang ist völlig unabhängig. Sie können die Karte einer beliebigen Ebene auf der xy-Ebene.

    InformationsquelleAutor Svante
  2. 3

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

    Nehmen alle Kanten aus Ihrer 2D-Dreiecke und gruppieren Sie Sie. Wenn zwei Kanten teilen sich beide Endpunkte, Sie sind in der gleichen Gruppe. Alle Gruppen, mit nur einer Kante ist, ist dann ein Teil der Schale.

    Schließlich können Sie kombinieren die shell-Kanten zu einem ring, durch den Beitritt zusammen.

    InformationsquelleAutor LaZe
  3. 2

    Die alpha-Formen-Technik erwähnt, in der diese Frage behandelt einen Allgemeinen Satz von Punkten, wo die Eckverbindungen sind nicht bekannt:

    Gibt es einen effizienten Algorithmus zum erzeugen einer 2D-konkaver Rumpf?

    Jedoch, da Sie bereits wissen, "Gesicht" Informationen, die erhalten werden kann, durch die Projektion, es ist wahrscheinlich nicht der beste Ansatz.

    Einem brute-force-Algorithmus möglicherweise machbar, vor allem, wenn räumliche Sortierung Strukturen verwendet. zB für jede Facette:

    1. Projekt-Facette auf der Ebene
    2. Überprüfen, wenn projiziert Facette ist komplett umschlossen von einer vorhandenen geometrie, wenn ja: fertig (keine Notwendigkeit, Sie zu erweitern projizierten silhouette)
    3. Wenn Punkte außerhalb der bestehenden geometrie, tun, Dreieck-Dreieck, Kreuzungen zu bestimmen, welche Teile fallen, bauen Sie eine beliebige n-gon (möglicherweise konkav) füllen Sie die fehlenden Raum, dann hacken das n-Eck in Dreiecke zu

    Andere Idee, je nach der treue, die Sie benötigen, ist nur Schießen Sie ein Bündel der Strahlen, die normal von Ihrem Projektionsfläche zu Ihrer ursprünglichen geometrie. Erstellen Sie ein 2d-hit/miss und verwenden, um zu bestimmen, Ihre Blöcke.

    InformationsquelleAutor nsanders
  4. 2

    Die 2D-Kontur des mesh-Projektion ist eine Teilmenge der Projektion der Kanten.

    Mithilfe dieser Beobachtung, kann man bestimmen, der 2D Kontur mit der folgenden Methode:

    • die Projektion von jeder Kante gehören, um nur eine Fläche ist Teil der 2D-Kontur,
    • für andere Kanten, bestimmen Sie den Normalenvektor von seinen angrenzenden Flächen
    • berechnen Sie die dot-Produkte dieser normalen mit der normalen der Ebene der Projektion
    • die Projektion dieser Rand gehört zu der 2D-Kontur, wenn alle Zeichen des dot-Produkte, die nicht den gleichen (das heißt, ein Gesicht weist in Richtung der Projektionsfläche, während mindestens eine andere nicht, identifiziert, die die Kante als ein Teil des Umrisses).

    Beachten Sie, dass diese Methode Bericht alle die Kanten, die orthogonal zur Projektionsfläche, auch diejenigen, die nicht sichtbar sind von der Projektionsfläche s point of view. Zum Beispiel mit einem torus, findet es die inneren und die äußeren Konturen, auch wenn der torus ist gedreht in solcher Weise, dass seine innere Loch ist nicht sichtbar von der Projektionsfläche s point of view. Sortieren Sie heraus, welche Kanten sichtbar sind, müssen Sie irgendeine Art von Sichtbarkeit zu testen. Wenn die beabsichtigte Verwendung ist für den Benutzer anzuzeigen, können Sie einen depth-buffer berechnet mit einer orthogonalen Projektions-matrix zum Rendern der geometrie der Projektionsfläche s point-of-view-und einige z-Tests, um festzustellen, welche Kanten sichtbar aus der Ebene. Wenn Sie brauchen Präzision, die Sie benötigen, um ausführen ray/triangle intersection zu bestimmen Sichtbarkeit.

    • Ich würde empfehlen die Ausrichtung test-post-Projektion. Ich versuche mich zu erinnern, warum pre-Projektion funktioniert nicht. Kann nicht kommen mit einer guten Mathematik-Grund obwohl. Es war mir einfach transformieren normals falsch wahrscheinlich, wenn ich es gemacht habe.
    InformationsquelleAutor Sebastien Pellizzari
  5. 1

    Nur hinzufügen: Eine sehr intuitive Art und Weise zu finden, der Kanten in der Projektion für das back-face-culling! Jede Kante zwischen einem gekeult und nicht gekeult Gesicht eine Kontur. Wenn Sie wollen sich zu verstecken innere Kanten, verwenden Sie einfach den z-buffer. Back-face-culling einfach die post-Projektion vertex Ordnung und sehr Billig zu berechnen.

    InformationsquelleAutor starmole
  6. 0

    Ist es einfach eine Frage der Projektion der xyz Punkte zu x 'Y' Punkte auf der willkürlichen Ebene und dann einfach nur tun, eine convex hull in diesen Koordinaten?

    • Als ich antwortete, um nsanders, bevor er schrieb seine Antwort. Wie Sie sehen können auf dem zweiten Bild, die rote Kanten, die nicht unbedingt die form einer konvexen gesetzt.
    • Die Frage ist also wirklich nur zu finden, dass die Begrenzungskanten der eine Masche? Wählen Sie einen Mittelpunkt in jeder Zeile und eine Anzahl von Kanten gekreuzt - Punkt-in-polygon-test mit all den anderen Dreiecken.
    InformationsquelleAutor Martin Beckett
Schreibe einen Kommentar