Content deleted Content added
→Application: Fix grammar (last sentence was unrelated to previous ones) |
DanielPharos (talk | contribs) m Fixed article link. |
||
Line 23:
*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. 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 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).
*1990 [[Seth J. Teller|Teller]] and Séquin proposed the offline generation of potentially visible sets to accelerate visible surface determination in orthogonal 2D environments.
| |||