The algorithm discussed in this section was proposed by Thatcher Ulrich of Oddworld Inhabitants at SIGGRAPH 2002. Its main focus is allowing massive terrain data sets to be displayed in real time. As an example, the classic demo of chunked LODs involves a Puget Sound data set that covers 160x160 km. The triangle data takes 512MB, and the textures require 3GB uncompressed (60MB in JPEG). Thus, the algorithm is very well suited for huge terrain data sets, such as the data sets found in flight simulators.
The algorithm starts with a huge data set, usually coming from a satellite picture. Then, it builds a quadtree so the root node contains a very low-resolution mesh from the original data set, and each descendant node refines the area covered by its parent in four quadrants, adding detail to the base geometry in each one of them. Leaf nodes then contain chunks of geometry that cover a very small area on the map, but provide very good quality.
A number of approaches can be used to implement this strategy. One possibility is to start at the leaves and build the quadtree bottom up. We start by dividing our picture into chunks of fixed sizes using a geometric progression. The base picture should be a power of two for this to work easily. For example, if the map is 4096x4096, we can start by doing chunks of 32x32 pixels. This means we will need a seven-layer quadtree. We then recurse by building the parent to each cluster of four chunks. Because we want this new cluster to have more or less the same geometric complexity as any one of its four descendants, we must apply a triangle reduction algorithm to the mesh. Overall, we will end up with chunks that are all about 32x32 triangles. Leaf nodes will represent small areas on our map, and as we move closer to the root, the area covered by the chunk will be much higher. So, any given level from our quadtree will cover the whole map. The only difference is the resolution at which we cover it. Take a look at Figure 14.11 to see the level of detail and huge data sets processed by a chunked LOD algorithm.
Figure 14.11. Chunked LOD demo by Thatcher Ulrich. If you look closely at the wire frame version, you will notice the skirts used to weld different resolution zones together.
Quadtree construction is usually performed as a preprocess. We start from a high-resolution reference mesh, creating lower resolution meshes by using mesh simplification algorithms. We then store these meshes hierarchically in the nodes of the quadtree: lower resolution, global meshes at the root, and then we refine them into higher resolution (and lower scope) meshes as we move toward the leaf nodes of the quadtree. For each node, we store a measure of its error with regard to the real data set. We compute the maximum geometric deviation of a chunk from the portion of the underlying mesh. Logically, nodes closer to the root will have higher error values, with errors converging to zero as we move toward the leaves. Then, at runtime, we set a screen-space maximum error threshold and use the nodes' error metrics to compute a conservative LOD error level. If a node has error level delta, the screen-space error is computed by:
where D is the distance from the viewpoint to the closest point in the bounding volume, and K is a perspective scaling factor that corrects the fact that the viewport is using perspective projection. The following equation is used:
Rendering the chunk quadtree is then pretty straightforward. The quadtree is traversed, using it to perform hierarchical clipping. Then, at each node we can choose between expanding it (thus, accessing higher detail data located closer to the leaves) or staying where we are, and use the current node's data to render it. The decision depends on the screen-space error metric, which determines if the region and the distance require further refinement or if we are fine with the current resolution. Thus, a view-dependent approach is used.
The problem with chunked LOD approaches is, as with ROAM and quadtrees, the appearance of pops and cracks. Pops are solved by geomorphing, which was explained in the "Geomipmapping" section. Remember that geomorphing involves transitioning from one base node to its children (and thus expanding data into a finer version), gradually. We start by placing the finer representation triangles along the planes used by the coarse version; we then interpolate those positions linearly with their final, fine detail version. This way detail in the terrain grows slowly, and popping is eliminated.
As for the cracks in the terrain, they can easily be solved by stitching terrain chunks together with additional mesh strips. Ulrich suggests sowing adjacent meshes by using vertical ribbons that join together the two meshes. This is the simplest of the possible approaches, and given the resolution at which we are working, results are fine. The ribbon will be limited in screen size due to our error metric bound, becoming virtually invisible.
An alternative is to use a skirt that surrounds each chunk. The skirt is simply a strip of triangles that vertically extends around the perimeter of the chunk. Its size is determined by the maximum error bound. With reasonable bounds (about five pixels typically), the skirt is unnoticeable, and assuming our texturing function is computed from X,Z values, texturing will work as expected. Skirts have an additional advantage over ribbons in that we do not really need to sew chunks together, so the algorithm is much simpler. We just place chunks beside each other, and use skirts to fill the gaps (see Figure 14.12).
A note on texturing: Texturing a chunk LOD approach is done in a very similar way to regular geometry processing. Textures are derived from an initial, high-resolution map (usually satellite pictures). Then, we build a texture quadtree similar in philosophy to the geometry quadtree. The root represents the lowest resolution texture, and each level toward the leaves expands the map, covering a smaller region with higher resolution. This way, at runtime, the criteria used to expand the geometry quadtree are recycled for the texture quadtree. Because texturing data sets are usually in the hundreds of megabytes, it is common to use two threads and load new texture portions in the background while we keep rendering frames to the graphics subsystem. All we need to do for this paging scheme to work is to be aware of the amount of memory available for texturing. As we move closer to the terrain, and new maps are paged in, we will be able to discard other maps (usually closer to the root of the tree). So the overall memory footprint for textures will stay consistent throughout the execution cycle.