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.