posted 23 years ago
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 quare
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:
The resulting BSP tree looks like this at each step:
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.
--
