View more

View more

View more

Image of the Day Submit

IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

How do I avoid hundreds of identical scene graph traversals?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

4 replies to this topic

#1mrheisenberg  Members

Posted 28 October 2012 - 04:15 PM

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.

#2JTippetts  Moderators

Posted 28 October 2012 - 04:45 PM

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.

#3mrheisenberg  Members

Posted 28 October 2012 - 05:04 PM

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.

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

#4Lauris Kaplinski  Members

Posted 29 October 2012 - 06:15 AM

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.
Lauris Kaplinski

First technology demo of my game Shinya is out: http://lauris.kaplinski.com/shinya
Khayyam 3D - a freeware poser and scene builder application: http://khayyam.kaplinski.com/

#5turch  Members

Posted 29 October 2012 - 07:26 AM

You usually do a two step update, parent -> child to update transforms, and then child -> parent to update bounding volumes for culling.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.