 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| Concave polygon splitting |
|
 |
Real World Member since: 8/9/2001 From: Nottingham, United Kingdom |
|||
 Posted - 11/27/2003 4:15:48 AM |
||||
| 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! |
||||
|
||||
|
SpaceDude Member since: 10/15/2003 |
|||
|
Posted - 11/27/2003 1:16:07 PM |
||||
| 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? |
||||
|
||||
|
Real World Member since: 8/9/2001 From: Nottingham, United Kingdom |
|||
|
Posted - 11/28/2003 5:03:28 AM |
||||
| 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 |
||||
|
||||
|
T2k Member since: 3/21/2002 From: Hannover, Germany |
|||
|
Posted - 11/28/2003 7:05:46 AM |
||||
| 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] |
||||
|
||||
|
MENTAL Member since: 4/8/2000 From: Herne Bay, United Kingdom |
|||
 Posted - 11/28/2003 7:35:02 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? |
||||
|
||||
|
quasar3d Member since: 12/1/2001 From: Rotterdam, Netherlands |
|||
|
Posted - 11/28/2003 9:49:02 AM |
||||
| 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] |
||||
|
||||
|
SpaceDude Member since: 10/15/2003 |
|||
|
Posted - 11/28/2003 10:22:12 AM |
||||
quote: 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. |
||||
|
||||
|
SpaceDude Member since: 10/15/2003 |
|||
|
Posted - 11/28/2003 10:25:07 AM |
||||
quote: what if (z+y+z=constant) for 1 or more nodes? |
||||
|
||||
|
quasar3d Member since: 12/1/2001 From: Rotterdam, Netherlands |
|||
|
Posted - 11/28/2003 10:32:46 AM |
||||
quote: 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 |
||||
|
||||
|
quasar3d Member since: 12/1/2001 From: Rotterdam, Netherlands |
|||
|
Posted - 11/28/2003 10:55:06 AM |
||||
| 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 |
||||
|
||||
|
quasar3d Member since: 12/1/2001 From: Rotterdam, Netherlands |
|||
|
Posted - 11/28/2003 10:59:18 AM |
||||
| 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 |
||||
|
||||
|
SpaceDude Member since: 10/15/2003 |
|||
|
Posted - 11/28/2003 7:35:31 PM |
||||
| 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 |
||||
|
||||
|
quasar3d Member since: 12/1/2001 From: Rotterdam, Netherlands |
|||
|
Posted - 11/29/2003 6:01:14 AM |
||||
| 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 |
||||
|
||||
|
Real World Member since: 8/9/2001 From: Nottingham, United Kingdom |
|||
|
Posted - 12/1/2003 6:45:21 AM |
||||
| 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  |
||||
|
||||
|
DaWizard Member since: 11/28/2000 From: Ontario, Canada |
|||
|
Posted - 12/1/2003 3:19:14 PM |
||||
| 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. |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
