With Blender's animation system growing in complexity, the need for a good system to evaluate dependencies was badly needed. Until version 2.37, many issues with incorrect evaluation order were either hidden by calculating things twice, like armature deform, or evident by a lagging in animation and screen updates. Sometimes, animation did not update at all...
The correct way of handling such dependancies is a directed acyclic graph (DAG). This is a very common and well studied structure in graph theory which is well suited to this task. It can be viewed as an extension of the tree structure where branches are allowed to merge. DAG are often used for scheduling applications.
Once the DAG is built, it can be queried to show which object depends on another, and also to find an order of evaluation that respects all dependancies, as long as there is no cycles in them. As a secondary task, it can be used to check that a new relation will not induce cycles. We will see that these simple abilities provide quite versatile services.
For more in depth information, the full technical article by Jean-Luc Peurriere can still be found in our wiki.
Although DAG can be used in many areas in Blender, for now we will restrict our discussion to the signalling of Object updates by the animation system or other tools in Blender.
Relation types
Four basic relation types can be defined:
1) Object affects Object (OB_OB)
For example, Parenting of Objects, or certain Constraint relations.
2) Object affects Geometry (OB_DATA)
This can be a Hook moving Mesh vertices, or an Inverse Kinematics target Object changing an Armature.
3) Geometry affects Object (DATA_OB)
For example a curve Path, or a Vertex-parented Object
4) Geometry affects Geometry (DATA_DATA)
Curves, Lattices or Armatures deforming other Objects.
The pictures illustrate a case with all four relations used, and how the DAG diagram would look.
Scene Sort
The first use of the DAG is to presort the list of Objects in a scene in dependency order, assuring calculations for updates happen without lag. The goal is to only calculate each Object once, which means that cyclic dependencies are not correctly tackled yet. This is on our todo list.
<ccode>void DAG_scene_sort(Scene *);</ccode>
This call will also create a new DAG from scratch. Always call it on changing dependencies (like Parenting) or switching scenes.
Object tagging and flushing
To prevent object update calculations on each event or redraw, Objects can become tagged to indicate they need a refresh. Only two tags are needed now;
Object->recalc:
OB_RECALC_OB: object should re-evaluate its own matrices and own Ipos
OB_RECALC_DATA: object should rebuild its display of own geometry.
Using the DAG and the relation types, a simple recursive 'flush' through the graph then can update all associated Objects. The relation types then serve as a filter, defining whether 'recalc' tags have to be set, and whether such tags should switch to another type.
Example: in the pictures above, moving the IK-handle Object (OB_RECALC_OB) gets flushed to the Armature as an OB_RECALC_DATA tag, which in turn flushes that to the Cube as an OB_RECALC_OB again.
There are two ways in the code to use these tags;
<ccode>void DAG_object_flush_update(Scene *, Object *, int tag);</ccode>
Where 'tag' is either OB_RECALC_OB or OB_RECALC_DATA. This call sets the tag for the current Object. If there's data involved, it tags all objects using the same geometry, and then flushes the tags through the DAG.
This call is meant for single Object changes, like in Edit Mode or on using buttons in the UI.
The second method is to tag Objects yourself (set ob->recalc) and in the end call:
<ccode>void DAG_scene_flush_update(Scene *);</ccode>
Which flushes the changes through the DAG.
Actual Object update calculation
The DAG flushing doesn't do any actual Object updates, it just tags Objects as in need of recalculation. The actual calculation then happens in the beginning of the drawing function for 3d windows;
<ccode>for(base= G.scene->base.first; base; base= base->next) {
object_handle_update(base->object);
}</ccode>
The call object_handle_update() checks the recalc tag, does the appropriate actions on the object, and clears the tag. All Objects have to be evaluated here, as the pre-sorted evaluation order is relevant.
Layers
To prevent Object calculations from being done on invisible layers, but also to ensure that visible changes are done when related Objects are invisible, the DAG flush code also flushes using layer settings.
This flush goes backwards actually (from children to parents), making sure that parent relationships include layer information for all the children.
Layer flushing happens before the 'recalc' tag flushes, and results in recalc tags not being flushed or even being cleared.
Transform support
With the calls as described above in place, the transform() module in Blender can now simply tag the changing Objects, flush these tags, and rely on the system to do all updates nicely.
As an optimization, the transform code only flushes the tags once and stores them temporally, to be set on each redraw.
Animation support
On advancing to a new frame, the animation systems can also tag Objects with what changes should be executed. For example, Object Ipos, Vertex Keys, Softbodies, Actions, animated Constraints, and so on.
The call for this is:
<ccode>void DAG_scene_update_flags(Scene *);</ccode>
which sets the tags and flushes.
There's also a call that makes sure all animation systems get updated (including materials, sound, scripts). That's the call now used by the render code and in Blender on frame changes:
<ccode>scene_update_for_newframe(Scene *, unsigned int layer);</ccode>
This also calls the DAG_scene_update_flags() and immediately applies the changes with object_handle_update().
Armature support
The bones within an Armature have complex relationships as well, specifically when using Inverse Kinematics and Constraints. On changes in an Armature Pose, the order of Pose 'channels' (bone wrappers) is defined by constructing a DAG and using that to sort the channels. This way, it can be assured that each Pose Channel only has to be evaluated once on changes.
<ccode>DAG_pose_sort(Object *);</ccode>
Future usage
DAGs can be constructed to help with the efficient evaluation of other relationships in Blender. Two obvious candidates:
- Database relations
- Lighting/shading relations