Dev:Source/Data System/Dependency Graph/Overview

Dependency Graph

The dependency graph is a part of Blender that is mostly invisible to users, but it is required to make constraints, modifiers and drivers work well, especially in more complex setups. What these features have in common is that they create dependencies between objects and armature bones.

An Example

We might have a scene with a tube mesh object, that is being deformed by an armature, which in turn is parented to a plane and uses an empty as an inverse kinematics target.

Looking at the dependencies, we can see that the armature bones must be evaluated first to reach the IK target, before we can deform the tube mesh with them.

If we consider all such relations in a scene, we get a dependency graph, where objects depend on other objects through dependency relations. This is much like a node setup for compositing or materials, except that it isn't as visible.

More precisely, the dependency graph is used to answer the following questions: In which order should objects and bones be evaluated? Which object should be (re-)evaluated when opening a file, editing some object, or changing the current frame? Which caches are invalidated by editing an object?

Order of Evaluation

Ordering is done for the list of objects in the file, and for the list of bones in an armature. When we update the scene, the objects will be evaluated one after the other, with the order ensuring that objects are evaluated when other objects use them.

The ordering of objects for evaluation is quite simple once we have the graph available, algorithms for this are this are well known in graph theory. The main issue here is that we might need to resolve cyclic dependencies, which make a correct ordering of objects impossible, for more details on that see the section on dependency cycles. Assuming there are no cycles, we have what is called a directed acyclic graph.

Propagating Updates

The other task of the dependency graph is propagating updates. When an object or other datablock in Blender changes, it is tagged to be updated. For example if we edit the vertices of a mesh, its modifiers need to be re-evaluated, so we tag the mesh datablock as needing an update. Such update tags are set when executing an operator, editing a property in the user interface, or editing data through python.

Where the dependency graph comes in, is when there are other objects depending on the data that we just modified. If we edited a mesh datablock that is used by multiple objects, all those objects need to be updated. If we edit an object location that other objects use in their constraints, those other objects need to be updated as well. To handle such cases, we use the dependency graph to propagate the update tag to all objects that depend on the edited object.

Another case to consider, is when objects are on hidden layers. Even if they are not directly visible, they might still affect objects on visible layers. In such cases, again the dependency graph is used to find out which objects need to be evaluated to correctly evaluate all objects that are visible.

Dependency Cycles

Users mostly do not need to know about the dependency graph, until they run into dependency cycles or loops. This happens when object A depends on object B, but B also depends on A. More indirect cycles are also possible. Such setups can't be evaluated correctly, because we don't know which of the two objects to evaluate first, there is no well defined solution.

Blender resolves such cycles by removing relations. In the viewport this will manifest itself as delayed updates: when changing frames or transforming, other objects may not follow immediately. In the console a warning will be printed, along with the relations that created the cycle.

Phantom Cycles

Sometimes it happens that a setup that you'd expect to work still generates a dependency cycle. These are an artifact of the implementation of Blender, which has limitations that could (mostly) be resolved with a refactoring of the system.

An example of such a phantom cycle is when we have an empty and a mesh object. The empty has the mesh as its parent, while the mesh uses the empty as object offset in the array modifier.

There's clearly a cycle here, as both objects depend on each other, but it could have worked correctly if we considered the object transformation and the object mesh separately. If we first evaluated the transformation of the mesh object, then the transformation of the emtpy object, and then the mesh modifiers, it would work. However, in the current implementation we evaluate an object in its entirety and then move on to the next, so this is a cycle.

Putting it all Together

For a high level overview of how the dependency graph fits into the broader system, we can consider a few stages.

First the dependency graph needs to be built. This happens on file load and each time new relations are added or removed. Then datablocks get tagged for update: on file load all objects visible in 3d viewports are tagged, on frame change all objects with animation data, and on editing an object that object is tagged. Next, we need to propagate those update flags to other objects, based on dependencies. And lastly, we evaluate tagged objects, in the order specified by the dependency graph.

Propagation of updates and evaluation of objects is done as part of the main loop, before Blender redraws the user interface. Rendering and changing frames may also cause updates, as well as a call to the function scene.update() in python.

We do this update only after all operators have run and properties have been changed, and this is important. If we were writing a python script, and on each little modification the entire scene would be re-evaluated, it would be a major performance problem.

Viewing Dependencies

There is currently no editor in Blender for visualizing and editing relations, but it might be added in the future. In Blender 2.61, there is a Dependency Relations operator, found through operator search, that can be used to print information about the dependency graph to the console.

Improving the System

The dependency graph currently handles the most common dependency relations, but the code could use a redesign to better integrate features that have been added since it was originally implemented. It also needs to be extended to cover more areas of blender, to solve missing updates and useful relations between datablocks that are not working currently. Further, it needs to be refined to avoid phantom cycles in common cases.

Partially this requires deeper changes to the way Blender updates and evaluates data, but on the dependency graph side, we could make these changes:

More datablocks: not only objects, but any datablock could be in the dependency graph. Now that drivers can be created on nearly any property on any datablock, this is required to support correct ordering of evaluation. Additionally, propagation of update tags is also required in other cases, for example when a node group is used by multiple materials, so it would make sense to handle such cases as well.

Finer granularity: by representing datablocks as consisting of smaller parts that can be evaluated separately, some phantom cycles can be avoided. An example of this would be pose bones in an armature, where you might have dependencies that go out to another object and come back to another bone. Another example of a case where finer granularity would be useful is particle systems, which we try to update independently from objects, but which the dependency graph design didn't really foresee.

Editor integration: for objects evaluation is centralized, but for example evaluating compositing nodes, the sequencer, or material preview icons are not. This makes it fuzzy what needs to be evaluated and who schedules this, leading to missed refreshes. A solution maybe to let editors tell the dependency graph which datablocks they expect to be evaluated, and leaving the scheduling to a centralized component.

Relations across time: features such as slow parent and dupliframes require other objects to be evaluated at a different time, but they have never worked reliably. For slow parent this means evaluating the parent one or more frames back in time, but for that to work fully as expected, also other objects that the parent depends on would need to evaluated at this time. It should be noted though that this problem of relations across time is mostly situated elsewhere, and the dependency graph itself can't solve this.