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) )
How to split polygon into triangles?
Author
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:
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!
Quote:Original post by CyberSlag5k
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?
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).
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...
Quote:Original post by iNsAn1tY
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, 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.
Quote:Original post by Yann LQuote:Original post by iNsAn1tY
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, 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]
Quote:Original post by iNsAn1tY
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]
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.
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.
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.
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.
Author
Quote:Original post by kburkhart84
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.
Nope. I even asked the program's creator. And you didn't sound rude at all.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
