Sign in to follow this  
freezzo

splitting terrain/loading quadtree?

Recommended Posts

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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by freezzo
Ok 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 this post


Link to post
Share on other sites
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
add them to patch

End

End

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

Any insight?

Share this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this