• Create Account

How to split polygon into triangles?

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.

9 replies to this topic

#1CyberSlag5k  Members

514
Like
0Likes
Like

Posted 16 May 2005 - 12:15 PM

I'm using anim8or as my 3D modeller and am writing the code to import the models into my OpenGL project. I've run into a problem, as I had intended to use vertex arrays to store the mesh data. However anim8or store objects as the highest n-gons available, and the number of points may vary thruought the mesh. The data stored looks like this:
5 4 0 -1 ( (2 0) (7 1) (4 2) (1 3) (0 4) )
5 4 0 -1 ( (3 5) (9 6) (6 7) (2 0) (0 4) )
5 4 0 -1 ( (1 3) (5 8) (8 9) (3 5) (0 4) )
5 4 0 -1 ( (4 2) (10 10) (11 11) (5 8) (1 3) )
5 4 0 -1 ( (6 7) (12 12) (13 13) (7 1) (2 0) )
5 4 0 -1 ( (8 9) (14 14) (15 15) (9 6) (3 5) )
5 4 0 -1 ( (7 1) (13 13) (16 16) (10 10) (4 2) )
5 4 0 -1 ( (11 11) (17 17) (14 14) (8 9) (5 8) )
5 4 0 -1 ( (9 6) (15 15) (18 18) (12 12) (6 7) )
5 4 0 -1 ( (16 16) (19 19) (17 17) (11 11) (10 10) )
5 4 0 -1 ( (18 18) (19 19) (16 16) (13 13) (12 12) )
5 4 0 -1 ( (17 17) (19 19) (18 18) (15 15) (14 14) )

That first number (a 5 in all of the cases in this example) is the number of sides the polygon will have. The next 3 numbers don't matter for this discussion. The following list is made up of n groupings, where the first one is the index into an array of vertices. So the first polygon in the mesh is a pentagon made up of the vertices 2, 7, 4, 1, and 0. Simple enough, right? Well, certainly not for using vertex arrays. I originally thought I could just split the mesh up into all triangles, but that appears to be complicated for anything more complex than a square. Does anyone know a simple algorithm to do this? Thanks in advance!
Without order nothing can exist - without chaos nothing can evolve.

#2Yann L  Members

1802
Like
0Likes
Like

Posted 16 May 2005 - 01:01 PM

Quote:
 Original post by CyberSlag5kWell, certainly not for using vertex arrays. I originally thought I could just split the mesh up into all triangles, but that appears to be complicated for anything more complex than a square. Does anyone know a simple algorithm to do this?

That's called a tesselator, or a triangulator. Check out this site.

Alternatively, you can also use the OpenGL glu library tesselation functions (GLUtesselator, and gluTess*() calls). From my experience, the glu tesselators are usually extremely robust, stable, and easy to use. Even if you don't use OpenGL, you can compile the tesselator separately, and use it with DirectX or whatever else (the source is available through Mesa).

#3iNsAn1tY  Members

476
Like
0Likes
Like

Posted 16 May 2005 - 01:15 PM

Well, if you need to split up the polygons into triangles (and perhaps I haven't understood your problem correctly, because this solution is very simple), you could create a linear index array for triangles. The index array would begin (2, 7, 4, 2, 4, 1, 2, 1, 0). You take the first index (2), then the second (7) and the third (4). Then you take the first vertex again, then the fourth (1), then the fifth (0) and so on. You cut the pentagon up into three triangles. The new index array is constructed from the indices you already have. You don't need to change your vertex/normal/texcoord arrays at all, just your index array...
My opinion is a recombination and regurgitation of the opinions of those around me. I bring nothing new to the table, and as such, can be safely ignored.[ Useful things - Firefox | GLee | Boost | DevIL ]

#4Yann L  Members

1802
Like
0Likes
Like

Posted 16 May 2005 - 01:18 PM

Quote:
 Original post by iNsAn1tYWell, if you need to split up the polygons into triangles (and perhaps I haven't understood your problem correctly, because this solution is very simple), you could create a linear index array for triangles. The index array would begin (2, 7, 4, 2, 1, 0). You take the first index (2), then the second (7) and the third (4). Then you take the first vertex again, then the fourth (1), then the fifth (0). You cut the pentagon up into two triangles. The new index array is constructed from the indices you already have. You don't need to change your vertex/normal/texcoord arrays at all, just your index array...

That doesn't work with concave polygons.

#5iNsAn1tY  Members

476
Like
0Likes
Like

Posted 16 May 2005 - 01:20 PM

Quote:
Original post by Yann L
Quote:
 Original post by iNsAn1tYWell, if you need to split up the polygons into triangles (and perhaps I haven't understood your problem correctly, because this solution is very simple), you could create a linear index array for triangles. The index array would begin (2, 7, 4, 2, 1, 0). You take the first index (2), then the second (7) and the third (4). Then you take the first vertex again, then the fourth (1), then the fifth (0). You cut the pentagon up into two triangles. The new index array is constructed from the indices you already have. You don't need to change your vertex/normal/texcoord arrays at all, just your index array...

That doesn't work with concave polygons.

Yes. The algorithm's based on the assumption that they're all convex. I should have mentioned that. Like I said, it's very simple [grin]

#6Yann L  Members

1802
Like
0Likes
Like

Posted 16 May 2005 - 01:28 PM

Quote:
 Original post by iNsAn1tYYes. The algorithm's based on the assumption that they're all convex. I should have mentioned that. Like I said, it's very simple [grin]

Well, if CyberSlag's 3D modeller polygon output is guaranteed to be convex, then the whole thing becomes just as easy as the example you outlined (which is basically a tri fan, you could also use tri-stripping based approaches). I don't know if that guarantee of convexity applies in this case, though.

#7SimmerD  Members

1210
Like
1Likes
Like

Posted 16 May 2005 - 01:36 PM

I used an algorithm based on this :

http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/twoears.html

IFIRC it handles covex & concave. You walk along the polygon in order, make a triangle out of three vertices, and make sure itdoesn't cross an existing edge. Eventually you have a list of tris from the polygon.

#8CyberSlag5k  Members

514
Like
0Likes
Like

Posted 16 May 2005 - 04:32 PM

Thanks guys. Most appreciated :)
Without order nothing can exist - without chaos nothing can evolve.

#9kburkhart84  Members

2882
Like
0Likes
Like

Posted 16 May 2005 - 06:10 PM

Can't the modeller you use output triangles instead. Is there not a setting? I ask because I have never used it, not to be rude as it may sound. I would think there would be such a setting.

#10CyberSlag5k  Members

514
Like
0Likes
Like

Posted 17 May 2005 - 02:46 AM

Quote:
 Original post by kburkhart84Can't the modeller you use output triangles instead. Is there not a setting? I ask because I have never used it, not to be rude as it may sound. I would think there would be such a setting.

Nope. I even asked the program's creator. And you didn't sound rude at all.
Without order nothing can exist - without chaos nothing can evolve.

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.