Binary Space Partition

A binary space-partitioning (BSP) tree is an efficient method for determining object visibility by painting surfaces onto the screen from back to front, as in the painter's algorithm. The BSP tree is particularly useful when the view reference point changes, but the objects in a scene are at fixed positions. 

Applying a BSP tree to visibility testing involves identifying surfaces that are "inside" and "outside" the partitioning plane at each step of the space subdivision, relative to the viewing direction. The basic concept in this algorithm. With plane P₁, we first partition the space into two sets of objects. One set of objects is behind, or in back of, plane P₁ relative to the view plane P₁, we divide that object into two separate objects, labeled A and B. Objects A and C are in front of P₁, and objects B and D are behind P₁. We next partition the space again with plane P₂ and construct the binary tree. In this tree, the objects are represented as terminal nodes, with front objects as left branches and back objects as right branches.