In Part One of this series I explained how to use a function based on Perlin noise and fractal Brownian motion (fBm) to dynamically generate any point on a planetary body from a set of coordinates. This article will focus on how to render those planetary bodies at real-time speeds using my own spherical version of the ROAMing (Real-time Optimally Adapting Mesh) terrain algorithm. For those of you who read Part One and downloaded the demo I provided, make sure you download the latest source code and Win32 executable files. I've made some significant performance improvements since then, and they are explained in this article.

There have been a number of articles published in the past few years on adaptive mesh algorithms, which are also called dynamic or continuous LOD (Level-Of-Detail) algorithms. Some good examples are "Real-Time Dynamic Level of Detail Terrain Rendering with ROAM" and "Continuous LOD Terrain Meshing Using Adaptive Quadtrees". However, all the articles I've read so far have drawn flat landscapes based mainly on a pre-built 2D height map. Using a little creative thinking, I managed to come up with a spherical version that dynamically generates height values as needed.

The Traditional ROAM Algorithm

If you haven't read anything about ROAM, I recommend that you read the online paper: "ROAMing Terrain: Real-time Optimally Adapting Meshes". For those who want to skip the gory details, I'll go over the concept more briefly here. The ROAM algorithm attempts to generate an optimal triangle mesh for quickly rendering large-scale terrain maps. It starts with a single square, which consists of two right triangles, covering the entire map. If more detail is needed, a vertex is added to the center of the square, splitting the two right triangles into four. Based on a view-dependent priority calculation, triangles are split recursively in the same fashion until the desired level of detail is reached. ROAM implementations typically implement two main functions that are called every frame, one called Update() to update the mesh and one called Draw() or Render() to draw it.

To determine when more detail is needed in the mesh, each triangle is assigned a split priority. A priority threshold is set, and any triangle that exceeds the threshold is split. A triangle's priority is calculated by determining the amount of visible error it contains. Visible error is essentially the actual amount of error in the triangle divided by the distance from the camera to that triangle. For any triangle that can be culled from the rendering process (i.e. outside the view frustum or facing away from the camera), the visible error should be 0 because the triangle isn't visible.

When splitting triangles in a 3D mesh, care must be taken to ensure that no cracks or seams appear in the mesh. The ROAM algorithm handles this by following one simple rule: except at the edges of the map, only a square can be split. In this case a square is defined as two right triangles of the same size sharing their longest edge. When you need to split a triangle whose neighbor along the longest edge is not the same size, you must split its neighbor first. If the neighbor isn't part of a square, then its neighbor must be split before that. This check continues recursively until a square is reached or the edge of the map is reached, and all triangles along the path are split as the recursion unwinds. The figure below illustrates how this works:

	Figure 1: Splitting triangle T requires multiple splits to avoid creating cracks in the mesh.

Attempting to split triangle T requires four new vertices to be added to the mesh. Those vertices and the new edges created are highlighted in red and numbered in order. The first vertex makes the bottom-right corner of the map into a square. The second vertex makes a diagonal square in the bottom center. The third vertex makes triangle T part of a square. Last but not least, the fourth vertex splits triangle T.

Because the mesh starts with two triangles and each is split recursively into two smaller triangles, a binary tree is often used to store the ROAM mesh in memory. In this case, each node in the tree contains a triangle at a certain level of detail, and each frame all the leaf nodes in the tree are rendered. Along with containing pointers to its vertices, the triangle object usually contains pointers to its neighbors and members dealing with its split priority.

To keep the mesh optimal as the camera moves around, we need to be able to remove triangles that are no longer needed. The rule for merging triangles back into their parent triangles is that, except at the edges of the map, only a diamond can be merged. A diamond is defined as four right triangles with their 90-degree angles sharing the same vertex, which is equates to a square that has just been split. To merge the diamond, just remove the center vertex and turn it back into a square. Unlike splitting a triangle through recursion, you must wait until a triangle becomes part of a diamond before you can merge it.

In addition, it's not very efficient to figure out if a particular triangle is part of a diamond and then figure out if that diamond needs to be merged. The best way to handle this seems to be to maintain a list of current diamonds at all times. Every split creates 1 diamond and destroys 0-2 diamonds, and every merge does the opposite. The diamond structure should contain pointers to its triangles and members dealing with its merge priority. Every frame merge priorities get checked, and all diamonds that fall below the split threshold get merged.

One of the best things about ROAM is the amount of control you have over the performance vs. visual quality trade-off. You can control it by fine-tuning the priority calculations, changing the priority threshold, setting limits on the frame rate, setting limits on the triangle count, or setting limits on the number of split/merge operations to perform per frame.
Probably the largest problem with ROAM is that mesh changes from one frame to the next might cause a visible "pop" in the terrain. This artifact can be reduced by a process called "geomorphing", where you gradually move vertices from the old position to the new position over a number of frames, smoothing the pop and making the transition less noticeable. You can also slowly change the vertex normal, color, and texture coordinates if necessary.