Jump to content
  • Advertisement
Sign in to follow this  

BSP tree and portals: Doing it right

This topic is 4563 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! I've studied every article I found on the Web regarding BSP-trees and portals for many months now and I think I have a good understanding of the concepts how portals and BSP trees work. Now I've developed some programs to use this mechanisms but I still don't know whether this all is correct or if I missed out something. One program is responsible for loading a map, creating the BSP tree and automatically placing the portals. Another program loads these data and renders the map using the portals. I can walk through the map like in a first-person-shooter and look around using the mouse. Now I'd like to know whether my implementation is "standard" - which means that this is the "usual" way to go when implementing a portal engine. I ran into some problems while developing it, so it was not as easy as it was mentioned in many articles. For the preprocessing program: * The map is recursivley split by infinite planes until a maximum level of recursion depth is reached. * Only every leaf of the BSP-Tree contains geometry data. The parents do not have faces attached/stored in them * Starting with a bounding box at the BSP-Tree root, I split the box against all splitting planes - so I create for every leaf the convex polyhedra that surrounds it. * Every polyhedra is checked against every other whether two sides are connected to each other - this means the intersection of the polygons of the corresponding sides are not empty. * Every intersection Polygon is stored as a Portal that ledas from a node to another. Finally, I end up with a complete BSP tree. Each leaf in the tree has a list of portals which exactly connect the leaf to its neighbours. Example: NodeA connects through exactly 1 portal ("2") to NodeB and portal "1" to NodeC. The Portals are numbers and are exactly as large as the wall connecting the nodes:
  |       |        |       |
  | NodeA 2        4 NodeD |
  |       |        +---5---+
  +---1---+  NodeB |       |
  |       |        |       |
  | NodeC 3        6 NodeE |
  |       |        |       |
Now I have a BSP-Tree and portals, but: The portals are quite large - which results in little occlusion of basically invisible geometry. I have to find a way to get these portals smaller: **Question** Would it be wise to let the BSP-Tree focus on splitting planes that coincide with large walls in the map?? This way I could cut out the coinciding walls from the portals thus creating far smaller portals...?! I know the "automatic portal generation" algorithms described on gamedev and somewhere else, too. But as far as I can see, they only work for non-compact worlds - this means rooms separated with floors between them... or does someone have implemented these algorithms yet and can provide me with some experience? For the rendering program: * Using the BSP-Tree I determine the leaf the viewer is currently located in. * If this node has not been checked before: * Mark this Node as "checked". * Loop through all portals of the current node * If the portal is not visible -> ignore it * If the portal is fully/partially visible -> clip the frustum * Descent into the neighbour node the portal leads into and use the clipped frustum for the "deeper" checks. (recursion call here) * Remove this node from the checked list * Return **Question** Is this the usual way to go? Or should I first collect all visible neighbour leafs and then handle them in a loop? My current approach is: first depth, then next... would it be better to recurse another way through the portals? **Question** Looking at the whole process I've implemented: Do you think this is "a good way" or "the usual way" to implement this? Or do you have some hints for me how and where I could do something better? Thanks for reading and please ask if you need more information! Greetings Stefan

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!