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

ツリー トラバーサルを行う簡単な方法の 1 つは、スタックを使用することです。すべての子ノードをスタックにプッシュし、各子ノードをポップし、その子ノードをスタックにプッシュし、処理します。

編集：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-26T19:18:52.387 に答える