Hi,

ich will gern ein beliebiges polygon Triangulieren, bzw Quadrangulieren.
Dafür fallen mir spontan ein paar wege ein.

Quadrangulieren:
Wenn die anzahl der Vertices im Polygon gerade ist kann man einfach jedes Vertex mit dem "gegenüberliegenden" verbinden. Also wenn es 8 Vertices hat würdem an einfach Vertex 1 mit 6 und 2 mit 5 verbinden. 0 und 7 sowie 3 und 4 sind ja schon.
Das würde dann 3 Quads ergeben.

Wenn es eine ungerade anzahl an Vertices sind, setzt man einfach in der mitte des Polygons sowie auf jeder Edge ein neues Vertex ein und verbindet diese.

Ggf. kann man noch beides mischen so das man maximal 2 vertices einfügen muß, statt bei einem Poly mit z.B. 9 Vertices 10 stück.


Triangulieren:
Wäre das simpelste vom Vertex 0 aus jeweils mit 1 und 2, 2 und 3, 3 und 4 etc ein neues triangle zu bilden, oder alternativ auch ein neues Vertex in der mitte platzieren und mit jedem vorhandenen vertex verbinden.


Beides wären meine ansätze wie ich das realisieren würde, nur.. ist es der optimale weg? Und, sobald es ein konkaves polygon ist funktioniert das natürlich alles nicht mehr.. nur, wie macht man es bei einem konkaven polygon?

Oder gibt es tolle Algorithmen dafür die sehr schnell sind und alle möglichen fälle (n-vertices, Konkav, Konvex..) abdecken?

Aya~

Für Dreiecke empfehle ich Corner-Cutting (auch bekannt als Marching). Funktioniert sowohl mit konvexen als auch mit konkaven Polygonen und ist relativ einfach zu implementieren. Wenn du optimal Triangulieren möchtest, also nicht im Sinne der Laufzeit sondern der Qualität des Dreiecksnetzes, such mal nach Delaunay-Triangulation.

Für Quads ist mir nichts bekannt. Ich kenne wen an meinem Lehrstuhl der da wohl dran bastelt, allerdings in der 3D-Variante. 2009 gabs da schon mal nen Paper vom Lehrstuhl zu, vielleicht findet sich da ja unter den Referenzen etwas brauchbares.
http://www-i8.informatik.rwth-aachen.de ... php?id=210 => Mixed-Integer Quadrangulation
Habe von der Thematik leider nicht mehr Ahnung als "die machen irgendwas mit Quads"....bin halt mit meinem eigenen Kram schon ausgelastet

_________________
Yeah!

It is not the best/fastest but for opengl maybe the easiest to implement it glutesselate.

I use that in my glvg project:
http://thuis.vanderhoning.net/svn_glvg
As glutesselate is not the fastest way i chache the tesselate mesh and render that. I only call tesselation if a polygon changes its shape.

More info on glu tesselation can be found at:
http://glprogramming.com/red/chapter11.html

Other possible methods are listed at:
http://vterrain.org/Implementation/Libs ... ulate.html
and there may even be more.

For 2d polygons there is also the shader way skipping triangulation altogether:
http://http.developer.nvidia.com/GPUGem ... _ch25.html

_________________
http://3das.noeska.com - create adventure games without programming

For that you need to have a already triangulated mesh if i read it correctly.

_________________
http://3das.noeska.com - create adventure games without programming

Hi,

in erster linie geht es mir um geschwindigkeit, also lieber einen schnellen algo mit nicht perfekten ergebnissen statt eines etwas langsameren mit über-perfektem



Vieleicht stell ich mich beim googlen auch grad echt doof an, aber ich finde dazu nix.. hast du da zufällig nen guten link wo das verfahren beschrieben wird?


@glutesselate:
I need it for a program that's not even using OpenGL ..

Aya~

Hab dir ne PM mit nem Skript-Auszug geschickt.

_________________
Yeah!

Cool, danke!

Oder auch im DGL-Wiki:

http://wiki.delphigl.com/index.php/Ear_ ... ngulierung

_________________
http://audorra.sourceforge.net//http://andorra.sourceforge.net