Heightmaps
With a heightmap, you store only the height component for each vertex (usually as 2D texture) and provide position and resolution only once for the whole quad. The landscape geometry is generated each frame using the geometry shader or hardware tessellation. Heightmaps are the fastest way to store landscape data for collision detection.
Pros:
Relatively low memory usage: You only need to store one value per vertex and no indices. It's possible to improve this further by using detail maps or a noise filter to increase perceived detail.
Relatively fast: The geometry shader for heightmaps is small and runs fast. It's not as fast as geometry terrain though.
On systems without triangle based 3D acceleration, ray marching heightmaps is the fastest way to render terrain. This was referred to as voxel graphics in older games.
Dynamic LOD/terrain: It's possible to change the resolution of the generated mesh based on distance from the camera. This will cause the shifting geometry if the resolution drops too far (around 0:40), but can be used for interesting effects.
Easy terrain generation/creation: Heightmaps can easily be created by blending noise functions like fractal Perlin Noise and heightmap editors are fast and easy to use. Both approaches can be combined. They are also easy to work with in an editor.
Efficient physics: A horizontal position maps directly to (usually) one to four positions in memory, so geometry lookups for physics are very fast.
Cons:
Exactly one height per x/y coordinate: There usually can't be holes in the ground or overhanging cliffs.
Less control: You can only control the precise height of each point if the grid size matches the texture coordinates.
Artifacts: If the four vertices that define a sub-quad aren't on the same plane, the split between the two vertices will become visible. This usually happens on steep cliffs with edges that don't follow a cardinal direction.
Heightmaps are the most efficient way of rendering terrain by far and are used in many newer games that don't rely on advanced terrain features and have large outdoor areas. Wikipedia has a list of programs that use heightmaps, but I'm not sure if that means they only use them as resources or also for rendering, so here a some games that are likely to use them:
Just Cause 2: Regions are loaded in square sectors and there are no holes in the terrain. In the demo, there's a deep hole with stretched triangles along the edges where there normally would be a building. (The area is normally inaccessible, but there are mods to remove some of the demo's limitations...)
Sims 2 (maybe): Neighborhood terrain is loaded as heightmap, but there are holes where lots (building sites) are placed. There are typical artifacts if you create cliffs on a lot, though, and it's quite tedious to add a cellar to a house (and hide the cliff under a veranda).
Valve's Source engine games: Rectangular brushes (static level geometry) can have heightmapped terrain on their faces. In these games, the usual quirks are often hidden with other brushes or props.
It's impossible to tell for sure without looking at the shaders because every heightmap terrain can be rendered as mesh.
Voxels
Voxel terrain stores terrain data for each point in a 3D grid. This method always uses the most storage per meaningful surface detail, even if you use compression methods like sparse octrees.
(The term "voxel engine" was often used to describe a method of ray marching terrain heightmaps common in older 3D games. This section applies only to terrain stored as voxel data.)
Pros:
Continuous 3D data: Voxels are pretty much the only efficient way to store continuous data about hidden terrain features like ore veins.
Easy to modify: Uncompressed voxel data can be changed easily.
Advanced terrain features: It's possible to create overhangs. Tunnels are seamless.
Interesting terrain generation: Minecraft does this by overlaying noise functions and gradients with predefined terrain features (trees, dungeons). (Read Terrain Generation, Part 1 in Notch's blog for more info. There is no part 2 as of 05.8.2011.)
Cons:
Slow: To render voxel data, you either have to use a ray tracer or compute a mesh, for example with marching cubes (There will be artifacts). Neighboring voxel aren't independent for mesh generation and the shaders are more complicated and usually produce more complex geometry. Rendering voxel data with high LOD can be very slow.
Huge storage requirements: Storing voxel data uses lots of memory. It's often not practicable to load the voxel data into VRAM for this reason, as you'd have to use smaller textures to compensate for it, even on modern hardware.
It's not practical to use voxels for games that don't rely on voxel features like deformable terrain, but it can allow interesting game mechanics in some cases. Voxel engines are more common in older games, but there are also newer examples:
Atomontage engine: Voxel rendering.
Worms 4: Uses "poxels". According to Wikipedia it's a mix of voxels and polygons.
Minecraft: Uses voxel to represent the terrain in RAM, the graphics are polygon graphics. It's mostly software calculated though.
Terraria: An example for 2D voxels. I don't know how it renders.
Voxels combined with physics: Not a game. but it nicely showcases the destruction potential.
Voxatron: A game using voxels for almost all of the graphics, including menus and HUD.
Meshes
Polygon meshes are the most flexible and precise way of storing and rendering terrain. They are often used in games where precise control or advanced terrain features are needed.
Pros:
Very fast: You only have to do the usual projection calculation in the vertex shader. A geometry shader isn't needed.
Very precise: All coordinates are store individually for each vertex, so it's possible to move them horizontally and increase mesh density in places with finer details.
Low memory impact: This also means the mesh will usually need less memory than a heighmap, because vertices can be more sparse in areas with less small features.
(See Triangulated irregular network on Wikipedia).
No artifacts: The mesh is rendered as-is, so there won't be any glitches or strange-looking borders.
Advanced terrain features: It's possible to leave holes and create overhangs. Tunnels are seamless.
Cons:
Poor dynamic LOD: Only possible with precomputed meshes. This will cause "jumps" when switching without additional data to map old to new vertices.
Not easy to modify: Finding vertices that correspond to an area that should be modified is slow.
Not very efficient for collision detection: Unlike in heightmaps and voxel data, the memory address for a certain location usually can't be calculated directly. This means physics and game logic that depend on the exact surface geometry will most likely run slower than with the other storage formats.
Polygon terrain is often uses in games that don't have large open areas or can't use heightmap terrain because of its lack of precision and overhangs. I don't have a list, but I'm pretty sure that
every 3D Zelda and
every 3D Mario game
use this.
Other methods
It's possible to create a terrain entirely in the shader pipeline. If the algorithm runs only in the fragment/pixel shader, the detail can be virtually unlimited while memory impact is almost zero. The obvious downsides are almost no control over the shape and problems when the camera intersects the original rendering surface. It's still useful in space games where players don't interact with the surface of a planet.
Parameter animations work best with this kind of terrain.
It should be possible to download the generated terrain geometry from the graphics card to use it for the rest of the game engine, but I don't know how the performance of that is or whether this has been done so far.
Conclusion
There is no method that works well for every scenario, but it's fairly easy to choose one for a certain task:
Heightmaps are the best solution if you don't need overhangs or holes in the terrain surface and use physics or dynamic terrain. They are scalable and work well for most games.
Meshes have the highest precision and can describe overhangs, holes and tunnels. Use them if you have complex terrain that doesn't change often.
Voxels are good for describing very dynamic terrain with many complex features. Avoid rendering them directly as they need large amounts of memory and processing.
Other methods may be better than any of the above if you don't have to interact with the terrain or need very detailed graphics. They usually work only for very specific scenarios.
It's possible to combine different methods to get features from more than one, for example by tessellating mesh terrain with a heightmap to increase the detail structure of a cliff.
Dynamic terrain generation is heavily used in procedural space simulation and some have become really advanced in the last years. The forums of these projects should have some resources on the topic.
