Two-Dimensional BSP Tree

To start, you'll go through an example of building and traversing a 2D BSP tree; afterward, you'll create an implementation. Take a look at the example 2D floor plan in Screenshot. You'll build a BSP tree based on this floor plan.

Screenshot The 2D floor plan shows a simple room with four walls.

Java graphics 10fig04.gif

In the one-dimensional example, each house was a partition, so partitions were points. In 2D, partitions are lines, and in 3D—surprise!—the partitions are planes. Lines easily partition a 2D area into two halves, but to actually build a BSP tree, you need to know what's to the "left" of the line and what's to the "right." Actually, the terms left and right are a bit inaccurate in this case. These terms work fine for a one-dimensional world, but in 2D, lines can be oriented in any way. A vertical line divides the world into "left" and "right," but a horizontal line divides the world into "north" and "south." Instead, we use the terms front and back. Line segments have a front and back just like polygons do, with the normal pointing in the direction of the front side, as shown in Screenshot. The front side is the visible side. This means you can use walls as the partitions.

Screenshot Line segments representing walls have a front and a back.

Java graphics 10fig05.gif

Because the partitions have a front and a back, you'll always be able to tell where the camera is in relation to each line: The camera is either in front of or in back of every partition. With this knowledge, let's walk through an example of building a BSP tree. If you're still a bit fuzzy on how line partitions divide the space, this example will help.

BSP Tree-Building Example

As an example, you'll build the floor plan from Screenshot by adding one wall at a time. The order in which you add walls will be arbitrary. In Screenshot, the first partition, wall A, is added to the tree. Notice that the partition formed by wall A extends beyond wall A, shown as a dotted line.

Screenshot Building a BSP tree, part 1. The first wall is added.

Java graphics 10fig06.gif

Here, the leaves of the BSP tree are the empty spaces. These empty spaces are the same shape as the floor and ceiling polygons. You want your floors and ceilings to have different heights (so you can create things such as platforms and stairs), so keep floor and ceiling height information in these leaves. In Screenshot, start with leaf 1, which represents the entire empty area. The first partition, wall A, splits this leaf into two, creating leaves 1 and 2. The empty spaces will always be convex because splitting a convex shape along a line always creates two convex shapes. So, the floor and ceiling polygons will be convex as well. Next, in Screenshot, walls B and C are added to the tree. Wall B is in front of A, so it is added to the front node of A. This splits leaf 1 into two leaves (1 and 3). Wall C is in front of A and in back of B, so it is added to the back node of B and splits leaf 3 into two leaves (3 and 4).

Screenshot Building a BSP tree, part 2. Walls B and C are added.

Java graphics 10fig07.gif

Notice that when you add wall B, leaf 3 is bounded by both wall B and the partition formed by wall A. The BSP building continues in Screenshot. There's just one more wall to add: wall D. But wall D actually spans the partition formed by wall B. Walls can't exist in two different locations in the tree, so wall D is split into two walls: D1 and D2.

Screenshot Building a BSP tree, part 3. Line D is split along the partition formed by line B.

Java graphics 10fig08.gif

That's it—you now have a built tree. Going through the process of building the tree, you probably noticed that the tree would be different if the walls were added in a different order. For example, if the walls were added in the order D, B, C, A, you would get the tree in Screenshot. This tree didn't require any walls to be split, so there are fewer nodes. Also, the tree has a shorter depth. However, the tree isn't well balanced—all the walls are in the front of the first node.

Screenshot This alternate BSP tree is shorter and has fewer nodes.

Java graphics 10fig09.gif

When you have enough polygons, shorter, balanced trees will make for faster searches. So, the order in which you add walls to the tree is important. An algorithm to decide the order in which you choose partitions should keep two things in mind:

  1. Minimize splits. Fewer splits mean fewer polygons and less tree traversal.

  2. Keep the tree as balanced as possible. Shorter, balanced trees means less tree traversal for unbalanced trees.

Sometimes these goals are mutually exclusive: Keeping the tree balanced can create more splits, and minimizing splits can create an unbalanced tree. Finding the right algorithm can be complicating. We present a couple of ideas here. First, you could just minimize the number of splits, ignoring the balance of the tree. Here, every time you choose a partition, you would choose the one resulting in the minimum number of splits. For example, you wouldn't choose wall B before wall D because wall B splits wall D. Second, you could just try to keep the tree as balanced as possible, ignoring the number of splits. Here you would always choose a partition that keeps the same number of walls (plus or minus one) on either side of the partition. For example, you could choose wall B as the first partition because two partitions would be on either side of it (even though it splits wall D). Or, you could combine these two ideas. For a set of partitions that keep the tree relatively well balanced (with a certain degree), choose the partition with the minimum number of splits. In this chapter, we don't get into the algorithms for picking partitions, so we leave that as an exercise for the reader. Instead, for a list of walls, just pick the first wall as the partition. This isn't the most ideal solution for large maps with lots of polygons, but it works fine for these examples.

BSP Tree-Traversing Example

Traversing the BSP tree is similar to how you traversed the one-dimensional BSP tree. Two rules apply:

  • Draw polygons in front of the camera in order (front node, current node, back node).
  • Draw polygons in back of the camera in reverse order (back node, current node, front node).

Take a look at the example in Screenshot. Imagine the camera is at the location marked with a star. This traversal algorithm traverses the nodes in this order: 4, D2, 6, C, 3, B, 1, D1, 5, A, 2. The polygons are traversed front to back, which is just what you want.

Screenshot Traversing the tree from the star's location.

Java graphics 10fig10.gif

Also with this algorithm, the first leaf traversed is the leaf that the camera is in. Because horizontal polygons can have different heights, if you know the leaf the player is in, you can determine at what height the player should be located. For example, if the player is 100 units tall and the player is in a leaf with a floor at y=200, the player's camera will be y=300. Now with the idea of building and traversing the polygons in a BSP tree, we move on a step deeper and write the code for a 2D BSP tree renderer.