Jump to content
  • Advertisement
Sign in to follow this  
maya18222

Quad Trees

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

Im looking into implementing a quad tree for my rendering. Where the camera frustum will be tested against the first node, and if an interesection occurs, it draws the objects linked to that node, and the does the same recurring process for that nodes 4 children. I have a few questions though. From my understanding, the general idea is to limit the amount of objects a single node can have. When the limit for a node is reached, you then divide the nodes space by 4 and instead add the new item to one of the 4 children depending on its location.
const UINT MAX_OBJECTS_PER_NODE = 8;
class QuadTreeNode 
{
    QuadTreeNode *m_Children[4];
    GameObjects  *m_Objects[MAX_OBJECTS_PER_NODE];
};

But what happens when the first nodes object list has become full, ie it has 8 objects, and the newly item to be added is too big to go into one of its children?

Share this post


Link to post
Share on other sites
Advertisement
Don't have a real max-size, but a preferred one. Use a dynamic vector to allow for any number of objects.
Also, don't store small objects in the large node at all. If you reach more than the max number of objects, and subdivide the node into 4 children, remove all the objects and re-add them, storing them in the children instead. This way they can be culled away.
Then when you draw, you can often do a check 'if the whole node is visible', and if that is true, draw all of its children without any more visibility checks. The same way, if the whole node is outside the view, don't check the children at all. Only if it's partly visible do you need to check the children, which can let you get away with drawing only a few of them. Storing objects higher up in the tree doesn't make sense, since it doesn't allow as aggressive culling. For large objects that doesn't fit it would make sense though, as you say.

Share this post


Link to post
Share on other sites
I don't think there's any one satisfactory answer to this, but this is one method you could use:

EDIT: Actually, what my rambling was trying to say is exactly what Erik managed so succinctly, so I'll leave you in his capable (and more literate) hands

[Edited by - webwraith on November 7, 2009 2:25:42 PM]

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!