One-Dimensional BSP Tree

Eventually, this chapter will focus on 2D BSP trees, but understanding how a 2D or 3D BSP tree works can be difficult at first. So, I'd like to make things a little easier by first explaining a one-dimensional BSP tree. This example might seem trivial, but it will give you the idea of how BSP trees work. In short, a BSP tree's node divides a world into halves-or, in other words, it is a binary space partition. Using a BSP tree allows you to sort polygons front to back from the camera's location. Now imagine the player is standing in a simple world with a row of houses, as shown in Screenshot. Note that the houses are sorted by their numbers. Also, the houses have the same numbers as in the example in Screenshot.

Screenshot The player is standing at position 7 in a row of houses.

Now assume that each house is a node partition. In this one-dimensional example, each house partitions the world into two spaces: the left space (everything to the left of the house) and the right space (everything to the right of the house). Building the tree follows the same process you used to build a sorted binary tree in the previous section. The resulting binary tree in this example could look just like the one in Screenshot. Now let's say you want to draw these houses in a 3D world. You want to draw the houses front to back from the camera's location, to eliminate overdraw and avoid the speed shortcomings of a z-buffer. So, in this example, you want to draw the houses closer to the player before drawing the farther ones. Looking at Screenshot, the order to draw the houses in front to back order is broken down into two simple rules:

• Draw houses to the left of the camera in reverse order: (6, 5, 3, 1).
• Draw houses to the right of the camera in order: (8, 9).

From a 3D perspective, the houses on the left side will never overlap the houses on the right side. Therefore, it doesn't matter whether the order in which you draw the houses is first the left side and then the right (6, 5, 3, 1, 8, 9) or whether the two sides are mixed in some variation (6, 8, 5, 9, 3, 1). It matters only if each side is drawn in order. So, this technique works no mater which way the player is facing. You'll implement these two rules with a variation of the printInOrder() method you created in the previous section, creating a printFrontToBack() method.

public void printFrontToBack(Node node, int camera) {
 if (node == null) return;
 if (camera < node.value) {
 // print in order
 printFrontToBack(node.left, camera);
 System.out.println(node.value);
 printFrontToBack(node.right, camera);
 }
 else if (camera > node.value) {
 // print in reverse order
 printFrontToBack(node.right, camera);
 System.out.println(node.value);
 printFrontToBack(node.left, camera);
 }
 else {
 // order doesn't matter
 printFrontToBack(node.left, camera);
 printFrontToBack(node.right, camera);
 }
}

This method is similar to the printInOrder() method, except that it prints in reverse order if the node's value is less than the camera's value. Let's walk through this method by looking at Screenshot.

Screenshot Traversing the tree from position 7.

With the binary tree from Screenshot, calling printFrontToBack() with camera location 7 follows these steps:

1. At the root node, 7 is greater than 5, so traverse the right node.
2. At node 8, 7 is less than 8, so traverse the left node.
3. Node 6 is a leaf, so print 6 and return to the parent.
4. Print 8 and traverse its right node.
5. Node 9 is a leaf, so print 9 and return to the parent.
6. You're finished traversing node 8, so return to the parent.
7. Print 5 and traverse its left node.
8. At node 1, 7 is greater than 1, so traverse the right node.
9. Node 3 is a leaf, so print 3 and return to the parent.
10. Node 1 does not have a left child, so print 1 and return.
11. You're finished traversing the root.

So, calling printFrontToBack() with camera location 7 prints the order (6, 8, 9, 5, 3, 1). Everything on the left is printed in front-to-back order (6, 5, 3, 1), and everything on the right it printed in front-to-back order (8, 9), which is just what we wanted. Problem solved! Next, let's extend this idea to two dimensions.