Leaf based Solid node BSP Trees
If you want to make first person shooter games like Quake, Half life, or Unreal Tournament, a data structure called a Binary Space Partition Tree will make collision detection and rendering very fast. If you want to make large outdoor environments, dynamic destructible terrain, or game levels that require no preprocessing, you are barking up the wrong tree.
Binary Space Partition Trees, or BSPTrees, have been around for a long time, but they are still widely used. Games used to use BSPTrees to ensure drawing polygons from back to front. This is not very important nowadays because z-buffers make it unimportant which order we draw our scene in. New BSPTrees take advantage of z-buffers and are used to speed up rendering and collision detection drastically! With a new BSPTree you can have enormous levels and still get great frame rates. These BSPTrees can still help to draw the scene from back to front, in case your hardware doesnít support z-buffers. This new BSPTree I am talking about is the Leaf Based Solid node Binary Space Partition Tree. Let me explain what that name means. Leaf Based just means that the data in the tree is only stored in the leaves of the tree. Leaves refer to nodes which don't have any children, also called terminal nodes. In a Leaf based tree, the nodes that have children donít have any polygons stored in them; they are just used to define the spatial relationships of the leaves. The solid part of the name refers to the fact that we store information in the nodes about whether it is in solid space or not. This helps with collision detection. This will become more clear when I step through building the tree. The Binary Space Partition part means that we split the data into two parts in each node; in front and behind the splitting plane. I will refer to these as just BSPTrees from now on, but note that there are many types of BSPTrees.
The basic idea behind a BSPTree is to address the problems that plague all game developers; collision detection and real time rendering. Average games have hundreds of thousands of polygons in the levels. If you need to determine when a character hits a wall, then you need to check to see if the characterís mesh intersects any polygons. If you where to do this without any spatial sorting data structure, you would have to make hundreds of thousands of tests. And you would need to do that every frame in the game. This would slow the game play down to a very choppy pace. A BSPTree sorts those hundreds of thousands of polygons into a tree. If you take a plane right through the polygons, you can divide the data into two sections; in front and behind the plane. When you want to know if a person has intersected anything in the level, you can now test to see which side the character is on. Then test the polygons on the appropriate side. This cuts the number of collision tests in half, but we donít stop there. We can subdivide both those halves, and keep going until we have a deep enough tree. That works great for collision detection, but what about rendering?
BSPTrees are not fast to render by themselves. They use PVS to speed up rendering. PVS stands for Possible Visibility Sets. This is just precalculated visibility information stored for the nodes of the tree. What it amounts to is keeping track of all the nodes that can be seen from every node. That way, you just figure out what node you are in, then draw every node that can be seen from there. This is fast because there is almost no run time to check for visibility. One problem is that the PVS doesnít take the direction you are looking into account when it calculates visibility. To get a slightly more accurate set of polygons to render, we can frustum cull the set of polygons that are visible from the node we are in. This provides a slight boost of performance. There is a drawback to PVS usage. They require tons of preprocessing, and require that the level is not dynamic. There are trees out there that could be used to implement destructible terrain, like the CSGTree. This stands for constructive surface geometry tree. These trees speed up collision detection, and allow for Boolean operations on the level, but donít offer any visibility determination. Thatís why we are focusing on the Leaf Based Solid Node Binary Space Partition Trees.
To understand how these trees work, letís run through how to pre-process them. The basic idea here is to select one of the polygons to represent an infinite splitting plane. Then sort all the polygons in the list into two sections, front or back. We may have to clip polygons to fit into these categories. Polygons that share the same plane as the splitting plane will be sorted into the front list if its normal points the same way as the splitting plane. Otherwise it gets sorted into the back list. Note that because this is a leaf based BSPTree, we will need to put the polygon we used as a splitter in one of these lists as well. Since its normal points the same way as the planeís normal, we will put it in the front list. Whenever we use a polygon as a splitter, we will mark it as used. We can stop this recursive pattern when all polygons have been used as splitters.
|Figure 1: This shows the possible orientations a polygon can have with respect
to a plane.
Take the room shown in figure 2. Itís an odd shaped room with a pillar in the middle of one of its sections. The white area represents empty space that you can walk in, and the gray represents solid space. To compile this into a BSPTree, first we select a splitter. Once a polygon is used as a splitter, it should not be used as one again. We select polygon A as our first splitter. Notice that both A and E lie on the splitting plane. Polygon A is entered into the front list because its normal points the same way as the splitting plane. Polygon E is put into the back list because itís normal points in the opposite direction of the splitting planeís normal. B, C, D and E are all placed in the back list for the first node. A, F, G, H, I, J, K and L are all placed into the front list for the first node. Now we just repeat this process for each list. Letís cover the back list first because itís the easiest. We choose B as the splitter, so E, C, B and D are put in the front list. Now we set the back to solid. This tells us if we ever end up at that point, we are in solid space. Now we sort the front list of the second node. We select E as our splitter, and once again we set the back list to solid. Note that we do this, because only B, D, E and C are in the list we are sorting. We canít see K, L and the rest of the polygons that are actually behind E. This is what gives us the binary portion of the tree. We are only dealing with polygons behind A, and in front of B at this point. Polygons D, E, B AND C are put into the front list of E. We continue to sort the front list of E, and choose D to be our splitter. Behind D is solid, and C, D, E and B is placed in Dís front list. We sort the front list of D and choose C as our splitter. Behind C is solid, and E, B, D, and C are placed into Cís Front. We now have used all the polygons in Aís Back list as splitter. This means that we stop our recursion, and save the polygons in the leaf node. Note that all of the polygons in a Leafy BSPTree are stored in the leaf nodes. The other nodes just give us solidity information. So far our Tree Structure looks like figure 3. We now need to go back and sort the front list of A.
|Figure 2: This figure shows a top view of a very simple level.
|Figure 3: This figure shows an incomplete tree representation
of the level in figure 2.
|Figure 4: This figure shows the complete tree representation
of the level in figure 5.
|Figure 5: This figure shows the locations of the splits that
where done to the level in figure 2.
|Figure 6: This figure shows the anti-penumbra from room A
for a set of four rooms, and a hall.
We select K to be the fist splitter. Note that we need to split polygons H and F in order to continue. We will call these H1, H2, F1, and F2 respectively. The right side of H gets put in the front list for K, and the back left side of H gets put into the back list for K. The Right side of F gets put into the front list of K, and the left side of F gets put into the back list of K. A and K get put into the front list of K, while G, I, J, and L get put into the back list for K. If you continue this pattern and select your splitters as I did, you will come up with something like figure 4.
Ok now you understand the process of pre processing the tree. After you have done this, you should save the level as a BSP file so you can load it at runtime. You may be asking, what good has this data structure done for me? Rendering this thing will not save us any time yet, but this structure already works well for collision detection. Say you have a point you wish to know if you can move to. Before you allow the move, you compare the point to the tree. If the point is in front of the plane formed by A, then you compare it to K. If itís in front of K, then you compare it to F2Ö Notice that eventually you will hit either solid, or a node with polygons in it. If you hit solid, then you can not move there. Otherwise itís open space. You may notice that worst case in the above tree gives us five compares out of the total of twelve polygons. Thatís pretty big savings because the compares are pretty cheep. This savings will grow tremendously with bigger levels.
Now letís try to get this thing to render quickly. We will use PVS. What we will do is calculate what can be seen from every node. To do this we need to use a concept called an Anti-penumbra. This is just a fancy name for a simple concept. If you were to light a bright light in the room you are in, the light would be cast all over the room. The door ways and windows of the room would let only a limited amount and shape exit the room. The Anti-penumbra in this case is the light. What would be visible from the room is all that the light touches.
There is one difference with the above example and the way we will do it. We donít know where the light in the room is, so we must assume it is everywhere. This has the effect of lighting up the entire room, and all rooms joined to it. To figure out what is lit up, take a look at Figure 6. If we want to calculate the visibility set for room A, then we draw lines from the corners of the doorways in room A to the opposite corners of doorways in rooms adjacent to room A. We must assume that all of room A is Visible, and all of room C is Visible. This is because we donít know where the player will be standing. We do know that the room D will not be seen no matter where the user is. This is where the savings comes from. We donít have to render room D, or any rooms connected to it. If there were a thousand rooms connected to room D, then we could just skip them all! And all this with virtually no runtime tests! Note that in typical first person games, we donít have more than a few rooms connected to one room. This means that the example of the thousand rooms connected to room D is not too far fetched.
When you store the visibility data for each node, I suggest using a bit array, and Zero Run Length Compression. If you were to store a pointer in each node to every node that is visible, it would suck up way too much memory. The bit array works like this: if you have five rooms in figure 6, each node will have a bit array with five bits in it. Each bit represents a Boolean value that tells you if a given room is visible or not. With the above example the bit array would look like this: 1 1 1 0 1. Where the first bit refers to room A, the second refers to room B, the third to room C the fourth to room D, and the last refers to the hallway connecting C and D. Using a tree that stores itís nodes in an array makes this method easier. It also helps when we want to save and load the levels. This method has a flaw. If you have one bit for each node, stored in each node, you will end up with a lot of used memory. Say you have 10,000 nodes. Each node must have 10,000 bits stored in each node. Thatís 100,000,000 bits, about 12mb! Thatís way too much space taken up on just visibility. We still have to account for vertex data and textures!
To fix this short coming, we will use Zero Run Length Compression. This just means we store how many zeros we find in a row, and represent them with a number, instead of many zeros. This will work well for us, because game levels usually have most of the level not visible at any given time. This will make our bit arrays take up much less space. To use it, we make our bit arrays like normal, then we will loop through each bit until we find a zero. We will count how many zeros are in a row, and then replace all the zeros with a single zero followed by a byte representing the length of zeros. When we are rendering, if we find a zero, we know to look at the next eight bits to tell us how long the zeros run. Then we can skip the rendering of all rooms whose indices lie within the run length.
Thatís it for the BSPTree overview. I have not covered how to actually code any of this stuff, but that will be another tutorial. Just know that the doors between rooms will be represented by portals. I will also post my full source code in the code section of my website.
[ Home - Products - Textures - Tutorials - About Us - Contact Us ]
XenosGames© Chris Rogers 2003. XenosEngine© Chris Rogers 2003.