Terrain Simplification

CS 481/681 2007 Lecture, Dr. Lawlor

Terrains are big.  That's what you want them for--to make your world keep rolling on and on.

But terrains can be big.  That's the problem--they stuff your graphics card with piles of little teeny polygons way off in the distance, even stuff behind you. 

For example, say you want 1m terrain resolution.  That's actually pretty coarse.  Say you want a 2km view distance.  That's a grid 4km on a side, centered on the camera.  So that's 16 million grid cells, or 32 million triangles.  Now at 30fps, you're talking 900 million polygons per second.   That's well beyond the capabilities of all existing graphics cards.

But:
Luckily a single technique can provide both view culling and level of detail--recursive bounding.

Recursive Bounding

There's a really simple powerful data structure we'll be using--a spatial subdivision tree.  Each node of the tree represents a certain region of space.  The child nodes of that tree represent a subset of that region of space.  To draw a tree node, you:
Spatial trees are everywhere.  You don't need very much at each node--a set of pointers to the child nodes, and some sort of bounding volume.  I like using bounding spheres.

Geometric Complications

Unfortunately, anywhere the terrain is nonlinear (that is, pretty much everywhere!) your big and little quads aren't going to match up along their boundaries.  There are several interesting ways to handle this:
So once you understand the basics, DO NOT IMPLEMENT YOUR OWN TERRAIN ALGORITHM.  Use one of the many existing nice libraries (collection by Stefan Röttger).

Geodetic Complications

Sadly, your average planet is curved.  Over a room, that doesn't make much difference, and you can draw the room as if the world is flat.  Over just a few dozen kilometers, the curvature of the Earth induces a several-meter height shift--the center of the elevation map is lifted due to the curve of the Earth:

Terrain surface over flat and curved references
It is possible to resample a heightfield specified across a map-friendly curved reference to a heightfield specified across a computation-friendly flat reference--this involves both a height change and a location shift.  You can also write your heightfield code carefully, and handle curved reference surfaces automatically.

Be aware that the "0.0m above sea level" surface is NOT a sphere, and not even an ellipsoid, it's a "geoid", whose shape depends on annoying nonmathematical entities such as mountain ranges (whose gravitational attraction tilts the sea, as well as all plumb bobs!).

Luckily, for scenes smaller than about four kilometers across, the Earth's curvature amounts to less than 1/3 meter, which can usually be safely ignored.