Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


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.

  • You cannot reply to this topic
9 replies to this topic

#1 CyberSlag5k   Members   -  Reputation: 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.

Sponsor:

#2 Yann L   Moderators   -  Reputation: 1798

Like
0Likes
Like

Posted 16 May 2005 - 01:01 PM

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).


#3 iNsAn1tY   Members   -  Reputation: 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 ]

#4 Yann L   Moderators   -  Reputation: 1798

Like
0Likes
Like

Posted 16 May 2005 - 01:18 PM

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.


#5 iNsAn1tY   Members   -  Reputation: 476

Like
0Likes
Like

Posted 16 May 2005 - 01:20 PM

Quote:
Original post by Yann L
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.

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]

#6 Yann L   Moderators   -  Reputation: 1798

Like
0Likes
Like

Posted 16 May 2005 - 01:28 PM

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.

#7 SimmerD   Crossbones+   -  Reputation: 1102

Like
0Likes
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.


#8 CyberSlag5k   Members   -  Reputation: 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.

#9 kburkhart84   Members   -  Reputation: 1703

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.

#10 CyberSlag5k   Members   -  Reputation: 514

Like
0Likes
Like

Posted 17 May 2005 - 02:46 AM

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.
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.



PARTNERS