Binary Triangle Trees for Terrain Tile Index Buffer Generation

If you look back at Table 1 you can see that ILT uses twice as many index buffers as BTT and produces one less level of detail. So not only are we using less memory, but we’re also getting more detail levels. Another interesting thing to note about the performance of these two techniques is that ILT may require up to 5 index buffers being sent to the graphics card for any given patch. That would be the body plus 4 linking pieces. BTT always requires only 1 index buffer to be sent for each patch, regardless of its detail level or what it is linking to.

We’ve seen how using BTT can be an improvement over ILT as far as performance and memory usage, now we’ll talk a look at what really makes this technique shine – algorithmic generation of index buffers.

There are two key objects in the BTT algorithm for generating index buffers. First, we need to specify a triangle object that can be recursively subdivided into two smaller triangles. Second, we need a tile class that will be made up of these triangle objects in order to handle the higher level concept of a patch. For simplicity, I’m not going to be including any source code in this article. There is a demo available with source code included so you can take a look for yourself and see how it works internally. We’ll just stick to theory here.

A 5x5 patch will be our example for the remainder of the article. First, we’ll look at the special case level of detail 0. This level doesn’t require any triangle objects and can be defined by hand as it is only 6 indices. Figure 6 shows this case.

Figure 6: Level 0 is a special case that can be defined by hand

The index buffer here is just going to be six elements defining two unique triangles. Assuming a clockwise winding order, the indices would be { (0, 20, 4), (24, 4, 20) }. Note that we always start from the apex of the triangle when defining the index buffers. This level doesn’t have any linking cases so we’re done!

Level 1 is where we really start to get into using BTT and we’ll see here why they are so well suited for this task. Take a look at Figure 7.

Figure 7: Level 1 is made up of 4 triangles

Ok, so here is the main base patch. Basically what we’re looking at here is a patch with 4 triangles (It’s important to remember that in the construction of the patch, you will need to supply the starting vertices indices for each of the base triangles. The base indices are what will be used during the rest of the splitting operations). Each triangle is labeled with a cardinal direction. This is important because it will help us with understanding the linking portion later. At this point, we could continue to generate base detail levels by simply splitting each triangle. Figure 8 shows what base level 2 looks like.

Figure 8: Base level 2 is generated by simply splitting all the triangles

This is what detail level two would look like. Note that each child triangle is tagged with its parent’s direction. However, just generating base detail levels isn’t quite enough. We know that detail level 1 needs extra buffers to handle linking, so how are we going to do that? Well, the tile is keeping track of 4 main triangles (N, S, E, W), and each triangle can be split independently. If, for instance, we wanted to generate a level 1 triangle that would link up to a level 2 triangle on the east, we just split the east triangle once. Figure 9 shows what this looks like.

Figure 9: Level 1 with a split on the east triangle to link up to a level 2

So this would handle the case of linking up to a higher detail level on the east, but remember that we have a total of 14 combinations that might come up. Figure 10 shows the index buffers that need to be generated for every odd detail level.

Figure 10: The 14 index buffers needed for odd detail levels

Figure 10 shows all of the index buffers we will ever need to handle linking between detail levels. By examining the neighboring tiles, we can figure out which linking buffer to use based in which sides are bordered by higher detail levels. The final selected buffer is the only index buffer required to be sent to the card. Let’s talk a little bit about the details of splitting triangles.