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: 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. 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: 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:

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