面向数据的树遍历没有递归

Question

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

在我的应用程序中,很多时候都花费遍历这个树并进行计算,如视图截顶剔除和矩阵乘法.目前,它是天真地实现的,其中每个节点具有子节点和网格的向量,并且递归地遍历树.这很慢.

我一直在关注面向数据的设计,我喜欢它对缓存非常友好的想法.我一直在想这样的事情:

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. 如何在不使用递归的情况下迭代树？除非我真的需要,否则我不想访问每个节点.例如,如果深度= 2的节点不可见,则不应测试其所有网格和子节点(及其网格),而是完全跳过.

Answer 1

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

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

std::vector<Node> nodes;

nextfield将下一个节点的索引保持在相同或更高的级别; 节点的第一个子节点没有明确说明,因为它是序列中当前节点之后的节点(除非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;
    }
}

通过保持显式堆栈,也可以将相同的代码转换为非递归(不确定为什么这将是一个好主意,除非节点操作和检查非常快或树太疯狂).