Contents

Introduction to Terrain Visualization

Explanation of Patch Class

Roam Engine Qualifiers

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.

________________________________________________________________

Roam Engine Qualifiers