Non-uniform LODs to minimise vertical error

[phire]

(This is partly me researching things, partly a low priority feature request. I have no idea if this is within scope of this add-on)

One major limitation of pure geometry clipmaps, is that LOD are selected based entirely on distance from the camera. But for most open word maps, the required minimum vertex density varies quite a lot based on the type of terrain. Mountains require a quite high vertex density to maintain their shape in the distance, rolling hills can get away with much less and flat planes can be represented with almost zero vertex density.

I've recorded a video of the demo scene as an example:

https://github.com/TokisanGames/Terrain3D/assets/138484/81580aa1-2e8a-4e21-a3ff-a335967e54f9

If you focus on the highest mountain, it changes shape from being quite sharp to very rounded. Ignore the pop-in and seems, that will be solved by #158's geomorphing. But even with geomorphing, the mountain is still going to morph between two very different shapes in a very obvious and distracting way.

Without some kind of non-uniform LODs, the developer will be forced to select manually LODs that are dense enough to represent their most extreme parts of their height map. Even if Terrian3D could select optimal LODs automatically, that single set of LODs will be used across the entire height map, even when most of world would be better represented with a lower vertex density, for better gpu performance.

Instead, it would be ideal to have a system that picks optimal LODs for each part of the high map.

The Witcher 3's solution

Slides

The talk doesn't go into much detail, but the Witcher 3 calculates a "max vertical error" texture at runtime that holds the error for each of the 3 lower LODs in R, G and B. They then use a mixture of software and hardware tessellation to navigate the quad-tree and generate the mesh (meshes?)

You can see the results of this tessellation here, and how it conforms to steep terrain like mountains and gullies.

Kurt Kühnert's Chunked Clipmaps

Demo Video | Thesis

Kühnert's algorithm doesn't do non-uniform LODs deliberately (the explicit goal was uniform distant-dependant LOD). But the algorithm does support arbitrary LODs for each tile, and can show a lower LOD if data for a higher LOD hasn't been loaded yet.

Here is a diagram from the Thesis demonstrating this scenario:

So we could absolutely extend this algorithm to implement non-uniform LODs.

Implementation wise, Kühnert uses a compute shader to traverse down the quad tree, evaluating LODs, computed-based frustum culling, then feeding that output into an indirect draw.

Implementation for Godot

Godot doesn't (and shouldn't) support hardware tessellation, and I don't think it's wise to do full tessellation on the CPU, so we can't really use the Witcher 3's solution.

But I think it would be smart to combine the vertical error texture from Witcher 3, with chunked clipmaps.

Godot doesn't support indirect draws (at least not yet), so we can't do compute shader frustum culling, but we should be able to implement quad tree LOD evaluation on the CPU without any issues.

---

Admin edit: Another paper on UDLOD

[Saul2022]

While true, doesn’t multimesh or gpu be modifed to do that indirect draw as it kind of using that based on what i saw from some people.

[TokisanGames]

Did we already talk on discord? Are you "Broken"?

Note that I plan to introduce compute shaders for sculpting and terrain generation, later. They may replace all usage of Images now.

Without some kind of non-uniform LODs, the developer will be forced to select manually LODs that are dense enough to represent their most extreme parts of their height map.

There is no option for anyone to select LODs at all. The LOD density is currently fixed and uniform at each level, and the position is automatically placed. I assume you've already read our System Design wiki page and Mike Savage's blog.

Godot doesn't support indirect draws (at least not yet), so we can't do compute shader frustum culling,

The clipmap is made up of several meshes. Half of them are already frustum culled.

So we could absolutely extend this algorithm to implement non-uniform LODs.

But I think it would be smart to combine the vertical error texture from Witcher 3, with chunked clipmaps.

but we should be able to implement quad tree LOD evaluation on the CPU without any issues.

Kurt's video looks great. I appreciate any help in designing and implementing better solutions. This issue is a good reference for the future.

[phire]

Did we already talk on discord? Are you "Broken"?

No, I should probably join your discord.

There is no option for anyone to select LODs at all. The LOD density is currently fixed and uniform at each level, and the position is automatically placed. I assume you've already read our System Design wiki page and Mike Savage's blog.

I've read through the system design and Mike's blog. In the current implementation, you change the Mesh size (upto a maximum of 64) which pushes each level further away, and changes the LOD density. Solving #191 would require some form of global LOD density option.

Godot doesn't support indirect draws (at least not yet), so we can't do compute shader frustum culling, The clipmap is made up of several meshes. Half of them are already frustum culled.

Good point. It's only the fancy compute-shader frustum culling that can't be done. I hadn't checked how Terrain3D was currently drawing the tiles, and I assumed it was a multimesh.
As long as we continue feed the tile instances to Godot individually with custom AABBs, we can use Godot's existing cpu frustum culling.

I'm just a little concerned about the overhead of that strategy (especially if we implement non-uniform LODs and need to subdivide tiles), and Kurt's compute-shader frustum culling is really attractive solution to potential problems there.

[esklarski]

I'm jumping in to this discussion inexperienced with this plugin and with no programing solution. But this issue is perhaps my biggest complaint with most terrain systems.

Now in my mind the key problem is that topographic prominence (link) for the observer is not maintained. All of the loss of detail is fine, except for the sudden change of altitude as the selected mesh points fail to capture the highest point of the terrain (the peak).

Aside from these specific points of prominence, I think this Terrain3D system looks spectacular. I feel the solution used by others over complicate the issue.

My first thought is to create a bunch control points at the highest vertex of all areas with xxx amount of prominence (calculated on import perhaps) and then ensure that that the mesh under those points is raised to maintain relative elevations for the skyline. Might this be a fairly low resource solution? It would basically be a list of vertices that don't move as lod changes.

I see there are plans for a variable mesh density system, which could also help by increasing mesh density for the most prominent areas.

[esklarski]

This app does some magic and maintains a skyline fast and accurately: Peak Finder

Don't know what they do, it's almost as if it billboards the terrain based on topographic outlines. But as a mountaineer, I can attest to the accuracy as I've used the app in the field many times and it is really good at helping to identify distant peaks.