Sign in to follow this  
TropicalPenguin

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.

Thanks in advance.

Share this post


Link to post
Share on other sites
samster581    120
Quote:
Original post by mokaschitta
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!


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

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Original post by samster581
GLU 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 this post


Link to post
Share on other sites
Yann L    1802
Quote:
Original post by samster581
GLU 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 this post


Link to post
Share on other sites
samster581    120
Quote:
Original post by Yann L
Quote:
Original post by samster581
GLU 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 this post


Link to post
Share on other sites
Yann L    1802
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 this post


Link to post
Share on other sites
jyk    2094
Quote:
Original post by Yann L
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.
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 this post


Link to post
Share on other sites
Dave Eberly    1173
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 this post


Link to post
Share on other sites
samster581    120
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 this post


Link to post
Share on other sites
Yann L    1802
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 this post


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

Share this post


Link to post
Share on other sites
Yann L    1802
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 this post


Link to post
Share on other sites
jyk    2094
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 this post


Link to post
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 this post


Link to post
Share on other sites
Yann L    1802
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 this post


Link to post
Share on other sites
rouncED    103
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 this post


Link to post
Share on other sites
Dave Eberly    1173
Quote:
Original post by Yann L
Now consider the following three triangles:
9 0 4
9 4 5
9 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 this post


Link to post
Share on other sites
Yann L    1802
Quote:
Original post by Dave Eberly
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...

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 this post


Link to post
Share on other sites
samster581    120
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,0,4 -> bad blocking edge
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 this post


Link to post
Share on other sites
Yann L    1802
Quote:
Original post by samster581
bad 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 samster581
I 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 samster581
And 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 samster581
And 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 this post


Link to post
Share on other sites
samster581    120
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 this post


Link to post
Share on other sites
Yann L    1802
Quote:
Original post by samster581
Well, 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).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Partner Spotlight

  • Similar Content

    • By pseudomarvin
      I assumed that if a shader is computationally expensive then the execution is just slower. But running the following GLSL FS instead just crashes
      void main() { float x = 0; float y = 0; int sum = 0; for (float x = 0; x < 10; x += 0.00005) { for (float y = 0; y < 10; y += 0.00005) { sum++; } } fragColor = vec4(1, 1, 1 , 1.0); } with unhandled exception in nvoglv32.dll. Are there any hard limits on the number of steps/time that a shader can take before it is shut down? I was thinking about implementing some time intensive computation in shaders where it would take on the order of seconds to compute a frame, is that possible? Thanks.
    • By Arulbabu Donbosco
      There are studios selling applications which is just copying any 3Dgraphic content and regenerating into another new window. especially for CAVE Virtual reality experience. so that the user opens REvite or CAD or any other 3D applications and opens a model. then when the user selects the rendered window the VR application copies the 3D model information from the OpenGL window. 
      I got the clue that the VR application replaces the windows opengl32.dll file. how this is possible ... how can we copy the 3d content from the current OpenGL window.
      anyone, please help me .. how to go further... to create an application like VR CAVE. 
       
      Thanks
    • By cebugdev
      hi all,

      i am trying to build an OpenGL 2D GUI system, (yeah yeah, i know i should not be re inventing the wheel, but this is for educational and some other purpose only),
      i have built GUI system before using 2D systems such as that of HTML/JS canvas, but in 2D system, i can directly match a mouse coordinates to the actual graphic coordinates with additional computation for screen size/ratio/scale ofcourse.
      now i want to port it to OpenGL, i know that to render a 2D object in OpenGL we specify coordiantes in Clip space or use the orthographic projection, now heres what i need help about.
      1. what is the right way of rendering the GUI? is it thru drawing in clip space or switching to ortho projection?
      2. from screen coordinates (top left is 0,0 nd bottom right is width height), how can i map the mouse coordinates to OpenGL 2D so that mouse events such as button click works? In consideration ofcourse to the current screen/size dimension.
      3. when let say if the screen size/dimension is different, how to handle this? in my previous javascript 2D engine using canvas, i just have my working coordinates and then just perform the bitblk or copying my working canvas to screen canvas and scale the mouse coordinates from there, in OpenGL how to work on a multiple screen sizes (more like an OpenGL ES question).
      lastly, if you guys know any books, resources, links or tutorials that handle or discuss this, i found one with marekknows opengl game engine website but its not free,
      Just let me know. Did not have any luck finding resource in google for writing our own OpenGL GUI framework.
      IF there are no any available online, just let me know, what things do i need to look into for OpenGL and i will study them one by one to make it work.
      thank you, and looking forward to positive replies.
    • By fllwr0491
      I have a few beginner questions about tesselation that I really have no clue.
      The opengl wiki doesn't seem to talk anything about the details.
       
      What is the relationship between TCS layout out and TES layout in?
      How does the tesselator know how control points are organized?
          e.g. If TES input requests triangles, but TCS can output N vertices.
             What happens in this case?
      In this article,
      http://www.informit.com/articles/article.aspx?p=2120983
      the isoline example TCS out=4, but TES in=isoline.
      And gl_TessCoord is only a single one.
      So which ones are the control points?
      How are tesselator building primitives?
    • By Orella
      I've been developing a 2D Engine using SFML + ImGui.
      Here you can see an image
      The editor is rendered using ImGui and the scene window is a sf::RenderTexture where I draw the GameObjects and then is converted to ImGui::Image to render it in the editor.
      Now I need to create a 3D Engine during this year in my Bachelor Degree but using SDL2 + ImGui and I want to recreate what I did with the 2D Engine. 
      I've managed to render the editor like I did in the 2D Engine using this example that comes with ImGui. 
      3D Editor preview
      But I don't know how to create an equivalent of sf::RenderTexture in SDL2, so I can draw the 3D scene there and convert it to ImGui::Image to show it in the editor.
      If you can provide code will be better. And if you want me to provide any specific code tell me.
      Thanks!
  • Popular Now