Nonconvex Polygon Tesselation

(L) [2007/10/17] [dr_eck] [Nonconvex Polygon Tesselation] Wayback!

Time to question the experts! I know that an arbitrary polygon can be tesselated into triangles. I've even found a reference for how to do it for convex polygons in RTNews, with a reference to a SIGGraph tutorial (Berlin, "Efficiency Considerations in Image Syntehsis", 1985) that tells how to extend this to nonconvex polygons. Unfortunately, I can't find the reference on the net. Can anyone tell me where I can get a description of an algorithm for tessellating nonconvex polygons into triangles? Thanks.
_________________
Opinions? Those are *facts* son.

(L) [2007/10/18] [greenhybrid] [Nonconvex Polygon Tesselation] Wayback!

An idea:

(take a pen and paper please, otherwise it might be hard to imagine by my words only;))

Let ABCD be a polygon. The corner at D is the one that makes your poly non-convex.

Now let P be any plane through A and D. Let E be the intersection between the line BC and P.

Now extract two new triangles ABE and DEC.

I hope you get my idea. There might be some deficiencies and special cases where this won't work, but at least it works in 2d, that is if all points lie in the same plane, on a paper here. [SMILEY Smile]
_________________
[LINK http://greenhybrid.net/ greenhybrid.net]

Real Men code Software Graphics.

(L) [2007/10/25] [bitshit] [Nonconvex Polygon Tesselation] Wayback!

I asked a similar question sometime ago on devmaster:

[LINK http://www.devmaster.net/forums/showthread.php?p=51972]

I got away with just writing a wrapper arounf the GLU tesselator, but as someone pointed out there you could take its sourcecode to remove the GLU dependancies and tweak it to your own needs.

(L) [2007/10/26] [dr_eck] [Nonconvex Polygon Tesselation] Wayback!

Thanks for the replies. From the first few I learned that "triangulation" is the search term to use. I've always thought of triangulation being "finding the coorrdinates of a position given known coordinates of three positions," so I started by looking for tesselation. Anyway, here a a summary of my findings for future reference:

For the most general case use Delaunay triangulation.

If your polygon has no holes and no edge intersects another, there are several options, two of which are:

1. If O(n^2) efficiency is fast enough, use Meisters' "Ear Cutting" method: [LINK http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/cutting_ears.html]

2. If you want O(n log n) efficiency, use the Seidel method: [LINK http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html]

3. There is an O(n) method, but the world has agreed that it's not worth the effort to program

If your polygons have no "reflex" angles (i.e. no angles that point into the polygon), just pick a vertex and draw diagonals to the other vertices to create the triangles.
_________________
Opinions? Those are *facts* son.

(L) [2007/10/26] [jogshy] [Nonconvex Polygon Tesselation] Wayback!

Other way to treat them is to thing they are just a group of coplanar triangles... not sure if that can help you.

why you want non-convex polys? Well... I just enforce the artists to use triangles or quads... non-convex polys are always a headache ( imagine one with a hole in the middle... ). What i'm trying to tell you is ... don't let the artists to use them, no , never, nein, niet, ni de coña, nevah!

[SMILEY Laughing]
_________________
I know I ask too much... but i'm on panic mode and there is no panic button to press [SMILEY stick out tongue]

(L) [2007/10/26] [dr_eck] [Nonconvex Polygon Tesselation] Wayback!

I agree that life would be easier if only quads & tris were allowed, but I want to be able to handle more general polygons, and ear cutting is not that hard. Restricting my users to simple (nonintersecting) polygons is physically justifiable, so I don't have to invite an accusation of laziness.
_________________
Opinions? Those are *facts* son.

Nonconvex Polygon Tesselation back