Dependency graph proposal

This post is all about dependency graph design for the Blender 2.8 project.

Brief overview

Before going too much into technical details let’s first look into some top-level design overview about what’s this project is all about, what would that all mean for users and how it’ll affect on everyone working in 2.8 branch.

  • Dependency graph is owned by layer.
  • Dependency graph holds both relations AND evaluation data (aka state of the scene).
  • Dependency graph allows Render Engine to store its specific data in the evaluation context.
  • Dependency graph evaluation data is aware of copy-on-write and data de-duplication.
  • Dependency graph stays flexible to support data compression in the future.

Now let’s look into all the technical details, digging into what benefits each decision brings.

Ownership

Here and in the rest of the document layers will be referencing to the new layers which are being worked on by Dalai currently. Those will have almost nothing to do with the layers existing in Blender so far.

Each layer will have it’s own dependency graph which will contain both relations and scene state. This gives the following benefits:

  • Each layer gets dependency graph which is highly optimized for that particular use.
    There is no objects in the dependency graph which does not affect this particular layer, meaning there’s no way to have any possible overhead on depsgraph reconstruction and evaluation. In practice this would mean that modelling layer where artists adds new environment objects will not trigger all the character’s rigs dependencies update, keeping interaction as responsive as possible.
  • There is a clear separation in evaluation data (also known as scene state), so this is impossible to have threading conflicts between render and viewport threads.
  • This leads to really clear ownership model and makes it clear what is the time life of the evaluation data.

Ownership Diagram

In order to keep memory usage as low as possible, dependency graph and its evaluation context gets freed when layer becomes invisible.

Such approach does not allow to have same layer to be in multiple states in different windows (for example, it’s not possible to have layer at frame 16 in one window and at frame 32 in another window). But it is possible to set up your workflow in a way that does not require this. For example, you can have animation layer with only character you’re currently animating and show it in one window and have another preview layer which includes everything required for the preview (which could include more objects from environment or other character).

As a possible downside (or at least something to be aware of) in such model is that showing two different layers with same objects in different windows will slow down performance (objects would need to be update for both windows). This is probably possible to solve in the future with some smart de-duplication of evaluation.

Evaluation Data

Previously, scene state was fully decoupled from the dependency graph, which had advantages of simplicity. Now we need to store multiple states of the same scene. Dependency graph seems to be the most appropriate place for that.

Proposal is to store actual data in the ID nodes (or other “outer” node types). This will make it simple to map original objects to evaluated ones and vice versa (just to state the obvious: it’ll cover any datablock which dependency graph is keeping track of, including node trees, collections, …).
Evaluated data for objects includes applied:

  • Drivers
  • Animation
  • Overrides
  • Modifiers

All the render engines will only access evaluated objects and will treat them as fully final (no need from render-engine side to worry about overrides i.e.). This will happen via DEG_OBJECT_ITER() macro (with similar semantics to GHASH_ITER).

Tools will work on original scene data, using objects from active layer.

NOTE: Still not fully clear whether we’ll need to keep bmain in depsgraph or not (as some container of all evaluated objects). This is a topic for discussion.

The data flow here would be:

  • Original DNA is feeding to the input of the dependency graph.
  • Dependency graph copies that data, and runs all operations on this copied data.
  • Dependency graph stores this modified (or evaluated) data in the corresponding outer node (ID node).

Evaluation Data Flow

In order to make node-based everything to work we’ll need to extend this idea deeper and allow operation nodes to have copies of the original data as well. This could be nicely hidden behind the API calls to make such specific to be fully transparent for all related code such as modifiers.

NOTE: We would need to have some API to get final state of the object for modifiers anyway, so extending the scope where the data is stored is not that much of an affect on API.

Data stored in operation nodes gets freed once all users of that data are evaluated, which will ensure lowest possible memory footprint. This is possible for as long as we don’t allow other objects to be dependent on intermediate evaluation result (otherwise we wouldn’t be able to re-evaluate other objects after we dropped all intermediate data).

Interaction with Render Engine

Just to re-cap things which were mentioned above:

  • Render engine only deals with final evaluated objects
  • Render engine does not worry about overrides and consider that all data blocks it interacts with has overrides applied on them.

One thing which was not covered here yet is the requirement to store some renderer-specific data in objects. Example of such data could be VBOs for OpenGL renderer.

Easiest way to deal with this seems to be to allow render engines to store their specific data in the evaluated datablocks. This will grant persistency of this data across redraws for as long as objects do no change. Once object changes and gets re-evaluated it’s renderer-specific data gets freed and recreated by the render engine later on.

If needed, we can go more granular here and allow renderers to have per-evaluation-channel storage, so moving object around will not invalidate it’s VBOs.

Copy-on-write and de-duplication

The goal here is to minimize memory footprint of dependency graph storage by duplicating only data which is getting changed. Roughly speaking, when dependency graph creates local copy of the datablock for the evaluation data storage it only duplicates datablock, but keeps all CustomData referencing the original object’s CustomData. If some modifier changes any CustomData layer it gets decoupled from the original storage and being re-allocated. This is actually quite close to how CustomData currently works in the DerivedMesh.

More tricky scenario here is data de-duplication across multiple dependency graphs, which will help keeping memory usage low when multiple layers are visible and are on the same state.
Proposal here is to go the following route:

  • Have a global storage of evaluated objects, where dependency graph stores evaluation result of all outer nodes (objects, node trees, …)
  • Objects in this storage are reference-counted so we know when we can remove data from the storage.
  • Objects from this storage gets removed when they are tagged for update.
  • Dependency graph evaluation checks whether object at a given state exists in that storage and if so, references to it instead of doing full object evaluation.

This sounds a bit complicated, but it has the following advantages:

  • Data is still de-duplicated even when two visible layers shares some of the objects between each other .
  • Allows us to know exact time-life of evaluated objects.

Data compression

There are now multiple techniques to do run-time data compression, some of which are used by render engines. However, this is a bit too much to worry from the beginning and this should be well hidden behind API already. Generally speaking, nobody outside of dependency graph module should be even aware of something being compressed, it is all up to dependency graph to deliver final unpacked datablock when it is requested. For example, DEG_OBJECT_ITER() will unpack objects one by one and provide fully unpacked self-containing structure to the caller.

Overrides

Overrides are supposed to be used to do simple tweaks to the data, such as “replace material” or “transform this object by given transform”. They are not supposed to be used for anything more sophisticated, such as topology changes (so for that it’s expected to simple make object local).

There are two types of overrides:

  • Static overrides, which are applied by the reading code.
  • Dynamic overrides which are applied by the dependency graph.

Overrides only appliable on top of existing datablocks. This means, you can not define override of some duplicated object (for example, you can’t apply override on a paritcular instance of dupli-group).

Static overrides

The idea of static overrides is to basically generalize idea of the existing proxy system which is currently only supports armatures. This overrides basically works like this: reading code creates a local copy of the linked data. If there’s already such a local copy existing, it’ll synchronize all the changes made in the library to the local copy.

This overrides ONLY appliable on the linkable data (linkable across .blend files). This means, those have nothing to do with things like Collections.

Dynamic overrides

Dependency graph is taking care about dynamic overrides. From the implementation point of view, it is an operation node which applies all overrides to a copied version of the datablock prior to anything else evaluated for that datablock. Since dependency graph is taking care of copying datablock already (as was mentioned above) then override operation node simply applies all the overrides on the object from within current context (read as: override operation does not care about copying object).

Here’s a fragment of dependency graph showing nodes setup:

Example of overrides nodes

The following dynamic overrides are supported:

  • Replace value
    Example: change material color
  • Add to the list
    Example: Add new modifier to the object
  • Remove item from list
    Example: Remove constraints from the object

This overrides also applies to the Collections. This is because collections are not linkable across files at all, so static overrides makes no sense here.

Caches

Now when lower-level dependency graph topics are somewhat covered, let’s look into a bigger picture of caches and streaming data.
The requirement here is to be able to have a pipeline in which artists can bake the whole chunk of their scene and pass it to the next department. For example, when animators finish animating their 10 characters in the scene, they bake all of them and pass the cache to the lighting/rendering department. This way rendering artists can have real-time playback of the whole scene. Being realtime is always a good thing!

Other requirement here is to be able to easily investigate and verify how cache was done, where it came from, whether it’s up-to-date or not. This could be done automatically and/or manually.
One of the first questions is what is being “baked” to cache and what is still coming from a linked scene/asset. Surely, for the maximum performance everything should be baked (including meshes, materials, …) but that makes it really difficult to modify anything after the cache was done.

Currently we consider the following:

  • Final department might consider baking everything (to pass to render engine, or other software in the pipeline)
  • Usually artists are baking everything apart from materials.

As an implementation of cache we’ll rely on Alembic. It has nice time compression, flexible object-based inner storage design and supports (to certain extend) storage of non-geometry data which we can use for storing meta-data of the cache.

Just to state the obvious: cache-based pipeline is not something mandatory to use, the old-school linking of .blend files will still stay here (for small projects or some trivial cases in the big projects). Cache-based pipeline is only to speed up performance of shots in a really big scenes. Using caches for small projects is not beneficial anyway because artists will have overhead of maintaining cache to always be up-to-date.

Defining what is to be baked to cache

The proposal is to have a collection property which indicates that this collection generates the cache. Everything in this collection gets baked to cache (by default, all geometry excluding materials).
The cache will also contain some “meta-information” about where it came from – which scene, which collection and such. This way we can always go back from cache to the original file and re-bake it.

Crucial part of dealing with caches is to know whether cache is up to date or not. To help artists here cache will store a modification timestamp of the file it came from, so everyone in the pipeline can immediately see when cache runs out of date (Blender will show warning message or nice warning icon in the header of cache collection).

Still to be decided: in a BAM-pack pipeline where artists are only checking out files and assets required for a particular task, it’s possible that files used to generate particular cache are not a part of that BAM pack. How to check whether cache is up to date then?

Using the cache

When one adds a baked cache to the scene, it links as a collection. For this collection we can visualize what objects are in there (because Alembic cache has a notion of objects, so we can deduct internal structure of the cached scene). Of course, all the properties of that objects are grayed out because the data is considered linked.

Since cache knows where it came from, cached collection will have a button to switch from cached data to visualize real data from the corresponding file. This will re-load parts of the scene and ideally (if the cache is all up to date) artists will see same exact scene but will be able to interact with real Blender objects.

17 comments
  1. I am not really getting, why there should be any slow down with multiple “same” evaluations. A well designed DAG with data passing should only pass on seemingly immutable data.
    So what you would do (especially for cache coherence) is to have a linear memory space, where the actual data lives (immutably + Copy-on-Write-Semantics).
    Then when passing data between Nodes you only pass a reference to the data.
    You can then go ahead an hash the input + output for each Edge and have a separate cache, which returns the already evaluated result (there may be rare races where multiple would get evaluated but that should be minimal).
    Or am I missing something?

  2. Really interesting article!
    Just a little question for TDs side, is it planned to have an UI representation of this DAG ?

  3. Will this make possible the automatic saving of external assets such as painted (or other) texture files when the blend file is saved (as opposed to clicking “Image,” “Save” after Texture Paint)?

  4. Ok as a developer I have a little concern over the memory consumption of this proposal as well as cuda’s running out of memory in some the final rendering, how is this going to be addressed?

    Where I am looking is at the “Rendering Farm” type scenario where each of my machines do not actually have the same memory and or video cards?

    (When one of my machines gets a little long in the tooth I reconfigure the linux box and add it to my small farm.)

    • This doesn’t really have much to do with rendering at its core. The data that gets passed to a render engine is going to be (more or less) the exact same as the data passed today. Offline rendering will be very minimally affected by depsgraph changes.

  5. this is apparently an important topic to developers, but as artist i got no clue what this is about and how it in the end will impact my future work. This is not strictly cycles i understand, its about how blender should work. i’m unable to tell if this would make blender faster or better, and what particular workflows would be improved by it?, maybe show a video of how things will become or if its to theoretically coding, then well i trust you that in the end blender will become better.
    As overtime Blender has proven to become better and better.

  6. Say you have Rig A and Rig B, two bones (Bone A and Bone B) each parented to nothing. Currently, you can constrain Bone A of Rig A to Bone A of Rig B, but if you subsequently constrain Bone B of Rig B to Bone B of Rig A it causes a dependency cycle despite the each of the rigs having no internal parenting hierarchy.
    Will dynamic overrides solve this? In character animation we often come across situations where we’d like to “lock” free-floating bones back and forth across different rigs.

    • This should already be fixed in the new dependency graph. Try using Blender with `–enable-new-depsgraph` command line argument and see if your case is solved.

      P.S. This is nothing to do with overrides :)

  7. Superlativo!!

  8. sounds like old discussions about LP mud and how let artists diff between copy and instanzes
    ( i hope implemented with some algebra sugar and petri-net spice ;)
    -> to implement that penrose tesselation at end 8-]

  9. Much of this goes over the top of my head. But something inside tells me this is going to be awesome. ;).

    All the best and thank you .

  10. Hi,

    it’s not easy to keep up with such a low level explanation, so few questions :

    1. can the action system/NLA strips benefit from dynamic overrides to become a real “relative” animation layering system ? Or does this have nothing to do with it ?

    2. can this make linking x times one asset possible, each having own animation ? (character with armature)

    3. so changing assigned material is possible, but what about tweaking nodetree ? (not thinking necessarily about materials but rather about future object nodes)

    Thanks for the writeup

    Hadrien

    • > 1. can the action system/NLA strips benefit from dynamic overrides to become a real “relative” animation layering system ? Or does this have nothing to do with it ?

      There are various limitations and issues with current NLA implementation. Some of them might indeed be solved using overrides.

      > 2. can this make linking x times one asset possible, each having own animation ? (character with armature)

      Yes, that’s the idea. Even more, each of the characters could be customized by overrides, so you create varieties of characters in the same scene.

      > 3. so changing assigned material is possible, but what about tweaking nodetree ? (not thinking necessarily about materials but rather about future object nodes)

      You could change any existing property, including settings of the shader nodes. Don’t think we’ll ever support changing topology of the shader graph itself, it’ll be really hard to manage in the pipeline. So for more comprehensive changes just create local material and override the whole slot.

      • Thanks for the answer !

      • On the third point, I feel like making *some* changes to the nodetree possible would be really valuable. Lets say you have a car shader, and it takes an image texture to define a custom paint job (like flames coming over the hood, or the markings you might see on an emergency vehicle). You link in multiple instances of that shader, but you want to change the input image texture on a per-instance basis, rather than cloning the material a bunch of times, which would make maintenance hard. Maybe the settings *on* the nodes could be over ridden, but not the connections themselves?

        • Yes, if I understand correctly that is what Sergey meant (“You could change any existing property, including settings of the shader nodes”).

In order to prevent spam, comments are closed 15 days after the post is published.
Feel free to continue the conversation on the forums.