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.
Polygon Tessellation/Triangulation Implementations
Author
I appreciate that it may be a pretty obscure question, but I'll try bumping it just once.
Thanks.
Thanks.
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 samster581Yup, I found that to be the case as well.
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.
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 LQuote: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.
srcAnd, 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 ?
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 LIt'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.)
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
