# Quadtree vs multiple resolution grids for terrain rendering

## Recommended Posts

Quadtree vs multiple resolution grids for terrain rendering

I have been thinking about quad trees with regards to terrain rendering.

From my understanding the basic functionality of quadtree terrain rendering is to frustum cull the terrain in such a manner:

    function render() {
lod_threshold++;
if(lod_threshold_reached || !has_children()) {
draw_terrain_mesh();
return;
}
for(child in children) {
if(child.bounds.intersect(viewing_frustum)) {
child.render();
}
}
}


where node.bounds is a 3d bounds calculated as containing the maximum heightmap value of the contained terrain

My questions are the following

1. If we are in fact testing a 2d portion of terrain with it's bounds calculated to include the maximum heightmap value against the 3d frustum, what is the preferred bounds calculation for generating the node.bounds in the quadtree?
2. That a tree is necessary because that one has to iterate every portion of a 3d scene to calculate frustum occlusion in a general way. Eg, there is no shortcut algorithm to calculate the set of 3d cells generated from a 2d grid that intersect the viewing frustum. As a more general question and to question the obvious, is there a way to calculate cells in a viewing frustum without having to iterate every cell in a scene? Presumably not otherwise you wouldn't need trees for culling

With regards to an alternative grid implementation:

Has this implementation been contemplated for general purpose terrain culling?

    function calc_cells_in_quadrilateral(frustum_projection_onto_2d_terrain_grid) {
//calculate cells in the resulting quadrilateral projection of the frustum onto the grid without having to bounds test every cell
//at some point based on distance from camera, assign lod
}
retrieve lod for each cell in the calculated set from lod grids
have multiple (array2 or intmap) containing the terrain data at every lod for O(1) retrieval

1. Is there is a way to calculate cells in a quadrilateral without having iterate every cell in a grid? eg, from shaving off cells from slopes or something?
2. If there is, in what fashion should one assign the lod cell based on distance? I haven't contemplated this in detail because #1 may be impossible
3. The terrain would not be optimally culled in this 2d culling algorithm against the quadrilateral frustum projection onto the heightmap, because the height value at the edges may be outside the screen, correct?

4. http://www.olhovsky.com/2011/03/terrain-started/ In this post, he describes assigning lod from a grid and from a quad tree. The illustrations are confusing with regards to whether question #1 is correct and terrain rendering with quad trees serves to draw the terrain mesh against the frustum as opposed to just as a function of distance 360 around the camera as at appears to do with his grid implementation. Please specify whether it appears that he is infact not frustum culling in the grid implementation but is frust

I am presuming that some form of grid base terrain culling is preferred in certain games, namely top down games where the possibility of terrain in the distance of being on camera is non-existent.

Edited by dlots

##### Share on other sites

I recommend you this paper :

It did not answers all questions, but there are some clues in it.

Edited by chrisendymion

##### Share on other sites

You should use Hull Shader for tessellation and Domain Shader which is your new vertex shader.

Then you have free LOD on GPU, you can add bounds on the vertex data to cull each patch of the terrain using frustum culling.

Edited by Alundra

##### Share on other sites

Then you have free LOD on GPU

TANSTAAFL

I prototyped this shortly after tessellation shaders became available in OpenGL, and while it works reasonably well, the complexity is high enough that I went back to a CPU-based CLOD setup fairly quickly.

##### Share on other sites

Although the posts here are useful in general, I am looking for specific answers to the questions I've posted. I've read the papers and articles on LOD terrain and the questions remain in general.

Eg, some people claim to have a requirement to use quadtrees for lod terrain but don't actually frustum cull which begs the question, why are you using a quadtree at all? The essence of an alternative of multiple indexed lod sets is specified in the original post.

The questions I posted have value in answering the unclarified statements encountered in certain articles.

##### Share on other sites

Eg, can you not implement terrain lods without frustum culling using a distance vector from the camera against the heightmap? Why would you need a quadtree if you do that?

## 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

• ### Forum Statistics

• Total Topics
627737
• Total Posts
2978880

• 10
• 10
• 21
• 14
• 13