   Terrain & Quadtrees -- Top-down vs. Bottom Up construction
  This has been bothering me for a bit, so I wanted to figure out what everyone is doing with their quadtrees. The classic way is to start at the top and recursively subdivide nodes, which is what I was planning to do with my new engine. But this has a few limitations:1) The actual size of each leaf is a little hard to determine, and I can''t really force it to be, say, 33x33 without forcing the terrain to be 1025x1025 and forcing the tree depth to be 5.2) I can''t do optimizations like using the same index buffer for a 33x33 patch for each leaf; I have to use a single massive buffer and figure out which indices each leaf uses. Kills performance and memory use.3) Basically can''t assume anything about geometry since the subdivision is based on previous node rather than the geometry itself (which is necessary so I can create the tree without referring to the actual data, and give myself the freedom to load/unload patches as required).So I thought, why not use an alternate algorithm, which starts by subdividing the terrain into 33x33 chunks, constructs indices, and constructs the tree from the bottom up, rejecting patches that are not really in the right ranges (e.g. a 1032x1032 map would get 7 vertices rejected on each side). A little harder to implement, but this has some advantages:1) Patch size is fixed, which allows me to use various geometrical optmizations without actually knowing the relevant geometry.2) Maps of weird size are automatically rejected in tree construction, so I get a full, balanced tree.3) Tree depth is flexible, and so is map size--the rejection step will neatly square off the maps as required.I''m not really asking about the algos themselves, but rather what all you GDNet people are using--top-down, or bottom-up? And why? 
  I implemented a quadtree in the last 2-3 days.  Here''s how I did it...I limited terrain height maps to square, power of 2 dimensions... so 256x256 or 512x512.I then choose the number of levels for the quadtree, and given that I know the heightmap size and number of levels I create one index buffer that is used by all leaf nodes.I load the vertices into one huge array at first (the size of the heightmap) and then I create the quadtree, when I get to the leaf node it creates its own vertex, normal and texture arrays at that stage taking the correct vertices from the huge arrays.The huge arrays are then deleted, leaving the quadtree with the correct number of leafs with their own graphics arrays and using a shared index array for lower memory usage.Works like a dream. ;  you can stop subdividing at 33x33 vertices as long as you keep track of the number of elements in each subdivision... ;  Hybrid: That''s more or less what I''ve been doing, but I still have to force certain details about the map, like the power of 2-ness, otherwise the tree will cut the map in all the wrong places and screw up everything.y2kiah: I don''t want to keep track at every step because it means I have to calculate at every step; if I get a weird size map it won''t quarter properly and things will go completely awry. And then I''ll have to check every vertex at every leaf...Mostly, I''m curious if anyone has done this bottom-up and how it turned out. ;  if this helps, i update it bottom up.you specify terrain and patch size, it will calculate the depth for the quadtree and build it as one big array (getting rid of all the annoying pointers and having nodes all over the memory). youre still limited to power of 2 sizes of course.then, if all leaves have the same size, why would you need more than one index array and an offset into the vertex buffer? if you live with a few redundant vertices you can create vertex buffers for each leaf and store x,z offsets. that means every point in your heightmap is reduced to a single float and saving a lot of memory. drawback: vertex program is needed to put the final vertex together (dont worry, its fast enough to make fillrate your problem even without fancy texturing).also: i store the patches themselves in a big array, using the indices of the leaves in the tree. i first stored the index in each leaf, until i realized its brainless and redundant, when i could just arrange the patches in the same way and use the leaves index (minus index of the first leaf, that info is stored in the tree "container" itself, along with number of nodes and levels, even though the last two things dont really matter when using it).but in general i always first created patches and then (if i felt like it) built a tree on top of them (as it wasnt worth it for just a few hundred - thousand patches.. though i like my new pointer free tree.. it seems to be pretty fast and gets rid of all the ugly things about trees).you can see it in work here (danger: ugly and early state)http://festini.device-zero.de/downloads/JSFramework.zipif its running slow (ie, you have a radeon like me, set VBOShort in the config file to 0). the test.map is just 129x129 to keep it small. you can create your own (plain old raw file, size must be 2^x +1, 16bit per channel, ie. heights are unsigned shorts). in the console use loadmap  (mapsize is "even", so 128 for the included one, patchsize must be power of two and not one.. it could be one with a few changes, but for now i just dont allow it, because its a stupid size anyway *g*).size of up to 2048 should definitely work, 4096 might hit some limits memory wise (edit: just tried, it does.. wont give me a vertex buffer of 64mb *lol*). but reduce the lod first (setlod x) or everything above 2048 might become a little "unresponsive" (lod isnt adjusted automatically yet).code (tree and using it)http://festini.device-zero.de/downloads/JSSource.zipin scquadtree and terrain files.   [edited by - Trienco on February 17, 2004 1:45:51 AM];  I use my quadtrees as more general data-structure that can hold bsp trees and octrees as well as more quadtrees. I have a general subdivision system that first builds the quadtree based on the maximum dimensions of the scene and then proceeds to divide up the data to appropriate data structures which are then linked to the quadtree. ;  I split the height map into patches then create a quad tree for each patch the patches are created when needed and deleted when not needed so the only real limitation in my engine is the memory the heightmap takes ;  With a hightmap, you don''t need to "consttuct" a quadtree, it''s already there implicitly.  The smallest blocks are 33x33 (or whatever you want) and the next level up is a group of four.  You can just create a tree from those and only have to worry about the leaves at the far borders (if the map isn''t pow-2+1).  Have all of the geometry in the leaves and just culling(bounding box) info in the inner nodes.karg 