• ### Announcements

• #### Wondering what's new and changed at GameDev.net?06/20/17

Check out the latest Staff Blog update that talks about what's changed, what's new, and what's up with these "Pixels".
Followers 0

# OpenGL Polygon Tessellation/Triangulation Implementations

## 30 posts in this topic

I'm currently looking for triangulator implementations, and a few look fairly promising.

How does the OpenGL Standard Implementation (by SGI) tessellator implementation compare in performance to, say, the "Fast Polygon Triangulation based on Seidel's Algorithm?" (http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html) Does it lose much in performance what it gains in robustness?

The former has the advantage of a very permissive license, I'm just concerned about how much I would lose by going with it if I'm not depending on managing a lot of obscure cases.

0

##### Share on other sites
I appreciate that it may be a pretty obscure question, but I'll try bumping it just once.

Thanks.
0

##### Share on other sites
Full source to a seriously great program right here: www.cs.cmu.edu/~quake/triangle.html
0

##### Share on other sites
I can recommend GLU tesselator which is very robust, has alot of features and performs really great. It's also really easy to use compared to others!
0

##### Share on other sites
Quote:
 Original post by mokaschittaI can recommend GLU tesselator which is very robust, has alot of features and performs really great. It's also really easy to use compared to others!

GLU tesselator creates T-junctions, which is why you should never use it for serious triangulation jobs.
0

##### Share on other sites
Quote:
 Original post by samster581GLU tesselator creates T-junctions, which is why you should never use it for serious triangulation jobs.
Yup, I found that to be the case as well.
0

##### Share on other sites
Quote:
 Original post by samster581GLU tesselator creates T-junctions, which is why you should never use it for serious triangulation jobs.

That's a sign of an incorrect combine callback function. If tesselating non-intersecting polygons, t-junctions cannot happen, since the tesselator will not generate new vertices. What may happen is that it might merge nearby vertices in epsilon range. In that case, it's the job of your combine function to make sure no t-junctions are created (by simply snapping onto one of the endpoints, instead of interpolating a new vertex). Note that the algorithm may generate degenerated (zero-area) triangles, but these are trivially removed.

Self-intersecting polygons, which are evil anyway, may generate t-junctions. But any tesselator that operates on a per-polygon granularity will have that problem.

[Edited by - Yann L on October 19, 2010 1:42:56 PM]
0

##### Share on other sites
Quote:
Original post by Yann L
Quote:
 Original post by samster581GLU tesselator creates T-junctions, which is why you should never use it for serious triangulation jobs.

That's a sign of an incorrect combine callback function. If tesselating non-intersecting polygons, t-junctions cannot happen, since the tesselator will not generate new vertices. What may happen is that it might merge nearby vertices in epsilon range. In that case, it's the job of your combine function to make sure no t-junctions are created (by simply snapping onto one of the endpoints, instead of interpolating a new vertex). Note that the algorithm may generate degenerated (zero-area) triangles, but these are trivially removed.

Self-intersecting polygons, which are evil anyway, may generate t-junctions. But any tesselator that operates on a per-polygon granularity will have that problem.

Well, I certainly would like to see a working example of a GLU tesselator that doesn't create T-junctions.

I use code from this example to tesselate 3D text:
http://realmike.org/blog/articles/triangulating-and-extruding-arbitrary-polygons/

GLU tesselator does create T-junctions when you send it non-intersecting polygons. These polygons are concave, but non-intersecting.
And they are simple polygons, no holes.

And I think the Combine callback function was only designed to record new vertices being inserted, not modify their position,
so it's not entirely the user's fault for using it as so.

Here's some examples of GLU tesselator. The green edge is where vertices don't connect.
src

And, some of these T-junctions happen at the original vertices, so the Combine callback function may not even be called.

[Edited by - samster581 on October 19, 2010 6:10:35 PM]
1

##### Share on other sites
Very strange, I never encountered anything like this. And we've been using the tesselator for years. Our engine would've barfed at us at the first sight of a t-junction.

Then again, I think we aren't using the old SGI implementation. What implementation did you try to get these results ?
0

##### Share on other sites
Quote:
 Original post by Yann LThat's a sign of an incorrect combine callback function. If tesselating non-intersecting polygons, t-junctions cannot happen, since the tesselator will not generate new vertices. What may happen is that it might merge nearby vertices in epsilon range. In that case, it's the job of your combine function to make sure no t-junctions are created (by simply snapping onto one of the endpoints, instead of interpolating a new vertex). Note that the algorithm may generate degenerated (zero-area) triangles, but these are trivially removed.
It's been a while, but I remember testing this with some very simple test cases (simple polygons with no holes and few edges) and getting T-junctions. Of course user error is always a possibility with this sort of thing, but the test cases were pretty straightforward, so I don't think it's a given that user error was the culprit. (I'm not that familiar with the different versions of the GLU library, but this was with the version that ships with Windows, so I imagine it's a fairly old implementation.)
0

##### Share on other sites
I had a client complain about similar problems with the GLU tessellator. It turned out that the tessellator was doing the right thing. The *fonts* were malformed, and several characters at specific sizes would have loops due to self-intersection of the font curves. Ideally you want to let the font designer know that he needs to fix his curves, but of course that is impractical :) My solution was to detect and remove the loops, although some very unusual fonts still caused some problems. The point is: You might want to look at the *input* to the tessellator and see whether it is what you expect.

0

##### Share on other sites
I'm using the glu.h header and libs that came with my VS2008 compiler or Windows Platform SDK.

And my input data comes from the path created from GDI's TextOut (see tutorial link above).
And I just checked it, there are no weird loops in the path.

// letter E, 13 points// starting point duplicated at end-128, -23, 0-128, 23, 0-94, 23, 0-94, 15, 0-119, 15, 0-119, 5, 0-96, 5, 0-96, -3, 0-119, -3, 0-119, -15, 0-93, -15, 0-93, -23, 0-128, -23, 0

src
0

##### Share on other sites
Samster, I can't reproduce your problem. Using your input data set (removed the last duplicate entry, but the triangulation is correct even if it is left in) I get the following triangles:

11 9 0
1 0 9
8 1 9
5 1 8
7 5 8
4 1 5
3 1 4
2 1 3
5 7 6
9 11 10

There are no t-junctions.

I have tested this on the old standard SGI implementation. So either your implementation of the GLU tesselator is broken, or you are using it incorrectly.
0

##### Share on other sites
Yann, would you be willing to post the code you used to generate those results? (It might be informative.)
0

##### Share on other sites
Just the minimal standard usage. Single polygon, single contour, all points pushed sequentially. Edge flag callback defined, so to get triangles only.

SGIs reference implementation.

I slightly modified the SGI code for some other project, changing the rules for vertex merging through the combine callback. But for this example it shouldn't make a difference.
0

##### Share on other sites
Ok, here's my test code (using samster581's data with the duplicate vertex removed):

#include <iostream>#include <windows.h>#include <GL/glu.h>double data[] = {    -128, -23, 0, -128, 23, 0, -94, 23, 0, -94, 15, 0,    -119, 15, 0, -119, 5, 0, -96, 5, 0, -96, -3, 0,    -119, -3, 0, -119, -15, 0, -93, -15, 0, -93, -23, 0};int count = 0;void CALLBACK Vertex(GLvoid* index){    std::cout << (int)index << (++count % 3 == 0 ? '\n' : ',');}void CALLBACK EdgeFlag(GLboolean flag) {}int main(){    GLUtesselator* tesselator = gluNewTess();    gluTessCallback(        tesselator,        GLU_TESS_VERTEX,        reinterpret_cast<GLvoid (CALLBACK *)()>(&Vertex)    );    gluTessCallback(        tesselator,        GLU_TESS_EDGE_FLAG,        reinterpret_cast<GLvoid (CALLBACK *)()>(&EdgeFlag)    );    gluTessBeginPolygon(tesselator, 0);    gluTessBeginContour(tesselator);    for (int i = 0; i < 12; ++i) {        gluTessVertex(tesselator, &data[i * 3], (void*)i);    }    gluTessEndContour(tesselator);    gluTessEndPolygon(tesselator);    gluDeleteTess(tesselator);}

Can anyone spot any obvious errors in the above? Or does this look correct?
0

##### Share on other sites
Interesting...

I took a look through the Mesa repository logs, and there have been only very minor changes (none to the core algorithm) since the SGI SI tessellation code was first incorporated in 2001, so I would presume that it's fairly reliable; OSG incorporates Mesa's code too.

I'm curious about which non-Mesa GLU tessellators are having problems; assuming/hoping they aren't from Mesa.
0

##### Share on other sites
I tried this with a couple of other GLU implementations, and I think I know what is going on.

I'll repost Samsters image here for convenience:

Now consider the following three triangles:
9 0 4
9 4 5
9 5 8

The first, 9 0 4, may look like a triangle creating two t-junctions with vertex 5 and 8. But in fact, it does not. It is topologically connected to these points by the two zero-area triangles 9 4 5 and 9 5 8. If you are having trouble visualizing this, then imagine vertices 5 and 8 being slightly offset to the right.

So geometrically speaking, the algorithm is not generating t-junctions. It is connecting the vertices using degenerated triangles, which is perfectly fine mathematically. Such a mesh will render correctly, and will be correctly processed by any geometrical algorithm that handles zero-area triangles (which a numerically stable algorithm should). For example, creating a connected edge graph on this mesh will work fine. If you removed these two degenerated triangles, then you would in fact have a t-junction, and an edge graph will fail to cover the resulting topological gap.
1

##### Share on other sites
Problem with 0 area triangles is you cant calculate normals for them... and you might need to do that.

I guess what your proposing (if the algorythm really does this) is probably ok, because if you put the mesh halfway through a point reduction process it would still be contained and filled, and thats a good thing i guess.

Id say that would be the passing test.
1

##### Share on other sites
Quote:
 Original post by Yann LNow consider the following three triangles:9 0 49 4 59 5 8

I would be surprised if a tessellator for a simple polygon produces zero-area triangles. Not claiming they do not, but you have to work very hard to get them to do this...

I ran the "E" data through my own tessellator. Mine produces triangles just like Samsters, except that I also have <0,9,8> and <0,5,4>. His tessellated polygon shows that edges <0,5> and <0,8> are missing. When these are included (as they should be), there are no T-junctions.
0

##### Share on other sites
Quote:
 Original post by Dave EberlyI would be surprised if a tessellator for a simple polygon produces zero-area triangles. Not claiming they do not, but you have to work very hard to get them to do this...

The GLU tesselator implementation on my Linux box does this on Samsters' data set. I don't know which implementation it is exactly, but it's probably one that came with Mesa. It's not the SGI reference one I mentioned earlier, as that one produces normal (ie. non-zero area) results.

I have not tried this on Windows yet.
0

##### Share on other sites
Here's the order of triangles produced for me:

1,4,0
4,1,2
4,2,3
6,8,5
8,6,7
0,9,11
9,4,5 -> degen
9,5,8 -> degen
11,9,10

I should have only 8 triangles, but I get two more (degenerate ones).

And I just noticed that my Combine callback function is called exactly once in the very beginning:
CombineCB: -128.000000, -23.000000, 0.000000

Am I getting these errors because I included a duplicate vertex point at the end of the list?
I thought I needed to duplicate it to close the poly loop.

And yes, I have a cleanup function that removes degenerate triangles, so I end up with T-junctions.
0

##### Share on other sites
Quote:
 Original post by samster581bad blocking edge

It's not a 'bad edge'. The triangulation you got might be a corner case, but it is perfectly valid and doesn't contain t-junctions.

Quote:
 Original post by samster581I should have only 8 triangles, but I get two more (degenerate ones).

8 triangles would be incorrect. The 10 you are getting are one valid permutation out of many others for a tesselation of that polygon.

Quote:
 Original post by samster581And I just noticed that my Combine callback function is called exactly once in the very beginning:CombineCB: -128.000000, -23.000000, 0.000000

As I mentioned above, the combine function is called for new vertices and for merged vertices. The tesselator is merging your first and last vertices.

Quote:
 Original post by samster581And yes, I have a cleanup function that removes degenerate triangles, so I end up with T-junctions.

So as I suspected, you are creating the t-junctions, and not the tesselator. Keep in mind that the two degenerated triangles are only degenerated in your original vertex configuration. As soon as you apply any transformation to your vertices (rotations, etc), these two triangles may suddenly get a non-zero area and will become visible (due to numerical inaccuracies in the transformation). They are needed for correct rendering, you cannot simply remove them.

Basically, your 'cleanup' function destroys valid geometry.
0

##### Share on other sites
I removed the duplicate vertex point, but I still get the same list with degenerate triangles.
The only difference was the Combine callback function is not called anymore.

Well, GLU tesselator may create degenerate triangles, but that is still bad for my purposes if I can't remove them.
0

##### Share on other sites
Quote:
 Original post by samster581Well, GLU tesselator may create degenerate triangles, but that is still bad for my purposes if I can't remove them.

Why ? They don't do any harm.

They're only semi-degenerated anyway. They're just zero area, but they have three individual indices. As such, they're actual valid triangles. A real degenerated triangle has two or three identical vertices, and becomes a line or a point (eg. something like 9,0,0 or 9,9,9). These triangles can be safely removed (usually).
0

## Create an account

Register a new account

Followers 0

• ## Game Jobs

• ### Similar Content

• By Sagaceil
It's always better to fight with a bro.
• By recp
Hi,
I'm working on new asset importer (https://github.com/recp/assetkit) based on COLLADA specs, the question is not about COLLADA directly
also I'm working on a new renderer to render (https://github.com/recp/libgk) imported document.
In the future I'll spend more time on this renderer of course, currently rendering imported (implemented parts) is enough for me
assetkit imports COLLADA document (it will support glTF too),
importing scene, geometries, effects/materials, 2d textures and rendering them seems working
GLSL profile provides shaders for effects so I don't need to wory about them just compile, link, group them before render

The problem occours in COMMON profile because I need to write shaders,
Actually I wrote them for basic matrials and another version for 2d texture
I would like to create multiple program but I am not sure how to split this this shader into smaller ones,

Basic material version (only colors):
Texture version:
https://gist.github.com/recp/b0368c74c35d9d6912f524624bfbf5a3
I used subroutines to bind materials, actually I liked it,
In scene graph every node can have different program, and it switches between them if parentNode->program != node->program
(I'll do scene graph optimizations e.g.  view frustum culling, grouping shaders... later)

I'm going to implement transparency but I'm considering to create separate shaders,
because default shader is going to be branching hell
I can't generate shader for every node because I don't know how many node can be exist, there is no limit.
I don't know how to write a good uber-shader for different cases:

Here material struct:
struct Material { ColorOrTexture emission; ColorOrTexture ambient; ColorOrTexture specular; ColorOrTexture reflective; ColorOrTexture transparent; ColorOrTexture diffuse; float shininess; float reflectivEyety; float transparency; float indexOfRefraction; }; ColorOrTexture could be color or 2d texture, if there would be single colorOrTex then I could split into two programs,
Also I'm going to implement transparency, I am not sure how many program that I needed

I'm considering to maintain a few default shaders for COMMON profile,
1-no-texture, 2-one of colorOrTexture contains texture, 3-........

What do you think the shaders I wrote, I would like to write them without branching if posible,
I hope I don't need to write 50+ or 100+ shaders, and 100+ default programs

PS: These default shaders should render any document, they are not specific, they are general purpose...