Kinetic visibility

An essential component of 3D graphics applications is a method to determine visibility, namely to determine which parts of a virtual scene should be drawn on the screen. The seminal paper of Sutherland, Sproull, and Schumacker in 1974 predicted that one of the most promising avenues for research on visibility would be to make use of frame-to-frame coherence, since in a typical computer animation the visible portion of the scene does not change very much from one frame to the next. In the time since this observation was made, however, practitioners and researchers alike have found this type of coherence to be difficult to fully exploit.; In recent years two general tools for addressing this type of problem have been developed in the computational geometry community: the visibility complex and Kinetic Data Structures. The visibility complex is a combinatorial structure that captures visibility relationships among objects in a scene and contextualizes the operation of many visibility algorithms. Kinetic Data Structures provide a general framework for the development of efficient algorithms in a dynamic environment of continuously moving objects. This dissertation explores various methods that result from applying the Kinetic Data Structures framework to substructures of the visibility complex. The algorithms described here are intended to bring theoretical tools for visibility algorithms closer to practical settings where low memory requirements and scalability are primary concerns.; We propose a framework for computing visibility in the plane and in space that leverages temporal coherence, through the use of orientable spatial data structures. We describe three algorithms and associated data structures. The first algorithm is a generalization and adaptation of the classic topological sweep algorithm to enable maintenance of visibility for a moving observer in a static two-dimensional environment. The second algorithm maintains visibility for a point observer in a planar environment of moving obstacles. A probabilistic analysis of the second algorithm demonstrates that in a particular average case setting, the intrinsic complexity of maintaining visibility in a static scene and in a moving scene is asymptotically identical, up to a poly-logarithmic factor in the scene density. The third algorithm illustrates how tools for planar visibility maintenance can be used in a scene of objects that all lie near to some fixed ground plane. An implementation of the third algorithm indicates that this approach can be viable in practice for large scenes with millions of objects.