Continuous
LOD Terrain Meshing
Using Adaptive
Quadtrees
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(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. 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(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 meshingare both
well-known. However,and
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.
_______________________________________________________________
Meshing