Sign in to follow this  

Quadtrees rendering question

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

Hello all, I've been wondering something about quadtrees, specifically about using them for geometry that is not part of a standard, grid-format terrain. I can definitely see how it works cleanly there, since the leaf nodes of the quad tree can be perfectly fitted with a single cell of the terrain. But that seems to be pretty limited; what about all the other static, graphical objects that are littered about the world? Is it possible to place them in the quadtree as well? The issue with them is that there could be multiple of them in a single quad tree node, meaing that you would need some kind of expand-able storage for them. This seems like it would severely limit their efficiency if you had to keep randomly allocated buckets per node. Does anybody have any good examples or links for this kind of usage? Thanks much for any help!

Share this post


Link to post
Share on other sites
I don't really have much experience working with quadtrees specifically, but my understanding of the idea is that adding a new object to the tree basically forces you to split the leaf it lands in. It sounds like the place you're running in to trouble is with tightly packed objects, like a character and his equipment, for example, yeah?

In that case, one trick to help alleviate pressure on the quadtree is keeping a spatial hierarchy tree for each complicated object group; the leaf of the quadtree would be an actor, which itself contains a tree of actors that are spatially related to it. Doing things this way buys you a bit of simplicity at the end of the quadtree, while keeping the quadtree's fast nearest-neighbor search at the actor level. It does mean it takes more effort to calculate which node in an actor's child tree is actually the nearest neighbor, if you need to resolve a query at that depth.

[EDIT-- I just realized I was missing the point of the question, here's some more thoughts on it]

Whether or not it's practical to use the same quadtree as your terrain for actor/object storage is a tricky question. It's really dependent on what those objects are, and what aspect of the quadtree you're trying to exploit by keeping them in it. In general, keeping objects in the terrain's tree structure is a good way to confuse the issue, IMO, since the tree ends up containing both terrain quadrants and actor nodes (because the terrain continues to exist underneath the actor). How you go about resolving the problem of multiple non-terrain objects on what would otherwise be a single quadrant of terrain depends on what aspect of the quadtree you're trying to exploit by keeping them on it to begin with (most importantly, are they nonmoving objects? If they are, increasing your tree depth to buy faster access isn't such a bad way to go).

If you're after nearest-neighbor efficiency, you have a tradeoff to make. Like you said, it's going to put a bit of pressure on the quadtree structure keeping tightly packed objects if you subdivide the tree such that each object exists on a single patch (quadrant) of terrain. Brainstorming, here's a couple ideas:

Keeping the actors on a single quadrant in a list, forcing a much slower search algorithm if your NN query happens to land on a quadrant with multiple actors, but not increasing the depth of our quadtree at all.

Keeping an array instead of a list, allowing the quadrant to subdivide on an add if the array is nearly full. This increases the cost of adding objects to already pressured quadrants, but bounds the possible slowdown introduced by keeping multiple objects per bucket. The size of those arrays is a way to control the weighting between quadtree depth and object search time, and a possible point for optimization.

One way to mitigate the cost of frequently subdividing and remerging quadtree nodes is pooling node objects to dodge instantiation costs.

Hope some of that was helpful, and I apologize if it's a little incoherent; I'm posting in between coding (while I wait for compiles) :-P

Share this post


Link to post
Share on other sites
Thanks for the response aberghage!

I'm fine with using a separate data structure for objects but actually this brings up another question I have, and that is that I don't understand how you could do the traditional "subdivide when you have more than one data member per node" method of a point-quadtree for objects.

The reason is, the objects aren't points; each object takes up a certain amount of space and is quite likely to sit on two or more nodes of your tree. This wouldn't prevent you from having only one object per node, but the fact that these objects can overlap would make this impossible, right? Because no matter how many times you subdivide, you will never get a single object in the nodes where the object areas overlap.

So in that respect, it seems to me that having unconstrained storage per node is required for a quad tree of objects. What I really want to avoid is using vectors, or other containers that allocate memory all over. But since these objects are all static, I suppose I could just linearly allocate each node's object pointers in a big array since they won't change at runtime...

Share this post


Link to post
Share on other sites
Have each node have a list (or whatever method is best) that stores all the things it contains, each sub divide, divide the node into 4, check if any of those objects fit inside the child nodes, if they do then more them into the child. If they do not fit then just leave them in the parent node.

I use this approach but I also try to slice up my onbjects to fit a bit.

When you create your tree you could give each node a unique id (just use its address) and for each object say which node it is in. No need for expandable storage in each node then.

if((object.GetContainingNode()).InView())
{
object.Render();
}

Share this post


Link to post
Share on other sites

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