'Wherever I May Roam' by Metallica is good music when coding a landscape engine.
Systems that push the terrain data to a GPU focus on chunks of triangles to render for maximum speed.
Seamless Patches - 2007
Roam 2 - 2006
Geometry Clipmaps - 2004
- Clipmap based Loading and Rendering of Large Terrain Texture - 2012
- Terrain Rendering using Spherical Clipmaps - 2006
- Terrain rendering using GPU-based geometry clipmaps - 2005
- Extending a battlefield simulator with large scale terrain rendering and flight simulator functionality - 2005
- GPUG2: Terrain Rendering Using GPU-Based Geometry Clipmaps - 2005
- Geometry Clipmaps: Terrain Rendering Using Nested Regular Grids - 2004
- The Clipmap: A Virtual Mipmap - 1998
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.
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 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
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.
Rottger - 1998
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
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.
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.
- XNA Terrain - 2009
C99 heightmap utilities - 2012
XNA Large Terrain - 2010
Global Terrain - 2006
Procedural Landscapes - 2001
Large 3D Terrain Generator - 2018
Desertscape Simulation - 2019