internetworks.
`
`IP broadcast, which is commonly used in DIS environments,
`cannot be used over'the Internet unless it is encapsulated. It also
`adds an additional burden because itrequires that all nodes examine
`a packet even if the information is not intended for that receiving
`host, incurring a major performance penalty for that host because it
`must interrupt operations in order to perfonn this task at the operat-
`ing system level.
`Point-to-point communication requires the establishment of a
`connection or path from each node to every other node in the net-
`work for a total of N*(N-1) virtual connections in a group. For ex-
`ample, with a 1000 member group each individual host would have
`to separately address and send 999 identical packets. If a client-
`server model is used, such as that typically found in networked
`games and multi-user domains (MUDs), the server manages all the
`connections and rapidly becomes an input,/output bottleneck.
`
`Dead-reckoning
`
`The networking technique used in NPSNET~IV, evolved from
`SIMNET, and embodied in DIS follows theplayers and ghosts par-
`adigm presented in [1][7]. In this paradigm, each object is con-
`trolled on its own host workstation by a software object called a
`Player. On every other workstation in the network. a version of the
`Player is dynamically modeled as an object called a Ghost.
`The Ghost objects on each workstation update their own posi-
`tion each time through the simulation loop, using a dead-reckoning
`algorithm. The Player tracks both its actual position and the predict-
`ed position calculated with dead-reckoning. An updated Entity
`State Protocol Data Unit is sent out on the network when the two
`postures differ by a predetermined error threshold, or when a fixed
`amount or time has passed since the last update (nominally 5 sec-
`onds). When the updated posture (location and orientation) and ve-
`locity vectors are received by the Ghost object, the Ghost’s is cor-
`rected to the updated values, and resumes dead-reckoning from this
`new posture.
`
`This dead-reckoning technique helps in overcoming a major
`problem found in a number of networked simulations -- excessive
`network utilization. For example, each networked participant play-
`ing the popular game DOOM generates a packet on every graphics
`frame. On an SGI, this translates into 30 packets per second, even
`when an entity is inactive. This not only wastes bandwidth, it also
`overloads the ability of network devices to process packets. On the
`other hand, a high performance aircraft in a DIS environment typi-
`cally produces about 8 packets per second --a dramatic difference.
`
`MB ONE
`
`MBONE is a virtual network that originated from an effort to
`multicast audio and video from the Internet Engineering Task Force
`(IETF) meetings [2]. MBONE today is used by several hundred re-
`searchers for developing protocols and applications for group com-
`munication.
`
`We have used MBONE to demonstrate the feasibility of IP
`Multicast for distributed simulations over a wide area network. In
`the past, participation with other sites required prior coordination
`for reserving bandwidth on the Defense Simulations Internet (DSI).
`DSI, funded by ARPA, is a private line network composed of T-1
`(1.5 Mbps) links, BBN switches and gateways using the ST-II net-
`work protocol. It had been necessary to use DSI because ARPA
`sponsored DIS simulations use IP broadcast - requi.ring a unique
`wide-area bridged network.
`With the inclusion of D3 Multicast in NPSNET-IV, sites con-
`nected viathe MBONE can immediately participate in a simulation.
`MBONE uses a tool developed by Van Jacobson and Steven Mc-
`
`Canne called the Session Directory (SD) to display the advertise-
`ments by multicast groups. SD is also used for launching multicast
`applications like NPSNET-IV and for automatically selecting an
`unused address for a new group session. Furthermore, we can inte-
`grate other multicast services such as video with NPSNET-IV. For
`example, participants are able to view each other’s simulation with
`a video tool, NV, developed by Ron Fredrickson at Xerox Parc [5].
`
`Acknowledgments
`
`We wish to express our thanks to the Air Force Institute of
`Technology, George Mason University, the Naval Research Labs
`and all those who participated in the demonstrations of NPSNET-
`IV.
`
`This work would not have been possible without the support of
`our research sponsors: USA ARL, DMSO, USA STRICOM, USA
`HQDA AI Center-Pentagon, USA TRAC, ARPA.
`
`Resources
`
`Many of the references noted below are available via the NPS-
`NET Research Group’s WW'Whome page:
`
`file://taurus.cs.nps.navy.mil/pub/NPSNET_MOSAIC,"
`npsnet_mosaic.html
`
`References
`
`1.Blau, Brian, Hughes, Charles E., Moshell, J. Michael and Lisle,
`Curtis “Networked Virtual Environments,” Computer Graphics,
`1992 Symposium on Interactive 3D Graphics (March 1992),
`pp.157.
`
`2.Casner, Steve. “Frequently Asked Questions on the Multicast
`Backbone". (6 May 1993). Available at venrera.isi.edu:,/rnboneg’
`faq.txt.
`
`3.Deering, Stephen. Host Extensions for IP Multicasting. RFC
`1112. (August 1989).
`
`4.Institute of Electrical and Electronics Engineers, International
`Standard, ANSUIEEE Std 1278-1993, Standard for Information
`Technology, Protocols for Distributed Interactive Simulation,
`(March 1993).
`
`5.Macedonia, Michael R. and Donald P. Brutzman. “MBone Pro-
`vides Audio and Video Across the Internet”. In IEEE Computer.
`(April 1994). pp. 30-36.
`
`6.Pope, Arthur, BBN Report No. 7102, “The SIMNET Network
`and Protocols", BBN Systems and Technologies, Cambridge. Mas-
`sachusetts, (July 1939).
`
`7.Pratt, David R. “A Software Architecture for the Construction
`and Management of Real Time Virtual Environments”. Disserta-
`tion, Naval Postgraduate School, Monterey, California (June 1993).
`
`8.Zyda, Michael J., Pratt, David R., John S. Falby, Chuck Lombar-
`do, Kelleher, Kristen M. “The Software Required for the Computer
`Generation of Virtual Environments”. In Presence. 2, 2. (Spring
`1993). pp. 130-140.
`
`BUNGIE - EXHIBIT 1006 - PART 7 OF 14
` ‘
`
`94
`
`BUNGIE - EXHIBIT 1006 - PART 7 OF 14
`
`

`
`Visual Navigation of Large Environments Using Textured Clusters
`
`Paulo W. C. Ma.ciel*
`
`Peter Shirleyl
`
`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 use 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 find 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 frame
`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 irnpostor is an entity that is
`faster to draw than the true object, but retains the important
`
`‘Department of Computer Science, Lindley Hall, Indiana Uni-
`versity, Bloomington, Indiana, pmaciel@m.indiana.edu
`lProgra.m of Computer Graphics, Cornell University, Ithaca,
`New York, shirley@graphics.cornei1.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 01 the publication and its date appear, and notice is given
`that copying is by permission ol the Association 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
`© 1995 ACM D-89791 -736-7/95/00O4...$3.50
`
`visuai 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
`The system described in this paper can be viewed as an
`extension of Funlchouser and Sequin’s system with the fol-
`lowing new properties:
`
`a 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.
`
`a 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 an NP-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 Eunkhouser and Se-
`quin assumes 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.
`Since effective walkthrough systems need to achieve a bal-
`ance between interactivity and visual quality, they use a hen-
`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-
`spade size of object, focus, speed relative to view point, se-
`rrrantics, accuracy of a LOD, and hysteresis with respect to
`switching between different LODs.
`Objects are selected to render using an incremental opti-
`mization algorithm that prioritizes the selection of objects
`with high benefit/cost value to render until the user-specified
`
`95
`
`

`
`
`
`
`
`
`
`__,,____,,_,-,...._.,_,._..,..,,,,..._,,...,,_._-.._........,c_.,...._.._._..-..._..————-—-—-———-.--—----.-uqgi
`
`
`
`
`
`
`
`
`
`
`
`Figure 1: Three representations for a house. The left two
`are view independent LODs while the right one is a view
`dependent texture map.
`
`frame time is reached. The result is that low-valued visible
`objects may not be displayed.
`In environments where too
`many visible primitives are present at a given point in the
`simulation, this can result in large “blank” spots on the scene
`which would cause a distracting effect.
`To reduce the number of primitives rendered at each
`frame, visibility information from a pre-processing phase is
`used to cull objects that are certainly blocked from view by
`partitions. This approach works well for models that can be
`subdivided into cells containing open spaces (such as doors
`and windows) through which visibility can be determined.
`In an outdoor environment such cells and portals are not
`easily identifiable making the pre-processing of such an en-
`vironment to extract visibility a hard problem.
`Our system is also a predictive system and assumes that it
`will nm on a multiprocessor machine with texture mapping
`capability. We allow for situations where more unoccluded
`primitives can occur inside the viewing frustum than can be
`rendered in real-time and do not assume that visibility infor-
`mation can be extracted from the model. This last feature,
`makes the system suitable for navigation of large outdoor
`environments.
`
`3 Benefit Calculation
`
`representations
`Visual navigation systems use different
`(LODs) of an object to improve the performance of the sim-
`ulation. As explained in the previous section, each LOD
`makes a contribution to the quality of the simulation that
`can be estimated by a benefit heuristic.
`In computing these benefits we face two interesting issues:
`how to compute the benefit of individual representations of
`objects taking into account their view angle dependent na-
`ture (e.g. a roadside billboard has a low benefit when seen
`from the side), and how a. group of objects is perceived (its
`“semantics" ).
`
`3.1 Benefit of Objects
`
`In our approach, an object can have associated with it not
`only the conventional LODs but also any other drawable rep-
`resentation that resembles the object from given viewpoints.
`Consider the possible representations we can use to render
`a house as in Figure 1. In this picture, the first (leftmost)
`of these representations is the house object at full detail,
`the second is a low LOD representation and the third is just
`a single polygon with a texture map representation of the
`front of the house.
`
`We classify the third representation as view dependent and
`the first two as view independent meaning that the view de-
`pendent would only be considered for a subset of all possible
`viewing directions, while the view independent LODs would
`be considered for all viewing angles.
`
`96
`
`We have divided the contribution to the simulation of ren-
`dering a given representation associated with an object in
`two parts. One that is intrinsic to the object, the object's
`benefit, and one that is intrinsic to a representation of the
`object, the accuracy with which it represents the full detail
`object.
`~
`Intrinsic to an object are factors such as its image-space
`size (since large objects on the screen seem to contribute
`more than smaller ones), its distance to the line of sight
`(since assuming that the eye is looking to the center of the
`screen, objects near the center of view are better resolved
`by our visual system than objects in the periphery of view),
`relative speed of the object to the viewpoint, and semantics
`(role of the object in the simulation). Our per-object benefit
`is computed as a weighted average of all these factors and it
`is used to guide the selection of representations to render in
`Section 4. The weights are empirically determined and can
`be changed for each run of the simulation.
`Intrinsic to a representation of an object is its accuracy
`with respect to the full detail object, that is, how similar a
`given representation is to the actual object for a particular
`view angle.
`Note that while the benefit of an object (except for its
`semantic) can only be detennined in real-time and therefore
`is inherently dynamic, the accuracy of a representation is
`inherently static and can be determined prior to the walk-
`through of the model, as described in Section 3.2.
`
`3.2 View Angle Dependent Benefit Calculation
`
`Consider again the house representations in Figure 1. The
`left most of these representations should have the highest
`benefit regardless of view angle but we might not want to
`render it since it is also the most expensive to render. The
`benefit that should be assigned to the other two will depend
`upon the user‘s view angle (for the texture maps) and view
`distance (for the low LOD).
`A way of incorporating view dependency information into
`the benefit heuristic is to measure the accuracy of each of the
`object’s representations according to each viewing direction
`possible.
`Since the space of possible viewpoints and viewing direc-
`tions is infinite, we approximate it by discretizing this space
`into a finite set of viewing directions, and assuming that
`the view distance is infinite (we use an orthographic pro-
`jection). This seems reasonable because we do not expect
`to use coare LODs when the view distance is small. To
`tabulate directional benefits, we sample the hemisphere of
`directions (Figure 2) and calculate an image of the object
`and impostor at each sample point.
`The number and location of these samples will depend on
`the number of representations that the object has and the
`possible viewpoints during the walkthrough. For instance, in
`the case of the 2D house impostor in Figure 1, we will never
`use it unless we are roughly in front of the house, so only
`directions around the line perpendicular to the 2D image are
`sampled.
`We sample each of the viewing directions and measure
`the accuracy of each representation and construct a table
`that has one entry for each pair (representation, viewing di-
`rection). Each of these entries contains a similarity value
`(accuracy) of the representation measured with respect to
`the full detail object for the particular viewing direction.
`During the walkthrough, the accuracy of a given representa-
`tion and viewing direction can be obtained by accessing this
`table.
`
`

`
`
`
`Figure 2: Discretizing the space of viewpoints around an
`object. Replication accuracies are shown at three of the
`view angles. The low LOD house looks the “best” from the
`top.
`
`Ideally the accuracy of an image with respect to the ideal
`image should be obtained by a perceptual comparison of the
`two images but since we are in search of automatic ways to
`determine similarity we resort to computational techniques.
`In our implementation we use simple image processing tech-
`niques to get this similarity value.
`We avoid a simple pixel-by-pixel comparison of the two
`images, since slight differences on the impostor's image
`would cause two very similar images to have a similarity
`close to zero. Because the achromatic channel of vision is the
`most important for shape recognition, we start by obtaining
`a gray scale version of the two images by simply averaging
`the rgb components at each pixel. Since edges are features
`on an image that are readily identified by the human visual
`system, an edge operator is applied to the images. The im-
`ages are convolved with a 5x5 Laplacian operator and its
`zero crossings are computed. A subsequent blurring step in-
`creases the chances of matching of the two images, which we
`then compare pixel-by-pixel.
`This image comparison method is far too simple to mimic
`human image processing, but does serve as a placeholder in
`our system that can be replaced later with a module that
`performs better by using segmentation and high level pro-
`cessing.
`
`3.3 Benefit of Clusters
`
`This section is meant to highlight that much more research
`needs to be done on how benefit heuristics can draw on per-
`ceptual behavior. We argue that a per-object benefit heuris-
`tic does not address how humans perceive a. collection of ob-
`jects when seen as a whole. Briefly, if two objects or and ,5
`are represented by an impostor -y and have benefits Ba and
`B3 what should the benefit B7 of 7 be?. 3, is not simply
`the sum of B0, and B5 since as and ,6 when viewed as a group
`might give a different contribution (meaning) to the simula-
`tion then the objects alone would, that is, the benefit of all
`the objects in a scene does not translate into a perceptual
`measure for the entire scene.
`A practical example would be to consider a walkthrough
`of a battle field containing many soldiers and guns. In this
`situation the benefit of a gun and a soldier do not add up
`to form the benefit of a soldier holding a gun, particularly if
`the soldier is pointing the gun toward the user of the system.
`Therefore we conclude that to determine the benefit of an
`
`object in some cases is undecidable without knowing what
`surrounds it. As pointed out by Gestalt Psychologists [7],
`
`the meaning conveyed by an object may be more than merely
`the “addition” of the meanings conveyed by each one of the
`objects alone, that is, the whole conveys more information
`then the sum of its parts.
`While realizing that it is extremely difficult to account
`for how objects interact in a scene we still use a per-object
`benefit heuristic knowing that it may not be suitable for
`some groupings of objects.
`
`4 Navigation System Design
`
`The ultimate goal of this work is to design a visual navigation
`system that is able to keep a. user-specified uniform frame
`rate when displaying a large environment.
`We begin by presenting a general framework for visual
`navigation systems. We then formalize the navigation prob-
`lem as an NP-complete tree traversal problem and explain
`in detail the design of our system.
`
`4.1
`
`Framework for Visual Navigation Systems
`
`In many cases, conventional LODs are either not readily
`available, are expensive, or are time consuming to generate.
`Since these LODs are simply representations of the “true"
`objects they do not necessarily need to be versions of the
`same object with fewer geometric primitives (or drawn with
`a less accurate rendering algorithm such as flat shading in-
`stead of Gouraud shading) but rather representations that
`can be drawn on the computer screen in less time than the
`true object and provide the simulation with a feel similar to
`that obtained by using the full detail object.
`With this in mind, our design allows an object to be as-
`sociated to many different representations that resembles it,
`possibly from different view angles.
`
`4.1.1 Object-Oriented Design
`
`The main abstraction for a single object, is the “conceptual
`object” abstraction.
`It corresponds to any object in the
`model that has a well defined meaning in the simulation,
`such as, a car or a building. Associated with the conceptual
`object is a set of “drawable representations”, which have
`characteristics similar to the actual object it represents.
`The “d.ra.wable representation” abstraction represents a.
`variety of hardware drawable representation or impostors for
`a given conceptual object. The abstractions for drawables
`encapsulate hardware defined primitives such as meshes of
`triangles, splines, list of polygons, etc., as well as the impos-
`tor representations presented in Section 4.1.2. This encap-
`sulation of both hardware primitives and impostors allows
`the design of very efficient rendering routines that extract
`the most performance of the graphics subsystem. Other im-
`postor abstractions may be added to this design as deemed
`necessary to solve a particular problem or to add a particular
`feature to the walk-through program.
`The conceptual object’s interface is defined by virtual
`functions to compute the object’s benefit, visibility, and a
`“draw” function that is redefined for each specific drawable
`representation. The drawable representa.tion’s interface is
`defined by functions to compute the drawable’s rendering
`cost, ‘accuracy, and by customized “draw" functions.
`
`4.1.2
`
`‘Types of Impostors
`
`As mentioned in Section 3.1, we allow an object to be rep-
`resented by both view dependent and view independent im-
`
`97
`
`

`
`postors.
`Examples of view dependent impostors are:
`
`0 A texture map that is pasted onto the appropriate face
`of an object's bounding box. This texture map is called
`a textured cluster when it corresponds to an image of
`a group of objects.
`
`a Another view dependent texture map is also known as
`billboard in [6} and is obtained in the same way as tex-
`ture maps. A billboard is centered at an object’s center
`and made to rotate in such a way that it always face
`the observer. Since one billboard is computed for each
`face of the object's bounding box as the observer moves
`around the object a different billboard is selected to dis-
`play according to the viewpoint. This impostor is useful
`to represent objects that are approximately rotationally
`symmetric such as pine trees.
`
`0 Another variant of the texture map described above is
`a pseudo-texture rnapl. A pseudo-texture map is a tri-
`angular mesh (or a quadrilateral strip) onto which a.
`texture map is pasted in such a way that each pixel in
`the image is associated to a. pair of triangles (or quadri-
`lateral) in the mesh.
`
`Examples of view independent
`
`impostors are:
`
`
`
`‘Ewen!
`
`Figure 3: Possible viewpoint regions in object coordinates.
`
`2. During the walkthrough we determine the viewpoint
`with respect
`to the object’s coordinate system and
`therefore the region it is in.
`
`In some situations, both a view dependent and a view
`independent representation are suitable. When this is the
`case, we can decide upon these two representations by ob-
`taining the accuracy of each representation for the particular
`observer view angle using the table described in Section 3.2
`and then select the representation with the highest accu-
`racy/cost ratio. This heuristic is particularly useful in cases
`where the observer's line of sight is approaching a 45 degree
`angle with the line perpendicular to the texture map.
`In
`such a case although the texture map may have a low ren-
`dering cost, its accuracy will also have a low value which will
`favor the selection of 3. possibly more costly view dependent
`representation.
`
`levels-of-detail,
`e The conventional
`coarse versions of a given object“.
`
`i.e., geometrically
`
`4.3 Formalization of the Problem
`
`o Boxes whose faces have the average areas and colors as
`the corresponding sides of the objects bounding box.
`
`a Texture mapped boxes. This representation uses tex-
`ture maps that are pasted onto each face of the object’s
`bounding box and is useful to represent box like objects
`such as the Standard Oil Building in Chicago.
`
`4.2
`
`Impostor Selection
`
`There are certain cases where specific impostors are more
`suitable than others and we can usually “suggest” to the
`walkthrough program which representation to display at a
`given point in the simulation.
`For example,
`if the image-space size N of an object is
`less then a. few pixels then the representation that should
`be used is the average box above.
`If N is greater then a
`pre-fixed maximum size then the full detail object might be
`required. If different LODs are present in the model, then
`difl’erent image space size thresholds may be used to select
`the appropriate LOD to be displayed.
`Box-like and symmetric objects can be displayed using a
`texture mapped box and a billboard, respectively. Texture
`maps can be selected according to the obeserver‘s viewpoint.
`Fbr example, if four texture maps are used for each face of
`an object’s bounding box, then the appropriate texture map
`for a given viewpoint can be selected as follows:
`
`1. In a pre-processing phase, associate to each texture map
`a number corresponding to the region it belongs as in
`Figure 3.
`
`1 It can be used in machines that do not have texture mapping
`hardware.
`
`“Some toolkits such as Performer[6] provide routines to auto.
`matically generate coarse versions of a given full-detail object.
`
`We begin by defining a meta—object abstraction to be an en-
`tity with one or more hardware drawable representations as
`in the framework described in Section 4.1. It is an abstrac-
`tion for both conceptual objects and groups of objects.
`As before, a hardware drawable representation is an entity
`that can be rendered by the graphics hardware to represent
`objects and has associated to it a. rendering cost and a. mea-
`sure of its “contribution" to the simulation.
`The model is then defined as a. collection of conceptual
`objects at specific positions and orientations in space that
`forms the environment in which the user navigates.
`The model hierarchy is defined to be a tree structure
`whose nodes are meta-objects that provide multiple repre-
`sentations of the model, each representing it at a given ren-
`dering time and providing the user with a given perception
`of it.
`In this hierarchy each node contains drawable rep-
`resentations of its children. The root contains the coarsest
`representations for the entire model with the lowest possible
`rendering cost while the leaves form the perceptually best
`representation of the model with the highest rendering cost.
`More formally, the model hierarchy M is a. tree structure
`that can recursively be defined by the following rules:
`
`1. A meta-object that has no children is a. model hierarchy
`with just one node, the root node.
`
`'
`
`r
`
`2. Let M1, Mg...M.. be model hierarchies whose root nodes
`are the meta-objects m1,m.2...m.., respectively, that
`represent sets of conceptual objects and have associ-
`ated with each of them the sets r1,r2...1',. of drawable
`representations. Let m be a. meta-object that repre-
`sents the union of m.- and has associated to it a set 1-
`of drawable representations such that C'ost(Mar(r)) <
`L, Cost(Min(r.-)), where Maa:(r) is the representa-
`tion that has the highest cost among those in 1-, Min(r.-)
`is the representation that has the lowest cost among
`
`98
`
`

`
`those in r.- and Cost(:c) is the rendering cost of repre-
`sentation :r. M is then defined to be a model hierarchy
`ifrnistheparentofm;fori=1...n.
`
`Figure A shows how the model of a city would be orga-
`nized to form a hierarchy in which each node has a set of
`impostors to represent the objects it subsumes.
`Given these definitions, we state the walk-through prob-
`lem as a tree traversal problem:
`
`“Select a set of nodes in the model hierarchy that pro-
`vides the user with a perceptually good representation of
`the model”, according to the following constraints:
`
`1. The sum of the rendering cost of all selected nodes is
`less than the user specified frame time.
`
`2. Only one node can be selected for each path from the
`root node to a leaf node, since each node already con-
`tains drawable representations that represent all its de-
`soendant nodes.
`
`The problem as described here is an NP-complete tree
`traversal problem and is a variant of the “Knapsack prob-
`lem”, which is not surprising since we are generalizing the
`system that Funlchouser and Sequin showed to be a knapsack
`problem. The candidate sets from which only one element
`will be selected to be put in the knapsack are the set of rep-
`resentations associated to each meta—object. The knapsack
`size is the frame time per frame that the selected represen-
`tations must not exceed. The cost of each element is the
`rendering cost associated to a representation. The profit of
`an element is the accuracy of the representation plus the
`benefit of the object with which it is associated.
`To solve this problem we use the framework described in
`Section 4.1 and develop a model hierarchy building algo-
`rithm and a heuristic representation selection algorithm.
`
`4.4 Design of the Model Hierarchy
`
`We partition the entire model according to our formalization
`of the problem, and form a tree structure in which each node
`contains low-cost representations for the nodes it subsumes.
`The structure that we use is a variation of an octree that
`is a. bounding volume hierarchy, that can be used to cull
`objects against the viewing frusturn and also serves as a
`rendering aid, since we can draw its nodes.
`This tree is constructed in a bottom-up fashion instead of
`the traditional top-down recursive way, so that we can see
`which objects are being “clustered” together as described
`in Section 5.
`The criteria used to group objects takes into account only
`the pro:-dmity of objects and our model hierarchy building
`program is designed to cluster together nearby objects first
`in the way illustrated in the 2D example of Figure 4.
`According to a user-supplied number of divisions in x, y,
`and z axis of the bounding box of the entire model an initial
`octree cell size and therefore tree depth is specified. We start
`by creating a “child l