Binary Space Partitioning Tree
A BSP Tree is a standard binary tree used for partitioning a spacial model. BSP trees (or variations on them) are commonly used in 3D games, such as Quake. A node of a BSP tree contains a description of a polygon. Every node of a BSP tree also has a "Is In Front of Me" link, and a "Is In Back of Me" link.
Creating a BSP tree is where most of the work comes in. Using a Quake level as an example, select a polygon from the list of available polygons. This is the polygon we will use at this node. Every polygon has a front side and a back side, with the front side being the visible face. All of the remaining, unplaced polygons are then examined. If the polygon being examined is in front of the current polygon, we group it with the leafs to be placed in front of this one. If the polygon examined is behind the current polygon, we group it with the other group instead. Finally, generate a tree for both lists using the same steps just listed. Select one of the polygons in the behind list. This is the current node (which incidentally is now set as the "Is In Back of Me" link for the previous node.)
If a polygon being compared is neither in back nor in front of our polygon, we have to split it up into two separate polygons. The portion in front of our current polygon, and the portion behind. Then each portion is added to the respective group.
Why bother with such a non-intuitive structure? Well, when we want to draw a scene, we start at the root of our tree. Then, we can quickly do a painter's algorithm rendering of our scene by checking whether our camera position is in front of the polygon at this node, or behind it. If we're in front, recurse through the tree in the opposite direction, and go down the front if we're behind the polygon. After we're finished in that direction (which ever one it was,) draw the current polygon, and then recurse through the tree in the remaining direction. This quickly draws the polygons in the order they are needed to do a back to front drawing of our scene. One beauty of BSP trees is in considering scenarios where the painter's algorithm typically fails. Consider the following view:
| | | |
| +--| |--+
| | | |
+--| |--+ |
| | | |
This is impossible for the painter's algorithm
, because both
polygons overlap each other. However, BSP trees have no problem with the scene as one of the offending polygons was split into two by necessity in the generation of the tree.
There are many other benefits that BSP trees, as an organizational structure, offer. Back face culling is free. If we're behind the polygon in the rendering walk, we simply don't draw the polygon. One more point to consider is that if the plane of a polygon we are considering never intersects with our viewing frustrum, we can immediately discard all elements of the BSP tree on the side opposite of the viewer by simply not walking through the tree in that direction.