Depsgraph: New dependency graph integration commit
authorSergey Sharybin <sergey.vfx@gmail.com>
Tue, 12 May 2015 10:05:57 +0000 (15:05 +0500)
committerSergey Sharybin <sergey.vfx@gmail.com>
Tue, 12 May 2015 11:06:37 +0000 (16:06 +0500)
This commit integrates the work done so far on the new dependency graph system,
where goal was to replace legacy depsgraph with the new one, supporting loads of
neat features like:

- More granular dependency relation nature, which solves issues with fake cycles
  in the dependencies.

- Move towards all-animatable, by better integration of drivers into the system.

- Lay down some basis for upcoming copy-on-write, overrides and so on.

The new system is living side-by-side with the previous one and disabled by
default, so nothing will become suddenly broken. The way to enable new depsgraph
is to pass `--new-depsgraph` command line argument.

It's a bit early to consider the system production-ready, there are some TODOs
and issues were discovered during the merge period, they'll be addressed ASAP.
But it's important to merge, because it's the only way to attract artists to
really start testing this system.

There are number of assorted documents related on the design of the new system:

* http://wiki.blender.org/index.php/User:Aligorith/GSoC2013_Depsgraph#Design_Documents
* http://wiki.blender.org/index.php/User:Nazg-gul/DependencyGraph

There are also some user-related information online:

* http://code.blender.org/2015/02/blender-dependency-graph-branch-for-users/
* http://code.blender.org/2015/03/more-dependency-graph-tricks/

Kudos to everyone who was involved into the project:

- Joshua "Aligorith" Leung -- design specification, initial code
- Lukas "lukas_t" Toenne -- integrating code into blender, with further fixes
- Sergey "Sergey" "Sharybin" -- some mocking around, trying to wrap up the
  project and so
- Bassam "slikdigit" Kurdali -- stressing the new system, reporting all the
  issues and recording/writing documentation.
- Everyone else who i forgot to mention here :)

133 files changed:
CMakeLists.txt
build_files/cmake/macros.cmake
build_files/scons/tools/Blender.py
build_files/scons/tools/btools.py
source/blender/CMakeLists.txt
source/blender/SConscript
source/blender/blenkernel/BKE_depsgraph.h
source/blender/blenkernel/BKE_modifier.h
source/blender/blenkernel/CMakeLists.txt
source/blender/blenkernel/SConscript
source/blender/blenkernel/intern/action.c
source/blender/blenkernel/intern/armature_update.c
source/blender/blenkernel/intern/depsgraph.c
source/blender/blenkernel/intern/library.c
source/blender/blenkernel/intern/mesh.c
source/blender/blenkernel/intern/object_update.c
source/blender/blenkernel/intern/scene.c
source/blender/blenloader/intern/readfile.c
source/blender/depsgraph/CMakeLists.txt [new file with mode: 0644]
source/blender/depsgraph/DEG_depsgraph.h [new file with mode: 0644]
source/blender/depsgraph/DEG_depsgraph_build.h [new file with mode: 0644]
source/blender/depsgraph/DEG_depsgraph_debug.h [new file with mode: 0644]
source/blender/depsgraph/DEG_depsgraph_query.h [new file with mode: 0644]
source/blender/depsgraph/SConscript [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph.cc [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph.h [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph_build.cc [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph_build.h [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph_build_nodes.cc [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph_build_relations.cc [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph_debug.cc [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph_debug.h [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph_eval.cc [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph_intern.h [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph_query.cc [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph_queue.cc [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph_queue.h [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph_tag.cc [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph_type_defines.cc [new file with mode: 0644]
source/blender/depsgraph/intern/depsgraph_types.h [new file with mode: 0644]
source/blender/depsgraph/intern/depsnode.cc [new file with mode: 0644]
source/blender/depsgraph/intern/depsnode.h [new file with mode: 0644]
source/blender/depsgraph/intern/depsnode_component.cc [new file with mode: 0644]
source/blender/depsgraph/intern/depsnode_component.h [new file with mode: 0644]
source/blender/depsgraph/intern/depsnode_opcodes.h [new file with mode: 0644]
source/blender/depsgraph/intern/depsnode_operation.cc [new file with mode: 0644]
source/blender/depsgraph/intern/depsnode_operation.h [new file with mode: 0644]
source/blender/depsgraph/util/depsgraph_util_cycle.cc [new file with mode: 0644]
source/blender/depsgraph/util/depsgraph_util_cycle.h [new file with mode: 0644]
source/blender/depsgraph/util/depsgraph_util_function.h [new file with mode: 0644]
source/blender/depsgraph/util/depsgraph_util_hash.h [new file with mode: 0644]
source/blender/depsgraph/util/depsgraph_util_map.h [new file with mode: 0644]
source/blender/depsgraph/util/depsgraph_util_pchanmap.cc [new file with mode: 0644]
source/blender/depsgraph/util/depsgraph_util_pchanmap.h [new file with mode: 0644]
source/blender/depsgraph/util/depsgraph_util_set.h [new file with mode: 0644]
source/blender/depsgraph/util/depsgraph_util_transitive.cc [new file with mode: 0644]
source/blender/depsgraph/util/depsgraph_util_transitive.h [new file with mode: 0644]
source/blender/editors/space_view3d/CMakeLists.txt
source/blender/editors/space_view3d/SConscript
source/blender/editors/space_view3d/space_view3d.c
source/blender/editors/transform/CMakeLists.txt
source/blender/editors/transform/SConscript
source/blender/editors/transform/transform_conversions.c
source/blender/makesdna/DNA_scene_types.h
source/blender/makesrna/SConscript
source/blender/makesrna/intern/CMakeLists.txt
source/blender/makesrna/intern/SConscript
source/blender/makesrna/intern/makesrna.c
source/blender/makesrna/intern/rna_depsgraph.c [new file with mode: 0644]
source/blender/makesrna/intern/rna_internal.h
source/blender/makesrna/intern/rna_object_api.c
source/blender/makesrna/intern/rna_scene.c
source/blender/modifiers/CMakeLists.txt
source/blender/modifiers/SConscript
source/blender/modifiers/intern/MOD_armature.c
source/blender/modifiers/intern/MOD_array.c
source/blender/modifiers/intern/MOD_bevel.c
source/blender/modifiers/intern/MOD_boolean.c
source/blender/modifiers/intern/MOD_build.c
source/blender/modifiers/intern/MOD_cast.c
source/blender/modifiers/intern/MOD_cloth.c
source/blender/modifiers/intern/MOD_collision.c
source/blender/modifiers/intern/MOD_correctivesmooth.c
source/blender/modifiers/intern/MOD_curve.c
source/blender/modifiers/intern/MOD_datatransfer.c
source/blender/modifiers/intern/MOD_decimate.c
source/blender/modifiers/intern/MOD_displace.c
source/blender/modifiers/intern/MOD_dynamicpaint.c
source/blender/modifiers/intern/MOD_edgesplit.c
source/blender/modifiers/intern/MOD_explode.c
source/blender/modifiers/intern/MOD_fluidsim.c
source/blender/modifiers/intern/MOD_hook.c
source/blender/modifiers/intern/MOD_laplaciandeform.c
source/blender/modifiers/intern/MOD_laplaciansmooth.c
source/blender/modifiers/intern/MOD_lattice.c
source/blender/modifiers/intern/MOD_mask.c
source/blender/modifiers/intern/MOD_meshcache.c
source/blender/modifiers/intern/MOD_meshdeform.c
source/blender/modifiers/intern/MOD_mirror.c
source/blender/modifiers/intern/MOD_multires.c
source/blender/modifiers/intern/MOD_none.c
source/blender/modifiers/intern/MOD_normal_edit.c
source/blender/modifiers/intern/MOD_ocean.c
source/blender/modifiers/intern/MOD_particleinstance.c
source/blender/modifiers/intern/MOD_particlesystem.c
source/blender/modifiers/intern/MOD_remesh.c
source/blender/modifiers/intern/MOD_screw.c
source/blender/modifiers/intern/MOD_shapekey.c
source/blender/modifiers/intern/MOD_shrinkwrap.c
source/blender/modifiers/intern/MOD_simpledeform.c
source/blender/modifiers/intern/MOD_skin.c
source/blender/modifiers/intern/MOD_smoke.c
source/blender/modifiers/intern/MOD_smooth.c
source/blender/modifiers/intern/MOD_softbody.c
source/blender/modifiers/intern/MOD_solidify.c
source/blender/modifiers/intern/MOD_subsurf.c
source/blender/modifiers/intern/MOD_surface.c
source/blender/modifiers/intern/MOD_triangulate.c
source/blender/modifiers/intern/MOD_util.h
source/blender/modifiers/intern/MOD_uvproject.c
source/blender/modifiers/intern/MOD_uvwarp.c
source/blender/modifiers/intern/MOD_warp.c
source/blender/modifiers/intern/MOD_wave.c
source/blender/modifiers/intern/MOD_weightvgedit.c
source/blender/modifiers/intern/MOD_weightvgmix.c
source/blender/modifiers/intern/MOD_weightvgproximity.c
source/blender/modifiers/intern/MOD_wireframe.c
source/blender/render/CMakeLists.txt
source/blender/render/SConscript
source/blender/render/intern/source/pipeline.c
source/blenderplayer/CMakeLists.txt
source/creator/CMakeLists.txt
source/creator/creator.c

index ae2c67b59bfbff1ff97bda1c49771ca23a78c6b9..a8b32b4dc0f5230cc715461495db0d44d1b0b085 100644 (file)
@@ -449,6 +449,9 @@ endif()
 option(WITH_CPP11 "Build with C++11 standard enabled, for development use only!" OFF)
 mark_as_advanced(WITH_CPP11)
 
+# Dependency graph
+option(WITH_LEGACY_DEPSGRAPH "Build Blender with legacy dependency graph" ON)
+
 # avoid using again
 option_defaults_clear()
 
index 8b2f3f18215a9169e34314bbd2a29f3ffd2f44d3..7de2b25f32128df439122d25b2ae80fce59fea20 100644 (file)
@@ -524,6 +524,7 @@ macro(SETUP_BLENDER_SORTED_LIBS)
                bf_blenloader
                bf_imbuf
                bf_blenlib
+               bf_depsgraph
                bf_intern_ghost
                bf_intern_string
                bf_avi
index 6e7417c76ecb4ca2095966026ff63ed896847130..ecf34759033e10f07159654190ac6c197849124d 100644 (file)
@@ -372,7 +372,7 @@ def propose_priorities():
 def creator(env):
     sources = ['creator.c']# + Blender.buildinfo(env, "dynamic") + Blender.resources
 
-    incs = ['#/intern/guardedalloc', '#/source/blender/blenlib', '#/source/blender/blenkernel', '#/source/blender/editors/include', '#/source/blender/blenloader', '#/source/blender/imbuf', '#/source/blender/renderconverter', '#/source/blender/render/extern/include', '#/source/blender/windowmanager', '#/source/blender/makesdna', '#/source/blender/makesrna', '#/source/gameengine/BlenderRoutines', '#/extern/glew/include', '#/source/blender/gpu', env['BF_OPENGL_INC']]
+    incs = ['#/intern/guardedalloc', '#/source/blender/blenlib', '#/source/blender/blenkernel', '#/source/blender/depsgraph', '#/source/blender/editors/include', '#/source/blender/blenloader', '#/source/blender/imbuf', '#/source/blender/renderconverter', '#/source/blender/render/extern/include', '#/source/blender/windowmanager', '#/source/blender/makesdna', '#/source/blender/makesrna', '#/source/gameengine/BlenderRoutines', '#/extern/glew/include', '#/source/blender/gpu', env['BF_OPENGL_INC']]
 
     defs = []
 
index c5342d6f349853edfd45c9dd8e45a55dabec6c01..76450fbd2239083433316d33457a991508a205bb 100644 (file)
@@ -199,7 +199,7 @@ def validate_arguments(args, bc):
             'LLIBS', 'PLATFORM_LINKFLAGS', 'MACOSX_ARCHITECTURE', 'MACOSX_SDK', 'XCODE_CUR_VER', 'C_COMPILER_ID',
             'BF_CYCLES_CUDA_BINARIES_ARCH', 'BF_PROGRAM_LINKFLAGS', 'MACOSX_DEPLOYMENT_TARGET',
             'WITH_BF_CYCLES_DEBUG', 'WITH_BF_CYCLES_LOGGING',
-            'WITH_BF_CPP11'
+            'WITH_BF_CPP11', 'WITH_BF_LEGACY_DEPSGRAPH',
     ]
 
 
@@ -657,6 +657,8 @@ def read_opts(env, cfg, args):
         ('BF_PROGRAM_LINKFLAGS', 'Link flags applied only to final binaries (blender and blenderplayer, not makesrna/makesdna)', ''),
 
         (BoolVariable('WITH_BF_CPP11', '"Build with C++11 standard enabled, for development use only!', False)),
+
+        (BoolVariable('WITH_BF_LEGACY_DEPSGRAPH', 'Build Blender with legacy dependency graph', True)),
     ) # end of opts.AddOptions()
 
     return localopts
index d87d5dfc2cce7abf0ebf010e7971d900efb497fd..9a73921bbc71cb42107d9f978ee367ed96414dac 100644 (file)
@@ -102,6 +102,7 @@ add_subdirectory(bmesh)
 add_subdirectory(render)
 add_subdirectory(blenfont)
 add_subdirectory(blenloader)
+add_subdirectory(depsgraph)
 add_subdirectory(ikplugin)
 add_subdirectory(physics)
 add_subdirectory(gpu)
index 64eca6a62dbec965aec9507dd0dd15ed1ac04726..e987b6be7792adf19ff6b2ad63c6fce120b87b67 100644 (file)
@@ -33,6 +33,7 @@ SConscript(['avi/SConscript',
             'blenkernel/SConscript',
             'blenlib/SConscript',
             'blenloader/SConscript',
+            'depsgraph/SConscript',
             'gpu/SConscript',
             'editors/SConscript',
             'imbuf/SConscript',
index f3a483fd0d873d71e3441fcd9ad7061778b904c2..862f91f567e6f413889d33fa5ea6b7529ec5c2e8 100644 (file)
@@ -92,6 +92,7 @@ void DAG_exit(void);
  */
 
 void DAG_scene_relations_update(struct Main *bmain, struct Scene *sce);
+void DAG_scene_relations_validate(struct Main *bmain, struct Scene *sce);
 void DAG_relations_tag_update(struct Main *bmain);
 void DAG_scene_relations_rebuild(struct Main *bmain, struct Scene *scene);
 void DAG_scene_free(struct Scene *sce);
index 9c5261c1583c5931a7e2f57d62cee4d9991d93d3..cc53f9409fd8ae03a4d02089d15de9bf16f44373 100644 (file)
@@ -43,6 +43,7 @@ struct bArmature;
 struct Main;
 struct ModifierData;
 struct BMEditMesh;
+struct DepsNodeHandle;
 
 typedef enum {
        /* Should not be used, only for None modifier type */
@@ -260,6 +261,17 @@ typedef struct ModifierTypeInfo {
                               struct Main *bmain, struct Scene *scene,
                               struct Object *ob, struct DagNode *obNode);
 
+       /* Add the appropriate relations to the dependency graph.
+        *
+        * This function is optional.
+        */
+       /* TODO(sergey): Remove once we finalyl switched to the new depsgraph. */
+       void (*updateDepsgraph)(struct ModifierData *md,
+                               struct Main *bmain,
+                               struct Scene *scene,
+                               struct Object *ob,
+                               struct DepsNodeHandle *node);
+
        /* Should return true if the modifier needs to be recalculated on time
         * changes.
         *
index fe713e64c647ddac218c218f46cc99574846e674..37e5b36779fdadbe53a7edb57eac1fb0102dbd09 100644 (file)
@@ -28,6 +28,7 @@ set(INC
        ../blenfont
        ../blenlib
        ../blenloader
+       ../depsgraph
        ../gpu
        ../ikplugin
        ../imbuf
@@ -482,4 +483,8 @@ endif()
 #      set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} /WX")
 #endif()
 
+if(WITH_LEGACY_DEPSGRAPH)
+       add_definitions(-DWITH_LEGACY_DEPSGRAPH)
+endif()
+
 blender_add_lib(bf_blenkernel "${SRC}" "${INC}" "${INC_SYS}")
index 47bba5f55379a6ece4025d56c3725183dc440bef..9d19e1c29b4c366a8d512bd30e43c817c085a175 100644 (file)
@@ -58,6 +58,7 @@ incs = [
     '../blenlib',
     '../blenloader',
     '../bmesh',
+    '../depsgraph',
     '../gpu',
     '../ikplugin',
     '../imbuf',
@@ -175,6 +176,9 @@ if env['WITH_BF_BINRELOC']:
     incs += ' #extern/binreloc/include'
     defs.append('WITH_BINRELOC')
 
+if env['WITH_BF_LEGACY_DEPSGRAPH']:
+    defs.append('WITH_LEGACY_DEPSGRAPH')
+
 if env['OURPLATFORM'] in ('win32-vc', 'win64-vc'):
     env.BlenderLib ( libname = 'bf_blenkernel', sources = sources, includes = Split(incs), defines = defs, libtype=['core','player'], priority = [166,25]) #, cc_compileflags = env['CCFLAGS'].append('/WX') )
 else:
index 708c64f8ffc0d7baaa7f7b12d48991024e8f6090..7e09ad355a7359be8ea5bfc85f3e8eabc0368264 100644 (file)
@@ -54,6 +54,7 @@
 #include "BKE_animsys.h"
 #include "BKE_constraint.h"
 #include "BKE_deform.h"
+#include "BKE_depsgraph.h"
 #include "BKE_fcurve.h"
 #include "BKE_global.h"
 #include "BKE_idprop.h"
@@ -1318,9 +1319,13 @@ bool BKE_pose_copy_result(bPose *to, bPose *from)
 }
 
 /* Tag pose for recalc. Also tag all related data to be recalc. */
-void BKE_pose_tag_recalc(Main *UNUSED(bmain), bPose *pose)
+void BKE_pose_tag_recalc(Main *bmain, bPose *pose)
 {
        pose->flag |= POSE_RECALC;
+       /* Depsgraph components depends on actual pose state,
+        * if pose was changed depsgraph is to be updated as well.
+        */
+       DAG_relations_tag_update(bmain);
 }
 
 /* For the calculation of the effects of an Action at the given frame on an object 
index 44ffb6a6697557c7ece6951552077d74122989f7..aa36036ed6ae0d0a9ffe547ea7aa69e3c8bec233 100644 (file)
@@ -51,6 +51,8 @@
 #include "BKE_global.h"
 #include "BKE_main.h"
 
+#include "DEG_depsgraph.h"
+
 #ifdef WITH_LEGACY_DEPSGRAPH
 #  define DEBUG_PRINT if (!DEG_depsgraph_use_legacy() && G.debug & G_DEBUG_DEPSGRAPH) printf
 #else
index 869404ae4a612dc2d1620f642c92f8c6c647b9b4..9ee9f3d57afc279fcecc21af1b5b326bf6b96d4a 100644 (file)
 
 #include "depsgraph_private.h"
 
+#include "DEG_depsgraph.h"
+#include "DEG_depsgraph_build.h"
+#include "DEG_depsgraph_debug.h"
+#include "DEG_depsgraph_query.h"
+
+#ifdef WITH_LEGACY_DEPSGRAPH
+
 static SpinLock threaded_update_lock;
 
 void DAG_init(void)
 {
        BLI_spin_init(&threaded_update_lock);
+       DEG_register_node_types();
 }
 
 void DAG_exit(void)
 {
        BLI_spin_end(&threaded_update_lock);
+       DEG_free_node_types();
 }
 
 /* Queue and stack operations for dag traversal 
@@ -1329,8 +1338,14 @@ static void (*EditorsUpdateSceneCb)(Main *bmain, Scene *scene, int updated) = NU
 
 void DAG_editors_update_cb(void (*id_func)(Main *bmain, ID *id), void (*scene_func)(Main *bmain, Scene *scene, int updated))
 {
-       EditorsUpdateIDCb = id_func;
-       EditorsUpdateSceneCb = scene_func;
+       if (DEG_depsgraph_use_legacy()) {
+               EditorsUpdateIDCb = id_func;
+               EditorsUpdateSceneCb = scene_func;
+       }
+       else {
+               /* New dependency graph. */
+               DEG_editors_set_update_cb(id_func, scene_func);
+       }
 }
 
 static void dag_editors_id_update(Main *bmain, ID *id)
@@ -1529,7 +1544,7 @@ static void dag_scene_build(Main *bmain, Scene *sce)
        Base *base;
 
        BLI_listbase_clear(&tempbase);
-       
+
        build_dag(bmain, sce, DAG_RL_ALL_BUT_DATA);
        
        dag_check_cycle(sce->theDag);
@@ -1621,32 +1636,65 @@ static void dag_scene_build(Main *bmain, Scene *sce)
 /* clear all dependency graphs */
 void DAG_relations_tag_update(Main *bmain)
 {
-       Scene *sce;
-
-       for (sce = bmain->scene.first; sce; sce = sce->id.next)
-               dag_scene_free(sce);
+       if (DEG_depsgraph_use_legacy()) {
+               Scene *sce;
+               for (sce = bmain->scene.first; sce; sce = sce->id.next) {
+                       dag_scene_free(sce);
+               }
+       }
+       else {
+               /* New dependency graph. */
+               DEG_relations_tag_update(bmain);
+       }
 }
 
 /* rebuild dependency graph only for a given scene */
 void DAG_scene_relations_rebuild(Main *bmain, Scene *sce)
 {
-       dag_scene_free(sce);
-       DAG_scene_relations_update(bmain, sce);
+       if (DEG_depsgraph_use_legacy()) {
+               dag_scene_free(sce);
+               DAG_scene_relations_update(bmain, sce);
+       }
+       else {
+               /* New dependency graph. */
+               DEG_scene_relations_rebuild(bmain, sce);
+       }
 }
 
 /* create dependency graph if it was cleared or didn't exist yet */
 void DAG_scene_relations_update(Main *bmain, Scene *sce)
 {
-       if (!sce->theDag)
-               dag_scene_build(bmain, sce);
+       if (DEG_depsgraph_use_legacy()) {
+               if (!sce->theDag)
+                       dag_scene_build(bmain, sce);
+       }
+       else {
+               /* New dependency graph. */
+               DEG_scene_relations_update(bmain, sce);
+       }
+}
+
+void DAG_scene_relations_validate(Main *bmain, Scene *sce)
+{
+       if (!DEG_depsgraph_use_legacy()) {
+               DEG_debug_scene_relations_validate(bmain, sce);
+       }
 }
 
 void DAG_scene_free(Scene *sce)
 {
-       if (sce->theDag) {
-               free_forest(sce->theDag);
-               MEM_freeN(sce->theDag);
-               sce->theDag = NULL;
+       if (DEG_depsgraph_use_legacy()) {
+               if (sce->theDag) {
+                       free_forest(sce->theDag);
+                       MEM_freeN(sce->theDag);
+                       sce->theDag = NULL;
+               }
+       }
+       else {
+               if (sce->depsgraph) {
+                       DEG_graph_free(sce->depsgraph);
+                       sce->depsgraph = NULL;
+               }
        }
 }
 
@@ -1889,7 +1937,11 @@ void DAG_scene_flush_update(Main *bmain, Scene *sce, unsigned int lay, const sho
        DagAdjList *itA;
        Object *ob;
        int lasttime;
-       
+
+       if (!DEG_depsgraph_use_legacy()) {
+               return;
+       }
+
        if (sce->theDag == NULL) {
                printf("DAG zero... not allowed to happen!\n");
                DAG_scene_relations_update(bmain, sce);
@@ -2300,7 +2352,7 @@ static void dag_current_scene_layers(Main *bmain, ListBase *lb)
        }
 }
 
-static void dag_group_on_visible_update(Group *group)
+static void dag_group_on_visible_update(Scene *scene, Group *group)
 {
        GroupObject *go;
 
@@ -2322,7 +2374,7 @@ static void dag_group_on_visible_update(Group *group)
                }
 
                if (go->ob->dup_group)
-                       dag_group_on_visible_update(go->ob->dup_group);
+                       dag_group_on_visible_update(scene, go->ob->dup_group);
        }
 }
 
@@ -2330,7 +2382,13 @@ void DAG_on_visible_update(Main *bmain, const bool do_time)
 {
        ListBase listbase;
        DagSceneLayer *dsl;
-       
+
+       if (!DEG_depsgraph_use_legacy()) {
+               /* Inform new dependnecy graphs about visibility changes. */
+               DEG_on_visible_update(bmain, do_time);
+               return;
+       }
+
        /* get list of visible scenes and layers */
        dag_current_scene_layers(bmain, &listbase);
        
@@ -2357,7 +2415,8 @@ void DAG_on_visible_update(Main *bmain, const bool do_time)
                        oblay = (node) ? node->lay : ob->lay;
 
                        if ((oblay & lay) & ~scene->lay_updated) {
-                               if (ELEM(ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE)) {
+                               /* TODO(sergey): Why do we need armature here now but didn't need before? */
+                               if (ELEM(ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE, OB_ARMATURE)) {
                                        ob->recalc |= OB_RECALC_DATA;
                                        lib_id_recalc_tag(bmain, &ob->id);
                                }
@@ -2375,7 +2434,7 @@ void DAG_on_visible_update(Main *bmain, const bool do_time)
                                        lib_id_recalc_tag(bmain, &ob->id);
                                }
                                if (ob->dup_group)
-                                       dag_group_on_visible_update(ob->dup_group);
+                                       dag_group_on_visible_update(scene, ob->dup_group);
                        }
                }
 
@@ -2609,7 +2668,12 @@ void DAG_ids_flush_tagged(Main *bmain)
        ListBase *lbarray[MAX_LIBARRAY];
        int a;
        bool do_flush = false;
-       
+
+       if (!DEG_depsgraph_use_legacy()) {
+               DEG_ids_flush_tagged(bmain);
+               return;
+       }
+
        /* get list of visible scenes and layers */
        dag_current_scene_layers(bmain, &listbase);
 
@@ -2653,6 +2717,11 @@ void DAG_ids_check_recalc(Main *bmain, Scene *scene, bool time)
        int a;
        bool updated = false;
 
+       if (!DEG_depsgraph_use_legacy()) {
+               DEG_ids_check_recalc(bmain, scene, time);
+               return;
+       }
+
        /* loop over all ID types */
        a  = set_listbasepointers(bmain, lbarray);
 
@@ -2769,6 +2838,11 @@ void DAG_ids_clear_recalc(Main *bmain)
 
 void DAG_id_tag_update_ex(Main *bmain, ID *id, short flag)
 {
+       if (!DEG_depsgraph_use_legacy()) {
+               DEG_id_tag_update_ex(bmain, id, flag);
+               return;
+       }
+
        if (id == NULL) return;
 
        if (G.debug & G_DEBUG_DEPSGRAPH) {
@@ -3160,6 +3234,10 @@ short DAG_get_eval_flags_for_object(Scene *scene, void *object)
 {
        DagNode *node;
 
+       if (!DEG_depsgraph_use_legacy()) {
+               return DEG_get_eval_flags_for_id(scene->depsgraph, (ID*)object);
+       }
+
        if (scene->theDag == NULL) {
                /* Happens when converting objects to mesh from a python script
                 * after modifying scene graph.
@@ -3198,3 +3276,286 @@ bool DAG_is_acyclic(Scene *scene)
 {
        return scene->theDag->is_acyclic;
 }
+
+#else
+
+/* *********************************************************************
+ * Stubs to avoid linking issues and make sure legacy crap is not used *
+ * *********************************************************************
+ */
+
+DagNodeQueue *queue_create(int UNUSED(slots))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+       return NULL;
+}
+
+void queue_raz(DagNodeQueue *UNUSED(queue))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+void queue_delete(DagNodeQueue *UNUSED(queue))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+void push_queue(DagNodeQueue *UNUSED(queue), DagNode *UNUSED(node))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+void push_stack(DagNodeQueue *UNUSED(queue), DagNode *UNUSED(node))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+DagNode *pop_queue(DagNodeQueue *UNUSED(queue))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+       return NULL;
+}
+
+DagNode *get_top_node_queue(DagNodeQueue *UNUSED(queue))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+       return NULL;
+}
+
+DagForest *dag_init(void)
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+       return NULL;
+}
+
+DagForest *build_dag(Main *UNUSED(bmain),
+                     Scene *UNUSED(sce),
+                     short UNUSED(mask))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+       return NULL;
+}
+
+void free_forest(DagForest *UNUSED(Dag))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+DagNode *dag_find_node(DagForest *UNUSED(forest), void *UNUSED(fob))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+       return NULL;
+}
+
+DagNode *dag_add_node(DagForest *UNUSED(forest), void *UNUSED(fob))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+       return NULL;
+}
+
+DagNode *dag_get_node(DagForest *UNUSED(forest), void *UNUSED(fob))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+       return NULL;
+}
+
+DagNode *dag_get_sub_node(DagForest *UNUSED(forest), void *UNUSED(fob))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+       return NULL;
+}
+
+void dag_add_relation(DagForest *UNUSED(forest),
+                      DagNode *UNUSED(fob1),
+                      DagNode *UNUSED(fob2),
+                      short UNUSED(rel),
+                      const char *UNUSED(name))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+/* debug test functions */
+
+void graph_print_queue(DagNodeQueue *UNUSED(nqueue))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+void graph_print_queue_dist(DagNodeQueue *UNUSED(nqueue))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+void graph_print_adj_list(DagForest *UNUSED(dag))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+void DAG_scene_flush_update(Main *UNUSED(bmain),
+                            Scene *UNUSED(sce),
+                            unsigned int UNUSED(lay),
+                            const short UNUSED(time))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+void DAG_scene_update_flags(Main *UNUSED(bmain),
+                            Scene *UNUSED(scene),
+                            unsigned int UNUSED(lay),
+                            const bool UNUSED(do_time),
+                            const bool UNUSED(do_invisible_flush))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+/* ******************* DAG FOR ARMATURE POSE ***************** */
+
+void DAG_pose_sort(Object *UNUSED(ob))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+}
+
+/* ************************  DAG FOR THREADED UPDATE  ********************* */
+
+void DAG_threaded_update_begin(Scene *UNUSED(scene),
+                               void (*func)(void *node, void *user_data),
+                               void *UNUSED(user_data))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+       (void)func;
+}
+
+void DAG_threaded_update_handle_node_updated(void *UNUSED(node_v),
+                                             void (*func)(void *node, void *user_data),
+                                             void *UNUSED(user_data))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+       (void)func;
+}
+
+/* ************************ DAG querying ********************* */
+
+Object *DAG_get_node_object(void *UNUSED(node_v))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+       return NULL;
+}
+
+const char *DAG_get_node_name(Scene *UNUSED(scene), void *UNUSED(node_v))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+       return "INVALID";
+}
+
+bool DAG_is_acyclic(Scene *UNUSED(scene))
+{
+       BLI_assert(!"Should not be used with new dependnecy graph");
+       return false;
+}
+
+/* ************************************
+ * This functions are to be supported *
+ * ************************************
+ */
+
+void DAG_init(void)
+{
+       DEG_register_node_types();
+}
+
+void DAG_exit(void)
+{
+       DEG_free_node_types();
+}
+
+/* ************************ API *********************** */
+
+void DAG_editors_update_cb(DEG_EditorUpdateIDCb id_func,
+                           DEG_EditorUpdateSceneCb scene_func)
+{
+       DEG_editors_set_update_cb(id_func, scene_func);
+}
+
+/* Tag all relations for update. */
+void DAG_relations_tag_update(Main *bmain)
+{
+       DEG_relations_tag_update(bmain);
+}
+
+/* Rebuild dependency graph only for a given scene. */
+void DAG_scene_relations_rebuild(Main *bmain, Scene *scene)
+{
+       DEG_scene_relations_rebuild(bmain, scene);
+}
+
+/* Create dependency graph if it was cleared or didn't exist yet. */
+void DAG_scene_relations_update(Main *bmain, Scene *scene)
+{
+       DEG_scene_relations_update(bmain, scene);
+}
+
+void DAG_scene_relations_validate(Main *bmain, Scene *scene)
+{
+       DEG_debug_scene_relations_validate(bmain, scene);
+}
+
+void DAG_scene_free(Scene *scene)
+{
+       DEG_scene_graph_free(scene);
+}
+
+void DAG_on_visible_update(Main *bmain, const bool do_time)
+{
+       DEG_on_visible_update(bmain, do_time);
+}
+
+void DAG_ids_check_recalc(Main *bmain, Scene *scene, bool time)
+{
+       DEG_ids_check_recalc(bmain, scene, time);
+}
+
+void DAG_id_tag_update(ID *id, short flag)
+{
+       DEG_id_tag_update_ex(G.main, id, flag);
+}
+
+void DAG_id_tag_update_ex(Main *bmain, ID *id, short flag)
+{
+       DEG_id_tag_update_ex(bmain, id, flag);
+}
+
+void DAG_id_type_tag(Main *bmain, short idtype)
+{
+       DEG_id_type_tag(bmain, idtype);
+}
+
+int DAG_id_type_tagged(Main *bmain, short idtype)
+{
+       return DEG_id_type_tagged(bmain, idtype);
+}
+
+void DAG_ids_clear_recalc(Main *bmain)
+{
+       DEG_ids_clear_recalc(bmain);
+}
+
+short DAG_get_eval_flags_for_object(Scene *scene, void *object)
+{
+       return DEG_get_eval_flags_for_id(scene->depsgraph, (ID*)object);
+}
+
+void DAG_ids_flush_tagged(Main *bmain)
+{
+       DEG_ids_flush_tagged(bmain);
+}
+
+/* ************************ DAG DEBUGGING ********************* */
+
+void DAG_print_dependencies(Main *UNUSED(bmain),
+                            Scene *scene,
+                            Object *UNUSED(ob))
+{
+       DEG_debug_graphviz(scene->depsgraph, stdout, "Depsgraph", false);
+}
+
+#endif
index ce118fe9fde8bc1508cecb15ba7d053171f1dfce..543d2de939aa77692a91f7f08bbf9a7836f6c9bb 100644 (file)
 #include "BKE_texture.h"
 #include "BKE_world.h"
 
+#include "DEG_depsgraph.h"
+
 #include "RNA_access.h"
 
 #ifdef WITH_PYTHON
@@ -1081,8 +1083,7 @@ void BKE_libblock_free_us(Main *bmain, void *idv)      /* test users */
 Main *BKE_main_new(void)
 {
        Main *bmain = MEM_callocN(sizeof(Main), "new main");
-       bmain->eval_ctx = MEM_callocN(sizeof(EvaluationContext),
-                                     "EvaluationContext");
+       bmain->eval_ctx = DEG_evaluation_context_new(DAG_EVAL_VIEWPORT);
        bmain->lock = MEM_mallocN(sizeof(SpinLock), "main lock");
        BLI_spin_init((SpinLock *)bmain->lock);
        return bmain;
@@ -1149,7 +1150,7 @@ void BKE_main_free(Main *mainvar)
 
        BLI_spin_end((SpinLock *)mainvar->lock);
        MEM_freeN(mainvar->lock);
-       MEM_freeN(mainvar->eval_ctx);
+       DEG_evaluation_context_free(mainvar->eval_ctx);
        MEM_freeN(mainvar);
 }
 
index 735e4358cb8e09899b6668c69816a042ffa64755..37a98eae58bf4f5963172ce5f3c9c9f278a5425e 100644 (file)
@@ -61,6 +61,7 @@
 #include "BKE_object.h"
 #include "BKE_editmesh.h"
 
+#include "DEG_depsgraph.h"
 
 enum {
        MESHCMP_DVERT_WEIGHTMISMATCH = 1,
@@ -2397,8 +2398,8 @@ Mesh *BKE_mesh_new_from_object(
                                 *               only contains for_render flag. As soon as CoW is
                                 *               implemented, this is to be rethinked.
                                 */
-                               EvaluationContext eval_ctx = {0};
-                               eval_ctx.mode = DAG_EVAL_RENDER;
+                               EvaluationContext eval_ctx;
+                               DEG_evaluation_context_init(&eval_ctx, DAG_EVAL_RENDER);
                                BKE_displist_make_mball_forRender(&eval_ctx, sce, ob, &disp);
                                BKE_mesh_from_metaball(&disp, tmpmesh);
                                BKE_displist_free(&disp);
index 76c20adf8c57128419cf2d874391b6c3802ae1f4..972a93b4a35fedc019f2c8f94c131b45af71b28a 100644 (file)
@@ -57,6 +57,8 @@
 #include "BKE_material.h"
 #include "BKE_image.h"
 
+#include "DEG_depsgraph.h"
+
 #ifdef WITH_LEGACY_DEPSGRAPH
 #  define DEBUG_PRINT if (!DEG_depsgraph_use_legacy() && G.debug & G_DEBUG_DEPSGRAPH) printf
 #else
index f810630c83bf548f7bcdb67ec5a03b02a77cccc3..3d87279e054ca4f1e8f3c820fc085abee8c77c56 100644 (file)
@@ -89,6 +89,8 @@
 #include "BKE_unit.h"
 #include "BKE_world.h"
 
+#include "DEG_depsgraph.h"
+
 #include "RE_engine.h"
 
 #include "PIL_time.h"
@@ -193,6 +195,7 @@ Scene *BKE_scene_copy(Scene *sce, int type)
 
                scen->ed = NULL;
                scen->theDag = NULL;
+               scen->depsgraph = NULL;
                scen->obedit = NULL;
                scen->stats = NULL;
                scen->fps_info = NULL;
@@ -431,6 +434,8 @@ void BKE_scene_free(Scene *sce)
        }
        
        DAG_scene_free(sce);
+       if (sce->depsgraph)
+               DEG_graph_free(sce->depsgraph);
        
        if (sce->nodetree) {
                ntreeFreeTree(sce->nodetree);
@@ -1167,6 +1172,7 @@ void BKE_scene_frame_set(struct Scene *scene, double cfra)
        scene->r.cfra = (int)intpart;
 }
 
+#ifdef WITH_LEGACY_DEPSGRAPH
 /* drivers support/hacks 
  *  - this method is called from scene_update_tagged_recursive(), so gets included in viewport + render
  *     - these are always run since the depsgraph can't handle non-object data
@@ -1267,6 +1273,7 @@ static void scene_depsgraph_hack(EvaluationContext *eval_ctx, Scene *scene, Scen
                }
        }
 }
+#endif  /* WITH_LEGACY_DEPSGRAPH */
 
 /* That's like really a bummer, because currently animation data for armatures
  * might want to use pose, and pose might be missing on the object.
@@ -1318,7 +1325,12 @@ static void scene_do_rb_simulation_recursive(Scene *scene, float ctime)
  * would pollute STDERR with whole bunch of timing information which then
  * could be parsed and nicely visualized.
  */
-#undef DETAILED_ANALYSIS_OUTPUT
+#ifdef WITH_LEGACY_DEPSGRAPH
+#  undef DETAILED_ANALYSIS_OUTPUT
+#else
+/* ALWAYS KEEY DISABLED! */
+#  undef DETAILED_ANALYSIS_OUTPUT
+#endif
 
 /* Mballs evaluation uses BKE_scene_base_iter_next which calls
  * duplilist for all objects in the scene. This leads to conflict
@@ -1330,6 +1342,7 @@ static void scene_do_rb_simulation_recursive(Scene *scene, float ctime)
  */
 #define MBALL_SINGLETHREAD_HACK
 
+#ifdef WITH_LEGACY_DEPSGRAPH
 typedef struct StatisicsEntry {
        struct StatisicsEntry *next, *prev;
        Object *object;
@@ -1619,6 +1632,7 @@ static void scene_update_tagged_recursive(EvaluationContext *eval_ctx, Main *bma
        BKE_mask_update_scene(bmain, scene);
        
 }
+#endif  /* WITH_LEGACY_DEPSGRAPH */
 
 static bool check_rendered_viewport_visible(Main *bmain)
 {
@@ -1670,13 +1684,26 @@ static void prepare_mesh_for_viewport_render(Main *bmain, Scene *scene)
 void BKE_scene_update_tagged(EvaluationContext *eval_ctx, Main *bmain, Scene *scene)
 {
        Scene *sce_iter;
-       
+#ifdef WITH_LEGACY_DEPSGRAPH
+       bool use_new_eval = !DEG_depsgraph_use_legacy();
+#endif
+
        /* keep this first */
        BLI_callback_exec(bmain, &scene->id, BLI_CB_EVT_SCENE_UPDATE_PRE);
 
        /* (re-)build dependency graph if needed */
-       for (sce_iter = scene; sce_iter; sce_iter = sce_iter->set)
+       for (sce_iter = scene; sce_iter; sce_iter = sce_iter->set) {
                DAG_scene_relations_update(bmain, sce_iter);
+               /* Uncomment this to check if graph was properly tagged for update. */
+#if 0
+#ifdef WITH_LEGACY_DEPSGRAPH
+               if (use_new_eval)
+#endif
+               {
+                       DAG_scene_relations_validate(bmain, sce_iter);
+               }
+#endif
+       }
 
        /* flush editing data if needed */
        prepare_mesh_for_viewport_render(bmain, scene);
@@ -1697,7 +1724,17 @@ void BKE_scene_update_tagged(EvaluationContext *eval_ctx, Main *bmain, Scene *sc
         *
         * in the future this should handle updates for all datablocks, not
         * only objects and scenes. - brecht */
-       scene_update_tagged_recursive(eval_ctx, bmain, scene, scene);
+#ifdef WITH_LEGACY_DEPSGRAPH
+       if (use_new_eval) {
+               DEG_evaluate_on_refresh(eval_ctx, scene->depsgraph, scene);
+       }
+       else {
+               scene_update_tagged_recursive(eval_ctx, bmain, scene, scene);
+       }
+#else
+       DEG_evaluate_on_refresh(eval_ctx, bmain, scene->depsgraph, scene);
+#endif
+
        /* update sound system animation (TODO, move to depsgraph) */
        BKE_sound_update_scene(bmain, scene);
 
@@ -1715,7 +1752,8 @@ void BKE_scene_update_tagged(EvaluationContext *eval_ctx, Main *bmain, Scene *sc
         * Need to do this so changing material settings from the graph/dopesheet
         * will update stuff in the viewport.
         */
-       if (DAG_id_type_tagged(bmain, ID_MA)) {
+#ifdef WITH_LEGACY_DEPSGRAPH
+       if (!use_new_eval && DAG_id_type_tagged(bmain, ID_MA)) {
                Material *material;
                float ctime = BKE_scene_frame_get(scene);
 
@@ -1730,7 +1768,7 @@ void BKE_scene_update_tagged(EvaluationContext *eval_ctx, Main *bmain, Scene *sc
        }
 
        /* Also do the same for node trees. */
-       if (DAG_id_type_tagged(bmain, ID_NT)) {
+       if (!use_new_eval && DAG_id_type_tagged(bmain, ID_NT)) {
                float ctime = BKE_scene_frame_get(scene);
 
                FOREACH_NODETREE(bmain, ntree, id)
@@ -1741,9 +1779,12 @@ void BKE_scene_update_tagged(EvaluationContext *eval_ctx, Main *bmain, Scene *sc
                }
                FOREACH_NODETREE_END
        }
+#endif
 
        /* notify editors and python about recalc */
        BLI_callback_exec(bmain, &scene->id, BLI_CB_EVT_SCENE_UPDATE_POST);
+
+       /* Inform editors about possible changes. */
        DAG_ids_check_recalc(bmain, scene, false);
 
        /* clear recalc flags */
@@ -1763,6 +1804,12 @@ void BKE_scene_update_for_newframe_ex(EvaluationContext *eval_ctx, Main *bmain,
 #ifdef DETAILED_ANALYSIS_OUTPUT
        double start_time = PIL_check_seconds_timer();
 #endif
+#ifdef WITH_LEGACY_DEPSGRAPH
+       bool use_new_eval = !DEG_depsgraph_use_legacy();
+#else
+       /* TODO(sergey): Pass to evaluation routines instead of storing layer in the graph? */
+       (void) do_invisible_flush;
+#endif
 
        /* keep this first */
        BLI_callback_exec(bmain, &sce->id, BLI_CB_EVT_FRAME_CHANGE_PRE);
@@ -1772,12 +1819,16 @@ void BKE_scene_update_for_newframe_ex(EvaluationContext *eval_ctx, Main *bmain,
         * call this at the start so modifiers with textures don't lag 1 frame */
        BKE_image_update_frame(bmain, sce->r.cfra);
        
+#ifdef WITH_LEGACY_DEPSGRAPH
        /* rebuild rigid body worlds before doing the actual frame update
         * this needs to be done on start frame but animation playback usually starts one frame later
         * we need to do it here to avoid rebuilding the world on every simulation change, which can be very expensive
         */
-       scene_rebuild_rbw_recursive(sce, ctime);
-
+       if (!use_new_eval) {
+               scene_rebuild_rbw_recursive(sce, ctime);
+       }
+#endif
+       
        BKE_sound_set_cfra(sce->r.cfra);
        
        /* clear animation overrides */
@@ -1786,14 +1837,18 @@ void BKE_scene_update_for_newframe_ex(EvaluationContext *eval_ctx, Main *bmain,
        for (sce_iter = sce; sce_iter; sce_iter = sce_iter->set)
                DAG_scene_relations_update(bmain, sce_iter);
 
-       /* flush recalc flags to dependencies, if we were only changing a frame
-        * this would not be necessary, but if a user or a script has modified
-        * some datablock before BKE_scene_update_tagged was called, we need the flush */
-       DAG_ids_flush_tagged(bmain);
+#ifdef WITH_LEGACY_DEPSGRAPH
+       if (!use_new_eval) {
+               /* flush recalc flags to dependencies, if we were only changing a frame
+                * this would not be necessary, but if a user or a script has modified
+                * some datablock before BKE_scene_update_tagged was called, we need the flush */
+               DAG_ids_flush_tagged(bmain);
 
-       /* Following 2 functions are recursive
-        * so don't call within 'scene_update_tagged_recursive' */
-       DAG_scene_update_flags(bmain, sce, lay, true, do_invisible_flush);   // only stuff that moves or needs display still
+               /* Following 2 functions are recursive
+                * so don't call within 'scene_update_tagged_recursive' */
+               DAG_scene_update_flags(bmain, sce, lay, true, do_invisible_flush);   // only stuff that moves or needs display still
+       }
+#endif
 
        BKE_mask_evaluate_all_masks(bmain, ctime, true);
 
@@ -1807,8 +1862,12 @@ void BKE_scene_update_for_newframe_ex(EvaluationContext *eval_ctx, Main *bmain,
         * can be overridden by settings from Scene, which owns the Texture through a hierarchy
         * such as Scene->World->MTex/Texture) can still get correctly overridden.
         */
-       BKE_animsys_evaluate_all_animation(bmain, sce, ctime);
-       /*...done with recursive funcs */
+#ifdef WITH_LEGACY_DEPSGRAPH
+       if (!use_new_eval) {
+               BKE_animsys_evaluate_all_animation(bmain, sce, ctime);
+               /*...done with recursive funcs */
+       }
+#endif
 
        /* clear "LIB_DOIT" flag from all materials, to prevent infinite recursion problems later 
         * when trying to find materials with drivers that need evaluating [#32017] 
@@ -1818,19 +1877,38 @@ void BKE_scene_update_for_newframe_ex(EvaluationContext *eval_ctx, Main *bmain,
 
        /* run rigidbody sim */
        /* NOTE: current position is so that rigidbody sim affects other objects, might change in the future */
-       scene_do_rb_simulation_recursive(sce, ctime);
-
+#ifdef WITH_LEGACY_DEPSGRAPH
+       if (!use_new_eval) {
+               scene_do_rb_simulation_recursive(sce, ctime);
+       }
+#endif
+       
        /* BKE_object_handle_update() on all objects, groups and sets */
-       scene_update_tagged_recursive(eval_ctx, bmain, sce, sce);
+#ifdef WITH_LEGACY_DEPSGRAPH
+       if (use_new_eval) {
+               DEG_evaluate_on_framechange(eval_ctx, bmain, sce->depsgraph, ctime, lay);
+       }
+       else {
+               scene_update_tagged_recursive(eval_ctx, bmain, sce, sce);
+       }
+#else
+       DEG_evaluate_on_framechange(eval_ctx, bmain, sce->depsgraph, ctime, lay);
+#endif
+
        /* update sound system animation (TODO, move to depsgraph) */
        BKE_sound_update_scene(bmain, sce);
 
-       scene_depsgraph_hack(eval_ctx, sce, sce);
+#ifdef WITH_LEGACY_DEPSGRAPH
+       if (!use_new_eval) {
+               scene_depsgraph_hack(eval_ctx, sce, sce);
+       }
+#endif
 
        /* notify editors and python about recalc */
        BLI_callback_exec(bmain, &sce->id, BLI_CB_EVT_SCENE_UPDATE_POST);
        BLI_callback_exec(bmain, &sce->id, BLI_CB_EVT_FRAME_CHANGE_POST);
 
+       /* Inform editors about possible changes. */
        DAG_ids_check_recalc(bmain, sce, true);
 
        /* clear recalc flags */
index 6634767d4129e6b66443718a3028d2a00dc0caad..c736e54c4e988f4513ce766db4ac25786a06e8cc 100644 (file)
@@ -5567,6 +5567,7 @@ static void direct_link_scene(FileData *fd, Scene *sce)
        SceneRenderLayer *srl;
        
        sce->theDag = NULL;
+       sce->depsgraph = NULL;
        sce->obedit = NULL;
        sce->stats = NULL;
        sce->fps_info = NULL;
diff --git a/source/blender/depsgraph/CMakeLists.txt b/source/blender/depsgraph/CMakeLists.txt
new file mode 100644 (file)
index 0000000..014bcb4
--- /dev/null
@@ -0,0 +1,116 @@
+# ***** BEGIN GPL LICENSE BLOCK *****
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software Foundation,
+# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+#
+# The Original Code is Copyright (C) 2014, Blender Foundation
+# All rights reserved.
+#
+# The Original Code is: all of this file.
+#
+# Contributor(s): Joshua Leung, Lukas Toenne
+#
+# ***** END GPL LICENSE BLOCK *****
+
+set(INC
+       .
+       ./intern
+       ./util
+       ../blenkernel
+       ../blenlib
+       ../bmesh
+       ../makesdna
+       ../makesrna
+       ../modifiers
+       ../windowmanager
+       ../../../intern/atomic
+       ../../../intern/guardedalloc
+)
+
+set(INC_SYS
+)
+
+set(SRC
+       intern/depsgraph.cc
+       intern/depsnode.cc
+       intern/depsnode_component.cc
+       intern/depsnode_operation.cc
+       intern/depsgraph_build.cc
+       intern/depsgraph_build_nodes.cc
+       intern/depsgraph_build_relations.cc
+       intern/depsgraph_debug.cc
+       intern/depsgraph_eval.cc
+       intern/depsgraph_query.cc
+       intern/depsgraph_queue.cc
+       intern/depsgraph_tag.cc
+       intern/depsgraph_type_defines.cc
+       util/depsgraph_util_cycle.cc
+       util/depsgraph_util_pchanmap.cc
+       util/depsgraph_util_transitive.cc
+
+       DEG_depsgraph.h
+       DEG_depsgraph_build.h
+       DEG_depsgraph_debug.h
+       DEG_depsgraph_query.h
+       intern/depsgraph.h
+       intern/depsnode.h
+       intern/depsnode_component.h
+       intern/depsnode_operation.h
+       intern/depsnode_opcodes.h
+       intern/depsgraph_build.h
+       intern/depsgraph_debug.h
+       intern/depsgraph_intern.h
+       intern/depsgraph_queue.h
+       intern/depsgraph_types.h
+
+       util/depsgraph_util_cycle.h
+       util/depsgraph_util_function.h
+       util/depsgraph_util_hash.h
+       util/depsgraph_util_map.h
+       util/depsgraph_util_pchanmap.h
+       util/depsgraph_util_set.h
+       util/depsgraph_util_transitive.h
+)
+
+TEST_UNORDERED_MAP_SUPPORT()
+if(HAVE_STD_UNORDERED_MAP_HEADER)
+       if(HAVE_UNORDERED_MAP_IN_STD_NAMESPACE)
+               add_definitions(-DDEG_STD_UNORDERED_MAP)
+       else()
+               if(HAVE_UNORDERED_MAP_IN_TR1_NAMESPACE)
+                       add_definitions(-DDEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE)
+               else()
+                       add_definitions(-DDEG_NO_UNORDERED_MAP)
+                       message(STATUS "Replacing unordered_map/set with map/set (warning: slower!)")
+               endif()
+       endif()
+else()
+       if(HAVE_UNORDERED_MAP_IN_TR1_NAMESPACE)
+               add_definitions(-DDEG_TR1_UNORDERED_MAP)
+       else()
+               add_definitions(-DDEG_NO_UNORDERED_MAP)
+               message(STATUS "Replacing unordered_map/set with map/set (warning: slower!)")
+       endif()
+endif()
+
+if(WITH_LEGACY_DEPSGRAPH)
+       add_definitions(-DWITH_LEGACY_DEPSGRAPH)
+endif()
+
+if(WITH_BOOST)
+       list(APPEND INC_SYS ${BOOST_INCLUDE_DIR})
+       add_definitions(-DHAVE_BOOST_FUNCTION_BINDINGS)
+endif()
+
+blender_add_lib(bf_depsgraph "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/source/blender/depsgraph/DEG_depsgraph.h b/source/blender/depsgraph/DEG_depsgraph.h
new file mode 100644 (file)
index 0000000..9fc5047
--- /dev/null
@@ -0,0 +1,210 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Joshua Leung
+ * Contributor(s): None Yet
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ *
+ * Public API for Depsgraph
+ */
+
+#ifndef __DEG_DEPSGRAPH_H__
+#define __DEG_DEPSGRAPH_H__
+
+/* Dependency Graph
+ *
+ * The dependency graph tracks relations between various pieces of data in
+ * a Blender file, but mainly just those which make up scene data. It is used
+ * to determine the set of operations need to ensure that all data has been
+ * correctly evaluated in response to changes, based on dependencies and visibility
+ * of affected data.
+ *
+ *
+ * Evaluation Engine
+ *
+ * The evaluation takes the operation-nodes the Depsgraph has tagged for updating, 
+ * and schedules them up for being evaluated/executed such that the all dependency
+ * relationship constraints are satisfied. 
+ */
+
+/* ************************************************* */
+/* Forward-defined typedefs for core types
+ * - These are used in all depsgraph code and by all callers of Depsgraph API...
+ */
+
+/* Dependency Graph */
+typedef struct Depsgraph Depsgraph;
+
+/* ------------------------------------------------ */
+
+struct EvaluationContext;
+struct Main;
+
+struct PointerRNA;
+struct PropertyRNA;
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+bool DEG_depsgraph_use_legacy(void);
+void DEG_depsgraph_switch_to_legacy(void);
+void DEG_depsgraph_switch_to_new(void);
+
+/* ************************************************ */
+/* Depsgraph API */
+
+/* CRUD ------------------------------------------- */
+
+// Get main depsgraph instance from context!
+
+/* Create new Depsgraph instance */
+// TODO: what args are needed here? What's the building-graph entry point?
+Depsgraph *DEG_graph_new(void);
+
+/* Free Depsgraph itself and all its data */
+void DEG_graph_free(Depsgraph *graph);
+
+/* Node Types Registry ---------------------------- */
+
+/* Register all node types */
+void DEG_register_node_types(void);
+
+/* Free node type registry on exit */
+void DEG_free_node_types(void);
+
+/* Update Tagging -------------------------------- */
+
+/* Tag node(s) associated with states such as time and visibility */
+void DEG_scene_update_flags(Depsgraph *graph, const bool do_time);
+
+/* Update dependency graph when visible scenes/layers changes. */
+void DEG_graph_on_visible_update(struct Main *bmain, struct Scene *scene);
+
+/* Update all dependency graphs when visible scenes/layers changes. */
+void DEG_on_visible_update(struct Main *bmain, const bool do_time);
+
+/* Tag node(s) associated with changed data for later updates */
+void DEG_graph_id_tag_update(struct Main *bmain,
+                             Depsgraph *graph,
+                             struct ID *id);
+void DEG_graph_data_tag_update(Depsgraph *graph, const struct PointerRNA *ptr);
+void DEG_graph_property_tag_update(Depsgraph *graph, const struct PointerRNA *ptr, const struct PropertyRNA *prop);
+
+/* Tag given ID for an update in all the dependency graphs. */
+void DEG_id_tag_update(struct ID *id, short flag);
+void DEG_id_tag_update_ex(struct Main *bmain,
+                          struct ID *id,
+                          short flag);
+
+/* Tag given ID type for update.
+ *
+ * Used by all sort of render engines to quickly check if
+ * IDs of a given type need to be checked for update.
+ */
+void DEG_id_type_tag(struct Main *bmain, short idtype);
+
+void DEG_ids_clear_recalc(struct Main *bmain);
+
+/* Update Flushing ------------------------------- */
+
+/* Flush updates */
+void DEG_graph_flush_updates(struct Main *bmain, Depsgraph *graph);
+
+/* Flush updates for all IDs */
+void DEG_ids_flush_tagged(struct Main *bmain);
+
+/* Check if something was changed in the database and inform
+ * editors about this.
+ */
+void DEG_ids_check_recalc(struct Main *bmain,
+                          struct Scene *scene,
+                          bool time);
+
+/* Clear all update tags
+ * - For aborted updates, or after successful evaluation
+ */
+void DEG_graph_clear_tags(Depsgraph *graph);
+
+/* ************************************************ */
+/* Evaluation Engine API */
+
+/* Evaluation Context ---------------------------- */
+
+/* Create new evaluation context. */
+struct EvaluationContext *DEG_evaluation_context_new(int mode);
+
+/* Initialize evaluation context.
+ * Used by the areas which currently overrides the context or doesn't have
+ * access to a proper one.
+ */
+void DEG_evaluation_context_init(struct EvaluationContext *eval_ctx, int mode);
+
+/* Free evaluation context. */
+void DEG_evaluation_context_free(struct EvaluationContext *eval_ctx);
+
+/* Graph Evaluation  ----------------------------- */
+
+/* Frame changed recalculation entry point
+ * < context_type: context to perform evaluation for
+ * < ctime: (frame) new frame to evaluate values on
+ */
+void DEG_evaluate_on_framechange(struct EvaluationContext *eval_ctx,
+                                 struct Main *bmain,
+                                 Depsgraph *graph,
+                                 float ctime,
+                                 const int layer);
+
+/* Data changed recalculation entry point.
+ * < context_type: context to perform evaluation for
+ * < layers: visible layers bitmask to update the graph for
+ */
+void DEG_evaluate_on_refresh_ex(struct EvaluationContext *eval_ctx,
+                                Depsgraph *graph,
+                                const int layers);
+
+/* Data changed recalculation entry point.
+ * < context_type: context to perform evaluation for
+ */
+void DEG_evaluate_on_refresh(struct EvaluationContext *eval_ctx,
+                             Depsgraph *graph,
+                             struct Scene *scene);
+
+/* Editors Integration  -------------------------- */
+
+/* Mechanism to allow editors to be informed of depsgraph updates,
+ * to do their own updates based on changes.
+ */
+
+typedef void (*DEG_EditorUpdateIDCb)(struct Main *bmain, struct ID *id);
+typedef void (*DEG_EditorUpdateSceneCb)(struct Main *bmain,
+                                        struct Scene *scene,
+                                        int updated);
+
+/* Set callbacks which are being called when depsgraph changes. */
+void DEG_editors_set_update_cb(DEG_EditorUpdateIDCb id_func,
+                               DEG_EditorUpdateSceneCb scene_func);
+
+#ifdef __cplusplus
+} /* extern "C" */
+#endif
+
+#endif  /* __DEG_DEPSGRAPH_H__ */
diff --git a/source/blender/depsgraph/DEG_depsgraph_build.h b/source/blender/depsgraph/DEG_depsgraph_build.h
new file mode 100644 (file)
index 0000000..08b83ac
--- /dev/null
@@ -0,0 +1,117 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Joshua Leung
+ * Contributor(s): Lukas Toenne
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ *
+ * Public API for Depsgraph
+ */
+
+#ifndef __DEG_DEPSGRAPH_BUILD_H__
+#define __DEG_DEPSGRAPH_BUILD_H__
+
+/* ************************************************* */
+
+/* Dependency Graph */
+struct Depsgraph;
+
+/* ------------------------------------------------ */
+
+struct Main;
+struct Scene;
+
+struct PointerRNA;
+struct PropertyRNA;
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* Graph Building -------------------------------- */
+
+/* Build depsgraph for the given scene, and dump results in given graph container */
+void DEG_graph_build_from_scene(struct Depsgraph *graph, struct Main *bmain, struct Scene *scene);
+
+/* Tag relations from the given graph for update. */
+void DEG_graph_tag_relations_update(struct Depsgraph *graph);
+
+/* Tag all relations in the database for update.*/
+void DEG_relations_tag_update(struct Main *bmain);
+
+/* Create new graph if didn't exist yet,
+ * or update relations if graph was tagged for update.
+ */
+void DEG_scene_relations_update(struct Main *bmain, struct Scene *scene);
+
+/* Rebuild dependency graph only for a given scene. */
+void DEG_scene_relations_rebuild(struct Main *bmain,
+                                 struct Scene *scene);
+
+/* Delete scene graph. */
+void DEG_scene_graph_free(struct Scene *scene);
+
+/* Add Dependencies  ----------------------------- */
+
+/* Handle for components to define their dependencies from callbacks.
+ * This is generated by the depsgraph and passed to dependency callbacks
+ * as a symbolic reference to the current DepsNode.
+ * All relations will be defined in reference to that node.
+ */
+struct DepsNodeHandle;
+
+struct Object;
+
+typedef enum eDepsSceneComponentType {
+       DEG_SCENE_COMP_PARAMETERS,     /* Parameters Component - Default when nothing else fits (i.e. just SDNA property setting) */
+       DEG_SCENE_COMP_ANIMATION,      /* Animation Component */                 // XXX: merge in with parameters?
+       DEG_SCENE_COMP_SEQUENCER,      /* Sequencer Component (Scene Only) */
+} eDepsSceneComponentType;
+
+typedef enum eDepsObjectComponentType {
+       DEG_OB_COMP_PARAMETERS,        /* Parameters Component - Default when nothing else fits (i.e. just SDNA property setting) */
+       DEG_OB_COMP_PROXY,             /* Generic "Proxy-Inherit" Component */   // XXX: Also for instancing of subgraphs?
+       DEG_OB_COMP_ANIMATION,         /* Animation Component */                 // XXX: merge in with parameters?
+       DEG_OB_COMP_TRANSFORM,         /* Transform Component (Parenting/Constraints) */
+       DEG_OB_COMP_GEOMETRY,          /* Geometry Component (DerivedMesh/Displist) */
+       
+       /* Evaluation-Related Outer Types (with Subdata) */
+       DEG_OB_COMP_EVAL_POSE,         /* Pose Component - Owner/Container of Bones Eval */
+       DEG_OB_COMP_BONE,              /* Bone Component - Child/Subcomponent of Pose */
+       
+       DEG_OB_COMP_EVAL_PARTICLES,    /* Particle Systems Component */
+       DEG_OB_COMP_SHADING,           /* Material Shading Component */
+} eDepsObjectComponentType;
+
+void DEG_add_scene_relation(struct DepsNodeHandle *node, struct Scene *scene, eDepsSceneComponentType component, const char *description);
+void DEG_add_object_relation(struct DepsNodeHandle *node, struct Object *ob, eDepsObjectComponentType component, const char *description);
+void DEG_add_bone_relation(struct DepsNodeHandle *handle, struct Object *ob, const char *bone_name, eDepsObjectComponentType component, const char *description);
+
+/* TODO(sergey): Remove once all geometry update is granular. */
+void DEG_add_special_eval_flag(struct Depsgraph *graph, struct ID *id, short flag);
+
+/* ************************************************ */
+
+#ifdef __cplusplus
+} /* extern "C" */
+#endif
+
+#endif  /* __DEG_DEPSGRAPH_BUILD_H__ */
diff --git a/source/blender/depsgraph/DEG_depsgraph_debug.h b/source/blender/depsgraph/DEG_depsgraph_debug.h
new file mode 100644 (file)
index 0000000..60e9a02
--- /dev/null
@@ -0,0 +1,107 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2014 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Lukas Toenne
+ * Contributor(s): None Yet
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ *
+ * Public API for Querying and Filtering Depsgraph
+ */
+
+#ifndef __DEG_DEPSGRAPH_DEBUG_H__
+#define __DEG_DEPSGRAPH_DEBUG_H__
+
+#include <stdio.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct DepsgraphSettings;
+struct GHash;
+struct ID;
+
+struct Depsgraph;
+struct DepsNode;
+struct DepsRelation;
+
+/* ************************************************ */
+/* Statistics */
+
+typedef struct DepsgraphStatsTimes {
+       float duration_last;
+} DepsgraphStatsTimes;
+
+typedef struct DepsgraphStatsComponent {
+       struct DepsgraphStatsComponent *next, *prev;
+       
+       char name[64];
+       DepsgraphStatsTimes times;
+} DepsgraphStatsComponent;
+
+typedef struct DepsgraphStatsID {
+       struct ID *id;
+       
+       DepsgraphStatsTimes times;
+       ListBase components;
+} DepsgraphStatsID;
+
+typedef struct DepsgraphStats {
+       struct GHash *id_stats;
+} DepsgraphStats;
+
+struct DepsgraphStats *DEG_stats(void);
+
+void DEG_stats_verify(void);
+
+struct DepsgraphStatsID *DEG_stats_id(struct ID *id);
+
+/* ------------------------------------------------ */
+
+void DEG_stats_simple(const struct Depsgraph *graph, 
+                      size_t *r_outer,
+                      size_t *r_operations,
+                      size_t *r_relations);
+
+/* ************************************************ */
+/* Diagram-Based Graph Debugging */
+
+void DEG_debug_graphviz(const struct Depsgraph *graph, FILE *stream, const char *label, bool show_eval);
+
+/* ************************************************ */
+
+/* Compare two dependency graphs. */
+bool DEG_debug_compare(const struct Depsgraph *graph1,
+                       const struct Depsgraph *graph2);
+
+/* Check that dependnecies in the graph are really up to date. */
+bool DEG_debug_scene_relations_validate(struct Main *bmain,
+                                        struct Scene *scene);
+
+
+/* Perform consistency check on the graph. */
+bool DEG_debug_consistency_check(struct Depsgraph *graph);
+
+#ifdef __cplusplus
+} /* extern "C" */
+#endif
+
+#endif  /* __DEG_DEPSGRAPH_DEBUG_H__ */
diff --git a/source/blender/depsgraph/DEG_depsgraph_query.h b/source/blender/depsgraph/DEG_depsgraph_query.h
new file mode 100644 (file)
index 0000000..000497c
--- /dev/null
@@ -0,0 +1,191 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Joshua Leung
+ * Contributor(s): None Yet
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ *
+ * Public API for Querying and Filtering Depsgraph
+ */
+
+#ifndef __DEG_DEPSGRAPH_QUERY_H__
+#define __DEG_DEPSGRAPH_QUERY_H__
+
+struct ListBase;
+struct ID;
+
+struct Depsgraph;
+struct DepsNode;
+struct DepsRelation;
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* ************************************************ */
+/* Type Defines */
+
+/* FilterPredicate Callback 
+ *
+ * Defines a callback function which can be supplied to check whether a 
+ * node is relevant or not.
+ *
+ * < graph: Depsgraph that we're traversing
+ * < node: The node to check
+ * < userdata: FilterPredicate state data (as needed)
+ * > returns: True if node is relevant
+ */
+typedef bool (*DEG_FilterPredicate)(const struct Depsgraph *graph, const struct DepsNode *node, void *userdata);
+
+
+/* Node Operation 
+ *
+ * Performs some action on the given node, provided that the node was
+ * deemed to be relevant to operate on.
+ *
+ * < graph: Depsgraph that we're traversing
+ * < node: The node to perform operation on/with
+ * < userdata: Node Operation's state data (as needed)
+ * > returns: True if traversal should be aborted at this point
+ */
+typedef bool (*DEG_NodeOperation)(const struct Depsgraph *graph, struct DepsNode *node, void *userdata);
+
+/* ************************************************ */
+/* Low-Level Filtering API */
+
+/* Create a filtered copy of the given graph which contains only the
+ * nodes which fulfill the criteria specified using the FilterPredicate
+ * passed in.
+ *
+ * < graph: The graph to be copied and filtered
+ * < filter: FilterPredicate used to check which nodes should be included
+ *           (If null, full graph is copied as-is)
+ * < userdata: State data for filter (as necessary)
+ *
+ * > returns: a full copy of all the relevant nodes - the matching subgraph
+ */
+// XXX: is there any need for extra settings/options for how the filtering goes?
+Depsgraph *DEG_graph_filter(const struct Depsgraph *graph, DEG_FilterPredicate *filter, void *userdata);
+
+
+/* Traverse nodes in graph which are deemed relevant,
+ * performing the provided operation on the nodes.
+ *
+ * < graph: The graph to perform operations on
+ * < filter: FilterPredicate used to check which nodes should be included
+ *           (If null, all nodes are considered valid targets)
+ * < filter_data: Custom state data for FilterPredicate
+ *                (Note: This can be the same as op_data, where appropriate)
+ * < op: NodeOperation to perform on each node
+ *       (If null, no graph traversal is performed for efficiency)
+ * < op_data: Custom state data for NodeOperation
+ *            (Note: This can be the same as filter_data, where appropriate)
+ */
+void DEG_graph_traverse(const struct Depsgraph *graph,
+                        DEG_FilterPredicate *filter, void *filter_data,
+                        DEG_NodeOperation *op, void *op_data);
+
+/* ************************************************ */
+/* Node-Based Operations */
+// XXX: do we want to be able to attach conditional requirements here?
+
+/* Find an (outer) node matching given conditions 
+ * ! Assumes that there will only be one such node, or that only the first one matters
+ *
+ * < graph: a dependency graph which may or may not contain a node matching these requirements
+ * < query: query conditions for the criteria that the node must satisfy 
+ */
+//DepsNode *DEG_node_find(const Depsgraph *graph, DEG_QueryConditions *query);
+
+/* Topology Queries (Direct) ---------------------- */
+
+/* Get list of nodes which directly depend on given node  
+ *
+ * > result: list to write results to
+ * < node: the node to find the children/dependents of
+ */
+void DEG_node_get_children(struct ListBase *result, const struct DepsNode *node);
+
+
+/* Get list of nodes which given node directly depends on 
+ *
+ * > result: list to write results to
+ * < node: the node to find the dependencies of
+ */
+void DEG_node_get_dependencies(struct ListBase *result, const struct DepsNode *node);
+
+
+/* Topology Queries (Subgraph) -------------------- */
+// XXX: given that subgraphs potentially involve many interconnected nodes, we currently
+//      just spit out a copy of the subgraph which matches. This works well for the cases
+//      where these are used - mostly for efficient updating of subsets of the nodes.
+
+// XXX: allow supplying a filter predicate to provide further filtering/pruning?
+
+
+/* Get all descendants of a node
+ *
+ * That is, get the subgraph / subset of nodes which are dependent
+ * on the results of the given node.
+ */
+Depsgraph *DEG_node_get_descendants(const struct Depsgraph *graph, const struct DepsNode *node);
+
+
+/* Get all ancestors of a node 
+ *
+ * That is, get the subgraph / subset of nodes which the given node
+ * is dependent on in order to be evaluated.
+ */
+Depsgraph *DEG_node_get_ancestors(const struct Depsgraph *graph, const struct DepsNode *node);
+
+/* ************************************************ */
+/* Higher-Level Queries */
+
+/* Get ID-blocks which would be affected if specified ID is modified 
+ * < only_direct: True = Only ID-blocks with direct relationships to ID-block will be returned
+ *
+ * > result: (LinkData : ID) a list of ID-blocks matching the specified criteria
+ * > returns: number of matching ID-blocks
+ */
+size_t DEG_query_affected_ids(struct ListBase *result, const struct ID *id, const bool only_direct);
+
+
+/* Get ID-blocks which are needed to update/evaluate specified ID 
+ * < only_direct: True = Only ID-blocks with direct relationships to ID-block will be returned
+ *
+ * > result: (LinkData : ID) a list of ID-blocks matching the specified criteria
+ * > returns: number of matching ID-blocks
+ */
+size_t DEG_query_required_ids(struct ListBase *result, const struct ID *id, const bool only_direct);
+
+/* ************************************************ */
+
+/* Check if given ID type was tagged for update. */
+bool DEG_id_type_tagged(struct Main *bmain, short idtype);
+
+/* Get additional evaluation flags for the given ID. */
+short DEG_get_eval_flags_for_id(struct Depsgraph *graph, struct ID *id);
+
+#ifdef __cplusplus
+} /* extern "C" */
+#endif
+
+#endif  /* __DEG_DEPSGRAPH_QUERY_H__ */
diff --git a/source/blender/depsgraph/SConscript b/source/blender/depsgraph/SConscript
new file mode 100644 (file)
index 0000000..dd0552e
--- /dev/null
@@ -0,0 +1,74 @@
+#!/usr/bin/env python
+#
+# ***** BEGIN GPL LICENSE BLOCK *****
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software Foundation,
+# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+#
+# The Original Code is Copyright (C) 2013, Blender Foundation
+# All rights reserved.
+#
+# The Original Code is: all of this file.
+#
+# Contributor(s): Nathan Letwory, Joshua Leung.
+#
+# ***** END GPL LICENSE BLOCK *****
+
+Import('env')
+
+sources = env.Glob('intern/*.cc') + env.Glob('util/*.cc')
+
+incs = [
+    '.',
+    './intern',
+    './util',
+    '#/intern/atomic',
+    '#/intern/guardedalloc',
+    '../bmesh',
+    '../blenlib',
+    '../blenkernel',
+    '../makesdna',
+    '../makesrna',
+    '../modifiers',
+    '../windowmanager',
+    ]
+
+defs = []
+
+if env['WITH_BF_BOOST']:
+    incs.append(env['BF_BOOST_INC'])
+    defs.append('HAVE_BOOST_FUNCTION_BINDINGS')
+
+if env['OURPLATFORM'] in ('win32-vc', 'win32-mingw', 'linuxcross', 'win64-vc', 'win64-mingw'):
+    incs.append(env['BF_PTHREADS_INC'])
+
+
+if env['WITH_UNORDERED_MAP_SUPPORT']:
+    if env['UNORDERED_MAP_HEADER'] == 'unordered_map':
+        if env['UNORDERED_MAP_NAMESPACE'] == 'std':
+            defs.append('DEG_STD_UNORDERED_MAP')
+        elif env['UNORDERED_MAP_NAMESPACE'] == 'std::tr1':
+            defs.append('DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE')
+    elif env['UNORDERED_MAP_NAMESPACE'] == 'std::tr1':
+        defs.append('DEG_TR1_UNORDERED_MAP')
+else:
+    print("-- Replacing unordered_map/set with map/set (warning: slower!)")
+    defs.append('DEG_NO_UNORDERED_MAP')
+
+if env['WITH_BF_LEGACY_DEPSGRAPH']:
+    defs.append('WITH_LEGACY_DEPSGRAPH')
+
+env.BlenderLib(libname='bf_depsgraph', sources=sources,
+               includes=incs, defines=defs,
+               libtype=['core', 'player'], priority=[200, 40])
diff --git a/source/blender/depsgraph/intern/depsgraph.cc b/source/blender/depsgraph/intern/depsgraph.cc
new file mode 100644 (file)
index 0000000..c519f1d
--- /dev/null
@@ -0,0 +1,469 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Joshua Leung
+ * Contributor(s): Sergey Sharybin
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ *
+ * Core routines for how the Depsgraph works
+ */
+
+#include <string.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_listbase.h"
+
+extern "C" {
+#include "DNA_action_types.h"
+#include "DNA_armature_types.h"
+#include "DNA_constraint_types.h"
+#include "DNA_key_types.h"
+#include "DNA_object_types.h"
+#include "DNA_sequence_types.h"
+
+#include "RNA_access.h"
+}
+
+#include "DEG_depsgraph.h"
+#include "depsgraph.h" /* own include */
+#include "depsnode.h"
+#include "depsnode_operation.h"
+#include "depsnode_component.h"
+#include "depsgraph_intern.h"
+
+static DEG_EditorUpdateIDCb deg_editor_update_id_cb = NULL;
+static DEG_EditorUpdateSceneCb deg_editor_update_scene_cb = NULL;
+
+Depsgraph::Depsgraph()
+  : root_node(NULL),
+    need_update(false),
+    layers((1 << 20) - 1)
+{
+       BLI_spin_init(&lock);
+}
+
+Depsgraph::~Depsgraph()
+{
+       /* Free root node - it won't have been freed yet... */
+       clear_id_nodes();
+       clear_subgraph_nodes();
+       if (this->root_node != NULL) {
+               OBJECT_GUARDED_DELETE(this->root_node, RootDepsNode);
+       }
+       BLI_spin_end(&lock);
+}
+
+/* Query Conditions from RNA ----------------------- */
+
+static bool pointer_to_id_node_criteria(const PointerRNA *ptr,
+                                        const PropertyRNA *prop,
+                                        ID **id)
+{
+       if (!ptr->type)
+               return false;
+
+       if (!prop) {
+               if (RNA_struct_is_ID(ptr->type)) {
+                       *id = (ID *)ptr->data;
+                       return true;
+               }
+       }
+
+       return false;
+}
+
+static bool pointer_to_component_node_criteria(const PointerRNA *ptr,
+                                               const PropertyRNA *prop,
+                                               ID **id,
+                                               eDepsNode_Type *type,
+                                               string *subdata)
+{
+       if (!ptr->type)
+               return false;
+
+       /* Set default values for returns. */
+       *id      = (ID *)ptr->id.data;  /* For obvious reasons... */
+       *subdata = "";                 /* Default to no subdata (e.g. bone) name
+                                       * lookup in most cases. */
+
+       /* Handling of commonly known scenarios... */
+       if (ptr->type == &RNA_PoseBone) {
+               bPoseChannel *pchan = (bPoseChannel *)ptr->data;
+
+               /* Bone - generally, we just want the bone component... */
+               *type = DEPSNODE_TYPE_BONE;
+               *subdata = pchan->name;
+
+               return true;
+       }
+       else if (ptr->type == &RNA_Bone) {
+               Bone *bone = (Bone *)ptr->data;
+
+               /* armature-level bone, but it ends up going to bone component anyway */
+               // TODO: the ID in thise case will end up being bArmature, not Object as needed!
+               *type = DEPSNODE_TYPE_BONE;
+               *subdata = bone->name;
+               //*id = ...
+
+               return true;
+       }
+       else if (RNA_struct_is_a(ptr->type, &RNA_Constraint)) {
+               Object *ob = (Object *)ptr->id.data;
+               bConstraint *con = (bConstraint *)ptr->data;
+
+               /* object or bone? */
+               if (BLI_findindex(&ob->constraints, con) != -1) {
+                       /* object transform */
+                       // XXX: for now, we can't address the specific constraint or the constraint stack...
+                       *type = DEPSNODE_TYPE_TRANSFORM;
+                       return true;
+               }
+               else if (ob->pose) {
+                       bPoseChannel *pchan;
+                       for (pchan = (bPoseChannel *)ob->pose->chanbase.first; pchan; pchan = pchan->next) {
+                               if (BLI_findindex(&pchan->constraints, con) != -1) {
+                                       /* bone transforms */
+                                       *type = DEPSNODE_TYPE_BONE;
+                                       *subdata = pchan->name;
+                                       return true;
+                               }
+                       }
+               }
+       }
+       else if (RNA_struct_is_a(ptr->type, &RNA_Modifier)) {
+               //ModifierData *md = (ModifierData *)ptr->data;
+
+               /* Modifier */
+               /* NOTE: subdata is not the same as "operation name",
+                * so although we have unique ops for modifiers,
+                * we can't lump them together
+                */
+               *type = DEPSNODE_TYPE_BONE;
+               //*subdata = md->name;
+
+               return true;
+       }
+       else if (ptr->type == &RNA_Object) {
+               //Object *ob = (Object *)ptr->data;
+
+               /* Transforms props? */
+               if (prop) {
+                       const char *prop_identifier = RNA_property_identifier((PropertyRNA *)prop);
+
+                       if (strstr(prop_identifier, "location") ||
+                           strstr(prop_identifier, "rotation") ||
+                           strstr(prop_identifier, "scale"))
+                       {
+                               *type = DEPSNODE_TYPE_TRANSFORM;
+                               return true;
+                       }
+               }
+               // ...
+       }
+       else if (ptr->type == &RNA_ShapeKey) {
+               Key *key = (Key *)ptr->id.data;
+
+               /* ShapeKeys are currently handled as geometry on the geometry that owns it */
+               *id = key->from; // XXX
+               *type = DEPSNODE_TYPE_PARAMETERS;
+
+               return true;
+       }
+       else if (RNA_struct_is_a(ptr->type, &RNA_Sequence)) {
+               Sequence *seq = (Sequence *)ptr->data;
+               /* Sequencer strip */
+               *type = DEPSNODE_TYPE_SEQUENCER;
+               *subdata = seq->name; // xxx?
+               return true;
+       }
+
+       if (prop) {
+               /* All unknown data effectively falls under "parameter evaluation" */
+               *type = DEPSNODE_TYPE_PARAMETERS;
+               return true;
+       }
+
+       return false;
+}
+
+/* Convenience wrapper to find node given just pointer + property. */
+DepsNode *Depsgraph::find_node_from_pointer(const PointerRNA *ptr,
+                                            const PropertyRNA *prop) const
+{
+       ID *id;
+       eDepsNode_Type type;
+       string name;
+
+       /* Get querying conditions. */
+       if (pointer_to_id_node_criteria(ptr, prop, &id)) {
+               return find_id_node(id);
+       }
+       else if (pointer_to_component_node_criteria(ptr, prop, &id, &type, &name)) {
+               IDDepsNode *id_node = find_id_node(id);
+               if (id_node)
+                       return id_node->find_component(type, name);
+       }
+
+       return NULL;
+}
+
+/* Node Management ---------------------------- */
+
+RootDepsNode *Depsgraph::add_root_node()
+{
+       if (!root_node) {
+               DepsNodeFactory *factory = DEG_get_node_factory(DEPSNODE_TYPE_ROOT);
+               root_node = (RootDepsNode *)factory->create_node(NULL, "", "Root (Scene)");
+       }
+       return root_node;
+}
+
+TimeSourceDepsNode *Depsgraph::find_time_source(const ID *id) const
+{
+       /* Search for one attached to a particular ID? */
+       if (id) {
+               /* Check if it was added as a component
+                * (as may be done for subgraphs needing timeoffset).
+                */
+               IDDepsNode *id_node = find_id_node(id);
+               if (id_node) {
+                       // XXX: review this
+//                     return id_node->find_component(DEPSNODE_TYPE_TIMESOURCE);
+               }
+               BLI_assert(!"Not implemented yet");
+       }
+       else {
+               /* Use "official" timesource. */
+               return root_node->time_source;
+       }
+       return NULL;
+}
+
+SubgraphDepsNode *Depsgraph::add_subgraph_node(const ID *id)
+{
+       DepsNodeFactory *factory = DEG_get_node_factory(DEPSNODE_TYPE_SUBGRAPH);
+       SubgraphDepsNode *subgraph_node =
+               (SubgraphDepsNode *)factory->create_node(id, "", id->name + 2);
+
+       /* Add to subnodes list. */
+       this->subgraphs.insert(subgraph_node);
+
+       /* if there's an ID associated, add to ID-nodes lookup too */
+       if (id) {
+#if 0
+               /* XXX subgraph node is NOT a true IDDepsNode - what is this supposed to do? */
+               // TODO: what to do if subgraph's ID has already been added?
+               BLI_assert(!graph->find_id_node(id));
+               graph->id_hash[id] = this;
+#endif
+       }
+
+       return subgraph_node;
+}
+
+void Depsgraph::remove_subgraph_node(SubgraphDepsNode *subgraph_node)
+{
+       subgraphs.erase(subgraph_node);
+       OBJECT_GUARDED_DELETE(subgraph_node, SubgraphDepsNode);
+}
+
+void Depsgraph::clear_subgraph_nodes()
+{
+       for (Subgraphs::iterator it = subgraphs.begin();
+            it != subgraphs.end();
+            ++it)
+       {
+               SubgraphDepsNode *subgraph_node = *it;
+               OBJECT_GUARDED_DELETE(subgraph_node, SubgraphDepsNode);
+       }
+       subgraphs.clear();
+}
+
+IDDepsNode *Depsgraph::find_id_node(const ID *id) const
+{
+       IDNodeMap::const_iterator it = this->id_hash.find(id);
+       return it != this->id_hash.end() ? it->second : NULL;
+}
+
+IDDepsNode *Depsgraph::add_id_node(ID *id, const string &name)
+{
+       IDDepsNode *id_node = find_id_node(id);
+       if (!id_node) {
+               DepsNodeFactory *factory = DEG_get_node_factory(DEPSNODE_TYPE_ID_REF);
+               id_node = (IDDepsNode *)factory->create_node(id, "", name);
+               id->flag |= LIB_DOIT;
+               /* register */
+               this->id_hash[id] = id_node;
+       }
+       return id_node;
+}
+
+void Depsgraph::remove_id_node(const ID *id)
+{
+       IDDepsNode *id_node = find_id_node(id);
+       if (id_node) {
+               /* unregister */
+               this->id_hash.erase(id);
+               OBJECT_GUARDED_DELETE(id_node, IDDepsNode);
+       }
+}
+
+void Depsgraph::clear_id_nodes()
+{
+       for (IDNodeMap::const_iterator it = id_hash.begin();
+            it != id_hash.end();
+            ++it)
+       {
+               IDDepsNode *id_node = it->second;
+               OBJECT_GUARDED_DELETE(id_node, IDDepsNode);
+       }
+       id_hash.clear();
+}
+
+/* Add new relationship between two nodes. */
+DepsRelation *Depsgraph::add_new_relation(OperationDepsNode *from,
+                                          OperationDepsNode *to,
+                                          eDepsRelation_Type type,
+                                          const char *description)
+{
+       /* Create new relation, and add it to the graph. */
+       DepsRelation *rel = OBJECT_GUARDED_NEW(DepsRelation, from, to, type, description);
+       return rel;
+}
+
+/* Add new relation between two nodes */
+DepsRelation *Depsgraph::add_new_relation(DepsNode *from, DepsNode *to,
+                                          eDepsRelation_Type type,
+                                          const char *description)
+{
+       /* Create new relation, and add it to the graph. */
+       DepsRelation *rel = OBJECT_GUARDED_NEW(DepsRelation, from, to, type, description);
+       return rel;
+}
+
+/* ************************ */
+/* Relationships Management */
+
+DepsRelation::DepsRelation(DepsNode *from,
+                           DepsNode *to,
+                           eDepsRelation_Type type,
+                           const char *description)
+  : from(from),
+    to(to),
+    name(description),
+    type(type),
+    flag(0)
+{
+#ifndef NDEBUG
+/*
+       for (OperationDepsNode::Relations::const_iterator it = from->outlinks.begin();
+            it != from->outlinks.end();
+            ++it)
+       {
+               DepsRelation *rel = *it;
+               if (rel->from == from &&
+                   rel->to == to &&
+                   rel->type == type &&
+                   rel->name == description)
+               {
+                       BLI_assert(!"Duplicated relation, should not happen!");
+               }
+       }
+*/
+#endif
+
+       /* Hook it up to the nodes which use it. */
+       from->outlinks.insert(this);
+       to->inlinks.insert(this);
+}
+
+DepsRelation::~DepsRelation()
+{
+       /* Sanity check. */
+       BLI_assert(this->from && this->to);
+       /* Remove it from the nodes that use it. */
+       this->from->outlinks.erase(this);
+       this->to->inlinks.erase(this);
+}
+
+/* Low level tagging -------------------------------------- */
+
+/* Tag a specific node as needing updates. */
+void Depsgraph::add_entry_tag(OperationDepsNode *node)
+{
+       /* Sanity check. */
+       if (!node)
+               return;
+
+       /* Add to graph-level set of directly modified nodes to start searching from.
+        * NOTE: this is necessary since we have several thousand nodes to play with...
+        */
+       this->entry_tags.insert(node);
+}
+
+void Depsgraph::clear_all_nodes()
+{
+       clear_id_nodes();
+       clear_subgraph_nodes();
+       id_hash.clear();
+       if (this->root_node) {
+               OBJECT_GUARDED_DELETE(this->root_node, RootDepsNode);
+               root_node = NULL;
+       }
+}
+
+/* **************** */
+/* Public Graph API */
+
+/* Initialize a new Depsgraph */
+Depsgraph *DEG_graph_new()
+{
+       return OBJECT_GUARDED_NEW(Depsgraph);
+}
+
+/* Free graph's contents and graph itself */
+void DEG_graph_free(Depsgraph *graph)
+{
+       OBJECT_GUARDED_DELETE(graph, Depsgraph);
+}
+
+/* Set callbacks which are being called when depsgraph changes. */
+void DEG_editors_set_update_cb(DEG_EditorUpdateIDCb id_func,
+                               DEG_EditorUpdateSceneCb scene_func)
+{
+       deg_editor_update_id_cb = id_func;
+       deg_editor_update_scene_cb = scene_func;
+}
+
+void deg_editors_id_update(Main *bmain, ID *id)
+{
+       if (deg_editor_update_id_cb != NULL) {
+               deg_editor_update_id_cb(bmain, id);
+       }
+}
+
+void deg_editors_scene_update(Main *bmain, Scene *scene, bool updated)
+{
+       if (deg_editor_update_scene_cb != NULL) {
+               deg_editor_update_scene_cb(bmain, scene, updated);
+       }
+}
diff --git a/source/blender/depsgraph/intern/depsgraph.h b/source/blender/depsgraph/intern/depsgraph.h
new file mode 100644 (file)
index 0000000..8ce7362
--- /dev/null
@@ -0,0 +1,220 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Joshua Leung
+ * Contributor(s): Sergey Sharybin
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ *
+ * Datatypes for internal use in the Depsgraph
+ *
+ * All of these datatypes are only really used within the "core" depsgraph.
+ * In particular, node types declared here form the structure of operations
+ * in the graph.
+ */
+
+#ifndef __DEPSGRAPH_H__
+#define __DEPSGRAPH_H__
+
+#include "BLI_threads.h"  /* for SpinLock */
+
+#include "depsgraph_types.h"
+
+#include "depsgraph_util_map.h"
+#include "depsgraph_util_set.h"
+
+struct PointerRNA;
+struct PropertyRNA;
+
+struct DepsNode;
+struct RootDepsNode;
+struct TimeSourceDepsNode;
+struct IDDepsNode;
+struct SubgraphDepsNode;
+struct ComponentDepsNode;
+struct OperationDepsNode;
+
+/* *************************** */
+/* Relationships Between Nodes */
+
+/* Settings/Tags on Relationship */
+typedef enum eDepsRelation_Flag {
+       /* "touched" tag is used when filtering, to know which to collect */
+       DEPSREL_FLAG_TEMP_TAG   = (1 << 0),
+
+       /* "cyclic" link - when detecting cycles, this relationship was the one
+        * which triggers a cyclic relationship to exist in the graph
+        */
+       DEPSREL_FLAG_CYCLIC     = (1 << 1),
+} eDepsRelation_Flag;
+
+/* B depends on A (A -> B) */
+struct DepsRelation {
+       /* the nodes in the relationship (since this is shared between the nodes) */
+       DepsNode *from;               /* A */
+       DepsNode *to;                 /* B */
+
+       /* relationship attributes */
+       const char* name;             /* label for debugging */
+
+       eDepsRelation_Type type;      /* type */
+       int flag;                     /* (eDepsRelation_Flag) */
+
+       DepsRelation(DepsNode *from,
+                    DepsNode *to,
+                    eDepsRelation_Type type,
+                    const char *description);
+
+       ~DepsRelation();
+};
+
+/* ********* */
+/* Depsgraph */
+
+/* Dependency Graph object */
+struct Depsgraph {
+       typedef unordered_map<const ID *, IDDepsNode *> IDNodeMap;
+       typedef unordered_set<SubgraphDepsNode *> Subgraphs;
+       typedef unordered_set<OperationDepsNode *> EntryTags;
+       typedef vector<OperationDepsNode *> OperationNodes;
+
+       Depsgraph();
+       ~Depsgraph();
+
+       /**
+        * Find node which matches the specified description.
+        *
+        * \param id: ID block that is associated with this
+        * \param subdata: identifier used for sub-ID data (e.g. bone)
+        * \param type: type of node we're dealing with
+        * \param name: custom identifier assigned to node
+        *
+        * \return A node matching the required characteristics if it exists
+        * or NULL if no such node exists in the graph.
+        */
+       DepsNode *find_node(const ID *id,
+                           eDepsNode_Type type,
+                           const string &subdata,
+                           const string &name);
+
+       /**
+        * Convenience wrapper to find node given just pointer + property.
+        *
+        * \param ptr: pointer to the data that node will represent
+        * \param prop: optional property affected - providing this effectively results in inner nodes being returned
+        *
+        * \return A node matching the required characteristics if it exists
+        * or NULL if no such node exists in the graph
+        */
+       DepsNode *find_node_from_pointer(const PointerRNA *ptr, const PropertyRNA *prop) const;
+
+       RootDepsNode *add_root_node();
+
+       TimeSourceDepsNode *find_time_source(const ID *id = NULL) const;
+
+       SubgraphDepsNode *add_subgraph_node(const ID *id);
+       void remove_subgraph_node(SubgraphDepsNode *subgraph_node);
+       void clear_subgraph_nodes();
+
+       IDDepsNode *find_id_node(const ID *id) const;
+       IDDepsNode *add_id_node(ID *id, const string &name = "");
+       void remove_id_node(const ID *id);
+       void clear_id_nodes();
+
+       /* Add new relationship between two nodes. */
+       DepsRelation *add_new_relation(OperationDepsNode *from,
+                                      OperationDepsNode *to,
+                                      eDepsRelation_Type type,
+                                      const char *description);
+
+       DepsRelation *add_new_relation(DepsNode *from,
+                                      DepsNode *to,
+                                      eDepsRelation_Type type,
+                                      const char *description);
+
+       /* Tag a specific node as needing updates. */
+       void add_entry_tag(OperationDepsNode *node);
+
+       /* Clear storage used by all nodes. */
+       void clear_all_nodes();
+
+       /* Core Graph Functionality ........... */
+
+       /* <ID : IDDepsNode> mapping from ID blocks to nodes representing these blocks
+        * (for quick lookups). */
+       IDNodeMap id_hash;
+
+       /* "root" node - the one where all evaluation enters from. */
+       RootDepsNode *root_node;
+
+       /* Subgraphs referenced in tree. */
+       Subgraphs subgraphs;
+
+       /* Indicates whether relations needs to be updated. */
+       bool need_update;
+
+       /* Quick-Access Temp Data ............. */
+
+       /* Nodes which have been tagged as "directly modified". */
+       EntryTags entry_tags;
+
+       /* Convenience Data ................... */
+
+       /* XXX: should be collected after building (if actually needed?) */
+       /* All operation nodes, sorted in order of single-thread traversal order. */
+       OperationNodes operations;
+
+       /* Spin lock for threading-critical operations.
+        * Mainly used by graph evaluation.
+        */
+       SpinLock lock;
+
+       /* Layers Visibility .................. */
+
+       /* Visible layers bitfield, used for skipping invisible objects updates. */
+       int layers;
+
+       // XXX: additional stuff like eval contexts, mempools for allocating nodes from, etc.
+};
+
+/**
+ * Helper macros for interating over set of relationship links
+ * incident on each node.
+ *
+ * \note it is safe to perform removal operations here...
+ *
+ * relations_set[in]: (DepsNode::Relations) set of relationships (in/out links)
+ * relation[out]:  (DepsRelation *) identifier where DepsRelation that we're
+ *              currently accessing comes up
+ */
+#define DEPSNODE_RELATIONS_ITER_BEGIN(relations_set_, relation_) \
+       { \
+               OperationDepsNode::Relations::const_iterator __rel_iter = relations_set_.begin();  \
+               while (__rel_iter != relations_set_.end()) { \
+                       DepsRelation *relation_ = *__rel_iter; \
+                       ++__rel_iter; \
+
+                       /* ... code for iterator body can be written here ... */
+
+#define DEPSNODE_RELATIONS_ITER_END \
+               } \
+       } ((void)0)
+
+#endif  /* __DEPSGRAPH_H__ */
diff --git a/source/blender/depsgraph/intern/depsgraph_build.cc b/source/blender/depsgraph/intern/depsgraph_build.cc
new file mode 100644 (file)
index 0000000..b5e09db
--- /dev/null
@@ -0,0 +1,365 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Joshua Leung
+ * Contributor(s): Based on original depsgraph.c code - Blender Foundation (2005-2013)
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ *
+ * Methods for constructing depsgraph
+ */
+
+#include <stack>
+
+#include "MEM_guardedalloc.h"
+
+extern "C" {
+#include "BLI_blenlib.h"
+#include "BLI_string.h"
+#include "BLI_utildefines.h"
+
+#include "DNA_action_types.h"
+#include "DNA_anim_types.h"
+#include "DNA_armature_types.h"
+#include "DNA_camera_types.h"
+#include "DNA_constraint_types.h"
+#include "DNA_curve_types.h"
+#include "DNA_effect_types.h"
+#include "DNA_group_types.h"
+#include "DNA_key_types.h"
+#include "DNA_lamp_types.h"
+#include "DNA_material_types.h"
+#include "DNA_mesh_types.h"
+#include "DNA_meta_types.h"
+#include "DNA_node_types.h"
+#include "DNA_particle_types.h"
+#include "DNA_object_types.h"
+#include "DNA_rigidbody_types.h"
+#include "DNA_scene_types.h"
+#include "DNA_texture_types.h"
+#include "DNA_world_types.h"
+
+#include "BKE_action.h"
+#include "BKE_armature.h"
+#include "BKE_animsys.h"
+#include "BKE_constraint.h"
+#include "BKE_curve.h"
+#include "BKE_effect.h"
+#include "BKE_fcurve.h"
+#include "BKE_group.h"
+#include "BKE_key.h"
+#include "BKE_library.h"
+#include "BKE_main.h"
+#include "BKE_material.h"
+#include "BKE_mball.h"
+#include "BKE_modifier.h"
+#include "BKE_node.h"
+#include "BKE_object.h"
+#include "BKE_particle.h"
+#include "BKE_rigidbody.h"
+#include "BKE_sound.h"
+#include "BKE_texture.h"
+#include "BKE_tracking.h"
+#include "BKE_world.h"
+
+#include "DEG_depsgraph.h"
+#include "DEG_depsgraph_debug.h"
+#include "DEG_depsgraph_build.h"
+
+#include "RNA_access.h"
+#include "RNA_types.h"
+} /* extern "C" */
+
+#include "depsnode.h"
+#include "depsnode_component.h"
+#include "depsgraph_debug.h"
+#include "depsnode_operation.h"
+#include "depsgraph_types.h"
+#include "depsgraph_build.h"
+#include "depsgraph_intern.h"
+
+#include "depsgraph_util_cycle.h"
+#include "depsgraph_util_transitive.h"
+
+/* ****************** */
+/* External Build API */
+
+static eDepsNode_Type deg_build_scene_component_type(eDepsSceneComponentType component)
+{
+       switch (component) {
+               case DEG_SCENE_COMP_PARAMETERS:     return DEPSNODE_TYPE_PARAMETERS;
+               case DEG_SCENE_COMP_ANIMATION:      return DEPSNODE_TYPE_ANIMATION;
+               case DEG_SCENE_COMP_SEQUENCER:      return DEPSNODE_TYPE_SEQUENCER;
+       }
+       return DEPSNODE_TYPE_UNDEFINED;
+}
+
+static eDepsNode_Type deg_build_object_component_type(eDepsObjectComponentType component)
+{
+       switch (component) {
+               case DEG_OB_COMP_PARAMETERS:        return DEPSNODE_TYPE_PARAMETERS;
+               case DEG_OB_COMP_PROXY:             return DEPSNODE_TYPE_PROXY;
+               case DEG_OB_COMP_ANIMATION:         return DEPSNODE_TYPE_ANIMATION;
+               case DEG_OB_COMP_TRANSFORM:         return DEPSNODE_TYPE_TRANSFORM;
+               case DEG_OB_COMP_GEOMETRY:          return DEPSNODE_TYPE_GEOMETRY;
+               case DEG_OB_COMP_EVAL_POSE:         return DEPSNODE_TYPE_EVAL_POSE;
+               case DEG_OB_COMP_BONE:              return DEPSNODE_TYPE_BONE;
+               case DEG_OB_COMP_EVAL_PARTICLES:    return DEPSNODE_TYPE_EVAL_PARTICLES;
+               case DEG_OB_COMP_SHADING:           return DEPSNODE_TYPE_SHADING;
+       }
+       return DEPSNODE_TYPE_UNDEFINED;
+}
+
+void DEG_add_scene_relation(DepsNodeHandle *handle, struct Scene *scene, eDepsSceneComponentType component, const char *description)
+{
+       eDepsNode_Type type = deg_build_scene_component_type(component);
+       ComponentKey comp_key(&scene->id, type);
+       handle->builder->add_node_handle_relation(comp_key, handle, DEPSREL_TYPE_GEOMETRY_EVAL, description);
+}
+
+void DEG_add_object_relation(DepsNodeHandle *handle, struct Object *ob, eDepsObjectComponentType component, const char *description)
+{
+       eDepsNode_Type type = deg_build_object_component_type(component);
+       ComponentKey comp_key(&ob->id, type);
+       handle->builder->add_node_handle_relation(comp_key, handle, DEPSREL_TYPE_GEOMETRY_EVAL, description);
+}
+
+void DEG_add_bone_relation(DepsNodeHandle *handle, struct Object *ob, const char *bone_name, eDepsObjectComponentType component, const char *description)
+{
+       eDepsNode_Type type = deg_build_object_component_type(component);
+       ComponentKey comp_key(&ob->id, type, bone_name);
+
+       // XXX: "Geometry Eval" might not always be true, but this only gets called from modifier building now
+       handle->builder->add_node_handle_relation(comp_key, handle, DEPSREL_TYPE_GEOMETRY_EVAL, description);
+}
+
+void DEG_add_special_eval_flag(Depsgraph *graph, ID *id, short flag)
+{
+       if (graph == NULL) {
+               BLI_assert(!"Graph should always be valid");
+               return;
+       }
+       IDDepsNode *id_node = graph->find_id_node(id);
+       if (id_node == NULL) {
+               BLI_assert(!"ID should always be valid");
+               return;
+       }
+       id_node->eval_flags |= flag;
+}
+
+/* ********************** */
+/* Utilities for Builders */
+
+/* Get unique identifier for FCurves and Drivers */
+string deg_fcurve_id_name(const FCurve *fcu)
+{
+       char index_buf[32];
+       sprintf(index_buf, "[%d]", fcu->array_index);
+
+       return string(fcu->rna_path) + index_buf;
+}
+
+static void deg_graph_build_finalize(Depsgraph *graph)
+{
+       std::stack<OperationDepsNode*> stack;
+
+       for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin();
+            it_op != graph->operations.end();
+            ++it_op)
+       {
+               OperationDepsNode *node = *it_op;
+               node->done = 0;
+               node->num_links_pending = 0;
+               for (OperationDepsNode::Relations::const_iterator it_rel = node->inlinks.begin();
+                    it_rel != node->inlinks.end();
+                    ++it_rel)
+               {
+                       DepsRelation *rel = *it_rel;
+                       if (rel->from->type == DEPSNODE_TYPE_OPERATION &&
+                           (rel->flag & DEPSREL_FLAG_CYCLIC) == 0) {
+                               ++node->num_links_pending;
+                       }
+               }
+               if (node->num_links_pending == 0) {
+                       stack.push(node);
+               }
+               IDDepsNode *id_node = node->owner->owner;
+               id_node->id->flag |= LIB_DOIT;
+       }
+
+       while (!stack.empty()) {
+               OperationDepsNode *node = stack.top();
+               if (node->done == 0 && node->outlinks.size() != 0) {
+                       for (OperationDepsNode::Relations::const_iterator it_rel = node->outlinks.begin();
+                            it_rel != node->outlinks.end();
+                            ++it_rel)
+                       {
+                               DepsRelation *rel = *it_rel;
+                               if (rel->to->type == DEPSNODE_TYPE_OPERATION) {
+                                       OperationDepsNode *to = (OperationDepsNode *)rel->to;
+                                       if ((rel->flag & DEPSREL_FLAG_CYCLIC) == 0) {
+                                               BLI_assert(to->num_links_pending > 0);
+                                               --to->num_links_pending;
+                                       }
+                                       if (to->num_links_pending == 0) {
+                                               stack.push(to);
+                                       }
+                               }
+                       }
+                       node->done = 1;
+               }
+               else {
+                       stack.pop();
+                       IDDepsNode *id_node = node->owner->owner;
+                       for (OperationDepsNode::Relations::const_iterator it_rel = node->outlinks.begin();
+                            it_rel != node->outlinks.end();
+                            ++it_rel)
+                       {
+                               DepsRelation *rel = *it_rel;
+                               if (rel->to->type == DEPSNODE_TYPE_OPERATION) {
+                                       OperationDepsNode *to = (OperationDepsNode *)rel->to;
+                                       IDDepsNode *id_to = to->owner->owner;
+                                       id_node->layers |= id_to->layers;
+                               }
+                       }
+
+                       /* Re-tag ID for update if it was tagged before the relations
+                        * update tag.
+                        */
+                       ID *id = id_node->id;
+                       if (id->flag & LIB_ID_RECALC_ALL &&
+                           id->flag & LIB_DOIT)
+                       {
+                               id_node->tag_update(graph);
+                               id->flag &= ~LIB_DOIT;
+                       }
+               }
+       }
+}
+
+/* ******************** */
+/* Graph Building API's */
+
+/* Build depsgraph for the given scene, and dump results in given graph container */
+// XXX: assume that this is called from outside, given the current scene as the "main" scene
+void DEG_graph_build_from_scene(Depsgraph *graph, Main *bmain, Scene *scene)
+{
+       /* 1) Generate all the nodes in the graph first */
+       DepsgraphNodeBuilder node_builder(bmain, graph);
+       /* create root node for scene first
+        * - this way it should be the first in the graph,
+        *   reflecting its role as the entrypoint
+        */
+       node_builder.add_root_node();
+       node_builder.build_scene(bmain, scene);
+
+       /* 2) Hook up relationships between operations - to determine evaluation order */
+       DepsgraphRelationBuilder relation_builder(graph);
+       /* hook scene up to the root node as entrypoint to graph */
+       /* XXX what does this relation actually mean?
+        * it doesnt add any operations anyway and is not clear what part of the scene is to be connected.
+        */
+       //relation_builder.add_relation(RootKey(), IDKey(scene), DEPSREL_TYPE_ROOT_TO_ACTIVE, "Root to Active Scene");
+       relation_builder.build_scene(bmain, scene);
+
+       /* Detect and solve cycles. */
+       deg_graph_detect_cycles(graph);
+
+       /* 3) Simplify the graph by removing redundant relations (to optimise traversal later) */
+       // TODO: it would be useful to have an option to disable this in cases where it is causing trouble
+       if (G.debug_value == 799) {
+               deg_graph_transitive_reduction(graph);
+       }
+
+       /* 4) Flush visibility layer and re-schedule nodes for update. */
+       deg_graph_build_finalize(graph);
+
+#if 0
+       if (!DEG_debug_consistency_check(graph)) {
+               printf("Consistency validation failed, ABORTING!\n");
+               abort();
+       }
+#endif
+}
+
+/* Tag graph relations for update. */
+void DEG_graph_tag_relations_update(Depsgraph *graph)
+{
+       graph->need_update = true;
+}
+
+/* Tag all relations for update. */
+void DEG_relations_tag_update(Main *bmain)
+{
+       for (Scene *scene = (Scene *)bmain->scene.first;
+            scene != NULL;
+            scene = (Scene *)scene->id.next)
+       {
+               if (scene->depsgraph != NULL) {
+                       DEG_graph_tag_relations_update(scene->depsgraph);
+               }
+       }
+}
+
+/* Create new graph if didn't exist yet,
+ * or update relations if graph was tagged for update.
+ */
+void DEG_scene_relations_update(Main *bmain, Scene *scene)
+{
+       if (scene->depsgraph == NULL) {
+               /* Rebuild graph from scratch and exit. */
+               scene->depsgraph = DEG_graph_new();
+               DEG_graph_build_from_scene(scene->depsgraph, bmain, scene);
+               return;
+       }
+
+       Depsgraph *graph = scene->depsgraph;
+       if (!graph->need_update) {
+               /* Graph is up to date, nothing to do. */
+               return;
+       }
+
+       /* Clear all previous nodes and operations. */
+       graph->clear_all_nodes();
+       graph->operations.clear();
+       graph->entry_tags.clear();
+
+       /* Build new nodes and relations. */
+       DEG_graph_build_from_scene(graph, bmain, scene);
+
+       graph->need_update = false;
+}
+
+/* Rebuild dependency graph only for a given scene. */
+void DEG_scene_relations_rebuild(Main *bmain, Scene *scene)
+{
+       if (scene->depsgraph != NULL) {
+               DEG_graph_tag_relations_update(scene->depsgraph);
+       }
+       DEG_scene_relations_update(bmain, scene);
+}
+
+void DEG_scene_graph_free(Scene *scene)
+{
+       if (scene->depsgraph) {
+               DEG_graph_free(scene->depsgraph);
+               scene->depsgraph = NULL;
+       }
+}
diff --git a/source/blender/depsgraph/intern/depsgraph_build.h b/source/blender/depsgraph/intern/depsgraph_build.h
new file mode 100644 (file)
index 0000000..84c09b8
--- /dev/null
@@ -0,0 +1,404 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Lukas Toenne
+ * Contributor(s): None Yet
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __DEPSGRAPH_BUILD_H__
+#define __DEPSGRAPH_BUILD_H__
+
+struct Base;
+struct bGPdata;
+struct ListBase;
+struct GHash;
+struct ID;
+struct FCurve;
+struct Group;
+struct Key;
+struct Main;
+struct Material;
+struct MTex;
+struct bNodeTree;
+struct Object;
+struct bPoseChannel;
+struct bConstraint;
+struct Scene;
+struct Tex;
+struct World;
+
+struct PropertyRNA;
+
+struct Depsgraph;
+struct DepsNode;
+struct DepsNodeHandle;
+struct RootDepsNode;
+struct SubgraphDepsNode;
+struct IDDepsNode;
+struct TimeSourceDepsNode;
+struct ComponentDepsNode;
+struct OperationDepsNode;
+struct RootPChanMap;
+
+struct DepsgraphNodeBuilder {
+       DepsgraphNodeBuilder(Main *bmain, Depsgraph *graph);
+       ~DepsgraphNodeBuilder();
+
+       RootDepsNode *add_root_node();
+       IDDepsNode *add_id_node(ID *id);
+       TimeSourceDepsNode *add_time_source(ID *id);
+
+       ComponentDepsNode *add_component_node(ID *id, eDepsNode_Type comp_type, const string &comp_name = "");
+
+       OperationDepsNode *add_operation_node(ComponentDepsNode *comp_node, eDepsOperation_Type optype,
+                                             DepsEvalOperationCb op, eDepsOperation_Code opcode, const string &description = "");
+       OperationDepsNode *add_operation_node(ID *id, eDepsNode_Type comp_type, const string &comp_name, eDepsOperation_Type optype,
+                                             DepsEvalOperationCb op, eDepsOperation_Code opcode, const string &description = "");
+       OperationDepsNode *add_operation_node(ID *id, eDepsNode_Type comp_type, eDepsOperation_Type optype,
+                                             DepsEvalOperationCb op, eDepsOperation_Code opcode, const string &description = "")
+       {
+               return add_operation_node(id, comp_type, "", optype, op, opcode, description);
+       }
+
+       bool has_operation_node(ID *id, eDepsNode_Type comp_type, const string &comp_name,
+                               eDepsOperation_Code opcode, const string &description = "");
+
+       OperationDepsNode *find_operation_node(ID *id,
+                                              eDepsNode_Type comp_type,
+                                              const string &comp_name,
+                                              eDepsOperation_Code opcode,
+                                              const string &description = "");
+
+       OperationDepsNode *find_operation_node(ID *id,
+                                              eDepsNode_Type comp_type,
+                                              eDepsOperation_Code opcode,
+                                              const string &description = "")
+       {
+               return find_operation_node(id, comp_type, "", opcode, description);
+       }
+
+       void build_scene(Main *bmain, Scene *scene);
+       SubgraphDepsNode *build_subgraph(Group *group);
+       void build_group(Scene *scene, Base *base, Group *group);
+       void build_object(Scene *scene, Base *base, Object *ob);
+       void build_object_transform(Scene *scene, Object *ob);
+       void build_object_constraints(Scene *scene, Object *ob);
+       void build_pose_constraints(Object *ob, bPoseChannel *pchan);
+       void build_rigidbody(Scene *scene);
+       void build_particles(Object *ob);
+       void build_animdata(ID *id);
+       OperationDepsNode *build_driver(ID *id, FCurve *fcurve);
+       void build_ik_pose(Scene *scene, Object *ob, bPoseChannel *pchan, bConstraint *con);
+       void build_splineik_pose(Scene *scene, Object *ob, bPoseChannel *pchan, bConstraint *con);
+       void build_rig(Scene *scene, Object *ob);
+       void build_proxy_rig(Object *ob);
+       void build_shapekeys(Key *key);
+       void build_obdata_geom(Scene *scene, Object *ob);
+       void build_camera(Object *ob);
+       void build_lamp(Object *ob);
+       void build_nodetree(DepsNode *owner_node, bNodeTree *ntree);
+       void build_material(DepsNode *owner_node, Material *ma);
+       void build_texture(DepsNode *owner_node, Tex *tex);
+       void build_texture_stack(DepsNode *owner_node, MTex **texture_stack);
+       void build_world(World *world);
+       void build_compositor(Scene *scene);
+       void build_gpencil(bGPdata *gpd);
+
+private:
+       Main *m_bmain;
+       Depsgraph *m_graph;
+};
+
+struct RootKey
+{
+       RootKey() {}
+};
+
+struct TimeSourceKey
+{
+       TimeSourceKey() : id(NULL) {}
+       TimeSourceKey(ID *id) : id(id) {}
+
+       string identifier() const
+       {
+               return string("TimeSourceKey");
+       }
+
+       ID *id;
+};
+
+struct ComponentKey
+{
+       ComponentKey() :
+           id(NULL), type(DEPSNODE_TYPE_UNDEFINED), name("")
+       {}
+       ComponentKey(ID *id, eDepsNode_Type type, const string &name = "") :
+           id(id), type(type), name(name)
+       {}
+
+       string identifier() const
+       {
+               const char *idname = (id) ? id->name : "<None>";
+
+               char typebuf[5];
+               sprintf(typebuf, "%d", type);
+
+               return string("ComponentKey(") + idname + ", " + typebuf + ", '" + name + "')";
+       }
+
+       ID *id;
+       eDepsNode_Type type;
+       string name;
+};
+
+struct OperationKey
+{
+       OperationKey() :
+           id(NULL), component_type(DEPSNODE_TYPE_UNDEFINED), component_name(""), opcode(DEG_OPCODE_OPERATION), name("")
+       {}
+
+       OperationKey(ID *id, eDepsNode_Type component_type, const string &name) :
+           id(id), component_type(component_type), component_name(""), opcode(DEG_OPCODE_OPERATION), name(name)
+       {}
+       OperationKey(ID *id, eDepsNode_Type component_type, const string &component_name, const string &name) :
+           id(id), component_type(component_type), component_name(component_name), opcode(DEG_OPCODE_OPERATION), name(name)
+       {}
+
+       OperationKey(ID *id, eDepsNode_Type component_type, eDepsOperation_Code opcode) :
+           id(id), component_type(component_type), component_name(""), opcode(opcode), name("")
+       {}
+       OperationKey(ID *id, eDepsNode_Type component_type, const string &component_name, eDepsOperation_Code opcode) :
+           id(id), component_type(component_type), component_name(component_name), opcode(opcode), name("")
+       {}
+
+       OperationKey(ID *id, eDepsNode_Type component_type, eDepsOperation_Code opcode, const string &name) :
+           id(id), component_type(component_type), component_name(""), opcode(opcode), name(name)
+       {}
+       OperationKey(ID *id, eDepsNode_Type component_type, const string &component_name, eDepsOperation_Code opcode, const string &name) :
+           id(id), component_type(component_type), component_name(component_name), opcode(opcode), name(name)
+       {}
+
+       string identifier() const
+       {
+               char typebuf[5];
+               sprintf(typebuf, "%d", component_type);
+
+               return string("OperationKey(") + "t: " + typebuf + ", cn: '" + component_name + "', c: " + DEG_OPNAMES[opcode] + ", n: '" + name + "')";
+       }
+
+
+       ID *id;
+       eDepsNode_Type component_type;
+       string component_name;
+       eDepsOperation_Code opcode;
+       string name;
+};
+
+struct RNAPathKey
+{
+       // Note: see depsgraph_build.cpp for implementation
+       RNAPathKey(ID *id, const string &path);
+
+       RNAPathKey(ID *id, const PointerRNA &ptr, PropertyRNA *prop) :
+           id(id), ptr(ptr), prop(prop)
+       {}
+
+       string identifier() const
+       {
+               const char *id_name   = (id) ?  id->name : "<No ID>";
+               const char *prop_name = (prop) ? RNA_property_identifier(prop) : "<No Prop>";
+
+               return string("RnaPathKey(") + "id: " + id_name + ", prop: " + prop_name +  "')";
+       }
+
+
+       ID *id;
+       PointerRNA ptr;
+       PropertyRNA *prop;
+};
+
+struct DepsgraphRelationBuilder
+{
+       DepsgraphRelationBuilder(Depsgraph *graph);
+
+       template <typename KeyFrom, typename KeyTo>
+       void add_relation(const KeyFrom &key_from, const KeyTo &key_to,
+                         eDepsRelation_Type type, const char *description);
+
+       template <typename KeyTo>
+       void add_relation(const TimeSourceKey &key_from, const KeyTo &key_to,
+                         eDepsRelation_Type type, const char *description);
+
+       template <typename KeyType>
+       void add_node_handle_relation(const KeyType &key_from, const DepsNodeHandle *handle,
+                                     eDepsRelation_Type type, const char *description);
+
+       void build_scene(Main *bmain, Scene *scene);
+       void build_group(Main *bmain, Scene *scene, Object *object, Group *group);
+       void build_object(Main *bmain, Scene *scene, Object *ob);
+       void build_object_parent(Object *ob);
+       void build_constraints(Scene *scene, ID *id, eDepsNode_Type component_type, const char *component_subdata,
+                              ListBase *constraints, RootPChanMap *root_map);
+       void build_animdata(ID *id);
+       void build_driver(ID *id, FCurve *fcurve);
+       void build_world(World *world);
+       void build_rigidbody(Scene *scene);
+       void build_particles(Scene *scene, Object *ob);
+       void build_ik_pose(Object *ob, bPoseChannel *pchan, bConstraint *con, RootPChanMap *root_map);
+       void build_splineik_pose(Object *ob, bPoseChannel *pchan, bConstraint *con, RootPChanMap *root_map);
+       void build_rig(Scene *scene, Object *ob);
+       void build_proxy_rig(Object *ob);
+       void build_shapekeys(ID *obdata, Key *key);
+       void build_obdata_geom(Main *bmain, Scene *scene, Object *ob);
+       void build_camera(Object *ob);
+       void build_lamp(Object *ob);
+       void build_nodetree(ID *owner, bNodeTree *ntree);
+       void build_material(ID *owner, Material *ma);
+       void build_texture(ID *owner, Tex *tex);
+       void build_texture_stack(ID *owner, MTex **texture_stack);
+       void build_compositor(Scene *scene);
+       void build_gpencil(ID *owner, bGPdata *gpd);
+
+protected:
+       RootDepsNode *find_node(const RootKey &key) const;
+       TimeSourceDepsNode *find_node(const TimeSourceKey &key) const;
+       ComponentDepsNode *find_node(const ComponentKey &key) const;
+       OperationDepsNode *find_node(const OperationKey &key) const;
+       DepsNode *find_node(const RNAPathKey &key) const;
+       OperationDepsNode *has_node(const OperationKey &key) const;
+
+       void add_time_relation(TimeSourceDepsNode *timesrc, DepsNode *node_to, const char *description);
+       void add_operation_relation(OperationDepsNode *node_from, OperationDepsNode *node_to,
+                                   eDepsRelation_Type type, const char *description);
+
+       template <typename KeyType>
+       DepsNodeHandle create_node_handle(const KeyType &key, const string &default_name = "");
+
+       bool needs_animdata_node(ID *id);
+
+private:
+       Depsgraph *m_graph;
+};
+
+struct DepsNodeHandle
+{
+       DepsNodeHandle(DepsgraphRelationBuilder *builder, OperationDepsNode *node, const string &default_name = "") :
+           builder(builder),
+           node(node),
+           default_name(default_name)
+       {
+               BLI_assert(node != NULL);
+       }
+
+       DepsgraphRelationBuilder *builder;
+       OperationDepsNode *node;
+       const string &default_name;
+};
+
+/* Utilities for Builders ----------------------------------------------------- */
+
+/* Get unique identifier for FCurves and Drivers */
+string deg_fcurve_id_name(const FCurve *fcu);
+
+template <typename KeyFrom, typename KeyTo>
+void DepsgraphRelationBuilder::add_relation(const KeyFrom &key_from,
+                                            const KeyTo &key_to,
+                                            eDepsRelation_Type type,
+                                            const char *description)
+{
+       DepsNode *node_from = find_node(key_from);
+       DepsNode *node_to = find_node(key_to);
+       OperationDepsNode *op_from = node_from ? node_from->get_exit_operation() : NULL;
+       OperationDepsNode *op_to = node_to ? node_to->get_entry_operation() : NULL;
+       if (op_from && op_to) {
+               add_operation_relation(op_from, op_to, type, description);
+       }
+       else {
+               if (!op_from) {
+                       /* XXX TODO handle as error or report if needed */
+                       fprintf(stderr, "add_relation(%d, %s) - Could not find op_from (%s)\n",
+                               type, description, key_from.identifier().c_str());
+               }
+               else {
+                       fprintf(stderr, "add_relation(%d, %s) - Failed, but op_from (%s) was ok\n",
+                               type, description, key_from.identifier().c_str());
+               }
+               if (!op_to) {
+                       /* XXX TODO handle as error or report if needed */
+                       fprintf(stderr, "add_relation(%d, %s) - Could not find op_to (%s)\n",
+                               type, description, key_to.identifier().c_str());
+               }
+               else {
+                       fprintf(stderr, "add_relation(%d, %s) - Failed, but op_to (%s) was ok\n",
+                               type, description, key_to.identifier().c_str());
+               }
+       }
+}
+
+template <typename KeyTo>
+void DepsgraphRelationBuilder::add_relation(const TimeSourceKey &key_from,
+                                            const KeyTo &key_to,
+                                            eDepsRelation_Type type,
+                                            const char *description)
+{
+       (void)type;  /* Ignored in release builds. */
+       BLI_assert(type == DEPSREL_TYPE_TIME);
+       TimeSourceDepsNode *time_from = find_node(key_from);
+       DepsNode *node_to = find_node(key_to);
+       OperationDepsNode *op_to = node_to ? node_to->get_entry_operation() : NULL;
+       if (time_from && op_to) {
+               add_time_relation(time_from, op_to, description);
+       }
+       else {
+       }
+}
+
+template <typename KeyType>
+void DepsgraphRelationBuilder::add_node_handle_relation(const KeyType &key_from,
+                                                        const DepsNodeHandle *handle,
+                                                        eDepsRelation_Type type,
+                                                        const char *description)
+{
+       DepsNode *node_from = find_node(key_from);
+       OperationDepsNode *op_from = node_from ? node_from->get_exit_operation() : NULL;
+       OperationDepsNode *op_to = handle->node->get_entry_operation();
+       if (op_from && op_to) {
+               add_operation_relation(op_from, op_to, type, description);
+       }
+       else {
+               if (!op_from) {
+                       /* XXX TODO handle as error or report if needed */
+               }
+               if (!op_to) {
+                       /* XXX TODO handle as error or report if needed */
+               }
+       }
+}
+
+template <typename KeyType>
+DepsNodeHandle DepsgraphRelationBuilder::create_node_handle(const KeyType &key,
+                                                            const string &default_name)
+{
+       return DepsNodeHandle(this, find_node(key), default_name);
+}
+
+#endif  /* __DEPSGRAPH_BUILD_H__ */
diff --git a/source/blender/depsgraph/intern/depsgraph_build_nodes.cc b/source/blender/depsgraph/intern/depsgraph_build_nodes.cc
new file mode 100644 (file)
index 0000000..a55fb90
--- /dev/null
@@ -0,0 +1,1199 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Joshua Leung
+ * Contributor(s): Based on original depsgraph.c code - Blender Foundation (2005-2013)
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ *
+ * Methods for constructing depsgraph's nodes
+ */
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "MEM_guardedalloc.h"
+
+extern "C" {
+#include "BLI_blenlib.h"
+#include "BLI_string.h"
+#include "BLI_utildefines.h"
+
+#include "DNA_action_types.h"
+#include "DNA_anim_types.h"
+#include "DNA_armature_types.h"
+#include "DNA_camera_types.h"
+#include "DNA_constraint_types.h"
+#include "DNA_curve_types.h"
+#include "DNA_effect_types.h"
+#include "DNA_gpencil_types.h"
+#include "DNA_group_types.h"
+#include "DNA_key_types.h"
+#include "DNA_lamp_types.h"
+#include "DNA_material_types.h"
+#include "DNA_mesh_types.h"
+#include "DNA_meta_types.h"
+#include "DNA_node_types.h"
+#include "DNA_particle_types.h"
+#include "DNA_object_types.h"
+#include "DNA_rigidbody_types.h"
+#include "DNA_scene_types.h"
+#include "DNA_texture_types.h"
+#include "DNA_world_types.h"
+
+#include "BKE_action.h"
+#include "BKE_armature.h"
+#include "BKE_animsys.h"
+#include "BKE_constraint.h"
+#include "BKE_curve.h"
+#include "BKE_depsgraph.h"
+#include "BKE_effect.h"
+#include "BKE_fcurve.h"
+#include "BKE_idcode.h"
+#include "BKE_group.h"
+#include "BKE_key.h"
+#include "BKE_lattice.h"
+#include "BKE_library.h"
+#include "BKE_main.h"
+#include "BKE_material.h"
+#include "BKE_mesh.h"
+#include "BKE_mball.h"
+#include "BKE_modifier.h"
+#include "BKE_node.h"
+#include "BKE_object.h"
+#include "BKE_particle.h"
+#include "BKE_rigidbody.h"
+#include "BKE_sound.h"
+#include "BKE_texture.h"
+#include "BKE_tracking.h"
+#include "BKE_world.h"
+
+#include "DEG_depsgraph.h"
+#include "DEG_depsgraph_build.h"
+
+#include "RNA_access.h"
+#include "RNA_types.h"
+} /* extern "C" */
+
+#include "depsnode.h"
+#include "depsnode_component.h"
+#include "depsnode_operation.h"
+#include "depsgraph_types.h"
+#include "depsgraph_build.h"
+#include "depsgraph_intern.h"
+
+/* ************ */
+/* Node Builder */
+
+/* **** General purpose functions **** */
+
+DepsgraphNodeBuilder::DepsgraphNodeBuilder(Main *bmain, Depsgraph *graph) :
+    m_bmain(bmain),
+    m_graph(graph)
+{
+}
+
+DepsgraphNodeBuilder::~DepsgraphNodeBuilder()
+{
+}
+
+RootDepsNode *DepsgraphNodeBuilder::add_root_node()
+{
+       return m_graph->add_root_node();
+}
+
+IDDepsNode *DepsgraphNodeBuilder::add_id_node(ID *id)
+{
+       const char *idtype_name = BKE_idcode_to_name(GS(id->name));
+       return m_graph->add_id_node(id, string(id->name+2) + "[" + idtype_name + "]");
+}
+
+TimeSourceDepsNode *DepsgraphNodeBuilder::add_time_source(ID *id)
+{
+       /* determine which node to attach timesource to */
+       if (id) {
+#if 0 /* XXX TODO */
+               /* get ID node */
+               IDDepsNode id_node = m_graph->find_id_node(id);
+
+               /* depends on what this is... */
+               switch (GS(id->name)) {
+                       case ID_SCE: /* Scene - Usually sequencer strip causing time remapping... */
+                       {
+                               // TODO...
+                       }
+                       break;
+
+                       case ID_GR: /* Group */
+                       {
+                               // TODO...
+                       }
+                       break;
+
+                       // XXX: time source...
+
+                       default:     /* Unhandled */
+                               printf("%s(): Unhandled ID - %s \n", __func__, id->name);
+                               break;
+               }
+#endif
+       }
+       else {
+               /* root-node */
+               RootDepsNode *root_node = m_graph->root_node;
+               if (root_node) {
+                       return root_node->add_time_source("Time Source");
+               }
+       }
+
+       return NULL;
+}
+
+ComponentDepsNode *DepsgraphNodeBuilder::add_component_node(
+        ID *id,
+        eDepsNode_Type comp_type,
+        const string &comp_name)
+{
+       IDDepsNode *id_node = add_id_node(id);
+       ComponentDepsNode *comp_node = id_node->add_component(comp_type, comp_name);
+       comp_node->owner = id_node;
+       return comp_node;
+}
+
+OperationDepsNode *DepsgraphNodeBuilder::add_operation_node(
+        ComponentDepsNode *comp_node,
+        eDepsOperation_Type optype,
+        DepsEvalOperationCb op,
+        eDepsOperation_Code opcode,
+        const string &description)
+{
+       OperationDepsNode *op_node = comp_node->has_operation(opcode, description);
+       if (op_node == NULL) {
+               op_node = comp_node->add_operation(optype, op, opcode, description);
+               m_graph->operations.push_back(op_node);
+       }
+       else {
+               fprintf(stderr, "add_operation: Operation already exists - %s has %s at %p\n",
+                       comp_node->identifier().c_str(),
+                       op_node->identifier().c_str(),
+                       op_node);
+               BLI_assert(!"Should not happen!");
+       }
+       return op_node;
+}
+
+OperationDepsNode *DepsgraphNodeBuilder::add_operation_node(
+        ID *id,
+        eDepsNode_Type comp_type,
+        const string &comp_name,
+        eDepsOperation_Type optype,
+        DepsEvalOperationCb op,
+        eDepsOperation_Code opcode,
+        const string &description)
+{
+       ComponentDepsNode *comp_node = add_component_node(id, comp_type, comp_name);
+       return add_operation_node(comp_node, optype, op, opcode, description);
+}
+
+bool DepsgraphNodeBuilder::has_operation_node(ID *id,
+                                              eDepsNode_Type comp_type,
+                                              const string &comp_name,
+                                              eDepsOperation_Code opcode,
+                                              const string &description)
+{
+       return find_operation_node(id, comp_type, comp_name, opcode, description) != NULL;
+}
+
+OperationDepsNode *DepsgraphNodeBuilder::find_operation_node(
+        ID *id,
+        eDepsNode_Type comp_type,
+        const string &comp_name,
+        eDepsOperation_Code opcode,
+        const string &description)
+{
+       ComponentDepsNode *comp_node = add_component_node(id, comp_type, comp_name);
+       return comp_node->has_operation(opcode, description);
+}
+
+
+/* **** Build functions for entity nodes **** */
+
+void DepsgraphNodeBuilder::build_scene(Main *bmain, Scene *scene)
+{
+       /* LIB_DOIT is used to indicate whether node for given ID was already
+        * created or not. This flag is being set in add_id_node(), so functions
+        * shouldn't bother with setting it, they only might query this flag when
+        * needed.
+        */
+       BKE_main_id_tag_all(bmain, false);
+
+       /* scene ID block */
+       add_id_node(&scene->id);
+
+       /* timesource */
+       add_time_source(NULL);
+
+       /* build subgraph for set, and link this in... */
+       // XXX: depending on how this goes, that scene itself could probably store its
+       //      own little partial depsgraph?
+       if (scene->set) {
+               build_scene(bmain, scene->set);
+       }
+
+       /* scene objects */
+       for (Base *base = (Base *)scene->base.first; base; base = base->next) {
+               Object *ob = base->object;
+
+               /* object itself */
+               build_object(scene, base, ob);
+
+               /* object that this is a proxy for */
+               // XXX: the way that proxies work needs to be completely reviewed!
+               if (ob->proxy) {
+                       build_object(scene, base, ob->proxy);
+               }
+
+               /* Object dupligroup. */
+               if (ob->dup_group) {
+                       build_group(scene, base, ob->dup_group);
+               }
+       }
+
+       /* rigidbody */
+       if (scene->rigidbody_world) {
+               build_rigidbody(scene);
+       }
+
+       /* scene's animation and drivers */
+       if (scene->adt) {
+               build_animdata(&scene->id);
+       }
+
+       /* world */
+       if (scene->world) {
+               build_world(scene->world);
+       }
+
+       /* compo nodes */
+       if (scene->nodetree) {
+               build_compositor(scene);
+       }
+
+       /* sequencer */
+       // XXX...
+
+       /* grease pencil */
+       if (scene->gpd) {
+               build_gpencil(scene->gpd);
+       }
+}
+
+void DepsgraphNodeBuilder::build_group(Scene *scene,
+                                       Base *base,
+                                       Group *group)
+{
+       ID *group_id = &group->id;
+       if (group_id->flag & LIB_DOIT) {
+               return;
+       }
+       group_id->flag |= LIB_DOIT;
+
+       for (GroupObject *go = (GroupObject *)group->gobject.first;
+            go != NULL;
+            go = go->next)
+       {
+               build_object(scene, base, go->ob);
+       }
+}
+
+SubgraphDepsNode *DepsgraphNodeBuilder::build_subgraph(Group *group)
+{
+       /* sanity checks */
+       if (!group)
+               return NULL;
+
+       /* create new subgraph's data */
+       Depsgraph *subgraph = DEG_graph_new();
+
+       DepsgraphNodeBuilder subgraph_builder(m_bmain, subgraph);
+
+       /* add group objects */
+       for (GroupObject *go = (GroupObject *)group->gobject.first;
+            go != NULL;
+            go = go->next)
+       {
+               /*Object *ob = go->ob;*/
+
+               /* Each "group object" is effectively a separate instance of the underlying
+                * object data. When the group is evaluated, the transform results and/or
+                * some other attributes end up getting overridden by the group
+                */
+       }
+
+       /* create a node for representing subgraph */
+       SubgraphDepsNode *subgraph_node = m_graph->add_subgraph_node(&group->id);
+       subgraph_node->graph = subgraph;
+
+       /* make a copy of the data this node will need? */
+       // XXX: do we do this now, or later?
+       // TODO: need API function which queries graph's ID's hash, and duplicates those blocks thoroughly with all outside links removed...
+
+       return subgraph_node;
+}
+
+void DepsgraphNodeBuilder::build_object(Scene *scene, Base *base, Object *ob)
+{
+       if (ob->id.flag & LIB_DOIT) {
+               IDDepsNode *id_node = m_graph->find_id_node(&ob->id);
+               id_node->layers = base->lay;
+               return;
+       }
+
+       IDDepsNode *id_node = add_id_node(&ob->id);
+       id_node->layers = base->lay;
+
+       /* standard components */
+       build_object_transform(scene, ob);
+
+
+       /* object data */
+       if (ob->data) {
+               /* type-specific data... */
+               switch (ob->type) {
+                       case OB_MESH:     /* Geometry */
+                       case OB_CURVE:
+                       case OB_FONT:
+                       case OB_SURF:
+                       case OB_MBALL:
+                       case OB_LATTICE:
+                       {
+                               /* TODO(sergey): This way using this object's
+                                * properties as driver target works fine.
+                                *
+                                * Does this depend on other nodes?
+                                */
+                               add_operation_node(&ob->id, DEPSNODE_TYPE_PARAMETERS, DEPSOP_TYPE_POST, NULL,
+                                                  DEG_OPCODE_PLACEHOLDER, "Parameters Eval");
+
+                               build_obdata_geom(scene, ob);
+                               /* TODO(sergey): Only for until we support granular
+                                * update of curves.
+                                */
+                               if (ob->type == OB_FONT) {
+                                       Curve *curve = (Curve *)ob->data;
+                                       if (curve->textoncurve) {
+                                               id_node->eval_flags |= DAG_EVAL_NEED_CURVE_PATH;
+                                       }
+                               }
+                       }
+                       break;
+
+                       case OB_ARMATURE: /* Pose */
+                               if (ob->id.lib != NULL && ob->proxy_from != NULL) {
+                                       build_proxy_rig(ob);
+                               }
+                               else {
+                                       build_rig(scene, ob);
+                               }
+                               break;
+
+                       case OB_LAMP:   /* Lamp */
+                               build_lamp(ob);
+                               break;
+
+                       case OB_CAMERA: /* Camera */
+                               build_camera(ob);
+                               break;
+
+                       default:
+                       {
+                               ID *obdata = (ID *)ob->data;
+                               if ((obdata->flag & LIB_DOIT) == 0) {
+                                       build_animdata(obdata);
+                               }
+                               break;
+                       }
+               }
+       }
+
+       /* Build animation data,
+        *
+        * Do it now because it's possible object data will affect
+        * on object's level animation, for example in case of rebuilding
+        * pose for proxy.
+        */
+       build_animdata(&ob->id);
+
+       /* particle systems */
+       if (ob->particlesystem.first) {
+               build_particles(ob);
+       }
+
+       /* grease pencil */
+       if (ob->gpd) {
+               build_gpencil(ob->gpd);
+       }
+}
+
+void DepsgraphNodeBuilder::build_object_transform(Scene *scene, Object *ob)
+{
+       /* local transforms (from transform channels - loc/rot/scale + deltas) */
+       add_operation_node(&ob->id, DEPSNODE_TYPE_TRANSFORM,
+                          DEPSOP_TYPE_INIT, function_bind(BKE_object_eval_local_transform, _1, scene, ob),
+                          DEG_OPCODE_TRANSFORM_LOCAL);
+
+       /* object parent */
+       if (ob->parent) {
+               add_operation_node(&ob->id, DEPSNODE_TYPE_TRANSFORM,
+                                  DEPSOP_TYPE_EXEC, function_bind(BKE_object_eval_parent, _1, scene, ob),
+                                  DEG_OPCODE_TRANSFORM_PARENT);
+       }
+
+       /* object constraints */
+       if (ob->constraints.first) {
+               build_object_constraints(scene, ob);
+       }
+
+       /* Temporary uber-update node, which does everything.
+        * It is for the being we're porting old dependencies into the new system.
+        * We'll get rid of this node as soon as all the granular update functions
+        * are filled in.
+        *
+        * TODO(sergey): Get rid of this node.
+        */
+       add_operation_node(&ob->id, DEPSNODE_TYPE_TRANSFORM,
+                          DEPSOP_TYPE_EXEC, function_bind(BKE_object_eval_uber_transform, _1, scene, ob),
+                          DEG_OPCODE_OBJECT_UBEREVAL);
+
+       /* object transform is done */
+       add_operation_node(&ob->id, DEPSNODE_TYPE_TRANSFORM,
+                          DEPSOP_TYPE_POST, function_bind(BKE_object_eval_done, _1, ob),
+                          DEG_OPCODE_TRANSFORM_FINAL);
+}
+
+/**
+ * Constraints Graph Notes
+ *
+ * For constraints, we currently only add a operation node to the Transform
+ * or Bone components (depending on whichever type of owner we have).
+ * This represents the entire constraints stack, which is for now just
+ * executed as a single monolithic block. At least initially, this should
+ * be sufficient for ensuring that the porting/refactoring process remains
+ * manageable.
+ *
+ * However, when the time comes for developing "node-based" constraints,
+ * we'll need to split this up into pre/post nodes for "constraint stack
+ * evaluation" + operation nodes for each constraint (i.e. the contents
+ * of the loop body used in the current "solve_constraints()" operation).
+ *
+ * -- Aligorith, August 2013
+ */
+void DepsgraphNodeBuilder::build_object_constraints(Scene *scene, Object *ob)
+{
+       /* create node for constraint stack */
+       add_operation_node(&ob->id, DEPSNODE_TYPE_TRANSFORM,
+                          DEPSOP_TYPE_EXEC, function_bind(BKE_object_eval_constraints, _1, scene, ob),
+                          DEG_OPCODE_TRANSFORM_CONSTRAINTS);
+}
+
+void DepsgraphNodeBuilder::build_pose_constraints(Object *ob, bPoseChannel *pchan)
+{
+       /* create node for constraint stack */
+       add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name,
+                          DEPSOP_TYPE_EXEC, function_bind(BKE_pose_constraints_evaluate, _1, ob, pchan),
+                          DEG_OPCODE_BONE_CONSTRAINTS);
+}
+
+/**
+ * Build graph nodes for AnimData block
+ * \param scene_node: Scene that ID-block this lives on belongs to
+ * \param id: ID-Block which hosts the AnimData
+ */
+void DepsgraphNodeBuilder::build_animdata(ID *id)
+{
+       AnimData *adt = BKE_animdata_from_id(id);
+
+       if (adt == NULL)
+               return;
+
+       /* animation */
+       if (adt->action || adt->nla_tracks.first || adt->drivers.first) {
+               // XXX: Hook up specific update callbacks for special properties which may need it...
+
+               /* actions and NLA - as a single unit for now, as it gets complicated to schedule otherwise */
+               if ((adt->action) || (adt->nla_tracks.first)) {
+                       /* create the node */
+                       add_operation_node(id, DEPSNODE_TYPE_ANIMATION,
+                                          DEPSOP_TYPE_EXEC, function_bind(BKE_animsys_eval_animdata, _1, id),
+                                          DEG_OPCODE_ANIMATION, id->name);
+
+                       // TODO: for each channel affected, we might also want to add some support for running RNA update callbacks on them
+                       // (which will be needed for proper handling of drivers later)
+               }
+
+               /* drivers */
+               for (FCurve *fcu = (FCurve *)adt->drivers.first; fcu; fcu = fcu->next) {
+                       /* create driver */
+                       build_driver(id, fcu);
+               }
+       }
+}
+
+/**
+ * Build graph node(s) for Driver
+ * \param id: ID-Block that driver is attached to
+ * \param fcu: Driver-FCurve
+ */
+OperationDepsNode *DepsgraphNodeBuilder::build_driver(ID *id, FCurve *fcu)
+{
+       ChannelDriver *driver = fcu->driver;
+
+       /* Create data node for this driver */
+       /* TODO(sergey): Avoid creating same operation multiple times,
+        * in the future we need to avoid lookup of the operation as well
+        * and use some tagging magic instead.
+        */
+       OperationDepsNode *driver_op = find_operation_node(id,
+                                                          DEPSNODE_TYPE_PARAMETERS,
+                                                          DEG_OPCODE_DRIVER,
+                                                          deg_fcurve_id_name(fcu));
+
+       if (driver_op == NULL) {
+               driver_op = add_operation_node(id, DEPSNODE_TYPE_PARAMETERS,
+                                              DEPSOP_TYPE_EXEC, function_bind(BKE_animsys_eval_driver, _1, id, fcu),
+                                              DEG_OPCODE_DRIVER, deg_fcurve_id_name(fcu));
+       }
+
+       /* tag "scripted expression" drivers as needing Python (due to GIL issues, etc.) */
+       if (driver->type == DRIVER_TYPE_PYTHON) {
+               driver_op->flag |= DEPSOP_FLAG_USES_PYTHON;
+       }
+
+       /* return driver node created */
+       return driver_op;
+}
+
+/* Recursively build graph for world */
+void DepsgraphNodeBuilder::build_world(World *world)
+{
+       ID *world_id = &world->id;
+       if (world_id->flag & LIB_DOIT) {
+               return;
+       }
+
+       /* world itself */
+       IDDepsNode *world_node = add_id_node(world_id); /* world shading/params? */
+
+       build_animdata(world_id);
+
+       /* TODO: other settings? */
+
+       /* textures */
+       build_texture_stack(world_node, world->mtex);
+
+       /* world's nodetree */
+       if (world->nodetree) {
+               build_nodetree(world_node, world->nodetree);
+       }
+}
+
+/* Rigidbody Simulation - Scene Level */
+void DepsgraphNodeBuilder::build_rigidbody(Scene *scene)
+{
+       RigidBodyWorld *rbw = scene->rigidbody_world;
+
+       /**
+        * Rigidbody Simulation Nodes
+        * ==========================
+        *
+        * There are 3 nodes related to Rigidbody Simulation:
+        * 1) "Initialize/Rebuild World" - this is called sparingly, only when the simulation
+        *    needs to be rebuilt (mainly after file reload, or moving back to start frame)
+        * 2) "Do Simulation" - perform a simulation step - interleaved between the evaluation
+        *    steps for clusters of objects (i.e. between those affected and/or not affected by
+        *    the sim for instance)
+        *
+        * 3) "Pull Results" - grab the specific transforms applied for a specific object -
+        *    performed as part of object's transform-stack building
+        */
+
+       /* create nodes ------------------------------------------------------------------------ */
+       /* XXX: is this the right component, or do we want to use another one instead? */
+
+       /* init/rebuild operation */
+       /*OperationDepsNode *init_node =*/ add_operation_node(&scene->id, DEPSNODE_TYPE_TRANSFORM,
+                                                             DEPSOP_TYPE_REBUILD, function_bind(BKE_rigidbody_rebuild_sim, _1, scene),
+                                                             DEG_OPCODE_RIGIDBODY_REBUILD);
+
+       /* do-sim operation */
+       // XXX: what happens if we need to split into several groups?
+       OperationDepsNode *sim_node     = add_operation_node(&scene->id, DEPSNODE_TYPE_TRANSFORM,
+                                                            DEPSOP_TYPE_SIM, function_bind(BKE_rigidbody_eval_simulation, _1, scene),
+                                                            DEG_OPCODE_RIGIDBODY_SIM);
+
+       /* XXX: For now, the sim node is the only one that really matters here. If any other
+        * sims get added later, we may have to remove these hacks...
+        */
+       sim_node->owner->entry_operation = sim_node;
+       sim_node->owner->exit_operation  = sim_node;
+
+
+       /* objects - simulation participants */
+       if (rbw->group) {
+               for (GroupObject *go = (GroupObject *)rbw->group->gobject.first; go; go = go->next) {
+                       Object *ob = go->ob;
+
+                       if (!ob || (ob->type != OB_MESH))
+                               continue;
+
+                       /* 2) create operation for flushing results */
+                       /* object's transform component - where the rigidbody operation lives */
+                       add_operation_node(&ob->id, DEPSNODE_TYPE_TRANSFORM,
+                                          DEPSOP_TYPE_EXEC, function_bind(BKE_rigidbody_object_sync_transforms, _1, scene, ob),
+                                          DEG_OPCODE_TRANSFORM_RIGIDBODY);
+               }
+       }
+}
+
+void DepsgraphNodeBuilder::build_particles(Object *ob)
+{
+       /**
+        * Particle Systems Nodes
+        * ======================
+        *
+        * There are two types of nodes associated with representing
+        * particle systems:
+        *  1) Component (EVAL_PARTICLES) - This is the particle-system
+        *     evaluation context for an object. It acts as the container
+        *     for all the nodes associated with a particular set of particle
+        *     systems.
+        *  2) Particle System Eval Operation - This operation node acts as a
+        *     blackbox evaluation step for one particle system referenced by
+        *     the particle systems stack. All dependencies link to this operation.
+        */
+
+       /* component for all particle systems */
+       ComponentDepsNode *psys_comp = add_component_node(&ob->id, DEPSNODE_TYPE_EVAL_PARTICLES);
+
+       /* particle systems */
+       for (ParticleSystem *psys = (ParticleSystem *)ob->particlesystem.first; psys; psys = psys->next) {
+               ParticleSettings *part = psys->part;
+
+               /* particle settings */
+               // XXX: what if this is used more than once!
+               build_animdata(&part->id);
+
+               /* this particle system */
+               // TODO: for now, this will just be a placeholder "ubereval" node
+               add_operation_node(psys_comp,
+                                  DEPSOP_TYPE_EXEC, function_bind(BKE_particle_system_eval, _1, ob, psys),
+                                  DEG_OPCODE_PSYS_EVAL,
+                                  psys->name);
+       }
+
+       /* pointcache */
+       // TODO...
+}
+
+/* IK Solver Eval Steps */
+void DepsgraphNodeBuilder::build_ik_pose(Scene *scene, Object *ob, bPoseChannel *pchan, bConstraint *con)
+{
+       bKinematicConstraint *data = (bKinematicConstraint *)con->data;
+
+       /* Find the chain's root. */
+       bPoseChannel *rootchan = BKE_armature_ik_solver_find_root(pchan, data);
+
+       if (has_operation_node(&ob->id, DEPSNODE_TYPE_EVAL_POSE, rootchan->name,
+                              DEG_OPCODE_POSE_IK_SOLVER))
+       {
+               return;
+       }
+
+       /* Operation node for evaluating/running IK Solver. */
+       add_operation_node(&ob->id, DEPSNODE_TYPE_EVAL_POSE, rootchan->name,
+                          DEPSOP_TYPE_SIM, function_bind(BKE_pose_iktree_evaluate, _1, scene, ob, rootchan),
+                          DEG_OPCODE_POSE_IK_SOLVER);
+}
+
+/* Spline IK Eval Steps */
+void DepsgraphNodeBuilder::build_splineik_pose(Scene *scene, Object *ob, bPoseChannel *pchan, bConstraint *con)
+{
+       bSplineIKConstraint *data = (bSplineIKConstraint *)con->data;
+
+       /* Find the chain's root. */
+       bPoseChannel *rootchan = BKE_armature_splineik_solver_find_root(pchan, data);
+
+       /* Operation node for evaluating/running Spline IK Solver.
+        * Store the "root bone" of this chain in the solver, so it knows where to start.
+        */
+       add_operation_node(&ob->id, DEPSNODE_TYPE_EVAL_POSE, rootchan->name,
+                          DEPSOP_TYPE_SIM, function_bind(BKE_pose_splineik_evaluate, _1, scene, ob, rootchan),
+                          DEG_OPCODE_POSE_SPLINE_IK_SOLVER);
+}
+
+/* Pose/Armature Bones Graph */
+void DepsgraphNodeBuilder::build_rig(Scene *scene, Object *ob)
+{
+       bArmature *arm = (bArmature *)ob->data;
+
+       /* animation and/or drivers linking posebones to base-armature used to define them
+        * NOTE: AnimData here is really used to control animated deform properties,
+        *       which ideally should be able to be unique across different instances.
+        *       Eventually, we need some type of proxy/isolation mechanism in-between here
+        *       to ensure that we can use same rig multiple times in same scene...
+        */
+       build_animdata(&arm->id);
+
+       /* Rebuild pose if not up to date. */
+       if (ob->pose == NULL || (ob->pose->flag & POSE_RECALC)) {
+               BKE_pose_rebuild(ob, arm);
+               /* XXX: Without this animation gets lost in certain circumstances
+                * after loading file. Need to investigate further since it does
+                * not happen with simple scenes..
+                */
+               if (ob->adt) {
+                       ob->adt->recalc |= ADT_RECALC_ANIM;
+               }
+       }
+
+       /**
+        * Pose Rig Graph
+        * ==============
+        *
+        * Pose Component:
+        * - Mainly used for referencing Bone components.
+        * - This is where the evaluation operations for init/exec/cleanup
+        *   (ik) solvers live, and are later hooked up (so that they can be
+        *   interleaved during runtime) with bone-operations they depend on/affect.
+        * - init_pose_eval() and cleanup_pose_eval() are absolute first and last
+        *   steps of pose eval process. ALL bone operations must be performed
+        *   between these two...
+        *
+        * Bone Component:
+        * - Used for representing each bone within the rig
+        * - Acts to encapsulate the evaluation operations (base matrix + parenting,
+        *   and constraint stack) so that they can be easily found.
+        * - Everything else which depends on bone-results hook up to the component only
+        *   so that we can redirect those to point at either the the post-IK/
+        *   post-constraint/post-matrix steps, as needed.
+        */
+
+       /* pose eval context */
+       add_operation_node(&ob->id, DEPSNODE_TYPE_EVAL_POSE,
+                          DEPSOP_TYPE_INIT, function_bind(BKE_pose_eval_init, _1, scene, ob, ob->pose), DEG_OPCODE_POSE_INIT);
+
+       add_operation_node(&ob->id, DEPSNODE_TYPE_EVAL_POSE,
+                          DEPSOP_TYPE_POST, function_bind(BKE_pose_eval_flush, _1, scene, ob, ob->pose), DEG_OPCODE_POSE_DONE);
+
+       /* bones */
+       for (bPoseChannel *pchan = (bPoseChannel *)ob->pose->chanbase.first; pchan; pchan = pchan->next) {
+               /* node for bone eval */
+               add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name,
+                                  DEPSOP_TYPE_INIT, NULL, // XXX: BKE_pose_eval_bone_local
+                                  DEG_OPCODE_BONE_LOCAL);
+
+               add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name,
+                                  DEPSOP_TYPE_EXEC, function_bind(BKE_pose_eval_bone, _1, scene, ob, pchan), // XXX: BKE_pose_eval_bone_pose
+                                  DEG_OPCODE_BONE_POSE_PARENT);
+
+               add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name,
+                                  DEPSOP_TYPE_OUT, NULL, /* NOTE: dedicated noop for easier relationship construction */
+                                  DEG_OPCODE_BONE_READY);
+
+               add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name,
+                                  DEPSOP_TYPE_POST, function_bind(BKE_pose_bone_done, _1, pchan),
+                                  DEG_OPCODE_BONE_DONE);
+
+               /* constraints */
+               if (pchan->constraints.first != NULL) {
+                       build_pose_constraints(ob, pchan);
+               }
+
+               /**
+                * IK Solvers...
+                *
+                * - These require separate processing steps are pose-level
+                *   to be executed between chains of bones (i.e. once the
+                *   base transforms of a bunch of bones is done)
+                *
+                * Unsolved Issues:
+                * - Care is needed to ensure that multi-headed trees work out the same as in ik-tree building
+                * - Animated chain-lengths are a problem...
+                */
+               for (bConstraint *con = (bConstraint *)pchan->constraints.first; con; con = con->next) {
+                       switch (con->type) {
+                               case CONSTRAINT_TYPE_KINEMATIC:
+                                       build_ik_pose(scene, ob, pchan, con);
+                                       break;
+
+                               case CONSTRAINT_TYPE_SPLINEIK:
+                                       build_splineik_pose(scene, ob, pchan, con);
+                                       break;
+
+                               default:
+                                       break;
+                       }
+               }
+       }
+}
+
+void DepsgraphNodeBuilder::build_proxy_rig(Object *ob)
+{
+       ID *obdata = (ID *)ob->data;
+       build_animdata(obdata);
+
+       add_operation_node(&ob->id,
+                          DEPSNODE_TYPE_EVAL_POSE,
+                          DEPSOP_TYPE_INIT,
+                          function_bind(BKE_pose_eval_proxy_copy, _1, ob),
+                          DEG_OPCODE_POSE_INIT);
+
+       for (bPoseChannel *pchan = (bPoseChannel *)ob->pose->chanbase.first;
+            pchan != NULL;
+            pchan = pchan->next)
+       {
+               add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name,
+                                  DEPSOP_TYPE_INIT, NULL,
+                                  DEG_OPCODE_BONE_LOCAL);
+
+               add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name,
+                                  DEPSOP_TYPE_EXEC, NULL,
+                                  DEG_OPCODE_BONE_READY);
+
+               add_operation_node(&ob->id, DEPSNODE_TYPE_BONE, pchan->name,
+                                  DEPSOP_TYPE_POST, NULL,
+                                  DEG_OPCODE_BONE_DONE);
+       }
+
+       add_operation_node(&ob->id,
+                          DEPSNODE_TYPE_EVAL_POSE,
+                          DEPSOP_TYPE_POST,
+                          NULL,
+                          DEG_OPCODE_POSE_DONE);
+}
+
+/* Shapekeys */
+void DepsgraphNodeBuilder::build_shapekeys(Key *key)
+{
+       build_animdata(&key->id);
+}
+
+/* ObData Geometry Evaluation */
+// XXX: what happens if the datablock is shared!
+void DepsgraphNodeBuilder::build_obdata_geom(Scene *scene, Object *ob)
+{
+       ID *obdata = (ID *)ob->data;
+
+       /* Temporary uber-update node, which does everything.
+        * It is for the being we're porting old dependencies into the new system.
+        * We'll get rid of this node as soon as all the granular update functions
+        * are filled in.
+        *
+        * TODO(sergey): Get rid of this node.
+        */
+       add_operation_node(&ob->id, DEPSNODE_TYPE_GEOMETRY,
+                          DEPSOP_TYPE_POST, function_bind(BKE_object_eval_uber_data, _1, scene, ob),
+                          DEG_OPCODE_GEOMETRY_UBEREVAL);
+
+       add_operation_node(&ob->id, DEPSNODE_TYPE_GEOMETRY,
+                          DEPSOP_TYPE_INIT, NULL,
+                          DEG_OPCODE_PLACEHOLDER, "Eval Init");
+
+       // TODO: "Done" operation
+
+       /* ShapeKeys */
+       Key *key = BKE_key_from_object(ob);
+       if (key)
+               build_shapekeys(key);
+
+       /* Modifiers */
+       if (ob->modifiers.first) {
+               ModifierData *md;
+
+               for (md = (ModifierData *)ob->modifiers.first; md; md = md->next) {
+                       add_operation_node(&ob->id, DEPSNODE_TYPE_GEOMETRY,
+                                          DEPSOP_TYPE_EXEC, function_bind(BKE_object_eval_modifier, _1, scene, ob, md),
+                                          DEG_OPCODE_GEOMETRY_MODIFIER, md->name);
+               }
+       }
+
+       /* materials */
+       if (ob->totcol) {
+               int a;
+
+               for (a = 1; a <= ob->totcol; a++) {
+                       Material *ma = give_current_material(ob, a);
+
+                       if (ma) {
+                               // XXX?!
+                               ComponentDepsNode *geom_node = add_component_node(&ob->id, DEPSNODE_TYPE_GEOMETRY);
+                               build_material(geom_node, ma);
+                       }
+               }
+       }
+
+       /* geometry collision */
+       if (ELEM(ob->type, OB_MESH, OB_CURVE, OB_LATTICE)) {
+               // add geometry collider relations
+       }
+
+       if (obdata->flag & LIB_DOIT) {
+               return;
+       }
+
+       build_animdata(obdata);
+
+       /* nodes for result of obdata's evaluation, and geometry evaluation on object */
+       switch (ob->type) {
+               case OB_MESH:
+               {
+                       //Mesh *me = (Mesh *)ob->data;
+
+                       /* evaluation operations */
+                       add_operation_node(obdata, DEPSNODE_TYPE_GEOMETRY,
+                                          DEPSOP_TYPE_INIT, function_bind(BKE_mesh_eval_geometry, _1, (Mesh *)obdata),
+                                          DEG_OPCODE_PLACEHOLDER, "Geometry Eval");
+               }
+               break;
+
+               case OB_MBALL:
+               {
+                       Object *mom = BKE_mball_basis_find(scene, ob);
+
+                       /* motherball - mom depends on children! */
+                       if (mom == ob) {
+                               /* metaball evaluation operations */
+                               /* NOTE: only the motherball gets evaluated! */
+                               add_operation_node(obdata, DEPSNODE_TYPE_GEOMETRY,
+                                                  DEPSOP_TYPE_INIT, function_bind(BKE_mball_eval_geometry, _1, (MetaBall *)obdata),
+                                                  DEG_OPCODE_PLACEHOLDER, "Geometry Eval");
+                       }
+               }
+               break;
+
+               case OB_CURVE:
+               case OB_FONT:
+               {
+                       /* curve evaluation operations */
+                       /* - calculate curve geometry (including path) */
+                       add_operation_node(obdata, DEPSNODE_TYPE_GEOMETRY,
+                                          DEPSOP_TYPE_INIT, function_bind(BKE_curve_eval_geometry, _1, (Curve *)obdata),
+                                          DEG_OPCODE_PLACEHOLDER, "Geometry Eval");
+
+                       /* - calculate curve path - this is used by constraints, etc. */
+                       add_operation_node(obdata, DEPSNODE_TYPE_GEOMETRY,
+                                          DEPSOP_TYPE_EXEC, function_bind(BKE_curve_eval_path, _1, (Curve *)obdata),
+                                          DEG_OPCODE_GEOMETRY_PATH, "Path");
+               }
+               break;
+
+               case OB_SURF: /* Nurbs Surface */
+               {
+                       /* nurbs evaluation operations */
+                       add_operation_node(obdata, DEPSNODE_TYPE_GEOMETRY,
+                                          DEPSOP_TYPE_INIT, function_bind(BKE_curve_eval_geometry, _1, (Curve *)obdata),
+                                          DEG_OPCODE_PLACEHOLDER, "Geometry Eval");
+               }
+               break;
+
+               case OB_LATTICE: /* Lattice */
+               {
+                       /* lattice evaluation operations */
+                       add_operation_node(obdata, DEPSNODE_TYPE_GEOMETRY,
+                                          DEPSOP_TYPE_INIT, function_bind(BKE_lattice_eval_geometry, _1, (Lattice *)obdata),
+                                          DEG_OPCODE_PLACEHOLDER, "Geometry Eval");
+               }
+               break;
+       }
+
+       add_operation_node(obdata, DEPSNODE_TYPE_GEOMETRY,
+                          DEPSOP_TYPE_POST, NULL,
+                          DEG_OPCODE_PLACEHOLDER, "Eval Done");
+
+       /* Parameters for driver sources. */
+       add_operation_node(obdata, DEPSNODE_TYPE_PARAMETERS, DEPSOP_TYPE_EXEC, NULL,
+                          DEG_OPCODE_PLACEHOLDER, "Parameters Eval");
+}
+
+/* Cameras */
+void DepsgraphNodeBuilder::build_camera(Object *ob)
+{
+       /* TODO: Link scene-camera links in somehow... */
+       Camera *cam = (Camera *)ob->data;
+       ID *camera_id = &cam->id;
+       if (camera_id->flag & LIB_DOIT) {
+               return;
+       }
+
+       build_animdata(&cam->id);
+
+       add_operation_node(camera_id, DEPSNODE_TYPE_PARAMETERS, DEPSOP_TYPE_EXEC, NULL,
+                          DEG_OPCODE_PLACEHOLDER, "Parameters Eval");
+
+       if (cam->dof_ob != NULL) {
+               /* TODO(sergey): For now parametrs are on object level. */
+               add_operation_node(&ob->id, DEPSNODE_TYPE_PARAMETERS,
+                                  DEPSOP_TYPE_EXEC, NULL,
+                                  DEG_OPCODE_PLACEHOLDER,
+                                  "Camera DOF");
+       }
+}
+
+/* Lamps */
+void DepsgraphNodeBuilder::build_lamp(Object *ob)
+{
+       Lamp *la = (Lamp *)ob->data;
+       ID *lamp_id = &la->id;
+       if (lamp_id->flag & LIB_DOIT) {
+               return;
+       }
+
+       build_animdata(&la->id);
+
+       /* node for obdata */
+       ComponentDepsNode *param_node = add_component_node(lamp_id, DEPSNODE_TYPE_PARAMETERS);
+
+       /* TODO(sergey): Is it really how we're supposed to work with drivers? */
+       add_operation_node(lamp_id, DEPSNODE_TYPE_PARAMETERS, DEPSOP_TYPE_EXEC, NULL,
+                          DEG_OPCODE_PLACEHOLDER, "Parameters Eval");
+
+       /* lamp's nodetree */
+       if (la->nodetree) {
+               build_nodetree(param_node, la->nodetree);
+       }
+
+       /* textures */
+       build_texture_stack(param_node, la->mtex);
+}
+
+void DepsgraphNodeBuilder::build_nodetree(DepsNode *owner_node, bNodeTree *ntree)
+{
+       if (!ntree)
+               return;
+
+       /* nodetree itself */
+       ID *ntree_id = &ntree->id;
+
+       build_animdata(ntree_id);
+
+       /* Parameters for drivers. */
+       add_operation_node(ntree_id, DEPSNODE_TYPE_PARAMETERS, DEPSOP_TYPE_EXEC, NULL,
+                          DEG_OPCODE_PLACEHOLDER, "Parameters Eval");
+
+       /* nodetree's nodes... */
+       for (bNode *bnode = (bNode *)ntree->nodes.first; bnode; bnode = bnode->next) {
+               if (bnode->id) {
+                       if (GS(bnode->id->name) == ID_MA) {
+                               build_material(owner_node, (Material *)bnode->id);
+                       }
+                       else if (bnode->type == ID_TE) {
+                               build_texture(owner_node, (Tex *)bnode->id);
+                       }
+                       else if (bnode->type == NODE_GROUP) {
+                               bNodeTree *ntree = (bNodeTree *)bnode->id;
+                               if ((ntree_id->flag & LIB_DOIT) == 0) {
+                                       build_nodetree(owner_node, ntree);
+                               }
+                       }
+               }
+       }
+
+       // TODO: link from nodetree to owner_component?
+}
+
+/* Recursively build graph for material */
+void DepsgraphNodeBuilder::build_material(DepsNode *owner_node, Material *ma)
+{
+       ID *ma_id = &ma->id;
+       if (ma_id->flag & LIB_DOIT) {
+               return;
+       }
+
+       /* material itself */
+       add_id_node(ma_id);
+
+       add_operation_node(ma_id, DEPSNODE_TYPE_SHADING,
+                          DEPSOP_TYPE_EXEC, NULL,
+                          DEG_OPCODE_PLACEHOLDER, "Material Update");
+
+       /* material animation */
+       build_animdata(ma_id);
+
+       /* textures */
+       build_texture_stack(owner_node, ma->mtex);
+
+       /* material's nodetree */
+       build_nodetree(owner_node, ma->nodetree);
+}
+
+/* Texture-stack attached to some shading datablock */
+void DepsgraphNodeBuilder::build_texture_stack(DepsNode *owner_node, MTex **texture_stack)
+{
+       int i;
+
+       /* for now assume that all texture-stacks have same number of max items */
+       for (i = 0; i < MAX_MTEX; i++) {
+               MTex *mtex = texture_stack[i];
+               if (mtex && mtex->tex)
+                       build_texture(owner_node, mtex->tex);
+       }
+}
+
+/* Recursively build graph for texture */
+void DepsgraphNodeBuilder::build_texture(DepsNode *owner_node, Tex *tex)
+{
+       ID *tex_id = &tex->id;
+       if (tex_id->flag & LIB_DOIT) {
+               return;
+       }
+       tex_id->flag |= LIB_DOIT;
+       /* texture itself */
+       build_animdata(tex_id);
+       /* texture's nodetree */
+       build_nodetree(owner_node, tex->nodetree);
+}
+
+void DepsgraphNodeBuilder::build_compositor(Scene *scene)
+{
+       /* For now, just a plain wrapper? */
+       // TODO: create compositing component?
+       // XXX: component type undefined!
+       //graph->get_node(&scene->id, NULL, DEPSNODE_TYPE_COMPOSITING, NULL);
+
+       /* for now, nodetrees are just parameters; compositing occurs in internals of renderer... */
+       ComponentDepsNode *owner_node = add_component_node(&scene->id, DEPSNODE_TYPE_PARAMETERS);
+       build_nodetree(owner_node, scene->nodetree);
+}
+
+void DepsgraphNodeBuilder::build_gpencil(bGPdata *gpd)
+{
+       ID *gpd_id = &gpd->id;
+
+       /* gpencil itself */
+       // XXX: what about multiple users of same datablock? This should only get added once
+       add_id_node(gpd_id);
+
+       /* The main reason Grease Pencil is included here is because the animation (and drivers)
+        * need to be hosted somewhere...
+        */
+       build_animdata(gpd_id);
+}
diff --git a/source/blender/depsgraph/intern/depsgraph_build_relations.cc b/source/blender/depsgraph/intern/depsgraph_build_relations.cc
new file mode 100644 (file)
index 0000000..300ed07
--- /dev/null
@@ -0,0 +1,1815 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Joshua Leung
+ * Contributor(s): Based on original depsgraph.c code - Blender Foundation (2005-2013)
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ *
+ * Methods for constructing depsgraph
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "MEM_guardedalloc.h"
+
+extern "C" {
+#include "BLI_blenlib.h"
+#include "BLI_string.h"
+#include "BLI_utildefines.h"
+
+#include "DNA_action_types.h"
+#include "DNA_anim_types.h"
+#include "DNA_armature_types.h"
+#include "DNA_camera_types.h"
+#include "DNA_constraint_types.h"
+#include "DNA_curve_types.h"
+#include "DNA_effect_types.h"
+#include "DNA_gpencil_types.h"
+#include "DNA_group_types.h"
+#include "DNA_key_types.h"
+#include "DNA_lamp_types.h"
+#include "DNA_material_types.h"
+#include "DNA_mesh_types.h"
+#include "DNA_meta_types.h"
+#include "DNA_node_types.h"
+#include "DNA_particle_types.h"
+#include "DNA_object_types.h"
+#include "DNA_rigidbody_types.h"
+#include "DNA_scene_types.h"
+#include "DNA_texture_types.h"
+#include "DNA_world_types.h"
+
+#include "BKE_action.h"
+#include "BKE_armature.h"
+#include "BKE_animsys.h"
+#include "BKE_constraint.h"
+#include "BKE_curve.h"
+#include "BKE_effect.h"
+#include "BKE_fcurve.h"
+#include "BKE_group.h"
+#include "BKE_key.h"
+#include "BKE_library.h"
+#include "BKE_main.h"
+#include "BKE_material.h"
+#include "BKE_mball.h"
+#include "BKE_modifier.h"
+#include "BKE_node.h"
+#include "BKE_object.h"
+#include "BKE_particle.h"
+#include "BKE_rigidbody.h"
+#include "BKE_sound.h"
+#include "BKE_texture.h"
+#include "BKE_tracking.h"
+#include "BKE_world.h"
+
+#include "DEG_depsgraph.h"
+#include "DEG_depsgraph_build.h"
+
+#include "RNA_access.h"
+#include "RNA_types.h"
+} /* extern "C" */
+
+#include "depsnode.h"
+#include "depsnode_component.h"
+#include "depsnode_operation.h"
+#include "depsgraph_build.h"
+#include "depsgraph_debug.h"
+#include "depsgraph_intern.h"
+#include "depsgraph_types.h"
+
+#include "depsgraph_util_pchanmap.h"
+
+/* ***************** */
+/* Relations Builder */
+
+/* **** General purpose functions ****  */
+
+RNAPathKey::RNAPathKey(ID *id, const string &path) :
+    id(id)
+{
+       /* create ID pointer for root of path lookup */
+       PointerRNA id_ptr;
+       RNA_id_pointer_create(id, &id_ptr);
+       /* try to resolve path... */
+       if (!RNA_path_resolve(&id_ptr, path.c_str(), &this->ptr, &this->prop)) {
+               this->ptr = PointerRNA_NULL;
+               this->prop = NULL;
+       }
+}
+
+DepsgraphRelationBuilder::DepsgraphRelationBuilder(Depsgraph *graph) :
+    m_graph(graph)
+{
+}
+
+RootDepsNode *DepsgraphRelationBuilder::find_node(const RootKey &key) const
+{
+       (void)key;
+       BLI_assert(!"Doesn't seem to be correct");
+       return m_graph->root_node;
+}
+
+TimeSourceDepsNode *DepsgraphRelationBuilder::find_node(
+        const TimeSourceKey &key) const
+{
+       if (key.id) {
+               /* XXX TODO */
+               return NULL;
+       }
+       else {
+               return m_graph->root_node->time_source;
+       }
+}
+
+ComponentDepsNode *DepsgraphRelationBuilder::find_node(
+        const ComponentKey &key) const
+{
+       IDDepsNode *id_node = m_graph->find_id_node(key.id);
+       if (!id_node) {
+               fprintf(stderr, "find_node component: Could not find ID %s\n",
+                       (key.id != NULL) ? key.id->name : "<null>");
+               return NULL;
+       }
+
+       ComponentDepsNode *node = id_node->find_component(key.type, key.name);
+       return node;
+}
+
+OperationDepsNode *DepsgraphRelationBuilder::find_node(
+        const OperationKey &key) const
+{
+       IDDepsNode *id_node = m_graph->find_id_node(key.id);
+       if (!id_node) {
+               fprintf(stderr, "find_node operation: Could not find ID\n");
+               return NULL;
+       }
+
+       ComponentDepsNode *comp_node = id_node->find_component(key.component_type,
+                                                              key.component_name);
+       if (!comp_node) {
+               fprintf(stderr, "find_node operation: Could not find component\n");
+               return NULL;
+       }
+
+       OperationDepsNode *op_node = comp_node->find_operation(key.opcode, key.name);
+       if (!op_node) {
+               fprintf(stderr, "find_node_operation: Failed for (%s, '%s')\n",
+                       DEG_OPNAMES[key.opcode], key.name.c_str());
+       }
+       return op_node;
+}
+
+DepsNode *DepsgraphRelationBuilder::find_node(const RNAPathKey &key) const
+{
+       return m_graph->find_node_from_pointer(&key.ptr, key.prop);
+}
+
+OperationDepsNode *DepsgraphRelationBuilder::has_node(
+        const OperationKey &key) const
+{
+       IDDepsNode *id_node = m_graph->find_id_node(key.id);
+       if (!id_node) {
+               return NULL;
+       }
+       ComponentDepsNode *comp_node = id_node->find_component(key.component_type,
+                                                              key.component_name);
+       if (!comp_node) {
+               return NULL;
+       }
+       return comp_node->has_operation(key.opcode, key.name);
+}
+
+void DepsgraphRelationBuilder::add_time_relation(TimeSourceDepsNode *timesrc,
+                                                 DepsNode *node_to,
+                                                 const char *description)
+{
+       if (timesrc && node_to) {
+               m_graph->add_new_relation(timesrc, node_to, DEPSREL_TYPE_TIME, description);
+       }
+       else {
+               DEG_DEBUG_PRINTF("add_time_relation(%p = %s, %p = %s, %s) Failed\n",
+                                timesrc,   (timesrc) ? timesrc->identifier().c_str() : "<None>",
+                                node_to,   (node_to) ? node_to->identifier().c_str() : "<None>",
+                                description);
+       }
+}
+
+void DepsgraphRelationBuilder::add_operation_relation(
+        OperationDepsNode *node_from,
+        OperationDepsNode *node_to,
+        eDepsRelation_Type type,
+        const char *description)
+{
+       if (node_from && node_to) {
+               m_graph->add_new_relation(node_from, node_to, type, description);
+       }
+       else {
+               DEG_DEBUG_PRINTF("add_operation_relation(%p = %s, %p = %s, %d, %s) Failed\n",
+                                node_from, (node_from) ? node_from->identifier().c_str() : "<None>",
+                                node_to,   (node_to)   ? node_to->identifier().c_str() : "<None>",
+                                type, description);
+       }
+}
+
+/* **** Functions to build relations between entities  **** */
+
+void DepsgraphRelationBuilder::build_scene(Main *bmain, Scene *scene)
+{
+       /* LIB_DOIT is used to indicate whether node for given ID was already
+        * created or not.
+        */
+       BKE_main_id_tag_all(bmain, false);
+
+       if (scene->set) {
+               // TODO: link set to scene, especially our timesource...
+       }
+
+       /* scene objects */
+       for (Base *base = (Base *)scene->base.first; base; base = base->next) {
+               Object *ob = base->object;
+
+               /* object itself */
+               build_object(bmain, scene, ob);
+
+               /* object that this is a proxy for */
+               if (ob->proxy) {
+                       build_object(bmain, scene, ob->proxy);
+                       /* TODO(sergey): This is an inverted relation, matches old depsgraph
+                        * behavior and need to be investigated if it still need to be inverted.
+                        */
+                       ComponentKey ob_pose_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE);
+                       ComponentKey proxy_pose_key(&ob->proxy->id, DEPSNODE_TYPE_EVAL_POSE);
+                       add_relation(ob_pose_key, proxy_pose_key, DEPSREL_TYPE_TRANSFORM, "Proxy");
+               }
+
+               /* Object dupligroup. */
+               if (ob->dup_group) {
+                       build_group(bmain, scene, ob, ob->dup_group);
+               }
+       }
+
+       /* rigidbody */
+       if (scene->rigidbody_world) {
+               build_rigidbody(scene);
+       }
+
+       /* scene's animation and drivers */
+       if (scene->adt) {
+               build_animdata(&scene->id);
+       }
+
+       /* world */
+       if (scene->world) {
+               build_world(scene->world);
+       }
+
+       /* compo nodes */
+       if (scene->nodetree) {
+               build_compositor(scene);
+       }
+
+       /* grease pencil */
+       if (scene->gpd) {
+               build_gpencil(&scene->id, scene->gpd);
+       }
+}
+
+void DepsgraphRelationBuilder::build_group(Main *bmain,
+                                           Scene *scene,
+                                           Object *object,
+                                           Group *group)
+{
+       ID *group_id = &group->id;
+       bool group_done = (group_id->flag & LIB_DOIT) != 0;
+       OperationKey object_local_transform_key(&object->id,
+                                               DEPSNODE_TYPE_TRANSFORM,
+                                               DEG_OPCODE_TRANSFORM_LOCAL);
+       for (GroupObject *go = (GroupObject *)group->gobject.first;
+            go != NULL;
+            go = go->next)
+       {
+               if (!group_done) {
+                       build_object(bmain, scene, go->ob);
+               }
+               ComponentKey dupli_transform_key(&go->ob->id, DEPSNODE_TYPE_TRANSFORM);
+               add_relation(dupli_transform_key,
+                            object_local_transform_key,
+                            DEPSREL_TYPE_TRANSFORM,
+                            "Dupligroup");
+       }
+       group_id->flag |= LIB_DOIT;
+}
+
+void DepsgraphRelationBuilder::build_object(Main *bmain, Scene *scene, Object *ob)
+{
+       if (ob->id.flag & LIB_DOIT) {
+               return;
+       }
+
+       /* Object Transforms */
+       eDepsOperation_Code base_op = (ob->parent) ? DEG_OPCODE_TRANSFORM_PARENT : DEG_OPCODE_TRANSFORM_LOCAL;
+       OperationKey base_op_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, base_op);
+
+       OperationKey local_transform_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_LOCAL);
+       OperationKey parent_transform_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_PARENT);
+       OperationKey final_transform_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_FINAL);
+
+       OperationKey ob_ubereval_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_OBJECT_UBEREVAL);
+
+       /* parenting */
+       if (ob->parent) {
+               /* parent relationship */
+               build_object_parent(ob);
+
+               /* local -> parent */
+               add_relation(local_transform_key, parent_transform_key, DEPSREL_TYPE_COMPONENT_ORDER, "[ObLocal -> ObParent]");
+       }
+
+       /* object constraints */
+       if (ob->constraints.first) {
+               OperationKey constraint_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_CONSTRAINTS);
+
+               /* constraint relations */
+               // TODO: provide base op
+               // XXX: this is broken
+               build_constraints(scene, &ob->id, DEPSNODE_TYPE_TRANSFORM, "", &ob->constraints, NULL);
+
+               /* operation order */
+               add_relation(base_op_key, constraint_key, DEPSREL_TYPE_COMPONENT_ORDER, "[ObBase-> Constraint Stack]");
+               add_relation(constraint_key, final_transform_key, DEPSREL_TYPE_COMPONENT_ORDER, "[ObConstraints -> Done]");
+
+               // XXX
+               add_relation(constraint_key, ob_ubereval_key, DEPSREL_TYPE_COMPONENT_ORDER, "Temp Ubereval");
+               add_relation(ob_ubereval_key, final_transform_key, DEPSREL_TYPE_COMPONENT_ORDER, "Temp Ubereval");
+       }
+       else {
+               /* operation order */
+               add_relation(base_op_key, final_transform_key, DEPSREL_TYPE_COMPONENT_ORDER, "Object Transform");
+
+               // XXX
+               add_relation(base_op_key, ob_ubereval_key, DEPSREL_TYPE_COMPONENT_ORDER, "Temp Ubereval");
+               add_relation(ob_ubereval_key, final_transform_key, DEPSREL_TYPE_COMPONENT_ORDER, "Temp Ubereval");
+       }
+
+
+       /* AnimData */
+       build_animdata(&ob->id);
+
+       // XXX: This should be hooked up by the build_animdata code
+       if (ob->adt && (ob->adt->action || ob->adt->nla_tracks.first)) {
+               ComponentKey adt_key(&ob->id, DEPSNODE_TYPE_ANIMATION);
+               add_relation(adt_key, local_transform_key, DEPSREL_TYPE_OPERATION, "Object Animation");
+       }
+
+
+       /* object data */
+       if (ob->data) {
+               ID *obdata_id = (ID *)ob->data;
+
+               /* ob data animation */
+               build_animdata(obdata_id);
+
+               /* type-specific data... */
+               switch (ob->type) {
+                       case OB_MESH:     /* Geometry */
+                       case OB_CURVE:
+                       case OB_FONT:
+                       case OB_SURF:
+                       case OB_MBALL:
+                       case OB_LATTICE:
+                       {
+                               build_obdata_geom(bmain, scene, ob);
+                       }
+                       break;
+
+
+                       case OB_ARMATURE: /* Pose */
+                               if (ob->id.lib != NULL && ob->proxy_from != NULL) {
+                                       build_proxy_rig(ob);
+                               }
+                               else {
+                                       build_rig(scene, ob);
+                               }
+                               break;
+
+                       case OB_LAMP:   /* Lamp */
+                               build_lamp(ob);
+                               break;
+
+                       case OB_CAMERA: /* Camera */
+                               build_camera(ob);
+                               break;
+               }
+       }
+
+       /* particle systems */
+       if (ob->particlesystem.first) {
+               build_particles(scene, ob);
+       }
+
+       /* grease pencil */
+       if (ob->gpd) {
+               build_gpencil(&ob->id, ob->gpd);
+       }
+}
+
+void DepsgraphRelationBuilder::build_object_parent(Object *ob)
+{
+       /* XXX: for now, need to use the component key (not just direct to the parent op), or else the matrix doesn't get reset */
+       // XXX: @sergey - it would be good if we got that backwards flushing working when tagging for updates
+       //OperationKey ob_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_PARENT);
+       ComponentKey ob_key(&ob->id, DEPSNODE_TYPE_TRANSFORM);
+
+       /* type-specific links */
+       switch (ob->partype) {
+               case PARSKEL:  /* Armature Deform (Virtual Modifier) */
+               {
+                       ComponentKey parent_key(&ob->parent->id, DEPSNODE_TYPE_TRANSFORM);
+                       add_relation(parent_key, ob_key, DEPSREL_TYPE_STANDARD, "Armature Deform Parent");
+               }
+               break;
+
+               case PARVERT1: /* Vertex Parent */
+               case PARVERT3:
+               {
+                       ComponentKey parent_key(&ob->parent->id, DEPSNODE_TYPE_GEOMETRY);
+                       add_relation(parent_key, ob_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Vertex Parent");
+                       /* XXX not sure what this is for or how you could be done properly - lukas */
+                       //parent_node->customdata_mask |= CD_MASK_ORIGINDEX;
+
+                       ComponentKey transform_key(&ob->parent->id, DEPSNODE_TYPE_TRANSFORM);
+                       add_relation(transform_key, ob_key, DEPSREL_TYPE_TRANSFORM, "Vertex Parent TFM");
+               }
+               break;
+
+               case PARBONE: /* Bone Parent */
+               {
+                       ComponentKey parent_key(&ob->parent->id, DEPSNODE_TYPE_BONE, ob->parsubstr);
+                       add_relation(parent_key, ob_key, DEPSREL_TYPE_TRANSFORM, "Bone Parent");
+               }
+               break;
+
+               default:
+               {
+                       if (ob->parent->type == OB_LATTICE) {
+                               /* Lattice Deform Parent - Virtual Modifier */
+                               // XXX: no virtual modifiers should be left!
+                               ComponentKey parent_key(&ob->parent->id, DEPSNODE_TYPE_TRANSFORM);
+                               ComponentKey geom_key(&ob->parent->id, DEPSNODE_TYPE_GEOMETRY);
+
+                               add_relation(parent_key, ob_key, DEPSREL_TYPE_STANDARD, "Lattice Deform Parent");
+                               add_relation(geom_key, ob_key, DEPSREL_TYPE_STANDARD, "Lattice Deform Parent Geom");
+                       }
+                       else if (ob->parent->type == OB_CURVE) {
+                               Curve *cu = (Curve *)ob->parent->data;
+
+                               if (cu->flag & CU_PATH) {
+                                       /* Follow Path */
+                                       ComponentKey parent_key(&ob->parent->id, DEPSNODE_TYPE_GEOMETRY);
+                                       add_relation(parent_key, ob_key, DEPSREL_TYPE_TRANSFORM, "Curve Follow Parent");
+
+                                       ComponentKey transform_key(&ob->parent->id, DEPSNODE_TYPE_TRANSFORM);
+                                       add_relation(transform_key, ob_key, DEPSREL_TYPE_TRANSFORM, "Curve Follow TFM");
+                               }
+                               else {
+                                       /* Standard Parent */
+                                       ComponentKey parent_key(&ob->parent->id, DEPSNODE_TYPE_TRANSFORM);
+                                       add_relation(parent_key, ob_key, DEPSREL_TYPE_TRANSFORM, "Curve Parent");
+                               }
+                       }
+                       else {
+                               /* Standard Parent */
+                               ComponentKey parent_key(&ob->parent->id, DEPSNODE_TYPE_TRANSFORM);
+                               add_relation(parent_key, ob_key, DEPSREL_TYPE_TRANSFORM, "Parent");
+                       }
+               }
+               break;
+       }
+
+       /* exception case: parent is duplivert */
+       if ((ob->type == OB_MBALL) && (ob->parent->transflag & OB_DUPLIVERTS)) {
+               //dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_OB, "Duplivert");
+       }
+}
+
+void DepsgraphRelationBuilder::build_constraints(Scene *scene, ID *id, eDepsNode_Type component_type, const char *component_subdata,
+                                                 ListBase *constraints, RootPChanMap *root_map)
+{
+       OperationKey constraint_op_key(id, component_type, component_subdata,
+                                      (component_type == DEPSNODE_TYPE_BONE) ? DEG_OPCODE_BONE_CONSTRAINTS : DEG_OPCODE_TRANSFORM_CONSTRAINTS);
+
+       /* add dependencies for each constraint in turn */
+       for (bConstraint *con = (bConstraint *)constraints->first; con; con = con->next) {
+               const bConstraintTypeInfo *cti = BKE_constraint_typeinfo_get(con);
+
+               /* invalid constraint type... */
+               if (cti == NULL)
+                       continue;
+
+               /* special case for camera tracking -- it doesn't use targets to define relations */
+               // TODO: we can now represent dependencies in a much richer manner, so review how this is done...
+               if (ELEM(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER, CONSTRAINT_TYPE_OBJECTSOLVER)) {
+                       bool depends_on_camera = false;
+
+                       if (cti->type == CONSTRAINT_TYPE_FOLLOWTRACK) {
+                               bFollowTrackConstraint *data = (bFollowTrackConstraint *)con->data;
+
+                               if (((data->clip) || (data->flag & FOLLOWTRACK_ACTIVECLIP)) && data->track[0])
+                                       depends_on_camera = true;
+
+                               if (data->depth_ob) {
+                                       // DAG_RL_DATA_OB | DAG_RL_OB_OB
+                                       ComponentKey depth_key(&data->depth_ob->id, DEPSNODE_TYPE_TRANSFORM);
+                                       add_relation(depth_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name);
+                               }
+                       }
+                       else if (cti->type == CONSTRAINT_TYPE_OBJECTSOLVER) {
+                               depends_on_camera = true;
+                       }
+
+                       if (depends_on_camera && scene->camera) {
+                               // DAG_RL_DATA_OB | DAG_RL_OB_OB
+                               ComponentKey camera_key(&scene->camera->id, DEPSNODE_TYPE_TRANSFORM);
+                               add_relation(camera_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name);
+                       }
+
+                       /* tracker <-> constraints */
+                       // FIXME: actually motionclip dependency on results of motionclip block here...
+                       //dag_add_relation(dag, scenenode, node, DAG_RL_SCENE, "Scene Relation");
+               }
+               else if (cti->get_constraint_targets) {
+                       ListBase targets = {NULL, NULL};
+                       cti->get_constraint_targets(con, &targets);
+
+                       for (bConstraintTarget *ct = (bConstraintTarget *)targets.first; ct; ct = ct->next) {
+                               if (!ct->tar)
+                                       continue;
+
+                               if (ELEM(con->type, CONSTRAINT_TYPE_KINEMATIC, CONSTRAINT_TYPE_SPLINEIK)) {
+                                       /* ignore IK constraints - these are handled separately (on pose level) */
+                               }
+                               else if (ELEM(con->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO)) {
+                                       /* these constraints require path geometry data... */
+                                       ComponentKey target_key(&ct->tar->id, DEPSNODE_TYPE_GEOMETRY);
+                                       add_relation(target_key, constraint_op_key, DEPSREL_TYPE_GEOMETRY_EVAL, cti->name); // XXX: type = geom_transform
+                                       // TODO: path dependency
+                               }
+                               else if ((ct->tar->type == OB_ARMATURE) && (ct->subtarget[0])) {
+                                       /* bone */
+                                       if (&ct->tar->id == id) {
+                                               /* same armature  */
+                                               eDepsOperation_Code target_key_opcode;
+
+                                               /* Using "done" here breaks in-chain deps, while using "ready" here breaks most production rigs instead...
+                                                * So, we do a compromise here, and only do this when an IK chain conflict may occur
+                                                */
+                                               if (root_map->has_common_root(component_subdata, ct->subtarget)) {
+                                                       target_key_opcode = DEG_OPCODE_BONE_READY;
+                                               }
+                                               else {
+                                                       target_key_opcode = DEG_OPCODE_BONE_DONE;
+                                               }
+
+                                               OperationKey target_key(&ct->tar->id, DEPSNODE_TYPE_BONE, ct->subtarget, target_key_opcode);
+                                               add_relation(target_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name);
+                                       }
+                                       else {
+                                               /* different armature - we can safely use the result of that */
+                                               OperationKey target_key(&ct->tar->id, DEPSNODE_TYPE_BONE, ct->subtarget, DEG_OPCODE_BONE_DONE);
+                                               add_relation(target_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name);
+                                       }
+                               }
+                               else if (ELEM(ct->tar->type, OB_MESH, OB_LATTICE) && (ct->subtarget[0])) {
+                                       /* vertex group */
+                                       /* NOTE: for now, we don't need to represent vertex groups separately... */
+                                       ComponentKey target_key(&ct->tar->id, DEPSNODE_TYPE_GEOMETRY);
+                                       add_relation(target_key, constraint_op_key, DEPSREL_TYPE_GEOMETRY_EVAL, cti->name);
+
+                                       if (ct->tar->type == OB_MESH) {
+                                               //node2->customdata_mask |= CD_MASK_MDEFORMVERT;
+                                       }
+                               }
+                               else if (con->type == CONSTRAINT_TYPE_SHRINKWRAP) {
+                                       /* Constraints which requires the target object surface. */
+                                       ComponentKey target_key(&ct->tar->id, DEPSNODE_TYPE_GEOMETRY);
+                                       add_relation(target_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name);
+
+                                       /* NOTE: obdata eval now doesn't necessarily depend on the object's transform... */
+                                       ComponentKey target_transform_key(&ct->tar->id, DEPSNODE_TYPE_TRANSFORM);
+                                       add_relation(target_transform_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name);
+                               }
+                               else {
+                                       /* standard object relation */
+                                       // TODO: loc vs rot vs scale?
+                                       if (&ct->tar->id == id) {
+                                               /* Constraint targetting own object:
+                                                * - This case is fine IFF we're dealing with a bone constraint pointing to
+                                                *   its own armature. In that case, it's just transform -> bone.
+                                                * - If however it is a real self targetting case, just make it depend on the
+                                                *   previous constraint (or the pre-constraint state)...
+                                                */
+                                               if ((ct->tar->type == OB_ARMATURE) && (component_type == DEPSNODE_TYPE_BONE)) {
+                                                       OperationKey target_key(&ct->tar->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_FINAL);
+                                                       add_relation(target_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name);
+                                               }
+                                               else {
+                                                       OperationKey target_key(&ct->tar->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_LOCAL);
+                                                       add_relation(target_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name);
+                                               }
+                                       }
+                                       else {
+                                               /* normal object dependency */
+                                               OperationKey target_key(&ct->tar->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_FINAL);
+                                               add_relation(target_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name);
+                                       }
+                               }
+
+                               /* Constraints which needs world's matrix for transform.
+                                * TODO(sergey): More constraints here?
+                                */
+                               if (ELEM(con->type,
+                                        CONSTRAINT_TYPE_ROTLIKE,
+                                        CONSTRAINT_TYPE_SIZELIKE,
+                                        CONSTRAINT_TYPE_LOCLIKE,
+                                        CONSTRAINT_TYPE_TRANSLIKE))
+                               {
+                                       /* TODO(sergey): Add used space check. */
+                                       ComponentKey target_transform_key(&ct->tar->id, DEPSNODE_TYPE_TRANSFORM);
+                                       add_relation(target_transform_key, constraint_op_key, DEPSREL_TYPE_TRANSFORM, cti->name);
+                               }
+
+                       }
+
+                       if (cti->flush_constraint_targets)
+                               cti->flush_constraint_targets(con, &targets, 1);
+               }
+       }
+}
+
+void DepsgraphRelationBuilder::build_animdata(ID *id)
+{
+       AnimData *adt = BKE_animdata_from_id(id);
+
+       if (adt == NULL)
+               return;
+
+       ComponentKey adt_key(id, DEPSNODE_TYPE_ANIMATION);
+
+       /* animation */
+       if (adt->action || adt->nla_tracks.first) {
+               /* wire up dependency to time source */
+               TimeSourceKey time_src_key;
+               add_relation(time_src_key, adt_key, DEPSREL_TYPE_TIME, "[TimeSrc -> Animation]");
+
+               // XXX: Hook up specific update callbacks for special properties which may need it...
+
+               // XXX: animdata "hierarchy" - top-level overrides need to go after lower-down
+       }
+
+       /* drivers */
+       for (FCurve *fcu = (FCurve *)adt->drivers.first; fcu; fcu = fcu->next) {
+               OperationKey driver_key(id, DEPSNODE_TYPE_PARAMETERS, DEG_OPCODE_DRIVER, deg_fcurve_id_name(fcu));
+
+               /* create the driver's relations to targets */
+               build_driver(id, fcu);
+
+               /* prevent driver from occurring before own animation... */
+               if (adt->action || adt->nla_tracks.first) {
+                       add_relation(adt_key, driver_key, DEPSREL_TYPE_OPERATION,
+                                                "[AnimData Before Drivers]");
+               }
+       }
+}
+
+void DepsgraphRelationBuilder::build_driver(ID *id, FCurve *fcu)
+{
+       ChannelDriver *driver = fcu->driver;
+       OperationKey driver_key(id, DEPSNODE_TYPE_PARAMETERS, DEG_OPCODE_DRIVER, deg_fcurve_id_name(fcu));
+       bPoseChannel *pchan = NULL;
+
+       /* create dependency between driver and data affected by it */
+       /* - direct property relationship... */
+       //RNAPathKey affected_key(id, fcu->rna_path);
+       //add_relation(driver_key, affected_key, DEPSREL_TYPE_DRIVER, "[Driver -> Data] DepsRel");
+
+       /* driver -> data components (for interleaved evaluation - bones/constraints/modifiers) */
+       // XXX: this probably should probably be moved out into a separate function
+       if (strstr(fcu->rna_path, "pose.bones[") != NULL) {
+               /* interleaved drivers during bone eval */
+               // TODO: ideally, if this is for a constraint, it goes to said constraint
+               Object *ob = (Object *)id;
+               char *bone_name;
+
+               bone_name = BLI_str_quoted_substrN(fcu->rna_path, "pose.bones[");
+               pchan = BKE_pose_channel_find_name(ob->pose, bone_name);
+
+               if (bone_name) {
+                       MEM_freeN(bone_name);
+                       bone_name = NULL;
+               }
+
+               if (pchan) {
+                       OperationKey bone_key(id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_LOCAL);
+                       add_relation(driver_key, bone_key, DEPSREL_TYPE_DRIVER, "[Driver -> Bone]");
+               }
+               else {
+                       fprintf(stderr,
+                               "Couldn't find bone name for driver path - '%s'\n",
+                               fcu->rna_path);
+               }
+       }
+       else if (GS(id->name) == ID_AR && strstr(fcu->rna_path, "bones[")) {
+               /* drivers on armature-level bone settings (i.e. bbone stuff),
+                * which will affect the evaluation of corresponding pose bones
+                */
+               IDDepsNode *arm_node = m_graph->find_id_node(id);
+               char *bone_name = BLI_str_quoted_substrN(fcu->rna_path, "bones[");
+
+               if (arm_node && bone_name) {
+                       /* find objects which use this, and make their eval callbacks depend on this */
+                       DEPSNODE_RELATIONS_ITER_BEGIN(arm_node->outlinks, rel)
+                       {
+                               IDDepsNode *to_node = (IDDepsNode *)rel->to;
+
+                               /* we only care about objects with pose data which use this... */
+                               if (GS(to_node->id->name) == ID_OB) {
+                                       Object *ob = (Object *)to_node->id;
+                                       bPoseChannel *pchan = BKE_pose_channel_find_name(ob->pose, bone_name); // NOTE: ob->pose may be NULL
+
+                                       if (pchan) {
+                                               OperationKey bone_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_LOCAL);
+                                               add_relation(driver_key, bone_key, DEPSREL_TYPE_DRIVER, "[Arm Bone -> Driver -> Bone]");
+                                       }
+                               }
+                       }
+                       DEPSNODE_RELATIONS_ITER_END;
+
+                       /* free temp data */
+                       MEM_freeN(bone_name);
+                       bone_name = NULL;
+               }
+               else {
+                       fprintf(stderr,
+                               "Couldn't find armature bone name for driver path - '%s'\n",
+                               fcu->rna_path);
+               }
+       }
+       else if (GS(id->name) == ID_OB && strstr(fcu->rna_path, "modifiers[")) {
+               /* modifier driver - connect directly to the modifier */
+               char *modifier_name = BLI_str_quoted_substrN(fcu->rna_path, "modifiers[");
+               if (modifier_name) {
+                       OperationKey modifier_key(id,
+                                                 DEPSNODE_TYPE_GEOMETRY,
+                                                 DEG_OPCODE_GEOMETRY_MODIFIER,
+                                                 modifier_name);
+                       if (has_node(modifier_key)) {
+                               add_relation(driver_key, modifier_key, DEPSREL_TYPE_DRIVER, "[Driver -> Modifier]");
+                       }
+                       else {
+                               printf("Unexisting driver RNA path: %s\n", fcu->rna_path);
+                       }
+
+                       MEM_freeN(modifier_name);
+               }
+       }
+       else if (GS(id->name) == ID_KE && strstr(fcu->rna_path, "key_blocks[")) {
+               /* shape key driver - hook into the base geometry operation */
+               // XXX: double check where this points
+               Key *shape_key = (Key *)id;
+
+               ComponentKey geometry_key(shape_key->from, DEPSNODE_TYPE_GEOMETRY);
+               add_relation(driver_key, geometry_key, DEPSREL_TYPE_DRIVER, "[Driver -> ShapeKey Geom]");
+       }
+       else {
+               if (GS(id->name) == ID_OB) {
+                       /* assume that driver affects a transform... */
+                       OperationKey local_transform_key(id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_LOCAL);
+                       add_relation(driver_key, local_transform_key, DEPSREL_TYPE_OPERATION, "[Driver -> Transform]");
+               }
+       }
+
+       /* ensure that affected prop's update callbacks will be triggered once done */
+       // TODO: implement this once the functionality to add these links exists in RNA
+       // XXX: the data itself could also set this, if it were to be truly initialised later?
+
+       /* loop over variables to get the target relationships */
+       for (DriverVar *dvar = (DriverVar *)driver->variables.first; dvar; dvar = dvar->next) {
+               /* only used targets */
+               DRIVER_TARGETS_USED_LOOPER(dvar)
+               {
+                       if (dtar->id == NULL)
+                               continue;
+
+                       /* special handling for directly-named bones */
+                       if ((dtar->flag & DTAR_FLAG_STRUCT_REF) && (dtar->pchan_name[0])) {
+                               Object *ob = (Object *)dtar->id;
+                               bPoseChannel *target_pchan = BKE_pose_channel_find_name(ob->pose, dtar->pchan_name);
+                               if (target_pchan != NULL) {
+                                       /* get node associated with bone */
+                                       // XXX: watch the space!
+                                       /* Some cases can't use final bone transform, for example:
+                                        * - Driving the bone with itself (addressed here)
+                                        * - Relations inside an IK chain (TODO?)
+                                        */
+                                       if (dtar->id == id &&
+                                           pchan != NULL &&
+                                           STREQ(pchan->name, target_pchan->name))
+                                       {
+                                               continue;
+                                       }
+                                       OperationKey target_key(dtar->id, DEPSNODE_TYPE_BONE, target_pchan->name, DEG_OPCODE_BONE_DONE);
+                                       add_relation(target_key, driver_key, DEPSREL_TYPE_DRIVER_TARGET, "[Bone Target -> Driver]");
+                               }
+                       }
+                       else if (dtar->flag & DTAR_FLAG_STRUCT_REF) {
+                               /* get node associated with the object's transforms */
+                               OperationKey target_key(dtar->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_FINAL);
+                               add_relation(target_key, driver_key, DEPSREL_TYPE_DRIVER_TARGET, "[Target -> Driver]");
+                       }
+                       else if (dtar->rna_path && strstr(dtar->rna_path, "pose.bones[")) {
+                               /* workaround for ensuring that local bone transforms don't end up
+                                * having to wait for pose eval to finish (to prevent cycles)
+                                */
+                               Object *ob = (Object *)dtar->id;
+                               char *bone_name = BLI_str_quoted_substrN(dtar->rna_path, "pose.bones[");
+                               bPoseChannel *target_pchan = BKE_pose_channel_find_name(ob->pose, bone_name);
+                               if (bone_name) {
+                                       MEM_freeN(bone_name);
+                                       bone_name = NULL;
+                               }
+                               if (target_pchan) {
+                                       if (dtar->id == id &&
+                                           pchan != NULL &&
+                                           STREQ(pchan->name, target_pchan->name))
+                                       {
+                                               continue;
+                                       }
+                                       OperationKey bone_key(dtar->id, DEPSNODE_TYPE_BONE, target_pchan->name, DEG_OPCODE_BONE_LOCAL);
+                                       add_relation(bone_key, driver_key, DEPSREL_TYPE_DRIVER, "[RNA Bone -> Driver]");
+                               }
+                       }
+                       else {
+                               /* resolve path to get node */
+                               RNAPathKey target_key(dtar->id, dtar->rna_path ? dtar->rna_path : "");
+                               add_relation(target_key, driver_key, DEPSREL_TYPE_DRIVER_TARGET, "[RNA Target -> Driver]");
+                       }
+               }
+               DRIVER_TARGETS_LOOPER_END
+       }
+}
+
+void DepsgraphRelationBuilder::build_world(World *world)
+{
+       ID *world_id = &world->id;
+       if (world_id->flag & LIB_DOIT) {
+               return;
+       }
+       world_id->flag |= LIB_DOIT;
+
+       build_animdata(world_id);
+
+       /* TODO: other settings? */
+
+       /* textures */
+       build_texture_stack(world_id, world->mtex);
+
+       /* world's nodetree */
+       build_nodetree(world_id, world->nodetree);
+}
+
+void DepsgraphRelationBuilder::build_rigidbody(Scene *scene)
+{
+       RigidBodyWorld *rbw = scene->rigidbody_world;
+
+       OperationKey init_key(&scene->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_REBUILD);
+       OperationKey sim_key(&scene->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_SIM);
+
+       /* rel between the two sim-nodes */
+       add_relation(init_key, sim_key, DEPSREL_TYPE_OPERATION, "Rigidbody [Init -> SimStep]");
+
+       /* set up dependencies between these operations and other builtin nodes --------------- */
+
+       /* time dependency */
+       TimeSourceKey time_src_key;
+       add_relation(time_src_key, init_key, DEPSREL_TYPE_TIME, "TimeSrc -> Rigidbody Reset/Rebuild (Optional)");
+       add_relation(time_src_key, sim_key, DEPSREL_TYPE_TIME, "TimeSrc -> Rigidbody Sim Step");
+
+       /* objects - simulation participants */
+       if (rbw->group) {
+               for (GroupObject *go = (GroupObject *)rbw->group->gobject.first; go; go = go->next) {
+                       Object *ob = go->ob;
+                       if (!ob || ob->type != OB_MESH)
+                               continue;
+
+                       /* hook up evaluation order...
+                        * 1) flushing rigidbody results follows base transforms being applied
+                        * 2) rigidbody flushing can only be performed after simulation has been run
+                        *
+                        * 3) simulation needs to know base transforms to figure out what to do
+                        *    XXX: there's probably a difference between passive and active
+                        *         - passive don't change, so may need to know full transform...
+                        */
+                       OperationKey rbo_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_RIGIDBODY);
+
+                       eDepsOperation_Code trans_opcode = ob->parent ? DEG_OPCODE_TRANSFORM_PARENT : DEG_OPCODE_TRANSFORM_LOCAL;
+                       OperationKey trans_op(&ob->id, DEPSNODE_TYPE_TRANSFORM, trans_opcode);
+
+                       add_relation(trans_op, rbo_key, DEPSREL_TYPE_OPERATION, "Base Ob Transform -> RBO Sync");
+                       add_relation(sim_key, rbo_key, DEPSREL_TYPE_COMPONENT_ORDER, "Rigidbody Sim Eval -> RBO Sync");
+
+                       /* if constraints exist, those depend on the result of the rigidbody sim
+                        * - This allows constraints to modify the result of the sim (i.e. clamping)
+                        *   while still allowing the sim to depend on some changes to the objects.
+                        *   Also, since constraints are hooked up to the final nodes, this link
+                        *   means that we can also fit in there too...
+                        * - Later, it might be good to include a constraint in the stack allowing us
+                        *   to control whether rigidbody eval gets interleaved into the constraint stack
+                        */
+                       if (ob->constraints.first) {
+                               OperationKey constraint_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_CONSTRAINTS);
+                               add_relation(rbo_key, constraint_key, DEPSREL_TYPE_COMPONENT_ORDER, "RBO Sync -> Ob Constraints");
+                       }
+                       else {
+                               /* final object transform depends on rigidbody */
+                               OperationKey done_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_FINAL);
+                               add_relation(rbo_key, done_key, DEPSREL_TYPE_COMPONENT_ORDER, "RBO Sync -> Done");
+
+                               // XXX: ubereval will be removed eventually, but we still need it in the meantime
+                               OperationKey uber_key(&ob->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_OBJECT_UBEREVAL);
+                               add_relation(rbo_key, uber_key, DEPSREL_TYPE_COMPONENT_ORDER, "RBO Sync -> Uber (Temp)");
+                       }
+
+
+                       /* needed to get correct base values */
+                       add_relation(trans_op, sim_key, DEPSREL_TYPE_OPERATION, "Base Ob Transform -> Rigidbody Sim Eval");
+               }
+       }
+
+       /* constraints */
+       if (rbw->constraints) {
+               for (GroupObject *go = (GroupObject *)rbw->constraints->gobject.first; go; go = go->next) {
+                       Object *ob = go->ob;
+                       if (!ob || !ob->rigidbody_constraint)
+                               continue;
+
+                       RigidBodyCon *rbc = ob->rigidbody_constraint;
+
+                       /* final result of the constraint object's transform controls how the
+                        * constraint affects the physics sim for these objects
+                        */
+                       ComponentKey trans_key(&ob->id, DEPSNODE_TYPE_TRANSFORM);
+                       OperationKey ob1_key(&rbc->ob1->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_RIGIDBODY);
+                       OperationKey ob2_key(&rbc->ob2->id, DEPSNODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_RIGIDBODY);
+
+                       /* - constrained-objects sync depends on the constraint-holder */
+                       add_relation(trans_key, ob1_key, DEPSREL_TYPE_TRANSFORM, "RigidBodyConstraint -> RBC.Object_1");
+                       add_relation(trans_key, ob2_key, DEPSREL_TYPE_TRANSFORM, "RigidBodyConstraint -> RBC.Object_2");
+
+                       /* - ensure that sim depends on this constraint's transform */
+                       add_relation(trans_key, sim_key, DEPSREL_TYPE_TRANSFORM, "RigidBodyConstraint Transform -> RB Simulation");
+               }
+       }
+}
+
+void DepsgraphRelationBuilder::build_particles(Scene *scene, Object *ob)
+{
+       /* particle systems */
+       for (ParticleSystem *psys = (ParticleSystem *)ob->particlesystem.first; psys; psys = psys->next) {
+               ParticleSettings *part = psys->part;
+
+               /* particle settings */
+               build_animdata(&part->id);
+
+               /* this particle system */
+               OperationKey psys_key(&ob->id, DEPSNODE_TYPE_EVAL_PARTICLES, DEG_OPCODE_PSYS_EVAL, psys->name);
+
+               /* XXX: if particle system is later re-enabled, we must do full rebuild? */
+               if (!psys_check_enabled(ob, psys))
+                       continue;
+
+#if 0
+               if (ELEM(part->phystype, PART_PHYS_KEYED, PART_PHYS_BOIDS)) {
+                       ParticleTarget *pt;
+
+                       for (pt = psys->targets.first; pt; pt = pt->next) {
+                               if (pt->ob && BLI_findlink(&pt->ob->particlesystem, pt->psys - 1)) {
+                                       node2 = dag_get_node(dag, pt->ob);
+                                       dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Particle Targets");
+                               }
+                       }
+               }
+
+               if (part->ren_as == PART_DRAW_OB && part->dup_ob) {
+                       node2 = dag_get_node(dag, part->dup_ob);
+                       /* note that this relation actually runs in the wrong direction, the problem
+                        * is that dupli system all have this (due to parenting), and the render
+                        * engine instancing assumes particular ordering of objects in list */
+                       dag_add_relation(dag, node, node2, DAG_RL_OB_OB, "Particle Object Visualization");
+                       if (part->dup_ob->type == OB_MBALL)
+                               dag_add_relation(dag, node, node2, DAG_RL_DATA_DATA, "Particle Object Visualization");
+               }
+
+               if (part->ren_as == PART_DRAW_GR && part->dup_group) {
+                       for (go = part->dup_group->gobject.first; go; go = go->next) {
+                               node2 = dag_get_node(dag, go->ob);
+                               dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Particle Group Visualization");
+                       }
+               }
+#endif
+
+               /* effectors */
+               ListBase *effectors = pdInitEffectors(scene, ob, psys, part->effector_weights, false);
+
+               if (effectors) {
+                       for (EffectorCache *eff = (EffectorCache *)effectors->first; eff; eff = eff->next) {
+                               if (eff->psys) {
+                                       // XXX: DAG_RL_DATA_DATA | DAG_RL_OB_DATA
+                                       ComponentKey eff_key(&eff->ob->id, DEPSNODE_TYPE_GEOMETRY); // xxx: particles instead?
+                                       add_relation(eff_key, psys_key, DEPSREL_TYPE_STANDARD, "Particle Field");
+                               }
+                       }
+               }
+
+               pdEndEffectors(&effectors);
+
+               /* boids */
+               if (part->boids) {
+                       BoidRule *rule = NULL;
+                       BoidState *state = NULL;
+
+                       for (state = (BoidState *)part->boids->states.first; state; state = state->next) {
+                               for (rule = (BoidRule *)state->rules.first; rule; rule = rule->next) {
+                                       Object *ruleob = NULL;
+                                       if (rule->type == eBoidRuleType_Avoid)
+                                               ruleob = ((BoidRuleGoalAvoid *)rule)->ob;
+                                       else if (rule->type == eBoidRuleType_FollowLeader)
+                                               ruleob = ((BoidRuleFollowLeader *)rule)->ob;
+
+                                       if (ruleob) {
+                                               ComponentKey ruleob_key(&ruleob->id, DEPSNODE_TYPE_TRANSFORM);
+                                               add_relation(ruleob_key, psys_key, DEPSREL_TYPE_TRANSFORM, "Boid Rule");
+                                       }
+                               }
+                       }
+               }
+       }
+
+       /* pointcache */
+       // TODO...
+}
+
+/* IK Solver Eval Steps */
+void DepsgraphRelationBuilder::build_ik_pose(Object *ob,
+                                             bPoseChannel *pchan,
+                                             bConstraint *con,
+                                             RootPChanMap *root_map)
+{
+       bKinematicConstraint *data = (bKinematicConstraint *)con->data;
+
+       /* attach owner to IK Solver too
+        * - assume that owner is always part of chain
+        * - see notes on direction of rel below...
+        */
+       bPoseChannel *rootchan = BKE_armature_ik_solver_find_root(pchan, data);
+       OperationKey solver_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, rootchan->name, DEG_OPCODE_POSE_IK_SOLVER);
+
+       /* IK target */
+       // XXX: this should get handled as part of the constraint code
+       if (data->tar != NULL) {
+               /* TODO(sergey): For until we'll store partial matricies in the depsgraph,
+                * we create dependency between target object and pose eval component.
+                *
+                * This way we ensuring the whole subtree is updated from scratch without
+                * need of intermediate matricies. This is an overkill, but good enough for
+                * testing IK solver.
+                */
+               // FIXME: geometry targets...
+               ComponentKey pose_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE);
+               if ((data->tar->type == OB_ARMATURE) && (data->subtarget[0])) {
+                       /* TODO(sergey): This is only for until granular update stores intermediate result. */
+                       if (data->tar != ob) {
+                               /* different armature - can just read the results */
+                               ComponentKey target_key(&data->tar->id, DEPSNODE_TYPE_BONE, data->subtarget);
+                               add_relation(target_key, pose_key, DEPSREL_TYPE_TRANSFORM, con->name);
+                       }
+                       else {
+                               /* same armature - we'll use the ready state only, just in case this bone is in the chain we're solving */
+                               OperationKey target_key(&data->tar->id, DEPSNODE_TYPE_BONE, data->subtarget, DEG_OPCODE_BONE_DONE);
+                               add_relation(target_key, solver_key, DEPSREL_TYPE_TRANSFORM, con->name);
+                       }
+               }
+               else if (ELEM(data->tar->type, OB_MESH, OB_LATTICE) && (data->subtarget[0])) {
+                       /* vertex group target */
+                       /* NOTE: for now, we don't need to represent vertex groups separately... */
+                       ComponentKey target_key(&data->tar->id, DEPSNODE_TYPE_GEOMETRY);
+                       add_relation(target_key, solver_key, DEPSREL_TYPE_GEOMETRY_EVAL, con->name);
+
+                       if (data->tar->type == OB_MESH) {
+                               //node2->customdata_mask |= CD_MASK_MDEFORMVERT;
+                       }
+               }
+               else {
+                       /* Standard Object Target */
+                       ComponentKey target_key(&data->tar->id, DEPSNODE_TYPE_TRANSFORM);
+                       add_relation(target_key, pose_key, DEPSREL_TYPE_TRANSFORM, con->name);
+               }
+
+               if ((data->tar == ob) && (data->subtarget[0])) {
+                       /* Prevent target's constraints from linking to anything from same
+                        * chain that it controls.
+                        */
+                       root_map->add_bone(data->subtarget, rootchan->name);
+               }
+       }
+
+       /* Pole Target */
+       // XXX: this should get handled as part of the constraint code
+       if (data->poletar != NULL) {
+               if ((data->tar->type == OB_ARMATURE) && (data->subtarget[0])) {
+                       // XXX: same armature issues - ready vs done?
+                       ComponentKey target_key(&data->poletar->id, DEPSNODE_TYPE_BONE, data->subtarget);
+                       add_relation(target_key, solver_key, DEPSREL_TYPE_TRANSFORM, con->name);
+               }
+               else if (ELEM(data->poletar->type, OB_MESH, OB_LATTICE) && (data->subtarget[0])) {
+                       /* vertex group target */
+                       /* NOTE: for now, we don't need to represent vertex groups separately... */
+                       ComponentKey target_key(&data->poletar->id, DEPSNODE_TYPE_GEOMETRY);
+                       add_relation(target_key, solver_key, DEPSREL_TYPE_GEOMETRY_EVAL, con->name);
+
+                       if (data->poletar->type == OB_MESH) {
+                               //node2->customdata_mask |= CD_MASK_MDEFORMVERT;
+                       }
+               }
+               else {
+                       ComponentKey target_key(&data->poletar->id, DEPSNODE_TYPE_TRANSFORM);
+                       add_relation(target_key, solver_key, DEPSREL_TYPE_TRANSFORM, con->name);
+               }
+       }
+
+       DEG_DEBUG_PRINTF("\nStarting IK Build: pchan = %s, target = (%s, %s), segcount = %d\n",
+                        pchan->name, data->tar->id.name, data->subtarget, data->rootbone);
+
+       bPoseChannel *parchan = pchan;
+       /* exclude tip from chain? */
+       if (!(data->flag & CONSTRAINT_IK_TIP)) {
+               OperationKey tip_transforms_key(&ob->id, DEPSNODE_TYPE_BONE,
+                                               parchan->name, DEG_OPCODE_BONE_LOCAL);
+               add_relation(solver_key, tip_transforms_key,
+                            DEPSREL_TYPE_TRANSFORM, "IK Solver Result");
+               parchan = pchan->parent;
+       }
+
+       root_map->add_bone(parchan->name, rootchan->name);
+
+       OperationKey parchan_transforms_key(&ob->id, DEPSNODE_TYPE_BONE,
+                                           parchan->name, DEG_OPCODE_BONE_READY);
+       add_relation(parchan_transforms_key, solver_key,
+                    DEPSREL_TYPE_TRANSFORM, "IK Solver Owner");
+
+       /* Walk to the chain's root */
+       //size_t segcount = 0;
+       int segcount = 0;
+
+       while (parchan) {
+               /* Make IK-solver dependent on this bone's result,
+                * since it can only run after the standard results
+                * of the bone are know. Validate links step on the
+                * bone will ensure that users of this bone only
+                * grab the result with IK solver results...
+                */
+               if (parchan != pchan) {
+                       OperationKey parent_key(&ob->id, DEPSNODE_TYPE_BONE, parchan->name, DEG_OPCODE_BONE_READY);
+                       add_relation(parent_key, solver_key, DEPSREL_TYPE_TRANSFORM, "IK Chain Parent");
+
+                       OperationKey done_key(&ob->id, DEPSNODE_TYPE_BONE, parchan->name, DEG_OPCODE_BONE_DONE);
+                       add_relation(solver_key, done_key, DEPSREL_TYPE_TRANSFORM, "IK Chain Result");
+               }
+               parchan->flag |= POSE_DONE;
+
+               OperationKey final_transforms_key(&ob->id, DEPSNODE_TYPE_BONE, parchan->name, DEG_OPCODE_BONE_DONE);
+               add_relation(solver_key, final_transforms_key, DEPSREL_TYPE_TRANSFORM, "IK Solver Result");
+
+               root_map->add_bone(parchan->name, rootchan->name);
+
+               /* continue up chain, until we reach target number of items... */
+               DEG_DEBUG_PRINTF("  %d = %s\n", segcount, parchan->name);
+               segcount++;
+               if ((segcount == data->rootbone) || (segcount > 255)) break;  /* 255 is weak */
+
+               parchan  = parchan->parent;
+       }
+
+       OperationKey flush_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, DEG_OPCODE_POSE_DONE);
+       add_relation(solver_key, flush_key, DEPSREL_TYPE_OPERATION, "PoseEval Result-Bone Link");
+}
+
+/* Spline IK Eval Steps */
+void DepsgraphRelationBuilder::build_splineik_pose(Object *ob,
+                                                   bPoseChannel *pchan,
+                                                   bConstraint *con,
+                                                   RootPChanMap *root_map)
+{
+       bSplineIKConstraint *data = (bSplineIKConstraint *)con->data;
+       bPoseChannel *rootchan = BKE_armature_splineik_solver_find_root(pchan, data);
+       OperationKey transforms_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_READY);
+       OperationKey solver_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, rootchan->name, DEG_OPCODE_POSE_SPLINE_IK_SOLVER);
+
+       /* attach owner to IK Solver too
+        * - assume that owner is always part of chain
+        * - see notes on direction of rel below...
+        */
+       add_relation(transforms_key, solver_key, DEPSREL_TYPE_TRANSFORM, "Spline IK Solver Owner");
+
+       /* attach path dependency to solver */
+       if (data->tar) {
+               /* TODO(sergey): For until we'll store partial matricies in the depsgraph,
+                * we create dependency between target object and pose eval component.
+                * See IK pose for a bit more information.
+                */
+               // TODO: the bigggest point here is that we need the curve PATH and not just the general geometry...
+               ComponentKey target_key(&data->tar->id, DEPSNODE_TYPE_GEOMETRY);
+               ComponentKey pose_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE);
+               add_relation(target_key, pose_key, DEPSREL_TYPE_TRANSFORM,"[Curve.Path -> Spline IK] DepsRel");
+       }
+
+       pchan->flag |= POSE_DONE;
+       OperationKey final_transforms_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_DONE);
+       add_relation(solver_key, final_transforms_key, DEPSREL_TYPE_TRANSFORM, "Spline IK Result");
+
+       root_map->add_bone(pchan->name, rootchan->name);
+
+       /* Walk to the chain's root */
+       //size_t segcount = 0;
+       int segcount = 0;
+
+       for (bPoseChannel *parchan = pchan->parent; parchan; parchan = parchan->parent) {
+               /* Make Spline IK solver dependent on this bone's result,
+                * since it can only run after the standard results
+                * of the bone are know. Validate links step on the
+                * bone will ensure that users of this bone only
+                * grab the result with IK solver results...
+                */
+               if (parchan != pchan) {
+                       OperationKey parent_key(&ob->id, DEPSNODE_TYPE_BONE, parchan->name, DEG_OPCODE_BONE_READY);
+                       add_relation(parent_key, solver_key, DEPSREL_TYPE_TRANSFORM, "Spline IK Solver Update");
+
+                       OperationKey done_key(&ob->id, DEPSNODE_TYPE_BONE, parchan->name, DEG_OPCODE_BONE_DONE);
+                       add_relation(solver_key, done_key, DEPSREL_TYPE_TRANSFORM, "IK Chain Result");
+               }
+               parchan->flag |= POSE_DONE;
+
+               OperationKey final_transforms_key(&ob->id, DEPSNODE_TYPE_BONE, parchan->name, DEG_OPCODE_BONE_DONE);
+               add_relation(solver_key, final_transforms_key, DEPSREL_TYPE_TRANSFORM, "Spline IK Solver Result");
+
+               root_map->add_bone(parchan->name, rootchan->name);
+
+               /* continue up chain, until we reach target number of items... */
+               segcount++;
+               if ((segcount == data->chainlen) || (segcount > 255)) break;  /* 255 is weak */
+       }
+
+       OperationKey flush_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, DEG_OPCODE_POSE_DONE);
+       add_relation(solver_key, flush_key, DEPSREL_TYPE_OPERATION, "PoseEval Result-Bone Link");
+}
+
+/* Pose/Armature Bones Graph */
+void DepsgraphRelationBuilder::build_rig(Scene *scene, Object *ob)
+{
+       /* Armature-Data */
+       // TODO: selection status?
+
+       /* attach links between pose operations */
+       OperationKey init_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, DEG_OPCODE_POSE_INIT);
+       OperationKey flush_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, DEG_OPCODE_POSE_DONE);
+
+       add_relation(init_key, flush_key, DEPSREL_TYPE_COMPONENT_ORDER, "[Pose Init -> Pose Cleanup]");
+
+       if (ob->adt && (ob->adt->action || ob->adt->nla_tracks.first)) {
+               ComponentKey animation_key(&ob->id, DEPSNODE_TYPE_ANIMATION);
+               add_relation(animation_key, init_key, DEPSREL_TYPE_OPERATION, "Rig Animation");
+       }
+
+       /* IK Solvers...
+       * - These require separate processing steps are pose-level
+       *   to be executed between chains of bones (i.e. once the
+       *   base transforms of a bunch of bones is done)
+       *
+       * - We build relations for these before the dependencies
+       *   between ops in the same component as it is necessary
+       *   to check whether such bones are in the same IK chain
+       *   (or else we get weird issues with either in-chain
+       *   references, or with bones being parented to IK'd bones)
+       *
+       * Unsolved Issues:
+       * - Care is needed to ensure that multi-headed trees work out the same as in ik-tree building
+       * - Animated chain-lengths are a problem...
+       */
+       RootPChanMap root_map;
+       bool pose_depends_on_local_transform = false;
+       for (bPoseChannel *pchan = (bPoseChannel *)ob->pose->chanbase.first; pchan; pchan = pchan->next) {
+               for (bConstraint *con = (bConstraint *)pchan->constraints.first; con; con = con->next) {
+                       switch (con->type) {
+                               case CONSTRAINT_TYPE_KINEMATIC:
+                                       build_ik_pose(ob, pchan, con, &root_map);
+                                       pose_depends_on_local_transform = true;
+                                       break;
+
+                               case CONSTRAINT_TYPE_SPLINEIK:
+                                       build_splineik_pose(ob, pchan, con, &root_map);
+                                       pose_depends_on_local_transform = true;
+                                       break;
+
+                               /* Constraints which needs world's matrix for transform.
+                                * TODO(sergey): More constraints here?
+                                */
+                               case CONSTRAINT_TYPE_ROTLIKE:
+                               case CONSTRAINT_TYPE_SIZELIKE:
+                               case CONSTRAINT_TYPE_LOCLIKE:
+                               case CONSTRAINT_TYPE_TRANSLIKE:
+                                       /* TODO(sergey): Add used space check. */
+                                       pose_depends_on_local_transform = true;
+                                       break;
+
+                               default:
+                                       break;
+                       }
+               }
+       }
+       //root_map.print_debug();
+
+       if (pose_depends_on_local_transform) {
+               /* TODO(sergey): Once partial updates are possible use relation between
+                * object transform and solver itself in it's build function.
+                */
+               ComponentKey pose_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE);
+               ComponentKey local_transform_key(&ob->id, DEPSNODE_TYPE_TRANSFORM);
+               add_relation(local_transform_key, pose_key, DEPSREL_TYPE_TRANSFORM, "Local Transforms");
+       }
+
+
+       /* links between operations for each bone */
+       for (bPoseChannel *pchan = (bPoseChannel *)ob->pose->chanbase.first; pchan; pchan = pchan->next) {
+               OperationKey bone_local_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_LOCAL);
+               OperationKey bone_pose_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_POSE_PARENT);
+               OperationKey bone_ready_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_READY);
+               OperationKey bone_done_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_DONE);
+
+               pchan->flag &= ~POSE_DONE;
+
+               /* pose init to bone local */
+               add_relation(init_key, bone_local_key, DEPSREL_TYPE_OPERATION, "PoseEval Source-Bone Link");
+
+               /* local to pose parenting operation */
+               add_relation(bone_local_key, bone_pose_key, DEPSREL_TYPE_OPERATION, "Bone Local - PoseSpace Link");
+
+               /* parent relation */
+               if (pchan->parent != NULL) {
+                       eDepsOperation_Code parent_key_opcode;
+
+                       /* NOTE: this difference in handling allows us to prevent lockups while ensuring correct poses for separate chains */
+                       if (root_map.has_common_root(pchan->name, pchan->parent->name)) {
+                               parent_key_opcode = DEG_OPCODE_BONE_READY;
+                       }
+                       else {
+                               parent_key_opcode = DEG_OPCODE_BONE_DONE;
+                       }
+
+                       OperationKey parent_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->parent->name, parent_key_opcode);
+                       add_relation(parent_key, bone_pose_key, DEPSREL_TYPE_TRANSFORM, "[Parent Bone -> Child Bone]");
+               }
+
+               /* constraints */
+               if (pchan->constraints.first != NULL) {
+                       /* constraints stack and constraint dependencies */
+                       build_constraints(scene, &ob->id, DEPSNODE_TYPE_BONE, pchan->name, &pchan->constraints, &root_map);
+
+                       /* pose -> constraints */
+                       OperationKey constraints_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_CONSTRAINTS);
+                       add_relation(bone_pose_key, constraints_key, DEPSREL_TYPE_OPERATION, "Constraints Stack");
+
+                       /* constraints -> ready */
+                       // TODO: when constraint stack is exploded, this step should occur before the first IK solver
+                       add_relation(constraints_key, bone_ready_key, DEPSREL_TYPE_OPERATION, "Constraints -> Ready");
+               }
+               else {
+                       /* pose -> ready */
+                       add_relation(bone_pose_key, bone_ready_key, DEPSREL_TYPE_OPERATION, "Pose -> Ready");
+               }
+
+               /* bone ready -> done
+                * NOTE: For bones without IK, this is all that's needed.
+                *       For IK chains however, an additional rel is created from IK to done,
+                *       with transitive reduction removing this one...
+                */
+               add_relation(bone_ready_key, bone_done_key, DEPSREL_TYPE_OPERATION, "Ready -> Done");
+
+               /* assume that all bones must be done for the pose to be ready (for deformers) */
+               add_relation(bone_done_key, flush_key, DEPSREL_TYPE_OPERATION, "PoseEval Result-Bone Link");
+       }
+}
+
+void DepsgraphRelationBuilder::build_proxy_rig(Object *ob)
+{
+       OperationKey pose_init_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, DEG_OPCODE_POSE_INIT);
+       OperationKey pose_done_key(&ob->id, DEPSNODE_TYPE_EVAL_POSE, DEG_OPCODE_POSE_DONE);
+       for (bPoseChannel *pchan = (bPoseChannel *)ob->pose->chanbase.first;
+            pchan != NULL;
+            pchan = pchan->next)
+       {
+               OperationKey bone_local_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_LOCAL);
+               OperationKey bone_ready_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_READY);
+               OperationKey bone_done_key(&ob->id, DEPSNODE_TYPE_BONE, pchan->name, DEG_OPCODE_BONE_DONE);
+               add_relation(pose_init_key, bone_local_key, DEPSREL_TYPE_OPERATION, "Pose Init -> Bone Local");
+               add_relation(bone_local_key, bone_ready_key, DEPSREL_TYPE_OPERATION, "Local -> Ready");
+               add_relation(bone_ready_key, bone_done_key, DEPSREL_TYPE_OPERATION, "Ready -> Done");
+               add_relation(bone_done_key, pose_done_key, DEPSREL_TYPE_OPERATION, "Bone Done -> Pose Done");
+       }
+}
+
+/* Shapekeys */
+void DepsgraphRelationBuilder::build_shapekeys(ID *obdata, Key *key)
+{
+       ComponentKey obdata_key(obdata, DEPSNODE_TYPE_GEOMETRY);
+
+       /* attach animdata to geometry */
+       build_animdata(&key->id);
+
+       if (key->adt) {
+               // TODO: this should really be handled in build_animdata, since many of these cases will need it
+               if (key->adt->action || key->adt->nla_tracks.first) {
+                       ComponentKey adt_key(&key->id, DEPSNODE_TYPE_ANIMATION);
+                       add_relation(adt_key, obdata_key, DEPSREL_TYPE_OPERATION, "Animation");
+               }
+
+               /* NOTE: individual shapekey drivers are handled above already */
+       }
+
+       /* attach to geometry */
+       // XXX: aren't shapekeys now done as a pseudo-modifier on object?
+       //ComponentKey key_key(&key->id, DEPSNODE_TYPE_GEOMETRY); // FIXME: this doesn't exist
+       //add_relation(key_key, obdata_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Shapekeys");
+}
+
+/**
+ * ObData Geometry Evaluation
+ * ==========================
+ *
+ * The evaluation of geometry on objects is as follows:
+ * - The actual evaluated of the derived geometry (e.g. DerivedMesh, DispList, etc.)
+ *   occurs in the Geometry component of the object which references this. This includes
+ *   modifiers, and the temporary "ubereval" for geometry.
+ * - Therefore, each user of a piece of shared geometry data ends up evaluating its own
+ *   version of the stuff, complete with whatever modifiers it may use.
+ *
+ * - The datablocks for the geometry data - "obdata" (e.g. ID_ME, ID_CU, ID_LT, etc.) are used for
+ *     1) calculating the bounding boxes of the geometry data,
+ *     2) aggregating inward links from other objects (e.g. for text on curve, etc.)
+ *        and also for the links coming from the shapekey datablocks
+ * - Animation/Drivers affecting the parameters of the geometry are made to trigger
+ *   updates on the obdata geometry component, which then trigger downstream
+ *   re-evaluation of the individual instances of this geometry.
+ */
+// TODO: Materials and lighting should probably get their own component, instead of being lumped under geometry?
+void DepsgraphRelationBuilder::build_obdata_geom(Main *bmain, Scene *scene, Object *ob)
+{
+       ID *obdata = (ID *)ob->data;
+
+       /* Init operation of object-level geometry evaluation. */
+       OperationKey geom_init_key(&ob->id, DEPSNODE_TYPE_GEOMETRY, DEG_OPCODE_PLACEHOLDER, "Eval Init");
+
+       /* get nodes for result of obdata's evaluation, and geometry evaluation on object */
+       ComponentKey obdata_geom_key(obdata, DEPSNODE_TYPE_GEOMETRY);
+       ComponentKey geom_key(&ob->id, DEPSNODE_TYPE_GEOMETRY);
+
+       /* link components to each other */
+       add_relation(obdata_geom_key, geom_key, DEPSREL_TYPE_DATABLOCK, "Object Geometry Base Data");
+
+       /* Modifiers */
+       if (ob->modifiers.first) {
+               ModifierData *md;
+               OperationKey prev_mod_key;
+
+               for (md = (ModifierData *)ob->modifiers.first; md; md = md->next) {
+                       const ModifierTypeInfo *mti = modifierType_getInfo((ModifierType)md->type);
+                       OperationKey mod_key(&ob->id, DEPSNODE_TYPE_GEOMETRY, DEG_OPCODE_GEOMETRY_MODIFIER, md->name);
+
+                       if (md->prev) {
+                               /* Stack relation: modifier depends on previous modifier in the stack */
+                               add_relation(prev_mod_key, mod_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Modifier Stack");
+                       }
+                       else {
+                               /* Stack relation: first modifier depends on the geometry. */
+                               add_relation(geom_init_key, mod_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Modifier Stack");
+                       }
+
+                       if (mti->updateDepsgraph) {
+                               DepsNodeHandle handle = create_node_handle(mod_key);
+                               mti->updateDepsgraph(md, bmain, scene, ob, &handle);
+                       }
+
+                       if (BKE_object_modifier_use_time(ob, md)) {
+                               TimeSourceKey time_src_key;
+                               add_relation(time_src_key, mod_key, DEPSREL_TYPE_TIME, "Time Source");
+                       }
+
+                       prev_mod_key = mod_key;
+               }
+       }
+
+       /* materials */
+       if (ob->totcol) {
+               int a;
+
+               for (a = 1; a <= ob->totcol; a++) {
+                       Material *ma = give_current_material(ob, a);
+
+                       if (ma)
+                               build_material(&ob->id, ma);
+               }
+       }
+
+       /* geometry collision */
+       if (ELEM(ob->type, OB_MESH, OB_CURVE, OB_LATTICE)) {
+               // add geometry collider relations
+       }
+
+       /* Make sure uber update is the last in the dependencies.
+        *
+        * TODO(sergey): Get rid of this node.
+        */
+       if (ob->type != OB_ARMATURE) {
+               /* Armatures does no longer require uber node. */
+               OperationKey obdata_ubereval_key(&ob->id, DEPSNODE_TYPE_GEOMETRY, DEG_OPCODE_GEOMETRY_UBEREVAL);
+               if (ob->modifiers.last) {
+                       ModifierData *md = (ModifierData *)ob->modifiers.last;
+                       OperationKey mod_key(&ob->id, DEPSNODE_TYPE_GEOMETRY, DEG_OPCODE_GEOMETRY_MODIFIER, md->name);
+                       add_relation(mod_key, obdata_ubereval_key, DEPSREL_TYPE_OPERATION, "Object Geometry UberEval");
+               }
+               else {
+                       add_relation(geom_init_key, obdata_ubereval_key, DEPSREL_TYPE_OPERATION, "Object Geometry UberEval");
+               }
+       }
+
+       if (obdata->flag & LIB_DOIT) {
+               return;
+       }
+       obdata->flag |= LIB_DOIT;
+
+       /* Link object data evaluation node to exit operation. */
+       OperationKey obdata_geom_eval_key(obdata, DEPSNODE_TYPE_GEOMETRY, DEG_OPCODE_PLACEHOLDER, "Geometry Eval");
+       OperationKey obdata_geom_done_key(obdata, DEPSNODE_TYPE_GEOMETRY, DEG_OPCODE_PLACEHOLDER, "Eval Done");
+       add_relation(obdata_geom_eval_key, obdata_geom_done_key, DEPSREL_TYPE_DATABLOCK, "ObData Geom Eval Done");
+
+       /* type-specific node/links */
+       switch (ob->type) {
+               case OB_MESH:
+                       break;
+
+               case OB_MBALL:
+               {
+                       Object *mom = BKE_mball_basis_find(scene, ob);
+
+                       /* motherball - mom depends on children! */
+                       if (mom != ob) {
+                               /* non-motherball -> cannot be directly evaluated! */
+                               ComponentKey mom_key(&mom->id, DEPSNODE_TYPE_GEOMETRY);
+                               add_relation(geom_key, mom_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Metaball Motherball");
+                       }
+               }
+               break;
+
+               case OB_CURVE:
+               case OB_FONT:
+               {
+                       Curve *cu = (Curve *)obdata;
+
+                       /* curve's dependencies */
+                       // XXX: these needs geom data, but where is geom stored?
+                       if (cu->bevobj) {
+                               ComponentKey bevob_key(&cu->bevobj->id, DEPSNODE_TYPE_GEOMETRY);
+                               add_relation(bevob_key, geom_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Curve Bevel");
+                       }
+                       if (cu->taperobj) {
+                               ComponentKey taperob_key(&cu->taperobj->id, DEPSNODE_TYPE_GEOMETRY);
+                               add_relation(taperob_key, geom_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Curve Taper");
+                       }
+                       if (ob->type == OB_FONT) {
+                               if (cu->textoncurve) {
+                                       ComponentKey textoncurve_key(&cu->taperobj->id, DEPSNODE_TYPE_GEOMETRY);
+                                       add_relation(textoncurve_key, geom_key, DEPSREL_TYPE_GEOMETRY_EVAL, "Text on Curve");
+                               }
+                       }
+               }
+               break;
+
+               case OB_SURF: /* Nurbs Surface */
+               {
+               }
+               break;
+
+               case OB_LATTICE: /* Lattice */
+               {
+               }
+               break;
+       }
+
+       /* ShapeKeys */
+       Key *key = BKE_key_from_object(ob);
+       if (key) {
+               build_shapekeys(obdata, key);
+       }
+
+       if (needs_animdata_node(obdata)) {
+               ComponentKey animation_key(obdata, DEPSNODE_TYPE_ANIMATION);
+               ComponentKey parameters_key(obdata, DEPSNODE_TYPE_PARAMETERS);
+               add_relation(animation_key, parameters_key,
+                            DEPSREL_TYPE_COMPONENT_ORDER, "Geom Parameters");
+       }
+}
+
+/* Cameras */
+// TODO: Link scene-camera links in somehow...
+void DepsgraphRelationBuilder::build_camera(Object *ob)
+{
+       Camera *cam = (Camera *)ob->data;
+       ID *camera_id = &cam->id;
+       if (camera_id->flag & LIB_DOIT) {
+               return;
+       }
+       camera_id->flag |= LIB_DOIT;
+
+       ComponentKey parameters_key(camera_id, DEPSNODE_TYPE_PARAMETERS);
+
+       if (needs_animdata_node(camera_id)) {
+               ComponentKey animation_key(camera_id, DEPSNODE_TYPE_ANIMATION);
+               add_relation(animation_key, parameters_key,
+                            DEPSREL_TYPE_COMPONENT_ORDER, "Camera Parameters");
+       }
+
+       /* DOF */
+       if (cam->dof_ob) {
+               ComponentKey ob_param_key(&ob->id, DEPSNODE_TYPE_PARAMETERS);
+               ComponentKey dof_ob_key(&cam->dof_ob->id, DEPSNODE_TYPE_TRANSFORM);
+               add_relation(dof_ob_key, ob_param_key, DEPSREL_TYPE_TRANSFORM, "Camera DOF");
+       }
+}
+
+/* Lamps */
+void DepsgraphRelationBuilder::build_lamp(Object *ob)
+{
+       Lamp *la = (Lamp *)ob->data;
+       ID *lamp_id = &la->id;
+       if (lamp_id->flag & LIB_DOIT) {
+               return;
+       }
+       lamp_id->flag |= LIB_DOIT;
+
+       ComponentKey parameters_key(lamp_id, DEPSNODE_TYPE_PARAMETERS);
+
+       if (needs_animdata_node(lamp_id)) {
+               ComponentKey animation_key(lamp_id, DEPSNODE_TYPE_ANIMATION);
+               add_relation(animation_key, parameters_key,
+                            DEPSREL_TYPE_COMPONENT_ORDER, "Lamp Parameters");
+       }
+
+       /* lamp's nodetree */
+       if (la->nodetree) {
+               build_nodetree(lamp_id, la->nodetree);
+               ComponentKey nodetree_key(&la->nodetree->id, DEPSNODE_TYPE_PARAMETERS);
+               add_relation(nodetree_key, parameters_key,
+                            DEPSREL_TYPE_COMPONENT_ORDER, "NTree->Lamp Parameters");
+       }
+
+       /* textures */
+       build_texture_stack(lamp_id, la->mtex);
+}
+
+void DepsgraphRelationBuilder::build_nodetree(ID *owner, bNodeTree *ntree)
+{
+       if (!ntree)
+               return;
+
+       ID *ntree_id = &ntree->id;
+
+       build_animdata(ntree_id);
+
+       /* nodetree's nodes... */
+       for (bNode *bnode = (bNode *)ntree->nodes.first; bnode; bnode = bnode->next) {
+               if (bnode->id) {
+                       if (GS(bnode->id->name) == ID_MA) {
+                               build_material(owner, (Material *)bnode->id);
+                       }
+                       else if (bnode->type == ID_TE) {
+                               build_texture(owner, (Tex *)bnode->id);
+                       }
+                       else if (bnode->type == NODE_GROUP) {
+                               bNodeTree *ntree = (bNodeTree *)bnode->id;
+                               if ((ntree_id->flag & LIB_DOIT) == 0) {
+                                       build_nodetree(owner, ntree);
+                                       ntree_id->flag |= LIB_DOIT;
+                               }
+                       }
+               }
+       }
+
+       if (needs_animdata_node(ntree_id)) {
+               ComponentKey parameters_key(ntree_id, DEPSNODE_TYPE_PARAMETERS);
+               ComponentKey animation_key(ntree_id, DEPSNODE_TYPE_ANIMATION);
+               add_relation(animation_key, parameters_key,
+                            DEPSREL_TYPE_COMPONENT_ORDER, "NTree Parameters");
+       }
+
+       // TODO: link from nodetree to owner_component?
+}
+
+/* Recursively build graph for material */
+void DepsgraphRelationBuilder::build_material(ID *owner, Material *ma)
+{
+       ID *ma_id = &ma->id;
+       if (ma_id->flag & LIB_DOIT) {
+               return;
+       }
+       ma_id->flag |= LIB_DOIT;
+
+       /* animation */
+       build_animdata(ma_id);
+
+       /* textures */
+       build_texture_stack(owner, ma->mtex);
+
+       /* material's nodetree */
+       build_nodetree(owner, ma->nodetree);
+}
+
+/* Recursively build graph for texture */
+void DepsgraphRelationBuilder::build_texture(ID *owner, Tex *tex)
+{
+       ID *tex_id = &tex->id;
+       if (tex_id->flag & LIB_DOIT) {
+               return;
+       }
+       tex_id->flag |= LIB_DOIT;
+
+       /* texture itself */
+       build_animdata(tex_id);
+
+       /* texture's nodetree */
+       build_nodetree(owner, tex->nodetree);
+}
+
+/* Texture-stack attached to some shading datablock */
+void DepsgraphRelationBuilder::build_texture_stack(ID *owner, MTex **texture_stack)
+{
+       int i;
+
+       /* for now assume that all texture-stacks have same number of max items */
+       for (i = 0; i < MAX_MTEX; i++) {
+               MTex *mtex = texture_stack[i];
+               if (mtex && mtex->tex)
+                       build_texture(owner, mtex->tex);
+       }
+}
+
+void DepsgraphRelationBuilder::build_compositor(Scene *scene)
+{
+       /* For now, just a plain wrapper? */
+       build_nodetree(&scene->id, scene->nodetree);
+}
+
+void DepsgraphRelationBuilder::build_gpencil(ID *UNUSED(owner), bGPdata *gpd)
+{
+       /* animation */
+       build_animdata(&gpd->id);
+
+       // TODO: parent object (when that feature is implemented)
+}
+
+bool DepsgraphRelationBuilder::needs_animdata_node(ID *id)
+{
+       AnimData *adt = BKE_animdata_from_id(id);
+       if (adt != NULL) {
+               return adt->action != NULL;
+       }
+       return false;
+}
+
diff --git a/source/blender/depsgraph/intern/depsgraph_debug.cc b/source/blender/depsgraph/intern/depsgraph_debug.cc
new file mode 100644 (file)
index 0000000..c876640
--- /dev/null
@@ -0,0 +1,1187 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2014 Blender Foundation.
+ * All rights reserved.
+ *
+ * Original Author: Lukas Toenne
+ * Contributor(s): None Yet
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ *
+ * Implementation of tools for debugging the depsgraph
+ */
+
+//#include <stdlib.h>
+#include <string.h>
+
+extern "C" {
+#include "BLI_utildefines.h"
+#include "BLI_listbase.h"
+#include "BLI_ghash.h"
+#include "BLI_string.h"
+
+#include "DNA_scene_types.h"
+#include "DNA_userdef_types.h"
+
+#include "DEG_depsgraph.h"
+#include "DEG_depsgraph_debug.h"
+#include "DEG_depsgraph_build.h"
+
+#include "WM_api.h"
+#include "WM_types.h"
+}  /* extern "C" */
+
+#include "depsgraph_debug.h"
+#include "depsnode.h"
+#include "depsnode_component.h"
+#include "depsnode_operation.h"
+#include "depsgraph_intern.h"
+
+/* ****************** */
+/* Graphviz Debugging */
+
+static SpinLock lock;
+
+#define NL "\r\n"
+
+/* Only one should be enabled, defines whether graphviz nodes
+ * get colored by individual types or classes.
+ */
+#define COLOR_SCHEME_NODE_CLASS 1
+//#define COLOR_SCHEME_NODE_TYPE  2
+
+static const char *deg_debug_graphviz_fontname = "helvetica";
+static float deg_debug_graphviz_graph_label_size = 20.0f;
+static float deg_debug_graphviz_node_label_size = 14.0f;
+static const int deg_debug_max_colors = 12;
+#if 0
+static const char *deg_debug_colors_dark[] = {
+    "#6e8997", "#144f77", "#76945b",
+    "#216a1d", "#a76665", "#971112",
+    "#a87f49", "#0a9540", "#86768e",
+    "#462866", "#a9a965", "#753b1a",
+};
+#endif
+#ifdef COLOR_SCHEME_NODE_TYPE
+static const char *deg_debug_colors[] = {
+    "#a6cee3", "#1f78b4", "#b2df8a",
+    "#33a02c", "#fb9a99", "#e31a1c",
+    "#fdbf6f", "#ff7f00", "#cab2d6",
+    "#6a3d9a", "#ffff99", "#b15928",
+};
+#endif
+static const char *deg_debug_colors_light[] = {
+    "#8dd3c7", "#ffffb3", "#bebada",
+    "#fb8072", "#80b1d3", "#fdb462",
+    "#b3de69", "#fccde5", "#d9d9d9",
+    "#bc80bd", "#ccebc5", "#ffed6f",
+};
+
+#ifdef COLOR_SCHEME_NODE_TYPE
+static const int deg_debug_node_type_color_map[][2] = {
+    {DEPSNODE_TYPE_ROOT,         0},
+    {DEPSNODE_TYPE_TIMESOURCE,   1},
+    {DEPSNODE_TYPE_ID_REF,       2},
+    {DEPSNODE_TYPE_SUBGRAPH,     3},
+
+    /* Outer Types */
+    {DEPSNODE_TYPE_PARAMETERS,   4},
+    {DEPSNODE_TYPE_PROXY,        5},
+    {DEPSNODE_TYPE_ANIMATION,    6},
+    {DEPSNODE_TYPE_TRANSFORM,    7},
+    {DEPSNODE_TYPE_GEOMETRY,     8},
+    {DEPSNODE_TYPE_SEQUENCER,    9},
+    {DEPSNODE_TYPE_SHADING,      10},
+    {-1,                         0}
+};
+#endif
+
+#if 0 /* unused */
+static const int deg_debug_relation_type_color_map[][2] = {
+    {DEPSREL_TYPE_STANDARD,         0},
+    {DEPSREL_TYPE_ROOT_TO_ACTIVE,   1},
+    {DEPSREL_TYPE_DATABLOCK,        2},
+    {DEPSREL_TYPE_TIME,             3},
+    {DEPSREL_TYPE_COMPONENT_ORDER,  4},
+    {DEPSREL_TYPE_OPERATION,        5},
+    {DEPSREL_TYPE_DRIVER,           6},
+    {DEPSREL_TYPE_DRIVER_TARGET,    7},
+    {DEPSREL_TYPE_TRANSFORM,        8},
+    {DEPSREL_TYPE_GEOMETRY_EVAL,    9},
+    {DEPSREL_TYPE_UPDATE,           10},
+    {DEPSREL_TYPE_UPDATE_UI,        11},
+    {-1,                            0}
+};
+#endif
+
+static int deg_debug_node_color_index(const DepsNode *node)
+{
+#ifdef COLOR_SCHEME_NODE_CLASS
+       /* Some special types. */
+       switch (node->type) {
+               case DEPSNODE_TYPE_ID_REF:
+                       return 5;
+               case DEPSNODE_TYPE_OPERATION:
+               {
+                       OperationDepsNode *op_node = (OperationDepsNode *)node;
+                       if (op_node->is_noop())
+                               return 8;
+               }
+
+               default:
+                       break;
+       }
+       /* Do others based on class. */
+       switch (node->tclass) {
+               case DEPSNODE_CLASS_OPERATION:
+                       return 4;
+               case DEPSNODE_CLASS_COMPONENT:
+                       return 1;
+               default:
+                       return 9;
+       }
+#endif
+
+#ifdef COLOR_SCHEME_NODE_TYPE
+       const int (*pair)[2];
+       for (pair = deg_debug_node_type_color_map; (*pair)[0] >= 0; ++pair) {
+               if ((*pair)[0] == node->type) {
+                       return (*pair)[1];
+               }
+       }
+       return -1;
+#endif
+}
+
+struct DebugContext {
+       FILE *file;
+       bool show_tags;
+       bool show_eval_priority;
+};
+
+static void deg_debug_fprintf(const DebugContext &ctx, const char *fmt, ...) ATTR_PRINTF_FORMAT(2, 3);
+static void deg_debug_fprintf(const DebugContext &ctx, const char *fmt, ...)
+{
+       va_list args;
+       va_start(args, fmt);
+       vfprintf(ctx.file, fmt, args);
+       va_end(args);
+}
+
+static void deg_debug_graphviz_legend_color(const DebugContext &ctx,
+                                            const char *name,
+                                            const char *color)
+{
+       deg_debug_fprintf(ctx, "<TR>");
+       deg_debug_fprintf(ctx, "<TD>%s</TD>", name);
+       deg_debug_fprintf(ctx, "<TD BGCOLOR=\"%s\"></TD>", color);
+       deg_debug_fprintf(ctx, "</TR>" NL);
+}
+
+#if 0
+static void deg_debug_graphviz_legend_line(const DebugContext &ctx,
+                                           const char *name,
+                                           const char *color,
+                                           const char *style)
+{
+       /* XXX TODO */
+       deg_debug_fprintf(ctx, "" NL);
+}
+
+static void deg_debug_graphviz_legend_cluster(const DebugContext &ctx,
+                                              const char *name,
+                                              const char *color,
+                                              const char *style)
+{
+       deg_debug_fprintf(ctx, "<TR>");
+       deg_debug_fprintf(ctx, "<TD>%s</TD>", name);
+       deg_debug_fprintf(ctx, "<TD CELLPADDING=\"4\"><TABLE BORDER=\"1\" CELLBORDER=\"0\" CELLSPACING=\"0\" CELLPADDING=\"0\">");
+       deg_debug_fprintf(ctx, "<TR><TD BGCOLOR=\"%s\"></TD></TR>", color);
+       deg_debug_fprintf(ctx, "</TABLE></TD>");
+       deg_debug_fprintf(ctx, "</TR>" NL);
+}
+#endif
+
+static void deg_debug_graphviz_legend(const DebugContext &ctx)
+{
+       deg_debug_fprintf(ctx, "{" NL);
+       deg_debug_fprintf(ctx, "rank = sink;" NL);
+       deg_debug_fprintf(ctx, "Legend [shape=none, margin=0, label=<" NL);
+       deg_debug_fprintf(ctx, "  <TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">" NL);
+       deg_debug_fprintf(ctx, "<TR><TD COLSPAN=\"2\"><B>Legend</B></TD></TR>" NL);
+
+#ifdef COLOR_SCHEME_NODE_CLASS
+       const char **colors = deg_debug_colors_light;
+       deg_debug_graphviz_legend_color(ctx, "Operation", colors[4]);
+       deg_debug_graphviz_legend_color(ctx, "Component", colors[1]);
+       deg_debug_graphviz_legend_color(ctx, "ID Node", colors[5]);
+       deg_debug_graphviz_legend_color(ctx, "NOOP", colors[8]);
+#endif
+
+#ifdef COLOR_SCHEME_NODE_TYPE
+       const int (*pair)[2];
+       for (pair = deg_debug_node_type_color_map; (*pair)[0] >= 0; ++pair) {
+               DepsNodeFactory *nti = DEG_get_node_factory((eDepsNode_Type)(*pair)[0]);
+               deg_debug_graphviz_legend_color(ctx,
+                                               nti->tname().c_str(),
+                                               deg_debug_colors_light[(*pair)[1] % deg_debug_max_colors]);
+       }
+#endif
+
+       deg_debug_fprintf(ctx, "</TABLE>" NL);
+       deg_debug_fprintf(ctx, ">" NL);
+       deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname);
+       deg_debug_fprintf(ctx, "];" NL);
+       deg_debug_fprintf(ctx, "}" NL);
+}
+
+#if 0 /* unused */
+static int deg_debug_relation_type_color_index(eDepsRelation_Type type)
+{
+       const int (*pair)[2];
+       for (pair = deg_debug_relation_type_color_map; (*pair)[0] >= 0; ++pair) {
+               if ((*pair)[0] == type) {
+                       return (*pair)[1];
+               }
+       }
+       return -1;
+}
+#endif
+
+static void deg_debug_graphviz_node_color(const DebugContext &ctx,
+                                          const DepsNode *node)
+{
+       const char *color_default = "black";
+       const char *color_modified = "orangered4";
+       const char *color_update = "dodgerblue3";
+       const char *color = color_default;
+       if (ctx.show_tags) {
+               if (node->tclass == DEPSNODE_CLASS_OPERATION) {
+                       OperationDepsNode *op_node = (OperationDepsNode *)node;
+                       if (op_node->flag & DEPSOP_FLAG_DIRECTLY_MODIFIED) {
+                               color = color_modified;
+                       }
+                       else if (op_node->flag & DEPSOP_FLAG_NEEDS_UPDATE) {
+                               color = color_update;
+                       }
+               }
+       }
+       deg_debug_fprintf(ctx, "\"%s\"", color);
+}
+
+static void deg_debug_graphviz_node_penwidth(const DebugContext &ctx,
+                                             const DepsNode *node)
+{
+       float penwidth_default = 1.0f;
+       float penwidth_modified = 4.0f;
+       float penwidth_update = 4.0f;
+       float penwidth = penwidth_default;
+       if (ctx.show_tags) {
+               if (node->tclass == DEPSNODE_CLASS_OPERATION) {
+                       OperationDepsNode *op_node = (OperationDepsNode *)node;
+                       if (op_node->flag & DEPSOP_FLAG_DIRECTLY_MODIFIED) {
+                               penwidth = penwidth_modified;
+                       }
+                       else if (op_node->flag & DEPSOP_FLAG_NEEDS_UPDATE) {
+                               penwidth = penwidth_update;
+                       }
+               }
+       }
+       deg_debug_fprintf(ctx, "\"%f\"", penwidth);
+}
+
+static void deg_debug_graphviz_node_fillcolor(const DebugContext &ctx,
+                                              const DepsNode *node)
+{
+       const char *defaultcolor = "gainsboro";
+       int color_index = deg_debug_node_color_index(node);
+       const char *fillcolor = color_index < 0 ? defaultcolor : deg_debug_colors_light[color_index % deg_debug_max_colors];
+       deg_debug_fprintf(ctx, "\"%s\"", fillcolor);
+}
+
+#if 0 /* implementation using stripes, a bit too noisy ... */
+static void deg_debug_graphviz_node_fillcolor(const DebugContext &ctx,
+                                              const DepsNode *node)
+{
+       const char *defaultcolor = "gainsboro";
+       const char *color_needs_update = "orange";
+       const int num_stripes = 10;
+       int color_index = deg_debug_node_color_index(node);
+       const char *base_color = color_index < 0 ? defaultcolor : deg_debug_colors_light[color_index % deg_debug_max_colors];
+       if (ctx.show_tags &&
+           (node->flag & (DEPSNODE_FLAG_DIRECTLY_MODIFIED | DEPSNODE_FLAG_NEEDS_UPDATE))) {
+               deg_debug_fprintf(ctx, "\"");
+               for (int i = 0; i < num_stripes; ++i) {
+                       if (i > 0) {
+                               deg_debug_fprintf(ctx, ":");
+                       }
+                       deg_debug_fprintf(ctx, "%s:%s", base_color, color_needs_update);
+               }
+               deg_debug_fprintf(ctx, "\"");
+       }
+       else {
+               deg_debug_fprintf(ctx, "\"%s\"", base_color);
+       }
+}
+#endif
+
+static void deg_debug_graphviz_relation_color(const DebugContext &ctx,
+                                              const DepsRelation *UNUSED(rel))
+{
+       const char *defaultcolor = "black";
+#if 0 /* disabled for now, edge colors are hardly distinguishable */
+       int color = deg_debug_relation_type_color_index(rel->type);
+       if (color < 0) {
+               deg_debug_fprintf(ctx, "%s", defaultcolor);
+       }
+       else {
+               deg_debug_fprintf(ctx, "\"%s\"", deg_debug_colors_dark[color % deg_debug_max_colors]);
+       }
+#else
+       deg_debug_fprintf(ctx, "%s", defaultcolor);
+#endif
+}
+
+static void deg_debug_graphviz_node_style(const DebugContext &ctx, const DepsNode *node)
+{
+       const char *base_style = "filled"; /* default style */
+       if (ctx.show_tags) {
+               if (node->tclass == DEPSNODE_CLASS_OPERATION) {
+                       OperationDepsNode *op_node = (OperationDepsNode *)node;
+                       if (op_node->flag & (DEPSOP_FLAG_DIRECTLY_MODIFIED | DEPSOP_FLAG_NEEDS_UPDATE)) {
+                               base_style = "striped";
+                       }
+               }
+       }
+       switch (node->tclass) {
+               case DEPSNODE_CLASS_GENERIC:
+                       deg_debug_fprintf(ctx, "\"%s\"", base_style);
+                       break;
+               case DEPSNODE_CLASS_COMPONENT:
+                       deg_debug_fprintf(ctx, "\"%s\"", base_style);
+                       break;
+               case DEPSNODE_CLASS_OPERATION:
+                       deg_debug_fprintf(ctx, "\"%s,rounded\"", base_style);
+                       break;
+       }
+}
+
+static void deg_debug_graphviz_node_single(const DebugContext &ctx,
+                                           const DepsNode *node)
+{
+       const char *shape = "box";
+       string name = node->identifier();
+       float priority = -1.0f;
+       if (node->type == DEPSNODE_TYPE_ID_REF) {
+               IDDepsNode *id_node = (IDDepsNode *)node;
+               char buf[256];
+               BLI_snprintf(buf, sizeof(buf), " (Layers: %d)", id_node->layers);
+               name += buf;
+       }
+       if (ctx.show_eval_priority && node->tclass == DEPSNODE_CLASS_OPERATION) {
+               priority = ((OperationDepsNode *)node)->eval_priority;
+       }
+       deg_debug_fprintf(ctx, "// %s\n", name.c_str());
+       deg_debug_fprintf(ctx, "\"node_%p\"", node);
+       deg_debug_fprintf(ctx, "[");
+//     deg_debug_fprintf(ctx, "label=<<B>%s</B>>", name);
+       if (priority >= 0.0f) {
+               deg_debug_fprintf(ctx, "label=<%s<BR/>(<I>%.2f</I>)>",
+                                name.c_str(),
+                                priority);
+       }
+       else {
+               deg_debug_fprintf(ctx, "label=<%s>", name.c_str());
+       }
+       deg_debug_fprintf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname);
+       deg_debug_fprintf(ctx, ",fontsize=%f", deg_debug_graphviz_node_label_size);
+       deg_debug_fprintf(ctx, ",shape=%s", shape);
+       deg_debug_fprintf(ctx, ",style="); deg_debug_graphviz_node_style(ctx, node);
+       deg_debug_fprintf(ctx, ",color="); deg_debug_graphviz_node_color(ctx, node);
+       deg_debug_fprintf(ctx, ",fillcolor="); deg_debug_graphviz_node_fillcolor(ctx, node);
+       deg_debug_fprintf(ctx, ",penwidth="); deg_debug_graphviz_node_penwidth(ctx, node);
+       deg_debug_fprintf(ctx, "];" NL);
+       deg_debug_fprintf(ctx, NL);
+}
+
+static void deg_debug_graphviz_node_cluster_begin(const DebugContext &ctx,
+                                                  const DepsNode *node)
+{
+       string name = node->identifier().c_str();
+       if (node->type == DEPSNODE_TYPE_ID_REF) {
+               IDDepsNode *id_node = (IDDepsNode *)node;
+               char buf[256];
+               BLI_snprintf(buf, sizeof(buf), " (Layers: %d)", id_node->layers);
+               name += buf;
+       }
+       deg_debug_fprintf(ctx, "// %s\n", name.c_str());
+       deg_debug_fprintf(ctx, "subgraph \"cluster_%p\" {" NL, node);
+//     deg_debug_fprintf(ctx, "label=<<B>%s</B>>;" NL, name);
+       deg_debug_fprintf(ctx, "label=<%s>;" NL, name.c_str());
+       deg_debug_fprintf(ctx, "fontname=\"%s\";" NL, deg_debug_graphviz_fontname);
+       deg_debug_fprintf(ctx, "fontsize=%f;" NL, deg_debug_graphviz_node_label_size);
+       deg_debug_fprintf(ctx, "style="); deg_debug_graphviz_node_style(ctx, node); deg_debug_fprintf(ctx, ";" NL);
+       deg_debug_fprintf(ctx, "color="); deg_debug_graphviz_node_color(ctx, node); deg_debug_fprintf(ctx, ";" NL);
+       deg_debug_fprintf(ctx, "fillcolor="); deg_debug_graphviz_node_fillcolor(ctx, node); deg_debug_fprintf(ctx, ";" NL);
+       deg_debug_fprintf(ctx, "penwidth="); deg_debug_graphviz_node_penwidth(ctx, node); deg_debug_fprintf(ctx, ";" NL);
+       /* dummy node, so we can add edges between clusters */
+       deg_debug_fprintf(ctx, "\"node_%p\"", node);
+       deg_debug_fprintf(ctx, "[");
+       deg_debug_fprintf(ctx, "shape=%s", "point");
+       deg_debug_fprintf(ctx, ",style=%s", "invis");
+       deg_debug_fprintf(ctx, "];" NL);
+       deg_debug_fprintf(ctx, NL);
+}
+
+static void deg_debug_graphviz_node_cluster_end(const DebugContext &ctx)
+{
+       deg_debug_fprintf(ctx, "}" NL);
+       deg_debug_fprintf(ctx, NL);
+}
+
+static void deg_debug_graphviz_graph_nodes(const DebugContext &ctx,
+                                           const Depsgraph *graph);
+static void deg_debug_graphviz_graph_relations(const DebugContext &ctx,
+                                               const Depsgraph *graph);
+
+static void deg_debug_graphviz_node(const DebugContext &ctx,
+                                    const DepsNode *node)
+{
+       switch (node->type) {
+               case DEPSNODE_TYPE_ID_REF:
+               {
+                       const IDDepsNode *id_node = (const IDDepsNode *)node;
+                       if (id_node->components.empty()) {
+                               deg_debug_graphviz_node_single(ctx, node);
+                       }
+                       else {
+                               deg_debug_graphviz_node_cluster_begin(ctx, node);
+                               for (IDDepsNode::ComponentMap::const_iterator it = id_node->components.begin();
+                                    it != id_node->components.end();
+                                    ++it)
+                               {
+                                       const ComponentDepsNode *comp = it->second;
+                                       deg_debug_graphviz_node(ctx, comp);
+                               }
+                               deg_debug_graphviz_node_cluster_end(ctx);
+                       }
+                       break;
+               }
+               case DEPSNODE_TYPE_SUBGRAPH:
+               {
+                       SubgraphDepsNode *sub_node = (SubgraphDepsNode *)node;
+                       if (sub_node->graph) {
+                               deg_debug_graphviz_node_cluster_begin(ctx, node);
+                               deg_debug_graphviz_graph_nodes(ctx, sub_node->graph);
+                               deg_debug_graphviz_node_cluster_end(ctx);
+                       }
+                       else {
+                               deg_debug_graphviz_node_single(ctx, node);
+                       }
+                       break;
+               }
+               case DEPSNODE_TYPE_PARAMETERS:
+               case DEPSNODE_TYPE_ANIMATION:
+               case DEPSNODE_TYPE_TRANSFORM:
+               case DEPSNODE_TYPE_PROXY:
+               case DEPSNODE_TYPE_GEOMETRY:
+               case DEPSNODE_TYPE_SEQUENCER:
+               case DEPSNODE_TYPE_EVAL_POSE:
+               case DEPSNODE_TYPE_BONE:
+               case DEPSNODE_TYPE_SHADING:
+               {
+                       ComponentDepsNode *comp_node = (ComponentDepsNode *)node;
+                       if (!comp_node->operations.empty()) {
+                               deg_debug_graphviz_node_cluster_begin(ctx, node);
+                               for (ComponentDepsNode::OperationMap::const_iterator it = comp_node->operations.begin();
+                                    it != comp_node->operations.end();
+                                    ++it)
+                               {
+                                       const DepsNode *op_node = it->second;
+                                       deg_debug_graphviz_node(ctx, op_node);
+                               }
+                               deg_debug_graphviz_node_cluster_end(ctx);
+                       }
+                       else {
+                               deg_debug_graphviz_node_single(ctx, node);
+                       }
+                       break;
+               }
+               default:
+                       deg_debug_graphviz_node_single(ctx, node);
+                       break;
+       }
+}
+
+static bool deg_debug_graphviz_is_cluster(const DepsNode *node)
+{
+       switch (node->type) {
+               case DEPSNODE_TYPE_ID_REF:
+               {
+                       const IDDepsNode *id_node = (const IDDepsNode *)node;
+                       return !id_node->components.empty();
+               }
+               case DEPSNODE_TYPE_SUBGRAPH:
+               {
+                       SubgraphDepsNode *sub_node = (SubgraphDepsNode *)node;
+                       return sub_node->graph != NULL;
+               }
+               case DEPSNODE_TYPE_PARAMETERS:
+               case DEPSNODE_TYPE_ANIMATION:
+               case DEPSNODE_TYPE_TRANSFORM:
+               case DEPSNODE_TYPE_PROXY:
+               case DEPSNODE_TYPE_GEOMETRY:
+               case DEPSNODE_TYPE_SEQUENCER:
+               case DEPSNODE_TYPE_EVAL_POSE:
+               case DEPSNODE_TYPE_BONE:
+               {
+                       ComponentDepsNode *comp_node = (ComponentDepsNode *)node;
+                       return !comp_node->operations.empty();
+               }
+               default:
+                       return false;
+       }
+}
+
+static bool deg_debug_graphviz_is_owner(const DepsNode *node,
+                                        const DepsNode *other)
+{
+       switch (node->tclass) {
+               case DEPSNODE_CLASS_COMPONENT:
+               {
+                       ComponentDepsNode *comp_node = (ComponentDepsNode *)node;
+                       if (comp_node->owner == other)
+                               return true;
+                       break;
+               }
+               case DEPSNODE_CLASS_OPERATION:
+               {
+