Paulo W. C. Maciel’ Peter Shirley+ Abstract A visual navigation system is described which uses texture mapped primitives to represent clusters of objects to main- tain high and approximately constant frame rates. In cases where there are more unoccluded primitives inside the view- ing frustum than can be drawn in real-time on the worksta- tion, this system ensures that each visible object, or a cluster that includes it, is drawn in each frame. The system sup- ports the we of traditional “level-of-detail” representations for individual objects, and supports the automatic genera- tion of a certain type of level-of-detail for objects and clusters of objects. The concept of choosing a representation from among those associated with an object that accounts for the direction from which the object is viewed is also supported. The level-of-detail concept is extended to the whole model and the entire scene is stored as a hierarchy of levels-of-detail that is traversed top-down to iind a good representation for a given viewpoint. This system does not assume that vis- ibility information can be extracted from the model and is thus especially suited for outdoor environments. 1 Introduction This paper describes a new approach to the “walkthrough” problem, where a viewer interactively moves through a static scene database at high and approximately constant hame rates. Traditional approaches to this problem use a hardware graphics pipeline and attempt to minimize the number of polygons sent to the system. This minimization is achieved both by culling the entire model or the part of it that is potentially visible in the next few frames against the view- ing frustum and using geometrically coarse representations (levels of detail, or LODs) of individual objects. The approach described in this paper attempts to extend the domain of traditional approaches by assuming that sets of potentially visible objects cannot easily be computed and at any given frame the visible scene can contain more graph- ics primitives than state-of-the-art hardware can render in real-time even if the lowest detail LODs are used for every object. The basic strategy underlying the system described in this paper is the use of impostors. An impostor is an entity that is faster to draw than the true object, but retains the important Visual Navigation of Large Environments Using Textured Clusters visual characteristics of the true object. Traditional LODs are a particular application of impostors. The key issue is how to decide which impostors to ren- der to maximize the quality of the displayed image without exceeding the available user-specified frame time. The best approach so far to solve this problem attempts to predict the complexity of the scene at the current frame and selects impostors accordingly and is described by Funkhouser and Sequin [3]. The system described in this paper can be viewed as au extension of Funkhouser and Sequin’s system with the fol- lowing new properties: l The entire database is a single hierarchy which con- tains drawable impostors (including LODs) for objects as well as clusters of objects. This is a global general- ization of the LOD concept to the entire model. l The system uses the graphics hardware to automat- ically create this hierarchy, generate impostors, com- pute their rendering cost, and compute a static portion of their benefit according to the direction from which they are viewed. In Section 2 we revisit the work done by Funkhouser and Sequin, briefly presenting the main components of their sys- tem and showing why it doesn’t scale well to arbitrary envi- ronments. In Section 3 we discuss how to extend the benefit concept to account for cluster primitives and view-dependent LODs. In Section 4 we show how the representation selection process can be formulated as au N-P-complete tree traversal problem, and present a heuristic solution that generates a complete, if non-optimal, representation of the model for display. In Section 5 we discuss our implementation. Fi- nally, we discuss the limitations of the system in Section 6 and the conclusions in Section 7. 2 Predictive Approach Revisited The predictive approach described by Funkhouser and Se- quin assume8 that the system runs on a machine in which the rendering cost of each object in the model can be es- timated. This rendering cost is estimated by empirically obtaining performance parameters of the machine and using these parameters in a simple formula. *Department of Computer Science, Lindley Hall, Indiana Uni- versity, Bloomington, Indiana, pmacielQca.indiana.edu t Program of Computer Graphics, Cornell University, Ithaca, New York, shirleyOgraphics.cornell.edu Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication andks date appear; and notice is given that copying is by permission of the Assocration of Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 1995 Symposium on Interactive 3D Graphics, Monterey CA USA 0 1995 ACM O-89791 -736-7/95/0004...$3.50 Since effective walkthrough systems need to achieve a bal- ance between interactivity and visual quality, they use a ben- efit heuristic to decide the amount of contribution to the overall scene caused by rendering an object with a particu- lar accuracy. This heuristic takes into consideration factors associated to a representation of the object such as image- space size of object, focus, speed relative to view point, se- mantics, accuracy of a LOD, and hysteresis with respect to switching between different LODs. Objects are