User:Sergey/DraftDependencyGraph

Dependency Graph

Draft This is a draft. Once the text and images are finalized the page will be moved to the official code documentation section.

This document covers all the design specifications of the dependency graph.

Introduction

Let’s start with making it really clear what the dependency graph is, what it is supposed to do and what it not supposed to do under any circumstances. The main goal of dependency graph is to make sure scene data is properly updated after any change in the most efficient way. This means the dependency graph only updates what was changed or was dependent on the modified value and will not update anything which was not changed. This way artists always have the scene in a relevant state with the maximum update frame rate possible. Dependency graph is doing that by preprocessing scene - creating graph where nodes are entities of the scene (for example, objects) and edges are relations between these objects (for example, when Object A has a parent Object B, the graph will have an edge between nodes which corresponds to these two objects).

Roughly speaking, the dependency graph is responsible for dynamic updates of the scene, where some value varies over time. It is not responsible for one-time changes. For example, the dependency graph is responsible for f-curves evaluation, but not for edge subdivide operation in mesh edit mode.

Overview

The top-level design overview is quite simple and is shown on the following picture.

• DNA data is directly delivered from .blend file
• Dependency graph applies all the required changes (modifiers, constraints, etc) on a copy of DNA data. Such data we call "evaluated".
• Dependency graph stores evaluation result on itself.
• Render engines are working with an evaluated data provided by the dependency graph and are never touching original DNA.
• Render engines have generalized and centralized API to store engine-specific data.

This allows to support features like dynamic overrides, having scene evaluated at different states.

Graph topology

As implies by the name, the dependency graph is a graph. Vertices in the graph are called Operation nodes, and Edges defines relations.

Operation node defines how the corresponding entity is to be evaluated. From a programming perspective it operation node is a function binding, which is involved whenever dependency graph needs to re-evaluate the entity.

Relations defines dependencies between entities. For example, if an MyObject is parented to an ParentObject then the MyObject's transform depends on ParentObject's transform. The relation edge in the graph goes from ParentObject's transform to MyObject's.

The operation nodes are granular, taking care of one specific aspect of evaluation: i.e. parent transform, constraint stack evaluation, modifier stack evaluation. This allows to have a complex inter-dependencies between objects without causing dependency cycles.

The operation modes are enclosed by Component nodes. Component node is a higher level concept. For example, component corresponds to object's Transform (parenting + local transform + constraint stack) or object's Geometry (modifier stack + geometry nodes). The component nodes is there to simplify construction of the dependency graph: it allows to define relation in terms "ObjectA's constraint stack depends on ObjectB's transform component". This way it is hidden how exactly the ObjectB's transform is calculated.

The component nodes are parenting by ID nodes. ID node corresponds to an ID from the main database. The ID nodes is what stores evaluated state of the corresponding ID in the graph.

Tagging for updates

Dependency graph reacts to update tags, and re-evaluates part of the graph which is affected by the changed entity. Consider a simple example of three objects: Suzanne, Cube, and Torus, where Suzanne is parented to Cube (illustrated in the picture below).

Simple object hierarchy

When Cube is moved, the position of Suzanne is to be updated accordingly. In this scenario Transform operator tags the Cube for TRANSFORM changes, and the dependency graph reacts to it by flushing tags to dependent entities, and evaluating tagged entities.

In the described scenario the dependency graph will flush transform tag from the Cube to Suzanne, and evaluate both Cube and Suzanne in the proper order. Since the Torus did not change and is not dependent on anything what changed the dependency graph does not re-evaluate.

It is important that tagging happens accordingly to the modification, and that no extra tagging is happening. The extra tagging does not affect validity of result, it only makes performance worse as it causes unnecessary evaluation. Using wrong tag will lead to a wrong evaluation result. It is up to a developer to ensure proper tag is used when data is changed.

Graph evaluation

Graph evaluation takes care of evaluating modified nodes. Evaluation consists of two distinct steps:

• Flushing of tags from directly tagged operations downstream via the relations.
• Multi-threaded execution of tagged operations.

The flushing process allows to simplify computations needed for proper scheduling, ensuring order of execution. Flushing is a straightforward process, with the only trick that if any operation node in a component is modified, the entire component is considered to be modified. This is more of an implementation details: most commonly only the component result is stored to minimize memory usage. For example, object's transform is stored as a final 4x4 matrix. This means that if constraint is changed, the object parenting is to be re-calculated.

Execution happens in a multi-threaded manner. First, all modified operations which all inputs are evaluated are scheduled for execution. If there are multiple of such operations all of them will start execution in parallel. Once operation is executed all children nodes are checked for availability of execution, and all children nodes which has all their dependencies evaluated are scheduled for evaluation.

Active dependency graph

Active dependency graph is the dependency graph which corresponds to a context which artist is currently interacting with. This is defined by active scene and view layer. On top of regular duties the active dependency graph will copy evaluated result to the original ID data-blocks. The active dependency graph is the only one which is allowed to do so. This makes it easier to implement tools and properly store/store state to a .blend file.

The active dependency graph (or graphs which potentially can become active by changing active scene/view layer) are owned by scene. Such dependency graphs are created on-demand and are stored in a hash in the Scene data-block.

Active dependency graph are evaluated as part of the application main loop.

Evaluated data and Copy-on-Write

Dependency graph stores evaluated data using same DNA structures as used for .blend file IO. This allows to re-use a lot of algorithms which needs to be agnostic to whether data is original or evaluated.

Allocation of DNA structures for the evaluated data is what is called Copy-on-Write. Dependency graph stores evaluated data in corresponding ID node. It is guaranteed that the evaluated data will be allocated prior to operation execution, but the exact moment when it happens is more of implementation detail (to transparently support features like lazy allocation, block de-duplication, and so on -- there are ideas and design drafts, but nothing concrete is put on code yet).

Debugging tools

To simplify development in the dependency graph area there is a "Dependency Graph Debug" add-on. It requires gnuplot and graphviz tools installed. Enabling this add-on beings a new panel in the View Layer Properties:

The Depsgraph as Image converts current active dependency graph to an image representation. The image is created as an image data-block, accessible from the Image Editor.

Note Keep the scene as simple as possible. Graph complexity grows quite quickly, making image hard to follow.

Error creating thumbnail: File with dimensions greater than 12.5 MP

Example of a dependency graph

There are certain semantic meaning of the relation line styling. Consider relation A -> B.

• Solid relation line meas that B depends on A and if A is changed the B is to be re-evaluated
• Dashed relation line means that B depends on A, but change of A does not imply re-evaluation of B.
• Dotted relation line means that depends on A and if A is changed the B is to be re-evaluated only if B was directly modified by user
• Blue relation line means that dependency cycle solver will not break the relation
• Red relation line means that the relation was removed in order to solve dependency cycle
• The square arrow implies that A is a Copy-on-Write operation, and that B depends on the Copy-on-Write operation, but modification of B` does not require synchronization of the evaluated ID with the original one.