How do I traverse a scene graph-like tree structure?

Question

I have a scene graph where I have:

class Node
{
public:

struct
{
    COLLISION_TYPE collisionType;

    void* boundingVolume;
}collisionData;

struct
{
    XMFLOAT3 position;
    XMFLOAT3 rotation;
}leafData;

Node(Model* representModel, Node* parentNode)
{
    this->parentNode = parentNode;
    this->representModel = representModel;

    this->collisionData.collisionType = representModel->collisionDataDefault.collisionType;
    this->collisionData.boundingVolume = &representModel->collisionDataDefault.boundingVolumeDefault;
};

~Node()
{

};

std::vector< std::vector<XMFLOAT3*> > GetChildTransformStream()
{

};

void Transform(XMMATRIX *world)
{

};

Model* representModel;

Node* parentNode;
std::vector<Node*> childNodes;
};

So in the method Transform I want to transform the coordinates of the node and those of all it's children,so I have to first get a list of all the children with GetChildTransformStream,but I don't know how to traverse it,since it can have any number of childnodes and they can have any number of childnodes and so on.How do you usually handle this?

Answer 1

One simple way to do a tree traversal is to use a stack. Push all children nodes on the stack, pop each child node, push it's children on the stack, process it, etc.

Edit: note that Chac's answer is just a special case of this. There, the stack that is used to store the traversal state is actually the function call stack.

Edit: source code outlining a typical tree traversal using a stack.

#include <vector>
#include <stack>
#include <iostream>

struct Node {
    std::vector<Node*> children;
    void Visit() const { std::cout << "Visited a node!\n"; }
};

void TraverseTree(Node* root) {
    std::stack<Node*> stack;
    stack.push(root);

    while (!stack.empty()) {
        Node* currentNode = stack.top();
        stack.pop();

        // push all children onto the stack:
        for (std::vector<Node*>::const_iterator i = currentNode->children.begin();
            i != currentNode->children.end();
            i++)
        {
            stack.push(*i);
        }

        // do any processing for this node here
        currentNode->Visit();
    }
}

int main(int argc, char** argv)
{
    Node a,b,c,d,e,f;
    a.children.push_back(&b);
    a.children.push_back(&c);
    b.children.push_back(&d);
    d.children.push_back(&e);
    d.children.push_back(&f);
    TraverseTree(&a);
}

Answer 2

an easy way is a recursive function:

void visit(Node *node) {
  // apply whatever needed to node
  for (int c = 0; c < node->childNodes.size(); ++c)
     visit(node->childNodes[c]);
}