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 Fuchs et al. 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 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 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 "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). 1990 Teller and Séquin proposed the offline generation of potentially visible sets to accelerate visible surface determination in orthogonal 2D environments. 1991 Gordon and Chen [CHEN91] described an efficient method