Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Faces für Poylgon berechnen

Werbeanzeige

Elmi

Treue Seele

  • »Elmi« ist der Autor dieses Themas

Beiträge: 253

  • Private Nachricht senden

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!

superolelli

Treue Seele

Beiträge: 105

  • Private Nachricht senden

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 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • 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 470

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

Ähnliche Themen