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.


Papers and Books



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. I hope I've got the above results right. Send me email if not.

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