I have a large heightmap, split into X-sized patches (e.g 32), inserted into a quad-tree for view culling on the CPU. All rendered as instanced drawing of a simple 4-vertex quad with each patch has it's own world-transform (with uniform scale for all). The tessellation of each chunk depends on it's height variance & screen-space size. Fair enough, that works mostly fine, although there are two cases that are problematic:

1. Performance, when zoomed out far enough that nearly all patches are visible
2. Loss of detail, when not in a top-down view or very very zoomed in

So I'm thinking of doing non-uniform sized patches like this image:

A quad-tree like this is different from mine as it's built from the camera as the root so I need to change that.

As for determining when to merge smaller patches into a larger one, is there a smart metric to use? The most simple one I can think of is measure distance from camera in absolute world units, but I would prefer something more adaptive perhaps, to handle really large & small terrains, and not dependent on such static boundaries. Any ideas?

That is from F. Strugar's paper "Continuous Distance Dependent LOD".

I (and others i am sure) have an implementation of that (C++/OpenGL), see my github.

- peformance is not an issue.

- level of detail and ranges as well as depths of transitions can be configured.

- LODs are independent from tile sizes and quadtree resolution. Edit: no extra metric needed for transitions.

- tile sizes can vary. I use square tiles for now cause it simplifies some things. Strugar's original uses non square tiles, but powers of two are convenient because quad-tree.

- the quadtree is not built from the camera, it is built from the tiles and it is static during a tile's lifetime.

- Otoh, the selection of nodes each frame is built from camera position (frustum culling) in world coords.

- camera distance is the measure for selection, so the angle plays a role in the LODding.

- size limit is (when streaming data) limited by the external storage media.

- data footprint is extremely small, only a (16bit) heightmap is needed per tile. Everything else can be done in the shaders. Strugar uses normal maps, but i will do that in the shader, eventually with edge detection and all that.

- only a single mesh the size of a node is needed. That makes it really fast, as only a small 2D vertex buffer of let's say 64/64 (the size of a leaf node * a multiplier) and its indices are needed. This is placed and scaled for every node to draw.

I love that algorithm. It is so clean and straight ?

Edit: the image does not show the whole quad tree of a tile (which is static and generated on loading), but the frame-based selection of nodes from that quadtree based on the camera position and view angle. I mention this to avoid eventual misunderstandings ...

3 hours ago, Green_Baron said:

That is from F. Strugar's paper "Continuous Distance Dependent LOD".

I (and others i am sure) have an implementation of that (C++/OpenGL), see my github.

Interesting; do you have a github link for reference?

3 hours ago, Green_Baron said:

- tile sizes can vary. I use square tiles for now cause it simplifies some things. Strugar's original uses non square tiles, but powers of two are convenient because quad-tree.

- the quadtree is not built from the camera, it is built from the tiles and it is static during a tile's lifetime.

I see, it's like how I do it currently, then.

Just to be sure, you build & cull nodes on the CPU right?

Also, how deep do you determine the quadtree should be, where do you stop splitting nodes? I have it set to 32x32 but is there a reason to do anything else? Given that there is quite abit of memory footprint on the CPU for each height in the quadtree

3 hours ago, Green_Baron said:

- size limit is (when streaming data) limited by the external storage media.

Not quite sure I understand this part. Which size limit do you refer to? And what is the external storage media?

3 hours ago, Green_Baron said:

- only a single mesh the size of a node is needed. That makes it really fast, as only a small 2D vertex buffer of let's say 64/64 (the size of a leaf node * a multiplier) and its indices are needed. This is placed and scaled for every node to draw.

Isn't it enough to do a unit-sized quad and then provide a scaling/translation transform for each patch?

Thanks alot for the answers! ?

41 minutes ago, KaiserJohan said:

Interesting; do you have a github link for reference?

Originally published here:

https://www.tandfonline.com/doi/abs/10.1080/2151237X.2009.10129287

and github as well:

https://github.com/fstrugar/CDLOD

Quote

Just to be sure, you build & cull nodes on the CPU right?

Yes. A node is just a bounding box. It does not contain any data. The data is in the heightmap.

Quote

Also, how deep do you determine the quadtree should be, where do you stop splitting nodes? I have it set to 32x32 but is there a reason to do anything else? Given that there is quite abit of memory footprint on the CPU for each height in the quadtree

A node is only a few bytes. A position, min/max height (two vectors), a bounding box 4 pointers to its children and a lod level. There is still some unnecessary redundancy in it that i'll take care of later. For example a quad tree for 2048/2048 height map, 5 lod levels and 32/32 leaf node size has ~725kb. But one could build it with 3 or 8 levels and node sizes of 128 or 8. Whatever fits the needs.

Quote

Not quite sure I understand this part. Which size limit do you refer to? And what is the external storage media?

Larger than 4096/4096 takes a few (2-3) seconds to load the height map texture and build the tree and extract the node's bounding boxes (extract min/max heights per node is probably the most intensive work). I haven't yet implemented any concurrency in my little framework.

Number of LOD levels, node size depend on the situation. I haven't played with more than 8 lod levels yet, because if the distances between levels in relation to camera depth of field gets too small for a clean gradual transition (morphing) between levels, cracks appear. In my tests, 3-6 levels and node sizes between 8 and 32 were good.

External storage, for me is anything not RAM, a hard disk, a server, network storage. One can actually render a real world sized planet, that's my far goal.

Quote

Isn't it enough to do a unit-sized quad and then provide a scaling/translation transform for each patch?

If you mean with patch a node of the quad tree, that's what the paper proposes ! But the world units can be and are different from the render resolution, if you mean that. One single mesh is sized and transformed and passed around for rendering each node. The node has (via its bounding box) world coordinates, but a configurable resolution. I have a blurry video of how that looks in my blog (someone must tell me how to configure OBS capture software to unblur it ;-)) that shows how the boxes and the terrain lod propagates as the camera moves.

Quote

Thanks alot for the answers! ?

Your welcome. I am also well pretty new to all this, and would like to take it to rendering a planet 13 million meters diameter ... for some of you maybe something they did ten years ago ...

4 hours ago, KaiserJohan said:

I have a large heightmap, split into X-sized patches (e.g 32), inserted into a quad-tree for view culling on the CPU. All rendered as instanced drawing of a simple 4-vertex quad with each patch has it's own world-transform (with uniform scale for all). The tessellation of each chunk depends on it's height variance & screen-space size. Fair enough, that works mostly fine, although there are two cases that are problematic:

1. Performance, when zoomed out far enough that nearly all patches are visible
2. Loss of detail, when not in a top-down view or very very zoomed in

So I'm thinking of doing non-uniform sized patches like this image:

A quad-tree like this is different from mine as it's built from the camera as the root so I need to change that.

As for determining when to merge smaller patches into a larger one, is there a smart metric to use? The most simple one I can think of is measure distance from camera in absolute world units, but I would prefer something more adaptive perhaps, to handle really large & small terrains, and not dependent on such static boundaries. Any ideas?

You can do something like this .... First the whole terrain is just one big quad-tree all the down to the leaf triangles.  A chunk is just some point in the quad-tree and everything under it.

Then you start start at the top of the quad-tree and go down. There is a bounding volume around each node in the tree. I use pills because I  have triangular chunks on a planet and for steep terrain it works better than spheres.  For square chunks on flat terrain you can also use tall axis aligned boxes with the top and bottom adjusted for the terrain height.

In any case as you go down the tree you check the distance from the camera to the edge of your bound and determine if your chunks are are at the right level based on the standard power of 2 distance calculation. You have four basic operations of which you rarely use two of them:

Grow chunk ---- This means you are increasing the subdivision of an existing chunk.  You really on used this when you are zoomed way out and have one chunk.  However you also use it as part of a split chunks operation right after new chunks are created.

Shrink chunk ---- Reverse of a grow chunk

Split chunk ----  As you start to zoom in you will find you have encountered a top of chunk too early in the tree for your given distance. In this case you wan to split it into multiple chunks that will be lower i the tree.  If you are moving fast this can be more than four but usually it will be four. You also should grow each chunk after it's split to get to the right LOD level.

Merge chunks --- As you zoom out you will find you come across a node in the tree that should be the top of a chunk however it isn't. That means there are chunks below it that you need to merge into a new chunk at this level. You will also need to shrink your new chunk because it will be too deep for the new LOD level.

Here is the demo. You can just skip the last part of the video that talks about noise. Again this uses triangular chunks on a sphere but you can do the same thing with flat terrain.