Binary Space Partitioning: An Attempt at a Simplified Explanation

This explanation, though simple, assumes that you have some familiarity with binary trees. If not, see information on what a binary tree is . The author of this page, Sherman Chin, wrote an illustrated introduction to binary trees that would be useful if you have not had much exposure to them. So, what is a binary space partitioning tree? Looking at each of the words can help us figure out the meaning. The word binary means "having two parts". You may have heard the term "binary star". A binary star is actually two stars that move around the same center. The word space as used here simply means the area that we are working with. From a game programmers perspective we may be talking about a certain game level layout, such as the floor plan for an adventure game where the user walks through many different rooms, encountering all types of monsters or some such thing. The space we would be considering would be all of the rooms and hallways, with all of the walls that make up these rooms and hallways. Here's a small portion of what a space might be (part of a game level):

Figure 1 This figure is based on a screenshot of Dog 3D, which is an applet that can be found at www.theparticle.com.

The word partition means to divide things up. For example, at a birthday party, a cake gets partitioned into several pieces so that each person who wants some hopefully gets a chunk.

The word tree as used here has a very specific meaning here (and I don't mean Maple tree or Pine). As mentioned above, this explanation assumes that you know what a tree data structure is. If not, please see the link mentioned above or do a search on Google for: binary search trees.

Basically, a binary space partition tree divides up space and then sort the parts of that space into some useful list, from which you can get information about how the parts relate to each other. The relations that are often important are the distance of the parts from some point or which parts are in front of, in back of, etc. , each other.

In a tiny bit more detail binary space partitioning means that we are dividing a space up into two parts. We then take each of the smaller parts and divide them up into two parts each. We continue to divide up the smaller parts, organizing them in a specific way (discussed in detail on the How to Create a BSP Tree page) until the parts are sufficiently small enough for our use. As an analogy, imagine planning to travel all over the world to visit four different friends. Two of them live in France (though not in the same city) and one of them lives in Australia and one lives down the street from you. Unless you love traveling and have a lot of money for plane fare, then you might want to create some sort of order for who you visit when. If you didn't, you might end up traveling to France to see the first friend, then back home to see the friend who lives down the street from you, then back to France to see the other French friend, then over to Australia to visit the friend there. One way to create the order of visits might be (and this isn't by any means the best way to do it, it is just a weak attempt at giving an analogy for this algorithm) to take a map of the world (the space) and to cut up the map into two parts. Put the part that is further from your house to the right of the part that is closer. Then, take each part of the map (there are now 2 parts) and cut those up into two parts each (and now you have 4 total parts). Place them in order of closeness to your house. Keep cutting each part of the map up into sections until each of your friends houses are in a separate piece of the map and keep putting each piece that you cut into the proper order of distance from your house. At the end you have a near to far listing of all of the areas between you and your friends residences. In your particular usage of this listing you can ignore all of the parts that don't have your friends houses in them, because you only need the information about which friend to visit first. Though this is a very, very loose and not particularly accurate analogy, it hopefully gives you the overall sense of what a binary space paritioning algorithm does, which is to divide up space and then sort the parts of that space into some useful list, from which you can get information about how the parts relate to each other. If you really want to know more about what a binary tree is then check out the rest of this site, specifically the links to Why use a bsp tree?, How to create a bsp tree, and Rendering with a bsp tree.