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
January 25, 2020
January 25, 2020
Press Releases
January 25, 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 4 of 4

It’s important to keep track of the triangle's original direction tag when splitting to produce its children. Each child needs to be either tagged with its parent’s direction, or tagged as “inner.” Inner triangles are those that don’t touch the tile border and do not need to be considered for further splitting. Figure 11 shows an example of inner triangles as a result of splitting.

Figure 11: Inner triangles produced a result of splitting

You can see that the second generation of eastern triangles has been split to produce two inner triangles. These triangles do not touch the borders of other tiles so they do not need to be considered for further splitting. Figure 12 illustrates how inner triangles can be safely ignored when splitting to the next detail level.

Figure 12: Inner triangles can be ignored in subsequent splitting operations

We can see that the third generation of eastern triangles can continue to be split as normal, and that the inner triangles are unaffected. This pattern will continue to be reproduced in the same way as we keep splitting to higher detail levels. In order to actually generate the index buffer for this tile, and all the other tiles we generate, we simply need to loop through each leaf triangles in the tree and add its three vertex indices to the final buffer.

In conclusion, I’ll recap on the pros and cons of using binary triangle trees for discrete level of detail in terrain rendering.

## Pros:

• Less memory usage than ILT
• More detail levels than ILT, resulting in less popping of the terrain
• Buffers can be generated algorithmically for any patch size
• Uniform lighting due to even more even triangle division

## Cons:

• Can only link to 1 detail level away. Not a real issue in practice
• Can’t support overhangs on the terrain. Same issues in other DLOD techniques

# References:

[Snook01] Snook G., “Simplified terrain using interlocking tiles”, Game Programming Gems 2, Charles River Media, 2001

Page 4 of 4

### Related Jobs

Disbelief — Chicago, Illinois, United States
[01.24.20]

Junior Programmer, Chicago
Disbelief — Cambridge, Massachusetts, United States
[01.24.20]

Junior Programmer, Cambridge, MA
Everi Games — Austin, Texas, United States
[01.24.20]

Game Developer
Insomniac Games — Burbank, California, United States
[01.24.20]

UI Developer