Binary space partitioning: Difference between revisions

Revision as of 01:43, 18 September 2023

Revision as of 01:45, 18 September 2023

Line 136:

== 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]]. However, BSP trees have been applied to image compression.<ref>{{CiteH. journal |last=Radha, |first=HM. |last2=Vetterli |first2=M.and |last3=Leonardi |first3=R. |date=12/1996Leonardi, |title="Image compression using binary space partitioning trees," |url=https://ieeexplore.ieee.org/document/544569in |journal=''IEEE Transactions on Image Processing'', vol. |volume=5, no. |issue=12, |pages=1610–1624pp. 1610-1624, Dec. 1996, |doi=: 10.1109/83.544569 |issn=1941-0042}}.</ref>

==See also==

Line 150:

==Additional references==

{{refbegin}}

*{{cite journal |first1=B. |last1=Naylor |first2=J. |last2=Amanatides |first3=W. |last3=Thibualt |title=Merging BSP Trees Yields Polyhedral Set Operations |journal= ACM SIGGRAPH Computer Graphics |volume=24 |issue=4 |pages=115–124 |date=August 1990 |year= |doi=10.1145/97880.97892 |citeseerx=10.1.1.69.292 }}

*{{cite journal |first=B. |last=Naylor |title=Constructing Good Partitioning Trees |date=May 1993 |journal=Graphics Interface |url=https://www.researchgate.net/publication/2492209 |citeseerx=10.1.1.16.4432}}{{dead link|date=July 2022|bot=medic}}{{cbignore|bot=medic}}

*{{cite journal |first1=S. |last1=Chen |first2=D. |last2=Gordon |title=Front-to-Back Display of BSP Trees |journal=IEEE Computer Graphics & Algorithms |volume=11 |issue=5 |pages=79–85 |date=September 1991 |doi=10.1109/38.90569 |s2cid=19056967 |url=}}

*{{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 }}

*{{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= http://infoscience.epfl.ch/record/33877 |pmid=18290079 |bibcode=1996ITIP....5.1610R }}https://ui.adsabs.harvard.edu/abs/1996ITIP....5.1610R/abstract

*{{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 |year=2000 |title=Computational Geometry |publisher=[[Springer-Verlag]] |edition=2nd |isbn=978-3-540-65620-3 |url-access=registration |url=https://archive.org/details/computationalgeo00berg |chapter=§12: Binary Space Partitions |pages=251–265}} Describes a randomized Painter's Algorithm..

*{{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}}