A Stratified Rendering Algorithm for Virtual Walkthroughs of Large Environments

This thesis investigates the effectiveness of using pre-computed scenes to accelerate on-line culling and rendering during virtual walkthroughs of large, irregular environ-ments. Maintaining a high frame rate is essential for a realistic virtual walkthrough ex-perience. For a large, irregular outdoor environment where most objects are visible, visibility-based algorithms for reducing the number of polygons to be rendered are often not applicable. Approximation algorithms that simplify individual objects or clusters of objects often require cost-benefit heuristics to select the best representa-tion. With new hardware support for texture mapping, a scheme that approximates parts of the scene as texture maps can be realized. This thesis presents a new approach to the approximation problem. The novel aspects of the approach are that 1) it maintains, in physical memory, a constant amount of state for scenes of bounded density; 2) substantially reduces the number of polygons to be rendered; 3) requires no cost-benefit calculation; 4) exploits objec