Terrain LOD: Runtime Regular-Grid Algorithms

Academic Papers

• GPU-Aware Hybrid Terrain Rendering, 2012
  • C. Dick, J. Krüger, R. Westermann (Munich, Saarbrucken), builds on their previous work (2009)
  • "rasterization and ray-casting in every frame simultaneously to determine eye ray intersections"
  • "shifts workloads flexibly between the triangle setup stage and the parallel execution units, depending on the GPU capacities"
  • As is frequently the case with modern papers, there is no algorithms or pseudocode or shader code, just a high-level overview of the approach.
• Continuous Distance-Dependent Level of Detail for Rendering Heightmaps (CDLOD), 2010
  • by Filip Strugar, originally published in journal of graphics, gpu, and game tools, 2009
  • GPU-based rendering, quadtree based, smooth geomorphing based on predictable detail across LODs.
  • Supports dynamic loading/paging of large datasets.  No skirts.
  • Supports all graphics hardware with Shader Model 3.0 and above.
  • Demo and complete DirectX source code is available under a free software license.
• GPU Ray-Casting for Scalable Terrain Rendering, Eurographics 2009
  • C. Dick, J. Krüger, R. Westermann (Munich, Utah)
  • The authors started with an existing terrain rendering system, which handles very large out-of-core datasets using a quadtree, and replaced the rendering portion with a GPU-based ray-casting algorithm.  There are many complex multi-pass operations, e.g. to exploit occlusion.  It performs well in certain cases with very high-resolution data with multiple height samples per on-screen pixel, but poorly (compared to normal rasterization) with higher screen resolutions and lower DEM resolutions.
  • No known public implementation.
  • Based on a terrain rendering system described in this paper:
    •  Efficient Geometry Compression for GPU-based Decoding in Realtime Terrain Rendering, 2009
    • C. Dick, J. Schneider, R. Westermann (Munich)
    • Terrain tiles of 512x512, pre-meshed quadtree, geometry is compressed using 2 bits per triangle for the topology, cracks between tiles are "fixed" using flanges/skirts.  Entire thing is then uploaded to the GPU, decoded, and rendered, with extensive caching.
• Seamless Patches for GPU-Based Terrain Rendering, WSCG 2007
  • Yotam Livny, Zvi Kogan, Jihad El-Sana (Ben-Gurion University)
  • Yet another approach using a quadtree, with the unusual approach of handling each quad as four right triangles, each whose resolution is chosen to match its neighbor, with a triangle strip running down the seam to stitch them together.
  • Claims to "balance computation load among the CPU and GPU and dramatically reduces the communication between them", sending elevation as a vertex texture via Fragment Buffer Object extensions (FBO).
  • Integrates paging of elevation from disk and texture LOD as well.
• Survey on Semi-Regular Multiresolution Models for Interactive Terrain Rendering, 2007
  • R. Pajarola, E.Gobbetti, 2007
  • A survey paper giving an overview of all the various semi-regular terrain LOD approaches: "models based on tiled blocks and nested regular grids, quadtrees and triangle bin-trees triangulations, as well as cluster-based approaches... LOD error metrics and system-level data management aspects of interactive terrain visualization, including dynamic scene management, out-of-core data organization and compression, as well as numerical accuracy".  Journal link.
• Terrain Rendering using Spherical Clipmaps, Eurographics 2006
  • Malte Clasen and Hans-Christian Hege (Zuse Institute Berlin)
  • extends Asirvatham's paper Terrain rendering using GPU-based geometry clipmaps to handle spherical planets, using an ambitious, novel approach which pushes a GPU to it limits
  • spherical coordinates centered at the viewpoint produce concentric rings of detail of increasing size, so unlike nearly every other LOD approach, there are no problems with gaps between adjacent areas of differing LOD
  • however, this requires doing plenty of math on the GPU, including trig functions, and a vertex texture lookup which is (as of 2006) only available on new, high-end NVidia cards
  • the bottleneck is the vertex texture lookup, which the authors feel might be solved in future GPUs by a unified shader architecture
• GPU-Friendly High-Quality Terrain Rendering Journal of WSCG 2006
  • J. Schneider, R. Westermann (Technische Universität München)
  • divides the terrain into a flat array of 257x257 tiles, uses ribbons of "zero area polygons" to fill the gaps between tiles
  • GPU programming is used to decode vertices as 9 bits X, 9 bits Y, 14 bits Z for total of 2 bytes
  • re-use of vertices and progressive transmission of vertices and indices for less bus traffic and better GPU cache behavior
  • paging is done with complex memory management, implemented as a mixture between a last recently used
    (LRU) and a tightest fit (TF) strategy
  • the primitive used is indexed triangle fans
• Terrain Rendering Engine (TRE): Cell Broadband Engine Optimized Real-time Ray-caster, 2005
  • intriguing paper on a unconventional approach: ray-casting (simpler than ray-tracing) using the Cell distributed-processing architecture to achieve realtime framerates
  • the special hardware consists of a Cell Broadband Engine (CBE) with one dual-threaded Power Processor Element (PPE) with eight SIMD Synergistic Processor Elements (SPE)
  • interestingly, there are no triangles involved at all in the rendering, just rays and heightfields
• Adaptive Streaming and Rendering of Large Terrains using Strip Masks, 2005
  • describes a very simple paging approach using a simple grid of tiles, each containing a simple 'strip mask'
  • boundary gaps are filled using a "texture shadow plane" which has the ground texture repeated just below the terrain
  • although crude, this works fairly well for very light devices such as PDAs
• Rendering Procedural Terrain by Geometry Image Warping. Eurographics 2004
  • C. Dachsbacher, M. Stamminger (University of Erlangen-Nuremberg)
  • describes a way to use the GPU to do most of the work with both CLOD and procedural detail
  • one very interesting step is the calculation of an "importance map" which factors distance, frustum and terrain surface characteristics
  • the procedural detail is a fairly straightforward noise function
  • no known public implementation
• Geometry clipmaps: Terrain rendering using nested regular grids. Siggraph 2004
  • F. Losasso, H. Hoppe (Stanford, Microsoft)
  • applies the concept of texture clipmaps to regular grid elevation, using the GPU to smooth the transitions between detail levels
  • simplifies purely on distance, so it doesn't fit high-contrast terrain well, but polygon count can be pushed so high on modern hardware that it doesn't visually matter
  • the clipmap construction allows compression, so that they can claim a memory usage of only 0.1 bytes per heixel, or less!
  • follow-on paper: Terrain rendering using GPU-based geometry clipmaps, 2005, A. Asirvatham, H. Hoppe.
    • an extension of the previous algorithm to perform nearly all computations on the GPU itself, thereby reducing CPU load
    • the technique is "easy to implement" although it requires an NVidia GeForce6-class card, and there is no public implementation
    • this paper also appears in the "GPU Gems 2" book
  • related paper: Terrain Rendering Using Geometry Clipmaps, Nick Brettell, 2005
    • Nick implements the Losasso/Hoppe paper, as well a several others, and compares their relative strengths and weaknesses.  However, there is no public implementation.
• Planet-Sized Batched Dynamic Adaptive Meshes (P-BDAM), IEEE Visualization 2003
  • Paolo Cignoni, Fabio Ganovelli, Enrico Gobbetti, Fabio Marton, Federico Ponchio, and Roberto Scopigno of  ISTI-CNR and CRS4 VCG
  • claims: a batched host-to-graphics communication model which outperforms other adaptive tessellation solutions, guaranteed overall geometric continuity, exploits programmable graphics hardware, a compressed out of core representation and speculative prefetching for hiding disk latency
  • the tessellation structure is topologically like a normal RTIN, but the vertex locations are allowed to leave the grid for more efficiency
  • significant pre-computation is required
  • an extension of: BDAM - Batched Dynamic Adaptive Meshes for High Performance Terrain Visualization, 2003
  • The open-source project RATMAN contains an implementation of BDAM (see Government / Academic Terrain Projects)
  • followup paper:
    • C-BDAM - Compressed Batched Dynamic Adaptive Meshes for Terrain Rendering, 2006
    • long list of claimed features and 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"
• Real-time Terrain Rendering using Smooth Hardware Optimized Level of Detail, 2003 [pdf]
  • B. D. Larsen, N. J. Christensen, Technical University of Denmark
  • based on a regular grid, quadtree of triangulated tiles, with a hardware vertex program to do geomorphing on each vertex
  • there is no significant difference in the framerates with or without morphing which indicates that the morphing feature does not cause a performance penalty when vertex programs are implemented in hardware
  • each tile is loaded into a display list, created as needed based on LOD of surrounding tiles, rather than created each frame, to further cut down on CPU usage and improve triangle throughput
  • their implementation enforces the constraint that two adjacent tiles may not differ by more than 1 LOD
  • their test implementation uses OpenGL and the NVidia vertex API on a GeForce 3
• Diamond Terrain Algorithm: CLOD for Height Fields, 2001
  • Henri Hakl, University of Stellenbosch
  • based on frame-coherent ROAM, with an alternative geometric structure: triangle quadtrees
  • claims: better for triangle strips, fewer split and merge operations
  • uses 4 LIFO buffers instead of priority queues
  • T-junctions are avoided with ad hoc splits that are not inherent in the geometric structure
• Visualization of Large Terrains Made Easy, 2001
  • Peter Lindstrom, Valerio Pascucci, LLNL, in Proceedings of IEEE Visualization 2001
  • mentions, and draws on, virtually every CLOD paper to date, including Lindstrom's previous work, ROAM, Hoppe's papers, and interestingly, prominent use of Jonathan Blow's nested spheres.
  • the two main innovations claimed are an efficient memory indexing scheme for better paging performance, and a new split/cull/stripping pass
  • claims that previous approaches have been overly complicated, and offers a new way which is "simple" and "easy to implement", yet still looks quite complicated
• Terrain Rendering at High Levels of Detail (pdf), 2000 
  • presented at GDC 2000 by Jonathan Blow
  • summarizes the Lindstrom-Koller and ROAM approaches, then proposes a major improvement in how to treat the ROAM error metric, by looking at the variance as a spherical isosurface around each vertex
  • best understood by looking at the illustrations in his slides for the lecture; browse all his writings to find them
  • the benefit applies (only?) to frame-coherent ROAM implements
  • Jonathan discusses his approach vs. split-only ROAM
• Real-Time Generation of Continuous Levels of Detail for Height Fields 1998
  • by Stephan Röttger, W. Heidrich, Ph. Slusallek, H.-P. Seidel (University of Erlangen-Nuremberg)
  • uses a quadtree which corresponds to the height grid
  • very low memory requirement (height value + 1 byte)
  • supports geomorphing
  • recommends using triangle fans, centered around each parent vertex, as an efficient way to render a vertex quadtree
  • an open-source implementation is available which is very fast and extensible to paging of large elevation grids
• ROAMing Terrain: Real-time Optimally Adapting Meshes, 1997
  • primary paper by Mark Duchaineau et al, from IEEE Visualization '97 Proceedings
  • features claimed:
    • optimizes flexible view-dependent error metrics,
    • produces guaranteed error bounds,
    • achieves specified triangle counts directly,
    • uses frame-to-frame coherence to operate at high frame rates
  • new site now has extensive implementation notes and Unix source!
• TopoVista / Right Triangular Irregular Networks (ps), 1997
  • by Will Evans and Gregg Townsend at the University of Arizona
  • uses ~12 bytes/vertex, plus the grid of elevation values, so typically 14 bytes/vertex total
  • uses a sophisticated storage approach which avoids having to allocate the entire (2ⁿ+1)² array
  • includes an example program with complete, functional source code
    • the sample program is designed to illustrate the LOD simplification
    • it isn't optimized for rendering speed, e.g.. they generate normals on the fly

Articles and Presentations Describing Algorithms

• XNA Large Terrain, 2010 by "skytiger"
  • A completely modern approach which uses a vertex shader to transform world-space positions into texture-space, sample the height map using VTF (Vertex Texture Fetch) and displace the height of the mesh, then use on-the-fly interpolation to smooth the result.
  • The result: "Uses almost no CPU, no CPU-to-GPU bandwidth, and is very GPU friendly! There is no need for quadtrees, octrees, clipmaps, roam or dynamic mesh generation."
  • There are demonstration videos but no source code.
• Chunked LOD: Rendering Massive Terrains using Chunked Level of Detail Control (pdf)
  • Thatcher Ulrich, presented at the at the "Super-size it! Scaling up to Massive Virtual Worlds" course at SIGGRAPH 02
  • uses a quadtree of "chunks", where each chunk is a rectangular, precomputed section of optimized geometry, and "skirts" to fill cracks rather than force each chunk edge to match
  • from the paper, advantages of this approach:
    • Low CPU overhead and high triangle throughput.
    • Efficient use of triangles within aggregates.
    • Texture LOD integrated with geometry LOD.
    • Easy to integrate with out-of-core storage.
    • Efficient, smooth vertex morphing; no vertex pops.
    • Low CPU load, even when viewpoint moves rapidly.
  • disadvantages:
    • Non-trivial preprocessing required.
    • Data set must be static.
    • Uses more triangles than a primitive-level algorithm, for the same screen-space error.
    • Some data size overhead, depending on lossiness of preprocessing.
• Continuous LOD Terrain Meshing Using Adaptive Quadtrees, 2000
  • Gamasutra article by Soul Ride author Thatcher Ulrich
  • his approach uses a single quadtree of 3x3 blocks, with the LOD computation performed directly on each block
  • the "tree of blocks" approach allows for memory to be used sparsely, only where needed, instead of a single monolithic vertex array
  • it's handling an area of 64K x 64K meters, yet allows the finest grid data to be 1m x 1m in selected areas
  • memory usage is typically around 12 bytes/vertex
• Real-Time Dynamic Level of Detail Terrain Rendering with ROAM, 2000
  • Gamasutra article by Bryan Turner
  • describes the Seumas McNally Treadmarks algorithm (split-only ROAM)
  • more references: an interview with Seumas, archived message board snippets, and a gamedev article: Binary Triangle Trees and Terrain Tessellation
• Fast Terrain Rendering Using Geometrical MipMapping, 2000
  • flipcode article by Willem H. de Boer
  • a quadtree LOD approach, like Röttger's but has less detail about how LOD levels are managed to avoid cracks
  • introduces a very direct analogy of texture MipMapping to terrain LOD, called GeoMipMaps
  • related paper: Real-Time Visualization of Large Textured Terrains, 2005
    • Anders Brodersen, University of Aarhus
    • Claims to extend Boer's GeoMipMaps with efficient paging of large textures.  However, the texture handling is barely described (one small sub-section in section 5 of the paper).  No known public implementation exists.

Older Papers / Presentations

• Procedural Landscapes
  • presentation at GDC 2001 by Glenn Corpes
  • includes a description of a regular-grid LOD algorithm which:
    • makes heavy use of precomputed vertex buffers, for each possible LOD tile
    • deals with edge conditions by storing each possible permutation of LOD differences
    • the precomputed LOD only varies by a maximum of .5 on adjacent cells - this condition is assured by walking through the map and dragging the LOD of high detail cells' neighbors up.
• A Fast Algorithm For Large Scale Terrain Walkthrough, 2001 (pdf)
  • Youbing Zhao, Ji Zhou, Jiaoying Shi, Zhigeng Pan
  • contains a good overview of the other papers on the subject
  • briefly describes a CLOD approach which prevents cracks by allowing T-junctions (!)
• Real-time Continuous LOD for PCs and Consoles (.ppt), 2000 [no longer online]
  • presented at GDC 2000 by Louis Castle et al. (Westwood Studios)
  • based on Röttger's paper above, extends it with:
    • Simplified quadtree subdivision: fewer subdivision tests and simpler code
    • Linked quadtree storage: rather than in a height-field-sized grid
  • what they call a "optional detail map" is considered a fundamental requirement ("variance") by other algorithms
  • the "detail map" is a rather crude workaround for the problem that their split metric is based only on distance
• Large Scale Terrain Visualization Using The Restricted Quadtree Triangulation, 1998
  • Renato Pajarola, IEEE Visualization '98
  • the approach looks very similar to Lindstrom-Koller '96, cleaned up a little and fleshed out, and made unambiguously top-down
• Lindstrom-Koller, 1996
  • main paper: Real-Time, Continuous LOD Rendering of Height Fields, Siggraph 1996
  • by David Koller and Peter Lindstrom
  • based on a square regular grid (power-of-2-plus 1)
  • structured as a dual quadtree of vertices (each vertex has 4 children and 2 parents)
  • related paper: Level-of-Detail Management for Real-Time Rendering of Photo-textured Terrains, same authors
• Fast Multiresolution Surface Meshing (postscript), 1995
  • M. H. Gross, R. Gatti, O. Staadt, Proceedings of the IEEE Visualization '95
  • a very math-intensive paper which uses a wavelet approach
  • doesn't use RTINs, but rather a lookup-table of special cases to handle detail transitions