A GPU draws triangles, and it draws them very quickly.
But it won’t draw more complex polygons, like quadrilaterals, pentagons, hexagons, etc. So if you want to use a GPU to draw any polygon other than a triangle,
you’ll need to break that polygon into multiple triangles, then pass these triangles to the GPU for drawing.
The GPU will seamlessly fill the triangles, leaving no visible evidence that the polygon was actually drawn as a set of triangles.
What we need is an algorithm that will consistently break up a polygon — even a very concave, possibly convoluted one — into triangles. For optimal GPU handling, we would prefer that it generate as few triangles as possible. It turns out that the minimum number of triangles is always n-2, where n is the number of corners of the polygon. So if we have a twenty-cornered polygon, it can always be broken up into eighteen triangles. And incidentally, all of those triangles will use corners of the original polygon as their corners; none of triangle’s corners will be points in the interior of the original polygon, nor along any of the original polygon’s sides.
Is it sometimes possible to break up a polygon into fewer than n-2 triangles? Yes, it is. For example, here’s a five-pointed star, which is a ten-cornered polygon. It can be rendered as eight triangles, like so.
But it could be drawn as just four triangles, like this.
However, there’s an important reason not to do that, and we’ll talk about it a bit later. For now, just be aware that our algorithm is going to make n-2 triangles, every time.
Question: Is it always possible to break up a concave polygon into n-2 triangles, using only corners of the original polygon? And if it is, is it guaranteed that the algorithm described in this presentation will always find such a solution? Yes, and yes. However, we’re not going to get into the proof of that here. Just trust me, it will always work.
You might be wondering: Why clockwise? What difference does it make? Isn’t that just an arbitrary direction? And what does clockwise mean, anyway? Doesn’t that depend on your coordinate system? Does your Y coordinate ascend from the bottom up, or from the top down, and doesn’t that affect the meaning of clockwise?
Yes, that’s all correct. What this requirement really says is: Decide what clockwise means in your system, then stick with that decision. It does matter, because if you trace the polygon in the wrong direction, then this algorithm is going to try to triangulate the area outside your polygon, which won’t work, and it’s not what you wanted anyway.
The polygon can’t cross itself, but can it touch itself? The answer is: maybe.
If it touches itself with shared corners, like this,
or fully shared sides, like this, that’s OK. (In fact, we’re going to be using that technique later when we talk about holes.)
But — if it touches itself corner-to-side, like this,
or partial-side-to-side, like this, that may not be OK. There’s an infinitely fine line between touching and crossing, and even if the touches are mathematically exactly correct, they still might fail our algorithm. So don’t do that.
Furthermore, all the triangles will be traced clockwise. That might not mean anything to your GPU — or, it might be necessary to ensure that the triangles fit together, filling all pixels without visible seams.
This candidate triangle is rejected, because it represents a locally counterclockwise bend, and therefore is on the outside of the polygon.
This candidate triangle also is rejected, because it includes a corner of the polygon in its interior space.
This candidate triangle is accepted. So we add these three corners, in this order (which is clockwise) to our list of triangles.
Then we remove the middle corner (of the accepted triangle) from our working polygon, which exactly removes the accepted triangle’s area from the polygon.
Then we go back and do it again. The polygon gets smaller and smaller as triangles are added to the list. When the polygon is reduced to just two corners, the process is done, and the triangle list is complete.
And if they’re not, then omitting that triangle might cause a tiny gap between the upper four and lower three triangles. That gap could be visible to the user as a light scattering of unfilled pixels. Yuck!
So, let’s watch the algorithm in action. Here’s a well-behaved polygon. It has seven corners, and coincidentally is shaped like the number seven.
(These images are generated from actual code; see the live animation at the bottom of this page. The JavaScript source code within the page itself can be viewed by choosing Develop > Show Page Source, or equivalent, in your web browser.)
Done! The seven-cornered polygon turned into five triangles, as expected.
Hey, it sure looks like we’ve only got one triangle left. But it made two triangles. Why did it do that? Of course, the reason is because the algorithm isn’t smart enough to see that it could have made one triangle. So should we modify it to detect this condition and make one triangle? No, we should not. Why not?
Notice that all of these triangles interface with each other by full sides. This triangle shares a full side with this one.
This one shares a full side with this one.
If we make this remaining (grey) area into a single triangle, then it will interface with the triangle below by less than a full side. That could cause the missing-pixels problem we discussed earlier in the zero-area-triangle situation.
So it’s best just to let the algorithm do its thing, generating exactly n-2 triangles every time.
Now let’s explore the possibility of a polygon with a hole.
If you just want the hole to contain a different color (or fill-pattern) than does the rest of the polygon, you can simply render the outside polygon first,
then render the hole polygon over it.
That works, but it does require the GPU to fill all the pixels in the hole’s area twice, first with yellow (in this example), then again with red. It also requires the GPU to render the yellow triangles first, then the red ones — instead of letting it render all of this object’s triangles in whatever order it finds most efficient.
But the biggest reason not to do it that way is that you might actually want a true hole in the polygon, not just a different fill. A true hole will allow whatever has already been drawn to show through the hole.
So how do we do it? First, check every connection between any corner of the outer polygon, and any corner of the hole polygon, keeping only the shortest one you find.
The connector must not cross any side of either polygon, so this one would be invalid.
Here’s why you want the shortest connector: This connector might not be considered to cross any side of either polygon,
but to avoid unnecessary potential problems, it would be better to use this one instead. It will always be shorter, so using the shortest connector will avoid such problems.
Here is the shortest valid connector in our example. When you find it,
then turn the two polygons into one, big polygon, that traces clockwise around the outside, goes in on the connector, then traces the hole polygon in reverse, and comes back out on the connector.
Now we have a single polygon, traced clockwise overall, and which does not cross itself (although it does have some duplicate corners at the connector; that’s OK). Simply apply the algorithm we already have discussed, and the polygon will be triangulated, with the hole left open.
Here’s an example: The number six. It has a big hole in the middle.
Triangulating...
Done!
Why is that OK? Because we haven’t even started the triangulation yet. Any modifications to the original polygon are perfectly fine, as long as it’s still a well-behaved polygon when you start the triangulating procedure.