Tessellation (off topic...sorry)

I need to break an arbitrary polygon into triangles. Unfortunately, I can’t use GLU to do it, as the program that it is done in isn’t even related to drawing…

The shape is defined by an ordered sequence of vertices, guaranteed to lie in a plane. That’s all the information I have to work with. I need to fill it with non-overlapping triangles.

Graphics Gems didn’t seem to have anything that would help me - can anyone recommend additional sources?

Thanks,
Chris

Mesa has all this stuff in the GLU code, I don’t think it would be to difficult to extract the code from the the Mesa source code and use that in your application.

Mikael

Are you indeed looking for triangulation algorithm?

Search google for links on “Delaunay triangulation” and “Voronoi diagram”. It is easiest to implement in 2D, so fits your problem perfectly. You can perform 3D triangulation as well, but it’s not trivial. One point to note is it works best if the vertices are unordered.

Hope that helps.

Can your polygon be degenerate? Does it need to be an optimal triangulation? If not, you can simply iterate around your list of vertices and cut out convex corners (sometimes called ears) until the list is down to two elements. The trimmed corners along with each adjacent vertex is added to a list of resultant triangles.

[This message has been edited by Decimal Dave (edited 08-07-2001).]

Originally posted by Decimal Dave:
Can your polygon be degenerate? Does it need to be an optimal triangulation?

No, and no.

If not, you can simply iterate around your list of vertices and cut out convex corners (sometimes called ears) until the list is down to two elements.

I’m not quite following this… what do you mean by “cut out”? Do you mean iterate through, find the places it turns concave, connect these places and treat them as seperate entities, and triangulate them individually? … or will this approach work (even if it’s not what you’re talking about?

mikael_aronsson: That was my first idea, but the source is virtually completely comment-free; I’d prefer not to use code that is not documented - other people are going to have to work on this thing, too.

Thanks for your help,
Chris

>>what do you mean by “cut out”? Do you mean iterate through, find the places it turns concave, connect these places and treat them as seperate entities, and triangulate them individually? … or will this approach work (even if it’s not what you’re talking about?<<

Assume that your polygon is stored as a list of ordered vertices. It might help to draw a polygon out on paper to see what is going on. If you look at an individual vertex, each one forms either a concave or convex corner with it’s neighbors. Every convex corner is an ear, formed by a triangle inside of the polygon. What you will do is treat your list of vertices as a loop (a circular list) and keep iterating around it cutting off ears until the whole polygon is gone (only two vertices are left). Each ear that is cut off will be a triangle in your triangulation. Note that cutting off an ear (which consists of three vertices) will only remove one vertex from your polygon. For example, a polygon with 6 vertices will triangulate into 4 ears using this method.

One other thing I forgot to mention, but is kind of important, is to avoid creating a degenerate polygon when cutting off an ‘ear’. As you can tell, when you remove a vertex from the list, a new edge is created between it’s neighbors. If this edge intersects with any other edge in the polygon, DON’T hack off that corner; just continue your iteration until you find a vertex that can be removed while preserivng the normality of your polygon (remember, there is always at least one removable ear).

[This message has been edited by Decimal Dave (edited 08-08-2001).]