Jump to content
  • Advertisement
Sign in to follow this  
CC Ricers

Quadtree dilemma

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

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.

 

2HezD.png

 

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.

Edited by CC Ricers

Share this post


Link to post
Share on other sites
Advertisement

In most cases, this is okay, just draw all 4.  These days it's probably quicker to just draw all the leaves you can see at your chosen quadtree depth.  If you've go so many objects that a quadtree doesn't work, then it's not really the quadtree that isn't working, it just becomes less applicable to your application.

 

I think the small object that spans all 4 leaves should probably exist in all 4 leaves but when you render it, just set a 'alreadyRendered' flag to make sure you don't render it 4 times.

Share this post


Link to post
Share on other sites

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

Edited by L. Spiro

Share this post


Link to post
Share on other sites

You should also look into loose quadtrees.  The benefit is that you can find exactly what level of the tree and what node in that level an object belongs by looking at its bounding center and bounding radius.

Share this post


Link to post
Share on other sites
For static data you can use an R-tree, which allows nodes to be anywhere within the parent and in any number.

As it removes the restrictions of a quad tree, it can be more optimal for a given set of data. Because the bounding boxes are fitted around the contents, overlap is not a problem.

However, it is difficult to maintain in an optimal form if there are many insertions and deletions. It's best to build the whole tree from a known set of data.

Share this post


Link to post
Share on other sites

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?

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
I've never actually implemented a quadtree, but as I understand it, the trick is that it's recursive... most objects will be several levels down, but objects that are sitting on boundaries have to be higher up. So yeah, in your picture, those objects would indeed go in the root node because the very first division has boundary lines there. But keep in mind that those objects are very large relative to the world size. Most could only fit in a first or second division cell at most anyway.

For collision detection, I usually use a fixed-size grid, where objects can belong to multiple cells, and use timestamps to avoid testing pairs twice. Could use that in quadtrees as well, I think. Subdivide until you're a minimum of maybe 3 levels deep, and if you're sitting on any boundaries, just link into to all the cells. Then at the start of the frame, increment a global timestamp value (just an int), and when you render each object, set its timestamp equal to the global, or reject it if it was already equal (i.e. had been drawn this frame from a different cell).

Of course, it's questionable which is better performance-wise... depends on the world size and number of objects, I guess. In most cases, it would probably be better to just let a few things go in the root and first division nodes, to reduce the amount of list management. You can still reject them early by testing their bounding sphere/box against the frustum. Edited by DekuTree64

Share this post


Link to post
Share on other sites
In some form they need to because if you have the case above where an object sits across the corner between four (or across the edge of two) boxes and one of the boxes is out of the frustum, you'll still need to draw the object.

Share this post


Link to post
Share on other sites

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.

Edited by CC Ricers

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!