Как пройти по древовидной структуре в виде графа сцены?
У меня есть граф сцены, где у меня есть:
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, но я не знаю, как его пройти, поскольку он может иметь любое количество дочерних узлов, и они могут иметь любое количество дочерних узлов и т. д. Как вы обычно справляетесь с этим?
Решение
простой способ — это рекурсивная функция:
void visit(Node *node) {
// apply whatever needed to node
for (int c = 0; c < node->childNodes.size(); ++c)
visit(node->childNodes[c]);
}
Другие решения
Один простой способ сделать обход дерева — это использовать стек. Поместите все дочерние узлы в стек, вставьте каждый дочерний узел, поместите его дочерние узлы в стек, обработайте его и т. Д.
Редактировать: обратите внимание, что ответ Чака является лишь частным случаем этого. Там стек, используемый для хранения состояния обхода, фактически является стеком вызовов функций.
Редактировать: исходный код, описывающий типичный обход дерева с использованием стека.
#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);
}