This article is dedicated to the memory of Seumas McNally. Please see the epilogue at the end of this article.

The demo to accompany this article can be found here.

Like many 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.

In 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.

Introduction to Terrain Visualization

It 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.

One 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.

Overview of LOD Terrain Algorithims

A good overview of LOD Terrain Algorithms can be represented by three papers [1 Hoppe][2 Lindstrom][3 Duchaineau]. In [1], 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.

The second paper [2] 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.

Finally, in [3] 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.

The 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.

The engine presented here was patterned after the engine in Tread Marks (http://www.TreadMarks.com). The lead programmer, Seumas McNally, was instrumental from its conception to completion. See the Acknowledgments at the end for more info.

Introduction to the ROAM Implementation

The 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.

The 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.

ROAM Source Explanation

Let me introduce the algorithm with a bird's-eye view and then we can focus on how the individual pieces interact:

• Height 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 is two-fold:
  1. The tree-based structures used for the rest of the algorithm expand RAM usage exponentially with depth, so keeping the areas small limits their depths.
  2. Dynamic 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.
• Each 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).
• After 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.

Height Map File Format

I 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.

Binary Triangle Trees

Instead 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.

To 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 children.

The 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.

Figure 1. Bindary triangle tree structure levels 0-3

Binary 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.

struct TriTreeNode {
&nbspTriTreeNode *LeftChild;
// Our Left child
&nbspTriTreeNode *RightChild;
// Our Right child
&nbspTriTreeNode *BaseNeighbor;
// Adjacent node, below us
&nbspTriTreeNode *LeftNeighbor;
// Adjacent node, to our left
&nbspTriTreeNode *RightNeighbor;
// Adjacent node, to our right
};

Figure 2. Basic binary triangle with children and neighbors.

When 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.

In 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 the state.

Figure 3. Typical patch of terrain. From left to right, Wireframe (overhead view), Lit, and Textured

Explanation of Landscape Class

The 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 definition:

class Landscape {
public:
&nbspvoid Init(unsigned char *hMap);
// Initialize the whole process
&nbspvoid Reset();
// Reset for a new frame
&nbspvoid Tessellate();
// Create mesh approximation
&nbspvoid Render();
// Render current mesh static
&nbspTriTreeNode *AllocateTri();
// Allocate a new node for the mesh
protected:
&nbspstatic int m_NextTriNode;
// Index to the next free TriTreeNode
&nbspstatic TriTreeNode m_TriPool[];
// Pool of nodes for tessellation
&nbspPatch m_aPatches[][];
// Array of patches to be rendered
&nbspunsigned char *m_HeightMap;
// Pointer to Height Field data
};

The 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.

Note 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.