Content deleted Content added
→Application: | Add: url, bibcode, pmid, pages, issue, volume, journal, date, title, doi, authors 1-3. Changed bare reference to CS1/2. Removed parameters. | Use this tool. Report bugs. | #UCB_Gadget |
|||
Line 20:
*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 games)|brushes]]", introduced in the Quake editor and picked up in the Unreal Editor.
| |||