Terrain LOD: Runtime Regular-Grid Approaches

Memory usage

  storage bytes/heixel notes
Lindstrom-Koller '96 block-based, each block is a dual quadtree of vertices "from 6 to 28" bottom-up evaluation!
Lindstrom 2001
(SOAR)
interleaved quadtrees around 53 for pre-process,
"20-33" at runtime
 
LKTerrain single block, dual quadtree of vertices 32 (30 + padding) top-down
TopoVista single bintree of faces heightfield + 12  
Treadmarks implicit binary tree of variance values, runtime binary tree of drawn triangles heightfield + 1-8, depending on precision and depth of variance bintree plus 10-20 bytes per drawn triangle
SMTerrain directly based on Treadmarks algo 3 (heightfield + 1) plus 20 bytes per drawn triangle
Soul Ride single quadtree of blocks, each block is 3x3 vertices ~11-14 the vertices of each block are evaluated as explicit cases 
Röttger et al. single quadtree of vertices heightfield + 1  
SRTerrain wraps Röttger's libMini in the VTP framework 5 fastest available rendering
CrystalSpace/DDG like ROAM heightfield + 3 plus 12 bytes per drawn vertex
Gizmo3d IRMA like ROAM 8-10  

...

Startup Time (time to fill arrays and calculate variances, in seconds, on a P3/800)

Grid Size SMTerrain SRTerrain SOAR (includes file IO)
1025 0.23 1.10 ~ 3
2049 0.91 4.53 ~ 14
4193 3.74 19.3  

...

Mesh Size Approximate Memory Required
SMTerrain
3 bytes/heixel
SRTerrain
5 bytes/heixel
TVTerrain
14 bytes/heixel
513 <1 MB 1.25 MB 3.5 MB
1025 3 MB 5 MB 14 MB
2049 12 MB 20 MB 56 MB
4097 48 MB 80 MB 224 MB
8193 192 MB 320 MB 896 MB
13k*15k
(theoretical)
557 MB 930 MB too much