nordisk/facett

CDLOD terrain quadtree — for idiots

The dead-simple version. No graphics maths required.

The problem, in one picture

You are flying over a landscape. Right under the plane you want crisp hills. On the far horizon you want cheap blobs, because you can't see the detail anyway and drawing it would melt the GPU. So: lots of little triangles near you, a few big ones far away.

The idea: split the map like a chessboard that only zooms in near you

Picture the whole terrain as one big square. Now the rule:

• If the camera is far from a square → leave it as one big square (cheap).
• If the camera is close to a square → cut it into four smaller squares, and ask the same question about each of those.

Do that over and over and you get tiny squares hugging the camera and big squares on the horizon. That tree of squares is the "quadtree". CDLOD is just the recipe for deciding, from the camera distance, how deep to cut.

+--------+--------+        far away → one big tile
|        |        |
|        |        |
+---+----+--------+        getting closer → cut into 4
| . |    |        |
+---+----+  near the camera (.) → cut again, and again

The crack problem (and the fix)

When a small square sits next to a big square, their shared edge doesn't line up — the small one has an extra point in the middle, and you get a little gap you can see through. Two safety rules stop that:

1. Neighbours are never more than one size apart. (The recipe guarantees it.)
2. Morphing. As a small square gets further away, its extra edge point slides until it exactly matches the big neighbour's edge — so the gap closes smoothly, with no sudden "pop". The morph number (0 = crisp, 1 = matched to the big neighbour) is how far along that slide it is.

How you use it (three lines)

let cdlod = Cdlod::new(region, CdlodConfig::default()); // set up the tree
let nodes = cdlod.select(camera);                       // which squares to draw now
let patches = cdlod.build_meshes(camera, &elevation, origin, 1.0); // the actual terrain

nodes is the list of squares (each with its morph number). patches is the terrain mesh for each square, sampled from the real height data (a DEM, or a fake procedural one for tests). Feed each morph to the shader and the edges won't crack.

How we know it works (no GPU needed)

Little tests check the important promises: closer camera → more squares; the squares always cover the whole map with no gaps or overlaps; neighbours differ by at most one size; the morph goes cleanly from 0 to 1; the same camera always gives the same answer. If any promise breaks, a test goes red. The GPU version of the morph is checked against the plain-Rust version when a graphics card is available, and politely skips (leaving a note) when there isn't one — so it's safe to test on a laptop with no GPU.