PDA

View Full Version : Tessellation (off topic...sorry)

chennes
08-07-2001, 01:46 PM
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

mikael_aronsson
08-07-2001, 02:16 PM
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

Coconut
08-07-2001, 02:28 PM
Are you indeed looking for triangulation algorithm?

ffish
08-07-2001, 08:12 PM
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.

Decimal Dave
08-07-2001, 08:24 PM
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).]

chennes
08-08-2001, 04:04 AM
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. http://www.opengl.org/discussion_boards/ubb/smile.gif