BSP Trees

This is a small collection of pointers to information on BSP trees.

A binary space partition (BSP) tree is a multidimensional generalization of the binary tree in which space is recursively split by lines, planes, or hyperplanes. It is also a generalization of the k-dimensional (k-d) tree.

Issues

• The amount of splitting that occurs during tree construction greatly affects its memory and time cost.
• Choosing a good split line (plane) at each step to minimize splitting and/or balance the tree is critical.
• When using a BSP tree for a painter's algorithm, typically the entire tree is traversed, so the total size of the tree should be minimized, and balance is unimportant.
• When using a BSP tree for ray tracing, typically several paths from root to leaves are followed, so minimizing the depth of the tree is more critical than minimizing its total size, and hence tree balance is important.

• Styles of BSP Tree
There are several options according to how one answers the questions:
• How are line segments / triangles / spheres / other objects that span the split line (plane) handled?
• split and recurse. Subdivide the segment (or whatever) into pieces with the splitter and recurse on the left and right subtrees. This is the standard approach.
• recurse without splitting. List the full object in both subtrees. Ray tracing this data structure is inefficient unless ray-intersection "mailboxes" are used.
• store the object at the internal node. This way tree size is linear, but queries on the data structure are less efficient in some (most?) cases.
• Which lines (planes) are used for splitting?
• Auto-partition: splitting lines (planes) are extensions of the line segments (triangles) in the input set.
• General: arbitrary lines (planes) can be used as splitters.
• Axis-aligned: if the split planes are always perpendicular to the axes, the BSP tree is called a k-d tree. Sometimes people split at the geometric midpoint, or at the median of the vertices along one dimension.
• When to stop splitting?
• split until the leaves contain a single line segment (triangle). This is the classic approach.
• stop sooner, when the leaves contain 10 objects or fewer, say. This might be better, in some situations.

Results

Note that theory folks (the computational geometry community) tend to study auto-partitions a lot, while computer graphics and game people usually don't limit themselves to auto-partitions. When reading "expected" results, be careful to note the statistics of the scenes being analyzed; they may differ significantly from "real" scenes, e.g. lots of possibly big polygons versus a triangulated manifold consisting of lots of small polygons. This difference probably explains the discrepancy between expected results and empirical results. Naylor '93 discusses this issue.
• optimal tree construction
Building the smallest tree is NP-complete; nobody does this in practice. Instead people use heuristics to find approximately-optimal trees.
• 2-D, auto-partition of non-intersecting line segments
• expected size
O(n log n). See de Berg's book.
• lower bound size
Just proven: there are configurations of segments whose BSP tree has superlinear size. In particular, there are sets of line segments where every BSP tree needs Omega((n log n)/log log n) cuts, disproving the long-standing conjecture that O(n) cuts suffice. See paper by Toth will be in the next (2001?) ACM SOCG proceedings.
• empirical size
O(n)?
• 2-D, auto-partition of non-intersecting "fat" line segments
• If the ratio of longest to shortest segment is bounded, a linear size BSP tree exists. See de Berg's papers.
• 3-D, auto-partition of non-intersecting triangles
• expected size
Best known algorithm: O(n log^2 n). See Agarwal's paper.
Older algorithms: O(n^2). See de Berg's book.
• lower bound size
Omega(n^2). That is, there are some configurations for which the smallest BSP tree is Theta(n^2). See de Berg's book.
• All known algorithms will sometimes build trees of quadratic size (Theta(n^2)) when a tree of linear size exists. No one knows a fast algorithm for building a BSP tree that is within a constant factor of the optimal size. See Agarwal's paper.
• empirical size
O(n log n)? See Naylor's GI'93 paper.
I hope I've got the above results right. Send me email if not.

15-463, Computer Graphics 2
Paul Heckbert, 12 Apr. 2001