Ok I''ve been reading some terrain tutorials and I''m wondering why a quad tree is used to store the terrain blocks. Since the blocks are in a grid layout, couldn''t you just use and array of structures with pointers to the blocks of map data? Whats the advantage or using a tree? I assume access speed doesn''t matter much either way, since you will be spending most of the time on rendering; similarly there is not too much difference between memory usuage for the tree and array since this is negligable compared to the memory used for the geometry data. Since you are just swapping a bunch of pointers, loading new map sections shouldn''t be too much faster or slower either way. With an array it seems its easier to figure out what square you are standing, so why use a tree? What am I missing?

quad trees can be much faster for LOD algorithms. They allow you to very quickly determine whether or not a large part of the map will be visible and thus whether or not you have to draw it. Similarly, if you are doing collision detection against your terrain, you can throw out huge portions of the map to cut down dramatically on the amount of time required to perform collision detection. I''d draw a picture but they don''t seem to come out right in these messages.

Imagine a huge square (your terrain) broken up into four smaller squares. If you have a car sitting on the ground in one of these squares, then the first collision detection pass can determine that the car is not in 3 of the 4 squares. You have just eliminated a HUGE amount of terrain to perform collision detection against. So now you are left with only 1 of the original 4 squares. Break THAT square up into 4 smaller ones, and do the same thing again. This is the quad tree approach. You can see how this allows you to very very quickly get down to exactly where the car is with very little processing and do some fine grain collision detection only where necessary.

The same type of argument applies to rendering. Imagine the viewing frustrum only has 1 of the 4 original squares in it. Then the other 3 can be completely ignored. Once again, 3/4 of the terrain can be ignored for this rendering pass. Then you can further subdivide the square that is left over depending on what pieces of it the camera can see, how far the camera is from various parts of it, and so on. I''m sure you''re getting the idea...


kiev

I understand how the trees are used and what they are used for© What I do not understand is why it is that we use a tree instead of an array© The reason that I ask is basically because I''m lazy, and its much easier to come up with a vector or an array than to come up with a quadtree ¥until they include quad and oct trees in the STL at least¤, and I can''t seem to understand why a quadtree would be preferable to an array© It seems that since the map data are fixed in a grid, an array of pointers to terran data structures will work just as well as a tree©

I have both quad tree and array in my project. I store a height map in the array, and usefull information about whole squares of map in the tree nodes and leaves. But for the future I plan to just put all of the data (height and all) in the tree. This would save a lot of memory if the tree splits to high detail only where its needed (rough areas).

As for stl, I'm sorry I made my tree with classes anyways.

Edited by - Diodor on May 4, 2001 4:58:23 PM