Output-sensitive rendering and communication in dynamic virtual environments

The efficient rendering of large dynamic scenes is an important open problem. Optimization techniques for static scenes, such as output-sensitive visibility calculation, must be carefully adapted to dynamic models in order to remain effective. Distributed virtual environments pose a particular difficulty, because communication between the users must be minimized in addition to each user's rendering time. We show how output-sensitive visibility calculation algorithms can be adapted to dynamic scenes, and used to reduce the communication requirements between workstations in a distributed virtual environment. The solution is based on temporal bounding volumes, guaranteed to contain the dynamic objects for some period of time. These volumes are inserted into a visibility algorithm's main data structure instead of hidden dynamic objects. Subsequently a dynamic object is ignored until its bounding volume becomes visible or is no longer guaranteed to contain the object. In a distributed virtual environment, this saves not only the rendering of the object, but its update through a communication network too. We show an algorithm which combines this method with BSP tree based output-sensitive visibility calculation, and report on the implementation of our system.