Binary space partitioning: Difference between revisions

Revision as of 19:23, 5 June 2025

Revision as of 19:40, 5 June 2025

Line 25:

*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 [[Seth J. Teller|Teller]] and Séquin<ref>{{cite journal |last1=Teller |first1=Seth J. |last2=Séquin |first2=Carlo H. |date=July 1, 1991 |title=Visibility preprocessing for interactive walkthroughs |url=https://dl.acm.org/doi/abs/10.1145/127719.122725 |journal=ACM SIGGRAPH Computer Graphics |volume=25 |issue=4 |publisher=Association of Computing Machinery |pages=61–70 |access-date=June 5, 2025}}</ref> proposed the offline generation of potentially visible sets to accelerate visible surface determination in orthogonal 2D environments.

*1991 Gordon and Chen<ref>{{cite [CHEN91]journal |first1=S. |last1=Chen |first2=D. |last2=Gordon |title=Front-to-Back Display of BSP Trees |journal=IEEE Computer Graphics and Applications |volume=11 |issue=5 |pages=79–85 |date=October 1991 |doi=10.1109/38.90569 |s2cid=19056967 |url=https://www.researchgate.net/publication/3208236_Front-to-back_display_of_BSP_trees}}</ref> described an efficient method of performing front-to-back rendering from a BSP tree, rather than the traditional back-to-front approach. They utilized a special data structure to record, efficiently, parts of the screen that have been drawn, and those yet to be rendered. This algorithm, together with the description of BSP Trees in the standard computer graphics textbook of the day (''[[Computer Graphics: Principles and Practice]]'') was used by [[John D. Carmack|John Carmack]] in the making of [[Doom (1993 video game)|''Doom'' (video game)]].

*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==