Archived

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

Concave polygon splitting

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

I would like to add an algorithm to my code that could split a concave shape along a split plane. I have the algorithm working for convex but that assumes that there will only be two resulting polygons. Does anyone know of any resources online where I could learn this complex technique? Planetblaze.com - http://www.planetblaze.com - As METAL as it gets!

Share this post


Link to post
Share on other sites
I''ve done something similar where you can take a slice of any number of 3D polygons through any plane, and it will create 2D polygons out of it. I guess then what you want to do is mesh the interior of the 2D polygons to create the face between the split 3D polygons?

How are you doing it for convex shapes?

Share this post


Link to post
Share on other sites
I am determining which polygons in the mesh are in each side of the plane and putting them in a front and back array then determining which cross the plane, finding the point of intersection and creating two new polygons from the one original. Then using the contents of the front and back array to generate two new meshes.
The problem arrises with concave because there could be any number of new meshes either side of the plane and trying to merge them into one mesh causes the 3d engine to do very oddd things

Share this post


Link to post
Share on other sites
one way you could do it is by simplify'ing the problem to convex polygons, triangulate your concave polygon, split each triangle that has to be split and rejoin them to your final polygons, this will become a bit tricky with non-planar-polygons...


edit, convex, concave, argh damn hope its now correct :D

T2k

[edited by - T2k on November 28, 2003 7:07:36 AM]

Share this post


Link to post
Share on other sites
This is how I did it:

first convert the polygon into a graph of links and nodes. A node is just a vertex, with pointers to the links that link to it. A link is a connection between two nodes, and has pointers to it's start and end node.
now it's very easy to split that graph. just split all the links, by adding new nodes on the places that intersect with the plane (You should save these newly created nodes in a list, because we need them later on).
Now you can easily split the graph in a front graph and a back graph. Those graphs don't look like polygons though, since there are gaps on the split plane.
To fill in these gaps, we'll create some new links between the new nodes. To do this, you should have saved the newly created nodes in a list, and sort that list to (n1.x + n1.y + n1.z) < (n2.x + n2.y + n2.z). This always places them in the right order on the line, no mather what the orientations of the polygon and splitplane are. Now we have sorted these list, we can create a new link from newVert[0] to newVert[1], one from newVert[2] to newVert[3], one from newVert[4] to newVert[5] and so on. (add those new links to both graphs)
Now we have two perfect graphs, for the front polygons and the back polygons. Note that a graph can hold more than one polygon.
All you have to do now is reconstruct the polygons from the graph.

I hope this helps you

btw. I can post the code if you want.


My Site

[edited by - Quasar3D on November 28, 2003 9:51:04 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Real World
I am determining which polygons in the mesh are in each side of the plane and putting them in a front and back array then determining which cross the plane, finding the point of intersection and creating two new polygons from the one original. Then using the contents of the front and back array to generate two new meshes.
The problem arrises with concave because there could be any number of new meshes either side of the plane and trying to merge them into one mesh causes the 3d engine to do very oddd things


When a triangle intersects a plane, you can determine a line that cuts accross the triangle. So if you keep track of all the lines created by the triangles intersecting the plane. You will end up with 2D polygons (to build the 2D polygons all you need to do is start with one of the lines and follow it until it loops back to itself). And by counting the number of those polygons you can find out how many 3D polygons you need to create. The number of 3D polygons = number of 2D polygons + 1.

Share this post


Link to post
Share on other sites
quote:
Original post by quasar3d
To fill in these gaps, we''ll create some new links between the new nodes. To do this, you should have saved the newly created nodes in a list, and sort that list to (n1.x + n1.y + n1.z) < (n2.x + n2.y + n2.z). This always places them in the right order on the line, no mather what the orientations of the polygon and splitplane are.


what if (z+y+z=constant) for 1 or more nodes?

Share this post


Link to post
Share on other sites
quote:
Original post by SpaceDude
quote:
Original post by quasar3d
To fill in these gaps, we''ll create some new links between the new nodes. To do this, you should have saved the newly created nodes in a list, and sort that list to (n1.x + n1.y + n1.z) < (n2.x + n2.y + n2.z). This always places them in the right order on the line, no mather what the orientations of the polygon and splitplane are.


what if (z+y+z=constant) for 1 or more nodes?


That means that the nodes are on the same position, and so you can''t sort them anyway. I know for sure that those points lay on one line, and I want to sort them to their position on that line. Every position on that line has a unique result. There can be other coordinates that result in the same value, but then it doesn''t lay on that line.

My Site

Share this post


Link to post
Share on other sites
damn, no you are right, if the x increases with 5, and the y decreases with 5, it''s still 0. Oops! strange that I didn''t notice it, for I''ve build bsp trees with it, without any problems.

so to correct my previous explaination: The points on that line should be sorted to their position on the line.
The best way I can come up with now is with a dot product

My Site

Share this post


Link to post
Share on other sites
I''m a bit confused... i thought we were talking about splitting 3D polygons... and so if you take a slice across a 3D polygon, you are going to end up with a 2D polygon... not a list of nodes that lie on a straight line...

:x

Share this post


Link to post
Share on other sites
if you split a 3D polygon, you still have 3D polygons, or a list of nodes that lay on a plane, but if you split that graph, there are nodes added that lay on the polygon plane, but also on the split plane. Those points, that were added because of the splitting, do lay on a line, since the intersection of two planes is a line.

My Site

Share this post


Link to post
Share on other sites
Lookup Sutherland-Hodgman polygon clipping for general 3D case. Some work might be required to deal with arbitrary half planes and concave polygons.

Lookup intersection of polygon and plane. The following one has some code: http://www.andrew.cmu.edu/~rrost/bsp/bsp8.html.

Concave polygons may or may not have all vertices in a single plane (rounding errors and the like). You could generalize the clipping algorithm further but it should be easy enough if you split a concave polygon into triangles and then split each one according to the clipping algorithm. You will get a lot more polygons this way but atleast the result will be correct.

Share this post


Link to post
Share on other sites