Contents  Background and  Theory: What are  quadtrees?  Putting it Together:  Coding a Quadtree  Printable version  Discuss this article  in the forums  Get the source

Putting it Together: Coding a Quadtree

Before we go any further, I advise those who are unsure about Indexed Lists to read through my tutorial here.

So, now we've got the theory under our belt. How do we put it together? We will need:

• A structure to hold our Quadtree data
• A function to create the tree
• A structure to hold triangle data

typedef struct node
{
  int bType;
  VERTEX vBoundingCoordinates[4];
  unsigned int uiBranches[4];
  unsigned int uiVertexStrip1[8];
  unsigned int uiVertexStrip2[8];
  unsigned int uiVertexStrip3[8];
  unsigned int uiVertexStrip4[8];
  unsigned int uiID;
  unsigned int uiParentID;
}NODE;

The variable bType tells us what type this node is. It can either be NODE_TYPE or LEAF_TYPE. If we are drawing our tree (terrain), it is used as a flag to tell the program to either stop and draw some triangles (LEAF_TYPE) or carry on reading through the tree (NODE_TYPE).

Next is an array of 4 vertices. These hold the node's bounding coordinates. The layout for the structure VERTEX is as follows:

typedef struct vertex
{
  float x,y,z;
}VERTEX;

Now we have an array called uiBranches. This is an array of four indexes to the quadtree array. These indexes are the 'children' of the node. If the bType is LEAF_TYPE, this isn't used.

As we said each leaf would hold 16 triangles, we have 4 arrays, named uiVertexStrip1 to uiVertexStrip 4. Each of these arrays holds 4 indexed triangles in the form of a triangle strip. In this tutorial, we won't be using these, so we won't go into detail about them (it also saves me an explanation).

The variable uiID holds the nodes ID in the quadtree. As I said before, the quadtree is just an array of nodes. The ID is just an index in that array.

Then we have our last variable, the uiParentID. This is the ID (index) of the parent. This, coupled with the uiBranches array, lets us navigate our way round the tree, by jumping from node to node. At any given node, we can go to its parent or its children, which, if we follow the tree, will take us to the root, or all of the leaves.

NODE *pNodeList;

The line above creates a pointer structure called pNodeList. It can be called anything. Basically, it is our quadtree. Note: we'll use array element pNodeList[0] as our root.

Formula 1.

The above formula gives us the number of leaves. The Leaf Width is the number of triangles across in each leaf. As we said each leaf will be one cell by one cell, we also said each cell contains 16 triangles. In our case, seeing as cells are 16x16 triangles, the Leaf Width will be 4. Grid Width is the width of the grid in triangles. As each cell is 4 triangles across, 16 cells x 4 is 64. To find out the total number of nodes in the tree, we call the function CalcNodeNum. Below is the function CalcNodeNum:

unsigned int CalcNodeNum(unsigned int max,unsigned int min)
{
  int ctr=0;
  int var = 0;

  while(var==0)
  {
    ctr+=max;
    max=max/min;

    if(max==1)
      {var=1;}
  }
  ctr++;

  return ctr;
}

Here, CalcNodeNum takes two parameters: the total number of leaves (max), and the leaf width (min). In our case, the leaf width is 4 triangles. The total number of leaves was obtained in the previous formula. What CalcNodeNum does is keep on dividing the grid by min to get the total number of leaves. Step through the function to understand it better. So, let's get the next bit of code done:

unsigned int Temp =(GridWidth/4)*(GridWidth/4);
unsigned int Temp2 = CalcNodeNum(Temp,4);

pNodeList = (NODE*)malloc(sizeof(NODE)*Temp2);

Ok. The first line uses Formula 1 to calculate the total number of leaves. The second line stores the total number of nodes in an unsigned integer called Temp2. The third line allocates memory for pNodeList. We typecast the function "malloc" with our structure "NODE". Then, we allocate memory for Temp2 nodes by multiplying the number of nodes by the size of the NODE structure. For more information, check out the "malloc" and "sizeof" functions in your compiler's help file. Now that we've calculated the number of nodes and allocated memory for our quadtree, let's call our quadtree creation function.

But first, let's lay the foundation knowledge for recursive code. We'll use a number counter as an example. If we want to display the numbers 1 to 10, we could do this:

void Count(int num)
{
  cout<<num<<"\n";
}

void main()
{
  Count(0);
  Count(1);
  Count(2);
  Count(3);
  Count(4);
  Count(5);
  Count(6);
  Count(7);
  Count(8);
  Count(9);

  return;
}

But as you know, that would be tedious every time we wanted to count with numbers. So, the natural progression would be something like so:

for(int ctr=0;ctr<10;ctr++)
{
  Count(ctr);
}

Although there is nothing wrong with the above code, using it for our quad-tree would be a real nightmare. This would involve having lots of temporary values and it would take a lot of time to get right. You'll understand why once we've coded our quadtree. In the above code, we have actually implicitly called Count 10 times ourselves. If we wanted to call it 20 times, we would have to explicitly tell the 'for' statement 20 times. Recursive code needs only be called once. There is no need for 'for' or 'while' statements. The reason is that we call the recursive function, and it calls itself however many times we tell it to. So, to the code:

void Count(int num)
{
  static int ctr = 0;

  if(ctr>num)
    {return;}
  else
  {
    cout<<ctr<<"\n";
    ctr++;
    Count(num);
  }
}

void main()
{
  Count(ctr);

  return;
}

The static integer 'ctr' means that 'ctr' is declared once (the first time the function is called), but its value is used by subsequent calls to the function. It is like a global variable which only Count can see. As you can see, we only call Count once. It keeps on calling itself until a certain condition is met (in our case, when 'ctr' reaches the value of 'num'). So, when we, the programmer, call Count for the first time, we have to set it up. We give it a condition to meet, in our case the number 10. If we wanted it to count to 20, we would pass '20' to Count when we call it. Right, let's summarise that:

The programmer only calls a recursive function once. The first call (made by the programmer) tends to 'initialise' the function, telling it what to do and what conditions are needed to stop calling itself.

Well, I'm glad that's out the way. On with our code. Now, let's look at the function CreateNode. As the name suggests, this creates nodes. If only it were that simple :) As this function is recursive, not only does it 'create a node', but by calling itself, it creates the whole quadtree! We only need to call the function CreateNode once, and it does all the hard work. The format for CreateNode is as follows:

void CreateNode(unsigned int Bounding[4],unsigned int ParentID,unsigned int NodeID)

This function returns nothing. Nil. Void. If you want, you could make it return something like a BOOL for error checking, but for this tutorial, I know the code works, so we'll leave it as 'void' ;). CreateNode takes 3 parameters. The first is the bounding coordinate for the node. These bounding coordinates are index values for the grid/terrain. They are in the following order. Top-left, top-right, bottom-left, bottom-right. The next value is the ID (index) for the node's parent. Last, but by no means least, is the ID (index) for the node. As I said above, when we, the programmer, call CreateNode, we need to initialise it. As the first node is the 'root', we need to set the parameters for the root. The bounding coordinates for the root are that of the whole terrain. In our case, they would be as follows: (0,0,0) (16,0,0) (0,0,16) (16,0,16). The only problem with that is that we just blurted some vertex data. Bounding[4] uses vertex indexes, so we need to find the indexes for the terrain. Put that calculator away, as I have done the work for you:

In a 2D array extending in the x/z plane with height values of '0' (i.e. our grid), to find the top left, we use the following equation:

Wow, that'll get your head scratching. Don't get too cocky, as that was the easy bit. To find the top-right, we use the following equation:

Easy, easy... Now let's try the bottom-left:

And now the bottom-right:

The mathematics isn't hard, but if you're having trouble understanding it, then just plot a grid on some paper (or better yet, squared paper), and step through it. Now we're ready to call CreateNode:

unsigned int uiBoundingCoordinates[] =
  {0,GridWidth,(GridHeight*(GridWidth+1)),((GridHeight)*(GridWidth+1))+GridWidth};

CreateNode(uiBoundingCoordinates,0,0);

What we have done is set up the root node. The root node has the bounding box described above, no parent (so a parent ID of 0), and its ID is 0, i.e. the first element in our quadtree array. We are now prepared to walk through the CreateNode code.

void CreateNode(unsigned int Bounding[4],unsigned int ParentID,unsigned int NodeID)
{
  static unsigned int TotalTreeID = 0;

  unsigned int uiNodeType;
  unsigned int uiWidth,uiHeight;

Ok, the static unsigned int 'TotalTreeID' holds the current number of nodes. We use this later on to assign the nodes children their IDs. The unsigned int uiNodeType holds the node's type, either a leaf (LEAF_TYPE) or a node (NODE_TYPE). The unsigned ints uiWidth and uiHeight will hold the width and height of the node. As we are passed just bounding coordinates, we don't actually know the dimensions of the node. We use the uiWidth and uiHeight to tell whether the node is a leaf or node. Now we need to get the width and height from the bounding coordinates:

  uiWidth = fVerts[(Bounding[1]*3)] - fVerts[(Bounding[0]*3)];
  uiHeight = fVerts[(Bounding[2]*3)+2] - fVerts[(Bounding[0]*3)+2];

This assumes fVerts is an array containing a list of vertices, which build up our grid. As a vertex contains 3 parts, x, y and z, each vertex in the array will occupy 3 elements. Normally, if we have an index of value 3, it would point to the third element. But... as each vertex occupies 3 elements, and index of 3 would point to the third element, i.e. Vertex 0's Z component.

Figure 14

As you can see, an index of 0 points to element[0]. Element [0] is Vertex 0's X component. Element 3 is Vertex 1's X component. This is all very nice, but our indices are wrong, right? Surely if Bounding[0] was '3', it wouldn't point to the third vertex, but the second vertex's X component? Well, we multiply the index by 3 for the vertex's X component, add 1 for the Y component, and add one more for the Z component. so, if we have an index of 3, it's supposed to point to vertex 3. Ok, 3*3 is 9, and the ninth element is vertex 3's x component. So, if we wanted index 3's z component, we would do (3*3)+2, which gives us element 11, vertex 3's Z component! To find the width of the node, we subtract the top-left vertex's X component (remember, x values in our grid go across, so they represent width) from the top-right vertex's X component. And to find the height, we subtract the top-left vertex's Z component (when we say 'height', we mean the depth, but we call it 'height' to make it easier to picture as a 2D grid) from the bottom-left vertex's Z component.

Now, we said that our leaves are 4x4 triangles. This implies that leaves are 4 triangles wide. As we know the width of the node (stored in uiWidth), if we divide the width by 2 and get a result of 2, then the width is 4, and hence our node is a leaf.

  if(0.5*uiWidth==2)
  {
    uiNodeType = LEAF_TYPE;
  }
  else
  {
    uiNodeType = NODE_TYPE;
  }

Notice that multiplying by 0.5 is the same as dividing by two. Next, we want a pointer to our node. The reason for this is to save me getting RSI from typing the same thing about 50 times. So, pNodeList contains all our nodes, we just need to select our node:

  NODE *pNode = &pNodeList[NodeID];

All this means is that instead of doing stuff with our node like so:

  pNodeList[NodeID].uID = Whatever;

We can simply do this:

  pNode->uiID = Whatever;

The next bit just fills our node with values we have already discussed.

  pNode->uiID = NodeID;
  pNode->uiParentID = ParentID;

  pNode->vBoundingCoordinates[0].x = fVerts[(Bounding[0]*3)];
  pNode->vBoundingCoordinates[0].y = fVerts[(Bounding[0]*3)+1];
  pNode->vBoundingCoordinates[0].z = fVerts[(Bounding[0]*3)+2];

  pNode->vBoundingCoordinates[1].x = fVerts[(Bounding[1]*3)];
  pNode->vBoundingCoordinates[1].y = fVerts[(Bounding[1]*3)+1];
  pNode->vBoundingCoordinates[1].z = fVerts[(Bounding[1]*3)+2];

  pNode->vBoundingCoordinates[2].x = fVerts[(Bounding[2]*3)];
  pNode->vBoundingCoordinates[2].y = fVerts[(Bounding[2]*3)+1];
  pNode->vBoundingCoordinates[2].z = fVerts[(Bounding[2]*3)+2];

  pNode->vBoundingCoordinates[3].x = fVerts[(Bounding[3]*3)];
  pNode->vBoundingCoordinates[3].y = fVerts[(Bounding[3]*3)+1];
  pNode->vBoundingCoordinates[3].z = fVerts[(Bounding[3]*3)+2];

  pNode->bType = uiNodeType;

Now, in this tutorial I won't deal with leaf nodes. Once we've assigned a leaf node its type (LEAF_TYPE), I'm going to just return to the calling function (i.e. do nothing). In the real world, you may wish to have a leaf point to an array or triangles. If you have a look at the NODE structure, you'll notice I left 4 vertex strips (uiVertexStrip1...4), which, if you want, you can fill with triangles. This is so when you are drawing the terrain and you hit a leaf, you can tell it to draw those triangle strips (which represent that portion of the terrain).

  if(uiNodeType == LEAF_TYPE)
  {
    return;
  }
  else
  {

Next, we need to do the following for each of the node's children: Add one to uiTotalTreeID, create a new bounding volume for that child, call CreateNode passing the new bounding volume, NodeID for the parent ID and uiTotalTreeID for the new node's (child's) ID.

    unsigned int BoundingBox[4];
    TotalTreeID++;
    pNode->uiBranches[0] = TotalTreeID;

    //Top-Left i.e. b[0]
    BoundingBox[0] = Bounding[0];
    //Between b[0] and b[1]
    BoundingBox[1] = Bounding[0]+((Bounding[1]-Bounding[0])/2);
    //[between b[0] and b[2]
    BoundingBox[2] = Bounding[0]+((Bounding[2]-Bounding[0])/2);
    //middle of node
    BoundingBox[3] = Bounding[0]+((Bounding[2]-Bounding[0])/2)
                                +((Bounding[1]-Bounding[0])/2);

    CreateNode(BoundingBox,NodeID,TotalTreeID);

What we have done is split the bounding volume to 1/4 its size. We do this differently for each child, as the above shows splitting for the top-left child. Notice for the top-left of the child, it is the same as the top-left of our node. The top-right of the child will be halfway between our nodes Bounding[0] and Bounding[1]. I'll show you the rest, just so you get the idea.

    //**************************************************************************

    TotalTreeID++;
    pNode->uiBranches[1] = TotalTreeID;

    // Between b[0] and b[1]
    BoundingBox[0] = Bounding[0]+((Bounding[1]-Bounding[0])/2);
    //Top-Right i.e. b[1]
    BoundingBox[1] = Bounding[1];
    //middle of node
    BoundingBox[2] = Bounding[0]+((Bounding[2]-Bounding[0])/2)
                                +((Bounding[1]-Bounding[0])/2);
    //between b[1] & b[3]
    BoundingBox[3] = Bounding[0]+((Bounding[2]-Bounding[0])/2)
                                +((Bounding[1]-Bounding[0]));

    CreateNode(BoundingBox,NodeID,TotalTreeID);

    //**************************************************************************

    TotalTreeID++;
    pNode->uiBranches[2] = TotalTreeID;

    //between b[0] and b[2]
    BoundingBox[0] = Bounding[0]+((Bounding[2]-Bounding[0])/2);
    //middle of node
    BoundingBox[1] = Bounding[0]+((Bounding[2]-Bounding[0])/2)
                                +((Bounding[1]-Bounding[0])/2);
    //Bottom-Left i.e. b[2]
    BoundingBox[2] = Bounding[2];
    //between b[2] and b[3]
    BoundingBox[3] = Bounding[2]+((Bounding[3]-Bounding[2])/2);

    CreateNode(BoundingBox,NodeID,TotalTreeID);

    //**************************************************************************

    TotalTreeID++;
    pNode->uiBranches[3] = TotalTreeID;

    //middle of node
    BoundingBox[0] = Bounding[0]+((Bounding[2]-Bounding[0])/2)
                                +((Bounding[1]-Bounding[0])/2);
    //between b[1] and b[3]
    BoundingBox[1] = Bounding[0]+((Bounding[2]-Bounding[0])/2) + uiWidth;
    //between b[2] and b[3]
    BoundingBox[2] = Bounding[2]+((Bounding[3]-Bounding[2])/2);
    //Bottom-Right i.e. b[3]
    BoundingBox[3] = Bounding[3];

    CreateNode(BoundingBox,NodeID,TotalTreeID);
  }

All we need to do is return nothing and end CreateNode's curly brackets:

  return;
}

And that's about it. You can download the fully annotated source and executable here.