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

## Recommended Posts

mrheisenberg    362
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
JTippetts    12950
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
mrheisenberg    362
[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
lauris71    841
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.

##### Share on other sites
turch    590
You usually do a two step update, parent -> child to update transforms, and then child -> parent to update bounding volumes for culling.

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account