Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Like
17Likes
Dislike

Polygon Triangulation

By Daniel Taylor | Published Jun 06 2014 11:38 PM in Graphics Programming and Theory
Peer Reviewed by (Servant of the Lord, dejaime, jbadams)

math triangulation algorithm

Modern GPUs have an annoying habbit of only liking to draw triangles. Often when using 3D modeling programs or vector-based drawing applications to produce game art, you'll get instead a soup of arbitrary polygons. This is an issue if you plan to rasterize these polygons. Fortunately, polygons can be decomposed into triangles relatively easily.

The Algorithm


There are many different ways to decompose polygons into triangles. Typically though you only implement an algorithm that's advanced enough to suit your needs. For example, convex polygons are easier to triangulate than concave ones, and polygons with a hole in the middle of it are a little complicated to get right (and are also beyond the scope of this article: I'll be covering ear clipping at the most in this article. Maybe for another article). If you know that you'll only ever be using convex polygons, then only implement the algorithm for convex polygon triangulation. No need to go overboard :)

For Convex Polygons


This one is by far the easiest. A convex polygon is one where there are no interior angles greater than 180 degrees in the polygon.

For this case, you can pick any vertex in the polygon and create a triangle fan outward. Pretty simple:


Attached Image: convex.png


create a stack with all of the vertecies in CW/CCW order;
pop the top vertex off the stack and store in p0;
pop the top vertex off the stack and store in pHelper;
while the stack is not empty
    pop the top vertex off the stack and store in pTemp;
    create a triangle with vertices p0, pHelper, pTemp;
    let pHelper = pTemp

The created triangle soup will be a complete triangulation of the polygon, but it only works with convex polygons!

For Concave Polygons


A concave polygon is a polygon that has at least one interior angle greater than 180 degrees. This also means that, for any concave polygon, there is at least one line that you can draw that will intersect the polygon at least 4 times.


Attached Image: comparison.png


For each and every closed polygon with more vertices than a triangle, convex or concave, there will always be at least two "ears" (the reason for this is more intuitive than anything: try drawing a polygon that doesn't have at least two ears; you'll find that doubling back to close the shape will inevitably end up creating at least two ears, normally). The way the algorithm works is that, after you clip off the ears of the original polygon, you end up with another closed polygon, with its own two ears to clip off. Rinse and repeat until you have no more ears left to clip off.

This algorithm is called "ear clipping." The image below shows how ear clipping procedurally degenerates a polygon into a soup of triangles by cutting off one corner at a time.

Here's the algorithm:


Attached Image: concave.png


create a list of the vertices (perferably in CCW order, starting anywhere)
while true
  for every vertex
    let pPrev = the previous vertex in the list
    let pCur = the current vertex;
    let pNext = the next vertex in the list
    if the vertex is not an interior vertex (the wedge product of (pPrev - pCur) and (pNext - pCur) <= 0, for CCW winding);
      continue;
    if there are any vertices in the polygon inside the triangle made by the current vertex and the two adjacent ones
      continue;
    create the triangle with the points pPrev, pCur, pNext, for a CCW triangle;
    remove pCur from the list;
  if no triangles were made in the above for loop
    break;

Polygons With Holes


Again, this one is beyond the scope of this article, but the general trick to solving this case is to decompose the polygon into a set of monotone polygons:


Attached Image: monotone.png


Conclusion


That's about it for most simple polygons you'll probably be creating in various art editors. For the most part, you shouldn't need any more than a concave polygon triangulator.

On a more case-specific note, I actually did need a more advanced triangulator, complete with support for triangulating bezier curves and the like. In the end, though, I decided to go with tile-based worlds and rasterized graphics, as they tended to end up looking better anyways :P

Well, the little thingy on the site says that I should write articles, no matter how trivial. In my defense, I know that I spent much more time than I should have needed to trying to figure out ear clipping. The same goes for monotone triangle decomposition, but that was just a matter of figuring out the state transitions.

Anyway, hope someone finds this helpful.

Article Update Log


8 June 2014: Added just a little more explanation, as per Aardvajk's advice
6 June 2014: Initial release



About the Author(s)


I'm an indie, kinda sorta, trying to do this whole college thing. I'm currently making a game using a lot of vector-based artwork, so I've gone through this stuff before :)

License


GDOL (Gamedev.net Open License)




Comments

Very nice, simple and understandable explanation plus pseudo code.

Yes, I like these very focused articles. The algorithm in the middle might benefit from a bit more of a discussion rather than just the images and psuedo though.

Just my two cents: If you are allowed to introduce new vertices (which you usually are), for convex polygons it is usually better to add a vertex in the center and join it to the other vertices, instead of just using one of the vertices of the polygon. This way you avoid slivers and have better triangles in general.

 

EDIT: The article is awesome, by the way ;)

Thanks, finally the return of a technical article on GameDev that is not another "Defining the color of your box to optimize your shipping".

Can I also suggest to look at the "triangle" library? If you need quality triangolator, that's your stop.

Aside from "triangle" library, here's also a lightweight solution that supports triangulation with holes and even optimal convex partition.

 

https://code.google.com/p/polypartition/

good article! smile.png

some while ago, I've also spent some time to write a triangulator. it started basic, but ended up to be hell of a stability hunt. with wholes, intersecting shapes, all possible types of shapes that CVS supports, there was always some case the killed the algorithm. sometimes tiny edges below epsilon, sometimes very very flat triangles that had such a huge variance in edge size that float wasn't enough. at some point I've decided to move to integer for better stability... at least that was my thought, turned out it has a whole different area of issues. e.g. intersecting lines in integer will 'snap' them into a different place and previously intersecting lines might intersect once again or might be intersected now by previously completely unrelated lines and create yet again more permutations. getting it stable, fast was really a challenge. yet now on mobile, rendering CVS at high framerate is really satisfying, you can use the typical MSAA and it looks totally smooth.
http://twitpic.com/82cun4

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS