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?

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.

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.

code:

---

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

---