# OpenGL How to split polygon into triangles?

This topic is 4958 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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!

##### Share on other sites
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).

##### Share on other sites
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...

##### Share on other sites
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.

##### Share on other sites
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]

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
Thanks guys. Most appreciated :)

##### Share on other sites
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.

##### Share on other sites
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.

1. 1
2. 2
3. 3
Rutin
13
4. 4
5. 5

• 26
• 10
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633696
• Total Posts
3013397
×