Terrain rendering is a perennial hot issue in the world of game programming. Right now we're at a particularly interesting point in the development of terrain rendering technology, because polygon budgets have risen to the point where, in conjunction with real-time LOD meshing algorithms taken from published academic papers, state-of-the-art game engines are able to draw quite a bit of reasonably detailed terrain. However, the techniques which are currently in common use must compromise either on terrain size or on close-up detail.

As part of the R&D for Soul Ride, the game I'm currently working on (http://www.soulride.com ), I experimented with the published algorithms, and eventually came up with an extension that eliminates the tradeoff between terrain size and close-up detail. This article presents my algorithm, along with its similarities and differences from the above-mentioned algorithms.

I'll start by reviewing the problem of terrain rendering, and describe the problem solved by [1], [2], and [3] (see references at the end of this article). Then I'll explain the additional problem solved by my algorithm. I'll present a detailed description of the algorithm, and discuss some of the problems with it and some of the untapped potential. And last but not least, I'll provide the source code to a demo that implements my algorithm, which you can use to help understand it, evaluate its effectiveness, and incorporate directly into your own projects if you want.

This article is not a general tutorial or review of terrain rendering. I'm going to assume some familiarity on your part with the problem. If things aren't making much sense, you may want to consult the excellent references listed at the end of the article.

The Problems

What do we want from a terrain renderer? We want a single continuous mesh from the foreground all the way to the horizon, with no cracks or T-junctions. We want to view a large area over a large range of detail levels: we want to see the bumps in front of our feet to the mountains in the background. For the sake of discussion, let's say that we want feature size to range from 1m up to 100000m; five orders of magnitude.

How can we do it? The brute-force approach won't work on ordinary computers circa Y2K. If we make a 100000m x 100000m grid of 16-bit height values, and just draw them in a mesh (Figure 1), we'll end up with two big problems.First, the triangle problem: we'll be sending up to 20 billion triangles/frame to our rendering API. Second, the memory problem: our heightfield will consume 20 GB of data. It will be many years before hardware advances to the point where we can just use brute-force and get good results.

Fig 1. Brute force approach to a heightfield mesh.

There are several previously-published methods which successfully tackle the triangle problem. The most widely used ones employ a clever family of recursive meshing algorithms [1], [2], [3]. Using one of these algorithms, we can effectively tame our mesh, and render a seamless terrain with a few thousand triangles, with the vertices intelligently selected on the fly from the 10 billion in the dataset.

However, we still have a memory problem, since the heightfield dataset consumes 20 GB (plus some overhead to support the meshing algorithm).

One obvious solution is to compromise on detail by making the heightfield dimensions smaller. 1k x 1k is a good practical size for a heightfield with today's machines. A recently released game called TreadMarks uses a 1k x 1k dataset to excellent effect [4] (see references at the end of the article). Unfortunately, 1k x 1k is still a far cry from 100k x 100k. We end up having to limit either the size of the terrain and the view distance, or the amount of foreground detail.

The solution which I cover in this article is to use an adaptive quadtree, instead of a regular grid, to represent the terrain height information. Using this quadtree, we can encode height data at different resolutions in different regions in the terrain. For example, in a driving game, you would want lots of fine detail on and around the roads, ideally showing every bump, but you wouldn't need that much detail for the surrounding wilderness that you can't drive to; you only need enough detail for the general shape of hills and valleys.

The quadtree can also be used for another attack on the memory problem: procedural detail. The idea is to pre-define the shape of the terrain at a coarse level, and have the computer automatically generate fine detail on the fly for the area immediately around the viewer. Because of the quadtree's adaptive nature, this detail can be discarded when the viewer moves, freeing up memory for creating procedural detail in a different region.

Separately, the use of quadtrees for adaptive representation of 2D functions, and the use of quadtrees for recursive meshing [1], [3] are both well-known. However, [1] and [3] both use regular grids for their underlying heightfield representation. Extending their meshing approach to work with a true adaptive quadtree presents numerous complications, and requires some tricky programming. Hence this article and the accompanying demo code.