Du bist nicht angemeldet.

Werbeanzeige

1

20.03.2018, 08:54

Faces für Poylgon berechnen

Hi,

ich habe ein Polygon, das ich in eine geschlossene Fläche umwandeln will, sprich ich will dieses in Dreiecke runterbrechen, die dann jeweils als geschlossene Fläche angesehen werden (es handelt sich hier um keine 3D-Engine, die Regel, dass eine Fläche nur dann geschlossen ist, wenn sie aus einem Dreieck besteht, hat also nichts mit der Darstellung/dem Rendering zu tun).

Meine Methode wäre es, jetzt einfach die aufeinanderfolgenden Vertices der Reihe nach zu Dreiecken zu verbinden. Leider klappt das natürlich nur bei bestimmten Polygonen:


(Link)


Bei dem Sechseck funktioniert die Methode problemlos, bei dem Stern geht es grandios in die Hose, weil Dreiecke so gebildet werden, dass die Zacken geschlossen werden.

Bevor ich jetzt das Rad neu erfinde: gibt's dafür schon einen fertigen, passenden Algorithmus?

Danke!

2

20.03.2018, 11:43

Hi,

Dein Ansatz funktioniert nur bei konvexen Polygonen.
Beim Stern könnte man die Vertices nach y-Koordinate ordnen und dann in dieser Reihenfolge verbinden, da der Stern monoton bzgl. einer senkrechten Gerade durch den Stern ist.
Ansonsten werden so genannte "Ear-Cutting"-Algorithmen verwendet.
Vielleicht hilft das hier dir weiter: https://github.com/greenm01/poly2tri
Ansonsten habe ich noch das gefunden: http://cgm.cs.mcgill.ca/~godfried/teachi…tting_ears.html
(Ich hab mir die Seiten nicht im Detail angeguckt. Das ist nur das, was ich nach einem ersten googeln gefunden habe. Wenn du selber nochmal suchen willst, empfehle ich dir nach "Triangulate polygon" o.ä. zu suchen).

Schorsch

Supermoderator

Beiträge: 5 199

Wohnort: Wickede

Beruf: Student

  • Private Nachricht senden

3

20.03.2018, 11:48

Als Einstieg in solche Themen ist Wikipedia oft nicht schlecht.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Schrompf

Alter Hase

Beiträge: 1 410

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

4

21.03.2018, 07:27

Assimp macht auch Ear Cutting. Ist die Standardlösung für konkave Polygone. Wird dann nochmal extra spannend, wenn Du Poly-Löcher in Polygonen unterstützen willst, aber bis dahin ist Ear Cutting ne praktische Sache und nichtmal sonderlich schwer zu implementieren.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

Werbeanzeige