Binary space partitioning: Difference between revisions

Revision as of 13:54, 27 April 2025

Revision as of 14:49, 29 April 2025

Line 21:

*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 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. |chapter=Near real-time shaded display of rigid objects |date=1983 |title=Proceedings of the 10th annual conference on Computer graphics and interactive techniques |chapter-url=https://dl.acm.org/doi/10.1145/800059.801134Near real-time shaded display of rigid objects |journaldate=SIGGRAPH Comput. Graph.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 games)|brushes]]", introduced in the Quake editor and picked up in the Unreal Editor.

*1990 Naylor, Amanatides, and Thibault 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).