# How do I avoid hundreds of identical scene graph traversals?

This topic is 1908 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello,I made a scene graph that contains a root node and each node contains a std::vector<Node*> children; so it's a basic tree structure that I use to organize my scene.Now the problem is,each node contains coordinates(XMFLOAT3 position,rotation,scale) and each node's coordinates are relative to it's parent's coordinates.So when I need to create a world/transform matrix from the node's coordinates,I have to take into account it's parent's(Node* parent ) coordinates,for which I have to take into account the parent's parent and so on until I reach the root node.So if I have an object with 200 children linked to it,I have to traverse all the way down to the root 200 times and that doesn't sound right.Is there some commonly accepted method of dealing with this problem?I really like the whole ''relative coordiantes'' functionality and I'm not willing to give it up just yet,I just need to find a good way to optimize away the repetative traversals.

##### Share on other sites
Instead of each node pulling from its parent (which in turn pulls from its parent), push instead. Calculate the root node's transforms first, then push them out to all children, who will calculate their transforms and push to their children in turn.

##### Share on other sites
[quote name='JTippetts' timestamp='1351464335' post='4994853']
Instead of each node pulling from its parent (which in turn pulls from its parent), push instead. Calculate the root node's transforms first, then push them out to all children, who will calculate their transforms and push to their children in turn.
[/quote]

oh yeah,that makes sense,I can maybe do a frustum cull first and set frustum flags on each node,so then I'll only push the transforms to those who have a VISIBLE flag,to save performance

##### Share on other sites
You cannot do frustum culling without knowing the world positions of your children. Unless you cache wold-space bounding boxes or transform frustum during tree traversal.

I think it usually makes sense to cache both world transforms and bounding boxes in each nodes, update these once after each mutation and reuse whenever you need.