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!

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

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...