What’s a BSP Tree?

A Binary Space Partitioning Tree (or BSP Tree) is a data structure that is used to organize objects within a space. Within the field of computer graphics, it has applications in hidden surface removal and ray tracing. A BSP tree is a recursive sub-division of space that treats each line segment (or polygon, in 3D) as a cutting plane which is used to categorize all remaining objects in the space as either being in “front” or in “back” of that plane. In other words, when a partition is inserted into the tree, it is first categorized with respect to the root node, and then recursively with respect to each appropriate child. For more information on BSP trees, see the BSP Tree FAQ.

Sorry, your browser does not support Java applets.

How To Use This Applet

You can draw line segments in the first canvas pane (the first line, when drawn, causes Java to perform some initialization, so it takes much longer to draw than subsequent ones). Segments are numbered in order, and the tree is built by inserting each segment in numbered order. If a partition must be split, the front and back parts of the partition have an “f” and a “b” appended to their respective names. For example, if partition 1 crosses the cutting plane formed by partition 0, then the part of partition 1 that is in front of partition 0 will be named “1f”, and the part in back will be named “1b”.

You can move the magenta eyepoint by clicking and dragging it, and if you click and drag the arrowhead near the end of the eyepoint’s look vector, you can rotate the camera that images the pseudo-3D scene. In drive mode the look vector points in the direction you move the eyepoint. The BSP tree classification of the eyepoint is shown as a magenta dot in the BSP tree graph.

If “Drive Mode” is enabled, when you move the eye point the look vector automatically points in the direction of motion to give the impression of driving through the 3D scene.

If the drawing of the tree becomes too large for its canvas, click and drag in that canvas to pan the tree around.

Technical Notes

The BSP Tree Algorithm

The BSP tree is created by inserting each segment in numbered order into the tree. In order to allow the user to more easily understand the demo, no attempt is made to select the BSP tree that produces the minimum splitting of segments. This is normally done because it minimizes the size of the tree and makes it more efficient. In addition, no attempt is made to produce a balanced (or nearly balanced) tree, which would also normally be desirable since it prevents degenerate cases such as those where the depth of the tree is approximately equivalent to the number of partitions. Because each partition must be classified with respect to O(lg(n)) other partitions, the expected running time for constructing this BSP tree is O(n*lg(n)).

The Graphing Algorithm

The graph is drawn using the Reingold and Tilford Rooted Tree Drawing Algorithm. More information on that algorithm can be found on page 6 of this PostScript document. If that document is unavailable, here is the relevant description of that algorithm:

After drawing the left and right subtrees, place the drawings of the subtrees at horizontal distance 2. Place the root one level above and half-way between the children. However, if there is only one child, place the root at a horizontal distance 1 from the child.

The Rendering Algorithm

The pseudo-3D scene is rendered by classifying the eyepoint with respect to the root segment, recursively drawing all segments on the other side of that segment, drawing that segment, and then recursively drawing all segments on the same side of that segment. If the eyepoint intersects a segment, we’re seeing it edge-on, so it isn’t drawn. Because each segment is visited exactly once while drawing the scene, the scene can be rendered in O(n) time. Here is pseudocode for a method on a BSP tree node class that implements this algorithm:

draw3DScene()
  if location(eye.point) == frontSide
    back.draw3DScene()
    drawPolygon()
    front.draw3DScene()
  else if location(eye.point) == backSide
    front.draw3DScene()
    drawPolygon()
    back.draw3DScene()
  else
    front.draw3DScene()
    back.draw3DScene()

When we’re ready to draw the scene, the eyepoint and look vector are used to determine the coordinate system for the camera space. Then each polygon is drawn by using the folowing algorithm:

drawPolygon()
  transform segment endpoints to camera space
  clip segment to view frustrum
  convert segment to polygon:
    set the width to the x values scaled down by the y values
    set the height to a constant value scaled down by the y values

More Information

• BSP Tree FAQ
• The Graphics bible: Computer Graphics: Principles and Practice by Foley, van Dam, Feiner, and Hughes
• Ray Tracing with BSP Trees: Graphics Gems III by David Kirk