# Turn an enclosed region into a triangle mesh

I have a (2d) region defined as a list of vertices that I'm currently drawing as a line loop in opengl. I want to draw this region solidly. I started by using triangle fan, but that doesn't work if the region has vertices positioned at the same angle (relative to the center) but different radii, because then that whole region is draw solid.

So, I think I just need some general method to convert an enclosed spline/list of points into a triangle mesh. Maybe there's a better way?

• Is the region always convex, or might it be concave? – Nathan Reed Feb 21 '17 at 0:49
• It could be either - it's guaranteed to be enclosed, though. – Sushisource Feb 21 '17 at 0:50

If the number of vertices is not too large, I would suggest looking into "ear clipping". It's a straightforward method to triangulate possibly-concave polygons, as long as they don't have holes. However, it's $O(n^2)$ in the number of vertices, so may not a great choice if you need to handle a large number of verts. Dave Eberly has a paper on ear clipping and also an open-source implementation in C++. There are many other links available on the web, too.

The basic idea is to find an "ear" of the polygon, which is defined as a triangular subset of the polygon, formed by three consecutive vertices of the polygon. Once you find an ear, you add it to the output triangle list, and remove it from the original polygon (which reduces the number of vertices by one). Repeat this until the polygon is gone.

The reason it's $O(n^2)$ is that you have to repeatedly search the list of vertices to find another ear to remove. There are more efficient triangulation algorithms as well, but they're more difficult to implement.

• One method to make this work faster is to perform a prepass on your array of vertices, duplicating or merging very close vertices and removing vertices that are in a straight line between two neighbouring vertices. They won't contribute to the resulting mesh in a meaningful way so they don't need to be considered. The amount of error you want to consider valid is up to you. This is a good approach when dealing with user input which is inherintly 'dirty' – Steven Feb 21 '17 at 16:41

If your aim is just to fill the region and since you say you're using opengl, an alternative to Nathan's suggestion of using a triangulation algorithm++, is to use the stencil buffer.

Assuming you want odd/even fill, clear the stencil buffer, dice up your polygon as before but have your triangles just (IIRC) invert the stencil. When all are sent, draw again but only where the stencil is non-zero. (It's been a while but I think you can clear the stencil buffer at the same time as this second pass to save time on the next complex polygon.)

The stencil buffer approach should also work with self-intersecting polygons.

One final thing, I think it is more fill-efficient if you use a triangle strip rather than a fan when you chop up your polygon. You just need to access your vertices in something like 0, 1, N-1, 2, N-2 etc. order

More information on the stencil buffer can be found in OpenGL Stencil Tests and in Drawing Filled, Concave Polygons Using the Stencil Buffer

++ Though, if you do want to use a triangulation algorithm but have a very large number of vertices, you could try Seidel's method as it's 'relatively' easy to implement but has nearly O(n) time complexity.

However if you do a search for Seidel, note that the code in Narkhede & Manocha is not actually Seidel's method as theirs is only O(n log n) not the faster O(n log* n) you should expect, where, if you're not familiar with it, $$log^*n =\begin{cases} 1+ log^*(log(n)) & \text{if n > 1} \\ 0 & \text{otherwise} \end{cases}$$

In practical terms, you can consider it to be constant as it grows so slowly.

• This is a really neat technique thanks for that. I think I managed to find an off-the-shelf tesselator I can use, but I might have to try this out just because it's a nifty idea. – Sushisource Feb 22 '17 at 17:40

Have you access to the OpenGL utility library? If so, you could use the tesselation functions from that. See this guide : Polygon Tessellation | OpenGL Programming Guide

• Interesting, thanks for that. I'm using rust and GLium, which I don't think has bindings to this but I could look into contributing a patch. – Sushisource Feb 22 '17 at 17:38