How do I traverse down my quad tree to get the bottom-most level nodes (3D, C++, DX11)

Question

I am creating a quad tree for my 3d terrain as I only need to worry about the Z and X axis and I'm having some trouble wrapping my head around how to actually traverse down once the tree is created.

I have created the tree and they are stored in my QuadTree object as QuadNode objects. Each QuadNode represents a 'Quad' of the quad tree. It takes the terrain and figures out whether it needs subdividing into new nodes until it finds the bottom-most level nodes and there is a sufficient amount of vertices per node.

I have stored a vertex/index buffer in each node object, but they only get populated once they reach the bottom-most nodes. So the buffers I am trying to obtain (to get the buffers to draw) are right at the bottom of the tree.

Now I can do this fairly simply with a basic tree that just has 4 nodes from the root, but as the tree gets bigger, I get confused. Here is an image to demonstrate

I store

• How many levels are in the quad tree (to perhaps help with searching, like traverse to level 6)
  • The total node count

The buffers are stored in the bottom-most nodes. Does anyone have an example function or pseudocode as how I would make a function to traverse down the tree given a specific level and it would give me the nodes for that level? Or is there a better approach?

Answer 1

Although it's not what I'm looking for, I've found this is how you traverse to the bottom nodes and seems to work nicely for what I want to do

How to iterating a Quad/Oct tree

void drawQuadtreeNodes()
{
    drawNode(quadtree->getRoot());
}

void drawNode(QuadNode * node)
{
    if (node->hasNodes) {
        drawNode(node->nodes[0]);
        drawNode(node->nodes[1]);
        drawNode(node->nodes[2]);
        drawNode(node->nodes[3]);
    }
    else {
        //bottom node
    }
}