Triangulation of concave polygon using Triangle library

Question

I'm using a C++ wrapper of the Triangle library and can't get rid of the triangles that are out of my polygon.

Here is what I want to get:

And here is what I got with Triangle:

(I intentionally didn't fill triangles to show that there are some triangles out of polygon)

I tried to get rid of outer triangles using Ray casting algorithm (finding the center of triangles edges and looking if it is in polygon. If at least one is not there than don't paint this triangle) but it is very slow for my purpose (the polygon is updated every frame). Did I miss something? Which parameters should I pass to Triangle to triangulate concave polygon?

If it is not possible to do what I want with Triangle, could someone suggest me a fast method for painting polygon (my program uses Qt Quick Scene Graph and I'm restricted to paint only in triangles or convex polygons as OpenGL requires)? Currently I want to try tessellation method from GLU and drawing using stencil buffer. Also I plan to try this library.

@j-p I tried ear clipping implementation from [this library] (github.com/ivanfratric/polypartition) but it doesn't produce correct results. Also I'm concerned about O(n^2) complexity of ear clipping. — Thelastpolaris
Do you have to deal with rendering completely generic concave polygons? Or is it always a simple shape like the one you show in your pictures? For this kind of shape, it would be very easy to generate triangulated geometry directly. — Reto Koradi
@RetoKoradi what do you mean by generating geometry directly? — Thelastpolaris

Reto Koradi Reto Koradi · Accepted Answer · 2016-06-05T04:43:59

There are at least two ways for drawing general concave polygons:

Apply a triangulation algorithm. This is what you have been trying. There should be plenty of literature about the topic, and source code you may be able to use.
Use the stencil buffer. This is illustrated in my answers to these older questions: Black out everything outside a polygon, How to force openGL to draw a non-convex filled polygon.

However, if you only need to draw the half-moon type shapes that you use in your example, and not arbitrary concave polygons, this all seems much more complicated than necessary. You can easily build a triangle strip to represent this shape.

Your current half moon is probably rendered with a vertex sequence that looks something like this, which defines the vertices in the order needed for a (concave) polygon:

0                                              9
  17                                        10
  1   16                                11   8
            15                    12
      2             14    13             7

            3                      6
                    4      5

You can render this shape directly with primitive type GL_TRIANGLE_STRIP by ordering the vertices differently, so that vertices from the bottom arc alternate with vertices from the top arc:

0                                             17
   2                                        16
  1    4                                14   15
             6                    12
      3              8    10             13

            5                      11
                    7      9

Triangulation of concave polygon using Triangle library

3 Answers