Concave polygon splitting

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?

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

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]

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?

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]

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.

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?

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

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

I could also test if the first two nodes result in the same value. If so, I just multiply x by some value. y by some other value, and leave z the same. Then it would work, right spacedude?

My Site

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

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

Aren''t there any good books or online papers about this kind of thing? It''s all very confusing to even conceptualise fully let alone implement
Appreciate your input of course

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.