Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Binary Triangle Trees for Terrain Tile Index Buffer Generation
August 12, 2020
Press Releases
August 12, 2020
Games Press

If you enjoy reading this site, you might also want to check out these UBM Tech sites:

# Binary Triangle Trees for Terrain Tile Index Buffer Generation

December 21, 2006 Page 2 of 4

So, we see that it requires a total of 72 different index buffers to set up a terrain with four levels of detail. One of the major issues with ILT is that as the level of detail gets higher, the number of linking pieces for each side becomes greater, resulting in ever increasing memory usage. We’ll see how this is totally eliminated using BTT shortly.

Another problem with ILT is that there is currently no way to generate these index buffers. Each body and linking piece has to be defined by hand. The inflexibility with this approach was the leading factor in my decision to research and implement a new technique. If you’d like a more in depth coverage on ILT, please refer to [Snook01] in the references section at the end of this article. Let’s move on to the new technique and see how we can use binary triangle trees to generate our index buffers and get some huge improvements for free on the side.

The idea behind binary triangle trees is simple. A triangle can be recursively bisected into two sub triangles whose vertices are related to their parent’s in a consistent pattern. If we’re using a patch of vertices that is defined according to our patch requirements [(2n + 1)2], each vertex of the new triangles will evenly match up with a vertex in the patch. Figure 4 illustrates this principle with a simplified patch of only 5x5 vertices.

When using BTT, each level of detail is defined as the splitting of all triangles in a given patch one time. It is interesting to note here that this means the number of detail levels available for a single patch is not calculated in the same way as in ILT. Equation 2 shows how to calculate how many levels of detail are available for a given patch size when using ILT.

Figure 4: Recursively splitting triangles will eventually use up all of the vertices in a patch

Equation 2: Where L is the levels of detail and n is the patch size exponent from Equation 1

For example, a 5x5 patch would be able to produce 3 levels of detail when using ILT. So, for each patch size increase, one extra level of detail will be attained. The following table shows the levels of detail possible with a given set of patch sizes when using ILT.

 Patch Size Levels of Detail 5x5 3 9x9 4 17x17 5 33x33 6 65x65 7

Table 2: Levels of detail possible for various patch sizes using ILT

The equation for calculating the number of detail levels for a given patch when using BTT is similar to Equation 2.

Equation 3: Where L is the levels of the detail and n is the patch size exponent from Equation 1

So we can see that by using BTT, the number of detail levels that can be achieved is almost a two fold increase over using ILT. Table 3 illustrates this.

 Patch Size Levels of Detail 5x5 5 9x9 7 17x17 9 33x33 11 65x65 13

Table 3: Levels of detail possible for various patch sizes using BTT

With the ability to have all these extra detail levels, you might think we’re going to be using way more index buffers and talking up tons more memory, right? Well, that actually isn’t the case at all. When using ILT, we had to create 16 body pieces for each level of detail, as well as all the linking pieces, in order to eliminate T-Junctions in the terrain. When using BTT, the concept of linking pieces is completely removed, and all we need are 15 index buffers. The linking information is built right into the patches, so extra linking piece buffers are not needed. In addition, only half of the detail levels need to link at all! Figure 5 illustrates this principle.

Figure 5: Half of the detail levels only require 1 buffer!

As you can see from the image, we only need to facilitate linking for odd detail levels. If you look at detail level two, you can see that it already seamlessly links to detail level three without us having to do any extra work! Two simple rules allow us to achieve this huge savings in memory. First, we make a simple rule that no neighboring patches can be more than 1 detail level away from each other. This isn’t really an issue in practice, because detail levels are assigned in a very linear fashion and are usually based on the distance from the camera. Second, patches will only link to detail levels that are higher than their own. Table 4 shows the index buffer usage for a 5x5 patch using BTT. Compare to Table 1.

 Levels of Detail Index Buffers Required Total Detail Levels 4 1 1 3 15 15 2 1 1 1 15 15 0 1 1 33

Table 4: Index buffers required for BTT

Page 2 of 4

### Related Jobs

Mountaintop Studios — Los Angeles, California, United States
[08.10.20]

Engine/Systems Engineer (remote)
Mountaintop Studios — Los Angeles, California, United States
[08.10.20]

Graphics Engineer (remote)
Mountaintop Studios — Los Angeles, California, United States
[08.10.20]

Network Engineer (remote)
Remedy Entertainment — Espoo, Finland
[08.10.20]

Senior Gameplay Programmer