Recommended Posts

freezzo    138
I understand the quadtree concept, what i dont quite understand is how to split up the terrain. Say i have a heightmap, how do i determine which nodes to put the data in, and how does the quadtree know when a leaf if full? Do i loop through the heightmap and add data on a per triangle basis? or pass the whole array to the quadtree. Also, is it better to have the height map into a vertex buffer, and have the quadtree just work with the index buffer? Thanks

Share on other sites
lancekt    348
What would it mean for a leaf to be 'full'? In a quadtree based on a heightmap, there would be no variation in the spatial density of your data (since the heightmap is regular). Thus, since the data is regular, you probably want to make a regular quadtree out of it (meaning each node will contain the same amount of data as every node on that level). Thus each node will contain one-quarter of the data contained by its parent node, i.e.:

*-----*|     ||     ||     |*-----**--*--*|  |  |*--*--*|  |  |*--*--*

So if your heightmap is 64x64, the four nodes just below the root node would each represent one of the 32x32 quadrants of the heightmap. And their children would each be 16x16. Etc.

It would be helpful to know what exactly you are using the quadtree for. Is it to speed up culling? Or for LOD?

Share on other sites
freezzo    138
Ok that makes sense, and then do i limit the splitting of a node when i read either max depth or max patch size?

I want to use the quadtree for terrain culling and lod eventually. I have brute force now and im trying to just get the quadtree working and the terrain culled properly, and then ill incorporate an lod technique.

Share on other sites
lancekt    348
Quote:
 Original post by freezzoOk that makes sense, and then do i limit the splitting of a node when i read either max depth or max patch size?

Yup! You probably want to determine the best depth experimentally. The right tradeoff between batch size and number of batches is something best figured out with lots of profiling.

Quote:
 I want to use the quadtree for terrain culling and lod eventually. I have brute force now and im trying to just get the quadtree working and the terrain culled properly, and then ill incorporate an lod technique.

Right, so for culling you'll only want actual geometry at the leaf nodes. The simplest/easiest way to start is just to have one vertex buffer per leaf. (You can use the same index buffer for every leaf node, since they'll all have the same amount of data. Although I don't think it would really make much difference performance-wise.)

Share on other sites
freezzo    138
Thanks.

Regarding splitting the terrain up into the quadtree, is this a typical method?

For x = 1 to patchsizex

For y = 1 to patchsize y

Loop through heightmap and find which triangles are in this patch

End

End

But then if i do that, im unsure how to build it into the quadtree?

Any insight?

Share on other sites
JohnBolton    1372
The classic quadtree is used to describe the shape of a region -- each node contains a flag telling if the node is fully inside the region, partially inside the region, or fully outside the region. It is not a container. You seem to be using the tree for something else.

So, first you need to figure out what you are using the tree for -- LOD? Frustum culling? Collision detection? Once you figure that out, then it should be simple to figure out what goes in each node.

If you are using the tree for LOD, then try looking up "Chunked LOD".

Share on other sites
freezzo    138
I *think* the concept and usage of a quadtree just fully hit me. I will try to explain to make sure I am understanding it.

This is in reference to frustum culling i believe.

The quadtree basically holds "bounding boxes"(the coords for it). You then Check your objects to see if its within this area, but it doesnt actaully hold the data for that area.

Is that the idea?

Share on other sites
JohnBolton    1372
If you are using a quadtree for culling, then you place objects (or patches or triangles) in the tree so that each object is in the smallest node that completely contains it. Then you intersect the tree with the view frustum to determine which nodes are in the frustum. You do this by rejecting nodes that are fully outside the frustum and descending into the children of nodes that are partially inside the frustum. This is not what I would call a "classic" quadtree, but it is similar, and everybody calls it a quadtree anyway.