This topic is 4394 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites

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.

##### Share on other sites
Quote:
 Original post by grhodes_at_workChrister Ericson's excellent book talks about this (quadtree/octrees, including algorithm for neighbor lookup):Real-Time Collision DetectionYou might find something on his website as well:realtimecollisiondetection.netThere 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 TracingLook 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...

1. 1
Rutin
29
2. 2
3. 3
4. 4
5. 5

• 13
• 13
• 11
• 10
• 13
• ### Forum Statistics

• Total Topics
632960
• Total Posts
3009475
• ### Who's Online (See full list)

There are no registered users currently online

×