Graphics Notes

BSP Trees

Dansk

Deutsch

English

What's a BSP Tree?

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 the response time is too slow when moving line segments, toggle the "interactive" ballot box to disable the interactive nature of the applet. In non-interactive mode the BSP tree is rebuilt only after a segment has been moved to a new location and the mouse button is released.
If the drawing of the tree becomes too large for its canvas, click and drag in that canvas to pan the tree around.
Click here for implementation details.
Click here for the BSP Tree FAQ.
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.