c++ - 无递归的面向数据的树遍历

Question

我有一个这样的树结构:一个模型有一个根节点，每个节点有任意数量的子节点和任意数量的网格。

在我的应用程序中，很多时间都花在遍历这棵树并进行诸如视锥体剔除和矩阵乘法之类的计算上。目前，它是幼稚的实现，其中每个节点都有子节点和网格的 vector ，并且树是递归遍历的。这很慢。

我一直在研究面向数据的设计，我喜欢它对缓存非常友好的想法。我一直在想这样的事情:

struct Mesh
{
    // misc data
    MeshID mMeshID;
}

// probably needs more information?
struct Node
{
    // begin and end index into Models 'mNodes'
    uint32_t mChildrenBegin;
    uint32_t mChildrenEnd;

    // as above but for meshes
    uint32_t mMeshesBegin;
    uint32_t mMeshesEnd;
}

struct Model
{
    std::vector<Node> mNodes;
    std::vector<Mesh> mMeshes;
}

现在我需要遍历树以获取可见网格的列表。在每个节点上，我必须检查该节点是否可见。以下分支:

• 节点可见。它下面的所有子节点和网格也是可见的。不要深入这个分支。检查相同深度的其他节点。
• 节点不可见。此节点或其下方的子节点或网格不可见。不要深入这个分支。检查相同深度的其他节点。
• 节点部分可见。一些节点和/或一些网格是可见的。必须深入层次结构。

树是静态的。一旦模型被加载到应用程序中，树就永远不会改变。所以不知何故，我肯定能够使用这些信息来获得一个有效的结构。

我很困惑如何解决这个问题。

几个问题；

1. 如何在内存中布局节点？是第一个索引的根节点吗？其他节点是根据深度添加的吗？
2. 如何在不使用递归的情况下迭代树？我不想访问每个节点，除非我真的必须这样做。例如，如果 depth=2 的节点不可见，则不应测试其所有网格和子节点(及其网格)，而应完全跳过。

Answer 1

您可以将树表示为内存中深度优先遍历顺序的单个数组

struct Node {
    ... node data ...
    int next;
};

std::vector<Node> nodes;

next 字段保持下一个节点的索引在相同或更高级别；节点的第一个子节点没有明确说明，因为它是序列中当前节点之后的节点(除非 next 也指向它；在这种情况下，当前节点没有子节点)。 例如在树中:

红色箭头表示next 所指向的位置。

例如用于渲染的遍历变成:

void check(int ix) {
    switch(nodes[ix].visibility()) {
        case VISIBLE:
            // Draw whole subtree, no more checking needed
            for (int i=ix,e=nodes[ix].next; i!=e; i++) {
                nodes[i].draw();
            }
            break;
        case PARTIALLY_VISIBLE:
            nodes[ix].draw();
            for (int c=ix+1, e=nodes[ix].next; c!=e; c=nodes[c].next) {
                check(c);
            }
            break;
    }
}

同样的代码也可以通过保留一个显式堆栈来转换为非递归代码(不知道为什么这是一个好主意，除非节点操作和检查非常快或者树非常深)。