Gamasutra.com - Binary Triangle Trees for Terrain Tile Index Buffer Generation
It's free to join Gamasutra!|Have a question? Want to know who runs this site? Here you go.|Targeting the game development market with your product or service? Get info on advertising here.||For altering your contact information or changing email subscription preferences.
Registered members can log in here.Back to the home page.

Search articles, jobs, buyers guide, and more.

By Chris Dallaire
[Author's Bio]
Gamasutra
December 21, 2006

Binary Triangle Trees for Terrain Tile Index Buffer Generation

arrowrightPage One
arrowrightPage Two
arrowrightPage Three
arrowrightPage Four




[Submit Letter]
[View All...]
  


Features

Binary Triangle Trees for Terrain Tile Index Buffer Generation


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


join | contact us | advertise | write | my profile
news | features | companies | jobs | resumes | education | product guide | projects | store


Copyright © 2006 CMP Media LLC

privacy policy | terms of service