|
Author Topic:   BinTri Tree & Terrain LOD
JaZzBrE
New Member
posted August 29, 1999 06:28 PM            
Hello,
thanks for that reply Seamus. I thought I'd open a new topic for this one, becouse it might get long.
Anyway I have a few more questions.

The BINTRI struct should look something like:

struct
{
int vertex_index[3];// or it would be better to use pointers?
.....
BINTRI *LeftChild,*RightChild;
BINTRI
*LeftNeighbor,*RightNeighbor,*BottomNeighbor;
}BINTRI;

right?
http://www2.arnes.si/~ngklubkis1/download/ex.jpg

here's a picture of the triangles and they are marked with A,B,C,..., becouse I want to be sure I understood your tutorial right.

A->RightChild=NULL;
A->LeftChild=NULL;
A->BottomNeighbor=B; // or is it B?
A->LeftNeighbor=NULL;
A->RightNeighbor=NULL;

B->RightChild=C;
B->LeftChild=E;
B->BottomNeighbor=A; ??
B->LeftNeighbor=E;
B->RightNeighbor=C;

C->RightChild=NULL;
C->LeftChild=NULL;
C->BottomNeighbor=D;
C->LeftNeighbor=B;
C->RightNeighbor=NULL;

Please correct this becouse it might be wrong.

- How do you build the tree do you just allocate all tris in a single array, and then just connect them, or do you do it recursively or something?

You said that the terrain is in higher detail, so how do you merge the triangles and form one big triangle, and doing so that it doesn't create cracks between the triangles? (some psuedo code would be nice )

That's all

Thanks

Regards,
Ales Mlakar

IP:

LDA Seumas
unregistered
posted August 29, 1999 09:47 PM           
That looks like a good structure. I don't store vertex pointers or indices in mine, as I output the polygons dynamically as I recursively descend the trees. It's a perfectly valid alternative to make bigger lists of shared vertices though, and I'll probably try that again myself using Compiled Vertex Arrays in OpenGL.

Triangles A and C are good, but Triangle B is wrong. Its child pointers should be null, as it has no children (children are new triangles _inside_ the parent, that you get when splitting the parent). Also the left/right are mixed up, its _right_ neighbor should be E. You rotate your perspective so that the hypotenuse is "down".

When building the terrain trees, I start with a number of parent bintris in much the same structure as your jpeg shows (exactly, actually), with each "diamond" of two tris covering a patch of texture and variance data. Then I just call a recursive splitting function on each parent tri in turn, which tests to see if it needs to be split (based on variance and distance from camera), and if it does, it splits it (if it isn't already split!), and then calls the same function on its two children. If it doesn't need splitting, it just returns.

There are no cracks, since the splitting function (see pseudo code in my article) makes sure to split neighbors if need be, and since all the patches are connected by neighbor pointers before any splitting occurs, "forced splits" propagate properly between the trees, and cracks simply can't form. It's almost magick.

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

IP:

LDA Seumas
unregistered
posted August 29, 1999 09:49 PM           
Just to clarify my first point, I make two recursive passes over the trees, one to split them, and then another pass after they have all been split to output triangles and draw them. You can't draw while splitting, as a bintri somewhere else might force-split an earlier bintri further once it has already been drawn.

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

IP:

JaZzBrE
New Member
posted August 29, 1999 10:16 PM            
Ohh, I understand now, the children are only those new tris created when splitting...
In my terrain engine which uses a simple quad-tree (basically just a bigger grid), I first check if a node has to be rendered LOD (the limits of the node) and then inform all neighbors so that the neighbor triangles fix their edges with the node's big poly. This kind of work, though I get a pretty small crack, which I'm not sure why are there.
Though I think I'll try using this bintri tree which is basically the same just a bit more flexabil.

Check it out (btw is a few days old project): http://www2.arnes.si/~ngklubkis1/download/te.zip

Thats what I don't understand, I try to render as few tris as posibile, but you split them, I thought you should merge them?
So when you split them, do you change the new vertex height at all?
Becouse what's the point splitting it if not?

Thanks
-Ales Mlakar

IP:

JaZzBrE
New Member
posted August 29, 1999 10:29 PM            
Ops forgot to tell you something...

You need dx6.1 becouse it's d3d (too bad I wanted to do opengl, but i just hate my voodoo2 rendering everything in fullscreen).

The command line for my terrain test:
/fullscreen - starts fullscreen
/device2 - forces d3d to use the 2nd device if available
/software - uses d3d software mode (a bit slow and colors messed up right now, tho I just need it to see if stuff work the same)

You can exit the test with Escape or Alt-F4 keys...

I've put a 64x64 terrain TGA image (basically the ground texture lol) with the test, cuz the other 512x512 just takes too much disk space for the internet heh.

Regards,
-Ales Mlakar

IP:

JaZzBrE
New Member
posted August 31, 1999 06:23 PM            
Ok, no need to reply the previous post, I finaly dig what're you doing with the bintritree.

I made a simple engine to test it and it looks like it could work quite well... the splitting is really fast becouse you don't acctually do nothing just construct two new tris per split.

You said that you use 1024x1024 terrain map, so you probobly make a 256x256 or 512x512 bintri tree and then just split the tris and add the vertexes from the highest terrain map, am I right? That was what I didn't understand in your engine, you didn't mention that anywhere.

Btw I construct the BinTri-Tree once for the whole terrain, then I can split tris and in every frame just clean the children, with no new's and delete's. It seems to work

Thanks
-Ales Mlakar

IP:

LDA Seumas
unregistered
posted August 31, 1999 10:50 PM           
Oops, sorry I forgot to reply earlier.

Yeah, you start with huge, coarse bin tris, and as you split to higher detail, pull heights out of the height map.

I split my 1024x1024 maps into "patches" that are 64x64 cells/meters square. Each patch has one 64x64 texture object that is downloaded to the 3D card, and 2 root binary triangle trees in a "diamond" form. All the initial trees in the initial patches are connected by neighbor pointers, and then I split each tree in turn. After everything is split, I go down each tree again and draw the triangles.

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

IP: