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.
Luckily a single technique can provide both view culling and level of detail--recursive bounding.
- Half the geometry is behind your head, and another substantial
fraction is off the sides of the window. So we need "view
- Most of the polygons are really far away and tiny; only the really nearby ones are actually needed. So we need "level of detail".
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.
- First figure out if you can even see the tree node. If you
can't, forget it--you don't even have to think about any of the node's
children. This automatically gives you view culling.
- Next figure out if it's worthwhile to draw the children. If
you're far enough from the camera that your whole node is only a few
pixels across (for some definition of "few", normally 0.5 to 50
pixels), then just draw some approximation of your terrain and
return. This gives you level of detail--big quads far away, and
little quads up close.
- Otherwise you have to draw your children. Recurse onto each
of them. If you just recurse in the right order, you can
automatically get back-to-front ordering (for the painter's algorithm)
or front-to-back ordering (for early-Z exit).
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
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).
- You can generate a gappy mesh, then add a "cleanup" step where
you fill in the gaps using little "skirts" of triangles. The
trickiest part about this is keeping track of where you need skirts,
and where you don't.
- Lindstrom's terrain
method has a cool way of generating big and little quads using
triangles that doesn't require any runtime size tracking--you
essentially bake the gap-filling into your error data structure, and at
runtime if you follow certain rules to generate triangles, then you'll
never end up with gaps.
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:
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