Advertisement Jump to content


This topic is now archived and is closed to further replies.


Question: triangulating a co-planer quad

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I''m currently writing a bsp compiler. Hence I want to be able to split poly''s with a plane. I''ve done this, and it (usually) results in a triangle and a quad - I need to split the quad into two discrete triangles. All the vertices of the quad are co-planer but their order varies (i.e. not guaranteed to be cw or ccw). I''m sure there is a very simple solution but I just can''t see it. All I''ve seen when I''ve looked this up is very general algorithms for complex poly''s. If anyone could describe a simple algorithm for this (it needn''t be quick), or point me in the right direction, it would be much appreciated. Thanks

Share this post

Link to post
Share on other sites
You could:

* work out the quad centre (average the vertices) and normal (take the outer product of two edges/diagonals)

* Let the vector from the centre C to a vertex be the X axis. Then work out the outer product of the vector and this normal be the Y axis. These are guaranteed to be perpendicular.

* Work out the coordinates of each vertex using these axes, i.e. by dot products with the X and Y axis vectors. Then do arctan2 (x, y) for each of them to get the bearing of each around the normal.

* You should now have four angles, one for each vertex, between 0 and 360 degrees. Sort these into the order of their angles to get them in CW or CCW order (which one depends whether your normal is ''up'' or ''down'': you can fix this when calculating the normal)

Another way:

Pick two pairs of vertices, work out the equations of the lines joining the pairs then work out where these lines cross. If they cross and the crossing point is between the pairs then the pairs are opposite corners. E.g. if the lines AB and CD cross between A and B and between C and D then the quad must be ACBD. There are only three possible pairs (AB & CD, AC & BD, AD & BC), and you need only chack two if you kno that one will always succeed. But this does not tell you whether the points are CW or CCW.

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!