Jump to content
  • Advertisement
Sign in to follow this  
TropicalPenguin

OpenGL Polygon Tessellation/Triangulation Implementations

This topic is 2857 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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


Link to post
Share on other sites
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
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
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
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
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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!