Cascading node::needUpdate() down to the leafs.

[Waruck]

I posted this 2 weeks ago in the 'papercuts' forum and I'm sorry to open a new thread on this but I don't thing it's a papercut anymore and I really want to get a feedback whether this is a good way to implement this, or whether it messes things up.

Also this statement has made me want to bring this up again for discussion:

In principle, the plan is to add back non-prefixed functions getWorldXXX that will always return the expected values, but so far this hasn't been investigated fully to find the proper way to implement those functions.

The idea is, that I want to cascade needUpdate() down to the leafs so that each node gets mNeedParentUpdate set to true when one of its parents above it moves and therfore can update its derived rotation/position when _getDerivedRotation()/Translation() is called.

My implementation:

Later Edit: version without extra flag, using mNeedParentUpdate as indication whether to cascade down or not.

In a call to Node::needUpdate() check mNeedParentUpdate and cascade the call down if needed:

Code: Select all

    void Node::needUpdate(bool forceParentUpdate)
    {

[b][u]      //mNeedParentUpdate = true; //don't set this here[/u][/b]
      mNeedChildUpdate = true;
      mCachedTransformOutOfDate = true;

      // Make sure we're not root and parent hasn't been notified before
      if (mParent && (!mParentNotified || forceParentUpdate))
      {
         mParent->requestUpdate(this, forceParentUpdate);
         mParentNotified = true ;
      }

[b][u]      //inform children that their combined transforms are out of date if they haven't been notified before
      if(!mNeedParentUpdate )
      {
         ChildNodeMap::iterator i, iend;
         iend = mChildren.end();
         for (i = mChildren.begin(); i != iend; ++i)
         {
            i->second->needUpdate(false);
         }
      mNeedParentUpdate = true ;
      }[/u][/b]

      // all children will be updated
      mChildrenToUpdate.clear();
   }

The problem I see here is that the children then will directly call requestUpdate on their parents but since mNeedChildUpdate is set to true this call will terminate immediately.

And in _update() don't cascade this to its children with parentHasChanged = true, since the children will now know whether they need to update from their parent or not. Maybe i would now remove this parameter completly but this would definetly mess things up with other classes.

Code: Select all

        void Node::_update(bool updateChildren, bool parentHasChanged)
        {
          // always clear information about parent notification
          mParentNotified = false;

          // See if we should process everyone
          if (mNeedParentUpdate || parentHasChanged)
          {
             // Update transforms from parent
             _updateFromParent();
          }

          if(updateChildren)
          {
             if (mNeedChildUpdate || parentHasChanged)
             {
                ChildNodeMap::iterator it, itend;
                itend = mChildren.end();
                for (it = mChildren.begin(); it != itend; ++it)
                {
                   Node* child = it->second;
[b][u]                   child->_update(true, false);                  //no longer call this with parentHasChanged = true, children are notified when parent moves.[/u][/b]
                }
             }
             else
             {
                // Just update selected children
                ChildUpdateSet::iterator it, itend;
                itend = mChildrenToUpdate.end();
                for(it = mChildrenToUpdate.begin(); it != itend; ++it)
                {
                   Node* child = *it;
                   child->_update(true, false);
                }

             }

             mChildrenToUpdate.clear();
             mNeedChildUpdate = false;
          }
       }

For performance I think this should be no problem, since needUpdate() only sets 3 bools, clears one vector and calls requestUpdate() to the parent which is immediately terminated. Thus cascading it down to the leafs shouldn't really hurt performance even in big scenes with deep node-trees since it is only cascaded once after each update.
The actual transforms are calculated anyway in the next call to _update(), the only thing changed is that it is now possible to prepone this if _getDerivedOrientation()/Position() is called in which case it is no longer calculated in _updated() unless a parent moves again after the calculation.

[CABAListic]

Did you find an actual bug in Ogre's rendering related to this, or is this about getting the world positions/orientations for your own use?

[Waruck]

This is for own use. When _update() is called in the render-loop derived rotations/positions are calculated for a node on that needUpdate() has been called (mNeedParentUpdate == true) and all its children (_update(true, parentHasChanged = true) ).

with this code the calculation of derived rotations/positions can be preponed in user-code if _getDerivedXXX() is called before ogre calls the actual _update()

[Eugene]

with this code the calculation of derived rotations/positions can be preponed in user-code if _getDerivedXXX() is called before ogre calls the actual _update()

In such situation I just call sceneManager->getRootSceneNode()->_update(true, false); and all what I needs is updated, and moreover, would not be updated second time during rendering. Why do you need something more?

[CABAListic]

I'm not sure this is the way to go, then. Ogre's scene updates are already slow and been marked for a major overhaul for 2.0, so adding additional overhead is at least a sensitive matter.

If instead we added getWorldXXX functions to be used by end users instead of _getDerivedXXX, would it significantly hurt your use case if they had to check their parents each time?

[Waruck]

The problem about adding extra functions would be, that they don't stop ogre from calculating the new transforms itself. if the user calls getWorldXXX it would need to recalculate the transforms if necessary and ogre would also calculate them in the next internal update.

my goal is that the transforms are only updated once, either by the user call to _getDerivedXXX or in Ogre's internal update, but not twice.

calling sceneManager->getRootSceneNode()->_update(true, false) would stop ogre from updating the transforms itself, but as CABAListic said it would be a big overload, because in user-code you would only want the positions to be updated, thus calling UpdateFromParent() for each node that needs it is my goal, which is achived by cascading NeedUpdate() and setting mNeedParentUpdate=true. But calling UpdateFromParent() manually currently doesn't solve this problem either, since _update(true, true) is called for each child of a node that has moved, thus it is forced to update its transforms (by the 2nd bool).

[AgentC]

I would recommend a complete overhaul of the world transform update, *both* for being able to easily get up-to-date world transforms, and for simpler code and better performance. You should only need one dirty flag.

- When any of local pos, rot, scale is changed, and dirty flag is not already set, set the dirty flag, and recursively set the dirty flag on children.
- When world transform is asked with getWorld...() function, check the dirty flag.
* If it is set, build new cached world transform. Ask parent for its world transform and multiply by it (if you're not root yourself). This will recursively drive dirty parents to update their transforms in turn. Clear the dirty flag.
* If not set, you're up to date, simply return the cached world transform.

Done this way, the explicit update step would no longer be needed for transform updates at all.

[Waruck]

this is exactly what my code does !

the dirty-flag is the bool mNeedParentUpdate, that is set in NeedUpdate(), but currently not cascaded down to the children.
mNeedParentUpdate is checked in _getDerivedXXX() and the transforms are updated if necessary. NeedUpdate() is called in each rotation/scale/translation to set this flag. The only problem is that it is not cascaded downwards.


but now that I think about it you can use this also as an indicator in NeedUpdate() to cascade it or not, what i currently do with mChildrenInformed. The only benefit of using a new flag is that nodes without children will never have to try to inform their children again, whereas mNeedParentUpdate is set to false for child-less nodes and therfore they'll again try to inform their children

[Eugene]

- When any of local pos, rot, scale is changed, and dirty flag is not already set, set the dirty flag, and recursively set the dirty flag on children.
Done this way, the explicit update step would no longer be needed for transform updates at all.

Initially I thought that complexity of invalidation for significant percent of moved/animated/etc nodes that cascades to the children would be O(N^2), but than realized that early exit for already invalidated nodes would keep complexity at O(N) level - the same as now. And lazy transform calculation makes it unnecessary to keep the lists of invalidated children so that very wide and shallow scene tree can be updated efficiently - that is good. But what about bounding boxes for scene nodes hierarchies?

[CABAListic]

My problem with this approach is that with any data-oriented redesign for 2.0 the update must work completely top-down, so any such solution must break with the redesign. There is no avoiding that as far as I understand data-oriented design (all dirty flags would be thrown away in the process, too). I don't think it is a good idea to introduce now a behaviour change that we cannot keep up in future versions.

There are really only two long-term solutions I see: Either require the user to update the whole scene graph manually before accessing world positions, or use a separate function that always works its way bottom-up and recalculates the world transform for the requested node. These solutions are not mutually exclusive, of course.

[AgentC]

Yes, bounding boxes are indeed trickier as they would need to cascade to parents, and also involve the attached drawable objects. I'm not completely sure though if updating a bounding box hierarchy is even useful; I'd rather be interested only of the individual drawable objects' bounds. In my own engine (component-based scene graph) drawable objects can opt to listen to their owner nodes' dirty notifications, and consequently dirty their own world bounding boxes. These are similarly updated on demand when queried, but there's no concept of a scene node's bounding box at all.

Certainly a proper data-driven multithreaded transform/bounding box update step will own lazy-update mechanisms, in cache coherency if not elsewhere. And at least for reasonable object counts. But can it easily optimize when a) most of the world is stationary b) most of the world's objects are not in view?

[CABAListic]

Certainly a proper data-driven multithreaded transform/bounding box update step will own lazy-update mechanisms, in cache coherency if not elsewhere. And at least for reasonable object counts. But can it easily optimize when a) most of the world is stationary b) most of the world's objects are not in view?

Actually, it's supposed to speed up things particularly for large scenes. For small to reasonable sizes performance bottlenecks don't matter so much, after all. As far as optimisations go, I'd say it depends on the way you implement it. Given that you still have to deal with a hierarchical structure, you will have to make some compromises in your data layout. For example, different hierarchy levels of the scene graph could go in different data blocks, which could allow for a single dirty flag per level of depth of the scene graph. And manipulating invisible nodes may not have to set those dirty flags at all.

I'm still unclear on an exact design and also probably not the most knowledgable person about DOD to come up with one. So take it with a grain of salt. Either way, the one thing I've learned from reading about DOD is to be careful with dirty flags and early outs and if in doubt, trust the profiler, not your instincts.

[xavier]

trust the profiler

QFT

[Waruck]

But what about bounding boxes for scene nodes hierarchies?

Bounding Boxes are updated in a call to SceneNode::_update(). I don't want to call this function outside of ogre's own loop at all. When _getDerivedXXX() is called and the dirty-flag is set, _updateFromParent() is cascaded upwarts until a node is not dirty, but this function only calculates the new transfroms and does nothing else. no other function is called.

My problem with this approach is that with any data-oriented redesign for 2.0 the update must work completely top-down, so any such solution must break with the redesign.

What the current update process of the scene-graph does:
- update is called on the root and cascaded down to each children that either requested an update itself or to all children if a parent-node has been moved.
- derived transforms are calculated befor updating the children for all nodes that have the dirty-flag (mNeedParentUpdate) set, or on wich _update() is called with ParentHasMoved = true (top to bottom)
- for all nodes that update has been called on, regardless of flags, bounding boxes are calcluated after updating all children. (bottom to top)

I don't see how one can change the update process of bounding boxes top to bottom, since they need to be merged with the bounding boxes of children, which need to be up-to-date. Also I don't want to change the update process itself, only the dirty-flag which controlls the update of derived transforms should be cascaded and checked outside of the update process to make it possible to manually calculate the new transforms before ogre does and make ogre to not calculate them again.

There is no avoiding that as far as I understand data-oriented design (all dirty flags would be thrown away in the process, too).

Do you mean that the update will recalculate the transforms without checking for the dirty-flag? That would be quite inefficient.

There are really only two long-term solutions I see: Either require the user to update the whole scene graph manually before accessing world positions, or use a separate function that always works its way bottom-up and recalculates the world transform for the requested node. These solutions are not mutually exclusive, of course.

updating the Scene Graph in its current state invokes the problem that bounding-boxes are calculated regardless of dirty-flags, thus if you update manually and move a node afterwards (since most time you want to get the world transform to move something...) you'll make the whole branch calculate its bounding-boxes twice.
recalculating the transform of the requested node leaves the problem, that it doesn't stop ogre from recalculating the transform itself.
So both of these solution would make some things unnecessarily calculated twice which I don't thing fits for a long-term solution.

[CABAListic]

I don't see how one can change the update process of bounding boxes top to bottom, since they need to be merged with the bounding boxes of children, which need to be up-to-date. Also I don't want to change the update process itself, only the dirty-flag which controlls the update of derived transforms should be cascaded and checked outside of the update process to make it possible to manually calculate the new transforms before ogre does and make ogre to not calculate them again.

Another part of DOD is to separate different tasks into different actions. As a consequence, updating world transforms and bounding boxes would be come two entirely separate things. First you'd update world transforms top to bottom for all nodes, then update bounding boxes bottom up for all nodes.

Do you mean that the update will recalculate the transforms without checking for the dirty-flag? That would be quite inefficient.

The point is that often the cost of doing the check for the dirty flag costs you more than just doing the update. Of course, if that's not true, you will want to do early out, but it's very likely that in a relatively flat scene graph a check per node would do more harm than good. As I said, we'll want to find a compromise between both approaches.

[Waruck]

Ok, I can agree that most nodes on that _update() is called will need to have their transform updated so it might be more efficient to ignore the flag and calculate the transform anyway. Checking a flag 100 times to early-out 1 update might not be worth the effort.
But as of 1.8 the flag is there and checked and we still have some time to go befor 2.0 (and 1.9) and i think if the flag is checked it makes sense to cascade it down to the leafs.