Hi all! I'm getting a headache trying to balance my dynamic quadtree. I want every neighbouring leaf to be at most 1 level beyond their neighbours. So only neighbours of level + 1, level - 1 and level are allowed. Otherwise i need to split the node. But splitting a node needs to recalculate the neighbours of the nodes neighbours. It's very hard to figure out this recursive stuff. So my question is, could anybody at least explain the steps neccessary to do this or have a link to a good paper or even source (C/C++, Java preferably) that explains how to find the neighbours and balance the tree? I fiddled out something but it's not robust and already took me a few ours to get it almost working. Thanks in advance, JMS

Quote:Original post by grhodes_at_work
Christer Ericson's excellent book talks about this (quadtree/octrees, including algorithm for neighbor lookup):

Real-Time Collision Detection

You might find something on his website as well:

realtimecollisiondetection.net

There was a talk at SIGGRAPH a couple of years ago about balancing K-d trees. Not quite the same, but very, very interesting and informative nonetheless. You can find some of the course notes here:

SIGGRAPH 2005 - Introduction to Real-Time Ray Tracing

Look for the optimization slides (Gordoon Stoll). Very nice presentation on optimization of K-d trees for high performance (millions of ray tests per second). This one, and the basic algorithms presentation from the same talk do discuss some of the traversal issues, and some stuff on data structure packing/optimization.

Great, i'll have a look at those...