gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

DS development > Non recursive Quadtree

#156742 - brett47 - Tue May 13, 2008 3:24 pm

I've been developing some 3d stuff on the DS, making use of quadtrees for partitioning the 3d world. However a 16kb stack isn't exactly a friendly match for recursive functions so I wanted to go for an non-recursive solution. However the algorithm to do so evades me as my brain gets lost trying to work out the solution. Here's my recursive function which is simple enough:

Code:
void RenderQuadtreeNode(CQuadtree* pNode)
{
    if (pNode == NULL) { return; }

    if (pNode->IsLeaf == true) {
        DrawNode();
    } else {
        CQuadtree **pSubNodes = pNode->GetSubNodes();
        RenderQuadtreeNode(pSubNodes[FRONTLEFT]);
        RenderQuadtreeNode(pSubNodes[FRONTRIGHT]);
        RenderQuadtreeNode(pSubNodes[BACKLEFT]);
        RenderQuadtreeNode(pSubNodes[BACKRIGHT]);
 }
}


Here's my effort so far, it really starts to get messier towards the end of the function at the point where you have to start thinking about coming back down the tree. Any suggestions?

Code:
void RenderQuadTree(CQuadtree* pNode) // Pass in root node
{
    int Level = 0;
    int CurrentChild[MaxLevels]; // Set these all to 0

    if (pNode == NULL) { return; }  // Process the root node
    CQuadtree **pSubNodes = pNode->GetSubNodes();
    pNode = pSubNodes[CurrentChild[Level]];
    Level = 1;

    while (Level > 0) {
        if (pNode->IsLeaf == false) {   // Get children and go up tree
            pSubNodes = pNode->GetSubNodes();
            pNode = pSubNodes[CurrentChild[Level]];
            Level++;
        } else {
            if (pNode != NULL) {    // The node has polygons to draw
                DrawNode();
            }
            // At this stage need to go across to next child
            Level--;
            CurrentChild[Level]++;
            if (CurrentChild[Level] > 3) {
                Level--;
                CurrentChild[Level]++;
            }
            Level++;
        }
    }
}

#156743 - Maxxie - Tue May 13, 2008 3:40 pm

There should be no problem in recursively walk the tree.

Your example code can be called several hundret recursive times before it exceeds the stacklimit.


As long as you avoid (as you did sucessfull) to declare unneeded vars in the recursive function (as for checking bounds, or DrawNode()) you shouldn't have any problems.


:edit: Beside that, you are in your non recursive function pushing a fairly big block onto the stack contraproductive to the goal of shrinking the stackusage. You could allways create an array on the heap rather then stack.

int CurrentChild[MaxLevels];
becomes
int CurrentChild[] = new int[MaxLevels];

and dont forget to delete at function exit.

#156747 - DekuTree64 - Tue May 13, 2008 5:24 pm

I don't quite understand the second function, but since the natural recursive version takes node pointers at each call, it would be easier to do a manual stack of node pointers:

Code:
void RenderQuadtreeNode(CQuadtree* pNode)
{
    int Level = 0;
    CQuadtree *Stack[MaxLevels];

    Stack[Level++] = pNode; // First iteration

    while(Level > 0)
    {
        CQuadtree *CurNode = Stack[--Level];

        if (CurNode == NULL) { continue; }

        if (CurNode->IsLeaf == true) {
            DrawNode(CurNode);
        } else {
            CQuadtree **pSubNodes = pNode->GetSubNodes();
            Stack[Level++] = pSubNodes[FRONTLEFT];
            Stack[Level++] = pSubNodes[FRONTRIGHT];
            Stack[Level++] = pSubNodes[BACKLEFT];
            Stack[Level++] = pSubNodes[BACKRIGHT];
        }
    }
}


As Maxxie says, you might need to allocate the stack on the heap. But maybe not, since now it's only 4 bytes per iteration, rather than needing the node pointer, return address, and any other register values that happened to be in use.

EDIT: On second thought, my stack might actually take more memory, since it's pushing on 4 nodes before going deeper. Could be condensed down slightly by having each entry store the pSubNodes double-pointer and an index into it. But since the stack is heapable now, it doesn't matter too much how big it is anyway.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku

#156826 - memoni - Wed May 14, 2008 9:05 am

There are stackless algorithms for traversing hierarchies too!
http://www.mpi-inf.mpg.de/~guenther/StacklessGPURT/index.html

I have used it for a stackless AABB tree traversal, I think it should work with quadtrees too.