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

Background and Theory: What are quadtrees?

With the revolution of consumer 3D graphics cards, there was a boom in 3D games. Most of these were first person shooters, and for a very good reason. The reason is that indoor environments, when compared to outdoor environments, are far simpler. With the great outdoors, there are no convenient staircases to the next level, or doors and walls blocking your view. Believable outdoor environments go on for miles. The sheer geometry involved is phenomenal, and any steps to cut this down are welcomed. Enter quadtrees.

Note: the following diagrams are a top-down view of a 3D terrain. The grid shows the terrain on the x/z axis, as the actual "height" (i.e. hills) isn't visible, as we are looking down the y-axis.

Figure 1

Imagine your terrain as a large grid, extending in the x/z plane. Take a look at Figure 1. Here, we have the camera located in the bottom right of the terrain, with the viewing frustum (the blue triangle) extending a few cells in the same direction. So, before any optimisations, the routine for drawing the terrain would look like this:

for(int ctr=0; ctr<num_of_cells; ctr++)
{
  DrawCell();
}

(Note: a cell is just a square containing a number of triangles that are part of the terrain.) This is all very nice, but as our terrain is 16x16 cells, 256 cells are being drawn. This is a lot of wastage, as only 5 cells are in our viewing frustum! Now our first optimisation: we'll test each cell to see if it lies in our viewing frustum, and if it does, draw it. Now our code looks a little like this:

for(int ctr=0; ctr<num_of_cells; ctr++)
{
  if(cell is in frustum) DrawCell();
}

If the cell is in our frustum, we'll draw it. Right, now we're only drawing 5 cells, as opposed to 256. With that bit of modified code, we've saved ourselves drawing 251 cells! But, once again, it is very inefficient. Take a look at Figure 2.

Figure 2

I've shaded certain cells blue, so they create a bounding box. If the blue cells aren't in the frustum, then we can safely say that the cells inside Section A won't be either. If we know that the blue cells aren't in the frustum, why do we bother testing the other 144 cells in section A? That's were quadtrees come into play.

Quadtrees take the terrain, and divide it up it into four smaller parts, then those smaller parts into four smaller parts, and so on, until it reaches a set size. That may seem a little confusing, but let me explain with pictures. First, we start off with our grid. We now divide that grid into 4 smaller sections.

Figure 3

As you can see from Figure 3, we now have four subsections of our terrain. We now need to keep dividing into 4 sections, until we reach, say, a section of only 1 cell. So, in our next diagram, we'll divide the first section into four smaller parts.

Figure 4

Again, we'll divide one section into 4 smaller parts:

Figure 5

And again, we'll divide a section into four more parts:

Figure 6

Ok. We've divided our section again, and its sub-sections are only one cell wide and tall. We tell our tree to stop dividing this section, but carry on to the next. Eventually, the whole tree will be divided up. So, to recap, to create a quadtree, you divide it into four sections, then those sections into four sections, then divide those smaller sections into four sections, and so on. When do we stop? When we reach a certain size. This size is abitary, so make it up yourself. In our example, we'll say each cell contains 16 triangles (4x4), so we'll stop when our subdivisions are one cell by one cell. We could keep on going, but we wont. One thing I haven't told you is the parent/child relationship. Each subdivision (called a Node) has one parent (the Node, which it was split from,) and four children. The exceptions are leaves, which only have a parent. A leaf is the smallest subdivision we allow, in our case, one cell by one cell. Another thing: before you subdivide, you have a root: The root has no parent, but, like the rules, has four children. Still don't get it? Let's have an example. You know those susceptible chain letters? It's like that. One person (the Root) sends a letter to four people (the Root's children). Now, these four people (Nodes) share the same parent: the evil conspirator (the Root). The letter says "Send this letter to four more people else you'll have seven years bad luck/unlimited fame/whatever." So, each one of those four people send the letter to four more people, and so on.

Look at figure one again. The dark red border is the root. In Figure 3, we divide the root, and assign it its children. The four squares represented by the blue line are the roots children. We'll call them Node 2, 3, 4 and 5 respectively. In Figure 4, we took the first child of the root (node 2), and divided it up into 4 more squares. These squares are that node's children. All of those children share the same parent: The first child of the root, or, as we called it, node 2. We'll call these nodes Node 6, 7, 8 and 9. Once again, we divide node 2's children into four more squares (nodes), and we'll name these 10, 11, 12 and 13. Nodes 10-13's parent is node 6. This is represented in Figure 5. In Figure 6, we divide node 10, giving us leaves 14, 15, 16 and 17. As they are leaves, we don't divide them, go back and carry on dividing our next node, node 11. When node 11 is done, we do 12 then 13, then 7, 8 and 9, then 3,4 and 5. Then we're done.

I know that's a really jagged piece of toast to swallow, but read it carefully. Then again. If you're still unsure, have a gander round the web. You'll probably click eventually, as they are easy to understand if explained correctly. In a final desperate attempt, I'll walk you through the process of using a quadtree. But first, let's have a nice summary:

A quadtree divides terrain into four pieces, and divides those pieces into four pieces, and so on, until it reaches a certain size, and stops dividing.

Quadtrees work by using the bounding coordinates of a node. Let's say our map goes from 0 - 16 in the x-axis and 0 - 16 in the z-axis. In that case, the bounding coordinates of our whole map are top-left = (0,0,0), top-right = (16,0,0), bottom-left = (16,0,0), and bottom right = (16,0,16). When we split the root node, we split its bounding coordinates as well, so node 2 has bounding coordinates: top-left = (0,0,0), top-right = (8,0,0), bottom-left = (0,0,8), and bottom right = (8,0,8), as in Figure 7.

Figure 7

Test 1

The way it works is we start at the root and say "Is the camera within the root's bounding coordinates?". Unless something is wrong, we say "yes". We know the camera is within the root's children, so now we test them. "Is the camera within Node 2's bounding coordinates?". The answer here is no, so we can dismiss node 2 and all its children. So far, we have dismissed testing 64 cells (the number of leaves in Node 2). Not bad, not bad.

Figure 8

Test 2

As you can see in Figure 8, I've removed Node 2 and all its children for the sake of clarity. Once again, we test the tree. "Is the camera within Node 3's bounding coordinates?". Again, the answer is "no", so we can safely dismiss Node 3 and all its children.

Figure 9

Test 3

So, here we go. "Is camera within Node 4's bounding coordinates?". No surprise, the answer is "no". Time to test Node 5.

Figure 10

Test 4

This time, the camera is within Node 5's bounding coordinates, so we test its children. I've named Node 5's four children A, B, C and D for clarity. Time to test Node 5's first child. "Is camera within Node A's bounding coordinates?". Looking at Figure 10, we can see that it isn't, so we'll dismiss Node A and its children.

Figure 11

Test 5

Now let's test Node 5's second child. "Is camera within Node B's bounding coordinates?". Looking at figure 11, we can see that it doesn't, so we'll dismiss Node B and its children.

Figure 12

Test 6

Right, let's test Node C, Node 5's third child. "Is the camera within Node C's bounding coordinates?". 'Course it's not, so let's just rid ourselves of node C altogether.

Figure 13

Test 7

Ok, it has to be in Node D. "Is the camera within Node D's bounding coordinates?" "Yes, yes it is." Finally. Now all we have to do is test all of Node D's children (groan). Well, I'm gonna stop here. Think of working the rest out as an exercise :). For your information, there are 16 more tests, resulting in 5 cells being visible. Let's total up the number of tests. 7 + 16 = 23. We've gone from 256 tests to 23 (22 really, as it wasn't worth testing the root. The camera must lie within the root, else nothing would be visible). With a quadtree, we've done approx. 11.6% of the work of the previous method of testing every cell/leaf. By now you should have a firm understanding of the theory of quadtrees, so put on your coding socks, because were going to make one. Not so fast, Sonny Jim. We'll just summarize what we've talked about:

A quadtree is used to dismiss large chunks of terrain at a time. If an apple is on a tree's leaf, chopping off the branches the apple is nowhere near saves you looking on every leaf.

Next : Putting it Together: Coding a Quadtree