BSP avoid recursion

From CGAFaq

A BSP tree resembles a standard binary tree structure in many ways. Using the tree for a painter's algorithm or for ray tracing is a "depth first" traversal of the tree structure. Depth first traversal is traditionally presented as a recursive operation, but can also be performed using an explicit stack.

Implementation Notes

Depth first traversal is a means of enumerating all of the leaves of a tree in sorted order. This is accomplished by visiting each child of each node in a recursive manner as follows:

void    Enumerate (BSP_tree *tree)
{
  if (tree->front)
    Enumerate (tree->front);
  if (tree->back)
    Enumerate (tree->back);
}

To eliminate the recursion, you have to explicitly model the recursion using a stack. Using a stack of pointers to BSP_tree, you can perform the enumeration like this:

void    Enumerate (BSP_tree *tree)
{
  Stack  stack;
  while (tree)
  {
    if (tree->back)
      stack.Push (tree->back);
    if (tree->front)
      stack.Push (tree->front);
    tree = stack.Pop ();
  }
}

On some processors, using a stack will be faster than the recursive method. This is especially true if the recursive routine has a lot of local variables. However, the recursive approach is usually easier to understand and debug, as well as requiring less code.

Initial content for this page from the BSP tree FAQ, included with permission of its maintainer, Bretton Wade.