如何遍历场景图形树状结构？

我有一个场景图，我有：如何遍历场景图形树状结构？

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

所以在变换方法我要变换的节点的坐标和那些所有它的孩子，所以我必须先得到所有列表有GetChildTransformStream的孩子，但我不知道如何遍历它，因为它可以有任意数量的子节点，并且它们可以有任意数量的子节点等等。你通常如何处理这个问题？

来源

2012-10-26 user1777994

通过深度优先搜索或广度优先搜索。如果它实际上是一个图表，则保存访问的节点列表。你有什么尝试？ – OmnipotentEntity

我试过循环._。 – user1777994

我以为有一些普遍接受的处理场景图的方法，所以我就这么问了xD – user1777994

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

编辑：请注意，Chac的回答只是一个特例。在那里，用于存储遍历状态的堆栈实际上是函数调用堆栈。

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

#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-26 19:18:52 WeirdlyCheezy

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

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

来源

2012-10-26 19:27:14 CapelliC

如何遍历场景图形树状结构？

回答

相关问题