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 realtime speeds using my own
spherical version of the ROAMing (Realtime 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 (LevelOfDetail) algorithms. Some good examples are "RealTime
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 prebuilt
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: Realtime 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 largescale 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 viewdependent 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 bottomright 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 90degree 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 02
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 tradeoff. You can control it by finetuning
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.