I have been running a few ideas through my head lately (ok, stop laughing) and I was thinking about deleting a wall from a BSP, lets say for purposes of a level editor. My list is comprised of a single splitter wall, front, and back nodes. The remaining polygons are either sent down the front or back list and setup that way. In my editor, I would most likely be using a BSP for whatever data there is to render it properly as well, this saves a lot of time as I can use the engine for the editor (duh). If a splitter was deleted from the BSP than all the data for that side of the node would be screwed up. It would only affect that side of its parent node. The parents node where that splitter wasn''t on wouldn''t be affected but the side that it was removed from would be. I was wondering what people have done to compensate this? I was thinking about just finding the parent node and building a list of all the polygons that are under that side of the node and save that list, than I would remove that side entirly and than reconstruct it. I think this would work fine, not the greatest but it would work. There is a problem however and thats if they delete the root node. This would result in both sides of the tree from being distrupted. Would it just mean that I would have to rebuild the entire list? Once the level has been constructed, I would build the BSP again to allow it to be optimized and constructed properly but for real time editing, this is what I was thinking. Any suggestions or comments? Shawn

You already know the relationship of all the nodes. Rebuilding it requires reestablishing all those relationships. Rotating the child tree and promoting it could use the relationships that are already established. What is in front of the node deleted is in front of the parent. What is behind it is behind what is in front of it. The easiest, though not most efficient is, to put what is behind the node deleted behind the backmost leaf of the front child. That lets you skip the rotation, but can end up with a highly lopsided tree. In the worst case you simply have a linked list of planes. Off the top of my head I don''t think a BSP tree is balanced so you may end up better or worse than you started based upon how the tree was built. If it is balanced then you already have the routines for rotating it.

I am not totaly sure of what you are trying to say.

You said that I already know the relationship between all the children nodes of the node I am deleting from and the parent. This is true. What I was saying is that if I delete a node from the BSP and it was the front node of the parent. This would mean that the back node of the parent would still be fine.

The front side however would need reconstruction. I was thinking about just reconstructing the front node since its the only one affected. This would result in a somewhat lopsided tree probably so to counter act that, I would rebuild the entire tree at the end of the creation process. This way the user could delete from the tree without too much reconstruction and the tree would also be balanced and optimized or whatever at the end, when it is rebuild.

Does this seem logical or a waste of time? Any suggestions would be appreciated.

Thanks
Shawn

If you delete a node then that whole section would have to be recompiled. Like if you take out the front node to a parent then ever node connected to the front node that was removed would have to be sent to the buildBSP funtion again. Im pretty sure you would just leave the rest of the tree (like the back node and its children) alone. Then again you would have to just try it out and see if it works ok.

-Snyper

Got any ideas on how to delete the entire polygon? Because if you split polygons than they become different nodes.

Maybe I should attach a tag number to each polygon and search my entire tree for all pieces of that #? I wouldn''t have to search the entire tree but just pieces of it anyways. Think that would be good?

Hopefully I can put together some sort of tutorial or whatever on all the info I grab from here

I think thats what i would do. Assign each polygon a number and if it gets split, rename the split polygon to the number then like a, b, etc.. after it. Like if the polygon was assigned 12. Then if it got split into two parts, it would be renamed to 12a, and 12b. Now that i think of it, i think i saw a BSP tree tutorial that had a member of the polygon class that had to do with the polygons id. Im not sure where i saw this tutorial.

-Snyper

Edited by - Snyper on November 12, 2000 4:12:32 PM