One way to LOD terrain is to look at the terrain on a triangle by triangle basis, and determine which triangles to merge and which to leave alone, based on the distance and angle from the camera. This type of algorithm will give us a perfect set of triangles to an exact degree of error. This approach was the norm before modern graphics hardware, when you didn't mind spending as much CPU time as possible to put out as few vertices as possible. This is not how Terrific works.

Once people started programming for graphics hardware, they found terrain rendering was no longer bound by rendering time, and had become bound by the CPU time. If you can keep the CPU idle by not worrying about rendering a perfect LOD and letting the GPU do the work, so be it! This also frees up the CPU for doing the things it's good at in a typical 3D game, such as physics, AI, voice chat audio compression... (What, you didn't think we're rendering terrain for the sake of rendering terrain did you?)

Instead of thinking of terrain LOD as "Which triangles should I render?", we can divide the terrain into larger blocks, or Patches, and ask "At what LOD should I render each Patch?". All of a sudden you've gone from doing culling and LODing on two million triangles to culling and LODing two hundred Patches. The result is an imperfect LOD (We may have to keep the GPU busy drawing more triangles than necessary) but we've gained a huge chunk of CPU that we can use for other things.

This Patch-based approach is used by a strategy called Geomipmapping, which involves precomputing the different levels of detail of each Patch at load time. As well as each LOD being precached in each Patch, we also precalculate at what distance that Patch can switch to a lower detail level. This also results in naturally flat Patches being LODed before hilly Patches, as expected.

The Patches are stored in a (balanced) quadtree structure for speedy visibility testing. At each leaf of the quadtree is a Patch, which contains its 3D (axis aligned) bounding box. Each node in the tree stores the bounding box that fully contains its four children. Once this tree is built at load time, we can get really zippy frustum culling, since if a quadnode's bounding box is not in the frustum, we can safely consider all the Patches under that node as offscreen. The result is large sections of the terrain being culled away at a time, and very quickly arriving at the Patches that exist inside the view frustum.

A texture is generated at load time for each Patch. This will generate the classic blended terrain demo texturing, with low to high elevation being smoothly blended from water to sand to grass, or whatever the programmer defines. Once this colormap is found, static lighting and shadows are also "baked" onto the texture.

Shadows

Now that the Patch texture is pseudo-lit with our static lighting witchcraft, why stop there? The terrain's original heightmap can be used to create another lightmap for shadows (This type of lightmap is called a shadowmap) to get shadows, for free! To keep things quick and simple, the sun is considered an infinite distance away and casts its rays directly along the rows.

Figure 2. Calculating shadowmaps. (From Twenty Sided)

Terrific is agnostic about where its heightmap comes from. All it asks for is a square heightmap, it doesn't care if it was loaded from a file or procedurally generated. That being said, this project comes with a simple procedural terrain generator using what's called particle deposition for creating an archipelago:

function generateTerrain()
{
	Start with a zeroed out heightmap

	loop N times (for each island):
	{
		Pick a random spot on the heightmap, this is the cursor.

		loop M times:
		{
			If the spot under the cursor isn't flat (based on it's neighbors) then have a chance of "rolling" the cursor down the slope.

			Drop a "rock" onto the cursor, increasing the height at that spot

			Move the cursor in a random direction.
		}
	}
}

The biggest embarrassing bug is the texture creasing clearly visible on Patch borders. This is because of a couple reasons. The first is that Patch light/shadowmaps are calculated and smoothed on a Patch-by-Patch basis. This could be fixed by considering the adjacent Patches when calculating lightmaps. The second reason is that texture filtering will not work between the textures of two different Patches no matter what you do. A lot of engines leave this untouched, and it isn't really clear to me how to go about fixing it, short of creating one giant texture for the entire terrain.