|
Author Topic:   Bintrees again
nurtsi
New Member
posted October 23, 1999 04:17 AM            
I'm strugling to ímplement a Bintree rendering to my landscape engine (uses quadtrees now) mainly because I need some type of LOD system.
I understand that some of you have implemented the ROAM method using just splits and no merges. Now doesn't this mean you'll have to reset the whole bintree every frame and isn't that slow? Or have I missed something?
I'd also like to know how do you actually render the bintree. Do you store the all the coordinates to the tree itself (not likely) or just pointers to the original heightmap or something?

------------------
---
Nurtsi

IP:

bdiscoe
Member
posted November 12, 1999 07:03 AM            
Yes, using a split-only method does mean that you'll have to reset your whole state every time. Yes, it can be slow.
In my implementation of Lindstrom-Koller (dual quadtree), i have 2 flag bits per vertex, which for a 2k*2k terrain means 1 MB of memory has to be cleared every time. That's not too bad, but gets much worse if you want to use larger terrain or have more data per vertex that needs to be reset.
Seumas has said that his algorithm doesn't preserve any state from the last frame, so he must have some state to clear too...?

-Ben

IP:

LDA Seumas
unregistered
posted November 13, 1999 06:47 AM           
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

IP:

brianl
Member
posted November 13, 1999 10:02 PM            
=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.

I assume when you say "passed and calculated on the stack", you are talking about during your splitting. How do you pass vertex coordinates into a bottom neighbor that you have to force split? I don't see any way for you to calculate this information, it seems like the triangle could be any size -- that is, any size "larger" than you. All you know, I think, is that it shares one vertex with you. I guess maybe there is a way to do some math knowing the "implicit indices" of both triangles in question... is that it?

Actually, now that I think about it, I don't see how you're doing this at all. In the main loop of the splitting code, when you pull a tri off the priority queue, how in the world do you know what its coordinates are, to get the ball rolling?? It seems like there is no "context" at all, whereas in the case of a forced split, you have one set of coordinates, the knowledge that one vertex is shared, and you know what "level" the two triangles are on, so i guess there might be some way to poop out another set of coordinates...

I know it's not necessary to precompute the vertex coords for every single tri in every single patch at every single level of subdivision. Assuming all your patches are equally sized, then you only really need to precalculate vertex coords for every tri in every level of subdivision for a root tri that is "pointing up" and one that is "pointing down". Then, these "local" coordinates are merely added to a position of the patch's "origin" to get their final absolute location.

But, I don't see you're getting away with not ever storing any vertex information anywhere, due to the "random access" nature of the priority queue and the forced splits.

You must be a magician... :^)

IP:

LDA Seumas
unregistered
posted November 15, 1999 02:46 AM           
Basically it's because 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

IP:

brianl
Member
posted November 15, 1999 03:27 PM            
I see... sorry, I didn't know that you weren't using a priority queue.

So I understand that you precompute variance values for every triangle, and while recursing through bintritrees, you can easily pass along an implicit index into an array of these triangles to get the variance for a particular bintritree. And I understand that you are scaling these precomputed variances by a distance. So I guess that's where I'm confused. Where is the distance coming from, if you're not passing coords down during your split step? Just the distance from the root triangle that the triangle belongs to?

IP:

assen
Member
posted November 17, 1999 06:40 AM            
If each triangle knows its index in the implicit binary tree, from that index (used to find the variance) you can calculate the coords of the vertices (or you can read them from a small look-up table).

IP:

brianl
Member
posted November 17, 1999 06:07 PM            
i understand that, but it sounds like seumas does NOT store vertices in the implicit array. if he did, then why would he need to pass down vertices during the rendering step? i'm trying to figure if and how it's possible to do the split step without accessing precomputed vertices...

IP:

LDA Seumas
unregistered
posted November 24, 1999 12:49 AM           
Sorry I wasn't clear. Currently I am passing down coordinates during my split step, though without height values, so only 2 numbers (and integers) per vertex of the triangle. I just had the brainstorm that I may be able to get away with only passing distance from camera and a bit of other magic to be able to calculate the distance from camera of the children, but I haven't tried implementing this yet, or even really considered whether it's feasible.

My recursive functions look something like this:

int BinTri::F(int x1, int y1, int x2, int y2, int x3, int y3){

int xc = (x1 + x2) >>1;
int yc = (y1 + y2) >>1;

LeftChild->F(x2, y2, x3, y3, xc, yc);
RightChild->F(x3, y3, x1, y1, xc, yc);

}

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

IP:

bdiscoe
Member
posted January 02, 2000 07:45 PM            
> My recursive functions look something like this:
> int BinTri::F(int x1, int y1, int x2, int y2, int x3, int y3)

Seumas, does this mean that you're using TWO numbers (x,y) to reference each vertex, instead of single vertex index? Wouldn't it be simpler/faster to use a single index?

Thanks,
Ben

IP:

LDA Seumas
unregistered
posted January 03, 2000 05:12 AM           
Ben,

In my case, a single index into what? I don't store vertex information anywhere, so would have nothing to index into.

However, I have recently performed the optimization of reducing the parameter to a single mangled distance value per vertex for the lowest level split-test function (for triangles that are guaranteed by who their parents are to be inside the view frustum), but this only works because the function doesn't require the vertex's world position, only its distance from the camera. The Z distance from the camera of the middle of hypotenuse vertex (for when recursively calling itself on its children) is simply the average of the Z distances of the two hypotenuse vertices.

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

IP: