Hi!

I was thinking I would store everything in my world in a quad tree and I thought I had it all solved and settled. So I thought I was going to store the terrain patches in (not the lowest) level of the quad tree and the objects, both static and dynamic, in the lowest levels/leaves. Also, I thought the rule that every item would only be a child of 1 quad tree node would make it easier to do things in the code.

Then it hit me that how do I decide in what node will the object be in? Well, the only reasonable solution would be in the node which the position of this object is in. But then I thought of bigger objects, and also smaller. If I was going to use the quad tree for visual culling some objects might be culled though the item actually intersects the view frustum and hence the object will pop up when I turn around or move.

Another idea I was having that perhaps (?) I might get a performance boost (a small one) if I store adjacent nodes in each lowest level-node for collision detection, for I've planned to do collision detection against objects in the object's node and also those around it to avoid errors if close to the edge. But then if some objects might be huge (castles and stuff) they might overlap with one of the adjacent nodes but not being checked for collision against. This might be solved with bigger lowest level-nodes or having to chop up big objects to fit in one node.

I wonder what are the general solutions to this? I thought I had it all planned but now I'm hesitating on how to do this.

I thought it was possible to loop through parent nodes in the quad tree for collision detection so the big items could be stored there, but I want to avoid this.

Often large objects will either have duplicate entries in any leaf nodes which they overlap, or they are placed higher up the quadtree in a larger cell (meaning you have to consider any objects you encounter as you descend into the tree)

Yeah I was considering multiple references to large objects from multiple nodes. But my idea was to loop through objects in the nodes and send to the render queue for rendering, but if I have multiple entries either I will have to have some flag to set when sent to rendering, which seems like a bad way to go. So then I'm thinking that placing it at a higher level in the tree would be a better idea, but I was hoping to avoid the (in almost all cases) unnecessary walk through the tree (upwards).


Well I suppose storing objects in appropriate tree levels would solve the problem pretty well though. But I'm still wondering if someone has a solution to the fact that objects' spans will sometimes span outside of the nodes' bounds. Could it be a good way to go about doing this if I'm using some bigger view frustum for culling? It seems like a crappy hack though. Any ideas?