| This dissertation presents an out-of-core algorithm for high-fidelity walkthroughs of large virtual environments. A novel feature of our walkthrough system is that it performs work proportional only to the required detail in the visible geometry at the rendering time. To accomplish this, we partition the space of possible view-points into view-cells (or view-regions). We use a pre-computation phase that efficiently generates per-cell vLOD: the geometry visible from a view-region reduced to an appropriate level. Our system takes as input a set of triangles with per vertex attributes. We present an out-of-core algorithm that partitions this set into a number of objects. Each object consists of triangles that tend to be either all visible or all occluded from each view-region. Only the objects marked visible from the viewer's current view-region will be sent for rendering during the walkthrough. This reduces the unnecessary information sent to the graphics pipeline for rendering. To accomplish the object partitioning, we give an approximation algorithm for a new error based binary matrix clustering problem.; To compute region based visibility for large polygonal models, we use an efficient hardware-accelerated algorithm. The algorithm works for general out-of-core 3D scenes. It conservatively bounds shadow-volumes and reduces the general shadow containment problem to hardware occlusion queries. As a result, we are able to take advantage of occluder fusion. We also present a 2.5D variant that is able to bound the frusta more tightly. Empirical results show that our algorithm overestimates the real visibility only by a factor of 2--5 and takes less than a second per cell for large 3D scenes.; The vLODs are not required to be memory resident in our scheme; rather they are fetched from the disk on the fly and cached before use. In order to support efficient prefetching, we lay out the vLOD data on the disk in an access-coherent fashion. We present a novel formulation of this disk layout problem and provide its solution. This custom disk layout helps reduce the time taken to load the data by 30% on average.; vLOD data is extremely large and must be compressed for efficient disk usage. We encode changes between neighboring cells' vLODs and store them in a compressed fashion on the disk. We provide a new specialized compression algorithm to achieve 60x compression on average; significantly better than prior approaches. (Abstract shortened by UMI.)... |
