Until recently, opportunities to experience large synthetic rnvironmcnts have been limited primarily to cxpcnsive training simulators. However, with the advent of “location based entertainment” at theme parks and cvcn CD-ROM based games for PCs. these kinds of experiences are beginning to be made available to the gcncral public as well. The constraints on the possibilities for appealing “content” arises from the technological capabilities that are possible for a given pcrformancc level on a given platform. Currently, for 3D graphics, performance is closely tied to the number of tcxturc mapped polygons that can be rendered for each frame as well as the rntc at which collisions of various kinds can be computed. Large synthetic environments require at least tens of thousands of polygons, and could easily entail millions. However. for each image, only a small subset of these polygons are typically required to synthesize the image. Similarly. collisions bctwcen two objects, or between a viewer and the environment, involve an cvcn smaller subset. The task then for efficient geometric computations is to. if possible. quickly identify the relevant subset. The principal methodology for finding the minimal subset of polygons is to use spatial search structures. such as regular grids, octrees, or binary space partitioning trees. In this paper, we describe briefly the current status of our efforts at using binary space partitioning trees for navigating through and playing with large environments, including rendering and collision dctcction. as well as permitting intcractivc modifications of the environment using set operations that should prove appealing for entertainment applications.

Partitioning Trees (or BSP Trees)[Fuchs, Krdem, and Naylor SO] differ from regular grids in that they are hierarchical(multi-resolution), and from octrccs in that the method of space partitioning requires not only determining when to partition. but where, as well. The absence of a restriction on the planes used in partitioning trees obviates the need for a distinction between the spatial search structure and the rcprescntation of polyhedra by using the planes containing faces to partition space. A single tree. reprcscnting some rigid object for example. can be transformed with affine and perspective transformations by only transforming the plane equations: thereby not changing the tree structure. The tree provides a visibility order for rendering objects with any mix of transparent and opaque surfnces. and the near-to-far ordering that can be used for pruning away fully occluded subtrees. In addition. it can be used for efficient solid clipping with a view-volume. for computing shadows and/or global illumination. for intersecting rays with an object, and for determining the location of points(representing, for example, sprites in computer games) in an environment. Spatial relations between two objects can be computed efficiently by merging their respective trees into a single tree [Naylor. Amanatides and Thibault 901. This provides,