#### Archived

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

# Concave polygon splitting

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

## 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 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 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 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 on other sites
when merging, couldn''t you just simply restore any triangles that wern''t split back to their original state, and any that were kept as triangles?

##### 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 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 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 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 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

1. 1
2. 2
3. 3
Rutin
15
4. 4
khawk
14
5. 5
frob
12

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633660
• Total Posts
3013223
×