# BSP tree and portals: Doing it right

This topic is 4744 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 14
• 14
• 45
• 22
• 27
• ### Forum Statistics

• Total Topics
634044
• Total Posts
3015211
×