<p>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<sup>++</sup>, is to use the stencil buffer. </p>

<p>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.)</p>

<p>The stencil buffer approach should also work with self-intersecting polygons.</p>

<p>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</p>

<p>More information on the stencil buffer can be found in <a href="https://www.khronos.org/opengl/wiki/Stencil_Test" rel="nofollow noreferrer">OpenGL Stencil Tests</a> and in <a href="http://www.glprogramming.com/red/chapter14.html#name13" rel="nofollow noreferrer">Drawing Filled, Concave Polygons Using the Stencil Buffer</a></p>

<p><sup>++</sup> 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 <em>nearly</em> O(n) time complexity. </p>

<p>However if you do a search for Seidel, note that the code in <a href="http://www.cs.unc.edu/%7Edm/CODE/GEM/chapter.html" rel="nofollow noreferrer">Narkhede &amp;
Manocha</a> is <em>not</em> 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))  &amp; \text{if $n$ &gt; 1} \\
0 &amp; \text{otherwise}
\end{cases}$$</p>

<p>In <em>practical</em> terms, you can consider it to be constant as it grows so slowly.</p>

CC BY-SA 3.0
2017-02-22T17:40:27.177Z
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
CC BY-SA 3.0
2017-02-21T12:16:05.027Z
2018-03-06T10:52:19.053Z
2018-03-06T10:52:19.053Z
Simon F
<p>Have you access to the OpenGL utility library? If so, you could use the tesselation functions from that. See this guide : <a href="http://www.glprogramming.com/red/chapter11.html#name1" rel="nofollow noreferrer">Polygon Tessellation | OpenGL Programming Guide</a></p>

CC BY-SA 3.0
2017-02-22T17:38:33.153Z
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
CC BY-SA 3.0
2017-02-22T00:10:33.493Z
2018-03-04T19:56:52.873Z
2018-03-04T19:56:52.873Z
PeteUK
<p>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 href="https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf" rel="noreferrer">a paper on ear clipping</a> and also <a href="https://www.geometrictools.com/Source/ComputationalGeometry.html" rel="noreferrer">an open-source implementation in C++</a>. There are many other links available on the web, too.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-02-21T16:41:57.947Z
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
CC BY-SA 3.0
2017-02-21T01:25:21.483Z
2017-02-21T01:25:21.483Z
Nathan Reed
<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2017-02-21T00:49:07.873Z
Is the region always convex, or might it be concave?
Nathan Reed
CC BY-SA 3.0
2017-02-21T00:50:45.137Z
It could be either - it's guaranteed to be enclosed, though.
Sushisource
<opengl>
Turn an enclosed region into a triangle mesh
Sushisource
# Turn an enclosed region into a triangle mesh

(Asked by: username_0 on 2017-02-21)

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?

**Tags:** opengl

> **Comments:**
> **username_1**: Is the region always convex, or might it be concave?  
> **username_0**: It could be either - it's guaranteed to be enclosed, though.  

---

## 3 answers

### Answer by username_1 on 2017-02-21. Score: 6 | Accepted answer

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](https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf) and also [an open-source implementation in C++](https://www.geometrictools.com/Source/ComputationalGeometry.html). 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.

> **Comments:**
> **username_4**: 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'  

---

### Answer by username_2 on 2017-02-21. Score: 6

If your aim is just to fill the region and since you say you're using opengl, an alternative to username_1'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](https://www.khronos.org/opengl/wiki/Stencil_Test) and in [Drawing Filled, Concave Polygons Using the Stencil Buffer](http://www.glprogramming.com/red/chapter14.html#name13)

++ 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](http://www.cs.unc.edu/%7Edm/CODE/GEM/chapter.html) 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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_3 on 2017-02-22. Score: 4

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](http://www.glprogramming.com/red/chapter11.html#name1)

> **Comments:**
> **username_0**: 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.  

---

