Polygon Tessellation/Triangulation Implementations

I appreciate that it may be a pretty obscure question, but I'll try bumping it just once.

Thanks.

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

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!

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.

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.

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]

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]

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 ?

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

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.

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

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.

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

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.

Ok, here's my test code (using samster581's data with the duplicate vertex removed):


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

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.

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.

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.

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.