Contents  Introduction  Quadtrees  Additional  considerations  Printable version  Discuss this article  in the forums

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;

Next : Additional Considerations