Search code examples
c++qtopenglgraphicstriangulation

Triangulation of concave polygon using Triangle library

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:

Goal

And here is what I got with Triangle:

Polygon after triangulation 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.

Solution

  • GLU tesselation solved the problem. It shows high performance and good triangulation quality and works well on my laptop as well as on Android tablet Nexus 7. You can find self-contained version of GLU libtess here.