Modeling for the plausible emulation of large worlds
John F. Hughes, Steven Charles Dollins · 2002
As interactive graphics applications such as driving- and flight-simulators and especially video games, advance towards ever more complex synthetic environments, numerous challenges arise in the modeling, storing, loading, simulating, animating and rendering of the large quantity of data involved. These challenges impose strict limitations upon the designers of typical interactive graphics applications, who, to maintain interactive display rates, must simplify the data that the computer processes in each frame. The goal of this dissertation is to enable the authoring and real-time emulation of highly interactive, large-scale synthetic environments. In order to support very large worlds, we want to present the user with an approximation of both the geometry and behaviors of these worlds, computing only enough detail to emulate a plausible experience based on the limits of the user's time-varying perception, knowledge, and expectation of the environment. Our approaches for achieving this goal are on-the-fly semantic procedural modeling of a multi-resolution description for geometry and behaviors, an event-driven runtime for managing and displaying these at interactive rates, and a cache mechanism which organizes the geometry for efficient rendering on current graphics hardware. Both as a modeling aid and as a means of data compression, we describe the world procedurally using stochastic subdivision techniques, generating geometric and behavioral detail only as needed by the application. Authored content, in a quadtree structure akin to a scene graph, provides the parameters that guide the procedural generation of the world. We present two new inter-related data structures, the quadtree cache and the quadtree dual, which manage the nested levels of detail of the procedurally generated terrain and object data. The novel interleaved update mechanism of the cache allows us to batch geometry into time-coherent pieces that are well-suited for real-time rendering.