Как пройти по древовидной структуре в виде графа сцены?

У меня есть граф сцены, где у меня есть:

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, но я не знаю, как его пройти, поскольку он может иметь любое количество дочерних узлов, и они могут иметь любое количество дочерних узлов и т. д. Как вы обычно справляетесь с этим?

0

Решение

простой способ — это рекурсивная функция:

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

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector