Jump to content
  • Advertisement
Sign in to follow this  
Stefire

Need help in Binary Space Partition Tree

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

Hi guys, I have been working on Binary Space Partition(BSP) and got a few problem. I am trying to delete a node from the BSP tree but I can't seem to get it right. When I try to google for a solution, I came across this website http://web.cs.wpi.edu/~matt/courses/cs563/talks/bsp/bsp.html . In that website, it talk about a function called FilterIntoTree where it merge a small subtree into a big one. Is there anyone here who know how to write the FilterIntoTree function or any idea on how to do it? Any code in any form or idea is appreciated. Thanks

Share this post


Link to post
Share on other sites
Advertisement
From what I can tell, FilterIntoTree, just detaches the sub-tree (rooted by the node you are deleting) from the main tree and then, one at a time, re-inserts all children into the main-tree. Start the insertion from the parent of the node you are deleting (in the main tree).

Share this post


Link to post
Share on other sites
Thanks for the reply...

The nodes in the BSP tree contain polygon information. So does it mean that when I'm am reinserting the sub-tree node into the main tree, I got to split the node depending on the main tree node. Cause the left child is (polygon infront of the node) and the right child is (polygon behind of the node).

Share this post


Link to post
Share on other sites
That's right, treat the separated sub-tree as a new list of polygons to be inserted into the tree. Except for the root of the sub-tree, which would be the node you are trying to remove. Its not the most efficient method, BSP trees are typically just used for static scenes. Although real-time kd-tree generation is probably the way things are going.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!