BSP Tree Intro

In the last chapter, "3D Objects," you created a z-buffer to correctly draw polygons in a scene. This created a perfectly drawn scene, with polygons close to the camera drawn in front of polygons farther away. But the drawback was checking and setting the z-buffer for every pixel: It was too much overhead for every pixel on the screen, and overdraw was often involved. The more polygons you have, the more z-buffer checking and potential overdraw you have. Obviously, this doesn't scale well. What you really want is an alternative to the z-buffer with the following goals:

• To potentially manage a large number of polygons
• To quickly decide which polygons are visible from any location in the scene
• To draw only the visible polygons (and to not draw parts of polygons that aren't visible)
• To draw every pixel only once (no overdraw)

At first, those seem like some difficult goals to accomplish. Of course, the technique you use to solve these goals really depends on the type of game you have. For example, a driving game in which you spend a lot of time looking at wide open spaces would probably use a different technique than an indoor game in which you spend a lot of time looking at walls, floors, and ceilings. You can organize polygons in many different ways to make it easy to decide which polygons are visible. Besides BSP trees, some other types of polygon-organization techniques are octrees and scene graphs. BSP trees enable you to draw all polygons from front-to-back order from any location in the scene. By extension, using BSP trees solves all of the previous goals. However, the BSP tree isn't perfect. Here are a couple drawbacks:

• The world must be static (no moving walls here). However, 3D game objects can move around, so you can use 3D game objects for things such as monsters and doors.
• It's computationally expensive to build the tree. However, the ideal solution is to build the tree beforehand, loading the built tree at startup time.

Games such as Doom were the first to implement BSP trees. Doom used a 2D BSP tree with variable-height floors and ceilings, and the rendering engine had a restriction that a player could not look up and down in the game. In the code you make in this chapter, you also use a 2D BSP tree with variable-height floors and ceilings, but you use the 3D rendering engine from the previous chapters so the player can look up and down. Even though we demonstrate a 2D BSP tree in this chapter, a 3D BSP tree, used in many modern games, is not that much more difficult to master. A 2D BSP tree just makes the examples and equations a bit easier to follow, and other topics such as collision detection and path finding are easier to describe. The drawback to using a 2D BSP tree is that you can make a world with only vertical walls and horizontal floors and ceilings. However, you still can make some cool worlds with this limitation.