# OpenGL Polygon Tessellation/Triangulation Implementations

## Recommended Posts

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.

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

Thanks.

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

##### 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!

##### 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.

##### 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.

##### 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]

##### 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]

##### 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 ?

##### 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.)

##### 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.

##### 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

##### 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.

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

##### 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.

##### 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?

##### 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.

##### 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.

##### 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.

##### 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.

##### 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.

##### 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.

##### 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.

##### 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.

##### 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).

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628293
• Total Posts
2981868
• ### Similar Content

• By mellinoe
Hi all,
First time poster here, although I've been reading posts here for quite a while. This place has been invaluable for learning graphics programming -- thanks for a great resource!
Right now, I'm working on a graphics abstraction layer for .NET which supports D3D11, Vulkan, and OpenGL at the moment. I have implemented most of my planned features already, and things are working well. Some remaining features that I am planning are Compute Shaders, and some flavor of read-write shader resources. At the moment, my shaders can just get simple read-only access to a uniform (or constant) buffer, a texture, or a sampler. Unfortunately, I'm having a tough time grasping the distinctions between all of the different kinds of read-write resources that are available. In D3D alone, there seem to be 5 or 6 different kinds of resources with similar but different characteristics. On top of that, I get the impression that some of them are more or less "obsoleted" by the newer kinds, and don't have much of a place in modern code. There seem to be a few pivots:
The data source/destination (buffer or texture) Read-write or read-only Structured or unstructured (?) Ordered vs unordered (?) These are just my observations based on a lot of MSDN and OpenGL doc reading. For my library, I'm not interested in exposing every possibility to the user -- just trying to find a good "middle-ground" that can be represented cleanly across API's which is good enough for common scenarios.
Can anyone give a sort of "overview" of the different options, and perhaps compare/contrast the concepts between Direct3D, OpenGL, and Vulkan? I'd also be very interested in hearing how other folks have abstracted these concepts in their libraries.
• By aejt
I recently started getting into graphics programming (2nd try, first try was many years ago) and I'm working on a 3d rendering engine which I hope to be able to make a 3D game with sooner or later. I have plenty of C++ experience, but not a lot when it comes to graphics, and while it's definitely going much better this time, I'm having trouble figuring out how assets are usually handled by engines.
I'm not having trouble with handling the GPU resources, but more so with how the resources should be defined and used in the system (materials, models, etc).
This is my plan now, I've implemented most of it except for the XML parts and factories and those are the ones I'm not sure of at all:
I have these classes:
For GPU resources:
Geometry: holds and manages everything needed to render a geometry: VAO, VBO, EBO. Texture: holds and manages a texture which is loaded into the GPU. Shader: holds and manages a shader which is loaded into the GPU. For assets relying on GPU resources:
Material: holds a shader resource, multiple texture resources, as well as uniform settings. Mesh: holds a geometry and a material. Model: holds multiple meshes, possibly in a tree structure to more easily support skinning later on? For handling GPU resources:
ResourceCache<T>: T can be any resource loaded into the GPU. It owns these resources and only hands out handles to them on request (currently string identifiers are used when requesting handles, but all resources are stored in a vector and each handle only contains resource's index in that vector) Resource<T>: The handles given out from ResourceCache. The handles are reference counted and to get the underlying resource you simply deference like with pointers (*handle).
And my plan is to define everything into these XML documents to abstract away files:
Resources.xml for ref-counted GPU resources (geometry, shaders, textures) Resources are assigned names/ids and resource files, and possibly some attributes (what vertex attributes does this geometry have? what vertex attributes does this shader expect? what uniforms does this shader use? and so on) Are reference counted using ResourceCache<T> Assets.xml for assets using the GPU resources (materials, meshes, models) Assets are not reference counted, but they hold handles to ref-counted resources. References the resources defined in Resources.xml by names/ids. The XMLs are loaded into some structure in memory which is then used for loading the resources/assets using factory classes:
Factory classes for resources:
For example, a texture factory could contain the texture definitions from the XML containing data about textures in the game, as well as a cache containing all loaded textures. This means it has mappings from each name/id to a file and when asked to load a texture with a name/id, it can look up its path and use a "BinaryLoader" to either load the file and create the resource directly, or asynchronously load the file's data into a queue which then can be read from later to create the resources synchronously in the GL context. These factories only return handles.
Factory classes for assets:
Much like for resources, these classes contain the definitions for the assets they can load. For example, with the definition the MaterialFactory will know which shader, textures and possibly uniform a certain material has, and with the help of TextureFactory and ShaderFactory, it can retrieve handles to the resources it needs (Shader + Textures), setup itself from XML data (uniform values), and return a created instance of requested material. These factories return actual instances, not handles (but the instances contain handles).

Is this a good or commonly used approach? Is this going to bite me in the ass later on? Are there other more preferable approaches? Is this outside of the scope of a 3d renderer and should be on the engine side? I'd love to receive and kind of advice or suggestions!
Thanks!
• By nedondev
I 'm learning how to create game by using opengl with c/c++ coding, so here is my fist game. In video description also have game contain in Dropbox. May be I will make it better in future.
Thanks.

• So I've recently started learning some GLSL and now I'm toying with a POM shader. I'm trying to optimize it and notice that it starts having issues at high texture sizes, especially with self-shadowing.
Now I know POM is expensive either way, but would pulling the heightmap out of the normalmap alpha channel and in it's own 8bit texture make doing all those dozens of texture fetches more cheap? Or is everything in the cache aligned to 32bit anyway? I haven't implemented texture compression yet, I think that would help? But regardless, should there be a performance boost from decoupling the heightmap? I could also keep it in a lower resolution than the normalmap if that would improve performance.
Any help is much appreciated, please keep in mind I'm somewhat of a newbie. Thanks!

• Hi,
I'm trying to learn OpenGL through a website and have proceeded until this page of it. The output is a simple triangle. The problem is the complexity.
I have read that page several times and tried to analyse the code but I haven't understood the code properly and completely yet. This is the code: