Geometry
'Wherever I May Roam' by Metallica is good music when coding a landscape engine.
'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
Roam 2 - 2006
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.
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
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
ROAMing Terrain: Real-time Optimally Adapting Meshes - 1997. ROAM homepage
Lindstrom-Koller - 1996
Other
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.
XNA Terrain - 2009
Links
Simplified Terrain using Interlocking Tiles - 2016
Fast Terrain Rendering with Continuous Detail on a Modern GPU - , 2014
Terrain LOD for DirectX 10 Graphics Cards, using SlimDX and Direct3D 11 - 2013
C99 heightmap utilities - 2012
XNA Large Terrain - 2010
Continuous Distance-Dependent Level of Detail for Rendering Heightmaps - 2010
Continuous Distance-Dependent Level of Detail for Rendering Heightmaps (CDLOD) - 2010
Binary Triangle Trees for Terrain Tile Index Buffer Generation - 2006
http://www-evasion.imag.fr/Membres/Eric.Bruneton - 2006
Global Terrain - 2006
Rendering Very Large, Very Detailed Terrains - 2005
Procedural Landscapes - 2001
Large 3D Terrain Generator - 2018
Desertscape Simulation - 2019