Data-oriented tree traversal without recursion

Question

I have a tree structure like this: a Model has a root Node and each Node has any number of child Nodes and also any number of Meshes.

A lot of the time in my application is spent traversing this tree and doing computations like view frustrum culling and doing matrix multiplications. Currently, it is naively implemented, where each Node has vectors of child Nodes and Meshes, and the tree is recursively traversed. This is very slow.

I've been looking at the data-oriented design and I like the idea of it being very cache friendly. I've been thinking of something like this:

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;
}

Now I need to traverse the tree to get a list of visible meshes. At each node, I must check if the node is visible. The following branches:

• The node is visible. All child nodes and meshes below it are visible too. Don't go deeper into this branch. Check other nodes at the same depth.
• The node is not visible. No child nodes or meshes at this node or below it will be visible. Don't go deeper into this branch. Check other nodes at the same depth.
• The node is partially visible. Some nodes and/or some meshes are visible. Must go deeper into hierarchy.

The tree is static. Once a model is loaded in the application, the tree never changes. So somehow surely I must be able to use this information to get an efficient structure.

I'm puzzled how to approach this though.

A couple of questions;

1. How do I layout the nodes in memory? Is the root node of the first index? Are the other nodes added based on depth?
2. How do I iterate the tree without using recursion? I don't want to visit each node unless I really have to. For example, if a node at depth=2 is not visible, all its meshes and children (and their meshes) should not be tested, but skipped completely.

Answer 1

You could represent the tree as a single array in memory in depth-first traversal order

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

std::vector<Node> nodes;

next field keeps the index of the next node at same or higher level; the first children of a node is not explicitly stated as it's the node following the current node in the sequence (unless next is also pointing to it; in that case the current node has no children). For example in the tree:

the red arrows represent where next is pointing to.

The traversing for example for rendering becomes:

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;
    }
}

The same code can also be converted to non-recursive by keeping an explicit stack (not sure why that would be a good idea unless the node operation and checking is extremely fast or the tree is insanely deep).