Which Terrain LOD algorithm should I use for super large terrain?

Question

My game needs a terrain, the requirements are:

1. Freely Zoom in & zoom out, like GoogleEarth. Max resolution when zooming in ~100 meter, Max range when zooming out ~2000km (a whole country scale).
2. Freely fly over to any direction with any height; Freely rotate camera; Framerate should not a bottleneck for all those basic camera movement.
3. Support large heightmap data. I got mine real world elevation data from NASA with 7.5arc resolution, around 30k * 15k for a whole country.
4. Also I need to consider the spherical earth surface curvature other than using a planar map. But this should be easy if I just map each vertex into spherical coordinates. I am not build the whole planetary LOD so it's not even a problem.

I noticed there are many different LOD algorithm out there. For example:

• ROAM: very classic algorithm, most done on CPU;
• Geomipmapping: store the whole heightmap with best resolution as vertex buffer, with different LOD in vertex index. Then determine LOD and draw range in vertex index at runtime.
• CDLOD:
• Geo Clipmapping: I am feeling excited about this one since it claims to load all 200k * 100k US heightmap into video card memory and compressed ~300M, it seems to meet all my requirements. see source paper. And this is paper in 2004 and think about the video card at that time!

That's pretty much all I know about terrain LOD. I am not familiar recently study/research in this area. Is Geo clipmapping my best option? What else algorithms are also useful to consider?

Answer 1

Forget about ROAM. That's the pre-3DFX era of SW rasterizers. I mean, if you're bored, it's a fun exercise, but it's useless in today's era of thousands of shaders units...

I would very strongly recommend Chunked LOD (Geomipmapping) because:

• it's super simple to implement - literally, one day is all it takes to create 3 different Index Buffers (High/Medium/Low Detail)
• it will serve as a reference implementation for further LOD schemes you will implement later

The single greatest issue with Chunked LOD is that it retains HighDetail on the border. So, while your base terrain chunk is, for example, 33x33 vertices, and your low detail would have only 7x7 on the inside of the chunk, the borders would be 33 vertices, which is much more than the ~90% of your chunk area.

This is why I would propose to first experiment a bit with your target data set:

• see if you can get away with completely without the high-detail border
• this will introduce cracks on the boundary (say, high-med or med-low) in distance, but only you can tell, if that's acceptable for your application or not.
• cracks visibility is exacerbated by the viewing angle. If you are only viewing terrain head on at zero angle (like, landing on the planet), you will not see any cracks. Opposite extreme is a first-person view, which will make every single one of them very visible against background.

I have alleviated the problem myself by creating additional sets of Index Buffers:

• have all combinations of hi/med/low on all 4 sides
• at run-time, based on actual LODs on the boundary, I then choose a correct Index Buffer
• this is only a slight complication that shouldn't take more than 1 day to implement, so well worth it

Once you've done the above, you can now implement a quadtree-style LOD where each base chunk will get progressively larger:

• 33x33
• 65x65
• 129x129 This will allow you to stop wasting vertices at the borders and relieve CPU from processing thousands of vertex batches. Which, again, depends on your target HW requirements. Perhaps you can start with 129x129, and just use 257x257 and 513x513 - we don't know your target HW specs...