is dedicated to the memory of Seumas McNally. Please see the epilogue
at the end of this article.
to accompany this article can be found here.
people, I find photographs of rolling hills or perilous canyons both
calming and awe-inspiring. It is unfortunate that as gamers, we are
not able to revel in the natural beauty of the outdoors. Only a few
current and upcoming games give us this feast for the eyes (Tribes
1 & 2, Tread Marks, Outcast, Myth 1 & 2, and HALO
are a few examples). These games have taken 3D action gaming to the
next level with the inclusion of incredibly detailed worlds upon which
the story and action are played out.
this article I will briefly examine the state of the art in hardware
accelerated landscape engines and the algorithms which power them. One
algorithm in particular will be presented, discussed, and finally implemented
as a starting point for anyone looking to add landscapes to their next
project. I'll assume an intermediate level of C++ knowledge and at least
general knowledge of 3D rendering.
to Terrain Visualization
seems you can't shake a stick in the world of terrain visualization
without hitting a reference to Level of Detail (LOD) Terrain Algorithms.
Level of Detail algorithms use a set of heuristics to determine which
parts of a landscape need more detail to look correct. You'll no doubt
find a slew of references to Height Fields and GPS datasets too.
All of this is perpetrated by the military SimNet applications, however
it is now finding its way into more trivial persuits.
of the many technical challenges to terrain rendering is how to store
the features inherent in a landscape. Height Fields are the de-facto
standard solution. Simply put, they are two-dimensional arrays which
hold the height of the terrain at that point. Think of a piece of graph
paper where a surveyor has filled in each square using his altitude
measuring tools. Height Fields are sometimes called Height Maps, I will
use the two terms interchangeably.
of LOD Terrain Algorithims
good overview of LOD Terrain Algorithms can be represented by three
papers [1 Hoppe][2 Lindstrom][3 Duchaineau]. In , Hugues Hoppe presents
an algorithm based on Progressive Meshes, a relatively new and
spiffy technique for adding triangles to arbitrary meshes as you need
more detail. The paper is an excellent read but a bit complex and has
high memory requirements for our needs.
second paper  is more our style, Lindstrom et. al. present a structure
called a Quad Tree that is used to represent a patch of landscape.
A Quad Tree recursively tessellates the landscape creating an approximation
of the Height Field. Quad Trees are very simple and efficient, sharing
many of the design principles of the next algorithm (such as recursion),
however the added bonuses of the next paper tilt the scale.
in  Duchaineau et.al. present an algorithm (Real-time Optimally
Adapting Meshes) based on a Binary Triangle Tree structure.
Here each patch is a simple isosceles right triangle. Splitting the
triangle from its apex to the middle of its hypotenuse produces two
new isosceles right triangles. The splitting is recursive and can be
repeated on the children until the desired level of detail is reached.
ROAM algorithm caught my eye while researching due to its simplicity
and extensibility. Unfortunately the paper is extremely short and only
minimal pseudocode is presented to hint at implementations. However,
it can be implemented from the most basic level up to the most advanced
optimizations in a nearly-continuous spectrum. This is helpful since
each step can be validated before continuing. Also, ROAM tessellates
very rapidly and allows dynamic updates to the Height Map.
engine presented here was patterned after the engine in Tread Marks
The lead programmer, Seumas McNally, was instrumental from its conception
to completion. See the Acknowledgments at the end for more info.
to the ROAM Implementation
code in the archive is written for Visual C++ 6.0 and uses OpenGL to
perform the rendering. I am new to OpenGL, but I have used every available
means to code this aspect of the project correctly. Comments and suggestions
on the engine's design or implementation are welcome.
project contains several files that are not covered in this explanation.
These files consist of utility routines and general application overhead
needed to run an OpenGL/Win32 application. Only "ROAMSimple.cpp" and
associated header files are examined here.
me introduce the algorithm with a bird's-eye view and then we can focus
on how the individual pieces interact:
Map files are loaded into memory and associated with an instance
of a Landscape class. Multiple Landscape objects may
be linked to generate terrains of infinite size.
- A new
Landscape object parcels out sections of the loaded Height
Map to new Patch class objects. The purpose for this step
tree-based structures used for the rest of the algorithm expand
RAM usage exponentially with depth, so keeping the areas small
limits their depths.
updates of the Height Field need a complete recalculation
of the variance tree over the modified locations. Overly large
Patches would be too slow to recompute in a real-time application.
Patch object is then called to create a mesh approximation
(tessellation). The Patches employ a structure called a Binary
Triangle Tree which stores implicit coordinates for the triangles
that will be displayed onscreen (instead of explicit X,Y,Z coordinates).
By storing the vertices in a logical manner, ROAM saves upwards of
36 bytes of RAM per triangle. Coordinates are calculated efficiently
as part of the rendering step (below).
tessellation, the engine traverses the Binary Triangle Tree created
in the previous step. Leaf nodes in the tree represent triangles which
need to be output to the graphics pipeline. The triangle coordinates
are calculated on the fly during the traversal.
Map File Format
have chosen the simplest route, reading in raw data files containing
8-bit height samples in row major format. This happens to be the exact
format my paint program outputs (by mere coincidence of course). The
Height Field is kept in memory at all times. I will discuss how to extend
the algorithm to take on larger datasets in the Advanced Topics section.
of storing a huge array of triangle coordinates to represent the landscape
mesh, the ROAM algorithm uses a structure called a Binary Triangle
Tree. This structure can be viewed as the result of a surveyor cutting
the landscape into triangular plots. The owners of these plots logically
view each other in terms of neighbor-relationships (left/right neighbor,
etc). Likewise, when an owner gives land as an inheritance, it is split
equally between the two children.
extend this analogy further, the original owner of a plot is the root
node of a Binary Triangle Tree. Other original owners are root nodes
of their own trees. The Landscape class acts like a local land-registry,
keeping track of all the original owners and which plot they owned.
The registry also keeps records of all inheritances from parents to
more generations of children, the more heavily surveyed the land becomes.
Any amount of detail can be produced simply by expanding the 'population'
in areas which need better approximations. See Figure 1 for an example.
1. Bindary triangle tree structure levels 0-3
Triangle Trees are represented by the TriTreeNode structure and keep
track of the five basic relationships needed for ROAM. Refer to Figure
2 for the standard view of these relationships.
// Our Left child
// Our Right child
// Adjacent node, below us
// Adjacent node, to our left
// Adjacent node, to our right
2. Basic binary triangle with children and neighbors.
creating a mesh approximation for the Height Field, we will recursively
add children to the tree until the desired level of detail is reached.
After this step is complete, the tree can be traversed again, this time
rendering the leaf nodes as actual triangles onscreen. This two-pass
system is the basic engine, and requires resetting for each frame. One
nice feature of the recursive method is that we are not storing any
per-vertex data, freeing up huge amounts of RAM for other goodies.
fact, the TriTreeNode structures are created and destroyed so many times
that the most efficient method of allocation is mandated. Also, there
may be tens of thousands of these structures, so even one extra pointer
would bloat the memory requirements tremendously. The TriTreeNode structures
are allocated from a static pool, bypassing the overhead of dynamic
memory allocation, which also gives us a rapid method for resetting
of Landscape Class
Landscape class acts as the high-level encapsulator for the dirty details
of landscape rendering. From the point of view of the application, the
landscape should simply appear in the screen buffer after a few simple
setup calls. Here's the important bits of the Landscape class
void Init(unsigned char *hMap);
// Initialize the whole process
// Reset for a new frame
// Create mesh approximation
// Render current mesh static
// Allocate a new node for the
static int m_NextTriNode;
// Index to the next free TriTreeNode
static TriTreeNode m_TriPool;
// Pool of nodes for tessellation
// Array of patches to be rendered
unsigned char *m_HeightMap;
// Pointer to Height Field data
Landscape class manages large square plots and can work together with
other Landscape objects each with their own plots. This design comes
into play later when you'll want to page-in larger terrain sets. During
initialization, the Height Map is cut into more manageable pieces and
given to new Patch objects. It is the Patch class and associated
methods that we will spend the most time on.
the simplicity of the functions. The Landscape class is designed to
be easily dropped into a rendering pipeline -- especially given the
gratuitous hardware z-buffering available these days. Several globals
are used to further simplify this demo.