Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Polygon Tessellation/Triangulation Implementations


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
30 replies to this topic

#1 TropicalPenguin   Members   -  Reputation: 100

Like
0Likes
Like

Posted 14 October 2010 - 08:10 AM

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.

Sponsor:

#2 TropicalPenguin   Members   -  Reputation: 100

Like
0Likes
Like

Posted 17 October 2010 - 09:39 AM

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

Thanks.

#3 Rubicon   Members   -  Reputation: 296

Like
0Likes
Like

Posted 17 October 2010 - 12:02 PM

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

------------------------------Great Little War Game

#4 mokaschitta   Members   -  Reputation: 124

Like
0Likes
Like

Posted 17 October 2010 - 10:39 PM

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!

#5 samster581   Members   -  Reputation: 120

Like
0Likes
Like

Posted 18 October 2010 - 09:16 PM

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.

#6 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 19 October 2010 - 02:35 AM

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.

#7 Yann L   Moderators   -  Reputation: 1798

Like
0Likes
Like

Posted 19 October 2010 - 06:42 AM

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]

#8 samster581   Members   -  Reputation: 120

Like
1Likes
Like

Posted 19 October 2010 - 10:10 AM

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]

#9 Yann L   Moderators   -  Reputation: 1798

Like
0Likes
Like

Posted 19 October 2010 - 09:49 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 ?

#10 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 19 October 2010 - 11:28 PM

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

#11 Dave Eberly   Members   -  Reputation: 1161

Like
0Likes
Like

Posted 20 October 2010 - 03:33 AM

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.



#12 samster581   Members   -  Reputation: 120

Like
0Likes
Like

Posted 20 October 2010 - 07:19 AM

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

#13 Yann L   Moderators   -  Reputation: 1798

Like
0Likes
Like

Posted 20 October 2010 - 07:48 AM

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.

#14 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 20 October 2010 - 08:22 AM

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

#15 Yann L   Moderators   -  Reputation: 1798

Like
0Likes
Like

Posted 20 October 2010 - 08:51 AM

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.


#16 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 20 October 2010 - 09:02 AM

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?

#17 TropicalPenguin   Members   -  Reputation: 100

Like
0Likes
Like

Posted 20 October 2010 - 09:20 AM

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.

#18 Yann L   Moderators   -  Reputation: 1798

Like
1Likes
Like

Posted 20 October 2010 - 09:50 AM

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.

#19 rouncED   Members   -  Reputation: 103

Like
1Likes
Like

Posted 20 October 2010 - 12:12 PM

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.

#20 Dave Eberly   Members   -  Reputation: 1161

Like
0Likes
Like

Posted 20 October 2010 - 12:38 PM

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.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS