Jump to content
  • Advertisement
Sign in to follow this  
kevlur

quadtree questions

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

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!