Longbow Digital Arts - Seumas's Programming Page

Seumas's Programming Page

Arcade Games:

Shopping:

General Info:

More LDA:

Cool Stuff:

Other:

Binary Triangle Trees and Terrain Tessellation:

A Binary Triangle Tree (bintritree) is a very interesting data structure. They combine the simplicity of a Binary Tree (each node having only two descendants) with the 2-dimensional area covering properties of a Quad-Tree. You also get the advantage of all areas being right isosceles triangles (a 90 degree angle connecting two equal sides) that are perfect for throwing at a 3D rendering API, and will never, ever develop cracks or T-junctions. This makes BinTriTrees especially handy for tessellating regular arrays (e.g. height fields) to non-regular triangle densities, so that e.g. close to the viewer you tessellate to a high density, and far from the viewer you use a very low triangle density.

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
}

As you can see from the steps above, when a triangle to be split doesn't share a hypotenuse with its bottom neighbor, the bottom neighbor is forced to split first. Since bottom neighbors will always be either at the same level or one level higher, it will only ever need to be forced to split once, before it is split normally in combination with the original triangle. Two triangles that share a hypotenuse are referred to as a Diamond, and happen to form a perfect square, which comes in handy when representing areas such as square 2D arrays using BinTriTrees. To encompass a square area, you will actually need two separate Binary Triangle Trees in a Diamond formation. As long as their Neighbor pointers are properly connected to each other, it won't matter that they are two separate trees descending from two separate root nodes. You can use this fact to easily create multiple linked sets of trees representing large tiles of terrain data.

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.

Pre-computing "variance" is easy, and can be handled very well using a recursive function. The only sticky issue is how to store the variance tree. If your terrain is small, you may be able to store a tree of variance values all the way down to the lowest level representable. However with even reasonably large terrain, storing all variance values becomes prohibitively expensive, and you have to cap the variance tree at some level higher than the lowest. I personally use a byte-based implicit tree, which is essentially a large array of bytes, with one byte for each triangle in a BinTriTree down to a certian level, with that byte holding the "variance" for that triangle. The following pseudo code should calculate the variances for a tree, with storing variances left as an excercise for the programmer. By adding a check to see if each triangle is within a "dirty rectangle" before recursing further, you can easily recalculate variances for just a small portion of a map, such as when a crater is blasted in real time.

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
}

August 31, 1999 update: See this post on our Programming Forum for an explanation of implicit binary trees, as suggested for Variance storage above.

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-dependent 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.

August 31, 1999 update: 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.

Back

Comments? Questions? Know of a good programming page? Send me email!