Sign in to follow this  
kevlur

quadtree questions

Recommended Posts

Hi all, im trying to implement a quadtree to manage the rendering of my objects, so can someone tell me if these thoughts that i have about it are right or wrong? 1. CreateQuadtree() (In the initialization of the program) create the quadtree with a default depth, and allocate the memory for all the nodes(all the nodes are empty now). 2. InitQuadtree()(Ever in the initialization of the program) load all the objects and all the terrain quads in the proper nodes.(Is it right to use the quadtree to manage either the terrain quads and the objects?) 3. Due to the fact that i have static and dynamic objects to take care of, i thought: i have already the static objects(like terrain quads, tree, buildings) in the proper nodes after the InitQuadtree() so i will not bother about their position (or should i do?), but i will track the position of the dynamic objects in the main loop (UpdateQuadtree()). (Will the processing of UpdateQuadtree() in the main loop slow down the frame rate too much?Is there another solution for the dynamic objects?) 4. Now is time to render: Should i render only the node inside of which is the frustum bounding box? or should i render either the nearest nodes? Thank you for any helps :) Kev

Share this post


Link to post
Share on other sites
In my experience I have used a quad tree for terrain and another quad tree for objects. I assume that you are using the quad tree to cull terrain and to perform visibility checks on objects... Is this correct or am I missing the point?

Share this post


Link to post
Share on other sites
First things first: If you are talking 3D - then you'll probably be using an OCtree rather than a quadtree.

Id have a quadtree class that lets you specify bounding size and depth, and lets you resize if you so wish.

As for moving objects, they should store the tree-node they occupy, and each tree node should know its parent. Then on the event that an object moves, you can speed up re-entry into the tree greatly by checking against the current bounding node, then on failure its parent, then its parent's parent, etc - much faster than starting from the tree root.

I'll go into more detail if you like

Share this post


Link to post
Share on other sites
U agree with everything you said ScootA apart from the bit about Octrees for 3d. That is an option but in depends very much on the application. Octrees are often overkill in simple terrain applications!

Mark Coleman

Share this post


Link to post
Share on other sites
to mrmrcoleman: yes im using it to cull the terrain chunks and the objects that are not in the same tree-node where the frustum bounding box is in.

_Are there know problems in using the same quadtree for either objects and terrain?


to ScootA: the idea to start checking the position of a dynamic object from its node parent is good:) i think the only thing that have to be added is the parent ID in the child node, isn't it?

_Should i render only the node where is the frustum bounding box inside, or either the nearest nodes?


Thanks for the help

Share this post


Link to post
Share on other sites
Quote:
Original post by kevlur
to ScootA: the idea to start checking the position of a dynamic object from its node parent is good:) i think the only thing that have to be added is the parent ID in the child node, isn't it?


Well all of your child-nodes should have parent-facing-pointers as an attribute. Another more complex optimisation is to have each child contain pointers to its neighbors (complex because neighbors might not share same parent). Assuming your objects aren't moving too fast, you can assume the object lies within the neighbor of the node it has just left - but this can get dangerous, so a hybrid method is generally best.

Quote:
Original post by kevlur
_Should i render only the node where is the frustum bounding box inside, or either the nearest nodes?


You should be using a range of frustrum-culling algorithms on your node-bounding-boxes, ranging from most to least trivial. Personally I am using 3 tests, each one only used if the one before passed:

>Node Bounding-sphere against frustrum bounding-sphere - very cheap
>Node Bounding-sphere against frustrum-planes - pretty cheap
>Node Bounding-box against frustrum-planes - expensive

There is also a sphere/cone test which I omitted in my current engine but can be added for possible performance increases in some cases.

You should have a general boundingVolume class which handles this for you - this class will become one of your most useful.

Share this post


Link to post
Share on other sites
Quote:
You should be using a range of frustrum-culling algorithms on your node-bounding-boxes, ranging from most to least trivial. Personally I am using 3 tests, each one only used if the one before passed:

>Node Bounding-sphere against frustrum bounding-sphere - very cheap
>Node Bounding-sphere against frustrum-planes - pretty cheap
>Node Bounding-box against frustrum-planes - expensive


You'd have a hard time convincing me that the cost of doing the tertiary check is justified. Basically you're incurring a third check for every chunk on the screen to catch trivial bordering cases missed by your sphere.

I would make the argument that it probably makes more sense to grid your terrain onto the cardinal axes and use AABB checks - eliminating both your box check (which I assume to be oriented) and your sphere check.

Quote:
U agree with everything you said ScootA apart from the bit about Octrees for 3d. That is an option but in depends very much on the application. Octrees are often overkill in simple terrain applications!


Is this the general consensus? I think Thatcher Ulrich used a quadtree when doing his chunked LOD code.

Share this post


Link to post
Share on other sites
Quote:
Original post by PornAgainChristian
You'd have a hard time convincing me that the cost of doing the tertiary check is justified. Basically you're incurring a third check for every chunk on the screen to catch trivial bordering cases missed by your sphere.


Do you disagree with all of the trivial-rejection checks, or only one of them? Its all about balancing the amount of time spent doing the checks, the amount of time saved by trivial rejection, and the amount of time spent actually performing the task itself.

After I implemented the above tests, I gained about a 50% speed increase when reclaculating the entire tree's visibility, as opposed to simply using box/frustrum on all nodes - if you optimise the trivial tests well enough, they take virtually no time to calculate and can save a great deal of time...

Share this post


Link to post
Share on other sites
Thanks for the explanation :)

i thought about other things...

The quadtree can be used either for collision detection, isn't it?
But i cant use quadtree to cull objects for AI, for movements or for physics, cause , for example, if i cant see some enemy characters on the screen, i need always to move them, and to apply physics and AI to them, isn't it?
So i can cull objects for the rendering and the collision detection, but i cant do it for physics, movement, and AI, is this right?

Share this post


Link to post
Share on other sites
I like the idea of using a sphere frustum culling before the box test :) Never thought of that....
Shouldn´t be collision detection part of the physics? Even if not, I wouldn´t even cull for the collision detection. Imagine some AI-controlled entity moving over the terrain or something like that... just you don´t see it doesn´t mean it can´t collide?

Share this post


Link to post
Share on other sites
Quote:
Original post by matches81
I like the idea of using a sphere frustum culling before the box test :) Never thought of that....
Shouldn´t be collision detection part of the physics? Even if not, I wouldn´t even cull for the collision detection. Imagine some AI-controlled entity moving over the terrain or something like that... just you don´t see it doesn´t mean it can´t collide?


Most (all?) physics engines incorporating collision-detection have the ability to use some kind of spatial tree (its not compulsory)- for instance ODE uses spaces, and they can be made to use octrees.

If you don't then you will be doing lots of expensive ray/plane intersections (etc) on objects that are just not worth doing computations on. Octrees really are more useful here than quads - as they subdivide the "vertical" as well, so for example an object dropping from a great height does not test against objects far below.

Share this post


Link to post
Share on other sites
Quote:
Original post by ScootA
Do you disagree with all of the trivial-rejection checks, or only one of them? Its all about balancing the amount of time spent doing the checks, the amount of time saved by trivial rejection, and the amount of time spent actually performing the task itself.

After I implemented the above tests, I gained about a 50% speed increase when reclaculating the entire tree's visibility, as opposed to simply using box/frustrum on all nodes - if you optimise the trivial tests well enough, they take virtually no time to calculate and can save a great deal of time...


Some trivial tests are definitely necessary. But I just don't see how doing a third-level, more expensive, bounding box check saves you time if you've already passed two sphere checks.

But I could be wrong. It just seemed a bit odd for me. This means pass cases are incurring a threefold check, the last of which doesn't seem much more/less likely to fail than the second (yes a box is a tighter fit than a sphere, but I'd do one or the other rather than both).

That's the beautiful thing about programming. We can niggle about such details.

Share this post


Link to post
Share on other sites
Quote:
Original post by matches81
I like the idea of using a sphere frustum culling before the box test :) Never thought of that....


Always look for ways to minimize the low-level work being done. It's the only way to make a simulation run in real-time.

Quote:
Shouldn´t be collision detection part of the physics?


Well, not _all_ collision detection. You will need to do some outside of the 'physics' part of your game, such as checking objects against the view frustum to see if they need to be rendered.

What you can do is write a utility routine for the collision test you need to do and have both your camera clipping and physics routines call that test. Modularity is very beneficial for longevity of code and helps a lot with debugging.

Quote:
Even if not, I wouldn´t even cull for the collision detection. Imagine some AI-controlled entity moving over the terrain or something like that... just you don´t see it doesn´t mean it can´t collide?


Definitely not. But it does mean it shouldn't _render_. Culling against the frustum will save you sending it to the card just to find out it isn't visible.

Share this post


Link to post
Share on other sites
Quote:
Original post by PornAgainChristian
Quote:
Original post by ScootA
Do you disagree with all of the trivial-rejection checks, or only one of them? Its all about balancing the amount of time spent doing the checks, the amount of time saved by trivial rejection, and the amount of time spent actually performing the task itself.

After I implemented the above tests, I gained about a 50% speed increase when reclaculating the entire tree's visibility, as opposed to simply using box/frustrum on all nodes - if you optimise the trivial tests well enough, they take virtually no time to calculate and can save a great deal of time...


Some trivial tests are definitely necessary. But I just don't see how doing a third-level, more expensive, bounding box check saves you time if you've already passed two sphere checks.

But I could be wrong. It just seemed a bit odd for me. This means pass cases are incurring a threefold check, the last of which doesn't seem much more/less likely to fail than the second (yes a box is a tighter fit than a sphere, but I'd do one or the other rather than both).

That's the beautiful thing about programming. We can niggle about such details.


Yes. You're totally right in your thinking. However - you are not taking into account the various different cases. What you are basically suggesting is a tradeoff between visibility calculation time (using less accurate bounding-checks) - versus faster rendering time (by using more accurate bounding-checks).

If a game is recalculating the visible-set very frequently (think FPS) - then you will want very fast visibility culling at a slight rendering performance decrease (you will be rendering more polygons). Now take a RTS. The camera actually changes extremely infequently compared to the amount of time it is stationary. Therefore you want the maximum rendering performance, and do not care if a visibility recalculation takes a little longer.

This is all going back to when I said that its all a balance - and what's more its a balance which depends on circumstance. There is no correct answer.

Share this post


Link to post
Share on other sites
I think AI and physics(gravity, speed...) should be apply to all the dynamic objects every frame, isn't it? So for AI and physics is impossible to cull any objects...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this