bsp tree

It depends on how you allocate the memory..here''s what I do:

Create the bsp using dynamically allocated data structures(linked lists)..each node structure has pointers to other structures, but also an extra int for each pointer to use as an offset..

Do an in-order traversal of the tree, giving each node an index value..

node->index = i++;
//recurse through all nodes

Do an in-order traversal of the tree, assigning index variables that correspond to whichever node the front/back pointers are pointing at..

node->frontid = node->front->index;
node->backid = node->back->index;

Do an in-order traversal of the tree, saving each node as you go along..the index value for each node in the file should be sequential..

When you load the bsp, you can allocate an array of nodes, load the data right from file, then go through and check your index variables to assign the pointers..

nodes.front = &node[nodes[i].frontid];
nodes[i].back = &node[nodes[i].backid];

Of course you need a way of assigning NULL pointers, I assign -1 to frontid or backid if the pointer is NULL..

Set the rootnode of your bsp as the first element of the array

rootnode = &nodes[0];

and WHAMMO!! you can use the bsp normally at this point and forget it''s actually in an array, the pointers will take care of themselves


"Like all good things, it starts with a monkey.."