Fläche aus 4 oder mehr Punkten in Dreiecke unterteilen

[Sunny]

Da ich mich ab jetzt mal ein bischen mit meinem .obj zu .mesh Konverter beschäftigen möchte und mir auch schon ein paar gedanken dazu gemacht habe, ist auch schon das erste Problem aufgetreten.
Da Flächen in .obj-Dateien nicht zwangsweise aus Dreiecken bestehen müssen, was allerdings für .mesh-Dateien nötig ist, müssen vor dem Convertieren zuerst alle Flächen Trianguliert (in Dreiecke unterteilt) werden. Jetzt habe ich mir überlegt, dass man das ja den Konverter übernehmen lassen könnte aber... Genau hier liegt das Problem.
Wenn ich z.B. eine Fläche bestehend aus mehr als 3 Punkten habe, ist das gar nicht so leicht, anhand der Punkte-Koordinaten einen passenden algorythmus zu finden um diese Fläche in mehrere Dreiecke aufzuteilen.
So ein Algorythmus müsste natürlich für jede mögliche Fläche funktionieren.
Ist das überhaupt machbar und wenn ja, hat vieleicht jemand einen Lösungsvorschlag für mein Problem?

Edit:
OK... ich hab mir jetzt ein nettes System überlegt, das auch funktionieren sollte. Dazu muss ich allerdings ein paar kleine überprüfungen vornehmen und dazu fehlt mir irgendwie ein Lösungsansatz.
Für Mein System muss ich prüfen, ob die Kanten der Dreiecke (die ich erstelle) eine Kante oder einen Eckpunkt des Grund-Polygons schneidet, oder ob sich eine Kante der Dreiecke außerhalb des Grundpolygons befindet. Kann man das ermittlen, wenn man vom Grund-Polygon nur 2 Informations-Typen hat? (1. Koordinaten der Eckpunkte / 2. In welcher Reihenfolge ie Eckpunkte miteinander verbunden sind)

[NicTheQuick]

In meiner "Computer Graphics"-Vorlesung 2005 mussten wir ja einen Raytracer schreiben, der obj-Dateien laden kann. Da wurde uns auch vorgegeben, wie wir zu triangulieren hatten:

You will need to triangulate the polygons. A polygon with vertex indices i(1), i(2), ..., i(n) should be triangulated to (i(1), i(2), i(3)), (i(1), i(3), i(4)), (i(1), i(4), i(5)), ..., (i(1), i(n-1), i(n)).

Da damals auf diese Art und Weise alles geklappt hat und ich unserem Professor mal glauben schenken will, sollte es so klappen. Ich hab meine Objekte mit Blender erstellt und da hatte ich üblicherweise auch nur konvexe Polygone. Der Blender-internen Triangulator scheint es übrigens auch so zu machen.

[Sunny]

Es müssen aber nicht zwangsweise konvexe Polygone sein.
In Cinema 4D können z.B. auch solche Polygone erstellt werden.


Und bei dieser Art von Polygonen funktioniert dieser Ansatz nicht mehr.
Ich hätte zwar eine andere Idee, weiß aber nicht, wie ich diese umsetzen soll.

Hier mal mein Lösungsversuch für dieses Problem.
1. Ich erstelle eine Liste, die alle Eckpunkte des Polygons enthält. ( 1 2 3 4 5 6 7 8 )
2. Ich prüfe der Reihe nach, ob ein Dreieck aus 3 nebeneinander liegenden Punkten außerhalb des Grund-Polygons (das 8-Eck) liegt.
(Hinweis: drei nebeneinander liegende Punkte können z.B.: 1 2 3, 3 4 5,... aber auch 7 8 1 oder 8 1 2 sein)
3. Ich prüfe, ob eine Kante dieses Dreiecks einen Eckpunkt oder eine Kante des Grund-Polygons schneidet.
4. Wenn die Bedingungen von Punkt 2 und 3 nicht erfüllt sind, dann kan das Dreieck erstellt werden.
5. Wenn das Dreieck erstellt wurde, wird der mittlere der 3 nebeneinander liegenden Punkte aus der liste gelöscht und wieder von vorne angefangen.
(Bsp.: Das erste Dreieck das erstellt werden kann besteht aus den Punkten 2, 3 und 4... dann muss der mittlere Punkt (3) aus der Liste gelöscht werden.
Somit sieht die Liste dann so aus: 1 2 4 5 6 7 8 )

Das mache ich so lange, bis die Liste nur noch 3 Eckpunkte enthält. Aus diesen bilde ich dann noch ein letztes Dreieck und fertig... ^^
Ich hoffe ihr habt das System soweit verstanden.

Das Problem liegt jetzt allerdings darin, dass ich nicht weiß, wie ich die Bedingungen von Punkt 2 und 3 prüfen kann.

[BSP]

Hallo.
Wenn ich Dein Beispiel betrachte kommt mir der Gedanke,
das erst einmal in Vierecke zu zerteilen
und die dann in Dreiecke zu zerteilen.
In Deinem Beispiel erhielte man so
3 Vierecke, daraus werden dann 6 Dreiecke.
Allerdings hatte ich meine letzte Geometriestunde vor ca. 35 Jahren. Smile.
Also nichts für ungut, wenn der Gedanke Mist ist.

Bernd

[NicTheQuick]

Wenn du nur die 3D-Koordinaten hast und dazu die Reihenfolge, in der sie verbunden sind. Wie willst du dann ganz generell heraus finden, welches Dreieck aus drei benachbarten Punkten innen liegt? Für einen Menschen erscheint es logisch, wo innen und außen ist, selbst im Dreidimensionalen, aber wie soll das der Computer machen?

Ich beantworte meine Frage jetzt mal selbst, indem ich einen Link zum englischen Wiki verlinke: Polygon triangulation - Ear clipping method
Sieht leicht zu implementieren aus und läuft in O(n²) Zeit, also schnell genug für Polygone mit wenigen Ecken.

[Sunny]

Also nichts für ungut, wenn der Gedanke Mist ist.

Nein nein der gedanke ist absolut richtig, da dann aus diesem Polygon mehrere konvexe Polygone erstellt werden würden und für konvexe Polygone kann dann die Möglichkeit genutzt werden, die NicTheQuick Zitiert hat. Allerdings wüsste ich nicht, wie ich das realiesieren soll, ein Polygon darauf zu Prüfen ob es auch wirklich konvex ist. Des weiteren kommt noch hinzu, dass das Programm dann auch noch wissen muss, wie so ein Polygon am besten in konvexe Polygone unterteilt werden kann und somit wäre ich wieder am Anfang...

Wenn du nur die 3D-Koordinaten hast und dazu die Reihenfolge, in der sie verbunden sind. Wie willst du dann ganz generell heraus finden, welches Dreieck aus drei benachbarten Punkten innen liegt?

Dann frage ich einfach mal drauf los...
Gäbe es denn eine Möglichkeit, das in 2 Dimensionen zu ermitteln... d.h. wenn z.B.: die Z-Koordinate wegfallen würde?
Wenn das nicht der Fall ist, gäbe es nur noch die Möglichkeit so ein Polygon in konvexe Polygone zu unterteilen aber wie stelle ich das am besten an?

[NicTheQuick]

Auf Konvexheit kannst du ganz easy prüfen. Nehmen wir nochmal das Bild hier:



Der Vektor aus dem Kreuzprodukt der Vektoren P1->P2 × P2->P3 zeigt in genau die entgegen gesetzte Richtung wie der Vektor aus dem Kreuzprodukt P2->P3 × P3->P4.
Das heißt bei einer Linkskurve im Polygon zeigt das Kreuzprodukt in die eine Richtung, bei einer Rechtskurve in die andere. Zeigen alle in die selbe Richtung, ist das Polygon konvex.

Ab hier kannst du den Gedanken sicherlich weiter spinnen. Ich geh jetzt erst mal schlafen.

Noch eins: Die Ear Clipping Methode geht immer, sogar mit Polygonen, die Löcher haben.

[Sunny]

Der Vektor aus dem Kreuzprodukt der Vektoren P1->P2 × P2->P3 zeigt in genau die entgegen gesetzte Richtung wie der Vektor aus dem Kreuzprodukt P2->P3 × P3->P4.

Anscheinend habe ich da im Unterricht nicht so ganz aufgepasst, deswegen verstehe ich das leider nicht so ganz.
Könntest du mir das mal an einem Beispiel vorrechnen und erklären wie man an den Ergebnissen erkennt, ob das Polygon konvex ist oder nicht?

[NicTheQuick]

Aber das Kreuzprodukt zweier Vektoren kennst du schon, oder? Das entspricht dem Vektor, der senkrecht zu den ersten beiden steht. Und je nachdem in welcher Reihenfolge man sie "multipliziert", steht der Ergebnisvektor dann in die eine oder die andere Richtung. In dem Fall oben macht dann auch die Richtung der beiden Eingangsvektoren genau diesen Unterschied aus.

[alter Mann]

Falls Du es nich unbedingt selber machen willst, kannst Du es auch von OpenGL machen lassen.
Stichwort: gluTess... Funktionen