Handout on BSP Trees

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

- recursively render the polygons in the back subtree of
*A*; - render
*A*; - recursively render the polygons in the front subtree of
*A*.

otherwise, if *p* is behind *A*,

- recursively render the polygons in the front subtree of
*A*; - render
*A*; - recursively render the polygons in the back subtree of
*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