Jump to content
  • Advertisement
Sign in to follow this  
Thomas Mathers

Questions Concerning Polygon Partitioning

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

Hello All, I am incorporating BSP Trees into my engine right now and I am having trouble figuring out a way of splitting polygons based on the intersection of it with a plane. I have looked through several algorithms for splitting polygons. It seems, that the general idea is to classify each vertex in a polygon against the plane which you are comparing it to. Then you sort each vertex into either a front or back list depending on where it is in relation to the plane. However most of these algorithms do not take into account texture coordinates and normals. I was just wondering if there is a way of preserving texture coordinates and normals while partioning a polygon. Any help would be greatly appreciated.

Share this post


Link to post
Share on other sites
Advertisement
The algorithm you describe is the correct one, sorting vertices into two lists. Are you sorting polygons with n sides, or triangles? Triangles make life a lot easier, as they're guaranteed to reside in one plane and only have three vertices.

If you're using the algorithm described above, a new vertex (call it v3) is created on the plane when two vertices (call them v1 and v2) are either side of the plane. You can use the value t (the distance between one of the vertices and the plane, used to calculate the new position of v3) to figure out both the texcoords and normal for v3.

To calculate the texcoords: v1 and v2 will have texcoords. Take them, and linearly interpolate between them by the value t, in the same way that you'll have interpolated the positions of v1 and v2 to get the position of v3.

To calculate the normal: Computing the normal of the new vertex is a bit more difficult than texcoords, if you're using per-vertex normals. You can't linearly interpolate them, as they're not linear like v3's position and texcoords. I believe you have to use spherical linear interpolatation with respect to t. It's outlined here: http://www.cg.tuwien.ac.at/studentwork/CESCG/CESCG-2002/GSchroecker/node13.html. Notice in the small diagram at the bottom how linear interpolation gives flat values across a surface, but spherical linear interpolation gives rounded values, based on the two normals.

Hope some of this helps...

[Edited by - iNsAn1tY on July 23, 2005 7:12:01 AM]

Share this post


Link to post
Share on other sites
I'd be interested in this too, my ABT partitioning currently only works for triangle polys with my own splitting algo but the rest of my engine is happy to work with n-sized polys so I'd really like to find out about any n-sided methods, in particular how to get the new face indices from the split vertices, the texture coords, normals and bone weights.

Thanx

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!