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