Binary Space Partitioning:
How do you create a bsp tree?

   
The goal of this page is to go through all the steps of creating a binary space partitioning tree that will sort the line segments (and thus the walls) of our little world shown in Figure 1.


Figure 1
A portion of a "no frills" game world




Figure 2
(Figure 1 viewed from above)

General algorithm for creating a bsp tree:
Step 1: Make a list of all the walls.
Step 2: Choose one of the walls, "the splitter wall" to split up the space into two parts, P1 and P2.
Step 3: Put all of the walls that are completely in front of the splitter wall into one list, called "front".
Step 4: Put all of the walls that are completely in back of the splitter wall into another list called "back".
Step 5: If the splitter wall intersects any of the walls, split that wall into two parts, putting the part of the wall in front of the splitter wall into the front list and the other part in the back list.
Note: for simplification, this algorithm doesn't address walls that lie on the same line as the splitter wall.
Step 6: The splitter wall is placed in the bsp tree. The first wall simply becomes the root of the tree. Thereafter, the wall is placed in the bsp tree to the right of its parent wall if in the scene the wall is in front of the parent wall. The wall is placed in the bsp tree to the left of the parent wall if in the scene the wall is in back of the parent wall. (See figures 8 and 9 for examples.)
Step 7: Recursively split up the P1 space until you are left with one line segment only. Then recursively split up the P2 space until there is only one line segment remaining.

We will now follow these steps in order to create a bsp tree of the world in figure 1.


Notes:
1) The explanation below assumes that you already know about binary trees. If you don't, check out: http://sherman3d.com/Sherman3D/download.php?view.7(Link updated 03-23-2009)
2) For simplicity sake, this explanation is done in 2D space (just using the xy plane). This 2D algorithm is very similar to what is done in 3D space.
3) No special method of choosing a "good" splitter node is used, though this topic really should be given consideration if you are going to implement a bsp tree algorithm.
4) In this 2D explanation, each wall is considered to be a separate polygon. There are initially eight polygons in our mini-world in Figure 1 below, which in Figure 4 are labelled A through H. In the top view (such as in figure 4), each wall can be represented as a line segment, with a starting point (x1,y1) and an end point (x2, y2). In this discussion, we use "line segment" and "line" interchangeably.
5) For an applet which demonstrates a game world where you can move around inside the world see: http://www.theparticle.com/dog3d.html. This applet is highly recommended because it shows the "bare bones" of how a bsp tree could be used for rendering a game world. There isn't even collision detection in this particular java demonstration, which means that the user can walk through walls. Though a bsp can be used for collision detection, too, the author of that applet wanted to show how just the rendering element of using bsp trees. The bsp code is available for viewing, is very thoroughly documented and is easy to follow if you know Java. If you are interested in implementing a binary space partitioning tree, definitely check out the site above.


Here is the algorithm worked out in more detail: Figure 1 shows an example of a portion of a game world where the player moves through rooms and halls. We can label each of the walls in this scene A through H, as is shown in both figures 3 and 4. Note that in the view in Figure 3 walls D and G are not visible to the player.

each room labelled A through H

Figure 3
(Figure 1 with letters added to each visible wall)

view of figure 3 from above
Figure 4
(Figure 3 as viewed from above with all walls labelled)

Step 1: Following the algorithm at the top of the page, we start with a list of all of the polygons in one of the levels of the game world. Here (in Figure 3 and 4), we have just a portion of a world, so our list of lines is quite small- list of all lines: { A,B,C,D,E,F,G,H }. In a real game level, this list would be huge, perhaps 10,000 or more polygons.

Step 2: In order to sort the line segments, we choose one segment with which to split up the world. There are ways to choose which line is best used to split up the world, but for simplicity sake, these ways are not used here. Here, line segment C is the chosen splitting line, as is shown in red in figure 6:

Figure 6
The red line is the first splitting line.
The arrow points to the front of line C.

Steps 3 and 4: After splitting the world into 2 parts using line segment C as the "splitter", we put all the other lines into lists as follows:
Lines that are in front of C: { G, H }
Lines that are in back of C: { A, B, D, E }
Lines that C splits: { F }
Step 5: Because line F is split by C, we break F up into the part of F that is in front of C and the part of F that is in back of C, labelled in figure 6 as F1 and F2.
 
Now we have finished the first split. Instead of the original list of all the lines, we now have 2 lists:
Lines in front of C: { G, H, F1 }
Lines in back of C: { A, B, D, E, F2 }
 
   
We now have the first node (the root node) of our binary space partitioning tree, namely:
Step 6: We next repeat this splitting process until we have assigned each line segment to a place in the bsp tree. More specifically, we will use the next line in the "front" list, which is line F1, to split the world again:

Figure 7
F1 used

 
 
 
 
Now we have the following lists:
Lines in front of G: { F1 }
Lines in back of G: { H }
 
Note that G doesn't split any lines. Also, lines H and F1 do not yield any further divisions of our tree, so they become leaf nodes as is shown below in figure 8.
 
   

The bsp tree now looks as follows: Figure 8

 
   
Next we look at the nodes in the list of lines that are behind line C, splitting up the space behind that line and creating the following bsp tree:

Figure 9
The bsp tree representing the figure 1 scene.

 
 
 
Step 7: This bsp tree shows all the relations between all the walls in figure 1. If a node, let's call it N1, is lower and to the right of a node, which we'll call N2, then that means that the wall represented by N1 is in front of the wall represented by node N2. If node N3 is lower and to the left of Node N1, then the wall representing N3 is in back of the wall represented by N1. For example: walls G, H and F1 are in front of wall C, while wall H is in back of wall G.
 
 
 
   
Thus we have created a bsp tree from our scene in Figure 1. A summary of what we just did is:

We took a scene that consists of walls that will not change during game play. We made a list of lines of those walls. Then we sorted the walls. First we chose one of the line to divide up the area that the walls cover. Then we sorted all of the remaining lines into two lists, one of which consisted of all the walls (or parts of walls) in front of the dividing wall and the other walls (or parts of walls) that were behind the dividing wall. We then performed the same procedure on the space in front of the dividing wall and then performed the procedure on the space behind the wall. This repeated breaking down of a problem into sub-problems and then repeating the same procedure on these smaller problems is called "recursion". When we finished recursively dividing up the space, we had formed a tree representing the relationships of all of the walls based on the initial dividing wall.

This BSP tree would only need to constructed one time before anyone played the game. It could then be used over and over to draw the above scene or for collision detection or for any other purpose that a bsp tree is used for.

This example is very general. If you are looking for more specifics of how to create a bsp tree, there is an excellent tutorial on this matter that includes extremely well documented Java code and several interesting (and highly recommended) applets demonstrating the code: http://www.theparticle.com.

Here's the pseudocode for the above algorithm that creates a BSP tree. It is a slightly modified from the version found at: http://occs.cs.oberlin.edu/faculty/jdonalds/357/lecture25.html

Algorithm BSPTree constructBSPTree(PolygonSet S)
Input: a set of polygons, S
Output: a binary search partitioning tree of S
{
  PolygonSet FrontSet, BackSet;
  if set S is empty, return an empty tree;
  Choose a polygon P from set S;
  Let FrontSet and BackSet be empty polygon sets;
  for each polygon Q in S - {P} {
      if Q is in front of the plane containing P
          insert Q in FrontSet;
      else if Q is in back of the plane containing P
          insert Q in BackSet;
      else
          split Q into two polygons Qfront (in front of P's plane) and
Qback (in back of P's plane);
          insert Qfront in FrontSet;
          insert Qback in BackSet;
      }
  return makeTree(P,constructBSPTree(FrontSet),constructBSPTree(BackSet));
}

Next: Rendering