PDA

View Full Version : Triangulation algorithm



chronozphere
06-11-2006, 03:20 PM
Hi PGD'ers :)

I am looking for a good, fast and solid triangulation algorithm. I will use it to triangulate small/medium polygons with approx <50 vertices.

Does anyone know a good algoritm??

Thank you.

[offtopic] First post on this subforum :razz: ;) [offtopic]

jdarling
06-11-2006, 06:47 PM
Isn't triangulation a 3 point primary system, or am I missing something here? If you mean average or center placement then its simple v1..vN/vC where v1..vN is the sum of each vertext and vC is the number of vertices. If you want to weight each you can do so with sum(vN*W)/(vC*WT) where WT is weight total.

chronozphere
06-11-2006, 07:45 PM
Owh... sorry i didn't explain what triangulation is :oops: :oops:

Triangulation is the process of dividing an arbitrary polygon (array of points) into triangles.
Unfortunatly this is not as easy as it seems. :(

So.. does anyone know a good triangulation algorithm???

jdarling
06-11-2006, 08:46 PM
Well, as long as the polys are convex in nature (meaning that they cannot have indentations) then the process is still as I described above. Simply find the mode point (average) of the points, then utilize two of the points in order along with your mode point to extropolate the triangle. Of course if you have concave polys then its another story all together. In witch case take a visit to your local wikipedia and read up. Find the formula you like, and I'm sure we can help you with implementation :) http://en.wikipedia.org/wiki/Computational_geometry, http://en.wikipedia.org/wiki/Polygon_triangulation, http://en.wikipedia.org/wiki/Point_set_triangulation, or self balancing graph theory (LOL don't look that one up).

Anonymous
07-11-2006, 02:31 PM
Thanx... i will take a look at those pages :D

chronozphere
07-11-2006, 02:33 PM
Oops.. :? that guest was me :lol:

Ingemar
12-10-2013, 08:11 AM
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
12-10-2013, 01:19 PM
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.