A Real-Time Procedural Universe, Part Two: Rendering Planetary Bodies
March 18, 2019
March 18, 2019
Press Releases
March 18, 2019
Games Press

If you enjoy reading this site, you might also want to check out these UBM Tech sites:

# A Real-Time Procedural Universe, Part Two: Rendering Planetary Bodies

August 10, 2001 Page 1 of 3

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.

As a side note, when I wrote the initial version of this spherical ROAM algorithm (more than a year ago), I couldn't find anything on the Internet regarding spherical DLOD algorithms. Since then, a number of projects have popped up using various techniques. I still haven't seen anyone take the same approach I did, but now you can find more information on this subject if you look for it.

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.

Page 1 of 3

### Related Jobs

LeFort Talent Group — Toronto, Ontario, Canada
[03.17.19]