Jump to content
  • Advertisement

Archived

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

Jedaye

Question: triangulating a co-planer quad

This topic is 6299 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
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


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!