Svante Lindgren 2020-06-13

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.

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.

static const int _lodLevels = 10;

float _lodRanges[_lodLevels];

for (int i = 0; i < _lodLevels; i++){

_lodRanges[i] = _minLodDistance * pow(2, i);

}

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.

if(lodLevel > _lodLevels){

for (Node* child : node->_children){

selectLods(child, _lodRanges, lodLevel - 1);

}

if(!node->_boundingBox.sphereIntersect(_lodRanges[lodLevel])){

// Skip nodes node not intersecting current lodrange.

if(!node->_boundingBox.frustumIntersect(_cameraFrustum)){

// Skip nodes node not visible to camera.

if(lodLevel == 0){

// Always add LOD0 within range.

}else{

if(!node->_boundingBox.sphereIntersect(_lodRanges[lodLevel - 1])){

// We now know this node is only covering one lodrange.

}else{

// If node is within LOD and also within range of LOD - 1

for (Node* child : node->_children){

if(!selectLods(child, _lodRanges, lodLevel - 1)){

}

}

return true;

}

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.

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);

}

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

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)

Copyright Â© All Rights Reserved