Sign in to follow this  

Understanding Quad/Octrees help

This topic is 3588 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

Okay i've finally finished the collision detection against triangles and edges in my game. In a low poly enviornment it works fine, however when i try in a enviornment with alot of triangles it slows down drastically. now i've heard of quad trees and octtrees and how they can help me out. ive read a tiny bit about them and how they divide the enviorment into fours and those fours into fours and so on But besides that, im pretty much stumped on how to use them efficiently. Can someone enlighten me plese?

Share this post


Link to post
Share on other sites
they are really just a simple data structure:

class quadtree_node {
quadtree_node* topleft;
quadtree_node* topright;
quadtree_node* bottomleft;
quadtree_node* bottomright;
list_of_some_kind* my_contents;
}

All you really need on top of that is a function to sort items into it.

QuadTree->AddItem( Thingoid* x );

There are a few variants on the basic idea. There is a true quadtree where you only divide nodes if they contain more than X number of items (some efficiency threshold). That requires you to dynamically add and prune nodes in real time. There is a grid variant where you create the recursive structure ahead of time and just sort things into it. That takes more memory, but no further structure changes.

Then you need to decide where an item goes. If an item is half-way between two nodes, should you add it to one node or the other or both or neither? Should you add it to the smallest node that wholly contains the object or link to the object from all nodes that touch it? That's a design decision left up to you. There are pros and cons for each.

But you asked about efficiency. You did not explain what you are trying to optimize. Speed? Size? Space? For balancing, determining the threshold level of objects per node before you decide to split the node is very important. If you use a grid, the number of levels deep is the most important thing.

Oh look, i have pictures from a previous post, still! lucky you:

Normal Quadtree:



Grid:



Share this post


Link to post
Share on other sites
okay its all starting t become a little more clear, now i would like to know about any methods for sorting the triangles into certain nodes

i thought of one way, but i didnt think it out much and it turns out it was so expensive my game wouldnt even start.

Share this post


Link to post
Share on other sites
you take the bounding box of the object and see if it is entirely contained by the topnode (it always is). If so, examine each of the four subdivisions. If a subdiv wholly contains the objects, check *its* four subdivs and so on (it's a recursive function if that helps). As soon as you find a node that contains the object and that none of its children can wholly contain, stop. Object goes in that node.

Share this post


Link to post
Share on other sites
The basic principle here is that you want to implement a spatial partition to minimise the number of comparisons you need to do between objects. Quad trees and Oct trees are uniform binary spatial partitions in 2 and 3 dimensions respectively (since they produce 4 and 8 child nodes per split respectively).

Once you have created your data structure that partitions objects based on where they are in the environment, you can use it by performing a simple range search (take a look on google for implementations of range search in quad and oct-trees... it's pretty trivial).

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Okay but whem setting it up,how do i sort them. How do i decide what node they go in.

Do i just go:

if ( X > NodeMidX and Z < NodeMidZ)
{
put them in the first node (quadrant 1)
}


and then again for those nodes and those nodes until im satisfyed, or what?

Share this post


Link to post
Share on other sites
something to the effect of:


// return true if object added to list, false otherwise
bool QuadTreeNode::AddObject( Object* x ) {
if (object fits inside my bounderies) {
add object to my list of contained objects
return true;
}
else if ( _topleft->AddObject(x) ) { return true; }
else if ( _topright->AddObject(x) ) { return true; }
else if ( _botleft->AddObject(x) ) { return true; }
else if ( _botright->AddObject(x) ) { return true; }
return false;
}

Share this post


Link to post
Share on other sites
Please clarify this:


If I use this code, instead of your original, it only places the object in the node that wholly contains it.

If I use your other code, then the object is contained in every node that contains it.

The retrieval is still linear time, just requires a recursive call (so both O(n), but this with a different constant)

This code, however, doesn't redundantly store the object in every parent that holds it.

Unless i've missed something...





// return true if object added to list, false otherwise

bool QuadTreeNode::AddObject( Object* x ) {

if ( _topleft->AddObject(x) ) { return true; }

else if ( _topright->AddObject(x) ) { return true; }

else if ( _botleft->AddObject(x) ) { return true; }

else if ( _botright->AddObject(x) ) { return true; }

else if (object fits inside my bounderies) {

add object to my list of contained objects

return true;

}

else {
return false;
}

}

Share this post


Link to post
Share on other sites
deciding whether or not to store the object in the largest containing node or in all touching nodes is a design choice. If you decide to go with the largest node, what you end up with is a lot of objects that tend to collect in the topmost nodes. If you place an object directly in the middle of the gamespace, it ends up in the topnode because it's not fully contained by an subnodes. If you're okay with that, go ahead. If not, you have to go with the other solution, but that requires more overhead maintenance when objects move from node to node.

also note that the pseudo-code i posted assumes you are working with a static data structure and that you are not adding or removing nodes from the structure.

Share this post


Link to post
Share on other sites

This topic is 3588 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.

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