Jump to content
• ### What is your GameDev Story?

• Advertisement

#### Archived

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

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

##### Share on other sites

• Advertisement
• Advertisement
• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• ### Popular Now

• 13
• 9
• 15
• 14
• 46
• Advertisement
• ### Forum Statistics

• Total Topics
634067
• Total Posts
3015324
×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net 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!