PDA

View Full Version : Info about Quad trees.



Anonymous Coward
09-11-2000, 02:35 AM
I want to make an engine using 'quad trees', but I have never read about them from a 'good' source. Do you know where can I get some info?

Games like Ground Control, Evolva, NBA2000 dont use BSPs or Octrees, do they use quad trees?

Don't Disturb
09-11-2000, 01:41 PM
I have only a simple knowledge of quad-tree based terrains, but I believe that you will get better results with ROAM (http://www.gamasutra.com/features/20000403/turner_01.htm) .

Chiguire
09-12-2000, 01:18 PM
Quad trees are best suited for collision detection and so, the ROAM algorithm is for landscape rendering (i've never tryied it). You have to know what you want your engine to do, because there's no QuadTree Engine, it's just a technique for poly sorting. If you want some info about it, i think there's some info in flipcode (www.flipcode.com). Making a quadtree engine is rather easy, just recursively subdivide your space into cells until you get some desired minimum number of polys for each cell. A little search on the net could give you some info about quadtrees.

zed
09-12-2000, 04:02 PM
well i render my landscape the same way as Chiguire (pity i cant see the previous posts when im replying) said but only i subdeivvide my tree down to a minimum size (a leaf) not a minimum number of polygons. which one is the more usual method? inside a leaf i store the pointers to all the static objects that are fully/partly inside

[This message has been edited by zed (edited 09-12-2000).]

Chiguire
09-13-2000, 10:51 AM
The optimum way to subdivide a leaf is to count the number of polygons and match it with a minimum number of polygons, because, when you use a quadtree to do collision tests, you know that you can process some number of polygons quite fast, that's the reason why you should use number of polygons instead of size. Rare, I can see the other posts by just pressing back!! http://www.opengl.org/discussion_boards/ubb/smile.gif, however, you can open the reply form in another window

Chiguire
09-13-2000, 10:58 AM
Oops!! in case anyone hasn't noticed it yet, in this whole conversation i've misinterpreted QuadTrees with Octrees, hehe, i think (by the little information i've got from the web) that quadtrees are the way to go for landscape rendering, and ROAM is just an advanced technique of quadtrees (blame me if i'm not right), i think that recently there's been so much hype around the *Tree techniques, that it would be a lot better if we (the programmers) stop calling techniques *Trees http://www.opengl.org/discussion_boards/ubb/biggrin.gif