I'm considering situations where the object may be small, but it is in the dead center of the world or contained in more than one top-level node. If I were to give these objects the largest it will completely fit in, it would have to be the root node. Should I be listing one node per object, or should I list multiple child nodes per object for a tighter fit? This picture illustrates a case I'm trying to figure out.

The blue outline represents the camera's view. I might be thinking that for a one-node-per-object approach, the root node would have too many objects to render. In this example the camera is only in one node, but the worst case scenario is that it draws everything from the root node, because for some objects the root node is the smallest one it can completely fit in, removing all the efficiency of the rendering.

That isn’t how the tree is meant to be traversed for rendering. The camera’s frustum isn’t inside any of the nodes.
It starts at the top node and checks for overlap into child nodes before going into them, recursively (an explicit stack helps here).

bool CFrustum::GatherObjects( const CFrustum &, std::vector<CNodeObjects *> & );

The frustum isn’t registered inside the quad-tree, it is just passed in when objects inside it are to be gathered.

You are thinking about collision detection. That is when both objects live inside the tree there are certain optimizations you can do based on the depth of each object (allowing you to cap how high up the tree you have to go).

Frustum culling is not done this way.

Firstly the frustum always starts at the root node and goes recursively into children it overlaps.
Secondly, on each level, the children of those nodes are tested individually against the frustum using frustum <-> AABB testing.

So you aren’t going to have objects being added multiple times or lose optimization by having to traverse too close to the root node just because of one small object sitting in the middle, or have the same thing cause you to render tons more objects than you otherwise would.


L. Spiro

L. Spiro, since the frustum isn't registered by the quad tree, and the tree nodes are used by the frustum to check for overlap before getting the objects, does this mean that objects can have a one-to-many relationship with the nodes?

One-to-many which way? One node to many objects? Yes. One object to many nodes? No.

After the frustum is found to overlap a node of the tree, all the objects on that node are checked against the frustum. Standard quad-tree rules apply. Each node can have many objects and each object must be contained entirely inside only one node, which should be the smallest node that can contain the object entirely.

L. Spiro

RobMaddison, that is the edge case (no pun intended) that I most want to resolve. Those objects that straddle across the borders of two or more level-one nodes, however small they may be, meaning that the largest single node they can fit is in the root node.

One-to-many which way? One node to many objects? Yes. One object to many nodes? No.

After the frustum is found to overlap a node of the tree, all the objects on that node are checked against the frustum. Standard quad-tree rules apply. Each node can have many objects and each object must be contained entirely inside only one node, which should be the smallest node that can contain the object entirely.

L. Spiro

This is what I have assumed all along. So how does one deal with worst case scenario in which the majority of the objects can only fit properly in the root node of the tree? I would think that this would cause all objects at the root to be drawn, regardless of their visibility.

Wait, is this where frustum culling kicks in? I think I see how this works now. The worst case isn't drawing a large amount of objects from the root, it's culling all those objects, and then drawing just the ones inside the frustum.