Binary space partitioning

Other applications of BSP include: performing geometrical operations with shapes (constructive solid geometry) in CAD,[3] collision detection in robotics and 3D video games, ray tracing, virtual landscape simulation,[4] and other applications that involve the handling of complex spatial scenes.

Binary space partitioning arose from computer graphics needing to rapidly draw three-dimensional scenes composed of polygons.

Typically, it is therefore performed once on static geometry, as a pre-calculation step, prior to rendering or other real-time operations on a scene.

The canonical use of a BSP tree is for rendering polygons (that are double-sided, that is, without back-face culling) with the painter's algorithm.

Each polygon is designated with a front side and a backside which could be chosen arbitrarily and only affects the structure of the tree but not the required result.

The choice of which polygon or line is used as a partitioning plane (in step 1 of the algorithm) is therefore important in creating an efficient BSP tree.

While binary space partitioning provides a convenient way to store and retrieve spatial information about polygons in a scene, it does not solve the problem of visible surface determination.