2D Polygon triangulaton algorithms

OpenGL
1

Hello.

I am implementing in my application 2D polygon triangulation algorithms to use in various cases. I have already successfully implemented the Ear clipping algorithm and am about to attempt the sweepline algorithm.

But apart from these two algorithms what other algorithms (open to the public domain of course) exist for polygon triangulation. The polygon types the algorithms should be able to triangulate should be non-simple with the possibility to have holes in them.

I know I can use many open-source already implemented algorithms but I choose not to. Knowing what my code does to the last detail and learning through implementing are my top priorities. So are there any algorithms out there which accomplish what I ask?

Thanks for the help!

2

It sounds you want “constrained Delaunay triangulation”, like this :
http://www.cs.cmu.edu/~quake/triangle.delaunay.html
The idea is to mark border edges and hole edges so that the triangulation never create an “outside” triangle : winding order allow to quickly check what is outside and what is inside.
Some related documentation :
http://www.geom.uiuc.edu/~samuelp/del_project.html

3

ZBuffer this is great! I was actually searching for something like that. Pretty detailed explanation

4

I’m currently considering solutions to a similarish problem I need to solve. I’m using procedural subdivision to make some pretty interesting terrain and even though it’s quite conservative on what it cuts up you inevitably end up with polygons which add nothing to the silhouette. I want to be able to consolidate these and remove the junk triangles that add nothing to the shape. The method is reasonably simple; run through every triangle in the shape, (it is already stored as indices by this point) and find touching triangles which face the same way in 3D space. When this is done, the outline would be discovered by finding edges that don’t touch another selected triangle. It’s then a fairly simple matter to find the sequence that runs around the shape. The problems are that I don’t know how I’d determine whether a potentially concave shape is CW or CCW and I’ve still got to look up the ear clipping algorithm properly.

In any case, that Delaunay triangulation is NICE, just these are singular solid shapes and as such don’t need support for interior shapes.

5

First, determine the ‘up’ vector for your shape. A crude version for heightfield terrain is to use the vertical axis for that.
Then flatten the shapes coordinates according to this direction.
Now Starting from any vertex A, walk in on direction with adjacent vertex I0 and the next one I1, adding or substracting triangle areas defined by A,Ii,Ii+1 : at the end if you have a negative surface sum, it means you walked backward.