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 [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.
_______________________________________________________________
Meshing
|
|
|
|
Features
