Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I wish to triangulate a polygon I only have the outline of (p0, p1, p2 ... pn) like described in this question: polygon triangulation algorithm and this webpage:

I do not wish to learn the subject and have a deep understanding of it at the moment. I only want to see an effective algorithm that can be used out of the box. The one described in the site seems to be of somewhat high complexity O(n) for finding one ear. I heard this could be done in O(n log n) time. Is there any well known easy to use algorithm that I can translate port to use in my engine that runs with somewhat reasonable complexity?

The reason I need to triangulate is that I wish to feel out a 2d-outline and render it 3d. Much like we fill out a 2d-outline in paint. I could use sprites. This would not serve cause I am planning to play with the resulting model on the z-axis, giving it different heights in the different areas.

I would love to try the books that were mentioned, although I suspect that is not the answer most readers are hoping for when they read this Q & A format. Mostly I like to see a code snippet I can cut and paste with some modifications and start running.

share|improve this question
up vote 1 down vote accepted

Not sure if this is the answer you seek, since you mention 3D. But I used Poly2Tri once to convert parametric curved shapes to triangles and it worked fine. I'm saying this because you need an easy implementation, and using this library I did it in an afternoon.


share|improve this answer

Farseer physics have the implementation of 5 different decomposers, which two of them decompose it in triangles. You can check them here

They're under the folder

share|improve this answer
I will look there and update you when I get more work done. – zehelvion Oct 14 '12 at 21:30

I have actually implemented it myself with a simple scanline algorithm. It doesnt grant the best results, but its good enough for me. From what I remember:

  1. You just have to sort your vertices along the X.

  2. Create column spans with the ordered vertices (thus, making it monotone polygons).

  3. And finally, find the diagonals lines connecting the vertices along the spans.

Is it clear?

EDIT: Please dont mind the mess: (look for it at svn/trunk/source/common/src/br/odb/libsvg/)

In fact, I used to provide a standalone runnable jar just for that. More details at:

share|improve this answer
Yes you can and should :P – Gustavo Maciel Oct 15 '12 at 23:36
Edit the answer and put the links in there, it will be easier to spot them :D – Gustavo Maciel Oct 16 '12 at 4:52
Done! Thanks for the tip. – Daniel Monteiro Oct 16 '12 at 13:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.