Large-scale terrain algorithms
Entry posted by Rastar ·
10,167 views
Leadwerks has a very nice terrain system that allows terrains of up to 4096x4096 units (in version 3.1, 3.0 goes up to 1024x1024) that performs very well and has a pretty unique texturing method. For most game applications, this is more than enough - filling such an area with objects and interesting gameplay is already quite a challenge. But some game ideas still require larger terrains. In my case, I am pondering something similar to a racing game, taking place in real-world areas, where a single level features tracks of between 50 and 200km.
My testbed is the Mediterranean Island of Mallorca, which is about 80x80 km in size. The image above shows its general topology, with its digital elevation data loaded into World Machine, a very nice terrain generator (more on this in another post). To render something like this with sufficient close-view detail, but still provide panoramic views (e.g. down a mountain pass) at acceptable frame rates is quite a challenge. Fortunately, there are a couple of algorithms that have been developed for just that. I'll list a few that I know of and of course would be interested to hear of others.
Chunked LOD
Pretty old but still in heavy use is the Chunked LOD algorithm of T. Ulrich (see http://tulrich.com/geekstuff/chunklod.html, where you can also find C++ sources of an implementation). In its typical incarnation it works off a heightmap and generates a quadtree of meshes for it, based on a simple level of detail calculation. So, at the root of this tree is a very coarse representation of the complete terrain, which is divided into 4 child nodes of the same basic patch size (e.g. 256x256) and correspondingly higher level of detail. Every of those child patches has four children with... and so on. These patches are created during design time and are tessellated according to the underlying terrain structure - fewer vertices for flat planes, more for rugged mountains.
During run-time, the Chunked LOD algorithm selects levels from the quad-tree based on a simple screen space error calculation. This will lead to patches of different detail levels lying next to each other and correspondingly to T-junctions - vertices of one patch lying on an edge of the next level. The resulting visible cracks in the surface have to be covered, usually by adding a small, angled skirt around every patch. In addition, to avoid a sudden popping of vertices when changing for lower or higher detailed patches, vertices are slowly "morphed" to their final position.
The Chunked LOD method, though pretty old, still has a few advantages:
- the meshes are optimally tessellated, so you don't create vertices where you don't need them (flat areas)
- it works on legacy hardware, even mobile devices (though it's of course questionable if rendering such a large terrain on a phone really makes sense). Most other algorithms make use of displacing a heightmap in the vertex shader, and the corresponding GLSL functions (texture or textureLod) aren't available in the vertex shader for lower-end devices.
But, as always, there are also many significant disadvantages:
- the preprocessing step (creating the mesh quad-tree) is quite time-consuming
- a lot of data has to be stored on disk (all three coordinates of the vertices plus additional morph data for the morphing algorithm)
- all those meshes have to be transferred from the CPU to the GPU
Geo Clipmapping
In the set of algorithms using heightmap displacement in the vertex shader, the geometry clipmaps approach of Losasso and Hoppe is a particularly interesting one (see http://research.microsoft.com/en-us/um/people/hoppe/geomclipmap.pdf or their GPU Gems 2 article http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter02.html). They construct a set of base mesh patches arranged in concentric rings around the viewer, with higher vertex density close to the viewer and fewer vertices farther away. Those base patches are reused, being only scaled and moved, so very few vertex buffers actually have to be sent to the GPU. Together with an algorithm for updating the heightmap being used for vertex displacement (thus taking care of viewer movement), this is a very efficient rendering method since it uses only a few static vertex and index buffers and most work is done on the GPU.
Among the set of six different patch types being used there is also a strip of degenerate triangles (ie triangles whose three vertices lie on a line). Their job is to cover T-junctions between adjacent rings. Remaining discontinuities in geometry (and texturing) are covered in the shaders by smoothly blending between values in a transition region.
In their paper, the authors also describe an interesting method for efficiently compressing and reconstructing heightmaps, which can be used for any heightmap-based approach and which I'll cover in a separate post. As an example, they managed to compress the USGS height data for the complete USA (a dataset of 40 GB) to just 355MB.
As a sidenote, if I remember correctly Josh once mentioned that the new "virtual megatextures" for the Leadwerks terrain use a similar approach.
Advantages:
- pretty fast rendering of large terrains
- minimal preprocessing
- small data size - just the heightmap, also only very few and small static buffers on the GPU
- good visual continuity
Disadvantages:
- doesn't run on legacy hardware (Shader model 2.0 and below)
- fixed amount of triangles, so a flat plane might be rendered using thousands of triangles while a rugged mountain might be represented by large, stretched triangles
CDLOD
Then there is the "Continuous Distance-Dependent Level of Detail" approach (see http://www.vertexasylum.com/downloads/cdlod/cdlod_latest.pdf). I must confess I haven't looked too deeply into this. As I understand, it is somewhat of a mixture between the quadtree structure of Chunked LOD and the heightmap displacement of geo clipmapping.
Real-time tessellation on the GPU
Finally we're coming to the title of this blog... Tessellation on the GPU can also be used for terrain rendering. While not a "large scale" approach itself, it of course can help to improve other algorithms by doing an optimal tessellation during run-time, based on both camera position and terrain structure. In addition, the generated mesh can be made water-tight, so you don't have to deal with cracks and T-junctions. An example of such an algorithm was described by N. Tatarchuk in the Advanced ShaderX 7 book ("Dynamic Terrain Rendering on GPUs using Real-Time Tessellation"). They start with a coarse, regular mesh and then render the terrain in two passes: First they render the heightmap as a point cloud to a buffer and use that information in a second pass to optimally tessellate the terrain.
OK - what's next?
What I'm going to try over the next couple of blog posts is a mixture of two approaches: A geometry clipmapping approach, but with a simpler patch structure and coarser grid. Tessellation will then be used to make the mesh water-tight and create an optimally structured mesh. I will move slowly, because many required techniques are still new to me, but if this is of interest to you - stay tuned!
-
6
8 Comments
Recommended Comments