0

我有一个场景图：

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;
};

所以在Transform方法中我想变换节点的坐标和它所有子节点的坐标，所以我必须首先用GetChildTransformStream获取所有子节点的列表，但我不知道如何遍历它，因为它可以有任意数量的子节点，它们可以有任意数量的子节点等等。你通常如何处理这个？

4

2 回答 2

1

一个简单的方法是递归函数：

void visit(Node *node) {
  // apply whatever needed to node
  for (int c = 0; c < node->childNodes.size(); ++c)
     visit(node->childNodes[c]);
}
于 2012-10-26T19:27:14.590 回答
1

进行树遍历的一种简单方法是使用堆栈。将所有子节点推入堆栈，弹出每个子节点，将其子节点推入堆栈，处理它等。

编辑：请注意，查克的回答只是这种情况的一个特例。在那里，用来存储遍历状态的栈其实就是函数调用栈。

编辑：源代码概述了使用堆栈的典型树遍历。

#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);
}
于 2012-10-26T19:18:52.387 回答