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.