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

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?

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

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

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.

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?

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?