Binary Space Partition

BSP (Binary Space Partition) Trees

BSP trees are a geometric tool that can be used for a variety of tasks, including resolving visibility, computing shadows and also to reject polygons that are outside the view volume. BSPs are too complex to implement in hardware (at least today), so those operations will be performed by the CPU rather than the GPU. BSPs are particularly useful for walkthrough/flythrough applications where the viewpoint is allowed to move but (most of) the scene and the lights are fixed (however, extending them to handle scene is, to some extent, possible). Historically, they have been used with great success inflight simulators. Variants of BSP trees are commonly used in computer games too.

The above is a direct quote from http://www.cc.gatech.edu/classes/AY2004/cs4451a_fall/bsp.pdf

---

Binary Space Partition Trees (or BSP trees for short) where introduced by Fuchs, Kedem, and Naylor around 1980. This graphics trio produced two papers: "Predeterming Visibility Priority in 3-D Scenes" and "On Visible Surface Generation by A Priori Tree Structures" which outlined the usefullness of BSP trees and how to implement them. Fuchs, Kedem, and Naylor primarly focused on enhancing rendering of static scenes. Later authors built on the above papers to incorporate shadow generation and handling of dynamic scenes.

Simply, a BSP tree is a heirarchical subdivisions of n dimensional space into convex subspaces. Each node has a front and back leaf. Starting off with the root node, all subsequent insertions are partitioned by the hyperplane of the current node. In 2 dimensional space, a hyperplane is a line. In 3 dimensional space, a hyperplane is a plane. The end goal of a BSP tree if for the hyperplanes of the leaf nodes to be trivially "behind" or "infront" of the parent hyperplane.

BSP trees are very useful for real time interaction with displays of static images. Before the static scene is rendered, the BSP tree is calculated. BSP trees can be traversed very quickly (linear time) for hidden surface removal and shadow casting. With some work, BSP trees can be modified to handle dynamic events in a scene.

The above is a direct quote from http://www.cs.wpi.edu/~matt/courses/cs563/talks/bsp/document.html

---

What is a BSP Tree?

Overview A Binary Space Partitioning (BSP) tree represents a recursive, hierarchical partitioning, or subdivision, of n-dimensional space into convex subspaces. BSP tree construction is a process which takes a subspace and partitions it by any hyperplane that intersects the interior of that subspace. The result is two new subspaces that can be further partitioned by recursive application of the method.

A "hyperplane" in n-dimensional space is an n-1 dimensional object which can be used to divide the space into two half-spaces. For example, in three dimensional space, the "hyperplane" is a plane. In two dimensional space, a line is used.

BSP trees are extremely versatile, because they are powerful sorting and classification structures. They have uses ranging from hidden surface removal and ray tracing hierarchies to solid modeling and robot motion planning.

Example

An easy way to think about BSP trees is to limit the discussion to two dimensions. To simplify the situation, let's say that we will use only lines parallel to the X or Y axis, and that we will divide the space equally at each node. For example, given a square somewhere in the XY plane, we select the first split, and thus the root of the BSP Tree, to cut the square in half in the X direction. At each slice, we will choose a line of the opposite orientation from the last one, so the second slice will divide each of the new pieces in the Y direction. This process will continue recursively until we reach a stopping point, and looks like this:

+-----------+......+-----+-----+......+-----+-----+
|-----------|......|-----|-----|......|-----|-----|
|-----------|......|-----|-----|......|--d--|-----|
|-----------|......|-----|-----|......|-----|-----|
|---- a ----|..->..|--b--X--c--|..->..+--Y--+--f--| -> ...
|-----------|......|-----|-----|......|-----|-----|
|-----------|......|-----|-----|......|--e--|-----|
|-----------|......|-----|-----|......|-----|-----|
+-----------+......+-----+-----+......+-----+-----+

      The resulting BSP tree looks like this at each step:

     a                  X                  X           ...
                      -/ \+              -/ \+
                      /   \              /   \
                     b     c            Y     f
                                      -/ \+
                                      /   \
                                     e     d
  
      

Other space partitioning structures

BSP trees are closely related to Quadtrees and Octrees. Quadtrees and Octrees are space partitioning trees which recursively divide subspaces into four and eight new subspaces, respectively. A BSP Tree can be used to simulate both of these structures.

Last Update: 05/16/95 01:18:59

The above is a direct quote from http://www.faqs.org/faqs/graphics/bsptree-faq/