vendredi 20 février 2015

Data-oriented tree traversal without recursion


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;



  1. How do I layout the nodes in memory? Is the root node 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.




Aucun commentaire:

Enregistrer un commentaire