Real-Time Dynamic Level of
Detail Terrain Rendering with ROAM

Contents

Introduction to Terrain Visualization Explanation of Patch Class Roam Engine Qualifiers

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 {
    TriTreeNode *LeftChild;
// Our Left child
    TriTreeNode *RightChild;
// Our Right child
    TriTreeNode *BaseNeighbor;
// Adjacent node, below us     
    TriTreeNode *LeftNeighbor;
// Adjacent node, to our left     
    TriTreeNode *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:
    void Init(unsigned char *hMap);
        // Initialize the whole process
    void Reset();
        // Reset for a new frame
    void Tessellate();
        // Create mesh approximation
    void Render();
        // Render current mesh static
    TriTreeNode *AllocateTri();
        // Allocate a new node for the mesh
protected:
    static int m_NextTriNode;
        // Index to the next free TriTreeNode
    static TriTreeNode m_TriPool[];
        // Pool of nodes for tessellation
    Patch m_aPatches[][];
        // Array of patches to be rendered
    unsigned 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.

Explanation of Patch Class

The Patch class is the meat & potatoes of the engine. It is roughly broken into two halves, the stub half and the recursive half. Here's the data declaration and stub half of the Patch class:

class Patch {
public:
    void Init( int heightX, int heightY, int worldX, int worldY, unsigned char *hMap);
        // Initialize the patch
    void Reset();
        // Reset for next frame
    void Tessellate();
        // Create mesh
    void Render();
        // Render mesh void
    ComputeVariance();
        // Update for Height Map changes
    ...

protected:
    unsigned char *m_HeightMap;
        // Adjusted pointer into Height Field
    int m_WorldX, m_WorldY;
        // World coordinate offset for patch

    unsigned char m_VarianceLeft[];
        // Left variance tree
    unsigned char m_VarianceRight[];
        // Right variance tree

    unsigned char *m_CurrentVariance;
        // Pointer to current tree in use
    unsigned char m_VarianceDirty;
        // Does variance tree need updating?

    TriTreeNode m_BaseLeft;
        // Root node for left triangle tree
    TriTreeNode m_BaseRight;
        // Root node for right triangle tree
    ...

In the flow of code, the stub functions explained below are called for each Patch object held by the parent Landscape. The Patch class method names are equivalent to the Landscape methods which call them. These methods are rather simplistic so there is no need for a detailed analysis:

Init() requires the offsets into the Height Field array and World. These are used for scaling the patch over different sizes of terrain. The pointer to the Height Field is adjusted to point to the first byte of this patch's data and stored internally.

Reset() erases any references to invalid TriTreeNodes, followed by relinking the two Binary Triangle Trees that make up each patch. It hasn't been mentioned until now, but each patch is actually made up of two discrete Binary Triangle Trees fitted together into a square (called a 'Diamond' in the ROAM paper). Take a look at Figure 2 again if you're confused. Much more detail on this in the next section.

Tessellate() is the first of our stub functions. It simply passes the proper parameters for the highest level triangles (the two root nodes from each patch) on to the recursive version of the function. Same goes for Render() and ComputeVariance().

ROAM Guts

So far we've only discussed the support structure for the actual algorithm. Now it's time to get to the goods. It might be handy to have a copy of the ROAM paper at this point, but I'll explain it as we go. Refer back to Figure 2 with the triangle relationships, and stele yourself for the next phase.

First we must define a metric for visible error in a mesh approximation. The method I use is a clone of the Tread Marks engine called 'Variance'. We will need such a metric for deciding when a node should be split (to add detail), and how deeply to split it. The ROAM paper uses a metric based on nested world- space bounds. While this metric is more accurate, it is also vastly slower.

Variance is the difference in height of the interpolated hypotenuse midpoint for a binary triangle node and the actual Height Field sample at that point. Simply put, how far off is the current binary triangle node from the actual Height Field area it covers. This calculation is relatively quick and only requires one memory hit for the Height Field lookup:

triVariance = abs( centerZ - ((leftZ + rightZ) / 2) );

But wait, there's more! We can't just calculate the variance for the two root Binary Triangle Trees of each Patch because the error associated with this calculation is too high. It has to be calculated deeper into the tree, then averaged back up to get a better estimate. The depth of this calculation for the demo can be specified at compile time.

Normally, the variance calculation would be required for each frame, however it won't change unless the underlying Height Field changes. Therefore we introduce a Variance Tree which works alongside the Binary Triangle Tree.

A Variance Tree is a full-height binary tree written into a sequential array. A few simple macros allow us to navigate the tree efficiently, and the data we fill it with is a single byte value of difference per node. Refer to Figure 4 if you've not encountered this structure before. Two variance trees are stored in the patch class, one each for the Left & Right Binary Triangles.

Figure 4. Implicit binary tree structure

Now we can get back to the job of creating an approximate mesh. Given our error metric (variance), we will decide to split the Binary Triangle node over a particular spot if its variance is too high. That is, if the terrain under the current triangle is bumpy, then we should split it to give a better approximation. Splitting entails creating two child nodes that exactly fill the parent triangle's area (see Figure 1 for an example).

After moving down to the children, we repeat the process. The variance roughly drops in half each iteration. At some point we either find smooth enough terrain to approximate with a single triangle, or we run out of 'steps'.. after all we can only create meshes down to the resolution of the Height Field, no more.

Figure 5. Terrain displayed at Low, Optimal and High variance settings

There's still one more complication. When splitting Binary Triangle Trees that are adjacent on the landscape, cracks will often appear in the mesh. These cracks are due to uneven splitting of the trees across patch boundaries. This problem is illustrated in Figure 6.

Figure 6. Patch showing cracks in mesh

To fix this, ROAM makes use of the neighbor pointers and an interesting fact of the mesh itself: Neighbors of a particular node are either of the same level, one level finer (for Right/Left Neighbors), or one level more coarse (for Base Neighbors). We apply this during the creation of the mesh in order to keep neighboring trees in sync with us.

It comes down to a simple rule: Only split if the current node and its Base Neighbor both point to each other (see Figure 7). This relationship is referred to as a Diamond. It is special because a split of one node in a Diamond can be mirrored by the other without causing cracks in the mesh.

Figure 7. Split operation on a diamond

Three cases exist when attempting to split a node:

1. The Node is part of a Diamond - Split the node and its Base Neighbor.
2. The Node is on the edge of the mesh - Trivial, only split the node.
3. The Node is not part of a Diamond - Force Split the Base Neighbor.

A Forced Split is a recursive traversal of the mesh which ends when it finds a Diamond or an edge triangle. Here's how it works: When splitting a node, check to see that it is part of a Diamond first. If not, call a second split operation on the Base Neighbor to create a Diamond, then continue with the original split.

The second call to split will do the same check, and recurs the process again if need be. Once a node is found that can be split legally the recursion unwinds, splitting nodes along the way. Figure 8 illustrates this.

Figure 8. Forced split operation

So let's review. Given a patch made up of two Binary Triangle Trees covering a particular area of the Height Field, we will perform the following operations:

1. Compute Variance Tree - Fill out a full-height binary tree with variance data for each Binary Triangle Tree. 'Variance' is the metric we are using to determine if our approximation is good enough. It is the difference between the height sample at the middle of the hypotenuse versus the interpolated height from the two points which border the hypotenuse.
2. Tessellate the Landscape - Using the variance tree we will split our Binary Triangle Trees by adding children if the variance of the top level is undesirably high.
3. Forced Splits - If the node we are attempting to split is not part of a Diamond, then call a Forced Split on the offending node. This will give us a Diamond to complete the original split operation.
4. Repeat - The tessellation step is repeated on the children until all the triangles in the Binary Triangle Tree are under the variance limit for the current frame - or until we run out of nodes in our allocation pool.

Return to Patch Guts

Now that we have all the details of the ROAM algorithm, let's finish up the Patch class implementation. All of the recursive functions (except Split) take coordinates for the triangles they represent. These coordinates are calculated on the stack and passed down to the next level, or given to OpenGL for rendering. Even at the deepest level of the Binary Triangle Tree, there are rarely more than thirteen triangles on the stack.

This is the basic algorithm for recursion that the following functions use:

int centerX = (leftX + rightX) / 2;
    // X coord for Hypotenuse center
int centerY = (leftY + rightY) / 2;
    // Y coord...
Recurs( apexX, apexY, leftX, leftY, centerX, centerY);
    // Recurs Left
Recurs( rightX, rightY, apexX, apexY, centerX, centerY);
    // Recurs Right

Recursive Patch Class Functions:

void Patch::Split( TriTreeNode *tri);

unsigned char Patch::RecursComputeVariance(
              int leftX, int leftY, unsigned char leftZ,
              int rightX, int rightY, unsigned char rightZ,
              int apexX, int apexY, unsigned char apexZ,
              int node);

void Patch::RecursTessellate( TriTreeNode *tri,
                            int leftX, int leftY,
                            int rightX, int rightY,
                            int apexX, int apexY, int node);

void Patch::RecursRender( TriTreeNode *tri,
                        int leftX, int leftY,
                        int rightX, int rightY,
                        int apexX, int apexY );

Split() performs all the ROAM splitting including the Forced Split operation. It checks for a legal Diamond, allocates child nodes, links them into the surrounding mesh, and calls additional Splits where needed.

RecurseComputeVariance() takes the full set of coordinates for the current triangle and a few extra bits of info to keep track of where we are. Variance for the triangle is calculated and combined with that of its children. I chose to pass in the height for each point as well as its X & Y coordinates in order to reduce the memory hits on the Height Field array.

RecurseTessellate() is where the Level of Detail operation is performed. After calculating distance to the camera, it adjusts the variance of the current node by a factor of the distance. This makes closer nodes have larger variances. The resulting mesh will use many triangles near the camera and fewer in the distance. Distance is calculated using a square root for simplicity (which is slow and should be replaced with a faster method).

RecurseRender() is remarkably simple, but take a look at the Triangle Fanning optimization under Advanced Topics for the next step up from here. Basically, if the current triangle is not a leaf node, recurs into the children. Otherwise, output a single triangle to OpenGL. Note that the OpenGL rendering is not optimized, but rather designed for maximum readability. That's all folks! We've covered everything you'll need to understand the code. The rest is icing for those who want to take the next step. But first, I'll give some engine qualifiers, and a note on the variance calculations.