Jump to content

  • Log In with Google      Sign In   
  • Create Account

Quadtree dilemma


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
13 replies to this topic

#1 CC Ricers   Members   -  Reputation: 738

Like
0Likes
Like

Posted 14 January 2013 - 01:35 PM

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, 14 January 2013 - 01:37 PM.

My development blog: Electronic Meteor

Sponsor:

#2 RobMaddison   Members   -  Reputation: 775

Like
0Likes
Like

Posted 14 January 2013 - 05:09 PM

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.



#3 L. Spiro   Crossbones+   -  Reputation: 14262

Like
2Likes
Like

Posted 14 January 2013 - 05:19 PM

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, 14 January 2013 - 06:12 PM.

It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#4 amorita   Members   -  Reputation: 138

Like
0Likes
Like

Posted 14 January 2013 - 08:51 PM

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.



#5 EWClay   Members   -  Reputation: 659

Like
0Likes
Like

Posted 15 January 2013 - 06:02 AM

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.

#6 CC Ricers   Members   -  Reputation: 738

Like
0Likes
Like

Posted 15 January 2013 - 05:04 PM

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?


My development blog: Electronic Meteor

#7 L. Spiro   Crossbones+   -  Reputation: 14262

Like
1Likes
Like

Posted 15 January 2013 - 07:42 PM

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


It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#8 DekuTree64   Members   -  Reputation: 986

Like
1Likes
Like

Posted 15 January 2013 - 10:28 PM

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, 15 January 2013 - 10:32 PM.


#9 RobMaddison   Members   -  Reputation: 775

Like
0Likes
Like

Posted 16 January 2013 - 01:56 AM

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.

#10 CC Ricers   Members   -  Reputation: 738

Like
0Likes
Like

Posted 16 January 2013 - 09:29 AM

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, 16 January 2013 - 09:33 AM.

My development blog: Electronic Meteor

#11 RobMaddison   Members   -  Reputation: 775

Like
0Likes
Like

Posted 16 January 2013 - 09:41 AM

How many objects are you likely to have that can move freely between nodes?

You can either have all objects at the leaf nodes and allow them to belong to up to 4 nodes, or only allow them to belong to one and if they happen to be spanning nodes, then move them up the tree until they are enclosed by only one. If your quadtree is only 2 levels deep (i.e.the root node and its children) then that will mean the objects will go into the root, but I would imagine that if your camera can move around the whole scene and it's fairly sizeable, you'd want far more levels.

If your game area is quite big and your objects are small, then the chances of them straddling nodes is pretty minimal. It all depends on how busy your scene is and how much depth you have in your quadtree. You can set this up fairly painlessly and just do some tests to see which way works best for you...

#12 RobMaddison   Members   -  Reputation: 775

Like
0Likes
Like

Posted 16 January 2013 - 09:50 AM

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.
Yes, the ideal situation is that you are able to split your world into 'manageable' chunks and only draw what's in that 'conceptual' chunk if any part of it is in the frustum.

The quadtree concept works like this:

Check if the root node 'box' is in the camera frustum - if it isn't, then you draw nothing and rendering is complete.

If any part of it is in the frustum, you then look at it's 4 children recursively and check to see if any part of them are in the frustum, you then continue down the tree until you've either reached the smallest box (the leaf node), in which case you draw all of the objects within it, or just ignore it if it's empty.

You can quickly see that large parts of the game world can be ignored very quickly. The whole notion is "if I can't see a box on the screen, then ill never be able to see any of its 4 children (this happens recursively), and hence any of the objects that live in that box."

A quick side note that someone pointed out the other day on a similar topic, if a quad node at any particular level is contained entirely within the frustum, you know that all its children will also be in the frustum so you can stop drilling down and draw everything below that node.

#13 L. Spiro   Crossbones+   -  Reputation: 14262

Like
0Likes
Like

Posted 16 January 2013 - 01:02 PM

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.
Now you’ve got it.


L. Spiro
It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#14 CC Ricers   Members   -  Reputation: 738

Like
0Likes
Like

Posted 16 January 2013 - 02:27 PM

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.
Now you’ve got it.


L. Spiro

 

Great, I can get started with populating the tree. I think the worst case won't be as bad as I thought. On older hardware, I've culled around 10,000 objects by brute force before noticing any slowdown.


My development blog: Electronic Meteor




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS