Survey of semi-regular multiresolution models for interactive terrain rendering
---
paper_title: Multiresolution models for topographic surface description

paper_content:

Multiresolution terrain models describe a topographic surface at various levels of resolution. Besides providing a data compression mechanism for dense topographic data, such models enable us to analyze and visualize surfaces at a variable resolution. This paper provides a critical survey of multiresolution terrain models. Formal definitions of hierarchical and pyramidal models are presented. Multiresolution models proposed in the literature (namely, surface quadtree, restricted quadtree, quaternary triangulation, ternary triangulation, adaptive hierarchical triangulation, hierarchical Delaunay triangulation, and Delaunay pyramid) are described and discussed within such frameworks. Construction algorithms for all such models are given, together with an analysis of their time and space complexities.
---
paper_title: Multiresolution Modeling: Survey and Future Opportunities

paper_content:

For twenty years, it has been clear that many datasets are excessively complex for applications such as real-time display, and that techniques for controlling the level of detail of models are crucial. More recently, there has been considerable interest in techniques for the automatic simplification of highly detailed polygonal models into faithful approximations using fewer polygons. Several effective techniques for the automatic simplification of polygonal models have been developed in recent years. This report begins with a survey of the most notable available algorithms. Iterative edge contraction algorithms are of particular interest because they induce a certain hierarchical structure on the surface. An overview of this hierarchical structure is presented,including a formulation relating it to minimum spanning tree construction algorithms. Finally, we will consider the most significant directions in which existing simplification methods can be improved, and a summary of other potential applications for the hierarchies resulting from simplification.
---
paper_title: Level of Detail for 3D Graphics

paper_content:

From the Publisher: ::: Level of detail (LOD) techniques are increasingly used by professional real-time developers to strike the balance between breathtaking virtual worlds and smooth, flowing animation. Level of Detail for 3D Graphics brings together, for the first time, the mechanisms, principles, practices, and theory needed by every graphics developer seeking to apply LOD methods. ::: Continuing advances in level of detail management have brought this powerful technology to the forefront of 3D graphics optimization research. This book, written by the very researchers and developers who have built LOD technology, is both a state-of-the-art chronicle of LOD advances and a practical sourcebook, which will enable graphics developers from all disciplines to apply these formidable techniques to their own work. ::: Features ::: Is a complete, practical resource for programmers wishing to incorporate LOD technology into their own systems. Is an important reference for professionals in game development, computer animation, information visualization, real-time graphics and simulation, data capture and preview, CAD display, and virtual worlds. Is accessible to anyone familiar with the essentials of computer science and interactive computer graphics. Covers the full range of LOD methods from mesh simplification to error metrics, as well as advanced issues of human perception, temporal detail, and visual fidelity measurement. Includes an accompanying Web site rich in supplementary material including source code, tools, 3D models, public domain software, documentation, LOD updates, and more. ::: ::: Author Biography:David Luebke ::: David is an Assistant Professor in the Department of Computer Science at the University of Virginia. His principal research interest is the problem of rendering very complex scenes at interactive rates. His research focuses on software techniques such as polygonal simplification and occlusion culling to reduce the complexity of such scenes to manageable levels. Luebke's dissertation research, summarized in a SIGGRAPH '97 paper, introduced a dynamic, view-dependent approach to polygonal simplification for interactive rendering of extremely complex CAD models. He earned his Ph.D. at the University of North Carolina, and his Bachelors degree at the Colorado College. ::: Martin Reddy ::: Martin is a Senior Computer Scientist at SRI International where he works in the area of terrain visualization. This work involves the real-time display of massive terrain databases that are distributed over wide-area networks. His research interests include level of detail, visual perception, and computer graphics. His doctoral research involved the application of models of visual perception to real-time computer graphics systems, enabling the selection of level of detail based upon measures of human perception. He received his B.Sc. from the University of Strathclyde and his Ph.D. from the University of Edinburgh, UK. He is on the Board of Directors of the Web3D Consortium and chair of the GeoVRML Working Group. ::: Jonathan D. Cohen ::: Jon is an Assistant Professor in the Department of Computer Science at The Johns Hopkins University. He earned his Doctoral and Masters degrees from The University of North Carolina at Chapel Hill and earned his Bachelors degree from Duke University. His interests include polygonal simplification and other software acceleration techniques, parallel rendering architectures, collision detection, and high-quality interactive computer graphics. ::: Amitabh Varshney ::: Amitabh is an Associate Professor in the Department of Computer Science at the University of Maryland. His research interests lie in interactive computer graphics, scientific visualization, molecular graphics, and CAD. Varshney has worked on several aspects of level-of-detail simplifications including topology-preserving and topology-reducing simplifications, view-dependent simplifications, parallelization of simplification computation, as well as using triangle strips in multiresolution rendering. Varshney received his PhD and MS from the University of North Carolina at Chapel Hill in 1994 and 1991 respectively. He received his B. Tech. in Computer Science from the Indian Institute of Technology at Delhi in 1989. ::: Benjamin Watson ::: Ben is an Assistant Professor in Computer Science at Northwestern University. He earned his doctoral and Masters degrees at Georgia Tech's GVU Center, and his Bachelors degree at the University of California, Irvine. His dissertation focused on user performance effects of dynamic level of detail management. His other research interests include object simplification, medical applications of virtual reality, and 3D user interfaces. ::: Robert Huebner ::: Robert is the Director of Technology at Nihilistic Software, an independent development studio located in Marin County, California. Prior to co-founding Nihilistic, Robert has worked on a number of successful game titles including "Jedi Knight: Dark Forces 2" for LucasArts Entertainment, "Descent" for Parallax Software, and "Starcraft" for Blizzard Entertainment. Nihilistic's first title, "Vampire The Masquerade: Redemption" was released for the PC in 2000 and sold over 500,000 copies worldwide. Nihilistic's second project will be released in the Winter of 2002 on next-generation game consoles. Robert has spoken on game technology topics at SIGGRAPH, the Game Developer's Conference (GDC), and Electronic Entertainment Expo (E3). He also serves on the advisory board for the Game Developer's Conference and the International Game Developer's Association (IGDA). Robert's e-mail address is .
---
paper_title: A Developer's Survey of Polygonal Simplification Algorithms

paper_content:

Polygonal models currently dominate interactive computer graphics. This is chiefly because of their mathematical simplicity: polygonal models lend themselves to simple, regular rendering algorithms that embed well in hardware, which has in turn led to widely available polygon rendering accelerators for every platform. Unfortunately, the complexity of these models, which is measured by the number of polygons, seems to grow faster than the ability of our graphics hardware to render them interactively. Put another way, the number of polygons we want always seems to exceed the number of polygons we can afford. Polygonal simplification techniques offer one solution for developers grappling with complex models. These methods simplify the polygonal geometry of small, distant, or otherwise unimportant portions of the model, seeking to reduce the rendering cost without a significant loss in the scene's visual content. The article surveys polygonal simplification algorithms, identifies the issues in picking an algorithm, relates the strengths and weaknesses of different approaches, and describes several published algorithms.
---
paper_title: A Comparison of mesh simplification algorithms

paper_content:

Abstract In many applications the need for an accurate simplification of surface meshes is becoming more and more urgent. This need is not only due to rendering speed reasons, but also to allow fast transmission of 3D models in network-based applications. Many different approaches and algorithms for mesh simplification have been proposed in the last few years. We present a survey and a characterization of the fundamental methods. Moreover, the results of an empirical comparison of the simplification codes available in the public domain are discussed. Five implementations, chosen to give a wide spectrum of different topology preserving methods, were run on a set of sample surfaces. We compared empirical computational complexities and the approximation accuracy of the resulting output meshes.
---
paper_title: Survey of Polygonal Surface Simplification Algorithms

paper_content:

Abstract : This paper surveys methods for simplifying and approximating polygonal surfaces. A polygonal surface is a piecewise-linear surface in 3-D defined by a set of polygons; typically a set of triangles. Methods from computer graphics, computer vision, cartography, computational geometry, and other fields are classified, summarized, and compared both practically and theoretically. The surface types range from height fields (bivariate functions), to manifolds, to non-manifold self-intersecting surfaces. Piecewise-linear curve simplification is also briefly surveyed.
---
paper_title: Smooth view-dependent level-of-detail control and its application to terrain rendering

paper_content:

The key to real-time rendering of large-scale surfaces is to locally adapt surface geometric complexity to changing view parameters. Several schemes have been developed to address this problem of view-dependent level-of-detail control. Among these, the view-dependent progressive mesh (VDPM) framework represents an arbitrary triangle mesh as a hierarchy of geometrically optimized refinement transformations, from which accurate approximating meshes can be efficiently retrieved. In this paper we extend the general VDPM framework to provide temporal coherence through the run-time creation of geomorphs. These geomorphs eliminate "popping" artifacts by smoothly interpolating geometry. Their implementation requires new output-sensitive data structures, which have the added benefit of reducing memory use. We specialize the VDPM framework to the important case of terrain rendering. To handle huge terrain grids, we introduce a block-based simplification scheme that constructs a progressive mesh as a hierarchy of block refinements. We demonstrate the need for an accurate approximation metric during simplification. Our contributions are highlighted in a real-time flyover of a large, rugged terrain. Notably, the use of geomorphs results in visually smooth rendering even at 72 frames/sec on a graphics workstation.
---
paper_title: Building and traversing a surface at variable resolution

paper_content:

The authors consider the multi-triangulation, a general model for representing surfaces at variable resolution based on triangle meshes. They analyse characteristics of the model that make it effective for supporting basic operations such as extraction of a surface approximation, and point location. An interruptible algorithm for extracting a representation at a resolution variable over the surface is presented. Different heuristics for building the model are considered and compared. Results on both the construction and the extraction algorithm are presented.
---
paper_title: A hybrid, hierarchical data structure for real-time terrain visualization

paper_content:

The approximation tree is a hybrid, hierarchical data structure for real-time terrain visualization which represents both geometry data and texture data of a terrain in a hierarchical manner. This framework can integrate different multiresolution modeling techniques operating on different types of data sets such as TLNs, regular grids, and non-regular grids. An approximation tree recursively aggregates terrain patches which reference geometry data and texture data. The rendering algorithm selects patches based on a geometric approximation error and a texture approximation error. Terrain shading and thematic texturing, which can be generated in a preprocessing step, improve the visual quality of level of detail models and eliminate the defects resulting from a Gouraud shaded geometric model since they do not depend on the current (probably reduced) geometry. The approximation tree can be implemented efficiently using object-oriented design principles. A case study for cartographic landscape visualization illustrates the use of approximation trees.
---
paper_title: Geometry clipmaps: terrain rendering using nested regular grids

paper_content:

Rendering throughput has reached a level that enables a novel approach to level-of-detail (LOD) control in terrain rendering. We introduce the geometry clipmap, which caches the terrain in a set of nested regular grids centered about the viewer. The grids are stored as vertex buffers in fast video memory, and are incrementally refilled as the viewpoint moves. This simple framework provides visual continuity, uniform frame rate, complexity throttling, and graceful degradation. Moreover it allows two new exciting real-time functionalities: decompression and synthesis. Our main dataset is a 40GB height map of the United States. A compressed image pyramid reduces the size by a remarkable factor of 100, so that it fits entirely in memory. This compressed data also contributes normal maps for shading. As the viewer approaches the surface, we synthesize grid levels finer than the stored terrain using fractal noise displacement. Decompression, synthesis, and normal-map computations are incremental, thereby allowing interactive flight at 60 frames/sec.
---
paper_title: TerraVision II: Visualizing Massive Terrain Databases in VRML

paper_content:

To disseminate 3D maps and spatial data over the Web, we designed massive terrain data sets accessible through either a VRML browser or the customized TerraVision II browser. Although not required to view the content, TerraVision II lets the user perform specialized browser level optimizations that offer increased efficiency and seamless interaction with the terrain data. We designed our framework to simplify terrain data maintenance and to let users dynamically select particular sets of geo-referenced data. Our implementation uses Java scripting to extend VRML's base functionality and the External Authoring Interface to offer application-specific management of the virtual geographic environment.
---
paper_title: Geometry clipmaps: terrain rendering using nested regular grids

paper_content:

Rendering throughput has reached a level that enables a novel approach to level-of-detail (LOD) control in terrain rendering. We introduce the geometry clipmap, which caches the terrain in a set of nested regular grids centered about the viewer. The grids are stored as vertex buffers in fast video memory, and are incrementally refilled as the viewpoint moves. This simple framework provides visual continuity, uniform frame rate, complexity throttling, and graceful degradation. Moreover it allows two new exciting real-time functionalities: decompression and synthesis. Our main dataset is a 40GB height map of the United States. A compressed image pyramid reduces the size by a remarkable factor of 100, so that it fits entirely in memory. This compressed data also contributes normal maps for shading. As the viewer approaches the surface, we synthesize grid levels finer than the stored terrain using fractal noise displacement. Decompression, synthesis, and normal-map computations are incremental, thereby allowing interactive flight at 60 frames/sec.
---
paper_title: Real-time, continuous level of detail rendering of height fields

paper_content:

We present an algorithm for real-time level of detail reduction and display of high-complexity polygonal surface data. The algorithm uses a compact and efficient regular grid representation, and employs a variable screen-space threshold to bound the maximum error of the projected image. A coarse level of simplification is performed to select discrete levels of detail for blocks of the surface mesh, followed by further simplification through repolygonalization in which individual mesh vertices are considered for removal. These steps compute and generate the appropriate level of detail dynamically in real-time, minimizing the number of rendered polygons and allowing for smooth changes in resolution across areas of the surface. The algorithm has been implemented for approximating and rendering digital terrain models and other height fields, and consistently performs at interactive frame rates with high image quality.
---
paper_title: Multiresolution Compression and Visualization of Global Topographic Data

paper_content:

We present a multiresolution model for terrain surfaces which is able to handle large-scale global topographic data. It is based on a hierarchical decomposition of the sphere by a recursive bisection triangulation in geographic coordinates. Error indicators allow the representation of the data at various levels of detail and enable data compression by local omission of data values. The resulting adaptive hierarchical triangulation is stored using a bit code of the underlying binary tree and additionally, relative pointers which allow a selective tree traversal. This way, it is possible to work directly on the compressed data. We show that significant compression rates can be obtained already for small threshold values. In a visualization application, adaptive triangulations which consist of hundreds of thousands of shaded triangles are extracted and drawn at interactive rates.
---
paper_title: Real-time optimal adaptation for planetary geometry and texture: 4-8 tile hierarchies

paper_content:

The real-time display of huge geometry and imagery databases involves view-dependent approximations, typically through the use of precomputed hierarchies that are selectively refined at runtime. A classic motivating problem is terrain visualization in which planetary databases involving billions of elevation and color values are displayed on PC graphics hardware at high frame rates. This paper introduces a new diamond data structure for the basic selective-refinement processing, which is a streamlined method of representing the well-known hierarchies of right triangles that have enjoyed much success in real-time, view-dependent terrain display. Regular-grid tiles are proposed as the payload data per diamond for both geometry and texture. The use of 4-8 grid refinement and coarsening schemes allows level-of-detail transitions that are twice as gradual as traditional quadtree-based hierarchies, as well as very high-quality low-pass filtering compared to subsampling-based hierarchies. An out-of-core storage organization is introduced based on Sierpinski indices per diamond, along with a tile preprocessing framework based on fine-to-coarse, same-level, and coarse-to-fine gathering operations. To attain optimal frame-to-frame coherence and processing-order priorities, dual split and merge queues are developed similar to the realtime optimally adapting meshes (ROAM) algorithm, as well as an adaptation of the ROAM frustum culling technique. Example applications of lake-detection and procedural terrain generation demonstrate the flexibility of the tile processing framework.
---
paper_title: Top–Down View–Dependent Terrain Triangulation using the Octagon Metric

paper_content:

A boat bumper/fender, comprising a resilient, flexible, weather resistant, body having opposing first end and a second ends, said body composed of a closed cell foam material and having length, width and height, said body being of greater length than width; said body having an internal passage extending substantially the length of said body and terminating at said first and second ends; bushing means adapted to be inserted into said first and second end of said body; anchoring means extending through said body in said passage and extending beyond the ends of said body; said anchoring means further equipped with stop means to cooperatively interact with said bushing to limit movement of the body along said anchoring means.
---
paper_title: BDAM - Batched Dynamic Adaptive Meshes for High Performance Terrain Visualization

paper_content:

This paper describes an efficient technique for out-of-core rendering and management of large textured terrain surfaces. The technique, called Batched Dynamic Adaptive Meshes (BDAM) , is based on a paired tree structure: a tiled quadtree for texture data and a pair of bintrees of small triangular patches for the geometry. These small patches are TINs and are constructed and optimized off-line with high quality simplification and tristripping algorithms. Hierarchical view frustum culling and view-dependent texture and geometry refinement is performed at each frame through a stateless traversal algorithm. Thanks to the batched CPU/GPU communication model, the proposed technique is not processor intensive and fully harnesses the power of current graphics hardware. Both preprocessing and rendering exploit out-of-core techniques to be fully scalable and to manage large terrain datasets.
---
paper_title: Visualization of large terrains made easy

paper_content:

We present an elegant and simple to implement framework for performing out-of-core visualization and view-dependent refinement of large terrain surfaces. Contrary to the recent trend of increasingly elaborate algorithms for large-scale terrain visualization, our algorithms and data structures have been designed with the primary goal of simplicity and efficiency of implementation. Our approach to managing large terrain data also departs from more conventional strategies based on data tiling. Rather than emphasizing how to segment and efficiently bring data in and out of memory, we focus on the manner in which the data is laid out to achieve good memory coherency for data accesses made in a top-down (coarse-to-fine) refinement of the terrain. We present and compare the results of using several different data indexing schemes, and propose a simple to compute index that yields substantial improvements in locality and speed over more commonly used data layouts.Our second contribution is a new and simple, yet easy to generalize method for view-dependent refinement. Similar to several published methods in this area, we use longest edge bisection in a top-down traversal of the mesh hierarchy to produce a continuous surface with subdivision connectivity. In tandem with the refinement, we perform view frustum culling and triangle stripping. These three components are done together in a single pass over the mesh. We show how this framework supports virtually any error metric, while still being highly memory and compute efficient.
---
paper_title: Terrain Simplification Simplified : A General Framework for View-Dependent Out-of-Core Visualization

paper_content:

We describe a general framework for out-of-core rendering and management of massive terrain surfaces. The two key components of this framework are: view-dependent refinement of the terrain mesh and a simple scheme for organizing the terrain data to improve coherence and reduce the number of paging events from external storage to main memory. Similar to several previously proposed methods for view-dependent refinement, we recursively subdivide a triangle mesh defined over regularly gridded data using longest-edge bisection. As part of this single, per-frame refinement pass, we perform triangle stripping, view frustum culling, and smooth blending of geometry using geomorphing. Meanwhile, our refinement framework supports a large class of error metrics, is highly competitive in terms of rendering performance, and is surprisingly simple to implement. Independent of our refinement algorithm, we also describe several data layout techniques for providing coherent access to the terrain data. By reordering the data in a manner that is more consistent with our recursive access pattern, we show that visualization of gigabyte-size data sets can be realized even on low-end, commodity PCs without the need for complicated and explicit data paging techniques. Rather, by virtue of dramatic improvements in multilevel cache coherence, we rely on the built-in paging mechanisms of the operating system to perform this task. The end result is a straightforward, simple-to-implement, pointerless indexing scheme that dramatically improves the data locality and paging performance over conventional matrix-based layouts.
---
paper_title: Scalable compression and rendering of textured terrain data

paper_content:

Several sophisticated methods are available for efficient rendering of out-of-core terrain data sets. For huge data sets the use of preprocessed tiles has proven to be more efficient than continuous levels of detail, since in the latter case the screen space error has to be verified for individual triangles. There are some prevailing problems of these approaches: i) the partitioning and simplification of the original data set and ii) the accurate rendering of these data sets. Current approaches still trade the approximation error in image space for increased frame rates. To overcome these problems we propose a data structure and LOD scheme. These enable the real-time rendering of out-of-core data sets while guaranteeing geometric and texture accuracy of one pixel between original and rendered mesh in image space. To accomplish this, we utilize novel scalable techniques for integrated simplification, compression, and rendering. The combination of these techniques with impostors and occlusion culling yields a truly output sensitive algorithm for terrain data sets. We demonstrate the potential of our approach by presenting results for several terrain data sets with sizes up to 16k x 16k. The results show the unprecedented fidelity of the visualization, which is maintained even during real-time exploration of the data sets.
---
paper_title: ROAMing terrain: Real-time Optimally Adapting Meshes

paper_content:

Terrain visualization is a difficult problem for applications requiring accurate images of large datasets at high frame rates, such as flight simulation and ground-based aircraft testing using synthetic sensor simulation. On current graphics hardware, the problem is to maintain dynamic, view-dependent triangle meshes and texture maps that produce good images at the required frame rate. We present an algorithm for constructing triangle meshes that optimizes flexible view-dependent error metrics, produces guaranteed error bounds, achieves specified triangle counts directly and uses frame-to-frame coherence to operate at high frame rates for thousands of triangles per frame. Our method, dubbed Real-time Optimally Adapting Meshes (ROAM), uses two priority queues to drive split and merge operations that maintain continuous triangulations built from pre-processed bintree triangles. We introduce two additional performance optimizations: incremental triangle stripping and priority-computation deferral lists. ROAM's execution time is proportional to the number of triangle changes per frame, which is typically a few percent of the output mesh size; hence ROAM's performance is insensitive to the resolution and extent of the input terrain. Dynamic terrain and simple vertex morphing are supported.
---
paper_title: Right-Triangulated Irregular Networks

paper_content:

We describe a hierarchical data structure for representing a digital terrain (height field) which contains approximations of the terrain at different levels of detail. The approximations are based on triangulations of the underlying two-dimensional space using right-angled triangles. The methods we discuss permit a single approximation to have a varying level of approximation accuracy across the surface. Thus, for example, the area close to an observer may be represented with greater detail than areas which lie outside their field of view. ::: ::: We discuss the application of this hierarchical data structure to the problem of interactive terrain visualization. We point out some of the advantages of this method in terms of memory usage and speed.
---
paper_title: Real-time, continuous level of detail rendering of height fields

paper_content:

We present an algorithm for real-time level of detail reduction and display of high-complexity polygonal surface data. The algorithm uses a compact and efficient regular grid representation, and employs a variable screen-space threshold to bound the maximum error of the projected image. A coarse level of simplification is performed to select discrete levels of detail for blocks of the surface mesh, followed by further simplification through repolygonalization in which individual mesh vertices are considered for removal. These steps compute and generate the appropriate level of detail dynamically in real-time, minimizing the number of rendered polygons and allowing for smooth changes in resolution across areas of the surface. The algorithm has been implemented for approximating and rendering digital terrain models and other height fields, and consistently performs at interactive frame rates with high image quality.
---
paper_title: Surface Modeling Using Quadtrees

paper_content:

Two quadtree variants effective in modeling 2 1/2-d surfaces are presented. The restricted quadtree can handle regularly sampled data. For irregular data, embedding a TIN inside a PMR quadtree is suggested. Together, these schemes facilitate the handling of most types of input within a single framework. Algorithms for the construction of both data structures from their respective data formats are described and analyzed. The possible application of each of the models to the problem of visibility determination is considered and theoretical evaluation of its performance is made.
---
paper_title: Variable Resolution Triangulations

paper_content:

Abstract A comprehensive study of multiresolution decompositions of planar domains into triangles is given. A general model is introduced, called a Multi-Triangulation (MT), which is based on a collection of fragments of triangulations arranged into a directed acyclic graph. Different decompositions of a domain can be obtained by combining different fragments of the model. Theoretical results on the expressive power of the MT are given. An efficient algorithm is proposed that can extract a triangulation from the MT, whose level of detail is variable over the domain according to a given threshold function. The algorithm works in linear time, and the extracted representation has minimum size among all possible triangulations that can be built from triangles in the MT, and that satisfy the given level of detail. Major applications of these results are in real-time rendering of complex surfaces, such as topographic surfaces in flight simulation.
---
paper_title: Accurate triangulations of deformed, intersecting surfaces

paper_content:

A quadtree algorithm is developed to triangulate deformed, intersecting parametric surfaces. The biggest problem with adaptive sampling is to guarantee that the triangulation is accurate within a given tolerance. A new method guarantees the accuracy of the triangulation, given a "Lipschitz" condition on the surface definition. The method constructs a hierarchical set of bounding volumes for the surface, useful for ray tracing and solid modeling operations. The task of adaptively sampling a surface is broken into two parts: a subdivision mechanism for recursively subdividing a surface, and a set of subdivision criteria for controlling the subdivision process.An adaptive sampling technique is said to be robust if it accurately represents the surface being sampled. A new type of quadtree, called a restricted quadtree, is more robust than the traditional unrestricted quadtree at adaptive sampling of parametric surfaces. Each sub-region in the quadtree is half the width of the previous region. The restricted quadtree requires that adjacent regions be the same width within a factor of two, while the traditional quadtree makes no restriction on neighbor width. Restricted surface quadtrees are effective at recursively sampling a parametric surface. Quadtree samples are concentrated in regions of high curvature, and along intersection boundaries, using several subdivision criteria. Silhouette subdivision improves the accuracy of the silhouette boundary when a viewing transformation is available at sampling time. The adaptive sampling method is more robust than uniform sampling, and can be more efficient at rendering deformed, intersecting parametric surfaces.
---
paper_title: A hybrid, hierarchical data structure for real-time terrain visualization

paper_content:

The approximation tree is a hybrid, hierarchical data structure for real-time terrain visualization which represents both geometry data and texture data of a terrain in a hierarchical manner. This framework can integrate different multiresolution modeling techniques operating on different types of data sets such as TLNs, regular grids, and non-regular grids. An approximation tree recursively aggregates terrain patches which reference geometry data and texture data. The rendering algorithm selects patches based on a geometric approximation error and a texture approximation error. Terrain shading and thematic texturing, which can be generated in a preprocessing step, improve the visual quality of level of detail models and eliminate the defects resulting from a Gouraud shaded geometric model since they do not depend on the current (probably reduced) geometry. The approximation tree can be implemented efficiently using object-oriented design principles. A case study for cartographic landscape visualization illustrates the use of approximation trees.
---
paper_title: Surface Modeling Using Quadtrees

paper_content:

Two quadtree variants effective in modeling 2 1/2-d surfaces are presented. The restricted quadtree can handle regularly sampled data. For irregular data, embedding a TIN inside a PMR quadtree is suggested. Together, these schemes facilitate the handling of most types of input within a single framework. Algorithms for the construction of both data structures from their respective data formats are described and analyzed. The possible application of each of the models to the problem of visibility determination is considered and theoretical evaluation of its performance is made.
---
paper_title: Real-time, continuous level of detail rendering of height fields

paper_content:

We present an algorithm for real-time level of detail reduction and display of high-complexity polygonal surface data. The algorithm uses a compact and efficient regular grid representation, and employs a variable screen-space threshold to bound the maximum error of the projected image. A coarse level of simplification is performed to select discrete levels of detail for blocks of the surface mesh, followed by further simplification through repolygonalization in which individual mesh vertices are considered for removal. These steps compute and generate the appropriate level of detail dynamically in real-time, minimizing the number of rendered polygons and allowing for smooth changes in resolution across areas of the surface. The algorithm has been implemented for approximating and rendering digital terrain models and other height fields, and consistently performs at interactive frame rates with high image quality.
---
paper_title: Variable Resolution 4-k Meshes: Concepts and Applications

paper_content:

In this paper we introduce variable resolution 4-k meshes, a powerful structure for the representation of geometric objects at multiple levels of detail. It combines most properties of other related descriptions with several advantages, such as more flexibility and greater expressive power. The main unique feature of the 4-k mesh structure lies in its variable resolution capability, which is crucial for adaptive computation. We also give an overview of the different methods for constructing the 4-k mesh representation, as well as the basic algorithms necessary to incorporate it in modeling and graphics applications.
---
paper_title: Finding neighbors of equal size in linear quadtrees and octrees in constant time

paper_content:

Abstract Linear quadtrees and octrees are data structures which are of interest in image processing, computer graphics, and solid modeling. Their representation involves spatial addresses called location codes. For many of the operations on objects in linear quadtree and octree representation, finding neighbors is a basic operation. By considering the components of a location code, named dilated integers, a representation and associated addition and subtraction operations may be defined which are efficient in execution. The operations form the basis for the definition of location code addition and subtraction, with which finding neighbors of equal size is accomplished in constant time. The translation of pixels is a related operation. The results for linear quadtrees can be generalized without difficulty to linear octrees.
---
paper_title: Surface Modeling Using Quadtrees

paper_content:

Two quadtree variants effective in modeling 2 1/2-d surfaces are presented. The restricted quadtree can handle regularly sampled data. For irregular data, embedding a TIN inside a PMR quadtree is suggested. Together, these schemes facilitate the handling of most types of input within a single framework. Algorithms for the construction of both data structures from their respective data formats are described and analyzed. The possible application of each of the models to the problem of visibility determination is considered and theoretical evaluation of its performance is made.
---
paper_title: Computational analysis of 4-8 meshes with application to surface simplification using global error

paper_content:

We present computational results when computing approximations of a class of meshes with subdivision connectivity, known as 4-8 meshes. We consider algorithms using vertex decimation or vertex insertion. We explain that a full decomposition of a 4-8 mesh using global error can be obtained with an decimation algorithm. Our algorithm produces progressive and adaptive representations of terrain data or subdivision surfaces in having arbitrary topology.
---
paper_title: Image encoding with triangulation wavelets

paper_content:

We demonstrate some wavelet-based image processing applications of a class of simplicial grids arising in finite element computations and computer graphics. The cells of a triangular grid form the set of leaves of a binary tree and the nodes of a directed graph consisting of a single cycle. The leaf cycle of a uniform grid forms a pattern for pixel image scanning and for coherent computation of coefficients of splines and wavelets. A simple form of image encoding is accomplished with a 1D quadrature mirror filter whose coefficients represent an expansion of the image in terms of 2D Haar wavelets with triangular support. A combination the leaf cycle and an inherent quadtree structure allow efficient neighbor finding, grid refinement, tree pruning and storage. Pruning of the simplex tree yields a partially compressed image which requires no decoding, but rather may be rendered as a shaded triangulation. This structure and its generalization to n-dimensions form a convenient setting for wavelet analysis and computations based on simplicial grids.© (1995) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Using Semi-Regular 4-8 Meshes for Subdivision Surfaces

paper_content:

Abstract Semi-regular 4–8 meshes are refinable triangulated quadmngulations. They provide a powerful hierarchical structure for multiresolution applications. In this paper, we show how to decompose the Doa-Sabin and Catmull-Clark subdivision schemes using 4–8 refinement. The described technique makes it possible to use these classical subdivision surfaces with semi-regular 4–8 meshes.
---
paper_title: Space Filling Curves and Their Use in the Design of Geometric Data Structures

paper_content:

We are given a two-dimensional square grid of size N×N, where N∶=2n and n≥0. A space filling curve (SFC) is a numbering of the cells of this grid with numbers from c+1 to c+N2, for some c≥0. We call a SFC recursive (RSFC) if it can be recursively divided into four square RSFCs of equal size. Examples of well-known RSFCs include the Hilbert curve, the z-curve, and the Gray code.
---
paper_title: QuadTIN: quadtree based triangulated irregular networks

paper_content:

Interactive visualization of large digital elevation models is of continuing interest in scientific visualization, GIS, and virtual reality applications. Taking advantage of the regular structure of grid digital elevation models, efficient hierarchical multiresolution triangulation and adaptive level-of-detail (LOD) rendering algorithms have been developed for interactive terrain visualization. Despite the higher triangle count, these approaches generally outperform mesh simplification methods that produce irregular triangulated network (TIN) based LOD representations. In this project we combine the advantage of a TIN based mesh simplification preprocess with high-performance quadtree based LOD triangulation and rendering at run-time. This approach, called QuadTIN, generates an efficient quadtree triangulation hierarchy over any irregular point set that may originate from irregular terrain sampling or from reducing oversampling in high-resolution grid digital elevation models.
---
paper_title: Real-time, continuous level of detail rendering of height fields

paper_content:

We present an algorithm for real-time level of detail reduction and display of high-complexity polygonal surface data. The algorithm uses a compact and efficient regular grid representation, and employs a variable screen-space threshold to bound the maximum error of the projected image. A coarse level of simplification is performed to select discrete levels of detail for blocks of the surface mesh, followed by further simplification through repolygonalization in which individual mesh vertices are considered for removal. These steps compute and generate the appropriate level of detail dynamically in real-time, minimizing the number of rendered polygons and allowing for smooth changes in resolution across areas of the surface. The algorithm has been implemented for approximating and rendering digital terrain models and other height fields, and consistently performs at interactive frame rates with high image quality.
---
paper_title: Variable Resolution 4-k Meshes: Concepts and Applications

paper_content:

In this paper we introduce variable resolution 4-k meshes, a powerful structure for the representation of geometric objects at multiple levels of detail. It combines most properties of other related descriptions with several advantages, such as more flexibility and greater expressive power. The main unique feature of the 4-k mesh structure lies in its variable resolution capability, which is crucial for adaptive computation. We also give an overview of the different methods for constructing the 4-k mesh representation, as well as the basic algorithms necessary to incorporate it in modeling and graphics applications.
---
paper_title: Efficient algorithms for embedded rendering of terrain models

paper_content:

Digital terrains are generally large files and need to be simplified to be rendered efficiently. We propose to build an adaptive embedded triangulation based on a binary tree structure to generate multiple levels of details. We present a O(nlogn) decimation algorithm and a O(nlogn) refinement algorithm, where n is the number of elevation points. We compare them in a rate-distortion (RD) framework. The algorithms are based on an improved version of the optimal tree pruning algorithm G-BFOS allowing one to deal with constrained tree structures and non-monotonic tree functionals.
---
paper_title: Computational analysis of 4-8 meshes with application to surface simplification using global error

paper_content:

We present computational results when computing approximations of a class of meshes with subdivision connectivity, known as 4-8 meshes. We consider algorithms using vertex decimation or vertex insertion. We explain that a full decomposition of a 4-8 mesh using global error can be obtained with an decimation algorithm. Our algorithm produces progressive and adaptive representations of terrain data or subdivision surfaces in having arbitrary topology.
---
paper_title: Using Semi-Regular 4-8 Meshes for Subdivision Surfaces

paper_content:

Abstract Semi-regular 4–8 meshes are refinable triangulated quadmngulations. They provide a powerful hierarchical structure for multiresolution applications. In this paper, we show how to decompose the Doa-Sabin and Catmull-Clark subdivision schemes using 4–8 refinement. The described technique makes it possible to use these classical subdivision surfaces with semi-regular 4–8 meshes.
---
paper_title: Real-time, continuous level of detail rendering of height fields

paper_content:

We present an algorithm for real-time level of detail reduction and display of high-complexity polygonal surface data. The algorithm uses a compact and efficient regular grid representation, and employs a variable screen-space threshold to bound the maximum error of the projected image. A coarse level of simplification is performed to select discrete levels of detail for blocks of the surface mesh, followed by further simplification through repolygonalization in which individual mesh vertices are considered for removal. These steps compute and generate the appropriate level of detail dynamically in real-time, minimizing the number of rendered polygons and allowing for smooth changes in resolution across areas of the surface. The algorithm has been implemented for approximating and rendering digital terrain models and other height fields, and consistently performs at interactive frame rates with high image quality.
---
paper_title: ROAMing terrain: Real-time Optimally Adapting Meshes

paper_content:

Terrain visualization is a difficult problem for applications requiring accurate images of large datasets at high frame rates, such as flight simulation and ground-based aircraft testing using synthetic sensor simulation. On current graphics hardware, the problem is to maintain dynamic, view-dependent triangle meshes and texture maps that produce good images at the required frame rate. We present an algorithm for constructing triangle meshes that optimizes flexible view-dependent error metrics, produces guaranteed error bounds, achieves specified triangle counts directly and uses frame-to-frame coherence to operate at high frame rates for thousands of triangles per frame. Our method, dubbed Real-time Optimally Adapting Meshes (ROAM), uses two priority queues to drive split and merge operations that maintain continuous triangulations built from pre-processed bintree triangles. We introduce two additional performance optimizations: incremental triangle stripping and priority-computation deferral lists. ROAM's execution time is proportional to the number of triangle changes per frame, which is typically a few percent of the output mesh size; hence ROAM's performance is insensitive to the resolution and extent of the input terrain. Dynamic terrain and simple vertex morphing are supported.
---
paper_title: Real-time, continuous level of detail rendering of height fields

paper_content:

We present an algorithm for real-time level of detail reduction and display of high-complexity polygonal surface data. The algorithm uses a compact and efficient regular grid representation, and employs a variable screen-space threshold to bound the maximum error of the projected image. A coarse level of simplification is performed to select discrete levels of detail for blocks of the surface mesh, followed by further simplification through repolygonalization in which individual mesh vertices are considered for removal. These steps compute and generate the appropriate level of detail dynamically in real-time, minimizing the number of rendered polygons and allowing for smooth changes in resolution across areas of the surface. The algorithm has been implemented for approximating and rendering digital terrain models and other height fields, and consistently performs at interactive frame rates with high image quality.
---
paper_title: Multiresolution Compression and Visualization of Global Topographic Data

paper_content:

We present a multiresolution model for terrain surfaces which is able to handle large-scale global topographic data. It is based on a hierarchical decomposition of the sphere by a recursive bisection triangulation in geographic coordinates. Error indicators allow the representation of the data at various levels of detail and enable data compression by local omission of data values. The resulting adaptive hierarchical triangulation is stored using a bit code of the underlying binary tree and additionally, relative pointers which allow a selective tree traversal. This way, it is possible to work directly on the compressed data. We show that significant compression rates can be obtained already for small threshold values. In a visualization application, adaptive triangulations which consist of hundreds of thousands of shaded triangles are extracted and drawn at interactive rates.
---
paper_title: ROAMing terrain: Real-time Optimally Adapting Meshes

paper_content:

Terrain visualization is a difficult problem for applications requiring accurate images of large datasets at high frame rates, such as flight simulation and ground-based aircraft testing using synthetic sensor simulation. On current graphics hardware, the problem is to maintain dynamic, view-dependent triangle meshes and texture maps that produce good images at the required frame rate. We present an algorithm for constructing triangle meshes that optimizes flexible view-dependent error metrics, produces guaranteed error bounds, achieves specified triangle counts directly and uses frame-to-frame coherence to operate at high frame rates for thousands of triangles per frame. Our method, dubbed Real-time Optimally Adapting Meshes (ROAM), uses two priority queues to drive split and merge operations that maintain continuous triangulations built from pre-processed bintree triangles. We introduce two additional performance optimizations: incremental triangle stripping and priority-computation deferral lists. ROAM's execution time is proportional to the number of triangle changes per frame, which is typically a few percent of the output mesh size; hence ROAM's performance is insensitive to the resolution and extent of the input terrain. Dynamic terrain and simple vertex morphing are supported.
---
paper_title: Right-Triangulated Irregular Networks

paper_content:

We describe a hierarchical data structure for representing a digital terrain (height field) which contains approximations of the terrain at different levels of detail. The approximations are based on triangulations of the underlying two-dimensional space using right-angled triangles. The methods we discuss permit a single approximation to have a varying level of approximation accuracy across the surface. Thus, for example, the area close to an observer may be represented with greater detail than areas which lie outside their field of view. ::: ::: We discuss the application of this hierarchical data structure to the problem of interactive terrain visualization. We point out some of the advantages of this method in terms of memory usage and speed.
---
paper_title: Methods for user-based reduction of model complexity for virtual planetary exploration

paper_content:

SUMMARY AND CONCLUSION5.1 Summary ofmodel and resultsWe have described a model for analysis of object geometric complexity and model display in visual simulationsystems that more fully exploits the power of adaptive methods than has been used previously. Our model is stronglyoriented towards user and application needs. A general version of the model that uses multiple analysis criteria, adaptsto system load feedback, and is applicable to nearly any real-time feedback control system was presented first. We thenspecialized that model for the case of virtual environment systems to one that includes three criteria: an application taskdependent one analyzed in Environment Coordinate Space, a view dependent criterion analyzed in 3D View CoordinateSpace, and a visual perception dependent criterion analyzed in 2D Display Coordinate Space. The latter criterion incor-porates both static and dynamic perceptual effects. Finally, we described a further specialization and implementation ofour model in the NASA Ames Virtual Planetary Exploration Testbed. The VPE Testbed utilizes hierarchical spatial sub-division of regularly gridded polygon mesh models of terrain surfaces for computational efficiency.Although portions of our model implementation take advantage of current system hardware and software architec-ture, the general principles are independent of these. Thus, with any performance advances in future architectures, ourmethods will always be able to enhance that performance.The results of our work can provide either a significant increase in visual appearance for a given frame update rate,or a higher update rate for comparable visual appearance than possible without using our methods. We address the"many polygons, little time" problem by showing the user many "important' polygons and fewer "unimportant" polygons.5.2
---
paper_title: Smooth view-dependent level-of-detail control and its application to terrain rendering

paper_content:

The key to real-time rendering of large-scale surfaces is to locally adapt surface geometric complexity to changing view parameters. Several schemes have been developed to address this problem of view-dependent level-of-detail control. Among these, the view-dependent progressive mesh (VDPM) framework represents an arbitrary triangle mesh as a hierarchy of geometrically optimized refinement transformations, from which accurate approximating meshes can be efficiently retrieved. In this paper we extend the general VDPM framework to provide temporal coherence through the run-time creation of geomorphs. These geomorphs eliminate "popping" artifacts by smoothly interpolating geometry. Their implementation requires new output-sensitive data structures, which have the added benefit of reducing memory use. We specialize the VDPM framework to the important case of terrain rendering. To handle huge terrain grids, we introduce a block-based simplification scheme that constructs a progressive mesh as a hierarchy of block refinements. We demonstrate the need for an accurate approximation metric during simplification. Our contributions are highlighted in a real-time flyover of a large, rugged terrain. Notably, the use of geomorphs results in visually smooth rendering even at 72 frames/sec on a graphics workstation.
---
paper_title: Scalable compression and rendering of textured terrain data

paper_content:

Several sophisticated methods are available for efficient rendering of out-of-core terrain data sets. For huge data sets the use of preprocessed tiles has proven to be more efficient than continuous levels of detail, since in the latter case the screen space error has to be verified for individual triangles. There are some prevailing problems of these approaches: i) the partitioning and simplification of the original data set and ii) the accurate rendering of these data sets. Current approaches still trade the approximation error in image space for increased frame rates. To overcome these problems we propose a data structure and LOD scheme. These enable the real-time rendering of out-of-core data sets while guaranteeing geometric and texture accuracy of one pixel between original and rendered mesh in image space. To accomplish this, we utilize novel scalable techniques for integrated simplification, compression, and rendering. The combination of these techniques with impostors and occlusion culling yields a truly output sensitive algorithm for terrain data sets. We demonstrate the potential of our approach by presenting results for several terrain data sets with sizes up to 16k x 16k. The results show the unprecedented fidelity of the visualization, which is maintained even during real-time exploration of the data sets.
---
paper_title: Fast view-dependent level-of-detail rendering using cached geometry

paper_content:

Level-of-detail rendering is essential for rendering very large, detailed worlds in real-time. Unfortunately, level-of-detail computations can be expensive, creating a bottleneck at the CPU.This paper presents the CABTT algorithm, an extension to existing binary-triangle-tree-based level-of-detail algorithms. Instead of manipulating triangles, the CABTT algorithm instead operates on clusters of geometry called aggregate triangles. This reduces CPU overhead, eliminating a bottleneck common to level-of-detail algorithms. Since aggregate triangles stay fixed over several frames, they may be cached on the video card. This further reduces CPU load and fully utilizes the hardware accelerated rendering pipeline on modern video cards. These improvements result in a fourfold increase in frame rate over ROAM [7] at high detail levels. Our implementation renders an approximation of an 8 million triangle heightfield at 42 frames per second with an maximum error of 1 pixel on consumer hardware.
---
paper_title: ROAMing terrain: Real-time Optimally Adapting Meshes

paper_content:

Terrain visualization is a difficult problem for applications requiring accurate images of large datasets at high frame rates, such as flight simulation and ground-based aircraft testing using synthetic sensor simulation. On current graphics hardware, the problem is to maintain dynamic, view-dependent triangle meshes and texture maps that produce good images at the required frame rate. We present an algorithm for constructing triangle meshes that optimizes flexible view-dependent error metrics, produces guaranteed error bounds, achieves specified triangle counts directly and uses frame-to-frame coherence to operate at high frame rates for thousands of triangles per frame. Our method, dubbed Real-time Optimally Adapting Meshes (ROAM), uses two priority queues to drive split and merge operations that maintain continuous triangulations built from pre-processed bintree triangles. We introduce two additional performance optimizations: incremental triangle stripping and priority-computation deferral lists. ROAM's execution time is proportional to the number of triangle changes per frame, which is typically a few percent of the output mesh size; hence ROAM's performance is insensitive to the resolution and extent of the input terrain. Dynamic terrain and simple vertex morphing are supported.
---
paper_title: QuadTIN: quadtree based triangulated irregular networks

paper_content:

Interactive visualization of large digital elevation models is of continuing interest in scientific visualization, GIS, and virtual reality applications. Taking advantage of the regular structure of grid digital elevation models, efficient hierarchical multiresolution triangulation and adaptive level-of-detail (LOD) rendering algorithms have been developed for interactive terrain visualization. Despite the higher triangle count, these approaches generally outperform mesh simplification methods that produce irregular triangulated network (TIN) based LOD representations. In this project we combine the advantage of a TIN based mesh simplification preprocess with high-performance quadtree based LOD triangulation and rendering at run-time. This approach, called QuadTIN, generates an efficient quadtree triangulation hierarchy over any irregular point set that may originate from irregular terrain sampling or from reducing oversampling in high-resolution grid digital elevation models.
---
paper_title: Fast view-dependent level-of-detail rendering using cached geometry

paper_content:

Level-of-detail rendering is essential for rendering very large, detailed worlds in real-time. Unfortunately, level-of-detail computations can be expensive, creating a bottleneck at the CPU.This paper presents the CABTT algorithm, an extension to existing binary-triangle-tree-based level-of-detail algorithms. Instead of manipulating triangles, the CABTT algorithm instead operates on clusters of geometry called aggregate triangles. This reduces CPU overhead, eliminating a bottleneck common to level-of-detail algorithms. Since aggregate triangles stay fixed over several frames, they may be cached on the video card. This further reduces CPU load and fully utilizes the hardware accelerated rendering pipeline on modern video cards. These improvements result in a fourfold increase in frame rate over ROAM [7] at high detail levels. Our implementation renders an approximation of an 8 million triangle heightfield at 42 frames per second with an maximum error of 1 pixel on consumer hardware.
---
paper_title: BDAM - Batched Dynamic Adaptive Meshes for High Performance Terrain Visualization

paper_content:

This paper describes an efficient technique for out-of-core rendering and management of large textured terrain surfaces. The technique, called Batched Dynamic Adaptive Meshes (BDAM) , is based on a paired tree structure: a tiled quadtree for texture data and a pair of bintrees of small triangular patches for the geometry. These small patches are TINs and are constructed and optimized off-line with high quality simplification and tristripping algorithms. Hierarchical view frustum culling and view-dependent texture and geometry refinement is performed at each frame through a stateless traversal algorithm. Thanks to the batched CPU/GPU communication model, the proposed technique is not processor intensive and fully harnesses the power of current graphics hardware. Both preprocessing and rendering exploit out-of-core techniques to be fully scalable and to manage large terrain datasets.
---
paper_title: Hyperblock-QuadTIN: Hyper-block quadtree based triangulated irregular networks

paper_content:

rendering has always been an expensive task due to large input data models. Hierarchical mul-tiresolution triangulation and level-of-detail rendering algorithms over regular structures of grid digital elevation models have been widely used for interactive terrain visualization. The main drawbacks of these are the large cost of memory storage required and the possible over-sampling of high- resolution terrain models. Triangulated irregular networks (TIN) can reduce the amount of vertices at the expense of more complex and slower memory data access. We present a hyper-block quadtree based triangulated irregular networks approach, where the notion of vertex-selection is extended to block-selection. The hyper-block structure allows to store different pre-calculated triangulations. This reduces the vertex selection time per frame and removes the calculations needed to build the geometric rendering primitives (triangle strips) of the scene at the expense of a larger number of selected vertices. The presented approach shows a speed increment of 20% for high-quality terrain rendering with small screen-projection error thresholds.
---
paper_title: Planet-sized batched dynamic adaptive meshes (P-BDAM)

paper_content:

We describe an efficient technique for out-of-core management and interactive rendering of planet sized textured terrain surfaces. The technique, called planet-sized batched dynamic adaptive meshes (P-BDAM), extends the BDAM approach by using as basic primitive a general triangulation of points on a displaced triangle. The proposed framework introduces several advances with respect to the state of the art: thanks to a batched host-to-graphics communication model, we outperform current adaptive tessellation solutions in terms of rendering speed; we guarantee overall geometric continuity, exploiting programmable graphics hardware to cope with the accuracy issues introduced by single precision floating points; we exploit a compressed out of core representation and speculative prefetching for hiding disk latency during rendering of out-of-core data; we efficiently construct high quality simplified representations with a novel distributed out of core simplification algorithm working on a standard PC network.
---
paper_title: Real-time, continuous level of detail rendering of height fields

paper_content:

We present an algorithm for real-time level of detail reduction and display of high-complexity polygonal surface data. The algorithm uses a compact and efficient regular grid representation, and employs a variable screen-space threshold to bound the maximum error of the projected image. A coarse level of simplification is performed to select discrete levels of detail for blocks of the surface mesh, followed by further simplification through repolygonalization in which individual mesh vertices are considered for removal. These steps compute and generate the appropriate level of detail dynamically in real-time, minimizing the number of rendered polygons and allowing for smooth changes in resolution across areas of the surface. The algorithm has been implemented for approximating and rendering digital terrain models and other height fields, and consistently performs at interactive frame rates with high image quality.
---
paper_title: BDAM - Batched Dynamic Adaptive Meshes for High Performance Terrain Visualization

paper_content:

This paper describes an efficient technique for out-of-core rendering and management of large textured terrain surfaces. The technique, called Batched Dynamic Adaptive Meshes (BDAM) , is based on a paired tree structure: a tiled quadtree for texture data and a pair of bintrees of small triangular patches for the geometry. These small patches are TINs and are constructed and optimized off-line with high quality simplification and tristripping algorithms. Hierarchical view frustum culling and view-dependent texture and geometry refinement is performed at each frame through a stateless traversal algorithm. Thanks to the batched CPU/GPU communication model, the proposed technique is not processor intensive and fully harnesses the power of current graphics hardware. Both preprocessing and rendering exploit out-of-core techniques to be fully scalable and to manage large terrain datasets.
---
paper_title: Batched multi triangulation

paper_content:

The multi triangulation framework (MT) is a very general approach for managing adaptive resolution in triangle meshes. The key idea is arranging mesh fragments at different resolution in a directed acyclic graph (DAG) which encodes the dependencies between fragments, thereby encompassing a wide class of multiresolution approaches that use hierarchies or DAGs with predefined topology. On current architectures, the classic MT is however unfit for real-time rendering, since DAG traversal costs vastly dominate raw rendering costs. In this paper, we redesign the MT framework in a GPU friendly fashion, moving its granularity from triangles to precomputed optimized triangle patches. The patches can be conveniently tri-stripped and stored in secondary memory to be loaded on demand, ready to be sent to the GPU using preferential paths. In this manner, central memory only contains the DAG structure and CPU workload becomes negligible. The major contributions of this work are: a new out-of-core multiresolution framework, that, just like the MT, encompasses a wide class of multiresolution structures; a robust and elegant way to build a well conditioned MT DAG by introducing the concept of V-partitions, that can encompass various state of the art multiresolution algorithms; an efficient multithreaded rendering engine and a general subsystem for the external memory processing and simplification of huge meshes.
---
paper_title: Planet-sized batched dynamic adaptive meshes (P-BDAM)

paper_content:

We describe an efficient technique for out-of-core management and interactive rendering of planet sized textured terrain surfaces. The technique, called planet-sized batched dynamic adaptive meshes (P-BDAM), extends the BDAM approach by using as basic primitive a general triangulation of points on a displaced triangle. The proposed framework introduces several advances with respect to the state of the art: thanks to a batched host-to-graphics communication model, we outperform current adaptive tessellation solutions in terms of rendering speed; we guarantee overall geometric continuity, exploiting programmable graphics hardware to cope with the accuracy issues introduced by single precision floating points; we exploit a compressed out of core representation and speculative prefetching for hiding disk latency during rendering of out-of-core data; we efficiently construct high quality simplified representations with a novel distributed out of core simplification algorithm working on a standard PC network.
---
paper_title: Real-time optimal adaptation for planetary geometry and texture: 4-8 tile hierarchies

paper_content:

The real-time display of huge geometry and imagery databases involves view-dependent approximations, typically through the use of precomputed hierarchies that are selectively refined at runtime. A classic motivating problem is terrain visualization in which planetary databases involving billions of elevation and color values are displayed on PC graphics hardware at high frame rates. This paper introduces a new diamond data structure for the basic selective-refinement processing, which is a streamlined method of representing the well-known hierarchies of right triangles that have enjoyed much success in real-time, view-dependent terrain display. Regular-grid tiles are proposed as the payload data per diamond for both geometry and texture. The use of 4-8 grid refinement and coarsening schemes allows level-of-detail transitions that are twice as gradual as traditional quadtree-based hierarchies, as well as very high-quality low-pass filtering compared to subsampling-based hierarchies. An out-of-core storage organization is introduced based on Sierpinski indices per diamond, along with a tile preprocessing framework based on fine-to-coarse, same-level, and coarse-to-fine gathering operations. To attain optimal frame-to-frame coherence and processing-order priorities, dual split and merge queues are developed similar to the realtime optimally adapting meshes (ROAM) algorithm, as well as an adaptation of the ROAM frustum culling technique. Example applications of lake-detection and procedural terrain generation demonstrate the flexibility of the tile processing framework.
---
paper_title: Accurate triangulations of deformed, intersecting surfaces

paper_content:

A quadtree algorithm is developed to triangulate deformed, intersecting parametric surfaces. The biggest problem with adaptive sampling is to guarantee that the triangulation is accurate within a given tolerance. A new method guarantees the accuracy of the triangulation, given a "Lipschitz" condition on the surface definition. The method constructs a hierarchical set of bounding volumes for the surface, useful for ray tracing and solid modeling operations. The task of adaptively sampling a surface is broken into two parts: a subdivision mechanism for recursively subdividing a surface, and a set of subdivision criteria for controlling the subdivision process.An adaptive sampling technique is said to be robust if it accurately represents the surface being sampled. A new type of quadtree, called a restricted quadtree, is more robust than the traditional unrestricted quadtree at adaptive sampling of parametric surfaces. Each sub-region in the quadtree is half the width of the previous region. The restricted quadtree requires that adjacent regions be the same width within a factor of two, while the traditional quadtree makes no restriction on neighbor width. Restricted surface quadtrees are effective at recursively sampling a parametric surface. Quadtree samples are concentrated in regions of high curvature, and along intersection boundaries, using several subdivision criteria. Silhouette subdivision improves the accuracy of the silhouette boundary when a viewing transformation is available at sampling time. The adaptive sampling method is more robust than uniform sampling, and can be more efficient at rendering deformed, intersecting parametric surfaces.
---
paper_title: Topology preserving and controlled topology simplifying multiresolution isosurface extraction

paper_content:

Multiresolution methods are becoming increasingly important tools for the interactive visualization of very large data sets. Multiresolution isosurface visualization allows the user to explore volume data using simplified and coarse representations of the isosurface for overview images, and finer resolution in areas of high interest or when zooming into the data. Ideally, a coarse isosurface should have the same topological structure as the original. The topological genus of the isosurface is one important property which is often neglected in multiresolution algorithms. This results in uncontrolled topological changes which can occur whenever the level-of-detail is changed. The scope of this paper is to propose an efficient technique which allows preservation of topology as well as controlled topology simplification in multiresolution isosurface extraction.
---
paper_title: Error Indicators for Multilevel Visualization and Computing on Nested Grids

paper_content:

Abstract Nowadays computing and post processing of simulation data is often based on efficient hierarchical methods. While multigrid methods are already established standards for fast simulation codes, multiresolution visualization methods have only recently become an important ingredient of real–time interactive post processing. Both methodologies use local error indicators which serve as criteria where to refine the data representation on the physical domain. In this article we give an overview on different types of error measurement on nested grids and compare them for selected applications in 2D as well as in 3D. Furthermore, it is pointed out that a certain saturation of the considered error indicator plays an important role in multilevel visualization and computing on implicitly defined adaptive grids.
---
paper_title: ROAMing terrain: Real-time Optimally Adapting Meshes

paper_content:

Terrain visualization is a difficult problem for applications requiring accurate images of large datasets at high frame rates, such as flight simulation and ground-based aircraft testing using synthetic sensor simulation. On current graphics hardware, the problem is to maintain dynamic, view-dependent triangle meshes and texture maps that produce good images at the required frame rate. We present an algorithm for constructing triangle meshes that optimizes flexible view-dependent error metrics, produces guaranteed error bounds, achieves specified triangle counts directly and uses frame-to-frame coherence to operate at high frame rates for thousands of triangles per frame. Our method, dubbed Real-time Optimally Adapting Meshes (ROAM), uses two priority queues to drive split and merge operations that maintain continuous triangulations built from pre-processed bintree triangles. We introduce two additional performance optimizations: incremental triangle stripping and priority-computation deferral lists. ROAM's execution time is proportional to the number of triangle changes per frame, which is typically a few percent of the output mesh size; hence ROAM's performance is insensitive to the resolution and extent of the input terrain. Dynamic terrain and simple vertex morphing are supported.
---
paper_title: Right-Triangulated Irregular Networks

paper_content:

We describe a hierarchical data structure for representing a digital terrain (height field) which contains approximations of the terrain at different levels of detail. The approximations are based on triangulations of the underlying two-dimensional space using right-angled triangles. The methods we discuss permit a single approximation to have a varying level of approximation accuracy across the surface. Thus, for example, the area close to an observer may be represented with greater detail than areas which lie outside their field of view. ::: ::: We discuss the application of this hierarchical data structure to the problem of interactive terrain visualization. We point out some of the advantages of this method in terms of memory usage and speed.
---
paper_title: Real-time, continuous level of detail rendering of height fields

paper_content:

We present an algorithm for real-time level of detail reduction and display of high-complexity polygonal surface data. The algorithm uses a compact and efficient regular grid representation, and employs a variable screen-space threshold to bound the maximum error of the projected image. A coarse level of simplification is performed to select discrete levels of detail for blocks of the surface mesh, followed by further simplification through repolygonalization in which individual mesh vertices are considered for removal. These steps compute and generate the appropriate level of detail dynamically in real-time, minimizing the number of rendered polygons and allowing for smooth changes in resolution across areas of the surface. The algorithm has been implemented for approximating and rendering digital terrain models and other height fields, and consistently performs at interactive frame rates with high image quality.
---
paper_title: Top–Down View–Dependent Terrain Triangulation using the Octagon Metric

paper_content:

A boat bumper/fender, comprising a resilient, flexible, weather resistant, body having opposing first end and a second ends, said body composed of a closed cell foam material and having length, width and height, said body being of greater length than width; said body having an internal passage extending substantially the length of said body and terminating at said first and second ends; bushing means adapted to be inserted into said first and second end of said body; anchoring means extending through said body in said passage and extending beyond the ends of said body; said anchoring means further equipped with stop means to cooperatively interact with said bushing to limit movement of the body along said anchoring means.
---
paper_title: Visualization of large terrains made easy

paper_content:

We present an elegant and simple to implement framework for performing out-of-core visualization and view-dependent refinement of large terrain surfaces. Contrary to the recent trend of increasingly elaborate algorithms for large-scale terrain visualization, our algorithms and data structures have been designed with the primary goal of simplicity and efficiency of implementation. Our approach to managing large terrain data also departs from more conventional strategies based on data tiling. Rather than emphasizing how to segment and efficiently bring data in and out of memory, we focus on the manner in which the data is laid out to achieve good memory coherency for data accesses made in a top-down (coarse-to-fine) refinement of the terrain. We present and compare the results of using several different data indexing schemes, and propose a simple to compute index that yields substantial improvements in locality and speed over more commonly used data layouts.Our second contribution is a new and simple, yet easy to generalize method for view-dependent refinement. Similar to several published methods in this area, we use longest edge bisection in a top-down traversal of the mesh hierarchy to produce a continuous surface with subdivision connectivity. In tandem with the refinement, we perform view frustum culling and triangle stripping. These three components are done together in a single pass over the mesh. We show how this framework supports virtually any error metric, while still being highly memory and compute efficient.
---
paper_title: Terrain Simplification Simplified : A General Framework for View-Dependent Out-of-Core Visualization

paper_content:

We describe a general framework for out-of-core rendering and management of massive terrain surfaces. The two key components of this framework are: view-dependent refinement of the terrain mesh and a simple scheme for organizing the terrain data to improve coherence and reduce the number of paging events from external storage to main memory. Similar to several previously proposed methods for view-dependent refinement, we recursively subdivide a triangle mesh defined over regularly gridded data using longest-edge bisection. As part of this single, per-frame refinement pass, we perform triangle stripping, view frustum culling, and smooth blending of geometry using geomorphing. Meanwhile, our refinement framework supports a large class of error metrics, is highly competitive in terms of rendering performance, and is surprisingly simple to implement. Independent of our refinement algorithm, we also describe several data layout techniques for providing coherent access to the terrain data. By reordering the data in a manner that is more consistent with our recursive access pattern, we show that visualization of gigabyte-size data sets can be realized even on low-end, commodity PCs without the need for complicated and explicit data paging techniques. Rather, by virtue of dramatic improvements in multilevel cache coherence, we rely on the built-in paging mechanisms of the operating system to perform this task. The end result is a straightforward, simple-to-implement, pointerless indexing scheme that dramatically improves the data locality and paging performance over conventional matrix-based layouts.
---
paper_title: ROAMing terrain: Real-time Optimally Adapting Meshes

paper_content:

Terrain visualization is a difficult problem for applications requiring accurate images of large datasets at high frame rates, such as flight simulation and ground-based aircraft testing using synthetic sensor simulation. On current graphics hardware, the problem is to maintain dynamic, view-dependent triangle meshes and texture maps that produce good images at the required frame rate. We present an algorithm for constructing triangle meshes that optimizes flexible view-dependent error metrics, produces guaranteed error bounds, achieves specified triangle counts directly and uses frame-to-frame coherence to operate at high frame rates for thousands of triangles per frame. Our method, dubbed Real-time Optimally Adapting Meshes (ROAM), uses two priority queues to drive split and merge operations that maintain continuous triangulations built from pre-processed bintree triangles. We introduce two additional performance optimizations: incremental triangle stripping and priority-computation deferral lists. ROAM's execution time is proportional to the number of triangle changes per frame, which is typically a few percent of the output mesh size; hence ROAM's performance is insensitive to the resolution and extent of the input terrain. Dynamic terrain and simple vertex morphing are supported.
---
paper_title: Real-time, continuous level of detail rendering of height fields

paper_content:

We present an algorithm for real-time level of detail reduction and display of high-complexity polygonal surface data. The algorithm uses a compact and efficient regular grid representation, and employs a variable screen-space threshold to bound the maximum error of the projected image. A coarse level of simplification is performed to select discrete levels of detail for blocks of the surface mesh, followed by further simplification through repolygonalization in which individual mesh vertices are considered for removal. These steps compute and generate the appropriate level of detail dynamically in real-time, minimizing the number of rendered polygons and allowing for smooth changes in resolution across areas of the surface. The algorithm has been implemented for approximating and rendering digital terrain models and other height fields, and consistently performs at interactive frame rates with high image quality.
---
paper_title: Real-time optimal adaptation for planetary geometry and texture: 4-8 tile hierarchies

paper_content:

The real-time display of huge geometry and imagery databases involves view-dependent approximations, typically through the use of precomputed hierarchies that are selectively refined at runtime. A classic motivating problem is terrain visualization in which planetary databases involving billions of elevation and color values are displayed on PC graphics hardware at high frame rates. This paper introduces a new diamond data structure for the basic selective-refinement processing, which is a streamlined method of representing the well-known hierarchies of right triangles that have enjoyed much success in real-time, view-dependent terrain display. Regular-grid tiles are proposed as the payload data per diamond for both geometry and texture. The use of 4-8 grid refinement and coarsening schemes allows level-of-detail transitions that are twice as gradual as traditional quadtree-based hierarchies, as well as very high-quality low-pass filtering compared to subsampling-based hierarchies. An out-of-core storage organization is introduced based on Sierpinski indices per diamond, along with a tile preprocessing framework based on fine-to-coarse, same-level, and coarse-to-fine gathering operations. To attain optimal frame-to-frame coherence and processing-order priorities, dual split and merge queues are developed similar to the realtime optimally adapting meshes (ROAM) algorithm, as well as an adaptation of the ROAM frustum culling technique. Example applications of lake-detection and procedural terrain generation demonstrate the flexibility of the tile processing framework.
---
paper_title: BDAM - Batched Dynamic Adaptive Meshes for High Performance Terrain Visualization

paper_content:

This paper describes an efficient technique for out-of-core rendering and management of large textured terrain surfaces. The technique, called Batched Dynamic Adaptive Meshes (BDAM) , is based on a paired tree structure: a tiled quadtree for texture data and a pair of bintrees of small triangular patches for the geometry. These small patches are TINs and are constructed and optimized off-line with high quality simplification and tristripping algorithms. Hierarchical view frustum culling and view-dependent texture and geometry refinement is performed at each frame through a stateless traversal algorithm. Thanks to the batched CPU/GPU communication model, the proposed technique is not processor intensive and fully harnesses the power of current graphics hardware. Both preprocessing and rendering exploit out-of-core techniques to be fully scalable and to manage large terrain datasets.
---
paper_title: Visualization of large terrains made easy

paper_content:

We present an elegant and simple to implement framework for performing out-of-core visualization and view-dependent refinement of large terrain surfaces. Contrary to the recent trend of increasingly elaborate algorithms for large-scale terrain visualization, our algorithms and data structures have been designed with the primary goal of simplicity and efficiency of implementation. Our approach to managing large terrain data also departs from more conventional strategies based on data tiling. Rather than emphasizing how to segment and efficiently bring data in and out of memory, we focus on the manner in which the data is laid out to achieve good memory coherency for data accesses made in a top-down (coarse-to-fine) refinement of the terrain. We present and compare the results of using several different data indexing schemes, and propose a simple to compute index that yields substantial improvements in locality and speed over more commonly used data layouts.Our second contribution is a new and simple, yet easy to generalize method for view-dependent refinement. Similar to several published methods in this area, we use longest edge bisection in a top-down traversal of the mesh hierarchy to produce a continuous surface with subdivision connectivity. In tandem with the refinement, we perform view frustum culling and triangle stripping. These three components are done together in a single pass over the mesh. We show how this framework supports virtually any error metric, while still being highly memory and compute efficient.
---
paper_title: Terrain Simplification Simplified : A General Framework for View-Dependent Out-of-Core Visualization

paper_content:

We describe a general framework for out-of-core rendering and management of massive terrain surfaces. The two key components of this framework are: view-dependent refinement of the terrain mesh and a simple scheme for organizing the terrain data to improve coherence and reduce the number of paging events from external storage to main memory. Similar to several previously proposed methods for view-dependent refinement, we recursively subdivide a triangle mesh defined over regularly gridded data using longest-edge bisection. As part of this single, per-frame refinement pass, we perform triangle stripping, view frustum culling, and smooth blending of geometry using geomorphing. Meanwhile, our refinement framework supports a large class of error metrics, is highly competitive in terms of rendering performance, and is surprisingly simple to implement. Independent of our refinement algorithm, we also describe several data layout techniques for providing coherent access to the terrain data. By reordering the data in a manner that is more consistent with our recursive access pattern, we show that visualization of gigabyte-size data sets can be realized even on low-end, commodity PCs without the need for complicated and explicit data paging techniques. Rather, by virtue of dramatic improvements in multilevel cache coherence, we rely on the built-in paging mechanisms of the operating system to perform this task. The end result is a straightforward, simple-to-implement, pointerless indexing scheme that dramatically improves the data locality and paging performance over conventional matrix-based layouts.
---
paper_title: ROAMing terrain: Real-time Optimally Adapting Meshes

paper_content:

Terrain visualization is a difficult problem for applications requiring accurate images of large datasets at high frame rates, such as flight simulation and ground-based aircraft testing using synthetic sensor simulation. On current graphics hardware, the problem is to maintain dynamic, view-dependent triangle meshes and texture maps that produce good images at the required frame rate. We present an algorithm for constructing triangle meshes that optimizes flexible view-dependent error metrics, produces guaranteed error bounds, achieves specified triangle counts directly and uses frame-to-frame coherence to operate at high frame rates for thousands of triangles per frame. Our method, dubbed Real-time Optimally Adapting Meshes (ROAM), uses two priority queues to drive split and merge operations that maintain continuous triangulations built from pre-processed bintree triangles. We introduce two additional performance optimizations: incremental triangle stripping and priority-computation deferral lists. ROAM's execution time is proportional to the number of triangle changes per frame, which is typically a few percent of the output mesh size; hence ROAM's performance is insensitive to the resolution and extent of the input terrain. Dynamic terrain and simple vertex morphing are supported.
---
paper_title: Right-Triangulated Irregular Networks

paper_content:

We describe a hierarchical data structure for representing a digital terrain (height field) which contains approximations of the terrain at different levels of detail. The approximations are based on triangulations of the underlying two-dimensional space using right-angled triangles. The methods we discuss permit a single approximation to have a varying level of approximation accuracy across the surface. Thus, for example, the area close to an observer may be represented with greater detail than areas which lie outside their field of view. ::: ::: We discuss the application of this hierarchical data structure to the problem of interactive terrain visualization. We point out some of the advantages of this method in terms of memory usage and speed.
---
paper_title: Planet-sized batched dynamic adaptive meshes (P-BDAM)

paper_content:

We describe an efficient technique for out-of-core management and interactive rendering of planet sized textured terrain surfaces. The technique, called planet-sized batched dynamic adaptive meshes (P-BDAM), extends the BDAM approach by using as basic primitive a general triangulation of points on a displaced triangle. The proposed framework introduces several advances with respect to the state of the art: thanks to a batched host-to-graphics communication model, we outperform current adaptive tessellation solutions in terms of rendering speed; we guarantee overall geometric continuity, exploiting programmable graphics hardware to cope with the accuracy issues introduced by single precision floating points; we exploit a compressed out of core representation and speculative prefetching for hiding disk latency during rendering of out-of-core data; we efficiently construct high quality simplified representations with a novel distributed out of core simplification algorithm working on a standard PC network.
---
paper_title: Real-time, continuous level of detail rendering of height fields

paper_content:

We present an algorithm for real-time level of detail reduction and display of high-complexity polygonal surface data. The algorithm uses a compact and efficient regular grid representation, and employs a variable screen-space threshold to bound the maximum error of the projected image. A coarse level of simplification is performed to select discrete levels of detail for blocks of the surface mesh, followed by further simplification through repolygonalization in which individual mesh vertices are considered for removal. These steps compute and generate the appropriate level of detail dynamically in real-time, minimizing the number of rendered polygons and allowing for smooth changes in resolution across areas of the surface. The algorithm has been implemented for approximating and rendering digital terrain models and other height fields, and consistently performs at interactive frame rates with high image quality.
---
paper_title: An Integrated Global GIS and Visual Simulation System

paper_content:

This paper reports on an integrated visual simulation system supporting visualization of global multiresolution terrain elevation and imagery data, static and dynamic 3D objects with multiple levels of detail, non-protrusive features such as roads and rivers, distributed simulation and real-time sensor input, and an embedded geographic information system. The requirements of real-time rendering, very large datasets, and heterogeneous detail management strongly affect the structure of this system. Use of hierarchical spatial data structures and multiple coordinate systems allow for visualization and manipulation of huge terrain datasets spanning the entire surface of the Earth at resolutions well below one meter. The multithreaded nature of the system supports multiple windows with independent, stereoscopic views. The system is portable, built on OpenGL, POSIX threads, and X11/Motif windowed interface. It has been tested and evaluated in the field with a variety of terrain data, updates due to real-time sensor input, and display of networked DIS simulations.
---
paper_title: The Alps at your fingertips: virtual reality and geoinformation systems

paper_content:

Advocates a desktop virtual reality (VR) interface to a geographic information system (GIS). The navigational capability to explore large topographic scenes is a powerful metaphor and a natural way of interacting with a GIS. VR systems succeed in providing visual realism and real-time navigation and interaction, but fail to cope with very large amounts of data and to provide the general functionality of information systems. We suggest a way to overcome these problems. We describe a prototype system, called ViRGIS (Virtual Reality GIS), that integrates two system platforms: a client that runs the VR component interacts via a (local or wide area) network with a server that runs an object-oriented database containing geographic data. For the purpose of accessing data efficiently, we describe how to integrate a geometric index into the database, and how to perform the operations that are requested in a real-time trip through the virtual world.
---
paper_title: Real-time optimal adaptation for planetary geometry and texture: 4-8 tile hierarchies

paper_content:

The real-time display of huge geometry and imagery databases involves view-dependent approximations, typically through the use of precomputed hierarchies that are selectively refined at runtime. A classic motivating problem is terrain visualization in which planetary databases involving billions of elevation and color values are displayed on PC graphics hardware at high frame rates. This paper introduces a new diamond data structure for the basic selective-refinement processing, which is a streamlined method of representing the well-known hierarchies of right triangles that have enjoyed much success in real-time, view-dependent terrain display. Regular-grid tiles are proposed as the payload data per diamond for both geometry and texture. The use of 4-8 grid refinement and coarsening schemes allows level-of-detail transitions that are twice as gradual as traditional quadtree-based hierarchies, as well as very high-quality low-pass filtering compared to subsampling-based hierarchies. An out-of-core storage organization is introduced based on Sierpinski indices per diamond, along with a tile preprocessing framework based on fine-to-coarse, same-level, and coarse-to-fine gathering operations. To attain optimal frame-to-frame coherence and processing-order priorities, dual split and merge queues are developed similar to the realtime optimally adapting meshes (ROAM) algorithm, as well as an adaptation of the ROAM frustum culling technique. Example applications of lake-detection and procedural terrain generation demonstrate the flexibility of the tile processing framework.
---
paper_title: TerraVision II: Visualizing Massive Terrain Databases in VRML

paper_content:

To disseminate 3D maps and spatial data over the Web, we designed massive terrain data sets accessible through either a VRML browser or the customized TerraVision II browser. Although not required to view the content, TerraVision II lets the user perform specialized browser level optimizations that offer increased efficiency and seamless interaction with the terrain data. We designed our framework to simplify terrain data maintenance and to let users dynamically select particular sets of geo-referenced data. Our implementation uses Java scripting to extend VRML's base functionality and the External Authoring Interface to offer application-specific management of the virtual geographic environment.
---
paper_title: BDAM - Batched Dynamic Adaptive Meshes for High Performance Terrain Visualization

paper_content:

This paper describes an efficient technique for out-of-core rendering and management of large textured terrain surfaces. The technique, called Batched Dynamic Adaptive Meshes (BDAM) , is based on a paired tree structure: a tiled quadtree for texture data and a pair of bintrees of small triangular patches for the geometry. These small patches are TINs and are constructed and optimized off-line with high quality simplification and tristripping algorithms. Hierarchical view frustum culling and view-dependent texture and geometry refinement is performed at each frame through a stateless traversal algorithm. Thanks to the batched CPU/GPU communication model, the proposed technique is not processor intensive and fully harnesses the power of current graphics hardware. Both preprocessing and rendering exploit out-of-core techniques to be fully scalable and to manage large terrain datasets.
---
paper_title: Visualization of large terrains made easy

paper_content:

We present an elegant and simple to implement framework for performing out-of-core visualization and view-dependent refinement of large terrain surfaces. Contrary to the recent trend of increasingly elaborate algorithms for large-scale terrain visualization, our algorithms and data structures have been designed with the primary goal of simplicity and efficiency of implementation. Our approach to managing large terrain data also departs from more conventional strategies based on data tiling. Rather than emphasizing how to segment and efficiently bring data in and out of memory, we focus on the manner in which the data is laid out to achieve good memory coherency for data accesses made in a top-down (coarse-to-fine) refinement of the terrain. We present and compare the results of using several different data indexing schemes, and propose a simple to compute index that yields substantial improvements in locality and speed over more commonly used data layouts.Our second contribution is a new and simple, yet easy to generalize method for view-dependent refinement. Similar to several published methods in this area, we use longest edge bisection in a top-down traversal of the mesh hierarchy to produce a continuous surface with subdivision connectivity. In tandem with the refinement, we perform view frustum culling and triangle stripping. These three components are done together in a single pass over the mesh. We show how this framework supports virtually any error metric, while still being highly memory and compute efficient.
---
paper_title: Smooth view-dependent level-of-detail control and its application to terrain rendering

paper_content:

The key to real-time rendering of large-scale surfaces is to locally adapt surface geometric complexity to changing view parameters. Several schemes have been developed to address this problem of view-dependent level-of-detail control. Among these, the view-dependent progressive mesh (VDPM) framework represents an arbitrary triangle mesh as a hierarchy of geometrically optimized refinement transformations, from which accurate approximating meshes can be efficiently retrieved. In this paper we extend the general VDPM framework to provide temporal coherence through the run-time creation of geomorphs. These geomorphs eliminate "popping" artifacts by smoothly interpolating geometry. Their implementation requires new output-sensitive data structures, which have the added benefit of reducing memory use. We specialize the VDPM framework to the important case of terrain rendering. To handle huge terrain grids, we introduce a block-based simplification scheme that constructs a progressive mesh as a hierarchy of block refinements. We demonstrate the need for an accurate approximation metric during simplification. Our contributions are highlighted in a real-time flyover of a large, rugged terrain. Notably, the use of geomorphs results in visually smooth rendering even at 72 frames/sec on a graphics workstation.
---
paper_title: C-BDAM – compressed batched dynamic adaptive meshes for terrain rendering

paper_content:

We describe a compressed multiresolution representation for supporting interactive rendering of very large planar and spherical terrain surfaces. The technique, called Compressed Batched Dynamic Adaptive Meshes (C-BDAM), is an extension of the BDAM and P-BDAM chunked level-of-detail hierarchy. In the C-BDAM approach, all patches share the same regular triangulation connectivity and incrementally encode their vertex attributes using a quantized representation of the difference with respect to values predicted from the coarser level. The structure provides a number of benefits: simplicity of data structures, overall geometric continuity for planar and spherical domains, support for variable resolution input data, management of multiple vertex attributes, efficient compression and fast construction times, ability to support maximum-error metrics, real-time decompression and shaded rendering with configurable variable level-of-detail extraction, and runtime detail synthesis. The efficiency of the approach and the achieved compression rates are demonstrated on a number of test cases, including the interactive visualization of a 29 gigasample reconstruction of the whole planet Earth created from high resolution SRTM data.
---
paper_title: Terrain Simplification Simplified : A General Framework for View-Dependent Out-of-Core Visualization

paper_content:

We describe a general framework for out-of-core rendering and management of massive terrain surfaces. The two key components of this framework are: view-dependent refinement of the terrain mesh and a simple scheme for organizing the terrain data to improve coherence and reduce the number of paging events from external storage to main memory. Similar to several previously proposed methods for view-dependent refinement, we recursively subdivide a triangle mesh defined over regularly gridded data using longest-edge bisection. As part of this single, per-frame refinement pass, we perform triangle stripping, view frustum culling, and smooth blending of geometry using geomorphing. Meanwhile, our refinement framework supports a large class of error metrics, is highly competitive in terms of rendering performance, and is surprisingly simple to implement. Independent of our refinement algorithm, we also describe several data layout techniques for providing coherent access to the terrain data. By reordering the data in a manner that is more consistent with our recursive access pattern, we show that visualization of gigabyte-size data sets can be realized even on low-end, commodity PCs without the need for complicated and explicit data paging techniques. Rather, by virtue of dramatic improvements in multilevel cache coherence, we rely on the built-in paging mechanisms of the operating system to perform this task. The end result is a straightforward, simple-to-implement, pointerless indexing scheme that dramatically improves the data locality and paging performance over conventional matrix-based layouts.
---
paper_title: Space Filling Curves and Their Use in the Design of Geometric Data Structures

paper_content:

We are given a two-dimensional square grid of size N×N, where N∶=2n and n≥0. A space filling curve (SFC) is a numbering of the cells of this grid with numbers from c+1 to c+N2, for some c≥0. We call a SFC recursive (RSFC) if it can be recursively divided into four square RSFCs of equal size. Examples of well-known RSFCs include the Hilbert curve, the z-curve, and the Gray code.
---
paper_title: Virtual GIS: a real-time 3D geographic information system

paper_content:

Advances in computer graphics hardware and algorithms, visualization, and interactive techniques for analysis offer the components for a highly integrated, efficient real-time 3D Geographic Information System. We have developed "Virtual GIS", a system with truly immersive capability for navigating and understanding complex and dynamic terrain-based databases. The system provides the means for visualizing terrain models consisting of elevation and imagery data, along with GIS raster layers, protruding features, buildings, vehicles, and other objects. We have implemented window-based and virtual reality versions and in both cases provide a direct manipulation, visual interface for accessing the GIS data. Unique terrain data structures and algorithms allow rendering of large, high resolution datasets at interactive rates.
---
paper_title: Planet-sized batched dynamic adaptive meshes (P-BDAM)

paper_content:

We describe an efficient technique for out-of-core management and interactive rendering of planet sized textured terrain surfaces. The technique, called planet-sized batched dynamic adaptive meshes (P-BDAM), extends the BDAM approach by using as basic primitive a general triangulation of points on a displaced triangle. The proposed framework introduces several advances with respect to the state of the art: thanks to a batched host-to-graphics communication model, we outperform current adaptive tessellation solutions in terms of rendering speed; we guarantee overall geometric continuity, exploiting programmable graphics hardware to cope with the accuracy issues introduced by single precision floating points; we exploit a compressed out of core representation and speculative prefetching for hiding disk latency during rendering of out-of-core data; we efficiently construct high quality simplified representations with a novel distributed out of core simplification algorithm working on a standard PC network.
---
paper_title: Geometry clipmaps: terrain rendering using nested regular grids

paper_content:

Rendering throughput has reached a level that enables a novel approach to level-of-detail (LOD) control in terrain rendering. We introduce the geometry clipmap, which caches the terrain in a set of nested regular grids centered about the viewer. The grids are stored as vertex buffers in fast video memory, and are incrementally refilled as the viewpoint moves. This simple framework provides visual continuity, uniform frame rate, complexity throttling, and graceful degradation. Moreover it allows two new exciting real-time functionalities: decompression and synthesis. Our main dataset is a 40GB height map of the United States. A compressed image pyramid reduces the size by a remarkable factor of 100, so that it fits entirely in memory. This compressed data also contributes normal maps for shading. As the viewer approaches the surface, we synthesize grid levels finer than the stored terrain using fractal noise displacement. Decompression, synthesis, and normal-map computations are incremental, thereby allowing interactive flight at 60 frames/sec.
---
paper_title: Real-time optimal adaptation for planetary geometry and texture: 4-8 tile hierarchies

paper_content:

The real-time display of huge geometry and imagery databases involves view-dependent approximations, typically through the use of precomputed hierarchies that are selectively refined at runtime. A classic motivating problem is terrain visualization in which planetary databases involving billions of elevation and color values are displayed on PC graphics hardware at high frame rates. This paper introduces a new diamond data structure for the basic selective-refinement processing, which is a streamlined method of representing the well-known hierarchies of right triangles that have enjoyed much success in real-time, view-dependent terrain display. Regular-grid tiles are proposed as the payload data per diamond for both geometry and texture. The use of 4-8 grid refinement and coarsening schemes allows level-of-detail transitions that are twice as gradual as traditional quadtree-based hierarchies, as well as very high-quality low-pass filtering compared to subsampling-based hierarchies. An out-of-core storage organization is introduced based on Sierpinski indices per diamond, along with a tile preprocessing framework based on fine-to-coarse, same-level, and coarse-to-fine gathering operations. To attain optimal frame-to-frame coherence and processing-order priorities, dual split and merge queues are developed similar to the realtime optimally adapting meshes (ROAM) algorithm, as well as an adaptation of the ROAM frustum culling technique. Example applications of lake-detection and procedural terrain generation demonstrate the flexibility of the tile processing framework.
---
paper_title: C-BDAM – compressed batched dynamic adaptive meshes for terrain rendering

paper_content:

We describe a compressed multiresolution representation for supporting interactive rendering of very large planar and spherical terrain surfaces. The technique, called Compressed Batched Dynamic Adaptive Meshes (C-BDAM), is an extension of the BDAM and P-BDAM chunked level-of-detail hierarchy. In the C-BDAM approach, all patches share the same regular triangulation connectivity and incrementally encode their vertex attributes using a quantized representation of the difference with respect to values predicted from the coarser level. The structure provides a number of benefits: simplicity of data structures, overall geometric continuity for planar and spherical domains, support for variable resolution input data, management of multiple vertex attributes, efficient compression and fast construction times, ability to support maximum-error metrics, real-time decompression and shaded rendering with configurable variable level-of-detail extraction, and runtime detail synthesis. The efficiency of the approach and the achieved compression rates are demonstrated on a number of test cases, including the interactive visualization of a 29 gigasample reconstruction of the whole planet Earth created from high resolution SRTM data.
---
paper_title: Fast progressive image coding without wavelets

paper_content:

We introduce a new image compression algorithm that allows progressive image reconstruction - both in resolution and in fidelity, with a fully embedded bit-stream. The algorithm is based on bit-plane entropy coding of reordered transform coefficients, similar to the progressive wavelet codec (PWC) previously introduced. Unlike PWC, however, our new progressive transform coder (PTC) does not use wavelets; it performs the space-frequency decomposition step via a new lapped biorthogonal transform (LBT). PTC achieves a rate distortion performance that is comparable (within 2%) to that of the state-of-the-art SPIHT (set partitioning in hierarchical trees) codec. However, thanks to the use of the LBT, the space-frequency decomposition step in PTC reduces the number of multiplications per pixel by a factor of 2.7, and the number of additions by about 15%, when compared to the fastest possible implementation of the "9/7" wavelet transform via lifting. Furthermore, since most of the computation in the LBT is in fact performed by a DCT, our PTC codec can make full use of fast software and hardware modules for 1D and 2D DCT.
---
paper_title: An Integrated Global GIS and Visual Simulation System

paper_content:

This paper reports on an integrated visual simulation system supporting visualization of global multiresolution terrain elevation and imagery data, static and dynamic 3D objects with multiple levels of detail, non-protrusive features such as roads and rivers, distributed simulation and real-time sensor input, and an embedded geographic information system. The requirements of real-time rendering, very large datasets, and heterogeneous detail management strongly affect the structure of this system. Use of hierarchical spatial data structures and multiple coordinate systems allow for visualization and manipulation of huge terrain datasets spanning the entire surface of the Earth at resolutions well below one meter. The multithreaded nature of the system supports multiple windows with independent, stereoscopic views. The system is portable, built on OpenGL, POSIX threads, and X11/Motif windowed interface. It has been tested and evaluated in the field with a variety of terrain data, updates due to real-time sensor input, and display of networked DIS simulations.
---
paper_title: TerraVision II: Visualizing Massive Terrain Databases in VRML

paper_content:

To disseminate 3D maps and spatial data over the Web, we designed massive terrain data sets accessible through either a VRML browser or the customized TerraVision II browser. Although not required to view the content, TerraVision II lets the user perform specialized browser level optimizations that offer increased efficiency and seamless interaction with the terrain data. We designed our framework to simplify terrain data maintenance and to let users dynamically select particular sets of geo-referenced data. Our implementation uses Java scripting to extend VRML's base functionality and the External Authoring Interface to offer application-specific management of the virtual geographic environment.
---
paper_title: Planet-sized batched dynamic adaptive meshes (P-BDAM)

paper_content:

We describe an efficient technique for out-of-core management and interactive rendering of planet sized textured terrain surfaces. The technique, called planet-sized batched dynamic adaptive meshes (P-BDAM), extends the BDAM approach by using as basic primitive a general triangulation of points on a displaced triangle. The proposed framework introduces several advances with respect to the state of the art: thanks to a batched host-to-graphics communication model, we outperform current adaptive tessellation solutions in terms of rendering speed; we guarantee overall geometric continuity, exploiting programmable graphics hardware to cope with the accuracy issues introduced by single precision floating points; we exploit a compressed out of core representation and speculative prefetching for hiding disk latency during rendering of out-of-core data; we efficiently construct high quality simplified representations with a novel distributed out of core simplification algorithm working on a standard PC network.
---

Title: Survey of semi-regular multiresolution models for interactive terrain rendering

Section 1: Introduction
Description 1: This section introduces the significance and challenges of efficient interactive visualization of large digital elevation models (DEMs) and overviews the multiresolution methods for interactive terrain rendering.

Section 2: Background and motivation
Description 2: This section provides foundational concepts and motivations behind multiresolution terrain models, discussing the encoding, extraction, and rendering processes.

Section 3: Non-conforming and limited adaptivity techniques: tiled blocks and nested regular grids
Description 3: This section explores techniques based on non-conforming representations, focusing on tiled blocks and nested regular grids, and their implementation.

Section 4: Variable resolution triangulation using quadtree and triangle bin-tree subdivision
Description 4: This section examines methods based on quadtree and triangle bin-tree triangulation, emphasizing their ability to create continuous variable resolution surfaces.

Section 5: Quadtree triangulation
Description 5: This section details algorithms and data structures associated with quadtree-based adaptive triangulation, including restricted quadtrees and continuous LOD quadtree methods.

Section 6: Triangle bin-trees
Description 6: This section discusses triangle bin-tree-based triangulation methods, such as ROAM, RTIN, and related efficient data storage and processing approaches.

Section 7: Cluster triangulations
Description 7: This section describes recent techniques that use cluster-based triangulation approaches to optimize performance, covering various methods like tiled blocks, cached triangle bin-trees, and combining regular and irregular triangulations.

Section 8: LOD error metric
Description 8: This section reviews the major error metrics proposed for terrain triangulation algorithms, including object-space and image-space approximation errors.

Section 9: System issues
Description 9: This section addresses system-level aspects of terrain visualization, such as dynamic scene management, out-of-core data organization, and client-server architecture.

Section 10: Conclusions
Description 10: This section summarizes the survey, highlighting contributions, current trends, and open research problems in the field of multiresolution terrain rendering.