Binary space partitioning: Difference between revisions

Revision as of 10:07, 2 June 2024

Revision as of 11:18, 3 July 2024

Line 3:

|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 ana [[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">