Normally you think of the triangles in a BinTriTree with the hypotenuse down, and with two children, a Left Child and a Right Child. Look at the simple BinTriTree represented below. The root triangle is A, with a Right Child B, and a Left Child C. C has a Right Child D, and a Left Child E. This subdivision can theoretically go on forever, though you usually stop once you've reached the granularity of your regular array (though you can go finer using algorithmic sampling).
In order to arbitrarily refine a particular triangle in the tree without causing cracks or T-junctions, you also need to store three more pointers in each BinTriTree node (or array indecise, depending on how you pool your node structures), a Left Neighbor Pointer, a Right Neighbor Pointer, and a Bottom Neighbor Pointer. The Left and Right Neighbors point to the triangles that are on the left and right with the hypotenuse down, and the Bottom Neighbor is the triangle that meets the hypotenuse. Note that Neighbor Pointers of lowest-level nodes should always point to other lowest-level nodes; if a neighboring triangle is split, all neighbor pointers should be updated to point to the new children.
Here's psuedo code for splitting a binary triangle in a tree:
Split(BinTri *tri){
if tri->BottomNeighbor is valid {
if tri->BottomNeighbor->BottomNeighbor != tri {
Split(tri->BottomNeighbor)
}
Split2(tri)
Split2(tri->BottomNeighbor)
tri->LeftChild->RightNeighbor = tri->BottomNeighbor->RightChild
tri->RightChild->LeftNeighbor = tri->BottomNeighbor->LeftChild
tri->BottomNeighbor->LeftChild->RightNeighbor = tri->RightChild
tri->BottomNeighbor->RightChild->LeftNeighbor = tri->LeftChild
}else{
Split2(tri)
tri->LeftChild->RightNeighbor = 0;
tri->RightChild->LeftNeighbor = 0;
}
}
Split2(tri){
tri->LeftChild = AllocateBinTri();
tri->RightChild = AllocateBinTri();
tri->LeftChild->LeftNeighbor = tri->RightChild
tri->RightChild->RightNeighbor = tri->LeftChild
tri->LeftChild->BottomNeighbor = tri->LeftNeighbor
if tri->LeftNeighbor is valid {
if tri->LeftNeighbor->BottomNeighbor == tri {
tri->LeftNeighbor->BottomNeighbor = tri->LeftChild
}else{
if tri->LeftNeighbor->LeftNeighbor == tri {
tri->LeftNeighbor->LeftNeighbor = tri->LeftChild
}else{
tri->LeftNeighbor->RightNeighbor = tri->LeftChild
}
}
}
tri->RightChild->BottomNeighbor = tri->RightNeighbor
if tri->RightNeighbor is valid {
if tri->RightNeighbor->BottomNeighbor == tri {
tri->RightNeighbor->BottomNeighbor = tri->RightChild
}else{
if tri->RightNeighbor->RightNeighbor == tri {
tri->RightNeighbor->RightNeighbor = tri->RightChild
}else{
tri->RightNeighbor->LeftNeighbor = tri->RightChild
}
}
}
tri->LeftChild->LeftChild = 0
tri->LeftChild->RightChild = 0
tri->RightChild->LeftChild = 0
tri->RightChild->RightChild = 0
} 
In the example above, if triangle A splits, the Diamond formed by A and B will be easily split. However if triangle 1 is asked to split, triangle 2 will need to be split first, so that its Right Child forms a diamond with 1, and then the two triangles in the Diamond can be split. Splitting a triangle deep in a BinTriTree can sometimes cause a recursive chain reaction of many forced splits, but they are required to keep the tree in order.
With the fundamental building block of Binary Triangle Trees laid bare, it's easy to see how it can be used for the real time display of highly detailed terrain. When tessellating a regular height array into triangles using a BinTriTree, there are a number of criteria that can be used to decide when a triangle should be split further, and when it should be left as-is:
- If the triangle is in the view frustum.
- If the pre-computed variance of the actual height values within the triangle's area vs. the flat plane of the triangle (as scaled by the distance from the camera) is greater than some defined maximum-variance quality setting. (This is the most critical one for variable frequency terrain.)
- If the triangle is facing the viewer.
- If the triangle is close to an important object that is resting on the ground.
int CalcVariance(tri){
int RealHeight = the map height at the middle of the hypotenuse
int AvgHeight = the average of the real heights at the two ends of the hypot
int v = abs( RealHeight - AvgHeight )
if tri->LeftChild is valid {
v = max( v, CalcVariance(tri->LeftChild) )
}
if tri->RightChild is valid {
v = max( v, CalcVariance(tri->RightChild) )
}
return v
}For more information on how to use Binary Triangle Trees for real time variable Level of Detail terrain rendering, have a look at the ROAM paper. It's only available as PDF or PostScript, but it's well worth printing out and reading a few times over.
Another paper to check out is Hugues Hoppe's "Smooth view-dependent level-of-detail control and its application to terrain rendering", available at his home page at Microsoft. It takes a different look at view-dependant LOD rendering, with an algorithm that should work great for caves and overhangs, but lacking the simplicity and mutability (real time craters etc.) of methods based on a regular height array.
Here's one I've been forgetting to add for a while. See Peter Lindstrom's Home Page for another interesting paper on terrain rendering. Also check out this page for some really cool ideas for random terrain generation algorithms.
Copyright 1998-1999 by Seumas McNally.
No reproduction may be made without the author's written consent.
Courtesy Of Longbow Digital Artists
