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.

   
   

Answer

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 :)