8e826cd01dfc6b2b00380e80c51e043f4ab73938
[blender.git] / source / blender / depsgraph / intern / builder / deg_builder_relations.cc
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2013 Blender Foundation.
19  * All rights reserved.
20  *
21  * Original Author: Joshua Leung
22  * Contributor(s): Based on original depsgraph.c code - Blender Foundation (2005-2013)
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 /** \file blender/depsgraph/intern/builder/deg_builder_relations.cc
28  *  \ingroup depsgraph
29  *
30  * Methods for constructing depsgraph
31  */
32
33 #include "intern/builder/deg_builder_relations.h"
34
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <cstring>  /* required for STREQ later on. */
38
39 #include "MEM_guardedalloc.h"
40
41 #include "BLI_utildefines.h"
42 #include "BLI_blenlib.h"
43
44 extern "C" {
45 #include "DNA_action_types.h"
46 #include "DNA_anim_types.h"
47 #include "DNA_armature_types.h"
48 #include "DNA_camera_types.h"
49 #include "DNA_cachefile_types.h"
50 #include "DNA_constraint_types.h"
51 #include "DNA_curve_types.h"
52 #include "DNA_effect_types.h"
53 #include "DNA_gpencil_types.h"
54 #include "DNA_group_types.h"
55 #include "DNA_key_types.h"
56 #include "DNA_lamp_types.h"
57 #include "DNA_material_types.h"
58 #include "DNA_mask_types.h"
59 #include "DNA_mesh_types.h"
60 #include "DNA_meta_types.h"
61 #include "DNA_movieclip_types.h"
62 #include "DNA_node_types.h"
63 #include "DNA_particle_types.h"
64 #include "DNA_lightprobe_types.h"
65 #include "DNA_object_types.h"
66 #include "DNA_rigidbody_types.h"
67 #include "DNA_scene_types.h"
68 #include "DNA_texture_types.h"
69 #include "DNA_world_types.h"
70 #include "DNA_object_force_types.h"
71
72 #include "BKE_action.h"
73 #include "BKE_armature.h"
74 #include "BKE_animsys.h"
75 #include "BKE_collection.h"
76 #include "BKE_constraint.h"
77 #include "BKE_curve.h"
78 #include "BKE_effect.h"
79 #include "BKE_collision.h"
80 #include "BKE_fcurve.h"
81 #include "BKE_key.h"
82 #include "BKE_library.h"
83 #include "BKE_main.h"
84 #include "BKE_material.h"
85 #include "BKE_mball.h"
86 #include "BKE_modifier.h"
87 #include "BKE_node.h"
88 #include "BKE_object.h"
89 #include "BKE_particle.h"
90 #include "BKE_rigidbody.h"
91 #include "BKE_sound.h"
92 #include "BKE_tracking.h"
93 #include "BKE_world.h"
94
95 #include "RNA_access.h"
96 #include "RNA_types.h"
97 } /* extern "C" */
98
99 #include "DEG_depsgraph.h"
100 #include "DEG_depsgraph_build.h"
101
102 #include "intern/builder/deg_builder.h"
103 #include "intern/builder/deg_builder_pchanmap.h"
104
105 #include "intern/nodes/deg_node.h"
106 #include "intern/nodes/deg_node_component.h"
107 #include "intern/nodes/deg_node_id.h"
108 #include "intern/nodes/deg_node_operation.h"
109 #include "intern/nodes/deg_node_time.h"
110
111 #include "intern/depsgraph_intern.h"
112 #include "intern/depsgraph_types.h"
113
114 #include "util/deg_util_foreach.h"
115
116 namespace DEG {
117
118 /* ***************** */
119 /* Relations Builder */
120
121 /* TODO(sergey): This is somewhat weak, but we don't want neither false-positive
122  * time dependencies nor special exceptions in the depsgraph evaluation.
123  */
124 static bool python_driver_depends_on_time(ChannelDriver *driver)
125 {
126         if (driver->expression[0] == '\0') {
127                 /* Empty expression depends on nothing. */
128                 return false;
129         }
130         if (strchr(driver->expression, '(') != NULL) {
131                 /* Function calls are considered dependent on a time. */
132                 return true;
133         }
134         if (strstr(driver->expression, "frame") != NULL) {
135                 /* Variable `frame` depends on time. */
136                 /* TODO(sergey): This is a bit weak, but not sure about better way of
137                  * handling this.
138                  */
139                 return true;
140         }
141         /* Possible indirect time relation s should be handled via variable
142          * targets.
143          */
144         return false;
145 }
146
147 static bool particle_system_depends_on_time(ParticleSystem *psys)
148 {
149         ParticleSettings *part = psys->part;
150         /* Non-hair particles we always consider dependent on time. */
151         if (part->type != PART_HAIR) {
152                 return true;
153         }
154         /* Dynamics always depends on time. */
155         if (psys->flag & PSYS_HAIR_DYNAMICS) {
156                 return true;
157         }
158         /* TODO(sergey): Check what else makes hair dependent on time. */
159         return false;
160 }
161
162 static bool object_particles_depends_on_time(Object *object)
163 {
164         LISTBASE_FOREACH (ParticleSystem *, psys, &object->particlesystem) {
165                 if (particle_system_depends_on_time(psys)) {
166                         return true;
167                 }
168         }
169         return false;
170 }
171
172 static bool check_id_has_anim_component(ID *id)
173 {
174         AnimData *adt = BKE_animdata_from_id(id);
175         if (adt == NULL) {
176                 return false;
177         }
178         return (adt->action != NULL) ||
179                (!BLI_listbase_is_empty(&adt->nla_tracks));
180 }
181
182 /* **** General purpose functions ****  */
183
184 DepsgraphRelationBuilder::DepsgraphRelationBuilder(Main *bmain,
185                                                    Depsgraph *graph)
186     : bmain_(bmain),
187       graph_(graph),
188       scene_(NULL)
189 {
190 }
191
192 TimeSourceDepsNode *DepsgraphRelationBuilder::get_node(
193         const TimeSourceKey &key) const
194 {
195         if (key.id) {
196                 /* XXX TODO */
197                 return NULL;
198         }
199         else {
200                 return graph_->time_source;
201         }
202 }
203
204 ComponentDepsNode *DepsgraphRelationBuilder::get_node(
205         const ComponentKey &key) const
206 {
207         IDDepsNode *id_node = graph_->find_id_node(key.id);
208         if (!id_node) {
209                 fprintf(stderr, "find_node component: Could not find ID %s\n",
210                         (key.id != NULL) ? key.id->name : "<null>");
211                 return NULL;
212         }
213
214         ComponentDepsNode *node = id_node->find_component(key.type, key.name);
215         return node;
216 }
217
218 OperationDepsNode *DepsgraphRelationBuilder::get_node(
219         const OperationKey &key) const
220 {
221         OperationDepsNode *op_node = find_node(key);
222         if (op_node == NULL) {
223                 fprintf(stderr, "find_node_operation: Failed for (%s, '%s')\n",
224                         operationCodeAsString(key.opcode), key.name);
225         }
226         return op_node;
227 }
228
229 DepsNode *DepsgraphRelationBuilder::get_node(const RNAPathKey &key) const
230 {
231         return graph_->find_node_from_pointer(&key.ptr, key.prop);
232 }
233
234 OperationDepsNode *DepsgraphRelationBuilder::find_node(
235         const OperationKey &key) const
236 {
237         IDDepsNode *id_node = graph_->find_id_node(key.id);
238         if (!id_node) {
239                 return NULL;
240         }
241         ComponentDepsNode *comp_node = id_node->find_component(key.component_type,
242                                                                key.component_name);
243         if (!comp_node) {
244                 return NULL;
245         }
246         return comp_node->find_operation(key.opcode, key.name, key.name_tag);
247 }
248
249 bool DepsgraphRelationBuilder::has_node(const OperationKey &key) const
250 {
251         return find_node(key) != NULL;
252 }
253
254 DepsRelation *DepsgraphRelationBuilder::add_time_relation(
255         TimeSourceDepsNode *timesrc,
256         DepsNode *node_to,
257         const char *description,
258         bool check_unique)
259 {
260         if (timesrc && node_to) {
261                 return graph_->add_new_relation(timesrc, node_to, description, check_unique);
262         }
263         else {
264                 DEG_DEBUG_PRINTF((::Depsgraph *)graph_,
265                                  BUILD, "add_time_relation(%p = %s, %p = %s, %s) Failed\n",
266                                  timesrc,   (timesrc) ? timesrc->identifier().c_str() : "<None>",
267                                  node_to,   (node_to) ? node_to->identifier().c_str() : "<None>",
268                                  description);
269         }
270         return NULL;
271 }
272
273 DepsRelation *DepsgraphRelationBuilder::add_operation_relation(
274         OperationDepsNode *node_from,
275         OperationDepsNode *node_to,
276         const char *description,
277         bool check_unique)
278 {
279         if (node_from && node_to) {
280                 return graph_->add_new_relation(node_from,
281                                                 node_to,
282                                                 description,
283                                                 check_unique);
284         }
285         else {
286                 DEG_DEBUG_PRINTF((::Depsgraph *)graph_,
287                                  BUILD, "add_operation_relation(%p = %s, %p = %s, %s) Failed\n",
288                                  node_from, (node_from) ? node_from->identifier().c_str() : "<None>",
289                                  node_to,   (node_to)   ? node_to->identifier().c_str() : "<None>",
290                                  description);
291         }
292         return NULL;
293 }
294
295 void DepsgraphRelationBuilder::add_collision_relations(
296         const OperationKey &key,
297         Scene *scene,
298         Object *object,
299         Collection *collection,
300         bool dupli,
301         const char *name)
302 {
303         unsigned int numcollobj;
304         Object **collobjs = get_collisionobjects_ext(scene,
305                                                      object,
306                                                      collection,
307                                                      &numcollobj,
308                                                      eModifierType_Collision,
309                                                      dupli);
310         for (unsigned int i = 0; i < numcollobj; i++) {
311                 Object *ob1 = collobjs[i];
312
313                 ComponentKey trf_key(&ob1->id, DEG_NODE_TYPE_TRANSFORM);
314                 add_relation(trf_key, key, name);
315
316                 ComponentKey coll_key(&ob1->id, DEG_NODE_TYPE_GEOMETRY);
317                 add_relation(coll_key, key, name);
318         }
319         if (collobjs != NULL) {
320                 MEM_freeN(collobjs);
321         }
322 }
323
324 void DepsgraphRelationBuilder::add_forcefield_relations(
325         const OperationKey &key,
326         Scene *scene,
327         Object *object,
328         ParticleSystem *psys,
329         EffectorWeights *eff,
330         bool add_absorption,
331         const char *name)
332 {
333         ListBase *effectors = pdInitEffectors(NULL, scene, object, psys, eff, false);
334         if (effectors != NULL) {
335                 LISTBASE_FOREACH (EffectorCache *, eff, effectors) {
336                         if (eff->ob != object) {
337                                 ComponentKey eff_key(&eff->ob->id, DEG_NODE_TYPE_TRANSFORM);
338                                 add_relation(eff_key, key, name);
339                         }
340                         if (eff->psys != NULL) {
341                                 if (eff->ob != object) {
342                                         ComponentKey eff_key(&eff->ob->id, DEG_NODE_TYPE_EVAL_PARTICLES);
343                                         add_relation(eff_key, key, name);
344
345                                         /* TODO: remove this when/if EVAL_PARTICLES is sufficient
346                                          * for up to date particles.
347                                          */
348                                         ComponentKey mod_key(&eff->ob->id, DEG_NODE_TYPE_GEOMETRY);
349                                         add_relation(mod_key, key, name);
350                                 }
351                                 else if (eff->psys != psys) {
352                                         OperationKey eff_key(&eff->ob->id,
353                                                              DEG_NODE_TYPE_EVAL_PARTICLES,
354                                                              DEG_OPCODE_PARTICLE_SYSTEM_EVAL,
355                                                              eff->psys->name);
356                                         add_relation(eff_key, key, name);
357                                 }
358                         }
359                         if (eff->pd->forcefield == PFIELD_SMOKEFLOW && eff->pd->f_source) {
360                                 ComponentKey trf_key(&eff->pd->f_source->id,
361                                                      DEG_NODE_TYPE_TRANSFORM);
362                                 add_relation(trf_key, key, "Smoke Force Domain");
363
364                                 ComponentKey eff_key(&eff->pd->f_source->id,
365                                                      DEG_NODE_TYPE_GEOMETRY);
366                                 add_relation(eff_key, key, "Smoke Force Domain");
367                         }
368                         if (add_absorption && (eff->pd->flag & PFIELD_VISIBILITY)) {
369                                 add_collision_relations(key,
370                                                         scene,
371                                                         object,
372                                                         NULL,
373                                                         true,
374                                                         "Force Absorption");
375                         }
376                 }
377         }
378
379         pdEndEffectors(&effectors);
380 }
381
382 Depsgraph *DepsgraphRelationBuilder::getGraph()
383 {
384         return graph_;
385 }
386
387 /* **** Functions to build relations between entities  **** */
388
389 void DepsgraphRelationBuilder::begin_build()
390 {
391 }
392
393 void DepsgraphRelationBuilder::build_id(ID *id)
394 {
395         if (id == NULL) {
396                 return;
397         }
398         switch (GS(id->name)) {
399                 case ID_GR:
400                         build_collection(NULL, (Collection *)id);
401                         break;
402                 case ID_OB:
403                         build_object(NULL, (Object *)id);
404                         break;
405                 case ID_NT:
406                         build_nodetree((bNodeTree *)id);
407                         break;
408                 case ID_MA:
409                         build_material((Material *)id);
410                         break;
411                 case ID_TE:
412                         build_texture((Tex *)id);
413                         break;
414                 case ID_WO:
415                         build_world((World *)id);
416                         break;
417                 case ID_MSK:
418                         build_mask((Mask *)id);
419                         break;
420                 case ID_MC:
421                         build_movieclip((MovieClip *)id);
422                         break;
423                 default:
424                         fprintf(stderr, "Unhandled ID %s\n", id->name);
425         }
426 }
427
428 void DepsgraphRelationBuilder::build_collection(Object *object, Collection *collection)
429 {
430         const int restrict_flag = (graph_->mode == DAG_EVAL_VIEWPORT) ?
431                 COLLECTION_RESTRICT_VIEW : COLLECTION_RESTRICT_RENDER;
432         if (collection->flag & restrict_flag) {
433                 return;
434         }
435
436         const bool group_done = built_map_.checkIsBuiltAndTag(collection);
437         OperationKey object_local_transform_key(object != NULL ? &object->id : NULL,
438                                                 DEG_NODE_TYPE_TRANSFORM,
439                                                 DEG_OPCODE_TRANSFORM_LOCAL);
440         if (!group_done) {
441                 LISTBASE_FOREACH (CollectionObject *, cob, &collection->gobject) {
442                         build_object(NULL, cob->ob);
443                 }
444                 LISTBASE_FOREACH (CollectionChild *, child, &collection->children) {
445                         build_collection(NULL, child->collection);
446                 }
447         }
448         if (object != NULL) {
449                 const ListBase group_objects = BKE_collection_object_cache_get(collection);
450                 LISTBASE_FOREACH (Base *, base, &group_objects) {
451                         ComponentKey dupli_transform_key(&base->object->id, DEG_NODE_TYPE_TRANSFORM);
452                         add_relation(dupli_transform_key, object_local_transform_key, "Dupligroup");
453                 }
454         }
455 }
456
457 void DepsgraphRelationBuilder::build_object(Base *base, Object *object)
458 {
459         if (built_map_.checkIsBuiltAndTag(object)) {
460                 if (base != NULL) {
461                         build_object_flags(base, object);
462                 }
463                 return;
464         }
465         /* Object Transforms */
466         eDepsOperation_Code base_op = (object->parent) ? DEG_OPCODE_TRANSFORM_PARENT
467                                                        : DEG_OPCODE_TRANSFORM_LOCAL;
468         OperationKey base_op_key(&object->id, DEG_NODE_TYPE_TRANSFORM, base_op);
469         OperationKey local_transform_key(&object->id,
470                                          DEG_NODE_TYPE_TRANSFORM,
471                                          DEG_OPCODE_TRANSFORM_LOCAL);
472         OperationKey parent_transform_key(&object->id,
473                                           DEG_NODE_TYPE_TRANSFORM,
474                                           DEG_OPCODE_TRANSFORM_PARENT);
475         OperationKey final_transform_key(&object->id,
476                                          DEG_NODE_TYPE_TRANSFORM,
477                                          DEG_OPCODE_TRANSFORM_FINAL);
478         OperationKey ob_ubereval_key(&object->id,
479                                      DEG_NODE_TYPE_TRANSFORM,
480                                      DEG_OPCODE_TRANSFORM_OBJECT_UBEREVAL);
481         /* Various flags, flushing from bases/collections. */
482         build_object_flags(base, object);
483         /* Parenting. */
484         if (object->parent != NULL) {
485                 /* Make sure parent object's relations are built. */
486                 build_object(NULL, object->parent);
487                 /* Parent relationship. */
488                 build_object_parent(object);
489                 /* Local -> parent. */
490                 add_relation(local_transform_key,
491                              parent_transform_key,
492                              "ObLocal -> ObParent");
493         }
494         /* Modifiers. */
495         if (object->modifiers.first != NULL) {
496                 BuilderWalkUserData data;
497                 data.builder = this;
498                 modifiers_foreachIDLink(object, modifier_walk, &data);
499         }
500         /* Constraints. */
501         if (object->constraints.first != NULL) {
502                 BuilderWalkUserData data;
503                 data.builder = this;
504                 BKE_constraints_id_loop(&object->constraints, constraint_walk, &data);
505         }
506         /* Object constraints. */
507         if (object->constraints.first != NULL) {
508                 OperationKey constraint_key(&object->id,
509                                             DEG_NODE_TYPE_TRANSFORM,
510                                             DEG_OPCODE_TRANSFORM_CONSTRAINTS);
511                 /* Constraint relations. */
512                 build_constraints(&object->id,
513                                   DEG_NODE_TYPE_TRANSFORM,
514                                   "",
515                                   &object->constraints,
516                                   NULL);
517                 /* operation order */
518                 add_relation(base_op_key, constraint_key, "ObBase-> Constraint Stack");
519                 add_relation(constraint_key, final_transform_key, "ObConstraints -> Done");
520                 // XXX
521                 add_relation(constraint_key, ob_ubereval_key, "Temp Ubereval");
522                 add_relation(ob_ubereval_key, final_transform_key, "Temp Ubereval");
523         }
524         else {
525                 /* NOTE: Keep an eye here, we skip some relations here to "streamline"
526                  * dependencies and avoid transitive relations which causes overhead.
527                  * But once we get rid of uber eval node this will need reconsideration.
528                  */
529                 if (object->rigidbody_object == NULL) {
530                         /* Rigid body will hook up another node inbetween, so skip
531                          * relation here to avoid transitive relation.
532                          */
533                         add_relation(base_op_key, ob_ubereval_key, "Temp Ubereval");
534                 }
535                 add_relation(ob_ubereval_key, final_transform_key, "Temp Ubereval");
536         }
537         /* Animation data */
538         build_animdata(&object->id);
539         /* Object data. */
540         build_object_data(object);
541         /* Particle systems. */
542         if (object->particlesystem.first != NULL) {
543                 build_particles(object);
544         }
545         /* Grease pencil. */
546         if (object->gpd != NULL) {
547                 build_gpencil(object->gpd);
548         }
549         /* Proxy object to copy from. */
550         if (object->proxy_from != NULL) {
551                 build_object(NULL, object->proxy_from);
552                 ComponentKey ob_pose_key(&object->proxy_from->id, DEG_NODE_TYPE_EVAL_POSE);
553                 ComponentKey proxy_pose_key(&object->id, DEG_NODE_TYPE_EVAL_POSE);
554                 add_relation(ob_pose_key, proxy_pose_key, "Proxy Pose");
555
556                 ComponentKey ob_transform_key(&object->proxy_from->id, DEG_NODE_TYPE_TRANSFORM);
557                 ComponentKey proxy_transform_key(&object->id, DEG_NODE_TYPE_TRANSFORM);
558                 add_relation(ob_transform_key, proxy_transform_key, "Proxy Transform");
559         }
560
561         /* Object dupligroup. */
562         if (object->dup_group != NULL) {
563                 build_collection(object, object->dup_group);
564         }
565 }
566
567 void DepsgraphRelationBuilder::build_object_flags(Base *base, Object *object)
568 {
569         if (base == NULL) {
570                 return;
571         }
572         OperationKey view_layer_done_key(&scene_->id,
573                                          DEG_NODE_TYPE_LAYER_COLLECTIONS,
574                                          DEG_OPCODE_VIEW_LAYER_EVAL);
575         OperationKey object_flags_key(&object->id,
576                                       DEG_NODE_TYPE_LAYER_COLLECTIONS,
577                                       DEG_OPCODE_OBJECT_BASE_FLAGS);
578         add_relation(view_layer_done_key, object_flags_key, "Base flags flush");
579 }
580
581 void DepsgraphRelationBuilder::build_object_data(Object *object)
582 {
583         if (object->data == NULL) {
584                 return;
585         }
586         ID *obdata_id = (ID *)object->data;
587         /* Object data animation. */
588         if (!built_map_.checkIsBuilt(obdata_id)) {
589                 build_animdata(obdata_id);
590         }
591         /* type-specific data. */
592         switch (object->type) {
593                 case OB_MESH:
594                 case OB_CURVE:
595                 case OB_FONT:
596                 case OB_SURF:
597                 case OB_MBALL:
598                 case OB_LATTICE:
599                 {
600                         build_obdata_geom(object);
601                         break;
602                 }
603                 case OB_ARMATURE:
604                         if (ID_IS_LINKED(object) && object->proxy_from != NULL) {
605                                 build_proxy_rig(object);
606                         }
607                         else {
608                                  build_rig(object);
609                         }
610                         break;
611                 case OB_LAMP:
612                         build_lamp(object);
613                         break;
614                 case OB_CAMERA:
615                         build_camera(object);
616                         break;
617                 case OB_LIGHTPROBE:
618                         build_object_data_lightprobe(object);
619                         break;
620         }
621         Key *key = BKE_key_from_object(object);
622         if (key != NULL) {
623                 ComponentKey geometry_key((ID *)object->data, DEG_NODE_TYPE_GEOMETRY);
624                 ComponentKey key_key(&key->id, DEG_NODE_TYPE_GEOMETRY);
625                 add_relation(key_key, geometry_key, "Shapekeys");
626                 build_nested_shapekey(&object->id, key);
627         }
628 }
629
630 void DepsgraphRelationBuilder::build_object_data_lightprobe(Object *object)
631 {
632         LightProbe *probe = (LightProbe *)object->data;
633         build_lightprobe(probe);
634         OperationKey probe_key(&probe->id,
635                                DEG_NODE_TYPE_PARAMETERS,
636                                DEG_OPCODE_LIGHT_PROBE_EVAL);
637         OperationKey object_key(&object->id,
638                                 DEG_NODE_TYPE_PARAMETERS,
639                                 DEG_OPCODE_LIGHT_PROBE_EVAL);
640         add_relation(probe_key, object_key, "LightProbe Update");
641 }
642
643 void DepsgraphRelationBuilder::build_object_parent(Object *object)
644 {
645         /* XXX: for now, need to use the component key (not just direct to the parent op),
646          * or else the matrix doesn't get reset/
647          */
648         // XXX: @sergey - it would be good if we got that backwards flushing working
649         // when tagging for updates.
650         //OperationKey ob_key(&object->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_TRANSFORM_PARENT);
651         ComponentKey ob_key(&object->id, DEG_NODE_TYPE_TRANSFORM);
652
653         /* type-specific links */
654         switch (object->partype) {
655                 case PARSKEL:  /* Armature Deform (Virtual Modifier) */
656                 {
657                         ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
658                         add_relation(parent_key, ob_key, "Armature Deform Parent");
659                         break;
660                 }
661
662                 case PARVERT1: /* Vertex Parent */
663                 case PARVERT3:
664                 {
665                         ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_GEOMETRY);
666                         add_relation(parent_key, ob_key, "Vertex Parent");
667
668                         /* XXX not sure what this is for or how you could be done properly - lukas */
669                         OperationDepsNode *parent_node = find_operation_node(parent_key);
670                         if (parent_node != NULL) {
671                                 parent_node->customdata_mask |= CD_MASK_ORIGINDEX;
672                         }
673
674                         ComponentKey transform_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
675                         add_relation(transform_key, ob_key, "Vertex Parent TFM");
676                         break;
677                 }
678
679                 case PARBONE: /* Bone Parent */
680                 {
681                         ComponentKey parent_bone_key(&object->parent->id,
682                                                      DEG_NODE_TYPE_BONE,
683                                                      object->parsubstr);
684                         OperationKey parent_transform_key(&object->parent->id,
685                                                           DEG_NODE_TYPE_TRANSFORM,
686                                                           DEG_OPCODE_TRANSFORM_FINAL);
687                         add_relation(parent_bone_key, ob_key, "Bone Parent");
688                         add_relation(parent_transform_key, ob_key, "Armature Parent");
689                         break;
690                 }
691
692                 default:
693                 {
694                         if (object->parent->type == OB_LATTICE) {
695                                 /* Lattice Deform Parent - Virtual Modifier */
696                                 // XXX: no virtual modifiers should be left!
697                                 ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
698                                 ComponentKey geom_key(&object->parent->id, DEG_NODE_TYPE_GEOMETRY);
699
700                                 add_relation(parent_key, ob_key, "Lattice Deform Parent");
701                                 add_relation(geom_key, ob_key, "Lattice Deform Parent Geom");
702                         }
703                         else if (object->parent->type == OB_CURVE) {
704                                 Curve *cu = (Curve *)object->parent->data;
705
706                                 if (cu->flag & CU_PATH) {
707                                         /* Follow Path */
708                                         ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_GEOMETRY);
709                                         add_relation(parent_key, ob_key, "Curve Follow Parent");
710
711                                         ComponentKey transform_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
712                                         add_relation(transform_key, ob_key, "Curve Follow TFM");
713                                 }
714                                 else {
715                                         /* Standard Parent */
716                                         ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
717                                         add_relation(parent_key, ob_key, "Curve Parent");
718                                 }
719                         }
720                         else {
721                                 /* Standard Parent */
722                                 ComponentKey parent_key(&object->parent->id, DEG_NODE_TYPE_TRANSFORM);
723                                 add_relation(parent_key, ob_key, "Parent");
724                         }
725                         break;
726                 }
727         }
728
729         /* exception case: parent is duplivert */
730         if ((object->type == OB_MBALL) && (object->parent->transflag & OB_DUPLIVERTS)) {
731                 //dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_OB, "Duplivert");
732         }
733 }
734
735 void DepsgraphRelationBuilder::build_constraints(ID *id,
736                                                  eDepsNode_Type component_type,
737                                                  const char *component_subdata,
738                                                  ListBase *constraints,
739                                                  RootPChanMap *root_map)
740 {
741         OperationKey constraint_op_key(
742                 id,
743                 component_type,
744                 component_subdata,
745                 (component_type == DEG_NODE_TYPE_BONE)
746                         ? DEG_OPCODE_BONE_CONSTRAINTS
747                         : DEG_OPCODE_TRANSFORM_CONSTRAINTS);
748         /* Add dependencies for each constraint in turn. */
749         for (bConstraint *con = (bConstraint *)constraints->first; con; con = con->next) {
750                 const bConstraintTypeInfo *cti = BKE_constraint_typeinfo_get(con);
751                 /* Invalid constraint type. */
752                 if (cti == NULL) {
753                         continue;
754                 }
755                 /* Special case for camera tracking -- it doesn't use targets to
756                  * define relations.
757                  */
758                 /* TODO: we can now represent dependencies in a much richer manner,
759                  * so review how this is done.
760                  */
761                 if (ELEM(cti->type,
762                          CONSTRAINT_TYPE_FOLLOWTRACK,
763                          CONSTRAINT_TYPE_CAMERASOLVER,
764                          CONSTRAINT_TYPE_OBJECTSOLVER))
765                 {
766                         bool depends_on_camera = false;
767                         if (cti->type == CONSTRAINT_TYPE_FOLLOWTRACK) {
768                                 bFollowTrackConstraint *data = (bFollowTrackConstraint *)con->data;
769                                 if (((data->clip) ||
770                                      (data->flag & FOLLOWTRACK_ACTIVECLIP)) && data->track[0])
771                                 {
772                                         depends_on_camera = true;
773                                 }
774                                 if (data->depth_ob) {
775                                         ComponentKey depth_transform_key(&data->depth_ob->id,
776                                                                          DEG_NODE_TYPE_TRANSFORM);
777                                         ComponentKey depth_geometry_key(&data->depth_ob->id,
778                                                                         DEG_NODE_TYPE_GEOMETRY);
779                                         add_relation(depth_transform_key, constraint_op_key, cti->name);
780                                         add_relation(depth_geometry_key, constraint_op_key, cti->name);
781                                 }
782                         }
783                         else if (cti->type == CONSTRAINT_TYPE_OBJECTSOLVER) {
784                                 depends_on_camera = true;
785                         }
786                         if (depends_on_camera && scene_->camera != NULL) {
787                                 ComponentKey camera_key(&scene_->camera->id, DEG_NODE_TYPE_TRANSFORM);
788                                 add_relation(camera_key, constraint_op_key, cti->name);
789                         }
790                         /* TODO(sergey): This is more a TimeSource -> MovieClip ->
791                          * Constraint dependency chain.
792                          */
793                         TimeSourceKey time_src_key;
794                         add_relation(time_src_key, constraint_op_key, "TimeSrc -> Animation");
795                 }
796                 else if (cti->type == CONSTRAINT_TYPE_TRANSFORM_CACHE) {
797                         /* TODO(kevin): This is more a TimeSource -> CacheFile -> Constraint
798                          * dependency chain.
799                          */
800                         TimeSourceKey time_src_key;
801                         add_relation(time_src_key, constraint_op_key, "TimeSrc -> Animation");
802                         bTransformCacheConstraint *data = (bTransformCacheConstraint *)con->data;
803                         if (data->cache_file) {
804                                 ComponentKey cache_key(&data->cache_file->id, DEG_NODE_TYPE_CACHE);
805                                 add_relation(cache_key, constraint_op_key, cti->name);
806                         }
807                 }
808                 else if (cti->get_constraint_targets) {
809                         ListBase targets = {NULL, NULL};
810                         cti->get_constraint_targets(con, &targets);
811                         LISTBASE_FOREACH (bConstraintTarget *, ct, &targets) {
812                                 if (ct->tar == NULL) {
813                                         continue;
814                                 }
815                                 if (ELEM(con->type,
816                                          CONSTRAINT_TYPE_KINEMATIC,
817                                          CONSTRAINT_TYPE_SPLINEIK))
818                                 {
819                                         /* Ignore IK constraints - these are handled separately
820                                          * (on pose level).
821                                          */
822                                 }
823                                 else if (ELEM(con->type,
824                                               CONSTRAINT_TYPE_FOLLOWPATH,
825                                               CONSTRAINT_TYPE_CLAMPTO))
826                                 {
827                                         /* These constraints require path geometry data. */
828                                         ComponentKey target_key(&ct->tar->id, DEG_NODE_TYPE_GEOMETRY);
829                                         add_relation(target_key, constraint_op_key, cti->name);
830                                         ComponentKey target_transform_key(&ct->tar->id,
831                                                                           DEG_NODE_TYPE_TRANSFORM);
832                                         add_relation(target_transform_key, constraint_op_key, cti->name);
833                                 }
834                                 else if ((ct->tar->type == OB_ARMATURE) && (ct->subtarget[0])) {
835                                         /* bone */
836                                         if (&ct->tar->id == id) {
837                                                 /* same armature  */
838                                                 eDepsOperation_Code target_key_opcode;
839                                                 /* Using "done" here breaks in-chain deps, while using
840                                                  * "ready" here breaks most production rigs instead.
841                                                  * So, we do a compromise here, and only do this when an
842                                                  * IK chain conflict may occur.
843                                                  */
844                                                 if (root_map->has_common_root(component_subdata,
845                                                                               ct->subtarget))
846                                                 {
847                                                         target_key_opcode = DEG_OPCODE_BONE_READY;
848                                                 }
849                                                 else {
850                                                         target_key_opcode = DEG_OPCODE_BONE_DONE;
851                                                 }
852                                                 OperationKey target_key(&ct->tar->id,
853                                                                         DEG_NODE_TYPE_BONE,
854                                                                         ct->subtarget,
855                                                                         target_key_opcode);
856                                                 add_relation(target_key, constraint_op_key, cti->name);
857                                         }
858                                         else {
859                                                 /* Different armature - we can safely use the result
860                                                  * of that.
861                                                  */
862                                                 OperationKey target_key(&ct->tar->id,
863                                                                         DEG_NODE_TYPE_BONE,
864                                                                         ct->subtarget,
865                                                                         DEG_OPCODE_BONE_DONE);
866                                                 add_relation(target_key, constraint_op_key, cti->name);
867                                         }
868                                 }
869                                 else if (ELEM(ct->tar->type, OB_MESH, OB_LATTICE) &&
870                                          (ct->subtarget[0]))
871                                 {
872                                         /* Vertex group. */
873                                         /* NOTE: for now, we don't need to represent vertex groups
874                                          * separately.
875                                          */
876                                         ComponentKey target_key(&ct->tar->id, DEG_NODE_TYPE_GEOMETRY);
877                                         add_relation(target_key, constraint_op_key, cti->name);
878                                         if (ct->tar->type == OB_MESH) {
879                                                 OperationDepsNode *node2 = find_operation_node(target_key);
880                                                 if (node2 != NULL) {
881                                                         node2->customdata_mask |= CD_MASK_MDEFORMVERT;
882                                                 }
883                                         }
884                                 }
885                                 else if (con->type == CONSTRAINT_TYPE_SHRINKWRAP) {
886                                         /* Constraints which requires the target object surface. */
887                                         ComponentKey target_key(&ct->tar->id, DEG_NODE_TYPE_GEOMETRY);
888                                         add_relation(target_key, constraint_op_key, cti->name);
889                                         /* NOTE: obdata eval now doesn't necessarily depend on the
890                                          * object's transform.
891                                          */
892                                         ComponentKey target_transform_key(&ct->tar->id,
893                                                                           DEG_NODE_TYPE_TRANSFORM);
894                                         add_relation(target_transform_key, constraint_op_key, cti->name);
895                                 }
896                                 else {
897                                         /* Standard object relation. */
898                                         // TODO: loc vs rot vs scale?
899                                         if (&ct->tar->id == id) {
900                                                 /* Constraint targetting own object:
901                                                  * - This case is fine IFF we're dealing with a bone
902                                                  *   constraint pointing to its own armature. In that
903                                                  *   case, it's just transform -> bone.
904                                                  * - If however it is a real self targetting case, just
905                                                  *   make it depend on the previous constraint (or the
906                                                  *   pre-constraint state).
907                                                  */
908                                                 if ((ct->tar->type == OB_ARMATURE) &&
909                                                     (component_type == DEG_NODE_TYPE_BONE))
910                                                 {
911                                                         OperationKey target_key(&ct->tar->id,
912                                                                                 DEG_NODE_TYPE_TRANSFORM,
913                                                                                 DEG_OPCODE_TRANSFORM_FINAL);
914                                                         add_relation(target_key, constraint_op_key, cti->name);
915                                                 }
916                                                 else {
917                                                         OperationKey target_key(&ct->tar->id,
918                                                                                 DEG_NODE_TYPE_TRANSFORM,
919                                                                                 DEG_OPCODE_TRANSFORM_LOCAL);
920                                                         add_relation(target_key, constraint_op_key, cti->name);
921                                                 }
922                                         }
923                                         else {
924                                                 /* Normal object dependency. */
925                                                 OperationKey target_key(&ct->tar->id,
926                                                                         DEG_NODE_TYPE_TRANSFORM,
927                                                                         DEG_OPCODE_TRANSFORM_FINAL);
928                                                 add_relation(target_key, constraint_op_key, cti->name);
929                                         }
930                                 }
931                                 /* Constraints which needs world's matrix for transform.
932                                  * TODO(sergey): More constraints here?
933                                  */
934                                 if (ELEM(con->type,
935                                          CONSTRAINT_TYPE_ROTLIKE,
936                                          CONSTRAINT_TYPE_SIZELIKE,
937                                          CONSTRAINT_TYPE_LOCLIKE,
938                                          CONSTRAINT_TYPE_TRANSLIKE))
939                                 {
940                                         /* TODO(sergey): Add used space check. */
941                                         ComponentKey target_transform_key(&ct->tar->id,
942                                                                           DEG_NODE_TYPE_TRANSFORM);
943                                         add_relation(target_transform_key, constraint_op_key, cti->name);
944                                 }
945                         }
946                         if (cti->flush_constraint_targets) {
947                                 cti->flush_constraint_targets(con, &targets, 1);
948                         }
949                 }
950         }
951 }
952
953 void DepsgraphRelationBuilder::build_animdata(ID *id)
954 {
955         /* Animation curves and NLA. */
956         build_animdata_curves(id);
957         /* Drivers. */
958         build_animdata_drivers(id);
959 }
960
961 void DepsgraphRelationBuilder::build_animdata_curves(ID *id)
962 {
963         AnimData *adt = BKE_animdata_from_id(id);
964         if (adt == NULL) {
965                 return;
966         }
967         if (adt->action == NULL && adt->nla_tracks.first == NULL) {
968                 return;
969         }
970         /* Wire up dependency to time source. */
971         ComponentKey adt_key(id, DEG_NODE_TYPE_ANIMATION);
972         TimeSourceKey time_src_key;
973         add_relation(time_src_key, adt_key, "TimeSrc -> Animation");
974         /* Relation from action itself. */
975         if (adt->action != NULL &&
976             !built_map_.checkIsBuiltAndTag(&adt->action->id))
977         {
978                 ComponentKey action_key(&adt->action->id, DEG_NODE_TYPE_ANIMATION);
979                 add_relation(action_key, adt_key, "Action -> Animation");
980         }
981         /* Get source operations. */
982         DepsNode *node_from = get_node(adt_key);
983         BLI_assert(node_from != NULL);
984         if (node_from == NULL) {
985                 return;
986         }
987         OperationDepsNode *operation_from = node_from->get_exit_operation();
988         BLI_assert(operation_from != NULL);
989         /* Build relations from animation operation to properties it changes. */
990         if (adt->action != NULL) {
991                 build_animdata_curves_targets(id, adt_key,
992                                       operation_from,
993                                       &adt->action->curves);
994         }
995         LISTBASE_FOREACH(NlaTrack *, nlt, &adt->nla_tracks) {
996                 build_animdata_nlastrip_targets(id, adt_key,
997                                                 operation_from,
998                                                 &nlt->strips);
999         }
1000 }
1001
1002 void DepsgraphRelationBuilder::build_animdata_curves_targets(
1003         ID *id, ComponentKey &adt_key,
1004         OperationDepsNode *operation_from,
1005         ListBase *curves)
1006 {
1007         /* Iterate over all curves and build relations. */
1008         PointerRNA id_ptr;
1009         RNA_id_pointer_create(id, &id_ptr);
1010         LISTBASE_FOREACH(FCurve *, fcu, curves) {
1011                 PointerRNA ptr;
1012                 PropertyRNA *prop;
1013                 int index;
1014                 if (!RNA_path_resolve_full(&id_ptr, fcu->rna_path,
1015                                            &ptr, &prop, &index))
1016                 {
1017                         continue;
1018                 }
1019                 DepsNode *node_to = graph_->find_node_from_pointer(&ptr, prop);
1020                 if (node_to == NULL) {
1021                         continue;
1022                 }
1023                 OperationDepsNode *operation_to = node_to->get_entry_operation();
1024                 /* NOTE: Special case for bones, avoid relation from animation to
1025                  * each of the bones. Bone evaluation could only start from pose
1026                  * init anyway.
1027                  */
1028                 if (operation_to->opcode == DEG_OPCODE_BONE_LOCAL) {
1029                         OperationKey pose_init_key(id,
1030                                                    DEG_NODE_TYPE_EVAL_POSE,
1031                                                    DEG_OPCODE_POSE_INIT);
1032                         add_relation(adt_key, pose_init_key, "Animation -> Prop", true);
1033                         continue;
1034                 }
1035                 graph_->add_new_relation(operation_from, operation_to,
1036                                          "Animation -> Prop",
1037                                          true);
1038                 /* It is possible that animation is writing to a nested ID datablock,
1039                  * need to make sure animation is evaluated after target ID is copied.
1040                  */
1041                 const IDDepsNode *id_node_from = operation_from->owner->owner;
1042                 const IDDepsNode *id_node_to = operation_to->owner->owner;
1043                 if (id_node_from != id_node_to) {
1044                         ComponentKey cow_key(id_node_to->id_orig,
1045                                              DEG_NODE_TYPE_COPY_ON_WRITE);
1046                         add_relation(cow_key, adt_key, "Target CoW -> Animation", true);
1047                 }
1048         }
1049 }
1050
1051 void DepsgraphRelationBuilder::build_animdata_nlastrip_targets(
1052         ID *id, ComponentKey &adt_key,
1053         OperationDepsNode *operation_from,
1054         ListBase *strips)
1055 {
1056         LISTBASE_FOREACH(NlaStrip *, strip, strips) {
1057                 if (strip->act != NULL) {
1058                         build_animdata_curves_targets(id, adt_key,
1059                                                       operation_from,
1060                                                       &strip->act->curves);
1061                 }
1062                 else if (strip->strips.first != NULL) {
1063                         build_animdata_nlastrip_targets(id, adt_key,
1064                                                         operation_from,
1065                                                         &strip->strips);
1066                 }
1067         }
1068 }
1069
1070 void DepsgraphRelationBuilder::build_animdata_drivers(ID *id)
1071 {
1072         AnimData *adt = BKE_animdata_from_id(id);
1073         if (adt == NULL) {
1074                 return;
1075         }
1076         ComponentKey adt_key(id, DEG_NODE_TYPE_ANIMATION);
1077         LISTBASE_FOREACH (FCurve *, fcu, &adt->drivers) {
1078                 OperationKey driver_key(id,
1079                                         DEG_NODE_TYPE_PARAMETERS,
1080                                         DEG_OPCODE_DRIVER,
1081                                         fcu->rna_path ? fcu->rna_path : "",
1082                                         fcu->array_index);
1083
1084                 /* create the driver's relations to targets */
1085                 build_driver(id, fcu);
1086                 /* Special case for array drivers: we can not multithread them because
1087                  * of the way how they work internally: animation system will write the
1088                  * whole array back to RNA even when changing individual array value.
1089                  *
1090                  * Some tricky things here:
1091                  * - array_index is -1 for single channel drivers, meaning we only have
1092                  *   to do some magic when array_index is not -1.
1093                  * - We do relation from next array index to a previous one, so we don't
1094                  *   have to deal with array index 0.
1095                  *
1096                  * TODO(sergey): Avoid liner lookup somehow.
1097                  */
1098                 if (fcu->array_index > 0) {
1099                         FCurve *fcu_prev = NULL;
1100                         LISTBASE_FOREACH (FCurve *, fcu_candidate, &adt->drivers) {
1101                                 /* Writing to different RNA paths is  */
1102                                 const char *rna_path = fcu->rna_path ? fcu->rna_path : "";
1103                                 if (!STREQ(fcu_candidate->rna_path, rna_path)) {
1104                                         continue;
1105                                 }
1106                                 /* We only do relation from previous fcurve to previous one. */
1107                                 if (fcu_candidate->array_index >= fcu->array_index) {
1108                                         continue;
1109                                 }
1110                                 /* Choose fcurve with highest possible array index. */
1111                                 if (fcu_prev == NULL ||
1112                                     fcu_candidate->array_index > fcu_prev->array_index)
1113                                 {
1114                                         fcu_prev = fcu_candidate;
1115                                 }
1116                         }
1117                         if (fcu_prev != NULL) {
1118                                 OperationKey prev_driver_key(id,
1119                                                              DEG_NODE_TYPE_PARAMETERS,
1120                                                              DEG_OPCODE_DRIVER,
1121                                                              fcu_prev->rna_path ? fcu_prev->rna_path : "",
1122                                                              fcu_prev->array_index);
1123                                 OperationKey driver_key(id,
1124                                                         DEG_NODE_TYPE_PARAMETERS,
1125                                                         DEG_OPCODE_DRIVER,
1126                                                         fcu->rna_path ? fcu->rna_path : "",
1127                                                         fcu->array_index);
1128                                 add_relation(prev_driver_key, driver_key, "Driver Order");
1129                         }
1130                 }
1131
1132                 /* prevent driver from occurring before own animation... */
1133                 if (adt->action || adt->nla_tracks.first) {
1134                         add_relation(adt_key, driver_key, "AnimData Before Drivers");
1135                 }
1136         }
1137 }
1138
1139 void DepsgraphRelationBuilder::build_driver(ID *id, FCurve *fcu)
1140 {
1141         ChannelDriver *driver = fcu->driver;
1142         OperationKey driver_key(id,
1143                                 DEG_NODE_TYPE_PARAMETERS,
1144                                 DEG_OPCODE_DRIVER,
1145                                 fcu->rna_path ? fcu->rna_path : "",
1146                                 fcu->array_index);
1147         /* Driver -> data components (for interleaved evaluation
1148          * bones/constraints/modifiers).
1149          */
1150         build_driver_data(id, fcu);
1151         /* Loop over variables to get the target relationships. */
1152         build_driver_variables(id, fcu);
1153         /* It's quite tricky to detect if the driver actually depends on time or
1154          * not, so for now we'll be quite conservative here about optimization and
1155          * consider all python drivers to be depending on time.
1156          */
1157         if ((driver->type == DRIVER_TYPE_PYTHON) &&
1158             python_driver_depends_on_time(driver))
1159         {
1160                 TimeSourceKey time_src_key;
1161                 add_relation(time_src_key, driver_key, "TimeSrc -> Driver");
1162         }
1163 }
1164
1165 void DepsgraphRelationBuilder::build_driver_data(ID *id, FCurve *fcu)
1166 {
1167         OperationKey driver_key(id,
1168                                 DEG_NODE_TYPE_PARAMETERS,
1169                                 DEG_OPCODE_DRIVER,
1170                                 fcu->rna_path ? fcu->rna_path : "",
1171                                 fcu->array_index);
1172         const char *rna_path = fcu->rna_path ? fcu->rna_path : "";
1173         const RNAPathKey self_key(id, rna_path);
1174         if (GS(id->name) == ID_AR && strstr(rna_path, "bones[")) {
1175                 /* Drivers on armature-level bone settings (i.e. bbone stuff),
1176                  * which will affect the evaluation of corresponding pose bones.
1177                  */
1178                 IDDepsNode *arm_node = graph_->find_id_node(id);
1179                 char *bone_name = BLI_str_quoted_substrN(rna_path, "bones[");
1180                 if (arm_node != NULL && bone_name != NULL) {
1181                         /* Find objects which use this, and make their eval callbacks
1182                          * depend on this.
1183                          */
1184                         foreach (DepsRelation *rel, arm_node->outlinks) {
1185                                 IDDepsNode *to_node = (IDDepsNode *)rel->to;
1186                                 /* We only care about objects with pose data which use this. */
1187                                 if (GS(to_node->id_orig->name) == ID_OB) {
1188                                         Object *object = (Object *)to_node->id_orig;
1189                                         // NOTE: object->pose may be NULL
1190                                         bPoseChannel *pchan = BKE_pose_channel_find_name(object->pose,
1191                                                                                          bone_name);
1192                                         if (pchan != NULL) {
1193                                                 OperationKey bone_key(&object->id,
1194                                                                       DEG_NODE_TYPE_BONE,
1195                                                                       pchan->name,
1196                                                                       DEG_OPCODE_BONE_LOCAL);
1197                                                 add_relation(driver_key,
1198                                                              bone_key,
1199                                                              "Arm Bone -> Driver -> Bone");
1200                                         }
1201                                 }
1202                         }
1203                         /* Free temp data. */
1204                         MEM_freeN(bone_name);
1205                         bone_name = NULL;
1206                 }
1207                 else {
1208                         fprintf(stderr,
1209                                 "Couldn't find armature bone name for driver path - '%s'\n",
1210                                 rna_path);
1211                 }
1212         }
1213         else {
1214                 RNAPathKey target_key(id, rna_path);
1215                 add_relation(driver_key, target_key, "Driver -> Target");
1216                 /* Similar to the case with f-curves, driver might drive a nested
1217                  * datablock, which means driver execution should wait for that
1218                  * datablock to be copied.
1219                  */
1220                 {
1221                         PointerRNA id_ptr;
1222                         PointerRNA ptr;
1223                         RNA_id_pointer_create(id, &id_ptr);
1224                         if (RNA_path_resolve_full(&id_ptr, fcu->rna_path, &ptr, NULL, NULL)) {
1225                                 if (id_ptr.id.data != ptr.id.data) {
1226                                         ComponentKey cow_key((ID *)ptr.id.data,
1227                                                              DEG_NODE_TYPE_COPY_ON_WRITE);
1228                                         add_relation(cow_key,
1229                                                      driver_key,
1230                                                      "Target CoW -> Driver",
1231                                                      true);
1232                                 }
1233                         }
1234                 }
1235                 if (RNA_pointer_is_null(&target_key.ptr)) {
1236                         /* TODO(sergey): This would only mean that driver is broken.
1237                          * so we can't create relation anyway. However, we need to avoid
1238                          * adding drivers which are known to be buggy to a dependency
1239                          * graph, in order to save computational power.
1240                          */
1241                 }
1242                 else {
1243                         if (target_key.prop != NULL &&
1244                             RNA_property_is_idprop(target_key.prop))
1245                         {
1246                                 OperationKey parameters_key(id,
1247                                                             DEG_NODE_TYPE_PARAMETERS,
1248                                                             DEG_OPCODE_PARAMETERS_EVAL);
1249                                 add_relation(target_key,
1250                                              parameters_key,
1251                                              "Driver Target -> Properties");
1252                         }
1253                         add_relation(driver_key, target_key, "Driver -> Target");
1254                 }
1255         }
1256 }
1257
1258 void DepsgraphRelationBuilder::build_driver_variables(ID *id, FCurve *fcu)
1259 {
1260         ChannelDriver *driver = fcu->driver;
1261         OperationKey driver_key(id,
1262                                 DEG_NODE_TYPE_PARAMETERS,
1263                                 DEG_OPCODE_DRIVER,
1264                                 fcu->rna_path ? fcu->rna_path : "",
1265                                 fcu->array_index);
1266         const char *rna_path = fcu->rna_path ? fcu->rna_path : "";
1267         const RNAPathKey self_key(id, rna_path);
1268
1269         LISTBASE_FOREACH (DriverVar *, dvar, &driver->variables) {
1270                 /* Only used targets. */
1271                 DRIVER_TARGETS_USED_LOOPER(dvar)
1272                 {
1273                         if (dtar->id == NULL) {
1274                                 continue;
1275                         }
1276                         build_id(dtar->id);
1277                         /* Special handling for directly-named bones. */
1278                         if ((dtar->flag & DTAR_FLAG_STRUCT_REF) &&
1279                             (((Object *)dtar->id)->type == OB_ARMATURE) &&
1280                             (dtar->pchan_name[0]))
1281                         {
1282                                 Object *object = (Object *)dtar->id;
1283                                 bPoseChannel *target_pchan =
1284                                         BKE_pose_channel_find_name(object->pose,
1285                                                                    dtar->pchan_name);
1286                                 if (target_pchan == NULL) {
1287                                         continue;
1288                                 }
1289                                 OperationKey variable_key(dtar->id,
1290                                                           DEG_NODE_TYPE_BONE,
1291                                                           target_pchan->name,
1292                                                           DEG_OPCODE_BONE_DONE);
1293                                 if (is_same_bone_dependency(variable_key, self_key)) {
1294                                         continue;
1295                                 }
1296                                 add_relation(variable_key, driver_key, "Bone Target -> Driver");
1297                         }
1298                         else if (dtar->flag & DTAR_FLAG_STRUCT_REF) {
1299                                 /* Get node associated with the object's transforms. */
1300                                 if (dtar->id == id) {
1301                                         /* Ignore input dependency if we're driving properties of
1302                                          * the same ID, otherwise we'll be ending up in a cyclic
1303                                          * dependency here.
1304                                          */
1305                                         continue;
1306                                 }
1307                                 OperationKey target_key(dtar->id,
1308                                                         DEG_NODE_TYPE_TRANSFORM,
1309                                                         DEG_OPCODE_TRANSFORM_FINAL);
1310                                 add_relation(target_key, driver_key, "Target -> Driver");
1311                         }
1312                         else if (dtar->rna_path) {
1313                                 RNAPathKey variable_key(dtar->id, dtar->rna_path);
1314                                 if (RNA_pointer_is_null(&variable_key.ptr)) {
1315                                         continue;
1316                                 }
1317                                 if (is_same_bone_dependency(variable_key, self_key) ||
1318                                     is_same_nodetree_node_dependency(variable_key, self_key) ||
1319                                     is_same_shapekey_dependency(variable_key, self_key))
1320                                 {
1321                                         continue;
1322                                 }
1323                                 add_relation(variable_key, driver_key, "RNA Target -> Driver");
1324                         }
1325                         else {
1326                                 if (dtar->id == id) {
1327                                         /* Ignore input dependency if we're driving properties of
1328                                          * the same ID, otherwise we'll be ending up in a cyclic
1329                                          * dependency here.
1330                                          */
1331                                         continue;
1332                                 }
1333                                 /* Resolve path to get node. */
1334                                 RNAPathKey target_key(dtar->id,
1335                                                       dtar->rna_path ? dtar->rna_path : "");
1336                                 add_relation(target_key, driver_key, "RNA Target -> Driver");
1337                         }
1338                 }
1339                 DRIVER_TARGETS_LOOPER_END
1340         }
1341 }
1342
1343 void DepsgraphRelationBuilder::build_world(World *world)
1344 {
1345         if (built_map_.checkIsBuiltAndTag(world)) {
1346                 return;
1347         }
1348         build_animdata(&world->id);
1349         /* TODO: other settings? */
1350         /* world's nodetree */
1351         if (world->nodetree != NULL) {
1352                 build_nodetree(world->nodetree);
1353                 ComponentKey ntree_key(&world->nodetree->id, DEG_NODE_TYPE_SHADING);
1354                 ComponentKey world_key(&world->id, DEG_NODE_TYPE_SHADING);
1355                 add_relation(ntree_key, world_key, "NTree->World Shading Update");
1356                 build_nested_nodetree(&world->id, world->nodetree);
1357         }
1358 }
1359
1360 void DepsgraphRelationBuilder::build_rigidbody(Scene *scene)
1361 {
1362         RigidBodyWorld *rbw = scene->rigidbody_world;
1363
1364         OperationKey init_key(&scene->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_REBUILD);
1365         OperationKey sim_key(&scene->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_SIM);
1366
1367         /* rel between the two sim-nodes */
1368         add_relation(init_key, sim_key, "Rigidbody [Init -> SimStep]");
1369
1370         /* set up dependencies between these operations and other builtin nodes --------------- */
1371
1372         /* time dependency */
1373         TimeSourceKey time_src_key;
1374         add_relation(time_src_key, init_key, "TimeSrc -> Rigidbody Reset/Rebuild (Optional)");
1375
1376         /* objects - simulation participants */
1377         if (rbw->group) {
1378                 const ListBase group_objects = BKE_collection_object_cache_get(rbw->group);
1379                 LISTBASE_FOREACH (Base *, base, &group_objects) {
1380                         Object *object = base->object;
1381                         if (object == NULL || object->type != OB_MESH) {
1382                                 continue;
1383                         }
1384
1385                         /* hook up evaluation order...
1386                          * 1) flushing rigidbody results follows base transforms being applied
1387                          * 2) rigidbody flushing can only be performed after simulation has been run
1388                          *
1389                          * 3) simulation needs to know base transforms to figure out what to do
1390                          *    XXX: there's probably a difference between passive and active
1391                          *         - passive don't change, so may need to know full transform...
1392                          */
1393                         OperationKey rbo_key(&object->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_TRANSFORM_COPY);
1394
1395                         eDepsOperation_Code trans_opcode = object->parent ? DEG_OPCODE_TRANSFORM_PARENT : DEG_OPCODE_TRANSFORM_LOCAL;
1396                         OperationKey trans_op(&object->id, DEG_NODE_TYPE_TRANSFORM, trans_opcode);
1397
1398                         add_relation(sim_key, rbo_key, "Rigidbody Sim Eval -> RBO Sync");
1399
1400                         /* if constraints exist, those depend on the result of the rigidbody sim
1401                          * - This allows constraints to modify the result of the sim (i.e. clamping)
1402                          *   while still allowing the sim to depend on some changes to the objects.
1403                          *   Also, since constraints are hooked up to the final nodes, this link
1404                          *   means that we can also fit in there too...
1405                          * - Later, it might be good to include a constraint in the stack allowing us
1406                          *   to control whether rigidbody eval gets interleaved into the constraint stack
1407                          */
1408                         if (object->constraints.first) {
1409                                 OperationKey constraint_key(&object->id,
1410                                                             DEG_NODE_TYPE_TRANSFORM,
1411                                                             DEG_OPCODE_TRANSFORM_CONSTRAINTS);
1412                                 add_relation(rbo_key, constraint_key, "RBO Sync -> Ob Constraints");
1413                         }
1414                         else {
1415                                 /* Final object transform depends on rigidbody.
1416                                  *
1417                                  * NOTE: Currently we consider final here an ubereval node.
1418                                  * If it is gone we'll need to reconsider relation here.
1419                                  */
1420                                 OperationKey uber_key(&object->id,
1421                                                       DEG_NODE_TYPE_TRANSFORM,
1422                                                       DEG_OPCODE_TRANSFORM_OBJECT_UBEREVAL);
1423                                 add_relation(rbo_key, uber_key, "RBO Sync -> Uber (Temp)");
1424                         }
1425
1426                         /* Needed to get correct base values. */
1427                         add_relation(trans_op, sim_key, "Base Ob Transform -> Rigidbody Sim Eval");
1428                 }
1429         }
1430
1431         /* constraints */
1432         if (rbw->constraints) {
1433                 const ListBase constraint_objects = BKE_collection_object_cache_get(rbw->constraints);
1434                 LISTBASE_FOREACH (Base *, base, &constraint_objects) {
1435                         Object *object = base->object;
1436                         if (object == NULL || !object->rigidbody_constraint) {
1437                                 continue;
1438                         }
1439
1440                         RigidBodyCon *rbc = object->rigidbody_constraint;
1441
1442                         /* final result of the constraint object's transform controls how the
1443                          * constraint affects the physics sim for these objects
1444                          */
1445                         ComponentKey trans_key(&object->id, DEG_NODE_TYPE_TRANSFORM);
1446                         OperationKey ob1_key(&rbc->ob1->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_TRANSFORM_COPY);
1447                         OperationKey ob2_key(&rbc->ob2->id, DEG_NODE_TYPE_TRANSFORM, DEG_OPCODE_RIGIDBODY_TRANSFORM_COPY);
1448
1449                         /* - constrained-objects sync depends on the constraint-holder */
1450                         add_relation(trans_key, ob1_key, "RigidBodyConstraint -> RBC.Object_1");
1451                         add_relation(trans_key, ob2_key, "RigidBodyConstraint -> RBC.Object_2");
1452
1453                         /* - ensure that sim depends on this constraint's transform */
1454                         add_relation(trans_key, sim_key, "RigidBodyConstraint Transform -> RB Simulation");
1455                 }
1456         }
1457 }
1458
1459 void DepsgraphRelationBuilder::build_particles(Object *object)
1460 {
1461         TimeSourceKey time_src_key;
1462         OperationKey obdata_ubereval_key(&object->id,
1463                                          DEG_NODE_TYPE_GEOMETRY,
1464                                          DEG_OPCODE_GEOMETRY_UBEREVAL);
1465         OperationKey eval_init_key(&object->id,
1466                                    DEG_NODE_TYPE_EVAL_PARTICLES,
1467                                    DEG_OPCODE_PARTICLE_SYSTEM_EVAL_INIT);
1468
1469         /* Particle systems. */
1470         LISTBASE_FOREACH (ParticleSystem *, psys, &object->particlesystem) {
1471                 ParticleSettings *part = psys->part;
1472
1473                 /* Build particle settings relations.
1474                  *
1475                  * NOTE: The call itself ensures settings are only build once.
1476                  */
1477                 build_particle_settings(part);
1478
1479                 /* This particle system. */
1480                 OperationKey psys_key(&object->id,
1481                                       DEG_NODE_TYPE_EVAL_PARTICLES,
1482                                       DEG_OPCODE_PARTICLE_SYSTEM_EVAL,
1483                                       psys->name);
1484
1485                 /* Update particle system when settings changes. */
1486                 OperationKey particle_settings_key(&part->id,
1487                                                    DEG_NODE_TYPE_PARAMETERS,
1488                                                    DEG_OPCODE_PARTICLE_SETTINGS_EVAL);
1489                 add_relation(particle_settings_key, eval_init_key, "Particle Settings Change");
1490                 add_relation(eval_init_key, psys_key, "Init -> PSys");
1491                 /* TODO(sergey): Currently particle update is just a placeholder,
1492                  * hook it to the ubereval node so particle system is getting updated
1493                  * on playback.
1494                  */
1495                 add_relation(psys_key, obdata_ubereval_key, "PSys -> UberEval");
1496                 /* Collisions */
1497                 if (part->type != PART_HAIR) {
1498                         add_collision_relations(psys_key,
1499                                                 scene_,
1500                                                 object,
1501                                                 part->collision_group,
1502                                                 true,
1503                                                 "Particle Collision");
1504                 }
1505                 else if ((psys->flag & PSYS_HAIR_DYNAMICS) &&
1506                          psys->clmd != NULL &&
1507                          psys->clmd->coll_parms != NULL)
1508                 {
1509                         add_collision_relations(psys_key,
1510                                                 scene_,
1511                                                 object,
1512                                                 psys->clmd->coll_parms->group,
1513                                                 true,
1514                                                 "Hair Collision");
1515                 }
1516                 /* Effectors. */
1517                 add_forcefield_relations(psys_key,
1518                                          scene_,
1519                                          object,
1520                                          psys,
1521                                          part->effector_weights,
1522                                          part->type == PART_HAIR,
1523                                          "Particle Field");
1524                 /* Boids .*/
1525                 if (part->boids) {
1526                         LISTBASE_FOREACH (BoidState *, state, &part->boids->states) {
1527                                 LISTBASE_FOREACH (BoidRule *, rule, &state->rules) {
1528                                         Object *ruleob = NULL;
1529                                         if (rule->type == eBoidRuleType_Avoid) {
1530                                                 ruleob = ((BoidRuleGoalAvoid *)rule)->ob;
1531                                         }
1532                                         else if (rule->type == eBoidRuleType_FollowLeader) {
1533                                                 ruleob = ((BoidRuleFollowLeader *)rule)->ob;
1534                                         }
1535                                         if (ruleob) {
1536                                                 ComponentKey ruleob_key(&ruleob->id,
1537                                                                         DEG_NODE_TYPE_TRANSFORM);
1538                                                 add_relation(ruleob_key, psys_key, "Boid Rule");
1539                                         }
1540                                 }
1541                         }
1542                 }
1543                 switch (part->ren_as) {
1544                         case PART_DRAW_OB:
1545                                 if (part->dup_ob != NULL) {
1546                                         /* Make sure object's relations are all built.  */
1547                                         build_object(NULL, part->dup_ob);
1548                                         /* Build relation for the particle visualization. */
1549                                         build_particles_visualization_object(object,
1550                                                                              psys,
1551                                                                              part->dup_ob);
1552                                 }
1553                                 break;
1554                         case PART_DRAW_GR:
1555                                 if (part->dup_group != NULL) {
1556                                         build_collection(NULL, part->dup_group);
1557                                         LISTBASE_FOREACH (CollectionObject *, go, &part->dup_group->gobject) {
1558                                                 build_particles_visualization_object(object,
1559                                                                                      psys,
1560                                                                                      go->ob);
1561                                         }
1562                                 }
1563                                 break;
1564                 }
1565         }
1566
1567         /* Particle depends on the object transform, so that channel is to be ready
1568          * first.
1569          *
1570          * TODO(sergey): This relation should be altered once real granular update
1571          * is implemented.
1572          */
1573         ComponentKey transform_key(&object->id, DEG_NODE_TYPE_TRANSFORM);
1574         add_relation(transform_key, obdata_ubereval_key, "Partcile Eval");
1575
1576         OperationKey point_cache_reset_key(&object->id,
1577                                            DEG_NODE_TYPE_CACHE,
1578                                            DEG_OPCODE_POINT_CACHE_RESET);
1579         add_relation(transform_key, point_cache_reset_key, "Object Transform -> Point Cache Reset");
1580         add_relation(point_cache_reset_key, obdata_ubereval_key, "Point Cache Reset -> UberEval");
1581 }
1582
1583 void DepsgraphRelationBuilder::build_particle_settings(ParticleSettings *part)
1584 {
1585         if (built_map_.checkIsBuiltAndTag(part)) {
1586                 return;
1587         }
1588         /* Animation data relations. */
1589         build_animdata(&part->id);
1590 }
1591
1592 void DepsgraphRelationBuilder::build_particles_visualization_object(
1593         Object *object,
1594         ParticleSystem *psys,
1595         Object *draw_object)
1596 {
1597         OperationKey psys_key(&object->id,
1598                               DEG_NODE_TYPE_EVAL_PARTICLES,
1599                               DEG_OPCODE_PARTICLE_SYSTEM_EVAL,
1600                               psys->name);
1601         OperationKey obdata_ubereval_key(&object->id,
1602                                          DEG_NODE_TYPE_GEOMETRY,
1603                                          DEG_OPCODE_GEOMETRY_UBEREVAL);
1604         ComponentKey dup_ob_key(&draw_object->id, DEG_NODE_TYPE_TRANSFORM);
1605         add_relation(dup_ob_key, psys_key, "Particle Object Visualization");
1606         if (draw_object->type == OB_MBALL) {
1607                 ComponentKey dup_geometry_key(&draw_object->id, DEG_NODE_TYPE_GEOMETRY);
1608                 add_relation(obdata_ubereval_key,
1609                              dup_geometry_key,
1610                              "Particle MBall Visualization");
1611         }
1612 }
1613
1614 void DepsgraphRelationBuilder::build_cloth(Object *object,
1615                                            ModifierData * /*md*/)
1616 {
1617         OperationKey cache_key(&object->id,
1618                                DEG_NODE_TYPE_CACHE,
1619                                DEG_OPCODE_GEOMETRY_CLOTH_MODIFIER);
1620         /* Cache component affects on modifier. */
1621         OperationKey modifier_key(&object->id,
1622                                   DEG_NODE_TYPE_GEOMETRY,
1623                                   DEG_OPCODE_GEOMETRY_UBEREVAL);
1624         add_relation(cache_key, modifier_key, "Cloth Cache -> Cloth");
1625 }
1626
1627 /* Shapekeys */
1628 void DepsgraphRelationBuilder::build_shapekeys(ID *obdata, Key *key)
1629 {
1630         ComponentKey obdata_key(obdata, DEG_NODE_TYPE_GEOMETRY);
1631
1632         /* attach animdata to geometry */
1633         build_animdata(&key->id);
1634
1635         if (key->adt) {
1636                 // TODO: this should really be handled in build_animdata, since many of these cases will need it
1637                 if (key->adt->action || key->adt->nla_tracks.first) {
1638                         ComponentKey adt_key(&key->id, DEG_NODE_TYPE_ANIMATION);
1639                         add_relation(adt_key, obdata_key, "Animation");
1640                 }
1641
1642                 /* NOTE: individual shapekey drivers are handled above already */
1643         }
1644
1645         /* attach to geometry */
1646         // XXX: aren't shapekeys now done as a pseudo-modifier on object?
1647         //ComponentKey key_key(&key->id, DEG_NODE_TYPE_GEOMETRY); // FIXME: this doesn't exist
1648         //add_relation(key_key, obdata_key, "Shapekeys");
1649 }
1650
1651 /**
1652  * ObData Geometry Evaluation
1653  * ==========================
1654  *
1655  * The evaluation of geometry on objects is as follows:
1656  * - The actual evaluated of the derived geometry (e.g. DerivedMesh, DispList, etc.)
1657  *   occurs in the Geometry component of the object which references this. This includes
1658  *   modifiers, and the temporary "ubereval" for geometry.
1659  * - Therefore, each user of a piece of shared geometry data ends up evaluating its own
1660  *   version of the stuff, complete with whatever modifiers it may use.
1661  *
1662  * - The datablocks for the geometry data - "obdata" (e.g. ID_ME, ID_CU, ID_LT, etc.) are used for
1663  *     1) calculating the bounding boxes of the geometry data,
1664  *     2) aggregating inward links from other objects (e.g. for text on curve, etc.)
1665  *        and also for the links coming from the shapekey datablocks
1666  * - Animation/Drivers affecting the parameters of the geometry are made to trigger
1667  *   updates on the obdata geometry component, which then trigger downstream
1668  *   re-evaluation of the individual instances of this geometry.
1669  */
1670 // TODO: Materials and lighting should probably get their own component, instead of being lumped under geometry?
1671 void DepsgraphRelationBuilder::build_obdata_geom(Object *object)
1672 {
1673         ID *obdata = (ID *)object->data;
1674
1675         /* Init operation of object-level geometry evaluation. */
1676         OperationKey geom_init_key(&object->id, DEG_NODE_TYPE_GEOMETRY, DEG_OPCODE_PLACEHOLDER, "Eval Init");
1677
1678         /* get nodes for result of obdata's evaluation, and geometry evaluation on object */
1679         ComponentKey obdata_geom_key(obdata, DEG_NODE_TYPE_GEOMETRY);
1680         ComponentKey geom_key(&object->id, DEG_NODE_TYPE_GEOMETRY);
1681
1682         /* link components to each other */
1683         add_relation(obdata_geom_key, geom_key, "Object Geometry Base Data");
1684
1685         OperationKey obdata_ubereval_key(&object->id,
1686                                          DEG_NODE_TYPE_GEOMETRY,
1687                                          DEG_OPCODE_GEOMETRY_UBEREVAL);
1688
1689         /* Special case: modifiers and DerivedMesh creation queries scene for various
1690          * things like data mask to be used. We add relation here to ensure object is
1691          * never evaluated prior to Scene's CoW is ready.
1692          */
1693         OperationKey scene_key(&scene_->id,
1694                                DEG_NODE_TYPE_PARAMETERS,
1695                                DEG_OPCODE_PLACEHOLDER,
1696                                "Scene Eval");
1697         DepsRelation *rel = add_relation(scene_key, obdata_ubereval_key, "CoW Relation");
1698         rel->flag |= DEPSREL_FLAG_NO_FLUSH;
1699
1700         /* Modifiers */
1701         if (object->modifiers.first != NULL) {
1702                 ModifierUpdateDepsgraphContext ctx = {};
1703                 ctx.scene = scene_;
1704                 ctx.object = object;
1705
1706                 LISTBASE_FOREACH (ModifierData *, md, &object->modifiers) {
1707                         const ModifierTypeInfo *mti = modifierType_getInfo((ModifierType)md->type);
1708                         if (mti->updateDepsgraph) {
1709                                 DepsNodeHandle handle = create_node_handle(obdata_ubereval_key);
1710                                 ctx.node = reinterpret_cast< ::DepsNodeHandle* >(&handle);
1711                                 mti->updateDepsgraph(md, &ctx);
1712                         }
1713                         if (BKE_object_modifier_use_time(object, md)) {
1714                                 TimeSourceKey time_src_key;
1715                                 add_relation(time_src_key, obdata_ubereval_key, "Time Source");
1716                         }
1717                         if (md->type == eModifierType_Cloth) {
1718                                 build_cloth(object, md);
1719                         }
1720                 }
1721         }
1722
1723         /* materials */
1724         if (object->totcol) {
1725                 for (int a = 1; a <= object->totcol; a++) {
1726                         Material *ma = give_current_material(object, a);
1727                         if (ma != NULL) {
1728                                 build_material(ma);
1729
1730                                 if (object->type == OB_MESH) {
1731                                         OperationKey material_key(&ma->id,
1732                                                                   DEG_NODE_TYPE_SHADING,
1733                                                                   DEG_OPCODE_MATERIAL_UPDATE);
1734                                         OperationKey shading_key(&object->id, DEG_NODE_TYPE_SHADING, DEG_OPCODE_SHADING);
1735                                         add_relation(material_key, shading_key, "Material Update");
1736                                 }
1737                         }
1738                 }
1739         }
1740
1741         /* geometry collision */
1742         if (ELEM(object->type, OB_MESH, OB_CURVE, OB_LATTICE)) {
1743                 // add geometry collider relations
1744         }
1745
1746         /* Make sure uber update is the last in the dependencies.
1747          *
1748          * TODO(sergey): Get rid of this node.
1749          */
1750         if (object->type != OB_ARMATURE) {
1751                 /* Armatures does no longer require uber node. */
1752                 OperationKey obdata_ubereval_key(&object->id, DEG_NODE_TYPE_GEOMETRY, DEG_OPCODE_GEOMETRY_UBEREVAL);
1753                 add_relation(geom_init_key, obdata_ubereval_key, "Object Geometry UberEval");
1754         }
1755
1756         if (built_map_.checkIsBuiltAndTag(obdata)) {
1757                 return;
1758         }
1759
1760         /* Link object data evaluation node to exit operation. */
1761         OperationKey obdata_geom_eval_key(obdata, DEG_NODE_TYPE_GEOMETRY, DEG_OPCODE_PLACEHOLDER, "Geometry Eval");
1762         OperationKey obdata_geom_done_key(obdata, DEG_NODE_TYPE_GEOMETRY, DEG_OPCODE_PLACEHOLDER, "Eval Done");
1763         add_relation(obdata_geom_eval_key, obdata_geom_done_key, "ObData Geom Eval Done");
1764
1765         /* type-specific node/links */
1766         switch (object->type) {
1767                 case OB_MESH:
1768                         /* NOTE: This is compatibility code to support particle systems
1769                          *
1770                          * for viewport being properly rendered in final render mode.
1771                          * This relation is similar to what dag_object_time_update_flags()
1772                          * was doing for mesh objects with particle system.
1773                          *
1774                          * Ideally we need to get rid of this relation.
1775                          */
1776                         if (object_particles_depends_on_time(object)) {
1777                                 TimeSourceKey time_key;
1778                                 OperationKey obdata_ubereval_key(&object->id,
1779                                                                  DEG_NODE_TYPE_GEOMETRY,
1780                                                                  DEG_OPCODE_GEOMETRY_UBEREVAL);
1781                                 add_relation(time_key, obdata_ubereval_key, "Legacy particle time");
1782                         }
1783                         break;
1784
1785                 case OB_MBALL:
1786                 {
1787                         Object *mom = BKE_mball_basis_find(scene_, object);
1788                         ComponentKey mom_geom_key(&mom->id, DEG_NODE_TYPE_GEOMETRY);
1789                         /* motherball - mom depends on children! */
1790                         if (mom == object) {
1791                                 ComponentKey mom_transform_key(&mom->id,
1792                                                                DEG_NODE_TYPE_TRANSFORM);
1793                                 add_relation(mom_transform_key,
1794                                              mom_geom_key,
1795                                              "Metaball Motherball Transform -> Geometry");
1796                         }
1797                         else {
1798                                 ComponentKey transform_key(&object->id, DEG_NODE_TYPE_TRANSFORM);
1799                                 add_relation(geom_key, mom_geom_key, "Metaball Motherball");
1800                                 add_relation(transform_key, mom_geom_key, "Metaball Motherball");
1801                         }
1802                         break;
1803                 }
1804
1805                 case OB_CURVE:
1806                 case OB_FONT:
1807                 {
1808                         Curve *cu = (Curve *)obdata;
1809
1810                         /* curve's dependencies */
1811                         // XXX: these needs geom data, but where is geom stored?
1812                         if (cu->bevobj) {
1813                                 ComponentKey bevob_geom_key(&cu->bevobj->id, DEG_NODE_TYPE_GEOMETRY);
1814                                 add_relation(bevob_geom_key, obdata_geom_key, "Curve Bevel Geometry");
1815                                 /* We only need scale, but we can't tag individual TRANSFORM components. */
1816                                 ComponentKey bevob_key(&cu->bevobj->id, DEG_NODE_TYPE_TRANSFORM);
1817                                 add_relation(bevob_key, obdata_geom_key, "Curve Bevel Scale");
1818                                 build_object(NULL, cu->bevobj);
1819                         }
1820                         if (cu->taperobj) {
1821                                 ComponentKey taperob_key(&cu->taperobj->id, DEG_NODE_TYPE_GEOMETRY);
1822                                 build_object(NULL, cu->taperobj);
1823                                 add_relation(taperob_key, geom_key, "Curve Taper");
1824                         }
1825                         if (object->type == OB_FONT) {
1826                                 if (cu->textoncurve) {
1827                                         ComponentKey textoncurve_key(&cu->textoncurve->id, DEG_NODE_TYPE_GEOMETRY);
1828                                         build_object(NULL, cu->textoncurve);
1829                                         add_relation(textoncurve_key, geom_key, "Text on Curve");
1830                                 }
1831                         }
1832                         break;
1833                 }
1834
1835                 case OB_SURF: /* Nurbs Surface */
1836                 {
1837                         break;
1838                 }
1839
1840                 case OB_LATTICE: /* Lattice */
1841                 {
1842                         break;
1843                 }
1844         }
1845
1846         /* ShapeKeys */
1847         Key *key = BKE_key_from_object(object);
1848         if (key) {
1849                 build_shapekeys(obdata, key);
1850         }
1851 }
1852
1853 /* Cameras */
1854 // TODO: Link scene-camera links in somehow...
1855 void DepsgraphRelationBuilder::build_camera(Object *object)
1856 {
1857         Camera *camera = (Camera *)object->data;
1858         if (built_map_.checkIsBuiltAndTag(camera)) {
1859                 return;
1860         }
1861
1862         ComponentKey object_parameters_key(&object->id, DEG_NODE_TYPE_PARAMETERS);
1863         ComponentKey camera_parameters_key(&camera->id, DEG_NODE_TYPE_PARAMETERS);
1864
1865         add_relation(camera_parameters_key, object_parameters_key,
1866                      "Camera -> Object");
1867
1868         /* DOF */
1869         if (camera->dof_ob != NULL) {
1870                 ComponentKey dof_ob_key(&camera->dof_ob->id, DEG_NODE_TYPE_TRANSFORM);
1871                 add_relation(dof_ob_key, object_parameters_key, "Camera DOF");
1872         }
1873 }
1874
1875 /* Lamps */
1876 void DepsgraphRelationBuilder::build_lamp(Object *object)
1877 {
1878         Lamp *lamp = (Lamp *)object->data;
1879         if (built_map_.checkIsBuiltAndTag(lamp)) {
1880                 return;
1881         }
1882
1883         ComponentKey object_parameters_key(&object->id, DEG_NODE_TYPE_PARAMETERS);
1884         ComponentKey lamp_parameters_key(&lamp->id, DEG_NODE_TYPE_PARAMETERS);
1885
1886         add_relation(lamp_parameters_key, object_parameters_key,
1887                      "Lamp -> Object");
1888
1889         /* lamp's nodetree */
1890         if (lamp->nodetree != NULL) {
1891                 build_nodetree(lamp->nodetree);
1892                 ComponentKey nodetree_key(&lamp->nodetree->id, DEG_NODE_TYPE_SHADING);
1893                 add_relation(nodetree_key, lamp_parameters_key, "NTree->Lamp Parameters");
1894                 build_nested_nodetree(&lamp->id, lamp->nodetree);
1895         }
1896
1897         /* Make sure copy on write of lamp data is always properly updated for
1898          * visible lamps.
1899          */
1900         OperationKey ob_copy_on_write_key(&object->id,
1901                                           DEG_NODE_TYPE_COPY_ON_WRITE,
1902                                           DEG_OPCODE_COPY_ON_WRITE);
1903         OperationKey lamp_copy_on_write_key(&lamp->id,
1904                                             DEG_NODE_TYPE_COPY_ON_WRITE,
1905                                             DEG_OPCODE_COPY_ON_WRITE);
1906         add_relation(lamp_copy_on_write_key, ob_copy_on_write_key, "Eval Order");
1907 }
1908
1909 void DepsgraphRelationBuilder::build_nodetree(bNodeTree *ntree)
1910 {
1911         if (ntree == NULL) {
1912                 return;
1913         }
1914         if (built_map_.checkIsBuiltAndTag(ntree)) {
1915                 return;
1916         }
1917         build_animdata(&ntree->id);
1918         ComponentKey shading_key(&ntree->id, DEG_NODE_TYPE_SHADING);
1919         /* nodetree's nodes... */
1920         LISTBASE_FOREACH (bNode *, bnode, &ntree->nodes) {
1921                 ID *id = bnode->id;
1922                 if (id == NULL) {
1923                         continue;
1924                 }
1925                 ID_Type id_type = GS(id->name);
1926                 if (id_type == ID_MA) {
1927                         build_material((Material *)bnode->id);
1928                 }
1929                 else if (id_type == ID_TE) {
1930                         build_texture((Tex *)bnode->id);
1931                 }
1932                 else if (id_type == ID_IM) {
1933                         /* nothing for now. */
1934                 }
1935                 else if (id_type == ID_OB) {
1936                         build_object(NULL, (Object *)id);
1937                 }
1938                 else if (id_type == ID_SCE) {
1939                         /* Scenes are used by compositor trees, and handled by render
1940                          * pipeline. No need to build dependencies for them here.
1941                          */
1942                 }
1943                 else if (id_type == ID_TXT) {
1944                         /* Ignore script nodes. */
1945                 }
1946                 else if (bnode->type == NODE_GROUP) {
1947                         bNodeTree *group_ntree = (bNodeTree *)id;
1948                         build_nodetree(group_ntree);
1949                         ComponentKey group_shading_key(&group_ntree->id,
1950                                                        DEG_NODE_TYPE_SHADING);
1951                         add_relation(group_shading_key, shading_key, "Group Node");
1952                 }
1953                 else {
1954                         BLI_assert(!"Unknown ID type used for node");
1955                 }
1956         }
1957
1958         OperationKey shading_update_key(&ntree->id,
1959                                         DEG_NODE_TYPE_SHADING,
1960                                         DEG_OPCODE_MATERIAL_UPDATE);
1961         OperationKey shading_parameters_key(&ntree->id,
1962                                             DEG_NODE_TYPE_SHADING_PARAMETERS,
1963                                             DEG_OPCODE_MATERIAL_UPDATE);
1964         add_relation(shading_parameters_key, shading_update_key, "NTree Shading Parameters");
1965
1966         if (check_id_has_anim_component(&ntree->id)) {
1967                 ComponentKey animation_key(&ntree->id, DEG_NODE_TYPE_ANIMATION);
1968                 add_relation(animation_key, shading_parameters_key, "NTree Shading Parameters");
1969         }
1970 }
1971
1972 /* Recursively build graph for material */
1973 void DepsgraphRelationBuilder::build_material(Material *material)
1974 {
1975         if (built_map_.checkIsBuiltAndTag(material)) {
1976                 return;
1977         }
1978         /* animation */
1979         build_animdata(&material->id);
1980         /* material's nodetree */
1981         if (material->nodetree != NULL) {
1982                 build_nodetree(material->nodetree);
1983                 OperationKey ntree_key(&material->nodetree->id,
1984                                        DEG_NODE_TYPE_SHADING,
1985                                        DEG_OPCODE_MATERIAL_UPDATE);
1986                 OperationKey material_key(&material->id,
1987                                           DEG_NODE_TYPE_SHADING,
1988                                           DEG_OPCODE_MATERIAL_UPDATE);
1989                 add_relation(ntree_key, material_key, "Material's NTree");
1990                 build_nested_nodetree(&material->id, material->nodetree);
1991         }
1992 }
1993
1994 /* Recursively build graph for texture */
1995 void DepsgraphRelationBuilder::build_texture(Tex *texture)
1996 {
1997         if (built_map_.checkIsBuiltAndTag(texture)) {
1998                 return;
1999         }
2000         /* texture itself */
2001         build_animdata(&texture->id);
2002         /* texture's nodetree */
2003         build_nodetree(texture->nodetree);
2004         build_nested_nodetree(&texture->id, texture->nodetree);
2005 }
2006
2007 void DepsgraphRelationBuilder::build_compositor(Scene *scene)
2008 {
2009         /* For now, just a plain wrapper? */
2010         build_nodetree(scene->nodetree);
2011 }
2012
2013 void DepsgraphRelationBuilder::build_gpencil(bGPdata *gpd)
2014 {
2015         if (built_map_.checkIsBuiltAndTag(gpd)) {
2016                 return;
2017         }
2018         /* animation */
2019         build_animdata(&gpd->id);
2020
2021         // TODO: parent object (when that feature is implemented)
2022 }
2023
2024 void DepsgraphRelationBuilder::build_cachefile(CacheFile *cache_file)
2025 {
2026         if (built_map_.checkIsBuiltAndTag(cache_file)) {
2027                 return;
2028         }
2029         /* Animation. */
2030         build_animdata(&cache_file->id);
2031 }
2032
2033 void DepsgraphRelationBuilder::build_mask(Mask *mask)
2034 {
2035         if (built_map_.checkIsBuiltAndTag(mask)) {
2036                 return;
2037         }
2038         ID *mask_id = &mask->id;
2039         /* F-Curve animation. */
2040         build_animdata(mask_id);
2041         /* Own mask animation. */
2042         OperationKey mask_animation_key(mask_id,
2043                                         DEG_NODE_TYPE_ANIMATION,
2044                                         DEG_OPCODE_MASK_ANIMATION);
2045         TimeSourceKey time_src_key;
2046         add_relation(time_src_key, mask_animation_key, "TimeSrc -> Mask Animation");
2047         /* Final mask evaluation. */
2048         ComponentKey parameters_key(mask_id, DEG_NODE_TYPE_PARAMETERS);
2049         add_relation(mask_animation_key, parameters_key, "Mask Animation -> Mask Eval");
2050 }
2051
2052 void DepsgraphRelationBuilder::build_movieclip(MovieClip *clip)
2053 {
2054         if (built_map_.checkIsBuiltAndTag(clip)) {
2055                 return;
2056         }
2057         /* Animation. */
2058         build_animdata(&clip->id);
2059 }
2060
2061 void DepsgraphRelationBuilder::build_lightprobe(LightProbe *probe)
2062 {
2063         if (built_map_.checkIsBuiltAndTag(probe)) {
2064                 return;
2065         }
2066         build_animdata(&probe->id);
2067 }
2068
2069 void DepsgraphRelationBuilder::build_copy_on_write_relations()
2070 {
2071         foreach (IDDepsNode *id_node, graph_->id_nodes) {
2072                 build_copy_on_write_relations(id_node);
2073         }
2074 }
2075
2076 /* Nested datablocks (node trees, shape keys) requires special relation to
2077  * ensure owner's datablock remapping happens after node tree itself is ready.
2078  *
2079  * This is similar to what happens in ntree_hack_remap_pointers().
2080  */
2081 void DepsgraphRelationBuilder::build_nested_datablock(ID *owner, ID *id)
2082 {
2083         OperationKey owner_copy_on_write_key(owner,
2084                                              DEG_NODE_TYPE_COPY_ON_WRITE,
2085                                              DEG_OPCODE_COPY_ON_WRITE);
2086         OperationKey id_copy_on_write_key(id,
2087                                           DEG_NODE_TYPE_COPY_ON_WRITE,
2088                                           DEG_OPCODE_COPY_ON_WRITE);
2089         add_relation(id_copy_on_write_key,
2090                      owner_copy_on_write_key,
2091                      "Eval Order");
2092 }
2093
2094 void DepsgraphRelationBuilder::build_nested_nodetree(ID *owner,
2095                                                      bNodeTree *ntree)
2096 {
2097         if (ntree == NULL) {
2098                 return;
2099         }
2100         build_nested_datablock(owner, &ntree->id);
2101 }
2102
2103 void DepsgraphRelationBuilder::build_nested_shapekey(ID *owner, Key *key)
2104 {
2105         if (key == NULL) {
2106                 return;
2107         }
2108         build_nested_datablock(owner, &key->id);
2109 }
2110
2111 void DepsgraphRelationBuilder::build_copy_on_write_relations(IDDepsNode *id_node)
2112 {
2113         ID *id_orig = id_node->id_orig;
2114
2115         TimeSourceKey time_source_key;
2116         OperationKey copy_on_write_key(id_orig,
2117                                        DEG_NODE_TYPE_COPY_ON_WRITE,
2118                                        DEG_OPCODE_COPY_ON_WRITE);
2119         /* XXX: This is a quick hack to make Alt-A to work. */
2120         // add_relation(time_source_key, copy_on_write_key, "Fluxgate capacitor hack");
2121         /* Resat of code is using rather low level trickery, so need to get some
2122          * explicit pointers.
2123          */
2124         DepsNode *node_cow = find_node(copy_on_write_key);
2125         OperationDepsNode *op_cow = node_cow->get_exit_operation();
2126         /* Plug any other components to this one. */
2127         GHASH_FOREACH_BEGIN(ComponentDepsNode *, comp_node, id_node->components)
2128         {
2129                 if (comp_node->type == DEG_NODE_TYPE_COPY_ON_WRITE) {
2130                         /* Copy-on-write component never depends on itself. */
2131                         continue;
2132                 }
2133                 if (!comp_node->depends_on_cow()) {
2134                         /* Component explicitly requests to not add relation. */
2135                         continue;
2136                 }
2137                 int rel_flag = 0;
2138                 if (comp_node->type == DEG_NODE_TYPE_ANIMATION) {
2139                         rel_flag |= DEPSREL_FLAG_NO_FLUSH;
2140                 }
2141                 /* All entry operations of each component should wait for a proper
2142                  * copy of ID.
2143                  */
2144                 OperationDepsNode *op_entry = comp_node->get_entry_operation();
2145                 if (op_entry != NULL) {
2146                         DepsRelation *rel = graph_->add_new_relation(
2147                                 op_cow, op_entry, "CoW Dependency");
2148                         rel->flag |= rel_flag;
2149                 }
2150                 /* All dangling operations should also be executed after copy-on-write. */
2151                 GHASH_FOREACH_BEGIN(OperationDepsNode *, op_node, comp_node->operations_map)
2152                 {
2153                         if (op_node == op_entry) {
2154                                 continue;
2155                         }
2156                         if (op_node->inlinks.size() == 0) {
2157                                 DepsRelation *rel = graph_->add_new_relation(
2158                                         op_cow, op_node, "CoW Dependency");
2159                                 rel->flag |= rel_flag;
2160                         }
2161                         else {
2162                                 bool has_same_comp_dependency = false;
2163                                 foreach (DepsRelation *rel_current, op_node->inlinks) {
2164                                         if (rel_current->from->type != DEG_NODE_TYPE_OPERATION) {
2165                                                 continue;
2166                                         }
2167                                         OperationDepsNode *op_node_from =
2168                                                 (OperationDepsNode *)rel_current->from;
2169                                         if (op_node_from->owner == op_node->owner) {
2170                                                 has_same_comp_dependency = true;
2171                                                 break;
2172                                         }
2173                                 }
2174                                 if (!has_same_comp_dependency) {
2175                                         DepsRelation *rel = graph_->add_new_relation(
2176                                                 op_cow, op_node, "CoW Dependency");
2177                                         rel->flag |= rel_flag;
2178                                 }
2179                         }
2180                 }
2181                 GHASH_FOREACH_END();
2182                 /* NOTE: We currently ignore implicit relations to an external
2183                  * datablocks for copy-on-write operations. This means, for example,
2184                  * copy-on-write component of Object will not wait for copy-on-write
2185                  * component of it's Mesh. This is because pointers are all known
2186                  * already so remapping will happen all correct. And then If some object
2187                  * evaluation step needs geometry, it will have transitive dependency
2188                  * to Mesh copy-on-write already.
2189                  */
2190         }
2191         GHASH_FOREACH_END();
2192         /* TODO(sergey): This solves crash for now, but causes too many
2193          * updates potentially.
2194          */
2195         if (GS(id_orig->name) == ID_OB) {
2196                 Object *object = (Object *)id_orig;
2197                 ID *object_data_id = (ID *)object->data;
2198                 if (object_data_id != NULL) {
2199                         OperationKey data_copy_on_write_key(object_data_id,
2200                                                             DEG_NODE_TYPE_COPY_ON_WRITE,
2201                                                             DEG_OPCODE_COPY_ON_WRITE);
2202                         add_relation(data_copy_on_write_key, copy_on_write_key, "Eval Order");
2203                 }
2204                 else {
2205                         BLI_assert(object->type == OB_EMPTY);
2206                 }
2207         }
2208 }
2209
2210 /* **** ID traversal callbacks functions **** */
2211
2212 void DepsgraphRelationBuilder::modifier_walk(void *user_data,
2213                                              struct Object * /*object*/,
2214                                              struct ID **idpoin,
2215                                              int /*cb_flag*/)
2216 {
2217         BuilderWalkUserData *data = (BuilderWalkUserData *)user_data;
2218         ID *id = *idpoin;
2219         if (id == NULL) {
2220                 return;
2221         }
2222         switch (GS(id->name)) {
2223                 case ID_OB:
2224                         data->builder->build_object(NULL, (Object *)id);
2225                         break;
2226                 case ID_TE:
2227                         data->builder->build_texture((Tex *)id);
2228                         break;
2229                 default:
2230                         /* pass */
2231                         break;
2232         }
2233 }
2234
2235 void DepsgraphRelationBuilder::constraint_walk(bConstraint * /*con*/,
2236                                                ID **idpoin,
2237                                                bool /*is_reference*/,
2238                                                void *user_data)
2239 {
2240         BuilderWalkUserData *data = (BuilderWalkUserData *)user_data;
2241         if (*idpoin) {
2242                 ID *id = *idpoin;
2243                 if (GS(id->name) == ID_OB) {
2244                         data->builder->build_object(NULL, (Object *)id);
2245                 }
2246         }
2247 }
2248
2249 }  // namespace DEG