ABSTRACT
Binary space partitioning (BSP) trees can be viewed as a generalization of kd-trees. Like kd-trees, BSP trees are binary trees. This chapter present a recursive definition for the BSP. A simple algorithm to render a set of polygons with correct hidden-surface removal, and without a Z-buffer, is the painter’s algorithm. The chapter mentions a few strategies to optimize this algorithm. BSPs offer a nice way to represent volumetric polygonal objects, i.e., closed objects. In other words, their border is represented by polygons and they have an “inside” and an “outside.” The chapter shows an example of such a BSP representation. It follows the convention that normals point to the “outside,” and that the right child of a BSP node lies in the positive half-space and the left child in the negative half-space.
