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.
Alot of 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 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. Dont 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. Dont 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;
- How do I layout the nodes in memory? Is the root node the first index? Are the other nodes added based on depth?
- 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.
Best How To :
Short version: Use 6502's pre-order answer instead. I'll leave my previous answer below because it still has some interesting code and comments.
Lay out your storage array in a semi-pre-order fashion. That is: sentinel end node, roots, first root's children, first root's first child's children, first root's first grandchild's children, and so on. Then traverse the tree using a recursive semi-pre-order traversal that keeps copies of the index information of direct ancestors and their siblings on the stack. This way, your traversal will scan the storage array from left to right with no backtracking. You don't need to visit all nodes with recursion and any skipping over subtrees that you do will only jump your scan forward in the storage array.
model.semiPreOrderTraversalRecur(model.getEnd()); // traverse the whole tree
...
// NOTE: pass prnt by *COPY* -- break Node into index portion and app. data portion; we only need the index portions here
void Model::semiPreOrderTraversalRecur(Node prnt)
{
Node children[prnt.mChildrenEnd - prnt.mChildrenBegin]; // just index info
uint32_t i;
// visit children of prnt; determine visibility etc.
for (i = prnt.mChildrenBegin; i < prnt.mChildrenEnd; ++i)
{
cout << "Visiting " << mNodes[i].mVal << endl;
mNodes[i].mInvisible = false; // TODO: determine based on culling, etc.
children[i - prnt.mChildrenBegin] = mNodes[i]; // just index info
}
// recurse on children as necessary
for (i = 0; i < prnt.mChildrenEnd - prnt.mChildrenBegin; ++i)
if (!children[i].mInvisible && children[i].mChildrenBegin != children[i].mChildrenEnd)
semiPreOrderTraversalRecur(children[i]);
}
Long version (some of this is obviated): I think you can achieve what you want by adding just a bit more information to your Node structure: the index of a Node's parent and the index of the current Node. (The latter may not be strictly necessary as it can probably be derived from a pointer to the Node and the Node storage vector.)
That should give you enough contextual information to easily move "up", "down" or "sideways" to a sibling as you desire given any Node in the tree. To move "up," you simply go to the parent index. To move down, you go to any one of the child indexes. To move "sideways" to a sibling you simply increase/decrease the current Node's index (after checking that you aren't your parent's last/first child).
You might want to consider combining your Node and Mesh structures so that you can store them contiguously in one vector. Cache performance that is good for the goose is typically good for the gander. With your Mesh's stored off in another vector, they are likely far away in memory from their Node siblings and accessing them mid-traversal will put more pressure on the cache. Of course, if your Mesh's have much more data than your Node's (or vice versa), or you don't need to visit Mesh's during a traversal, then this might not be a good option as it will waste memory. Also, your Mesh's likely don't need all the tree indexes since they are terminal nodes and can be special cased when you visit a Node's children. Depending on the particulars, your original proposal for storing Mesh's separately may be superior.
In the code below, I combine your Node and Mesh structures and store them in a single vector.
#include <cstdint>
#include <iostream>
#include <vector>
#include <string>
#include <chrono>
#include <thread>
using namespace std;
struct Node
{
uint32_t mParentIndex; // index of parent Node in Model
uint32_t mIndex; // index of this Node in Model (may be possible to derive this from Node pointer and Model's vector rather than storing it)
uint32_t mChildrenBegin; // begin and end index of children Node in Model
uint32_t mChildrenEnd;
bool mInvisible; // used during semiPreOrderTraversal to remember no need to traverse subtree rooted at this Node
int mVal; // dummy data for debugging
};
struct Model
{
vector<Node> mNodes; // preferably private, but your call
Model(istream *in = NULL);
Node *getEnd(void) { return &mNodes[0]; } // sentinel end node that always exists and has itself as parent
Node *getRoot(void) { return getChild(getEnd()); }
Node *getParent(Node *curr) { return &mNodes[curr->mParentIndex]; } // always safe to call; returns end as sentinel
Node *getNextSibling(Node *curr) { Node *prnt = getParent(curr); return (curr->mIndex && curr->mIndex + 1 < prnt->mChildrenEnd ? &mNodes[curr->mIndex + 1] : NULL); }
Node *getPrevSibling(Node *curr) { Node *prnt = getParent(curr); return (curr->mIndex > prnt->mChildrenBegin ? &mNodes[curr->mIndex - 1] : NULL); }
Node *getChild(Node *curr, unsigned nth_child = 0) { unsigned index = curr->mChildrenBegin + nth_child; return (index < curr->mChildrenEnd ? &mNodes[index] : NULL); }
void semiPreOrderTraversal(void);
void semiPreOrderTraversalRecur(Node prnt);
private:
int buildFromStreamRecur(Node *curr, int val, istream &in);
};
void Model::semiPreOrderTraversal(void)
{
Node *curr = getRoot();
Node *next;
cout << "Beginning Semi-Pre-Order traversal of tree!" << endl;
if (NULL == curr)
goto DONE;
while (1)
{
// TODO: visit curr; determine and record mInvisible in curr
cout << "Visiting " << curr->mVal << endl;
curr->mInvisible = false;
// try to move to sibling
if (NULL == (next = getNextSibling(curr)))
{
// try to move to children of siblings
curr = getChild(getParent(curr)); // move back to oldest sibling
cout << "No more siblings to visit! Try to visit their children. Rewinding to oldest sibling " << curr->mVal << endl;
while (curr->mInvisible || NULL == (next = getChild(curr)))
{
cout << "No children to visit of " << curr->mVal << endl;
// shouldn't visit curr's children or it has no children
// try to move to sibling
if (NULL == (next = getNextSibling(curr)))
{
cout << "Reached end of siblings again -> completed traversal of subtree rooted by parent " << getParent(curr)->mVal << endl;
// ascend while we can't find a uncle to check for children to visit
do {
if (getEnd() == (curr = getParent(curr)))
goto DONE; // got back to end -> traversal complete
cout << "Moved back up to " << curr->mVal << endl;
} while (NULL == (next = getNextSibling(curr)));
cout << "Found a great^Nth uncle (" << next->mVal << ") to check for children to visit!" << endl;
}
// else check sibling for children to visit
curr = next;
cout << "Trying to visit children of " << curr->mVal << endl;
}
// visit children of curr
cout << "Will visit children of " << curr->mVal << endl;
}
else
cout << "Will visit sibling of " << curr->mVal << endl;
curr = next;
}
DONE:
cout << "Finished Semi-Pre-Order traversal of tree!" << endl;
}
void Model::semiPreOrderTraversalRecur(Node prnt)
{
Node children[prnt.mChildrenEnd - prnt.mChildrenBegin]; // just index info
uint32_t i;
// visit children of prnt; determine visibility etc.
for (i = prnt.mChildrenBegin; i < prnt.mChildrenEnd; ++i)
{
cout << "Visiting " << mNodes[i].mVal << endl;
mNodes[i].mInvisible = false;
children[i - prnt.mChildrenBegin] = mNodes[i]; // just index info
}
// recurse on children as necessary
for (i = 0; i < prnt.mChildrenEnd - prnt.mChildrenBegin; ++i)
if (!children[i].mInvisible && children[i].mChildrenBegin != children[i].mChildrenEnd)
semiPreOrderTraversalRecur(children[i]);
}
Model::Model(istream *in)
{
Node dmy, *end;
mNodes.push_back(dmy); // create sentinel end node
end = getEnd();
end->mParentIndex = 0;
end->mIndex = 0;
end->mChildrenBegin = 1;
end->mChildrenEnd = 1;
end->mVal = -1;
if (in)
buildFromStreamRecur(getEnd(), 0, *in);
}
int Model::buildFromStreamRecur(Node *curr, int val, istream &in)
{
uint32_t numChildren, i, currInd = curr->mIndex;
// read in how many children curr will have
in >> numChildren;
// allocate children in mNodes and set curr's children references
// NOTE: protect against reallocations of mNodes
curr->mChildrenBegin = mNodes.size();
for (i = 0; i < numChildren; ++i)
{
Node node;
node.mParentIndex = currInd;
node.mIndex = mNodes.size();
node.mChildrenBegin = (uint32_t) -1;
node.mChildrenEnd = (uint32_t) -1;
node.mVal = val++;
mNodes.push_back(node);
}
curr = &mNodes[currInd];
curr->mChildrenEnd = mNodes.size();
cout << "Node " << curr->mVal << " is complete! mParentIndex = " << curr->mParentIndex << "; mIndex = " << curr->mIndex
<< "; mChildrenBegin = " << curr->mChildrenBegin << "; mChildrenEnd = " << curr->mChildrenEnd << endl;
// recursively build children
// NOTE: protect against reallocations of mNodes
for (i = 0; i < numChildren; ++i)
{
curr = &mNodes[currInd];
curr = &mNodes[curr->mChildrenBegin + i];
val = buildFromStreamRecur(curr, val, in);
}
return val;
}
int main(int argc, char **argv)
{
Model m(&cin);
m.semiPreOrderTraversal();
m.semiPreOrderTraversalRecur(*m.getEnd());
return 0;
}
A non-recursive, pre-order traversal of the entire tree would look something like this:
Node *curr = model.getRoot(); // TODO: handle empty tree
Node *next;
bool shouldnt_visit_children;
while (1)
{
// TODO: visit curr -- determine shouldnt_visit_children
if (shouldnt_visit_children || NULL == (next = model.getChild(curr)))
{
// move to next sibling; if no siblings remain then ascend while no siblings remain
while (NULL == (next = model.getNextSibling(curr)))
if (model.getEnd() == (curr = model.getParent(curr)))
goto DONE;
curr = next;
}
else
curr = next; // descend to first child
}
DONE:;
All that being said, I don't see any blazingly obvious reasons why this kind of implementation (as opposed to a linked structure like you had previously) is likely to have MUCH better cache performance. How the vectors get laid out and how you access them is what will drive your cache performance. Regardless, I don't see any compelling reasons why laying it out in any particular fashion you can't likely achieve a similar result building a linked tree similarly. For example, if you find/believe that laying out your vectors in a semi-pre-order kind of tree traversal (i.e. - the vector is laid out like: end, root, root's children, root's first child's children, root's first grandchild's children, etc.) gives optimal cache performance for your application, then it is highly likely that building a linked tree using the same semi-pre-order build order will yield similar results as your memory allocator is likely to pack your tree in memory in a similar manner as you would do explicitly. Of course, with your approach you can control this with certainty, rather than depending on your structures and associated allocators being intelligent.
Explicitly managing the layout of your Node's and Mesh's in memory may yield you some better cache performance as you can "force" it to tightly pack your objects in memory and enforce the kind of access pattern / locality you prefer -- but a decent allocator will likely achieve a similar result, particularly if the tree building is only done once at start up.
If you mostly do pre-order traversals as your questions seem to suggest, then I'd recommend laying out your storage vector in a semi-pre-order fashion, like I above described: end, root, root's children, root's first child's children, root's first grandchild's children and so on.
PS - If your traversals always start from the root, then you can eliminate the mParentIndex in Node too and instead build an explicit stack of ancestors as you walk the tree to allow you to traverse back up the tree after you descend (this is likely what the recursion did implicitly). If you need to be able to move around the tree from any random given Node, then you need to store your parent's index in the Node.
EDIT: As I mentioned in one of my comments, the semi-pre-order layout I proposed also has the property that all the descendant Mesh's of a Node can be represented in a simple numeric range [Node.mDescedantMeshBegin, Node.mDescendantMeshEnd) when you store the Mesh's separately as your proposed. So, if you need or want to build an explicit list of visible Mesh's by traversing the tree, then whenever you find a visible Node you can easily incorporate this entire range of visible descendant Mesh's into your list very easily.
EDIT2: I updated the code significantly. I added a recursive Model builder based on a semi-pre-order input stream. I fixed some bugs. Most importantly, I added a function that does a non-recursive, semi-pre-order traversal of a Model. It's not nearly as simple as a true pre-order traversal, but it may interest you. A recursive version might be much simpler -- I'll think about adding that. In my testing, the visitation of Nodes proceeds very nicely from left to right in mNodes. However, memory accesses sometimes go backwards in the storage array when we ascend back up the tree. I believe these backwards references could be removed by maintaining an explicit array of copies of ancestors (at least their index information) on the stack during a traversal. Functionality of calls like getParent() and getNextSibling() would have to be rewritten to use this array rather than jumping around in the storage vector itself, but it could be done. Then your memory accesses of mNodes will only slide from left to right, which is probably near to optimal for cache performance (assuming your tree is shallow enough that your ancestors on the stack will always be in the cache and not create undue cache pressure).
EDIT3: I added a recursive semi-pre-order traversal and it is trivial compared to the iterative version. It is also ridiculously easy to pass copies of the index portions of your Nodes to keep on the stack so that when your recursion unrolls you don't actually go back and access earlier parts of your storage array again. Instead you just look at what's on the stack, which will almost certainly be in the cache -- assuming your trees aren't super deep+wide. You do need to store copies of all the children at a given level. It's not enough to store just your direct ancestors, you also have to store their siblings. With this code and laying out your storage vector in a semi-pre-order, all your memory accesses in a traversal will scan from left to right over your storage array with no backtracking. I think you'll have near optimal cache performance. I don't see how it could get much better.
Sample input.txt: each number represents how many children the implicit current node has in pre-order fashion. In the below, the sentinel end node only has 1 child, a singular root (the code supports multiple roots if you want), the root has 5 children, the first child of the root has 0 children, the second child of the root has 2 children and so on. I used spacing to indicate the tree structure to the eye, but it's not necessary for the program itself.
1
5
0
2
7
0
0
0
1
0
0
0
0
2
1
0
0
1
0
4
1
0
2
1
0
1
0
0
0
0
Sample output:
john-schultzs-macbook-pro:~ jschultz$ clear; ./a.out < input.txt
Node -1 is complete! mParentIndex = 0; mIndex = 0; mChildrenBegin = 1; mChildrenEnd = 2
Node 0 is complete! mParentIndex = 0; mIndex = 1; mChildrenBegin = 2; mChildrenEnd = 7
Node 1 is complete! mParentIndex = 1; mIndex = 2; mChildrenBegin = 7; mChildrenEnd = 7
Node 2 is complete! mParentIndex = 1; mIndex = 3; mChildrenBegin = 7; mChildrenEnd = 9
Node 6 is complete! mParentIndex = 3; mIndex = 7; mChildrenBegin = 9; mChildrenEnd = 16
Node 8 is complete! mParentIndex = 7; mIndex = 9; mChildrenBegin = 16; mChildrenEnd = 16
Node 9 is complete! mParentIndex = 7; mIndex = 10; mChildrenBegin = 16; mChildrenEnd = 16
Node 10 is complete! mParentIndex = 7; mIndex = 11; mChildrenBegin = 16; mChildrenEnd = 16
Node 11 is complete! mParentIndex = 7; mIndex = 12; mChildrenBegin = 16; mChildrenEnd = 17
Node 15 is complete! mParentIndex = 12; mIndex = 16; mChildrenBegin = 17; mChildrenEnd = 17
Node 12 is complete! mParentIndex = 7; mIndex = 13; mChildrenBegin = 17; mChildrenEnd = 17
Node 13 is complete! mParentIndex = 7; mIndex = 14; mChildrenBegin = 17; mChildrenEnd = 17
Node 14 is complete! mParentIndex = 7; mIndex = 15; mChildrenBegin = 17; mChildrenEnd = 17
Node 7 is complete! mParentIndex = 3; mIndex = 8; mChildrenBegin = 17; mChildrenEnd = 19
Node 16 is complete! mParentIndex = 8; mIndex = 17; mChildrenBegin = 19; mChildrenEnd = 20
Node 18 is complete! mParentIndex = 17; mIndex = 19; mChildrenBegin = 20; mChildrenEnd = 20
Node 17 is complete! mParentIndex = 8; mIndex = 18; mChildrenBegin = 20; mChildrenEnd = 20
Node 3 is complete! mParentIndex = 1; mIndex = 4; mChildrenBegin = 20; mChildrenEnd = 21
Node 19 is complete! mParentIndex = 4; mIndex = 20; mChildrenBegin = 21; mChildrenEnd = 21
Node 4 is complete! mParentIndex = 1; mIndex = 5; mChildrenBegin = 21; mChildrenEnd = 25
Node 20 is complete! mParentIndex = 5; mIndex = 21; mChildrenBegin = 25; mChildrenEnd = 26
Node 24 is complete! mParentIndex = 21; mIndex = 25; mChildrenBegin = 26; mChildrenEnd = 26
Node 21 is complete! mParentIndex = 5; mIndex = 22; mChildrenBegin = 26; mChildrenEnd = 28
Node 25 is complete! mParentIndex = 22; mIndex = 26; mChildrenBegin = 28; mChildrenEnd = 29
Node 27 is complete! mParentIndex = 26; mIndex = 28; mChildrenBegin = 29; mChildrenEnd = 29
Node 26 is complete! mParentIndex = 22; mIndex = 27; mChildrenBegin = 29; mChildrenEnd = 30
Node 28 is complete! mParentIndex = 27; mIndex = 29; mChildrenBegin = 30; mChildrenEnd = 30
Node 22 is complete! mParentIndex = 5; mIndex = 23; mChildrenBegin = 30; mChildrenEnd = 30
Node 23 is complete! mParentIndex = 5; mIndex = 24; mChildrenBegin = 30; mChildrenEnd = 30
Node 5 is complete! mParentIndex = 1; mIndex = 6; mChildrenBegin = 30; mChildrenEnd = 30
Beginning Semi-Pre-Order traversal of tree!
Visiting 0
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 0
Will visit children of 0
Visiting 1
Will visit sibling of 1
Visiting 2
Will visit sibling of 2
Visiting 3
Will visit sibling of 3
Visiting 4
Will visit sibling of 4
Visiting 5
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 1
No children to visit of 1
Trying to visit children of 2
Will visit children of 2
Visiting 6
Will visit sibling of 6
Visiting 7
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 6
Will visit children of 6
Visiting 8
Will visit sibling of 8
Visiting 9
Will visit sibling of 9
Visiting 10
Will visit sibling of 10
Visiting 11
Will visit sibling of 11
Visiting 12
Will visit sibling of 12
Visiting 13
Will visit sibling of 13
Visiting 14
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 8
No children to visit of 8
Trying to visit children of 9
No children to visit of 9
Trying to visit children of 10
No children to visit of 10
Trying to visit children of 11
Will visit children of 11
Visiting 15
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 15
No children to visit of 15
Reached end of siblings again -> completed traversal of tree rooted by parent 11
Moved back up to 11
Found a great^Nth uncle (12) to check for children to visit!
Trying to visit children of 12
No children to visit of 12
Trying to visit children of 13
No children to visit of 13
Trying to visit children of 14
No children to visit of 14
Reached end of siblings again -> completed traversal of tree rooted by parent 6
Moved back up to 6
Found a great^Nth uncle (7) to check for children to visit!
Trying to visit children of 7
Will visit children of 7
Visiting 16
Will visit sibling of 16
Visiting 17
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 16
Will visit children of 16
Visiting 18
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 18
No children to visit of 18
Reached end of siblings again -> completed traversal of tree rooted by parent 16
Moved back up to 16
Found a great^Nth uncle (17) to check for children to visit!
Trying to visit children of 17
No children to visit of 17
Reached end of siblings again -> completed traversal of tree rooted by parent 7
Moved back up to 7
Moved back up to 2
Found a great^Nth uncle (3) to check for children to visit!
Trying to visit children of 3
Will visit children of 3
Visiting 19
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 19
No children to visit of 19
Reached end of siblings again -> completed traversal of tree rooted by parent 3
Moved back up to 3
Found a great^Nth uncle (4) to check for children to visit!
Trying to visit children of 4
Will visit children of 4
Visiting 20
Will visit sibling of 20
Visiting 21
Will visit sibling of 21
Visiting 22
Will visit sibling of 22
Visiting 23
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 20
Will visit children of 20
Visiting 24
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 24
No children to visit of 24
Reached end of siblings again -> completed traversal of tree rooted by parent 20
Moved back up to 20
Found a great^Nth uncle (21) to check for children to visit!
Trying to visit children of 21
Will visit children of 21
Visiting 25
Will visit sibling of 25
Visiting 26
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 25
Will visit children of 25
Visiting 27
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 27
No children to visit of 27
Reached end of siblings again -> completed traversal of tree rooted by parent 25
Moved back up to 25
Found a great^Nth uncle (26) to check for children to visit!
Trying to visit children of 26
Will visit children of 26
Visiting 28
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 28
No children to visit of 28
Reached end of siblings again -> completed traversal of tree rooted by parent 26
Moved back up to 26
Moved back up to 21
Found a great^Nth uncle (22) to check for children to visit!
Trying to visit children of 22
No children to visit of 22
Trying to visit children of 23
No children to visit of 23
Reached end of siblings again -> completed traversal of tree rooted by parent 4
Moved back up to 4
Found a great^Nth uncle (5) to check for children to visit!
Trying to visit children of 5
No children to visit of 5
Reached end of siblings again -> completed traversal of tree rooted by parent 0
Moved back up to 0
Finished Semi-Pre-Order traversal of tree!
