Editing Binary space partitioning (section)

{{Short description|Method for recursively subdividing a space into two subsets using hyperplanes}}
{{More citations needed
|date=May 2016}}
[[File:Binary space partition.png|thumb|300x300px|The process of making a BSP tree]]
In [[computer science]], '''binary space partitioning''' ('''BSP''') is a method for [[space partitioning]] which [[recursively]] subdivides a [[Euclidean space]] into two [[convex set]]s by using [[hyperplane]]s as partitions. This process of subdividing gives rise to a representation of objects within the space in the form of a [[Tree (data structure)|tree data structure]] known as a '''BSP tree'''.

Binary space partitioning was developed in the context of [[3D computer graphics]] in 1969.<ref name="schumacker69">{{Cite report |url=https://books.google.com/books?id=0mtk5MdXJhEC |title=Study for Applying Computer-Generated Images to Visual Simulation |last1=Schumacker |first1=R.A. |last2=Brand |first2=B. |date=1969 |publisher=U.S. Air Force Human Resources Laboratory |id=AFHRL-TR-69-14 |last3=Gilliland |first3=M.G. |last4=Sharp |first4=W.H.}}</ref><ref name="fuchs80" /> The structure of a BSP tree is useful in [[rendering (computer graphics)|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<!-- , to be accessed rapidly -->. Other applications of BSP include: performing [[geometrical]] operations with [[shape]]s ([[constructive solid geometry]]) in [[Computer-aided design|CAD]],<ref name="thibault87">
{{cite conference 
 | last1      = Thibault | first1 = William C.
 | last2     = Naylor     | first2 = Bruce F.
 |title=Set operations on polyhedra using binary space partitioning trees
|book-title=SIGGRAPH '87 Proceedings of the 14th annual conference on Computer graphics and interactive techniques
| year=1987
|pages=153–162 
| publisher=ACM
| doi=10.1145/37402.37421}}</ref> [[collision detection]] in [[robotics]] and 3D video games, [[ray tracing (graphics)|ray tracing]], virtual landscape simulation,<ref>{{Cite journal |last1=Etherington |first1=Thomas R. |last2=Morgan |first2=Fraser J. |last3=O’Sullivan |first3=David |date=2022 |title=Binary space partitioning generates hierarchical and rectilinear neutral landscape models suitable for human-dominated landscapes |journal=Landscape Ecology |language=en |volume=37 |issue=7 |pages=1761–1769 |doi=10.1007/s10980-022-01452-6 |doi-access=free|bibcode=2022LaEco..37.1761E }}</ref> and other applications that involve the handling of complex spatial scenes.