Ok, can show off preliminary results, and a description of how things work. Would very much like to get realistic estimations if that can be reasonably well integrated into the Godot structure.
A disclaimer: this has not grown on my dung ! Credits must be given to the inventor F. Strugar (see first post), who was even so friendly to offer a reference implementation under the MIT license. Here's the theory.
Won't repeat the paper, so just a superficial (how fitful :-)) overview: based on a heightmap image (e.g. 16 bit grayscale png for low storage usage) a quad tree is built which each level being half the size of the previous. Each node of the quadtree though has the same size in terms of triangles to render. This way, a single square mesh (in my case limited to power of two alongside, reason for this comes later down the line) can be used to render each of the nodes. The transition between positions is calculated over an area, so that positions move gradually between lod levels.
Image data from SRTM V3 90m spatial resolution, converted from ASCIII to png, just to have something
Each frame, a selection of nodes from the quad tree to render this frame is being made. The selection only depends on the camera position and the distance to the node in question. Thus, the transition areas move with the camera. Selection is done by a fast frustum check against a bounding box of the node in question.
All data necessary for rendering is calculated during loading of the heightmap image. In the example, a 2048*2048 png this takes around half a second. A larger heightmap (8 or 16k) take several seconds, and the resulting data structure has considerable size (several MB), so this will certainly have an impact on overall performance then because it fits in no cache any more. But smaller sizes (2 or 4k) can easily be rendered on less powerful devices than my PC. Frame rate single threaded, not overclocked, AMD 5800X, Radeon RX 6700XT.
Momentarily, it is till rather buggy. Once it runs sufficiently well I will put it on github.
Most of the parameters can theoretically be changed on the fly, maybe requiring rebuilding of the data structure. This at least for a limited size of the landscape, think a bunch of worlds of floating discs. But even a planet sized object could hypothetically be represented, with the help of a large data structure (e.g. spherical/ellipsoid cube map with six quad trees) and intense streaming.
Paremeters:
static const int NUMBER_OF_LOD_LEVELS{ 5 };
self explanatory, the depth of the quadtree.
static const int MAX_NUMBER_SELECTED_NODES{1024};
The selection should be limited to a size that can be handled easily during a frame and not to bust the stack. This should play together with quad tree node sizes, resolution, and resulting number of render calls.
static const int LEAF_NODE_SIZE{64};
The size of a leaf node. Together with size of the heightmal and number of LOD levels this determines the size inb memory of the quad tree, and the available space for LOD transitions. Shouldn't be too small or popping artefacts appear and the data structure gets really big.
static const omath::uvec2 TILE_SIZE{2048,2048};
The size of a heightmap image.
static const float LOD_LEVEL_DISTANCE_RATIO{2.5f};
The space between each LOD level get greater with the distance from the camera. In order to keep the number of triangles to render roughly equal, this is a tweak to change 'density' more to the foreground, or to the background.
static const float MORPH_START_RATIO{ 0.7f };
Morphing in Strugar's terms refers to the gradual between LOD levels. This means that 70% of a node remains at its resolution, 30% are used for 'morphing' between positions.
static const int RENDER_GRID_RESULUTION_MULT{1};
Simply a multiplier to increase resolution on large or spacey heightmaps.
static const int GRIDMESH_DIMENSION{ LEAF_NODE_SIZE * RENDER_GRID_RESULUTION_MULT };
Clear, right ?
static const bool SHADOW_MAP_HIGH_QUALITY{false};
static const int SHADOW_MAP_RESOLUTION{SHADOW_MAP_HIGH_QUALITY ? 4096 : 2048 };
Ideally, a shadow map's cascades follow the LOD level transitions. I have not implemented that yet.
Sorry, must cut and run now, love to hear from you what you think about the feasibility. A lot of conceptual things are still missing, like how to render it nicely, and how to do physics with it.
