Terrain rendering is a popular area of research in modern games. From Microsoft’s Flight Simulator series to Bungie’s Halo, games that take place in the outdoors have to be able to render large areas of terrain in an efficient manner.

The most prominent method for achieving this on modern hardware is a method called level of detail. The idea behind level of detail is simple; do less processing on pieces of terrain that are very far away from the user’s viewpoint so that more processing can be focused on areas that the user can clearly see. This article will focus on a branch of the level of detail concept known as discrete level of detail (DLOD).

I will be presenting a new technique for generating index buffers that can be used when implementing discrete level of detail in terrain rendering. This algorithm addresses specifically the issue of index buffer generation, but also has a few extra benefits as a byproduct of the technique. For comparison with current techniques, I will be referring to an article written by Greg Snook that addresses LOD using an approach called interlocking tiles (ILT). I will point out some of the drawbacks of ILT and how using binary triangle trees (BTT) can eliminate them. Greg’s article can be found in Game Programming Gems 2 [Snook01].

What we’re really trying to do with LOD is optimize the rendering pipeline by sending down fewer triangles for pieces of terrain that are far away from the camera. As the distance to the camera increases, the number of distant triangles being represented by a small number of pixels increases. We can save time in the rendering pipeline by reducing the number of distant triangles that are being rendered. Discrete level of detail is achieved by using different index buffers to represent different sets of triangles using the same patch of vertices. Each patch is a square section of vertices. The total size of the vertex patches must conform to equation 1.

Equation 1: Where s is the total number of vertices in the patch

In this equation, n will be the deciding factor in how big your patches are, as well as how many levels of detail are possible with that patch. We’ll talk shortly about how n relates to the number of detail levels.

Figure 1 illustrates how a single patch of vertices can be used to represent different levels of detail. This figure is shown with the triangles laid out as they are in the ILT system.

Figure 1: The same vertices can be used to render different levels of detail

You can see here that these patches are 17x17, conforming to our previously stated equation (2n + 1)2, where n = 4. The patch on the left is using an index buffer that specifies only 8 triangles, while the patch on the right is using an index buffer specifying 32 triangles. This idea is the basis for DLOD in terrain rendering. As patches move farther away from the camera, index buffers with a lower triangle count can be used to represent the patch.

We can notice one problem right away, which is that when patches of different detail levels are placed next to each other, T-junctions form on the borders creating nasty cracks in the terrain. This problem is illustrated in figure 2.

Figure 2: T-Junctions occur between patches of different detail levels

In the ILT system, the solution to this problem is to create linking pieces. Linking pieces take into account the neighboring patches’ LOD and use index buffers that were built specifically to link up to those levels. Figure 3 demonstrates this principle.

Figure 3: The lighter colored area shows the linking piece used to eliminate the T-Junctions

As you can see in Figure 3, the ugly T-Junctions are now gone and our terrain would be nice and smooth at this point. However, these linking pieces must be defined by hand for all four sides of the patch, and for each level of detail. In addition, 16 body pieces must be defined for each level of detail. Each of these body pieces makes room for different variations of linking pieces. Table 1 shows the number of buffers that have to be created for a patch with 4 levels of detail.