Since the other objects (depicted as green balls) are in other quadrants than the moving ball, we do a simple check of our quad tree and discover there are no objects in the moving ball's quadrant!  This reduces our collision detection computation time greatly because we don't have to do any collision detection at all.  Without using the quad tree, we would have had 21 circle-to-circle or ball-to-ball collisions to test for, since there are 21 other objects.

We have simplified some issues so far in order to give you an idea of what this is all about, but don't worry, we will visit each one of the nitty gritty details later.  For example, since the blue ball is moving around, don't we need to check both the quadrant its currently in AND the quadrant it will be moving to, if it is crossing quadrant boundaries?  The answer is yes, and we will explore this topic a bit later in our article.

What did we just do?  We took each one of the 4 quadrants we already had and subdivided each one of them into 4 more quadrants, which results in a total of 16 quadrants!  You can see how this helps us even more, because now the moving ball has to be very near the stationary balls before we need to check for any collisions, and even once it gets near them it only has to check for collisions against the subset of balls in the particular quadrant it is in.

You can also see from the above figure that some of the green balls are on quadrant boundaries and are partially in two quadrants.  What do we do with these?  Well, we have to include them in both quadrants they overlap with, otherwise we will have errors if the moving ball should hit one of them but we don't think it needs to check against them, so it would pass through them.

This is all great and dandy, you are probably saying to yourself, and it looks nice to draw little lines everywhere, but what about the code to do this?  Great question!  Let's get after it.  We are going to create a class that will represent the quad tree.  Two things will help us in the initial design of this class:

1. The quad tree we have described above would seem to lend itself well to the concept of recursion.  (If you are unfamiliar with this or rusty on it, don't worry, we will explain it).
2. A quad tree is a tree that consists of branches and leaf nodes, but these can both be abstracted by the concept of a node.  (If you just said: "Huh?  What the heck is he talking about?"  This too will be explained).
   

Let's create the class and then see how this works out.

class CQuadTreeNode
{
public:
    CQuadTreeNode(long lowerLeftX, long lowerLeftY, long width, long height);
    virtual ~CQuadTreeNode();

   HRESULT SubDivide();

private:
   long m_LowerLeftX;
   long m_LowerLeftY;
   long m_Width;
   long m_Height;

   CQuadTreeNode** m_SubNodes;
};

Alright, let's examine what we have created here in depth.  First off, we have the constructor, which takes the values for the lower left corner of the quadrant this node describes.  We also create four member variables to store these values.  Then we have our destructor, and our first and only function, SubDivide().  Don't worry about the HRESULT return value if you don't know what it is.  On Windows systems an HRESULT is just a typedef for a long, which is just an integer.  Finally, we have the strange looking line CQuadTreeNode** m_SubNodes; . What can this mean?  It is a pointer to a pointer to a CQuadTreeNode, which is what our class is, so it will be used to store the children nodes, if any exist, of this node.  We will explain this more in a bit.

Here is the body of our constructor, in case you are wondering how to write it:

CQuadTreeNode::CQuadTreeNode(long lowerLeftX, long lowerLeftY,
   long width, long height) : m_LowerLeftX(lowerLeftX),
   m_LowerLeftY(lowerLeftY), m_Width(width), m_Height(height),
   m_SubNodes(NULL)
{
}

All we do is initialize our member variables to what they pass us in for the quadrant coordinates, and then the m_SubNodes to NULL, since we don't know what those are yet, or even if we will have any.  You can download the code for the entire class at the end of this article.

Let's use this new class immediately in our program.  When we start out, we have the entire screen to draw to.  Using whatever means are available for your platform, get the size of the screen.  On Windows, this is often done with the GetClientRect function.  For an example, you can download our screensaver example project.  Think of the screen as one big quadrant, since that is all it is, which means we can represent it with one CQuadTreeNode object!

// get width and height of screen somehow
CQuadTreeNode* entireScreen = new CQuadTreeNode(0, 0, screenWidth, screenHeight);

Alright!  We have created one quad tree node object that has its lower left corner at the origin and stretches the entire screen width and height.  


Windows users caveat: Beware that Windows thinks of the origin as the upper left corner of the screen, and positive y values indicate movement downwards from the top of the screen.  In my programs, I reverse this logic in my graphics class by making the origin the lower left of the screen and the graphics class hides from the rest of the program the detail of converting the more logical Cartesian coordinates into Windows drawing coordinates.

This quad tree node doesn't do us much good as it is because it represents the entire screen.  We need to subdivide it into 4 quadrants to start taking advantage of the quad tree's power.  Before we do that, let's understand what type of node this first quad tree node we created is.  Is it a leaf node or a branch node?

Well, since a leaf node has no children, and a branch node has children, this one is a leaf node.  When we call subdivide on it, since it is a leaf node without children, it will create four CQuadTreeNode's which will be its children, and it will automatically become a branch node.  Let's look at the first pass at the subdivide function:

HRESULT CQuadTreeNode::SubDivide()
{
   HRESULT result = S_OK;
   if (!m_SubNodes) {
      // We have no subnodes, so this must be
      // a leaf node.  Create 4 children nodes
      // which will be its children.
      // w is new width for subnodes
      // (half of current width), h similarly
      long w = m_Width / 2;
      long h = m_Height / 2;
      // shorter variable names for current lower x,y position
      long llx = m_LowerLeftX;
      long lly = m_LowerLeftY;

      // node 0: upper left quadrant
      // node 1: upper right quadrant
      // node 2: lower right quadrant
      // node 3: lower left quadrant
      // Since we have a pointer to a pointer for
      // our member variable, we need to allocate
      // memory for the 4 pointers that we are
      // creating.  Note CoTaskMemAlloc is a Windows
      // function, you can just use malloc in other
      // platforms.
      m_SubNodes = (CQuadTreeNode**)
         ::CoTaskMemAlloc(4 * sizeof(CQuadTreeNode*));
      // Now that we have room for the four pointers,
      // actually create the 4 CQuadTreeNode objects and
      // store them in our array.  We pass in the correct
      // values for the lower left points of each one,
      // and the width and height of them are all the
      // same (1/2 the width and height of this parent node).
      m_SubNodes[0] = new CQuadTreeNode(llx, lly + h, w, h);
      m_SubNodes[1] = new CQuadTreeNode(llx + w, lly + h, w, h);
      m_SubNodes[2] = new CQuadTreeNode(llx + w, lly, w, h);
      m_SubNodes[3] = new CQuadTreeNode(llx, lly, w, h);
   }
   else {
      // This node already has children, so it is a branch
      // node.  All we have to do is forward this call to
      // our sub nodes and tell them to subdivide.  If they
      // are leaf nodes, they will subdivide and create 4
      // children of their own, otherwise they will just do
      // what we do and tell their existing children to
      // subdivide.
      for (int i = 0; i < 4 && SUCCEEDED(result); i++) {
         result = m_SubNodes[i]->SubDivide();
      }
   }
   return result;
}

This function is at the heart of the quad tree class.  Let's call it in our code:
// get width and height of screen somehow
CQuadTreeNode* entireScreen = new CQuadTreeNode(0, 0, screenWidth, screenHeight);
// tell the quad tree node to subdivide itself.
entireScreen->SubDivide();

What we have after subdividing our only quad tree node (the "root" node, since it is at the root of the tree), is the root node plus 4 more quad tree nodes, which are the root node's children: