Contents |
|
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:
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:
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.
________________________________________________________________