• Advertisement
Sign in to follow this  

GLUtesselator : Issues with zero-area triangles and T-intersections

This topic is 2094 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

[b] [url="http://www.dixittech.com/blog/2012/04/16/glutesselator-issues-with-zero-area-triangles-and-t-intersections/"]GLUtesselator : Issues with zero-area triangles and T-intersections[/url][/b]

[font=inherit][color=#373737][font=inherit][size=4]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.[/size][/font][/color][/font]
[color=#373737][size=4]
[font=inherit]I will try to demonstrate the problem with tessellation of character ‘H’. Input vertices to the GLUtesselator are:[/font] [/size][/color]
[center][url="http://www.dixittech.com/blog/wp-content/uploads/2012/04/H_input.jpg"][img]http://www.dixittech.com/blog/wp-content/uploads/2012/04/H_input.jpg[/img][/url][/center]

[font=inherit][font=inherit]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.[/font][/font]
[center][font=inherit][url="http://www.dixittech.com/blog/wp-content/uploads/2012/04/H_Tesselation4.jpg"][img]http://www.dixittech.com/blog/wp-content/uploads/2012/04/H_Tesselation4.jpg[/img][/url][/font][/center]
[center]
[font=inherit][url="http://www.dixittech.com/blog/wp-content/uploads/2012/04/vertexlist-table3.jpg"][img]http://www.dixittech.com/blog/wp-content/uploads/2012/04/vertexlist-table3.jpg[/img][/url][/font]
[font=inherit]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 were not allowed.[/font] [/center]
[center][font=inherit][url="http://www.dixittech.com/blog/wp-content/uploads/2012/04/H_T-Intersection2.jpg"][img]http://www.dixittech.com/blog/wp-content/uploads/2012/04/H_T-Intersection2.jpg[/img][/url][/font][/center]

[font=inherit]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:[/font]

[center][font=inherit][url="http://www.dixittech.com/blog/wp-content/uploads/2012/04/table_trilist2.jpg"][img]http://www.dixittech.com/blog/wp-content/uploads/2012/04/table_trilist2.jpg[/img][/url][/font][/center]


[center][font=inherit][b]Legend : T = True , F = False[/b][/font][/center]

[font=inherit]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.[/font]
[font=inherit]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.[/font]
[font=inherit]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:[/font]
[center][font=inherit][url="http://www.dixittech.com/blog/wp-content/uploads/2012/04/H_Wanted_Tesselation1.jpg"][img]http://www.dixittech.com/blog/wp-content/uploads/2012/04/H_Wanted_Tesselation1.jpg[/img][/url][/font][/center]

[font=inherit]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.[/font]

Share this post


Link to post
Share on other sites
Advertisement
[quote name='irreversible' timestamp='1334690991' post='4932243']
As a robust workaround, why do you need to recalculate the normal for each triangle? You already know it per face - why can't you use that?
[/quote]

How did I miss that! That should work...

I guess it wasn't very obvious to me as per vertex normals were re-calculated for each triangle based on the geometry and connectivity information for smooth shading in a separate dll. I guess I just need to figure out a way to pass normal information to the dll and to block re-calculation of normal for zero-area triangles. Thanks a lot!

Share this post


Link to post
Share on other sites
[quote name='pjdixit' timestamp='1334692819' post='4932264']
How did I miss that! That should work...
[/quote]

I guess i spoke too early. Even with correct normals because of zero-area triangles there is flickering of edges and there are artifacts with stencil shadows. I suppose it is because of limited precision of depth buffer.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement