Mipmapping (explained in detail in Chapter 18, "Texture Mapping") is a texture mapping technique aimed at improving the visual quality of distant, textured primitives. In a distant triangle, the screen area of the triangle (in pixels) will be smaller than the size of the texture. This means each pixel gets to be textured by several texels, and as the triangle moves even slightly, flicker appears. Texture mipmapping works by precomputing a series of scaled-down texture maps (½, ¼, and so on) called mipmaps. Mipmaps are prefiltered so they average texel value correctly. Then, when texturing, the triangle is textured using the mipmap that most closely resembles its screen size. This way flicker is reduced, and even distant triangles get proper texturing.
Based on the same concept, Willem de Boer devised the geomipmapping algorithm (www.flipcode.com/tutorials/geomipmaps.pdf), which implements a CLOD terrain system by using mipmaps computed not on textures, but on the terrain geometry (hence the name). All we need to do is select the right geometrical representation depending on the distance to the viewer, and make sure the seams where two different representations meet merge smoothly without visible artifacts.
The concept behind geomipmapping can be adapted to any terrain data structure. However, because it is a texture-like approach, the easiest way to use it is to start from a heightfield representation. Incidentally, heightfields can be represented using grayscale images, so the similarities with texture maps are still present. We then need to compute the geometry mipmaps. To do so, we can scale down the heightfield bitmaps using image processing software or simply compute them at runtime. Just remember that mipmaps are computed sequentially by dividing the last texture map's size by a factor of two, combining each of the four texels of the initial map into a single, averaged value. Again, building geometry mipmaps is no different than working on textures.
Remember that your terrain size must be a power of two for this method to work (because of the subdivision step). Specifically, terrain size must be in the form 2n+1 because we need an extra vertex to make sure we get a power-of-two number of quads. See Figure 14.4, which shows this in a 4x4 mesh, using 5x5 vertices.
Figure 14.4. To create a 4x4 triangle mesh (which actually holds 32 triangles), we need a 5x5 vertex mesh.
The first step in the rendering process is to effectively load the data structures in memory. For geomipmapping, terrain data is organized in a quadtree; each leaf node contains what's called a terrain block. Terrain blocks are pieces of terrain consisting of several triangles each. In his initial formulation, de Boer suggests using a 4x4 mesh (consisting of 32 triangles). To build the quadtree, you start with the whole terrain data set. The root node stores its 3D bounding box, and then each of the four descendants contains one of the four subquadrants of the data set. Each subsequent node will contain the bounding box of the incoming set and pass four pointers to its descendants until a node is exactly composed of a single terrain block. A 257x257 terrain map will require exactly six levels (measuring 256, 128, 64, 32, 16, 8, and 4 triangles across each). Organizing the data in a quadtree will help us perform fast hierarchical clipping. We will depth-traverse the tree, and as soon as the bounding box from one node is rejected as totally invisible, the whole subtree will be rejected, hence speeding up the calculations significantly.
Notice how, up to this point, we have not performed any LOD. All we have done is arrange the source data in a quadtree, which will indeed speed up clipping, but that's about it. In fact, we could stop here and implement the preceding algorithm. Using hardware culling, it would be a good way of selecting only those triangles effectively onscreen. Besides, the block layout allows for packed primitives such as strips and indexed triangle lists to be used, delivering quite good performance.
But there is no LOD policy yet, so distant triangles would probably eat away all our CPU cycles, effectively killing performance. This is where geomipmaps enter the scene to speed up the rendering process. The idea is straightforward: As we reach the leaves of the quadtree, we decide which resolution to use for that terrain block. We need to store not only the high-resolution terrain, but mipmapped versions as well. The decision criteria, as usual, depend on the quantity of detail in the block and the distance to the viewer. We begin by computing the error of a geometry block, expressed as the maximal distance (in screen space) from a mipmap's position to the real position of the actual geometry. We call this an error because it is a measure of how much deviation actually exists between the real value (taken from the mesh) and the value we are using for rendering purposes.
Thus, we take all the vertices in a block and compute the distances from the mipmapped vertices to the real geometry. When projected to the screen, these return pixel amounts, which take into consideration detail (the more detail, the more error) and distance (the more distance, the less error). Then, we work with a fixed threshold (values of about 5 pixels are frequent) and select the first mipmap level so error is bounded. Thus, distant geometry blocks will be heavily simplified, and closer blocks will not. An interesting side effect of such an approach is that top-down cameras will usually end up rendering lower resolution meshes, because the screen-space error will be virtually none.
Using geomipmapping, we must deal with two potential issues in order to convey a good sense of realism. First, we must deal with the geometry gaps that occur whenever two blocks of different resolution are adjacent. This breaks the continuity of the terrain. Second, we must ensure that a change in detail in a certain area is virtually imperceptible, so the player does not realize the LOD work that is taking place. Let's examine each problem and the way to deal with it.
We will start by dealing with geometry cracks and gaps, which occur whenever two blocks with different mipmaps are adjacent. This is a common problem that is shared by most terrain algorithms, not just mipmapping, so the solution we will propose is valid for other algorithms as well. A good overview of different approaches can be found in de Boer's original paper. The best solution proposed is to alter the connectivity of the higher detail mesh so it blends with the lower detail mesh seamlessly. Basically, we have a high detail mesh and a lower detail mesh (see Figure 14.5, left). Then, all we have to do is reconstruct the high-res mesh so it connects cleanly with the low-res mesh. By skipping one in each of the two vertices of the high-res mesh, we can ensure that both meshes connect properly with no gaps. This implies that some vertices in the high-res meshes will remain unused, but the result will be unnoticeable.
Figure 14.5. Left: Connected, unsown mesh. Right: Skip one of every two vertices in the high-res mesh and reconstruct the face loops to weld terrain blocks together.
Let's now discuss how to avoid sudden pops that take place whenever we change the resolution level of a terrain block. A powerful technique for this problem is called geomorphing and involves smoothing the transition from one mipmap to the next by linear interpolation. The key idea is simple: Popping is caused whenever we change the resolution suddenly, so new vertices appear (each with its own shading), and overall we see an abrupt change in appearance. Geomorphing works by ensuring that no single frame actually changes the appearance more than a fixed threshold. Whenever we want to increase the detail level, we start by using the high-detail mesh but with its new vertices aligned with the plane of the low-res mesh. Thus, we change a low-res mesh by using a high-res mesh, but the Y of each point in the terrain is still the same for both resolutions. We then take these interpolated Y values and progressively shift them to their final position as the camera approaches. This way detail does not appear suddenly but "pops in" slowly, ensuring continuity and eliminating pops completely.