• Advertisement
Sign in to follow this  

Balanced quadtree

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement