Content deleted Content added
Starlighsky (talk | contribs) Added application and citation |
Link suggestions feature: 3 links added. |
||
| (38 intermediate revisions by 19 users not shown) | |||
Line 14:
|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.
=={{Anchor|Timeline}}History==
*1969 Schumacker et al.<ref name="schumacker69" /> published a report that described how carefully positioned planes in a virtual environment could be used to accelerate polygon ordering. The technique made use of depth coherence, which states that a polygon on the far side of the plane cannot, in any way, obstruct a closer polygon. This was used in flight simulators made by GE as well as Evans and Sutherland. However, the creation of the polygonal data organization was performed manually by the scene designer.
*1980 [[Henry Fuchs|Fuchs]] et al.<ref name="fuchs80" /> extended Schumacker's idea to the representation of 3D objects in a virtual environment by using planes that lie coincident with polygons to recursively partition the 3D space. This provided a fully automated and algorithmic generation of a hierarchical polygonal data structure known as a Binary Space Partitioning Tree (BSP Tree). The process took place as an off-line preprocessing step that was performed once per environment/object. At run-time, the view-dependent visibility ordering was generated by traversing the tree.
*1981 Naylor's Ph.D. thesis<ref>{{cite thesis |last=Naylor |first=Bruce |date=May 1981 |title=A Priori Based Techniques for Determining Visibility Priority for 3-D Scenes |url=https://www.proquest.com/openview/94daf3b8677f8ca4567915515efeefac/1?pq-origsite=gscholar&cbl=18750&diss=y |degree=Ph.D. |___location=University of Texas at Dallas |access-date=June 5, 2025}}</ref> provided a full development of both BSP trees and a graph-theoretic approach using strongly connected components for pre-computing visibility, as well as the connection between the two methods. BSP trees as a dimension-independent spatial search structure were emphasized, with applications to visible surface determination. The thesis also included the first empirical data demonstrating that the size of the tree and the number of new polygons were reasonable (using a model of the Space Shuttle).
*1983 [[Henry Fuchs|Fuchs]] et al.<ref>{{Cite book |last1=Fuchs |first1=Henry |last2=Abram |first2=Gregory D. |last3=Grant |first3=Eric D. |title=Proceedings of the 10th annual conference on Computer graphics and interactive techniques |chapter=Near real-time shaded display of rigid objects |date=1983 |language=en |publisher=ACM |pages=65–72 |doi=10.1145/800059.801134 |isbn=978-0-89791-109-2}}</ref> described a micro-code implementation of the BSP tree algorithm on an Ikonas frame buffer system. This was the first demonstration of real-time visible surface determination using BSP trees.
*1987 Thibault and Naylor<ref name="thibault87" /> described how arbitrary polyhedra may be represented using a BSP tree as opposed to the traditional b-rep ([[boundary representation]]). This provided a solid representation vs. a surface based-representation. Set operations on polyhedra were described using a tool, enabling [[constructive solid geometry]] (CSG) in real-time. This was the forerunner of BSP level design using "[[brush (video
*1990 Naylor, Amanatides, and Thibault<ref>{{cite journal |last1=Naylor |first1=Bruce |last2=Amanatides |first2=John |last3=Thibault |first3=William |date=August 1990 |title=Merging BSP Trees Yields Polyhedral Set Operations |url=https://dl.acm.org/doi/pdf/10.1145/97880.97892 |doi=10.1145/97880.97892 |citeseerx=10.1.1.69.292|journal=ACM SIGGRAPH Computer Graphics |volume=24 |issue=4 |publisher=Association of Computing Machinery |pages=115–124 |access-date=June 5, 2025}}</ref> provided an algorithm for merging two BSP trees to form a new BSP tree from the two original trees. This provides many benefits including combining moving objects represented by BSP trees with a static environment (also represented by a BSP tree), very efficient CSG operations on polyhedra, exact collisions detection in O(log n * log n), and proper ordering of transparent surfaces contained in two interpenetrating objects (has been used for an x-ray vision effect).
*
*1991 Gordon and Chen<ref>{{cite
*1992 [[Seth J. Teller|Teller]]'s Ph.D. thesis<ref>{{cite thesis |last=Teller |first=Seth |date=1992 |title=Visibility computations in densely occluded polyhedral environments |url=https://www.proquest.com/openview/80322259984cf6c676a345676ab1d74a/1?pq-origsite=gscholar&cbl=18750&diss=y |degree=Ph.D. |___location=University of California at Berkeley |access-date=June 5, 2025}}</ref> described the efficient generation of potentially visible sets as a pre-processing step to accelerate real-time visible surface determination in arbitrary 3D polygonal environments. This was used in ''[[Quake (video game)|Quake]]'' and contributed significantly to that game's performance.
*1993 Naylor<ref>{{cite journal |last1=Naylor |first1=Bruce |date=1993 |title=Constructing good partitioning trees |url=https://www.researchgate.net/profile/Bruce-Naylor/publication/2492209_Constructing_Good_Partitioning_Trees/links/55cc86be08aea2d9bdce442d/Constructing-Good-Partitioning-Trees.pdf |journal=Graphics Interface |publisher=Canadian Information Processing Society |pages=181–191 |access-date=June 5, 2025}}</ref> answered the question of what characterizes a good BSP tree. He used expected case models (rather than worst-case analysis) to mathematically measure the expected cost of searching a tree and used this measure to build good BSP trees. Intuitively, the tree represents an object in a multi-resolution fashion (more exactly, as a tree of approximations). Parallels with Huffman codes and probabilistic [[binary search]] trees are drawn.
*1993 Hayder Radha's Ph.D. thesis<ref>{{cite thesis |last=Radha |first=Hayder |date=1993 |title=Efficient image representation using binary space partitioning trees |url=https://www.proquest.com/openview/a80bc19b1374b928afa8844a8ed05ef4/1?pq-origsite=gscholar&cbl=18750&diss=y |degree=Ph.D. |publisher=Columbia University |access-date=June 5, 2025}}</ref> described (natural) image representation methods using BSP trees. This includes the development of an optimal BSP-tree construction framework for any arbitrary input image. This framework is based on a new image transform, known as the Least-Square-Error (LSE) Partitioning Line (LPE) transform. H. Radha's thesis also developed an optimal rate-distortion (RD) [[image compression]] framework and image manipulation approaches using BSP trees.
==Overview==
[[File:2D Binary Index.svg|thumb|An example of a recursive binary space partitioning [[quadtree]] for a 2D index]]
Binary space partitioning is a generic process of [[recursion|recursively]] dividing a scene into two until the partitioning satisfies one or more requirements. It can be seen as a generalization of other spatial tree structures such as [[K-d tree|''k''-d trees]] and [[quadtree]]s, one where hyperplanes that partition the space may have any orientation, rather than being aligned with the coordinate axes as they are in ''k''-d trees or quadtrees. When used in computer graphics to render scenes composed of planar [[Polygon mesh|polygons]], the partitioning planes are frequently chosen to coincide with the planes defined by polygons in the scene.▼
▲Binary space partitioning is a generic process of [[recursion|recursively]] dividing a scene into two using [[hyperplanes]]<ref>{{cite web |last=Naylor |first=Bruce |date=January 2005 |title=A Tutorial on Binary Space Partitioning Trees |url=https://www.researchgate.net/publication/238348725_A_Tutorial_on_Binary_Space_Partitioning_Trees |website=ResearchGate |access-date=July 1, 2025}}</ref> until the partitioning satisfies one or more requirements. It can be seen as a generalization of other spatial tree structures such as [[K-d tree|''k''-d trees]] and [[quadtree]]s, one where hyperplanes that partition the space may have any orientation, rather than being aligned with the coordinate axes as they are in ''k''-d trees or quadtrees. When used in computer graphics to render scenes composed of planar [[Polygon mesh|polygons]], the partitioning planes are frequently chosen to coincide with the planes defined by polygons in the scene.
The specific choice of partitioning plane and criterion for terminating the partitioning process varies depending on the purpose of the BSP tree. For example, in computer graphics rendering, the scene is divided until each node of the BSP tree contains only polygons that can be rendered in arbitrary order. When [[back-face culling]] is used, each node, therefore, contains a convex set of polygons, whereas when rendering double-sided polygons, each node of the BSP tree contains only polygons in a single plane. In collision detection or ray tracing, a scene may be divided up into [[Geometric primitive|primitives]] on which collision or ray intersection tests are straightforward.
Line 65 ⟶ 67:
|
| Start with a list of lines, (or in 3D, polygons) making up the scene. In the tree diagrams, lists are denoted by rounded rectangles and nodes in the BSP tree by circles. In the spatial diagram of the lines, the direction chosen to be the 'front' of a line is denoted by an arrow.
| style="text-align:right;" | [[File:Example of BSP tree construction - step 1.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''i.'''
Line 74 ⟶ 76:
# We first process the lines in front of A (in steps ii–v),...
# ...followed by those behind (in steps vi–vii).
| style="text-align:right;" | [[File:Example of BSP tree construction - step 2.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''ii.''' || We now apply the algorithm to the list of lines in front of A (containing B2, C2, D2). We choose a line, B2, add it to a node and split the rest of the list into those lines that are in front of B2 (D2), and those that are behind it (C2, D3). || style="text-align:right;" | [[File:Example of BSP tree construction - step 3.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''iii.'''
| Choose a line, D2, from the list of lines in front of B2 and A. It is the only line in the list, so after adding it to a node, nothing further needs to be done.
| style="text-align:right;" | [[File:Example of BSP tree construction - step 4.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''iv.'''
| We are done with the lines in front of B2, so consider the lines behind B2 (C2 and D3). Choose one of these (C2), add it to a node, and put the other line in the list (D3) into the list of lines in front of C2.
| style="text-align:right;" | [[File:Example of BSP tree construction - step 5.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''v.'''
| Now look at the list of lines in front of C2. There is only one line (D3), so add this to a node and continue.
| style="text-align:right;" | [[File:Example of BSP tree construction - step 6.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''vi.''' || We have now added all of the lines in front of A to the BSP tree, so we now start on the list of lines behind A. Choosing a line (B1) from this list, we add B1 to a node and split the remainder of the list into lines in front of B1 (i.e. D1), and lines behind B1 (i.e. C1). || [[File:Example of BSP tree construction - step 7.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''vii.''' || Processing first the list of lines in front of B1, D1 is the only line in this list, so add this to a node and continue. || style="text-align:right;" | [[File:Example of BSP tree construction - step 8.svg|class=skin-invert]]
|- valign="top"
| style="text-align:right;" | '''viii.''' || Looking next at the list of lines behind B1, the only line in this list is C1, so add this to a node, and the BSP tree is complete. || style="text-align:right;" | [[File:Example of BSP tree construction - step 9.svg|class=skin-invert]]
|}
Line 136 ⟶ 138:
== Application ==
BSP trees are often used by 3D [[video game]]s, particularly [[first-person shooter]]s and those with indoor environments. [[Game engine]]s using BSP trees include the [[Doom engine|Doom (id Tech 1)]], [[Quake engine|Quake (id Tech 2 variant)]], [[GoldSrc]] and [[Source (game engine)|Source]] engines. In them, BSP trees containing the static geometry of a scene are often used together with a [[Z-buffer]], to correctly merge movable objects such as doors and characters onto the background scene. 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 [[Hidden surface determination|visible surface determination]].
BSP trees have also been applied to image compression.<ref>{{ ==See also==
* [[Chazelle polyhedron]]
* [[k-d tree]]
* [[Octree]]
Line 150 ⟶ 154:
==Additional references==
{{refbegin}}
*{{cite journal |
*{{cite journal |first1=H. |last1=Radha |first2=R. |last2=Leoonardi |first3=M. |last3=Vetterli |first4=B. |last4=Naylor |title=Binary space partitioning tree representation of images |journal=Journal of Visual Communications and Image Processing |volume=2 |issue=3 |pages=201–221 |date=1991 |doi=10.1016/1047-3203(91)90023-9 |url=http://infoscience.epfl.ch/record/33911 |doi-access=free
▲*{{cite journal |first1=H. |last1=Radha |first2=R. |last2=Leoonardi |first3=M. |last3=Vetterli |first4=B. |last4=Naylor |title=Binary space partitioning tree representation of images |journal=Journal of Visual Communications and Image Processing |volume=2 |issue=3 |pages=201–221 |date=1991 |doi=10.1016/1047-3203(91)90023-9 |url=http://infoscience.epfl.ch/record/33911|doi-access=free }}
*{{cite thesis |first=H.M.S. |last=Radha |title=Efficient Image Representation using Binary Space Partitioning Trees |date=1993 |type=PhD |publisher=Columbia University |oclc=30775044}}
*{{cite journal |first=H.M.S. |last=Radha |title=Efficient image representation using binary space partitioning trees |journal=Signal Processing |volume=35 |issue=2 |pages=174–181 |date=1994 |doi=10.1016/0165-1684(94)90047-7|bibcode=1994SigPr..35..174R }}
*{{cite journal |first1=H. |last1=Radha |first2=M. |last2=Vetterli |first3=R. |last3=Leoonardi |title=Image compression using binary space partitioning trees |journal=IEEE Transactions on Image Processing |volume=5 |issue=12 |pages=1610–24 |date=December 1996 |doi=10.1109/83.544569 |url=
*{{cite CiteSeerX |first=A.S. |last=Winter |title=An investigation into real-time 3d polygon rendering using bsp trees |date=April 1999 |citeseerx=10.1.1.11.9725
*{{cite book |first1=M. |last1=de Berg |author-link=Mark de Berg |first2=M. |last2=van Kreveld |author2-link=Marc van Kreveld |first3=M. |last3=Overmars |author3-link=Mark Overmars |first4=O. |last4=Schwarzkopf |author4-link=Otfried Schwarzkopf
*{{cite book |first=Christer |last=Ericson |chapter=8. BSP Tree Hierarchies |chapter-url=https://books.google.com/books?id=WGpL6Sk9qNAC&pg=PA350 |title=Real-Time collision detection |publisher=Morgan Kaufmann |date=2005 |isbn=1-55860-732-3 |pages=349–382 |series=Morgan Kaufmann Series in Interactive 3-D Technology}}
{{refend}}
Line 170 ⟶ 172:
*[https://web.archive.org/web/20111115163809/http://www.devmaster.net/articles/bsp-trees BSP Trees: Theory and Implementation]
*[http://www.euclideanspace.com/threed/solidmodel/spatialdecomposition/bsp/index.htm BSP in 3D space]
*[https://www.google.com/books/edition/Graphics_Gems_V_Macintosh_Version/ekGjBQAAQBAJ?hl=en&gbpv=1&dq=graphics%20gems%20v&pg=PA121&printsec=frontcover Graphics Gems V: A Walk through BSP Trees]
{{Authority control}}
| |||