Traditionally computer graphic applications - particularly applications requiring real-time, interactive display - have approached graphic problems by determining a best possible subset of graphic data that needs to be send through the graphics pipeline, rather then processing an entire data set. Quadtrees, octrees, BSP-trees, back-face culling, potential visibility sets and many other methods were developed for this purpose.
Modern computer graphic hardware has in recent years grown exponentially in processing power and functionality. The current state of affairs indicates that it is in many cases preferable and faster to find a good data set quickly and send it to the graphics pipeline, rather then finding a best data set elaborately. Such a good data set is an approximation to a best data set and can often be found with more efficient and elegant (if less accurate) algorithms. The task at hand is thus to review existing techniques and algorithms in an attempt to find faster alternatives that are not burdened with finding the best solution possible.
In this article a heuristic approach to quadtree and octree culling is described, that is both easy to understand and easy to implement, yet still delivers very satisfactory results. I will focus on quadtrees for the remainder of the article, but the technique applies equally well to octrees.
[size="5"]Quadtrees
Quadtrees have been a favored data representation technique for many years. Particularly terrain rendering engines make use of its efficient view culling mechanism. The remainder of this section will give a short account of quadtrees and a conventional, high-level approach to using quadtrees, before describing a fast approximation.
[size="3"]Quadtree data-structure
Quadtrees are characterized by possessing four child nodes for every parent node. In a terrain rendering context the root node would represent the square region that encloses the terrain data set. The children would represent the top-left, top-right, bottom-left and bottom-right quadrants that the root node is made up of, and each of these is recursively refined with sets of four children per child upto a desired resolution. The following illustration should clarify the concept:
A data structure for a quadtree is not difficult to program, the following pascalesque code demonstrates a typical quadtree node:
TPosition = record
x,y : float;
end;
PQuad = pointer to TQuadNode;
TQuad = record
p1,p2,p3,p4 : TPosition; // corners
c1,c2,c3,c4 : PQuadNode; // children
end;function InitQuad(x,y,w : float; lev : int) : PQuad;
var
tmp : PQuad;
begin
inc(lev);
if lev > max_depth then return(nil);
new(tmp);
...initialize tmp node with corner data
w := w / 2;
tmp^.c1 := InitQuad(x - w, y - w, w, lev);
tmp^.c2 := InitQuad(x - w, y + w, w, lev);
tmp^.c3 := InitQuad(x + w, y + w, w, lev);
tmp^.c4 := InitQuad(x + w, y - w, w, lev);
return(tmp);
end;In many applications the primary function of a quadtree is to offer efficient culling of data against the viewing frustrum. The following high-level description to quadtree-based view culling should suffice:
procedure CullQuad(q : PQuad);
begin
case Clip_Quad_against_View(q) of
inside : DrawQuad(q);
outside : ; // ignore quad
else begin
...CullQuad children of q
end;
end;
end;[size="3"]Alternative quadtree-based view culing
The method described above yields correct results in the general case, however it does not make any provision for the simple, static structure of the quadtree. Several optimizations can be applied to the quadtree culling process. The following two-phase alternative produces a very fast and efficient quadtree-based view culling:
- Point-based culling - a complete cull evaluation can be performed by noting the relation between the four cornerpoints that make up the quad and the field-of-view planes.
Several special cases can be considered, for example: if a single point is found to be in the field-of-view (FOV), then the quad is in the FOV. If all points are to one side of FOV, then the quad is not in the FOV. A number of additional possibilities exist, and need to be evaluated for a complete evaluation, however the two cases given above yield a sufficient heuristic to accept, reject or further refine a potential quad. - Memoization - memoization is the technique to store the results of an evaluation and looking up the stored result when the same evaluation is required.
Note that a quadtree is a static structure, the corner points of a particular quad are always the same. Additionally, note that a most corners are shared by four quads, and that during the recursive descent of the quadtree the same corners are tested again and again - by determining a corners position relative to the FOV once and memoizing the result quad evaluation is greatly facilitated.
(globals:)
Memoized : array[0..256,0..256] of byte;
posx,posy : float; // origin of FOW
Lx,Ly,Lz : float; // normal of left FOV plane
Rx,Ry,Rz : float; // normal of right FOV plane
function CheckPos(x, y : int) : int;
// checks position x,y against FOV planes, memoize
// Results: bit 1 (inside), bit 2 (left), bit 3 (right)
var
res : int;
begin
res := 0;
if (x-posx)*Lx + (y-posy)*Ly > 0 then res := 2;
if (x-posx)*Rx + (y-posy)*Ry > 0 then res := res or 4;
if res = 0 then res := 1;
Memoized[x,y] := res;
return res;
end;
function TestQuad(x, y, w : int) : int;
// quad-midpoint: (x,y)
// quad-width: 2w
// test quad against FOV
// Results: 0 (out), 1 (partially in), 2 (completely in), -1 (unknown)
var
m1,m2,m3,m4 : int;
tmp : int;
begin
m1 := Memoized[x - w, y + w];
if m1 = 0 then CheckPos(x - w, y + w);
m2 := Memoized[x + w, y + w];
if m2 = 0 then CheckPos(x + w, y + w);
m3 := Memoized[x + w, y - w];
if m3 = 0 then CheckPos(x + w, y - w);
m4 := Memoized[x - w, y - w];
if m4 = 0 then CheckPos(x - w, y - w);
tmp := m1 and m2 and m3 and m4;
if tmp = 1 then
return 2; // quad completely inside FOV
if m1 or m2 or m3 or m4 = 1 then
return 1; // quad partially inside FOV
if tmp => 0 then
return 0; // quad completely outside FOV
return -1; // else quad state undetermined
end;procedure CullQuadtree;
begin
Clear_Memoized_Array_to_Zero;
CullQuad(Quadtree_Root);
end;
procedure CullQuad(q : PQuad);
begin
case Test(quadmidpoints and half-width) of
2 : ...handle complete quad
1 : ...handle partial quad
0 : ; // ignore quad
else begin
...CullQuad children of q
end;
end;
end;[size="5"]Additional considerations
A few points should be mentioned regarding the presented code and the algorithm in general
- The quadtree version of this algorithm as it was presented only culls the quadtree for left/right evaluation of FOV, no near, far, top or bottom planes are considered. Additionally only flat-(2D)-projection of the FOV is considered. Thus the algorithm (as it is presented in the code) only covers quadtree culling at quadtree height and viewing along the quadtree plane.
Extending the code to traverse a 3D-quadtree (corner points form a cube, rather then a square) and applying the algorithm to process octrees removes these limitations - any viewing position and direction will be correctly processed. - Several additional point / FOV considerations can be implemented, for example: if two corner points are in front of the FOV origin and on opposing sides of the FOV, then the quad is partially inside the FOV. For most scenarios the algorithm described yields very satisfactory results.
- The primary concern with the proposed algorithm is its memory requirement, though certainly not steep the memoization requires an additional byte (at most) for each possible quad corner point. Thus if a square region with n intervals per side is memoized, the memoization requires n[sup]2[/sup] bytes. Though typically only a fraction of this memory is accessed for a given traversal, and the part that is accessed is likely to be accessed several times.
[size="5"]Bibliography
Alan Watt, "3D Computer Graphics", 3rd Edition, Addison-Wesley
Thatcher Ulrich, Continuous LOD Terrain Meshing Using Adaptive Quadtrees
