Triangulation algorithm

[Ingemar]

I just found this old thread when searching for a good solution for polygon triangulation. Is there a good solution around?

I found this reasonably simple program:

http://www.flipcode.com/archives/triangulate.cpp

and converted it (back?) to plain C (from where it is easier to make FPC code of it) and it seems to work, but is there something better available?

[phibermon]

I've searched for a robust solution for quite some time, found various C/C++ based sources for tessellation/triangulation that I felt were robust enough. However I've never found anything that I could be bothered to spend the time translating to pascal, mainly because I use the GLU tessellator which is available on Win/Mac/Linux as part of the OpenGL libs (so nothing to install/setup in addition to the standard OpenGL offering). I use it for my OpenGL 2D editor, SVG importer and for importers for 3D models (in various formats) that are not already triangulated.

I figured that any platforms GLU is not available on (don't know, IOS maybe) I'd be using models that were stored in a GL optimized/friendly manner, pre-tesselated and would simply not support none tesselated models on platforms without GLU and it's tessellator.

I'd prefer a native solution of course and would happily split the workload on translating a robust C lib.

Tip : if you're going to use the GLU tesselator, bare in mind that the callback functions that you bind need to be declared with the correct calling convention in order to work on the 3 major platforms (I'll refer to my code if you have issues, probably 'stdcall') and they must also be flat, unit level functions. Doesn't like the callbacks to be members of a class at all.

But it works. it's fast and it's available on most of the GL platforms.

EDIT : You don't need an OpenGL context to use the GLU tesselator, you can make use of it stand alone or use it's output with Direct3D even (which a lot of people in the Direct3D world have done in the past) and it'll be available on most systems regardless if they have any form of hardware OpenGL acceleration.

It works fine for both 3D and 2D I/O, if working in 2D simply pass the vertices with a zero Z value.

Oh and judging by the size of the source you linked to and the size and complexity of solutions I've seen online, I would guess that you couldn't concider that source robust, it will perhaps have points of failure depending on input, it may not support the insertion of new points IE handling intersections. Reading the comments it also doesn't support holes (which you may not care about depending on your intended input) Also if you usage pattern for triangulation requires real-time performance I would guess that there are faster solutions.