Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/algorithm2.html

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
add comment

3 Answers

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.

Link: http://code.google.com/p/poly2tri/

share|improve this answer
add comment

Farseer physics have the implementation of 5 different decomposers, which two of them decompose it in triangles. You can check them here http://farseerphysics.codeplex.com/SourceControl/changeset/view/99885#1436514

They're under the folder

>SourceFiles
    >Common
        >Decomposition
share|improve this answer
    
I will look there and update you when I get more work done. –  Arthur Wulf White Oct 14 '12 at 21:30
add comment

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: http://code.google.com/p/bzk3/source/browse/#svn%2Ftrunk%2Fsource%2Fcommon%2Fsrc%2Fbr%2Fodb%2Flibsvg (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: https://sites.google.com/site/montysprojects/current-projects/svgtriangulator

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
add comment

Your Answer

 
discard

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.