Quadtree and Octree Culling Alternative
by Henri Hakl

Introduction

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.

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.

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;

A simple recursion to initialize a quadtree to depth max_depth can be given by:

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;

Quadtree-based view culling

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;

Clip_Quad_against_View is the critical function within CullQuad The conventional - and certainly robust and functional - manner of resolving the question whether a quad (or any polygon) intersects the viewing frustrum, is by interpreting the view frustrum pyramid as a set of planes and interpreting a polygon as a set of rays, and then consecutively test how the polygon rays intersect the viewing planes. The equations for such a ray-plane test can be found in any good book on 3D geometry and will not be repeated here.

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

The following pseudo code should clarify the algorithm, for a quadtree that spans the area (0,0) to (256,256):

(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;

The above functions should be clear and need only be integrated into the CullQuad procedure given earlier:

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;

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 infront 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² 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.

This concludes the presentation of the algorithm. I have found it a useful and effective approach - if you have any queries regarding the algorithm feel free to mail me and ask.

Bibliography

Alan Watt, "3D Computer Graphics", 3rd Edition, Addison-Wesley
Thatcher Ulrich, Continuous LOD Terrain Meshing Using Adaptive Quadtrees

Discuss this article in the forums

Date this article was posted to GameDev.net: 8/30/2001
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Algorithms and Data Structures