View-Dependent Refinement of Progressive Meshes
Hugues Hoppe
Microsoft Research
ABSTRACT
Level-of-detail (LOD) representations are an important tool for real-time rendering of complex geometric environments. The previously introduced progressive mesh representation defines for an arbitrary triangle mesh a sequence of approximating meshes optimized for view-independent LOD. In this paper, we introduce a framework for selectively refining an arbitrary progressive mesh according to changing view parameters. We define efficient refinement criteria based on the view frustum, surface orientation, and screen-space geometric error, and develop a real-time algorithmfor incrementally refining and coarsening the mesh according to these criteria. The algorithm exploits view coherence, supports frame rate regulation, and is found to require less than 15% of total frame time on a graphics workstation. Moreover, for continuous motions this work
can be amortized over consecutive frames. In addition, smooth visual transitions (geomorphs) can be constructed between any two selectively refined meshes.
A number of previous schemes create view-dependent LOD meshes for height fields (e.g. terrains) and parametric surfaces (e.g.NURBS). Our framework also performs well for these special cases.
Notably, the absence of a rigid subdivision structure allows more accurate approximations than with existing schemes. We include results for these cases as well as for general meshes. CR Categories: I.3.3 [Computer Graphics]: Picture/Image Generation -Display
algorithms; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling - surfaces and object representations. Additional Keywords: mesh simplification, level-of-detail, multiresolution representations, dynamic tessellation, shape interpolation.
1 INTRODUCTION
Rendering complex geometric models at interactive rates is a chal-lenging problem in computer graphics. While rendering perfor-mance is continually improving, significant gains are obtained by adapting the complexity of a model to its contribution to the ren-dered
image. The ideal solution would be to efficiently determine the coarsest model that satisfies some perceptual image qualities. One common heuristic technique is to author several versions of a model at various levels of detail (LOD); a detailed triangle mesh is used when the object is close to the viewer, and coarser approx-imations are substituted as the object recedes [4, 8]. Such LOD meshes can be computed automatically using mesh simplification
Email: hhoppe@microsoft.com
Web: http://research.microsoft.com/˘hoppe/
techniques (e.g. [5, 10, 19, 21]). The recently introduced progres-sive mesh (PM) representation [10] captures a continuous sequence of meshes optimized for view-independent LODcontrol, and allows fast traversal of the sequence at runtime.
Sets or sequences of view-independent LOD meshes are appro-priate for many applications, but difficulties arise when rendering large-scale models, such as environments, that may surround the viewer:
Many faces of the model may lie outside the view frustum and thus do not contribute to the image (Figure 12a). While these faces are typically culled early in the rendering pipeline, this processing incurs a cost.
Similarly, it is often unnecessary to render faces oriented away from the viewer, and such faces are usually culled using a “back-facing” test, but again at a cost.
Within the view frustum, some regions of the model may lie much closer to the viewer than others. View-independent LOD meshes fail to provide the appropriate level of detail over the entire model (e.g. as does the mesh in Figure 12b). Some of these problems can be addressed by representing a graph-icsscene as a hierarchy of meshes. Parts of the scene outside the view frustum can then be removed efficiently using hierarchical culling, and LOD can be adjusted independently for each mesh in the hierarchy [4, 8]. However, establishing such hierarchies on con-tinuous surfaces is a challenging problem. For instance, if a terrain mesh (Figure 11d) is partitioned into blocks, and these blocks are
rendered at different levels of detail, one has to address the problem of cracks between the blocks [14]. In addition, the block boundaries are unlikely to correspond to natural features in the surface, result-ing in suboptimal approximations. Similar problems also arise in
the adaptive tessellation of smooth parametric surfaces [1, 13, 18].Specialized schemes have been presented to adaptively refine meshes for the cases of height fields and parametric surfaces, as summarized in Section 2.1. In this paper, we offer a general runtime LOD framework for selectively refining arbitrary meshes according
to changing view parameters. A similar approach was developed in-dependently
by Xia and Varshney [24]; their scheme is summarized and compared in Section 2.3.
The principal contributions of this paper are:
It presents a framework for real-time selective refinement of arbitrary progressive meshes (Section 3).
It defines fast view-dependent refinement criteria involving the view frustum, surface orientation, and screen-space projected error (Section 4).
It presents an efficient algorithm for incrementally adapting the mesh refinement based on these criteria (Section 5). The algo-rithm exploits view coherence, supports frame rate regulation,and may be amortized over consecutive frames. To reduce pop-ping, geomorphs can be constructed between any two selectively refined meshes.
