I came across this issue when I was trying to triangulate Text entities using GLUtesselator.  However, it can occur during triangulation of any polygon using GLUtesselator. The problem is that sometimes GLUtesselator generates zero-area triangles. Most of the times you can ignore them but there are cases where they can’t be ignored. I am trying to find a solution so that final triangulation of a given polygon do not have any zero-area triangles or T-intersections. As far as I know, GLUtesselator is one of the most robust and stable tesselator available so I would like to stick to it and won’t mind doing some post-processing to fix the triangulation rather than writing a new tesselator myself.

I will try to demonstrate the problem with tessellation of character ‘H’. Input vertices to the GLUtesselator are:

This is how it was triangulated using GLUtesselator. I set the winding to GLU_TESS_WINDING_ODD and GLU_TESS_TOLERANCE was set to default 0.

After preliminary inspection of the triangulation, it seemed as if there were T-intersections at vertex 5 and 10 which raised a red flag as the geometry was further processed by half-edge data structure and T-intersections are not allowed.

However, generating the list of triangles showed that tessellation actually generated zero-area triangles and not T-intersections. Here is the list of generated triangles:  

The problem is  that I can’t use zero-area triangles either as I can’t calculate normal or equation of plane correctly for zero-area triangles. Normals and equation of planes can be  very critical for implementing smoothing and shadow generation algorithms so they need to have a valid value.

So, I am stuck here with a very bad situation: If I have zero-area triangles then I can’t calculate normal and equation of plane correctly which is a must. It is trivial to remove zero-area triangles but if I remove them then I am stuck with T-intersections and I can’t live with them either.

So I would like to make sure that in cases where GLUtesselator generates zero-area triangles, my application will re-triangulate a sub-portion of the polygon such that there are no zero-area triangles or T-intersections. For our example case, triangulation should look some thing like this:

I think its a very fundamental problem and a solution to it will benefit lot of developers working in a similar area. I am sure I am not the first one to stumble upon it. Any suggestions how it can be done? Any alternate approach is very welcome as well.