Geometry

'Wherever I May Roam' by Metallica is good music when coding a landscape engine.

The common source format of a terrain is often in the form of a heightmap. Then one of the algorithms below is used to render the terrain. Besides the geometry the terrain then needs a material.

Summary

Modern Algorithms for Real-Time Terrain Visualization on Commodity Hardware - 2010

Adaptive GPU-based terrain rendering - 2008

Chunk Algorithms

Systems that push the terrain data to a GPU focus on chunks of triangles to render for maximum speed.

Seamless Patches - 2007

- Seamless Patches for GPU-Based Terrain Rendering - 2007

Roam 2 - 2006

Realtime Optimal Adaptation for Planetary Geometry and Texture: 4-8 Tile Hierarchies

Geometry Clipmaps - 2004

Dynamic Adaptive Meshes - 2003

BDAM, P-BDAM and C-BDAM.

Chunked LOD - 2002

As a preprocess step the terrain is split with a quad tree. At each level in the tree there is an independent mesh generated. At the root level the mesh cover the whole terrain and each child in turn split the terrain it in smaller pieces with more and more detail. When rendering the quad-tree is used for culling and to select and what level of the tree to render for each area. To hide visible cracks between meshes each chunk has a vertical 'shirt' around the perimeter. The top of the shirt match the chunk edge and the bottom of the shirt goes down far enough to always cover any cracks between edges. To improve the quality of the LOD switch one can add support to morph between LOD levels. In the preprocess step each mesh stores the distance each vertex needs to move to fit it's less detailed LOD.

- RT3DCD: Chapter 8 Tiled geometry techniques. p 170-189. - 2003
- Rendering Massive Terrains using Chunked LOD - 2002. Chunked LOD Web

Geometrical Mip-Mapping - 2000

The terrain is split up into square chunks of the same size. A quad-tree is used to cull the non visible chunks and to set the LOD level that will be used on the visible chunks. It also makes sure that no chunk is more then one lod level away from the lod of any of it's neighbors. A chunk is drawn using a index buffer. Each LOD has it's own index buffer and uses half the vertices along each side then the lod before it. So LOD0 is full detail and use all the vertices in the chunk to form triangles. LOD1 use every other vertex and LOD2 every forth vertex and so on. Each LOD will have a 1/4 of the triangles then the previous one. Hiding seams between diffent lod levels are done by selecting a variation of the lod index buffer. This variations have extra triangles one each side that are towards a higher lod. If there is a max difference in one lod level between chunks there are not that many variations needed. The triangle count for a 17x17 vertices mesh is for LOD0: 512, LOD1: 128, LOD2: 32, LOD3: 8 and LOD4: 2.

- Tech Feature: Terrain geometry - 2010
- GPG2 : Simplified Terrain using interlocking tiles. p 377-383. - 2005
- RT3DCD: Chapter 8 Tiled geometry techniques. p 189-195. - 2003
- Fast Terrain Rendering Using Geometrical MipMapping - 2000

Triangle Algorithms

Triangle algorithms focus on the invidiual triangles. Avoiding drawing a single triangle can be a win when software rendering is used. With GPU's now available for everyone these are now less useful. The focus is now on the chunk algorithms that work on groups of triangles.

SOAR - 2001

- Galfar's Lair: Soar - 2005
- SOAR: Visualization of Large Terrains Made Easy - 2001

LOD using Adaptive Quadtrees - 2000

A quad tree is used to subdivide the terrain down to a selected level. The data for the terrain can be stored in the tree so only areas of high detail consume memory.

- Continuous LOD Terrain Meshing Using Adaptive Quadtrees - 2000

Rottger - 1998

Real-Time Generation of Continuous Levels of Detail for Height Fields

Real-time optimally adapting mesh - 1997

Roam is a algorithm that each frame optimize the terrain mesh based on the current viewpoint. As a preprocess the terrain is turned into a triangle binary tree, or bintree. All the triangles in the tree is isosceles right triangles. Each tree level from the root is formed by recursively splitting each triangle in the middle from the apex vertex to the midpoint of the base edge. When all levels have been created an error value is calculated for each triangle.

Each frame the algorithm optimises the mesh from the previous frame using the viewer’s position and orientation. Using the bintree it split or merge triangles in the mesh to get the minimal visible error from the viewers position.

- RT3DCD: Chapter 7 The roam terrain system. p 154-168 - 2003
- Real-Time Dynamic Level of Detail Terrain Rendering with ROAM - 2000
- Terrain Rendering at High Levels of Detail - 2000
- Terrain Rendering Research for Games - 2000
- Binary Triangle Trees and Terrain Tessellation - 1999
- ROAMing Terrain: Real-time Optimally Adapting Meshes - 1997. ROAM homepage

Lindstrom-Koller - 1996

- Large Scale Terrain Visualization Using The Restricted Quadtree Triangulation - 1998
- Real-Time, Continuous LOD Rendering of Height Fields - 1996

Other

- Smooth View-Dependent Level-of-Detail Control and its Application to Terrain Rendering - 1998

Other

Horizon line - 1988

If the world is flat like in a ancient flight simulator the only thing needed is a horizon. The horizon is a line that split the view and color one side with the ground and the other side with the sky. Green and blue are the common ones. Extra points is awarded for a gradient sky. The horizon is really a circle but one have to get really high to notice it. Only rotation of the view is needed to position the horizon line. It's hard to judge the distance to the ground in a flat world so it makes sense to add some classic pyramid mountains.

Static -

This algorithm is simple to grasp, you draw the whole mesh. Upload all of it to the GPU and then draw away without any other worries to think of. For this to work it makes sense to run a optimize step on the terrain mesh first. That way triangles are only used where they are really needed. This algorithm returns as the ultimate answer to terrain rendering each time a new faster graphic card generation is released. Then everyone start to add more details to the terrain and the old and newer algorithms are needed again.