# 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? I am presuming that some form of grid base terrain culling is certainly preferred in certain games, namely top down games where the possibility of terrain in the distance of being on camera is non-existent.

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 frustum culling the quadtree.

For performance reasons I never frustum cull on the CPU -- I just distance cull as part of the LOD determination so I'm rendering everything in front of and behind the camera (let the GPU do the culling for the frustum) so that when the player turns there is no potential lag while new terrain chunks are activated or (even worse) sent to the gpu. I also don't worry much about terrain occlusion.. if the player is within viewing range of a chunk the data needs to be there in case he walks over the ridge.. again a case where having the data on the GPU and letting the GPU depth buffering handle the occlusion is worth the trouble.

LOD for distance needs to be based on the distance between the corners of a chunk in pixels at a given viewing distance and camera field of view. There just isn't much point to rendering a distant chunk at such high LOD that the chunk is only a few pixels of screen area, so you step up the quad tree or don't drill down so far that you are processing a lot of vertex and texture data for a very small number of pixels. Finding a good balance here can be a royal pain :) Especially note that the pixel size of an edge viewed edge on can be calculated using nothing more than the distance and field of view numbers without performing any matrix math using the view/projection transform, and typically that pixel width of an edge is more than sufficient to determine what LOD needs to be used for a specific branch of the quad tree.

You do need the quad tree to manage the LOD data and to contain references to the GPU objects that represent your terrain, and to manage loading and unloading that GPU data as needed while the player is moving around. Just pay attention to what the GPU can do FOR you that reduces CPU load for deciding what needs to be active on the GPU because it is potentially viewable now or in the near future :)

• If you are not frustum culling why do you need a quadtree which is my question essentially. As you specified, you can determine the lod of a set of cells, then you can lookup the lod from the set of lod arrays, facilitating O(1) access for just the specific caclulated set of cells. Other than O(1) access, there was a big thread on a java forum that is innaccessible at the moment, that specified that quadtrees also do not work well with the CPU cache. Sep 18 '14 at 0:52
• you need something to manage your references to GPU objects at different LODs (my design keeps lower LOD data on hand for quite a while since I can be fairly certain I'll need it again at SOME point as the player is moving around). I agree that quad trees can be expensive to traverse but you can limit the number of times you perform the traversal by only running the tree code when the player crosses into a neighbor node rather than every frame. The problem is I don't know how many levels of LOD you might need -- I'm working at planetary scale and may need as many as 30 levels. Sep 18 '14 at 3:55
• Okay so why don't you have 30 indexed array's for the set of 30 lods? If you can calculate the set of lods without traversing a tree, I fail to see the reason why you wouldn't just look at an index in memory... as facilitated by an array. If you aren't traversing the tree because you potentially need to traverse every block of space in a scene, to calculate the set of lods, there is no reason for the tree... hence these questions. Sep 18 '14 at 6:47
• but then you MUST search every chunk container in the list doing the comparisons as the player moves -- for large scale terrain where you may have undisplayed containers (chunks that the code knows about but havent yet been generated or loaded yet) in the list this is a lot of overhead, it would take profiling to determine if searching that list and doing the distance calcs would be cheaper than walking a subset of the tree and doing fewer distance calcs.. Sep 19 '14 at 14:23
• This is something I haven't put a lot of thought into because my terrain rendering system naturally breaks into a quad tree structure even though I'm not actually using square chunks of terrain (makes the distance calcs more interesting)... One of my friends is doing a voxel system that searches lists of chunks like you are suggesting, but he hasn't done anything more than a few hundred meters on a side at this point so there really isn't anything to compare against. Sep 19 '14 at 14:32