The size of a full binary tree should be ((1 << Levels) - 1) nodes, which means if you're storing an implicit tree of bytes, you need that many bytes for the array.

Each "level" of the tree is represented by a contiguous set of array elements starting at a specific index. That starting index is computed with levelindex = ((1 << level) - 1), where level is 0 for the root node. There will be (1 << level) nodes at that level, as array entries progressing from (and including) levelindex.

To go to a node's left child, increment l and double i. For the right child, add another 1 to i.

Now there's another way to access the tree, which is better if you're doing a lot of jumping around. If you index the tree from 1, rather than 0 (as arrays normally are), it's really easy to jump around the tree. Just use a global node index G as the 1-based index into the array for this node. To go to the left child, double G. For the right child, double and add 1. To go back to the parent, divide by 2 (which is right shifting by 1).

If you're using an implicit tree to store a hierarchical set of multi-resolution information, such as the variance levels of triangles in a binary triangle tree, it is very much like a a 1-dimensional mip-mapped texture, as you might use for 3D rendering.

If you draw the tree on a piece of paper, it becomes pretty clear. Draw one box, which is the root. Then to the right draw 2 more boxes, and to the right of those 4 more boxes, and then 8 more. Each set of boxes is a level in the tree.

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

Correct, the morph is between the interpolated center of the parent's hypotenuse, and the real height at that location. The amount of morph is calculated by making the split test a "fuzzy" test, rather than a binary test. The fuzziness is on the side of "split", rather than "not-split". Just as the variance crosses the "split" boundary, the morph is completely towards the interpolated height. As the variance gets further into the "split" region, the morph progresses towards the fully sampled (from the height map) height, until after a certain variance, the sampled height is always used.

So it's basically:

if (TriVariance > VarianceLimit) { //Split tri.
	t = TriVariance - VarianceLimit;
	if (t < MORPH_RANGE) { //Tri is morphing.
		TriMorph = t / MORPH_RANGE;
	} else {
		TriMorph = 1.0; //Sampled height, no lerp.
	}
}

Using floats for all those variables. And of course you wouldn't use a divide by MORPH_RANGE, but instead a multiply by a pre-calculated 1.0 / MORPH_RANGE.

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

I get around the problem of different "morph" values on either side of the line by averaging the two morph values and using that average for both sides. It adds a little complication, but I think the morphing is worth it.

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

In my engine, "resetting the state" entails setting the NextBinTriPool index variable to zero, and deleting the handful of heap allocated "patch" structures which contain worldspace coordinates for their location, and pointers to the root nodes of two pool-allocated binary triangle trees. Which basically means that resetting state takes an insignificant amount of time.

I allocate "patch" structures dynamically since with the way the map wraps, you could theoretically have a large enough view distance to be able to see the entire map 2 or 3 times off in the distance, and obviously you wouldn't want those wrapped areas to be tessellated the very same. Thus it wouldn't work to pre-allocate patch structures only covering the physical extents of the height field.

Oh, and I don't store vertex coordinates or indices in my binary triangle structures, just child and neighbor pointers and some goop for geomorphs. Coordinates are passed and calculated on the stack in the recursive functions, with heights pulled out of the height field when needed.

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

... I don't use a priority queue. As I've said, my engine is not frame coherent, and rebuilds the trees each frame. This is a brute force, direct operation, with only a single "quality" value used to scale the distance at which a particular variance level is split. Forced splits don't require any vertex coordinates, since the triangle is just being split; it doesn't require any tests that would require vertex coordinates.

The split pass itself only accesses the pre-computed variance implicit tree, and the binary triangle structures. It doesn't concern itself with the height map directly. That gives me an idea, actually... Since all I am concerned with is the Z distance from camera of each bintri, I could probably optimize the splitting pass to only pass down a Z distance and a delta to be added and subtracted to find the Z distances of the children. If that worked I could really simplify my split pass...

Once the splitting is done, rendering is accomplished by recursively diving the trees again, passing down vertex coordinates on the stack, and batching up triangle fans when the leaves are processed.

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts