Sign in to follow this  
spe

quadtree + moving objects

Recommended Posts

spe    122
Hi! I want to use a quadtree to store my geometry but I don't know how to handle moving objects. I read something about loose quadtrees but I can't find to much info on it (I googled). Could someone help me with this or point me to a good tutorial? Thanks, spe

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
well, you could use BSP trees. i found the following tutorial helpful . . . dynamic objects are about 3/4 the way down the page -
http://www.gamespp.com/graphicsprogramming/BSPTreeFaq.html

Share this post


Link to post
Share on other sites
NoahAdler    290
See http://www.tulrich.com/geekstuff/partitioning.html for Thatcher Ulrich's notes on loose octrees. I believe he's the originator of the idea, or at least the authoritative source now. There's also an article on loose octrees by Thatcher in one of the Game Programming Gems, which may explain things a bit better. Of course, octrees are mostly discussed, but it should be very easy to transfer the idea to quadtrees. Hope this helps some.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Loose quad-trees are just a different method of doing quad-trees.

For moving objects you need to know this:

Moving objects should always be attached to the furthest node (from the root) as possible.

Whenever a moving object "moves" you must check if it is still _entirely_ within its current node. If it is not, then remove it from that node and put the object back into the tree.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Oh and when you "check if it is still _entirely_ within its current node", you need to check if the moving object will now fit entirely within one of the current node's children as well.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this