Jump to content

  • Log In with Google      Sign In   
  • Create Account


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.

  • You cannot reply to this topic
4 replies to this topic

#1 mrheisenberg   Members   -  Reputation: 356

Like
0Likes
Like

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.

Sponsor:

#2 JTippetts   Moderators   -  Reputation: 8264

Like
2Likes
Like

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.

#3 mrheisenberg   Members   -  Reputation: 356

Like
0Likes
Like

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

#4 Lauris Kaplinski   Members   -  Reputation: 841

Like
2Likes
Like

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/

#5 turch   Members   -  Reputation: 590

Like
1Likes
Like

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.



PARTNERS