A BSP tree (for Binary Space Partition) is a data structure that is used extensively in 3D gaming applications such as Quake and Doom to handle occlusion when rendering polyhedral objects.
In such games, the user roams around in a simulated three-dimensional space. The space typically contains polyhedral walls and obstacles consisting of many small polygons. All these polygons are repainted on the screen many times a second. When a polygon is drawn on the screen, it overpaints whatever was there before, so it makes sense to paint the polygons in back-to-front order with respect to the position of the viewer so that occlusion will be handled correctly. That is, if object A is behind object B with respect to the viewer, then A should be painted first, so that any part of A that overlaps B will be hidden (occluded) when B is painted. Of course, the position of the viewer is constantly changing, so the back-to-front order must be constantly recalculated. BSP trees allow this to be done very quickly.
The beauty of BSP trees is that they are completely static. They are constructed once and for all when the game starts up; no restructuring is ever necessary. As the viewer moves about, the tree is walked in a different order depending on the viewer's position, but the calculation of the tree-walk order is very simple.
A polygon is a 2D object. Embedded in 3D space, the polygon lies in a plane, which is an infinite 2D object that cuts the space in half. We arbitrarily name one side of this plane the front side and the other the back side; there is no special significance to these names at this point, since we don't have a viewer yet. For now it is just a way of distinguishing the two sides. Thus every point in 3D space is either on the plane, in front of the plane, or in back of the plane.
We can determine whether a given point is in front or in back if we know a point c of the plane and a normal vector n (a vector pointing perpendicularly out from the plane) pointing in the direction of the front of the plane. Then a point p is in front of the plane if the inner (dot) product of p-c with n is positive; it lies in the plane if the dot product is 0; and it is behind the plane if the dot product is negative. Recall that the dot product of (a,b,c) and (x,y,z) is ax + by + cz.
The dot product of two unit (length 1) vectors is the cosine of the angle between them. Since we can scale a nonzero vector by its length to make it a unit vector, the condition above is same as saying: a point p is in front of the plane if the angle between p-c and n is acute (less than pi/2); it lies in the plane if the angle is right (exactly pi/2); and it is behind the plane if the angle is obtuse (between pi/2 and pi).
For example, the plane in x,y,z space determined by a triangle with vertices (0,0,0), (1,0,0), and (0,1,0) is the x,y plane. Let c be the point (0,0,0), which lies in this plane. We can take the unit vector (0,0,1) pointing in the z direction as the normal. The front of the plane is then upper half space {(x,y,z) | z > 0}. To show that the point (2,-3,4) is in front of the plane, we compute the dot product ((2,-3,4) - (0,0,0)) · (0,0,1) = 4, which is positive, so the point is in front. The point (0,1,0) is on the plane, so the dot product should be 0, and indeed ((0,1,0) - (0,0,0)) · (0,0,1) = 0.
We assume that for every pair of polygons A, B in our collection, A does not have points both strictly in front of and strictly behind the plane of B. (If this occurs, we split A into two polygons. You do not have to worry about this for the assignment, though--the data we will give you will already satisfy this property.) A may have points lying in the plane of B. Thus we can assume that if c and n are the reference point and normal of B, then either (p-c) · n >= 0 for every point p in A or (p-c) · n <= 0 for every point p of A. In the former case we say that A is in front of B and in the latter that A is behind B. "In front of" and "behind" have no significance in terms of the viewer here. Assuming A contains its reference point, we can check whether A is behind B by checking whether A's reference point is behind B.
A BSP tree is a binary tree containing all the polygons in the collection, one at each node. The two subtrees of any node are designated as the front and back subtrees of that node. A BSP tree satisfies the property: for any node of the tree containing a polygon A, all the polygons in the front subtree of that node are in front of A, and all the polygons in the back subtree of that node are behind A. BSP trees do not have to be balanced.
We can insert a new polygon B into a BSP tree as follows. If the tree is empty, make B the root. Otherwise, say A is the polygon at the root. If B is behind A, move down to the back subtree of A and recursively try to insert B in that subtree. Otherwise, if B is in front of A, move down to the front subtree of A and recursively try to insert B in that subtree. Keep moving recursively down the tree in this fashion, checking at each node whether B is in front of or behind the polygon there to see which direction to move down. Continue until encountering a null pointer, and insert B there.
Now suppose we want to render the polygons in an order determined by the position p of a viewer. We wish to enumerate all the polygons in the tree so that the polygons that are farther away from the viewer are enumerated first. The following algorithm does it:
Starting at the root polygon A. If p is in front of A, then
otherwise, if p is behind A,
and similarly down the tree. Note that there is never any restructuring of the tree; it is only traversed in different orders depending on the position p of the viewer relative to the polygons in the tree.
Check out these links for some pictures and a nifty applet:
http://www.cs.yorku.ca/~shao/bsp/BSP.html
http://www.ce.unipr.it/~tommesa/jaluit.html