Thomas Allen Funkhouser

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-93-771
September 1993

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/CSD-93-771.pdf

This thesis describes a system for interactive walkthroughs of large, fully furnished architectural models.

Realistic-looking architectural models with furniture may consist of millions of polygons and require gigabytes of data -- far more than today's workstations can render at interactive frame rates or fit into memory simultaneously. In order to achieve interactive walkthroughs of such large building models, a system must store in memory and render only a small portion of the model in each frame; that is, the portion seen by the observer. As the observer "walks" through the model, some parts of the model become visible and others become invisible; some objects appear larger and others appear smaller. The challenge is to identify the relevant portions of the model, swap them into memory and render them at interactive frame rates as the observer's viewpoint is moved under user control.

We have developed data structures and algorithms for identifying a small portion of a large model to render and store in memory during each frame of an interactive walkthrough. Our algorithms rely upon an efficient display database that represents a building model as a set of objects, each of which can be described at multiple levels of detail. The database also contains an index of spatial cells with precomputed cell-to-cell and cell-to-object visibility information.

As the observer moves through the model during an interactive walkthrough, visibility information for the cell containing the observer is fetched from the display database and used by dynamic culling algorithms to identify a small superset of objects potentially visible to the observer. An optimization algorithm is used to select a level of detail and rendering algorithm with which to display each potentially visible object in order to meet a user-specified target frame time. Meanwhile, memory management algorithms are used to predict observer motion and to pre-fetch objects from disk that may become visible during upcoming future frames.

We have implemented an interactive building walkthrough system using these data structures and algorithms. During tests, this system is able to maintain over ten frames per second with little noticeable detail elision during interactive walkthroughs of a building model containing over one million polygons.

Advisor: Carlo H. Séquin

BibTeX citation:

@phdthesis{Funkhouser:CSD-93-771,
    Author = {Funkhouser, Thomas Allen},
    Title = {Database and Display Algorithms for Interactive Visualization of Architectural Models},
    School = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {Sep},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6297.html},
    Number = {UCB/CSD-93-771},
    Abstract = {This thesis describes a system for interactive walkthroughs of large, fully furnished architectural models. <p>Realistic-looking architectural models with furniture may consist of millions of polygons and require gigabytes of data -- far more than today's workstations can render at interactive frame rates or fit into memory simultaneously. In order to achieve interactive walkthroughs of such large building models, a system must store in memory and render only a small portion of the model in each frame; that is, the portion seen by the observer. As the observer "walks" through the model, some parts of the model become visible and others become invisible; some objects appear larger and others appear smaller. The challenge is to identify the relevant portions of the model, swap them into memory and render them at interactive frame rates as the observer's viewpoint is moved under user control. <p>We have developed data structures and algorithms for identifying a small portion of a large model to render and store in memory during each frame of an interactive walkthrough. Our algorithms rely upon an efficient display database that represents a building model as a set of objects, each of which can be described at multiple levels of detail. The database also contains an index of spatial cells with precomputed cell-to-cell and cell-to-object visibility information. <p>As the observer moves through the model during an interactive walkthrough, visibility information for the cell containing the observer is fetched from the display database and used by dynamic culling algorithms to identify a small superset of objects potentially visible to the observer. An optimization algorithm is used to select a level of detail and rendering algorithm with which to display each potentially visible object in order to meet a user-specified target frame time. Meanwhile, memory management algorithms are used to predict observer motion and to pre-fetch objects from disk that may become visible during upcoming future frames. <p>We have implemented an interactive building walkthrough system using these data structures and algorithms. During tests, this system is able to maintain over ten frames per second with little noticeable detail elision during interactive walkthroughs of a building model containing over one million polygons.}
}

EndNote citation:

%0 Thesis
%A Funkhouser, Thomas Allen
%T Database and Display Algorithms for Interactive Visualization of Architectural Models
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/CSD-93-771
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6297.html
%F Funkhouser:CSD-93-771