Author Topic:   Implicit variance trees?
New Member
posted February 13, 2000 02:21 AM            
Hi. I understand ROAM a lot better now, thanks in part to this forum and Seumas. There's one thing I don't understand, however, about the variance and how to store it.
First of all, you should pre-compile the variance at run time, right? if so, do you split the tree first to the max resolution? I'm asking this because Seumas's pseudocode that calculates variance checks for variance in children, which would assume the triangle is split.

Second of all, how many levels do you store, an what happens to the triangles that do not have variance set because we've reached the maximum level?
if you need (1<<level)-1 bytes for the tree, you can't get more than 22 or 23 levels, because you start needing 4 or 8 MB of RAM for the tree and it grows exponentially. am I right?
So is 22 levels a lot, a little, how much?
and what do you do if you should still split but you've reached the end of the tree?

Also, if a square terrain needs 2 trees to store the terrain, do you need 2 variance trees, one for each triangle tree?
when you are starting splitting from the first tree and you reach the second tree, through the bottom neighbors in the first tree, how do you know you're in the second one, so you get the variance from the other tree?

Thank you...


Bryan T
posted February 15, 2000 11:08 PM            

Yes, the variance is pre-computed (not precompiled) at run time, before drawing the first frame.

Yes, split the tree to the max (or not quite that far, see below).

In my code, I split the tree 9 levels deep. This is to reduce the amount of RAM needed, but still yield a good tesselation. Once I get to that level of depth, if the variance is enough to split the node, I split ALL the nodes under it without checking variance again.

For a 64x64 patch, the max split depth is 14 (if I recall correctly).

Yes, two variance trees are needed.

You should not need the variance from the 'other' tree during tessellation. If you need to split a node in your tree, then call the split for it. Your split operation may cause a node in the other tree to split, but the variance is not needed for this operation.



New Member
posted February 16, 2000 05:46 PM            
hmm, there are still some things I don't get. if you say I won't need to get into the other variance tree, why compute it?

and another thing I don't understand. Why a full power of 2? I would think it's 65X65, because I get a vertex smack in the middle of the hypothenuse of the triangle. if it's 64X64 what do I do, interpolate values?

How do I "scale" the variance by the distance? Multiply or divide? People here said multiply, but it sems it should be the opposite... wouldn't multiplying by the distance make it bigger?

let's see how the algorithm would work. Let's assume I have a terrain that's split in 8X8 patches. Let's say my terrain is 1025X1025, a patch is a diamond (contains 2 roots and 2 variance trees)
now I have a 8 by 8 array of patches?
now let's say I'm in the middle of the terrain. I would just go through my array of patches and... do what?
take one root at random, or the closer one?
and after picking that root, split it until the desired level of detail is reched?
what about the other root? Do I ignore it and be happy with the splits that occur because of the other one?


Bryan T
posted February 17, 2000 04:24 PM            
You won't need the other tree when SPLITTING, that's different from when you're deciding to split. There are two passes each frame, one to split and one to draw.

The split pass decides to split based on the distance to the middle of the hypotenuse and the variance stored in the tree. After deciding to split a node, it may move through the mesh splitting triangles in far-off trees to keep everything in sync. At this point it is not deciding if it needs to split those nodes - it MUST split them to keep the mesh from cracking. Thus, no need to check variance.

Always use powers of two with computers, especially arrays. This is for optimization in accessing. You can use bit shift operations instead of multiplies (lots faster).

I multiplied the variance by the inverse of the distance (same as dividing by distance). You are right, if you multiply by the distance variance gets bigger - which is why I used division.

I go through each patch in the grid, split them until their level of detail is correct for their distance, then go to the next one. Since ALL the roots must be split to the correct detail level before drawing the scene, just go through them in array order it's simpler.