CDLOD Terrain 🗻
Continuous Distance-Dependent Level of Detail
Svante Lindgren 2020-06-13
Introduction
CDLOD divides the terrain area into a uniform quadtree. The different levels of the tree represents a different LOD, the further down the tree the lower the LOD.
At run-time before each frame is rendered the program selects the appropriate nodes for the given LOD ranges. Each selected node will then be rendered by covering it's area by one unique mesh grid with a given resolution. The terrain height information will be retrieved for each vertex in the vertex shader for every draw call.
Defining LOD ranges
When selecting which nodes to draw we need to know which LOD we want within a certain distance.
Since the areas in the quadtree are always divided by four going down the tree we want the LOD ranges to increase by a factor of two. This will decrease the probability of a node to cover more than one LOD range at once, which we want to avoid.
float _minLodDistance = 15.0f;
static const int _lodLevels = 10;
float _lodRanges[_lodLevels];
for (int i = 0; i < _lodLevels; i++){
_lodRanges[i] = _minLodDistance * pow(2, i);
}
Selecting nodes to draw
Before each frame we want to select all the smallest nodes that are within LOD0 distance and all the second smallest nodes that are within LOD1 and so on.
We do this by traversing from the top node downards and only selecting the nodes that are within the correct LOD range. We also need to handle the nodes that cover more than one LOD range by selecting its children.
To make the distance calculations to the nodes more accurate, it is good to add the correct height for the node bounding boxes. This is done by sampling the height map while creating the quadtree.
// Call function using top node, going from lodlevel _treeDepth - 1
// down to zero.
void selectLods(Node* node, int lodLevel){
// If _treeDepth is greater than _lodLevels traverse down tree.
if(lodLevel > _lodLevels){
for (Node* child : node->_children){
selectLods(child, _lodRanges, lodLevel - 1);
}
return true;
}
if(!node->_boundingBox.sphereIntersect(_lodRanges[lodLevel])){
// Skip nodes node not intersecting current lodrange.
return false;
}
if(!node->_boundingBox.frustumIntersect(_cameraFrustum)){
// Skip nodes node not visible to camera.
return true;
}
if(lodLevel == 0){
// Always add LOD0 within range.
AddNoteToDrawList(node);
return true;
}else{
if(!node->_boundingBox.sphereIntersect(_lodRanges[lodLevel - 1])){
// We now know this node is only covering one lodrange.
// Add node to draw list.
AddNoteToDrawList(node);
}else{
// If node is within LOD and also within range of LOD - 1
// we add children of node that only covers LOD and skip
// children that covers LOD - 1
for (Node* child : node->_children){
if(!selectLods(child, _lodRanges, lodLevel - 1)){
// Add child to draw list that doesn't cover LOD - 1
AddNoteToDrawList(child);
}
}
}
}
return true;
}
Morphing between LODs
To remove holes in the geometry between different LODs we morph lower LODs into a higher one when a vertex is close to its LOD range edge. This is all done within the vertex shader and to do this we need to know the mesh grid dimension, the vertex position in the grid mesh and the vertex LOD level.
Below you can see how the grid will morph into a less detailed version of itself.
We want to start morphing a vertex when it is about 50% to 30% percent away from the LOD edge. In this example we will use 50%. To get the morph value we calculate where the vertex is located between the LOD levels and then return what morph value that position corrisponds two.
In this case a morph value of zero when the vertex is halfway in between the LOD ranges and morph value 1.0 when its at the higher LOD distance.
// Calculates the morph value from 0.0 to 1.0 given the distance
// from the camera to the vertex, and the current LOD level.
float getMorphValue(float dist){
float low = 0.0;
if(lodLevel != 0){
low = lodRangesLUT[lodLevel - 1];
}
float high = lodRangesLUT[lodLevel];
float delta = high - low;
float factor = (dist - low) / delta;
return clamp(factor / 0.5 - 1.0, 0.0, 1.0);
}
// Morphs the vertex position in object-space given its
// position in the mesh grid ranging from 0.0 to the mesh grid dimensions.
// All positions only contain its x and z values, y values will be
// retrieved later from the height texture.
vec2 morphVertex(vec2 vertex, vec2 mesh_pos, float morphValue){
vec2 fraction = fract(mesh_pos * mesh_dim * 0.5 ) * 2.0 / mesh_dim;
return vertex - fraction * morphValue;
}
The resulting morph should look something like the example below
Resources
Filip Struger, Continuous Distance-Dependent Level of Detail for Rendering Heightmaps (2011)
https://www.tandfonline.com/doi/abs/10.1080/2151237X.2009.10129287
Oreon Engine, Terrain Quadtree (2017)