|
Author Topic:   Bintrees again
Dreamer
Member
posted March 18, 2002 04:14 PM         
I'm trying to implement ROAM-like terrain in Java3D...

The main problem I keep running into is that my BinTree uses extremely huge amounts of RAM (~100MB for 1024x1024 terrain, BinTree implemented purely object-based: One object for each Node). My tries to map the tree into a plain array all resulted in hilariously slow access to specific nodes.

Does anyone have any clues for me? Is there a really fast method for accessing the tree stored in an array?

Concerning the prejudice that Java3D is too slow for terrain - Java1.4 has a redesigned native interface that can speed up OpenGL calls by up to 40 times...

IP:

Cthulhu
Member
posted March 23, 2002 06:53 AM            
Array is the way to store bintrees, because it saves a huge amounts of memory.

Have you read this: /forums/archive/ubb/Forum3/HTML/000016.html

I also suggest reading forum history. There was a copy of all the old messages somewhere, but I can't remember where. I can email you a zip package if you want to.

It's been long since I toyed with bintrees, but I remember my split-only algorithm recursively went through the tree just once per frame. Not too much array accessing there, unless it's very slow using Java.

Try splitting your terrain into smaller blocks (I think I used 64x64 or 128x128) that are somehow linked to each other to make correct splits. That should save some memory.

IP:

Dreamer
Member
posted March 23, 2002 09:07 AM         
I have read that and I am using that. The main speed problem is finding the base (hypotenuse) neighbour (==split partner) for each node in real-time - of course that's not very problematic with a "real" tree structure stored in seperate objects...

IP:

Cthulhu
Member
posted March 28, 2002 01:25 PM            
Lookup table worked well for me.

I divided my terrain grid into smaller blocks, two bintrees each. Each of these trees has 65536 triangles (the first one is not used, it's just there to make indexing start from 1 for faster calculations). Of course you don't need base neighbour information for lowest-level triangles, so that makes my lookup table 32768 units.

I used four bytes per triangle (the whole table taking 128kb). Three bytes for base neighbour index in tree array and the one byte to determine if the base neighbour is in the same tree, or one of the three possible neighbour trees (base, left, right). This way the same lookup table works for every tree in the terrain.

For each tree, I had a four-pointer array, where one pointer was to that tree itself and the others to neighbour trees, NULL pointer for non-existing neighbours (if the tree is in the border of the terrain). That makes accessing neighbour triangles easy:

int bntree = table[tri.index] & 0xFF;
int bntri = table[tri.index] >> 8;

if(tree->neighbours[bntree] != NULL)
{
split(tree->neighbours[bntree]->triangles[bntri])
}


I had a precalculated lookup table stored in file for fast loading times.


Hope this helped.

IP:

Dreamer
Member
posted March 28, 2002 02:01 PM         
Reused Lookup table sounds like a good idea... I was thinking along the lines of
code:

if (mustSplit){
if (isLChild){
SplitPartner=parent.LNeighbour.RChild;
}else{
SplitPartner=parent.RNeighbour.LChild;
}
}
SplitPartner.split();


for calculation on the fly, but a lookup table might be faster - even in Java. If all else fails, I might even have to implement this in C, using the java native interface.

IP:

Cthulhu
Member
posted March 29, 2002 03:46 AM            
Of course you can make the table smaller by reducing block size - 64x64 blocks are still large enough for base grid and it makes the table only 4096 units and 16kb in size.

IP: