Binary space partitioning

In computer science, binary space partitioning (BSP) is a method for space partitioning which recursively subdivides a Euclidean space into two convex sets by using hyperplanes as partitions. This process of subdividing gives rise to a representation of objects within the space in the form of a tree data structure known as a BSP tree.

Binary space partitioning was developed in the context of 3D computer graphics in 1969.^[1]^[2] The structure of a BSP tree is useful in rendering because it can efficiently give spatial information about the objects in a scene, such as objects being ordered from front-to-back with respect to a viewer at a given location. 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.

^ Schumacker, R.A.; Brand, B.; Gilliland, M.G.; Sharp, W.H. (1969). Study for Applying Computer-Generated Images to Visual Simulation (Report). U.S. Air Force Human Resources Laboratory. AFHRL-TR-69-14.
^ Cite error: The named reference fuchs80 was invoked but never defined (see the help page).
^ Thibault, William C.; Naylor, Bruce F. (1987). "Set operations on polyhedra using binary space partitioning trees". SIGGRAPH '87 Proceedings of the 14th annual conference on Computer graphics and interactive techniques. ACM. pp. 153–162. doi:10.1145/37402.37421.
^ Etherington, Thomas R.; Morgan, Fraser J.; O’Sullivan, David (2022). "Binary space partitioning generates hierarchical and rectilinear neutral landscape models suitable for human-dominated landscapes". Landscape Ecology. 37 (7): 1761–1769. Bibcode:2022LaEco..37.1761E. doi:10.1007/s10980-022-01452-6.

[schumacker69-1] Schumacker, R.A.; Brand, B.; Gilliland, M.G.; Sharp, W.H. (1969). Study for Applying Computer-Generated Images to Visual Simulation (Report). U.S. Air Force Human Resources Laboratory. AFHRL-TR-69-14.

[fuchs80-2] Cite error: The named reference fuchs80 was invoked but never defined (see the help page).

[thibault87-3] Thibault, William C.; Naylor, Bruce F. (1987). "Set operations on polyhedra using binary space partitioning trees". SIGGRAPH '87 Proceedings of the 14th annual conference on Computer graphics and interactive techniques. ACM. pp. 153–162. doi:10.1145/37402.37421.

[4] Etherington, Thomas R.; Morgan, Fraser J.; O’Sullivan, David (2022). "Binary space partitioning generates hierarchical and rectilinear neutral landscape models suitable for human-dominated landscapes". Landscape Ecology. 37 (7): 1761–1769. Bibcode:2022LaEco..37.1761E. doi:10.1007/s10980-022-01452-6.

[1]

[2]

[3]

[4]