Binary Space Partitioning: Why bother to use it at all?

If you have ever played a game, such as Quake or Doom, in which you move around various rooms from a first person perspective, meaning that it seems as though you personally are moving around the halls and rooms and are not just watching a character move around, then you may have been using binary space partitioning without even knowing it. Figure 1 (below) is an example of what part of such a game world might look like (minus all the frills such as textures on the walls and floors). As you move around such a game world during game play, the computer has to keep redrawing everything you see because your viewpoint changes as you move. Since the computer is redrawing the scene over and over again, everything must be drawn very quickly or else there would seem to be pauses in the motion and the game would seem very "jerky". A scene of a game world, such as the small segment of such a world shown in Figure 1, can be considered to be made up of polygons. There may be thousands of polygons in a scene. A BSP tree is simply a sorted list of all the polygons of such a scene. The sorting is done in a particular way so that we can use the information in the list very quickly.   Figure 1 A small segment of a "no frills" game world

In order for the computer to quickly redraw the scence during game play it has to have a way to quickly "look at" and decide which polygons should get drawn (there is no need to draw the ones that are not in the current view) and in what order they should be drawn. We know ahead of time what the layout of the walls of the game will be because the game designer will have mapped out the entire world. This layout will not change during the play of the game, which is important information to know because we can make a list of all the polygons in the game world before anyone plays the game. Because there may be thousands of polygons, our list might be very long, which would take a long time to search through. During game play, where we want the motion to appear very smooth, there probably isn't enough time to search through a very long list of unsorted polygons over and over again, which is what the computer must do to keep redrawing the scenes as the player moves around. What should we do? One solution is to create a binary space partition tree, which sorts and stores all the polygons of the game world in a way that a computer can search very quickly. this BSP tree can then be used to quickly render the scenes during game play. This use, rendering of static scenes is merely one use of BSP trees. They are also used in hidden surface removal, collision detection, creating ray tracing hierarchies, computing analytic visibility, performing boolean operations on polytopes, computing shadows and in robot motion planning, among other things.