Recent spinlock commit made scheduling unsafe for threading
[blender.git] / source / blender / blenkernel / intern / depsgraph.c
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) 2004 Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): none yet.
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 /** \file blender/blenkernel/intern/depsgraph.c
27  *  \ingroup bke
28  */
29
30  
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <math.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #ifdef WIN32
39 #  include "BLI_winstuff.h"
40 #endif
41
42 #include "BLI_utildefines.h"
43 #include "BLI_listbase.h"
44 #include "BLI_ghash.h"
45 #include "BLI_threads.h"
46
47 #include "DNA_anim_types.h"
48 #include "DNA_camera_types.h"
49 #include "DNA_group_types.h"
50 #include "DNA_lamp_types.h"
51 #include "DNA_lattice_types.h"
52 #include "DNA_key_types.h"
53 #include "DNA_material_types.h"
54 #include "DNA_mesh_types.h"
55 #include "DNA_node_types.h"
56 #include "DNA_scene_types.h"
57 #include "DNA_screen_types.h"
58 #include "DNA_windowmanager_types.h"
59 #include "DNA_movieclip_types.h"
60 #include "DNA_mask_types.h"
61
62 #include "BKE_animsys.h"
63 #include "BKE_action.h"
64 #include "BKE_effect.h"
65 #include "BKE_fcurve.h"
66 #include "BKE_global.h"
67 #include "BKE_group.h"
68 #include "BKE_key.h"
69 #include "BKE_library.h"
70 #include "BKE_main.h"
71 #include "BKE_node.h"
72 #include "BKE_material.h"
73 #include "BKE_mball.h"
74 #include "BKE_modifier.h"
75 #include "BKE_object.h"
76 #include "BKE_particle.h"
77 #include "BKE_pointcache.h"
78 #include "BKE_scene.h"
79 #include "BKE_screen.h"
80 #include "BKE_tracking.h"
81
82 #include "atomic_ops.h"
83
84 #include "depsgraph_private.h"
85  
86 /* Queue and stack operations for dag traversal 
87  *
88  * the queue store a list of freenodes to avoid successive alloc/dealloc
89  */
90
91 DagNodeQueue *queue_create(int slots)
92 {
93         DagNodeQueue *queue;
94         DagNodeQueueElem *elem;
95         int i;
96         
97         queue = MEM_mallocN(sizeof(DagNodeQueue), "DAG queue");
98         queue->freenodes = MEM_mallocN(sizeof(DagNodeQueue), "DAG queue");
99         queue->count = 0;
100         queue->maxlevel = 0;
101         queue->first = queue->last = NULL;
102         elem = MEM_mallocN(sizeof(DagNodeQueueElem), "DAG queue elem3");
103         elem->node = NULL;
104         elem->next = NULL;
105         queue->freenodes->first = queue->freenodes->last = elem;
106         
107         for (i = 1; i < slots; i++) {
108                 elem = MEM_mallocN(sizeof(DagNodeQueueElem), "DAG queue elem4");
109                 elem->node = NULL;
110                 elem->next = NULL;
111                 queue->freenodes->last->next = elem;
112                 queue->freenodes->last = elem;
113         }
114         queue->freenodes->count = slots;
115         return queue;
116 }
117
118 void queue_raz(DagNodeQueue *queue)
119 {
120         DagNodeQueueElem *elem;
121         
122         elem = queue->first;
123         if (queue->freenodes->last)
124                 queue->freenodes->last->next = elem;
125         else
126                 queue->freenodes->first = queue->freenodes->last = elem;
127         
128         elem->node = NULL;
129         queue->freenodes->count++;
130         while (elem->next) {
131                 elem = elem->next;
132                 elem->node = NULL;
133                 queue->freenodes->count++;
134         }
135         queue->freenodes->last = elem;
136         queue->count = 0;
137 }
138
139 void queue_delete(DagNodeQueue *queue)
140 {
141         DagNodeQueueElem *elem;
142         DagNodeQueueElem *temp;
143         
144         elem = queue->first;
145         while (elem) {
146                 temp = elem;
147                 elem = elem->next;
148                 MEM_freeN(temp);
149         }
150         
151         elem = queue->freenodes->first;
152         while (elem) {
153                 temp = elem;
154                 elem = elem->next;
155                 MEM_freeN(temp);
156         }
157         
158         MEM_freeN(queue->freenodes);
159         MEM_freeN(queue);
160 }
161
162 /* insert in queue, remove in front */
163 void push_queue(DagNodeQueue *queue, DagNode *node)
164 {
165         DagNodeQueueElem *elem;
166         int i;
167
168         if (node == NULL) {
169                 fprintf(stderr, "pushing null node\n");
170                 return;
171         }
172         /*fprintf(stderr, "BFS push : %s %d\n", ((ID *) node->ob)->name, queue->count);*/
173
174         elem = queue->freenodes->first;
175         if (elem != NULL) {
176                 queue->freenodes->first = elem->next;
177                 if (queue->freenodes->last == elem) {
178                         queue->freenodes->last = NULL;
179                         queue->freenodes->first = NULL;
180                 }
181                 queue->freenodes->count--;
182         }
183         else { /* alllocating more */
184                 elem = MEM_mallocN(sizeof(DagNodeQueueElem), "DAG queue elem1");
185                 elem->node = NULL;
186                 elem->next = NULL;
187                 queue->freenodes->first = queue->freenodes->last = elem;
188
189                 for (i = 1; i < DAGQUEUEALLOC; i++) {
190                         elem = MEM_mallocN(sizeof(DagNodeQueueElem), "DAG queue elem2");
191                         elem->node = NULL;
192                         elem->next = NULL;
193                         queue->freenodes->last->next = elem;
194                         queue->freenodes->last = elem;
195                 }
196                 queue->freenodes->count = DAGQUEUEALLOC;
197                         
198                 elem = queue->freenodes->first;
199                 queue->freenodes->first = elem->next;
200         }
201         elem->next = NULL;
202         elem->node = node;
203         if (queue->last != NULL)
204                 queue->last->next = elem;
205         queue->last = elem;
206         if (queue->first == NULL) {
207                 queue->first = elem;
208         }
209         queue->count++;
210 }
211
212
213 /* insert in front, remove in front */
214 void push_stack(DagNodeQueue *queue, DagNode *node)
215 {
216         DagNodeQueueElem *elem;
217         int i;
218
219         elem = queue->freenodes->first;
220         if (elem != NULL) {
221                 queue->freenodes->first = elem->next;
222                 if (queue->freenodes->last == elem) {
223                         queue->freenodes->last = NULL;
224                         queue->freenodes->first = NULL;
225                 }
226                 queue->freenodes->count--;
227         }
228         else { /* alllocating more */
229                 elem = MEM_mallocN(sizeof(DagNodeQueueElem), "DAG queue elem1");
230                 elem->node = NULL;
231                 elem->next = NULL;
232                 queue->freenodes->first = queue->freenodes->last = elem;
233
234                 for (i = 1; i < DAGQUEUEALLOC; i++) {
235                         elem = MEM_mallocN(sizeof(DagNodeQueueElem), "DAG queue elem2");
236                         elem->node = NULL;
237                         elem->next = NULL;
238                         queue->freenodes->last->next = elem;
239                         queue->freenodes->last = elem;
240                 }
241                 queue->freenodes->count = DAGQUEUEALLOC;
242                         
243                 elem = queue->freenodes->first;
244                 queue->freenodes->first = elem->next;
245         }
246         elem->next = queue->first;
247         elem->node = node;
248         queue->first = elem;
249         if (queue->last == NULL)
250                 queue->last = elem;
251         queue->count++;
252 }
253
254
255 DagNode *pop_queue(DagNodeQueue *queue)
256 {
257         DagNodeQueueElem *elem;
258         DagNode *node;
259
260         elem = queue->first;
261         if (elem) {
262                 queue->first = elem->next;
263                 if (queue->last == elem) {
264                         queue->last = NULL;
265                         queue->first = NULL;
266                 }
267                 queue->count--;
268                 if (queue->freenodes->last)
269                         queue->freenodes->last->next = elem;
270                 queue->freenodes->last = elem;
271                 if (queue->freenodes->first == NULL)
272                         queue->freenodes->first = elem;
273                 node = elem->node;
274                 elem->node = NULL;
275                 elem->next = NULL;
276                 queue->freenodes->count++;
277                 return node;
278         }
279         else {
280                 fprintf(stderr, "return null\n");
281                 return NULL;
282         }
283 }
284
285 DagNode *get_top_node_queue(DagNodeQueue *queue)
286 {
287         return queue->first->node;
288 }
289
290 DagForest *dag_init(void)
291 {
292         DagForest *forest;
293         /* use callocN to init all zero */
294         forest = MEM_callocN(sizeof(DagForest), "DAG root");
295         return forest;
296 }
297
298 /* isdata = object data... */
299 /* XXX this needs to be extended to be more flexible (so that not only objects are evaluated via depsgraph)... */
300 static void dag_add_driver_relation(AnimData *adt, DagForest *dag, DagNode *node, int isdata)
301 {
302         FCurve *fcu;
303         DagNode *node1;
304         
305         for (fcu = adt->drivers.first; fcu; fcu = fcu->next) {
306                 ChannelDriver *driver = fcu->driver;
307                 DriverVar *dvar;
308                 int isdata_fcu = (isdata) || (fcu->rna_path && strstr(fcu->rna_path, "modifiers["));
309                 
310                 /* loop over variables to get the target relationships */
311                 for (dvar = driver->variables.first; dvar; dvar = dvar->next) {
312                         /* only used targets */
313                         DRIVER_TARGETS_USED_LOOPER(dvar) 
314                         {
315                                 if (dtar->id) {
316                                         /* FIXME: other data types need to be added here so that they can work! */
317                                         if (GS(dtar->id->name) == ID_OB) {
318                                                 Object *ob = (Object *)dtar->id;
319                                                 
320                                                 /* normal channel-drives-channel */
321                                                 node1 = dag_get_node(dag, dtar->id);
322                                                 
323                                                 /* check if bone... */
324                                                 if ((ob->type == OB_ARMATURE) &&
325                                                     ( ((dtar->rna_path) && strstr(dtar->rna_path, "pose.bones[")) ||
326                                                       ((dtar->flag & DTAR_FLAG_STRUCT_REF) && (dtar->pchan_name[0])) ))
327                                                 {
328                                                         dag_add_relation(dag, node1, node, isdata_fcu ? DAG_RL_DATA_DATA : DAG_RL_DATA_OB, "Driver");
329                                                 }
330                                                 /* check if ob data */
331                                                 else if (dtar->rna_path && strstr(dtar->rna_path, "data."))
332                                                         dag_add_relation(dag, node1, node, isdata_fcu ? DAG_RL_DATA_DATA : DAG_RL_DATA_OB, "Driver");
333                                                 /* normal */
334                                                 else
335                                                         dag_add_relation(dag, node1, node, isdata_fcu ? DAG_RL_OB_DATA : DAG_RL_OB_OB, "Driver");
336                                         }
337                                 }
338                         }
339                         DRIVER_TARGETS_LOOPER_END
340                 }
341         }
342 }
343
344 /* XXX: forward def for material driver handling... */
345 static void dag_add_material_driver_relations(DagForest *dag, DagNode *node, Material *ma);
346
347 /* recursive handling for shader nodetree drivers */
348 static void dag_add_shader_nodetree_driver_relations(DagForest *dag, DagNode *node, bNodeTree *ntree)
349 {
350         bNode *n;
351
352         /* nodetree itself */
353         if (ntree->adt) {
354                 dag_add_driver_relation(ntree->adt, dag, node, 1);
355         }
356         
357         /* nodetree's nodes... */
358         for (n = ntree->nodes.first; n; n = n->next) {
359                 if (n->id) {
360                         if (GS(n->id->name) == ID_MA) {
361                                 dag_add_material_driver_relations(dag, node, (Material *)n->id);
362                         }
363                         else if (n->type == NODE_GROUP) {
364                                 dag_add_shader_nodetree_driver_relations(dag, node, (bNodeTree *)n->id);
365                         }
366                 }
367         }
368 }
369
370 /* recursive handling for material drivers */
371 static void dag_add_material_driver_relations(DagForest *dag, DagNode *node, Material *ma)
372 {
373         /* Prevent infinite recursion by checking (and tagging the material) as having been visited 
374          * already (see build_dag()). This assumes ma->id.flag & LIB_DOIT isn't set by anything else
375          * in the meantime... [#32017]
376          */
377         if (ma->id.flag & LIB_DOIT)
378                 return;
379
380         ma->id.flag |= LIB_DOIT;
381         
382         /* material itself */
383         if (ma->adt)
384                 dag_add_driver_relation(ma->adt, dag, node, 1);
385
386         /* textures */
387         // TODO...
388         //dag_add_texture_driver_relations(DagForest *dag, DagNode *node, ID *id);
389
390         /* material's nodetree */
391         if (ma->nodetree)
392                 dag_add_shader_nodetree_driver_relations(dag, node, ma->nodetree);
393
394         ma->id.flag &= ~LIB_DOIT;
395 }
396
397 /* recursive handling for lamp drivers */
398 static void dag_add_lamp_driver_relations(DagForest *dag, DagNode *node, Lamp *la)
399 {
400         /* Prevent infinite recursion by checking (and tagging the lamp) as having been visited 
401          * already (see build_dag()). This assumes la->id.flag & LIB_DOIT isn't set by anything else
402          * in the meantime... [#32017]
403          */
404         if (la->id.flag & LIB_DOIT)
405                 return;
406
407         la->id.flag |= LIB_DOIT;
408         
409         /* lamp itself */
410         if (la->adt)
411                 dag_add_driver_relation(la->adt, dag, node, 1);
412
413         /* textures */
414         // TODO...
415         //dag_add_texture_driver_relations(DagForest *dag, DagNode *node, ID *id);
416
417         /* lamp's nodetree */
418         if (la->nodetree)
419                 dag_add_shader_nodetree_driver_relations(dag, node, la->nodetree);
420
421         la->id.flag &= ~LIB_DOIT;
422 }
423
424 static void dag_add_collision_field_relation(DagForest *dag, Scene *scene, Object *ob, DagNode *node, int skip_forcefield, bool no_collision)
425 {
426         Base *base;
427         DagNode *node2;
428
429         /* would be nice to have a list of colliders here
430          * so for now walk all objects in scene check 'same layer rule' */
431         for (base = scene->base.first; base; base = base->next) {
432                 if ((base->lay & ob->lay) && base->object->pd) {
433                         Object *ob1 = base->object;
434                         if ((ob1->pd->deflect || ob1->pd->forcefield) && (ob1 != ob)) {
435                                 if ((skip_forcefield && ob1->pd->forcefield == skip_forcefield) || (no_collision && ob1->pd->forcefield == 0))
436                                         continue;
437                                 node2 = dag_get_node(dag, ob1);
438                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Field Collision");
439                         }
440                 }
441         }
442 }
443
444 static void build_dag_object(DagForest *dag, DagNode *scenenode, Scene *scene, Object *ob, int mask)
445 {
446         bConstraint *con;
447         DagNode *node;
448         DagNode *node2;
449         DagNode *node3;
450         Key *key;
451         ParticleSystem *psys;
452         int addtoroot = 1;
453         
454         node = dag_get_node(dag, ob);
455         
456         if ((ob->data) && (mask & DAG_RL_DATA)) {
457                 node2 = dag_get_node(dag, ob->data);
458                 dag_add_relation(dag, node, node2, DAG_RL_DATA, "Object-Data Relation");
459                 node2->first_ancestor = ob;
460                 node2->ancestor_count += 1;
461         }
462
463         /* also build a custom data mask for dependencies that need certain layers */
464         node->customdata_mask = 0;
465         
466         if (ob->type == OB_ARMATURE) {
467                 if (ob->pose) {
468                         bPoseChannel *pchan;
469                         
470                         for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) {
471                                 for (con = pchan->constraints.first; con; con = con->next) {
472                                         bConstraintTypeInfo *cti = BKE_constraint_get_typeinfo(con);
473                                         ListBase targets = {NULL, NULL};
474                                         bConstraintTarget *ct;
475                                         
476                                         if (cti && cti->get_constraint_targets) {
477                                                 cti->get_constraint_targets(con, &targets);
478                                                 
479                                                 for (ct = targets.first; ct; ct = ct->next) {
480                                                         if (ct->tar && ct->tar != ob) {
481                                                                 // fprintf(stderr, "armature %s target :%s\n", ob->id.name, target->id.name);
482                                                                 node3 = dag_get_node(dag, ct->tar);
483                                                                 
484                                                                 if (ct->subtarget[0]) {
485                                                                         dag_add_relation(dag, node3, node, DAG_RL_OB_DATA | DAG_RL_DATA_DATA, cti->name);
486                                                                         if (ct->tar->type == OB_MESH)
487                                                                                 node3->customdata_mask |= CD_MASK_MDEFORMVERT;
488                                                                 }
489                                                                 else if (ELEM3(con->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO, CONSTRAINT_TYPE_SPLINEIK))
490                                                                         dag_add_relation(dag, node3, node, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, cti->name);
491                                                                 else
492                                                                         dag_add_relation(dag, node3, node, DAG_RL_OB_DATA, cti->name);
493                                                         }
494                                                 }
495                                                 
496                                                 if (cti->flush_constraint_targets)
497                                                         cti->flush_constraint_targets(con, &targets, 1);
498                                         }
499                                         
500                                 }
501                         }
502                 }
503         }
504         
505         /* driver dependencies, nla modifiers */
506 #if 0 // XXX old animation system
507         if (ob->nlastrips.first) {
508                 bActionStrip *strip;
509                 bActionChannel *chan;
510                 for (strip = ob->nlastrips.first; strip; strip = strip->next) {
511                         if (strip->modifiers.first) {
512                                 bActionModifier *amod;
513                                 for (amod = strip->modifiers.first; amod; amod = amod->next) {
514                                         if (amod->ob) {
515                                                 node2 = dag_get_node(dag, amod->ob);
516                                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "NLA Strip Modifier");
517                                         }
518                                 }
519                         }
520                 }
521         }
522 #endif // XXX old animation system
523         if (ob->adt)
524                 dag_add_driver_relation(ob->adt, dag, node, (ob->type == OB_ARMATURE));  // XXX isdata arg here doesn't give an accurate picture of situation
525                 
526         key = BKE_key_from_object(ob);
527         if (key && key->adt)
528                 dag_add_driver_relation(key->adt, dag, node, 1);
529
530         if (ob->modifiers.first) {
531                 ModifierData *md;
532                 
533                 for (md = ob->modifiers.first; md; md = md->next) {
534                         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
535                         
536                         if (mti->updateDepgraph) mti->updateDepgraph(md, dag, scene, ob, node);
537                 }
538         }
539         if (ob->parent) {
540                 node2 = dag_get_node(dag, ob->parent);
541                 
542                 switch (ob->partype) {
543                         case PARSKEL:
544                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_OB, "Parent");
545                                 break;
546                         case PARVERT1: case PARVERT3:
547                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_OB | DAG_RL_OB_OB, "Vertex Parent");
548                                 node2->customdata_mask |= CD_MASK_ORIGINDEX;
549                                 break;
550                         case PARBONE:
551                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_OB | DAG_RL_OB_OB, "Bone Parent");
552                                 break;
553                         default:
554                                 if (ob->parent->type == OB_LATTICE)
555                                         dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_OB, "Lattice Parent");
556                                 else if (ob->parent->type == OB_CURVE) {
557                                         Curve *cu = ob->parent->data;
558                                         if (cu->flag & CU_PATH) 
559                                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_OB | DAG_RL_OB_OB, "Curve Parent");
560                                         else
561                                                 dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Curve Parent");
562                                 }
563                                 else
564                                         dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Parent");
565                                 break;
566                 }
567                 /* exception case: parent is duplivert */
568                 if (ob->type == OB_MBALL && (ob->parent->transflag & OB_DUPLIVERTS)) {
569                         dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_OB, "Duplivert");
570                 }
571                 
572                 addtoroot = 0;
573         }
574         if (ob->proxy) {
575                 node2 = dag_get_node(dag, ob->proxy);
576                 dag_add_relation(dag, node, node2, DAG_RL_DATA_DATA | DAG_RL_OB_OB, "Proxy");
577                 /* inverted relation, so addtoroot shouldn't be set to zero */
578         }
579         
580         if (ob->transflag & OB_DUPLI) {
581                 if ((ob->transflag & OB_DUPLIGROUP) && ob->dup_group) {
582                         GroupObject *go;
583                         for (go = ob->dup_group->gobject.first; go; go = go->next) {
584                                 if (go->ob) {
585                                         node2 = dag_get_node(dag, go->ob);
586                                         /* node2 changes node1, this keeps animations updated in groups?? not logical? */
587                                         dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Dupligroup");
588                                 }
589                         }
590                 }
591         }
592
593         /* softbody collision  */
594         if ((ob->type == OB_MESH) || (ob->type == OB_CURVE) || (ob->type == OB_LATTICE)) {
595                 if (ob->particlesystem.first ||
596                     modifiers_isModifierEnabled(ob, eModifierType_Softbody) ||
597                     modifiers_isModifierEnabled(ob, eModifierType_Cloth) ||
598                     modifiers_isModifierEnabled(ob, eModifierType_DynamicPaint))
599                 {
600                         dag_add_collision_field_relation(dag, scene, ob, node, 0, false);  /* TODO: use effectorweight->group */
601                 }
602                 else if (modifiers_isModifierEnabled(ob, eModifierType_Smoke)) {
603                         dag_add_collision_field_relation(dag, scene, ob, node, PFIELD_SMOKEFLOW, false);
604                 }
605                 else if (ob->rigidbody_object) {
606                         dag_add_collision_field_relation(dag, scene, ob, node, 0, true);
607                 }
608         }
609         
610         /* object data drivers */
611         if (ob->data) {
612                 AnimData *adt = BKE_animdata_from_id((ID *)ob->data);
613                 if (adt)
614                         dag_add_driver_relation(adt, dag, node, 1);
615         }
616         
617         /* object type/data relationships */
618         switch (ob->type) {
619                 case OB_CAMERA:
620                 {
621                         Camera *cam = (Camera *)ob->data;
622                         
623                         if (cam->dof_ob) {
624                                 node2 = dag_get_node(dag, cam->dof_ob);
625                                 dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Camera DoF");
626                         }
627                         break;
628                 }
629                 case OB_MBALL: 
630                 {
631                         Object *mom = BKE_mball_basis_find(scene, ob);
632                         
633                         if (mom != ob) {
634                                 node2 = dag_get_node(dag, mom);
635                                 dag_add_relation(dag, node, node2, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Metaball");  /* mom depends on children! */
636                         }
637                         break;
638                 }
639                 case OB_CURVE:
640                 case OB_FONT:
641                 {
642                         Curve *cu = ob->data;
643                         
644                         if (cu->bevobj) {
645                                 node2 = dag_get_node(dag, cu->bevobj);
646                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Curve Bevel");
647                         }
648                         if (cu->taperobj) {
649                                 node2 = dag_get_node(dag, cu->taperobj);
650                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Curve Taper");
651                         }
652                         if (ob->type == OB_FONT) {
653                                 if (cu->textoncurve) {
654                                         node2 = dag_get_node(dag, cu->textoncurve);
655                                         dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Texture On Curve");
656                                 }
657                         }
658                         break;
659                 }
660         }
661         
662         /* material drivers */
663         if (ob->totcol) {
664                 int a;
665                 
666                 for (a = 1; a <= ob->totcol; a++) {
667                         Material *ma = give_current_material(ob, a);
668                         
669                         if (ma) {
670                                 /* recursively figure out if there are drivers, and hook these up to this object */
671                                 dag_add_material_driver_relations(dag, node, ma);
672                         }
673                 }
674         }
675         else if (ob->type == OB_LAMP) {
676                 dag_add_lamp_driver_relations(dag, node, ob->data);
677         }
678         
679         /* particles */
680         psys = ob->particlesystem.first;
681         if (psys) {
682                 GroupObject *go;
683
684                 for (; psys; psys = psys->next) {
685                         BoidRule *rule = NULL;
686                         BoidState *state = NULL;
687                         ParticleSettings *part = psys->part;
688                         ListBase *effectors = NULL;
689                         EffectorCache *eff;
690
691                         dag_add_relation(dag, node, node, DAG_RL_OB_DATA, "Particle-Object Relation");
692
693                         if (!psys_check_enabled(ob, psys))
694                                 continue;
695
696                         if (ELEM(part->phystype, PART_PHYS_KEYED, PART_PHYS_BOIDS)) {
697                                 ParticleTarget *pt = psys->targets.first;
698
699                                 for (; pt; pt = pt->next) {
700                                         if (pt->ob && BLI_findlink(&pt->ob->particlesystem, pt->psys - 1)) {
701                                                 node2 = dag_get_node(dag, pt->ob);
702                                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Particle Targets");
703                                         }
704                                 }
705                         }
706
707                         if (part->ren_as == PART_DRAW_OB && part->dup_ob) {
708                                 node2 = dag_get_node(dag, part->dup_ob);
709                                 /* note that this relation actually runs in the wrong direction, the problem
710                                  * is that dupli system all have this (due to parenting), and the render
711                                  * engine instancing assumes particular ordering of objects in list */
712                                 dag_add_relation(dag, node, node2, DAG_RL_OB_OB, "Particle Object Visualization");
713                                 if (part->dup_ob->type == OB_MBALL)
714                                         dag_add_relation(dag, node, node2, DAG_RL_DATA_DATA, "Particle Object Visualization");
715                         }
716
717                         if (part->ren_as == PART_DRAW_GR && part->dup_group) {
718                                 for (go = part->dup_group->gobject.first; go; go = go->next) {
719                                         node2 = dag_get_node(dag, go->ob);
720                                         dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Particle Group Visualization");
721                                 }
722                         }
723
724                         effectors = pdInitEffectors(scene, ob, psys, part->effector_weights);
725
726                         if (effectors) {
727                                 for (eff = effectors->first; eff; eff = eff->next) {
728                                         if (eff->psys) {
729                                                 node2 = dag_get_node(dag, eff->ob);
730                                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Particle Field");
731                                         }
732                                 }
733                         }
734
735                         pdEndEffectors(&effectors);
736
737                         if (part->boids) {
738                                 for (state = part->boids->states.first; state; state = state->next) {
739                                         for (rule = state->rules.first; rule; rule = rule->next) {
740                                                 Object *ruleob = NULL;
741                                                 if (rule->type == eBoidRuleType_Avoid)
742                                                         ruleob = ((BoidRuleGoalAvoid *)rule)->ob;
743                                                 else if (rule->type == eBoidRuleType_FollowLeader)
744                                                         ruleob = ((BoidRuleFollowLeader *)rule)->ob;
745
746                                                 if (ruleob) {
747                                                         node2 = dag_get_node(dag, ruleob);
748                                                         dag_add_relation(dag, node2, node, DAG_RL_OB_DATA, "Boid Rule");
749                                                 }
750                                         }
751                                 }
752                         }
753                 }
754         }
755         
756         /* object constraints */
757         for (con = ob->constraints.first; con; con = con->next) {
758                 bConstraintTypeInfo *cti = BKE_constraint_get_typeinfo(con);
759                 ListBase targets = {NULL, NULL};
760                 bConstraintTarget *ct;
761                 
762                 if (!cti)
763                         continue;
764
765                 /* special case for camera tracking -- it doesn't use targets to define relations */
766                 if (ELEM3(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER, CONSTRAINT_TYPE_OBJECTSOLVER)) {
767                         int depends_on_camera = 0;
768
769                         if (cti->type == CONSTRAINT_TYPE_FOLLOWTRACK) {
770                                 bFollowTrackConstraint *data = (bFollowTrackConstraint *)con->data;
771
772                                 if ((data->clip || data->flag & FOLLOWTRACK_ACTIVECLIP) && data->track[0])
773                                         depends_on_camera = 1;
774
775                                 if (data->depth_ob) {
776                                         node2 = dag_get_node(dag, data->depth_ob);
777                                         dag_add_relation(dag, node2, node, DAG_RL_DATA_OB | DAG_RL_OB_OB, cti->name);
778                                 }
779                         }
780                         else if (cti->type == CONSTRAINT_TYPE_OBJECTSOLVER)
781                                 depends_on_camera = 1;
782
783                         if (depends_on_camera && scene->camera) {
784                                 node2 = dag_get_node(dag, scene->camera);
785                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_OB | DAG_RL_OB_OB, cti->name);
786                         }
787
788                         dag_add_relation(dag, scenenode, node, DAG_RL_SCENE, "Scene Relation");
789                         addtoroot = 0;
790                 }
791                 else if (cti->get_constraint_targets) {
792                         cti->get_constraint_targets(con, &targets);
793                         
794                         for (ct = targets.first; ct; ct = ct->next) {
795                                 Object *obt;
796                                 
797                                 if (ct->tar)
798                                         obt = ct->tar;
799                                 else
800                                         continue;
801                                 
802                                 node2 = dag_get_node(dag, obt);
803                                 if (ELEM(con->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO))
804                                         dag_add_relation(dag, node2, node, DAG_RL_DATA_OB | DAG_RL_OB_OB, cti->name);
805                                 else {
806                                         if (ELEM3(obt->type, OB_ARMATURE, OB_MESH, OB_LATTICE) && (ct->subtarget[0])) {
807                                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_OB | DAG_RL_OB_OB, cti->name);
808                                                 if (obt->type == OB_MESH)
809                                                         node2->customdata_mask |= CD_MASK_MDEFORMVERT;
810                                         }
811                                         else
812                                                 dag_add_relation(dag, node2, node, DAG_RL_OB_OB, cti->name);
813                                 }
814                                 addtoroot = 0;
815                         }
816                         
817                         if (cti->flush_constraint_targets)
818                                 cti->flush_constraint_targets(con, &targets, 1);
819                 }
820         }
821
822         if (addtoroot == 1)
823                 dag_add_relation(dag, scenenode, node, DAG_RL_SCENE, "Scene Relation");
824 }
825
826 DagForest *build_dag(Main *bmain, Scene *sce, short mask)
827 {
828         Base *base;
829         Object *ob;
830         Group *group;
831         GroupObject *go;
832         DagNode *node;
833         DagNode *scenenode;
834         DagForest *dag;
835         DagAdjList *itA;
836
837         dag = sce->theDag;
838         if (dag)
839                 free_forest(dag);
840         else {
841                 dag = dag_init();
842                 sce->theDag = dag;
843         }
844         
845         /* clear "LIB_DOIT" flag from all materials, to prevent infinite recursion problems later [#32017] */
846         tag_main_idcode(bmain, ID_MA, FALSE);
847         tag_main_idcode(bmain, ID_LA, FALSE);
848         
849         /* add base node for scene. scene is always the first node in DAG */
850         scenenode = dag_add_node(dag, sce);
851         
852         /* add current scene objects */
853         for (base = sce->base.first; base; base = base->next) {
854                 ob = base->object;
855                 
856                 build_dag_object(dag, scenenode, sce, ob, mask);
857                 if (ob->proxy)
858                         build_dag_object(dag, scenenode, sce, ob->proxy, mask);
859                 
860                 /* handled in next loop */
861                 if (ob->dup_group) 
862                         ob->dup_group->id.flag |= LIB_DOIT;
863         }
864         
865         /* add groups used in current scene objects */
866         for (group = bmain->group.first; group; group = group->id.next) {
867                 if (group->id.flag & LIB_DOIT) {
868                         for (go = group->gobject.first; go; go = go->next) {
869                                 build_dag_object(dag, scenenode, sce, go->ob, mask);
870                         }
871                         group->id.flag &= ~LIB_DOIT;
872                 }
873         }
874         
875         /* Now all relations were built, but we need to solve 1 exceptional case;
876          * When objects have multiple "parents" (for example parent + constraint working on same object)
877          * the relation type has to be synced. One of the parents can change, and should give same event to child */
878         
879         /* nodes were callocced, so we can use node->color for temporal storage */
880         for (node = sce->theDag->DagNode.first; node; node = node->next) {
881                 if (node->type == ID_OB) {
882                         for (itA = node->child; itA; itA = itA->next) {
883                                 if (itA->node->type == ID_OB) {
884                                         itA->node->color |= itA->type;
885                                 }
886                         }
887
888                         /* also flush custom data mask */
889                         ((Object *)node->ob)->customdata_mask = node->customdata_mask;
890                 }
891         }
892         /* now set relations equal, so that when only one parent changes, the correct recalcs are found */
893         for (node = sce->theDag->DagNode.first; node; node = node->next) {
894                 if (node->type == ID_OB) {
895                         for (itA = node->child; itA; itA = itA->next) {
896                                 if (itA->node->type == ID_OB) {
897                                         itA->type |= itA->node->color;
898                                 }
899                         }
900                 }
901         }
902         
903         /* cycle detection and solving */
904         // solve_cycles(dag);
905         
906         return dag;
907 }
908
909
910 void free_forest(DagForest *Dag) 
911 {  /* remove all nodes and deps */
912         DagNode *tempN;
913         DagAdjList *tempA;
914         DagAdjList *itA;
915         DagNode *itN = Dag->DagNode.first;
916         
917         while (itN) {
918                 itA = itN->child;
919                 while (itA) {
920                         tempA = itA;
921                         itA = itA->next;
922                         MEM_freeN(tempA);
923                 }
924                 
925                 itA = itN->parent;
926                 while (itA) {
927                         tempA = itA;
928                         itA = itA->next;
929                         MEM_freeN(tempA);
930                 }
931                 
932                 tempN = itN;
933                 itN = itN->next;
934                 MEM_freeN(tempN);
935         }
936
937         BLI_ghash_free(Dag->nodeHash, NULL, NULL);
938         Dag->nodeHash = NULL;
939         Dag->DagNode.first = NULL;
940         Dag->DagNode.last = NULL;
941         Dag->numNodes = 0;
942
943 }
944
945 DagNode *dag_find_node(DagForest *forest, void *fob)
946 {
947         if (forest->nodeHash)
948                 return BLI_ghash_lookup(forest->nodeHash, fob);
949
950         return NULL;
951 }
952
953 static int ugly_hack_sorry = 1;         /* prevent type check */
954 static int dag_print_dependencies = 0;  /* debugging */
955
956 /* no checking of existence, use dag_find_node first or dag_get_node */
957 DagNode *dag_add_node(DagForest *forest, void *fob)
958 {
959         DagNode *node;
960                 
961         node = MEM_callocN(sizeof(DagNode), "DAG node");
962         if (node) {
963                 node->ob = fob;
964                 node->color = DAG_WHITE;
965
966                 if (ugly_hack_sorry) node->type = GS(((ID *) fob)->name);  /* sorry, done for pose sorting */
967                 if (forest->numNodes) {
968                         ((DagNode *) forest->DagNode.last)->next = node;
969                         forest->DagNode.last = node;
970                         forest->numNodes++;
971                 }
972                 else {
973                         forest->DagNode.last = node;
974                         forest->DagNode.first = node;
975                         forest->numNodes = 1;
976                 }
977
978                 if (!forest->nodeHash)
979                         forest->nodeHash = BLI_ghash_ptr_new("dag_add_node gh");
980                 BLI_ghash_insert(forest->nodeHash, fob, node);
981         }
982
983         return node;
984 }
985
986 DagNode *dag_get_node(DagForest *forest, void *fob)
987 {
988         DagNode *node;
989         
990         node = dag_find_node(forest, fob);
991         if (!node) 
992                 node = dag_add_node(forest, fob);
993         return node;
994 }
995
996
997
998 DagNode *dag_get_sub_node(DagForest *forest, void *fob)
999 {
1000         DagNode *node;
1001         DagAdjList *mainchild, *prev = NULL;
1002         
1003         mainchild = ((DagNode *) forest->DagNode.first)->child;
1004         /* remove from first node (scene) adj list if present */
1005         while (mainchild) {
1006                 if (mainchild->node == fob) {
1007                         if (prev) {
1008                                 prev->next = mainchild->next;
1009                                 MEM_freeN(mainchild);
1010                                 break;
1011                         }
1012                         else {
1013                                 ((DagNode *) forest->DagNode.first)->child = mainchild->next;
1014                                 MEM_freeN(mainchild);
1015                                 break;
1016                         }
1017                 }
1018                 prev = mainchild;
1019                 mainchild = mainchild->next;
1020         }
1021         node = dag_find_node(forest, fob);
1022         if (!node) 
1023                 node = dag_add_node(forest, fob);
1024         return node;
1025 }
1026
1027 static void dag_add_parent_relation(DagForest *UNUSED(forest), DagNode *fob1, DagNode *fob2, short rel, const char *name) 
1028 {
1029         DagAdjList *itA = fob2->parent;
1030         
1031         while (itA) { /* search if relation exist already */
1032                 if (itA->node == fob1) {
1033                         itA->type |= rel;
1034                         itA->count += 1;
1035                         return;
1036                 }
1037                 itA = itA->next;
1038         }
1039         /* create new relation and insert at head. MALLOC alert! */
1040         itA = MEM_mallocN(sizeof(DagAdjList), "DAG adj list");
1041         itA->node = fob1;
1042         itA->type = rel;
1043         itA->count = 1;
1044         itA->next = fob2->parent;
1045         itA->name = name;
1046         fob2->parent = itA;
1047 }
1048
1049 void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, short rel, const char *name) 
1050 {
1051         DagAdjList *itA = fob1->child;
1052         
1053         /* parent relation is for cycle checking */
1054         dag_add_parent_relation(forest, fob1, fob2, rel, name);
1055
1056         while (itA) { /* search if relation exist already */
1057                 if (itA->node == fob2) {
1058                         itA->type |= rel;
1059                         itA->count += 1;
1060                         return;
1061                 }
1062                 itA = itA->next;
1063         }
1064         /* create new relation and insert at head. MALLOC alert! */
1065         itA = MEM_mallocN(sizeof(DagAdjList), "DAG adj list");
1066         itA->node = fob2;
1067         itA->type = rel;
1068         itA->count = 1;
1069         itA->next = fob1->child;
1070         itA->name = name;
1071         fob1->child = itA;
1072 }
1073
1074 static const char *dag_node_name(DagNode *node)
1075 {
1076         if (node->ob == NULL)
1077                 return "null";
1078         else if (ugly_hack_sorry)
1079                 return ((ID *)(node->ob))->name + 2;
1080         else
1081                 return ((bPoseChannel *)(node->ob))->name;
1082 }
1083
1084 static void dag_node_print_dependencies(DagNode *node)
1085 {
1086         DagAdjList *itA;
1087
1088         printf("%s depends on:\n", dag_node_name(node));
1089
1090         for (itA = node->parent; itA; itA = itA->next)
1091                 printf("  %s through %s\n", dag_node_name(itA->node), itA->name);
1092         printf("\n");
1093 }
1094
1095 static int dag_node_print_dependency_recurs(DagNode *node, DagNode *endnode)
1096 {
1097         DagAdjList *itA;
1098
1099         if (node->color == DAG_BLACK)
1100                 return 0;
1101
1102         node->color = DAG_BLACK;
1103
1104         if (node == endnode)
1105                 return 1;
1106
1107         for (itA = node->parent; itA; itA = itA->next) {
1108                 if (dag_node_print_dependency_recurs(itA->node, endnode)) {
1109                         printf("  %s depends on %s through %s.\n", dag_node_name(node), dag_node_name(itA->node), itA->name);
1110                         return 1;
1111                 }
1112         }
1113
1114         return 0;
1115 }
1116
1117 static void dag_node_print_dependency_cycle(DagForest *dag, DagNode *startnode, DagNode *endnode, const char *name)
1118 {
1119         DagNode *node;
1120
1121         for (node = dag->DagNode.first; node; node = node->next)
1122                 node->color = DAG_WHITE;
1123
1124         printf("  %s depends on %s through %s.\n", dag_node_name(endnode), dag_node_name(startnode), name);
1125         dag_node_print_dependency_recurs(startnode, endnode);
1126         printf("\n");
1127 }
1128
1129 static int dag_node_recurs_level(DagNode *node, int level)
1130 {
1131         DagAdjList *itA;
1132         int newlevel;
1133
1134         node->color = DAG_BLACK; /* done */
1135         newlevel = ++level;
1136         
1137         for (itA = node->parent; itA; itA = itA->next) {
1138                 if (itA->node->color == DAG_WHITE) {
1139                         itA->node->ancestor_count = dag_node_recurs_level(itA->node, level);
1140                         newlevel = MAX2(newlevel, level + itA->node->ancestor_count);
1141                 }
1142                 else
1143                         newlevel = MAX2(newlevel, level + itA->node->ancestor_count);
1144         }
1145         
1146         return newlevel;
1147 }
1148
1149 static void dag_check_cycle(DagForest *dag)
1150 {
1151         DagNode *node;
1152         DagAdjList *itA;
1153
1154         /* debugging print */
1155         if (dag_print_dependencies)
1156                 for (node = dag->DagNode.first; node; node = node->next)
1157                         dag_node_print_dependencies(node);
1158
1159         /* tag nodes unchecked */
1160         for (node = dag->DagNode.first; node; node = node->next)
1161                 node->color = DAG_WHITE;
1162         
1163         for (node = dag->DagNode.first; node; node = node->next) {
1164                 if (node->color == DAG_WHITE) {
1165                         node->ancestor_count = dag_node_recurs_level(node, 0);
1166                 }
1167         }
1168         
1169         /* check relations, and print errors */
1170         for (node = dag->DagNode.first; node; node = node->next) {
1171                 for (itA = node->parent; itA; itA = itA->next) {
1172                         if (itA->node->ancestor_count > node->ancestor_count) {
1173                                 if (node->ob && itA->node->ob) {
1174                                         printf("Dependency cycle detected:\n");
1175                                         dag_node_print_dependency_cycle(dag, itA->node, node, itA->name);
1176                                 }
1177                         }
1178                 }
1179         }
1180
1181         /* parent relations are only needed for cycle checking, so free now */
1182         for (node = dag->DagNode.first; node; node = node->next) {
1183                 while (node->parent) {
1184                         itA = node->parent->next;
1185                         MEM_freeN(node->parent);
1186                         node->parent = itA;
1187                 }
1188         }
1189 }
1190
1191 /* debug test functions */
1192
1193 void graph_print_queue(DagNodeQueue *nqueue)
1194 {       
1195         DagNodeQueueElem *queueElem;
1196         
1197         queueElem = nqueue->first;
1198         while (queueElem) {
1199                 fprintf(stderr, "** %s %i %i-%i ", ((ID *) queueElem->node->ob)->name, queueElem->node->color, queueElem->node->DFS_dvtm, queueElem->node->DFS_fntm);
1200                 queueElem = queueElem->next;
1201         }
1202         fprintf(stderr, "\n");
1203 }
1204
1205 void graph_print_queue_dist(DagNodeQueue *nqueue)
1206 {       
1207         DagNodeQueueElem *queueElem;
1208         int count;
1209         
1210         queueElem = nqueue->first;
1211         count = 0;
1212         while (queueElem) {
1213                 fprintf(stderr, "** %25s %2.2i-%2.2i ", ((ID *) queueElem->node->ob)->name, queueElem->node->DFS_dvtm, queueElem->node->DFS_fntm);
1214                 while (count < queueElem->node->DFS_dvtm - 1) { fputc(' ', stderr); count++; }
1215                 fputc('|', stderr);
1216                 while (count < queueElem->node->DFS_fntm - 2) { fputc('-', stderr); count++; }
1217                 fputc('|', stderr);
1218                 fputc('\n', stderr);
1219                 count = 0;
1220                 queueElem = queueElem->next;
1221         }
1222         fprintf(stderr, "\n");
1223 }
1224
1225 void graph_print_adj_list(DagForest *dag)
1226 {
1227         DagNode *node;
1228         DagAdjList *itA;
1229         
1230         node = dag->DagNode.first;
1231         while (node) {
1232                 fprintf(stderr, "node : %s col: %i", ((ID *) node->ob)->name, node->color);
1233                 itA = node->child;
1234                 while (itA) {
1235                         fprintf(stderr, "-- %s ", ((ID *) itA->node->ob)->name);
1236                         
1237                         itA = itA->next;
1238                 }
1239                 fprintf(stderr, "\n");
1240                 node = node->next;
1241         }
1242 }
1243
1244 /* ************************ API *********************** */
1245
1246 /* mechanism to allow editors to be informed of depsgraph updates,
1247  * to do their own updates based on changes... */
1248 static void (*EditorsUpdateIDCb)(Main *bmain, ID *id) = NULL;
1249 static void (*EditorsUpdateSceneCb)(Main *bmain, Scene *scene, int updated) = NULL;
1250
1251 void DAG_editors_update_cb(void (*id_func)(Main *bmain, ID *id), void (*scene_func)(Main *bmain, Scene *scene, int updated))
1252 {
1253         EditorsUpdateIDCb = id_func;
1254         EditorsUpdateSceneCb = scene_func;
1255 }
1256
1257 static void dag_editors_id_update(Main *bmain, ID *id)
1258 {
1259         if (EditorsUpdateIDCb)
1260                 EditorsUpdateIDCb(bmain, id);
1261 }
1262
1263 static void dag_editors_scene_update(Main *bmain, Scene *scene, int updated)
1264 {
1265         if (EditorsUpdateSceneCb)
1266                 EditorsUpdateSceneCb(bmain, scene, updated);
1267 }
1268
1269 /* groups with objects in this scene need to be put in the right order as well */
1270 static void scene_sort_groups(Main *bmain, Scene *sce)
1271 {
1272         Base *base;
1273         Group *group;
1274         GroupObject *go;
1275         Object *ob;
1276         
1277         /* test; are group objects all in this scene? */
1278         for (ob = bmain->object.first; ob; ob = ob->id.next) {
1279                 ob->id.flag &= ~LIB_DOIT;
1280                 ob->id.newid = NULL; /* newid abuse for GroupObject */
1281         }
1282         for (base = sce->base.first; base; base = base->next)
1283                 base->object->id.flag |= LIB_DOIT;
1284         
1285         for (group = bmain->group.first; group; group = group->id.next) {
1286                 for (go = group->gobject.first; go; go = go->next) {
1287                         if ((go->ob->id.flag & LIB_DOIT) == 0)
1288                                 break;
1289                 }
1290                 /* this group is entirely in this scene */
1291                 if (go == NULL) {
1292                         ListBase listb = {NULL, NULL};
1293                         
1294                         for (go = group->gobject.first; go; go = go->next)
1295                                 go->ob->id.newid = (ID *)go;
1296                         
1297                         /* in order of sorted bases we reinsert group objects */
1298                         for (base = sce->base.first; base; base = base->next) {
1299                                 
1300                                 if (base->object->id.newid) {
1301                                         go = (GroupObject *)base->object->id.newid;
1302                                         base->object->id.newid = NULL;
1303                                         BLI_remlink(&group->gobject, go);
1304                                         BLI_addtail(&listb, go);
1305                                 }
1306                         }
1307                         /* copy the newly sorted listbase */
1308                         group->gobject = listb;
1309                 }
1310         }
1311 }
1312
1313 /* free the depency graph */
1314 static void dag_scene_free(Scene *sce)
1315 {
1316         if (sce->theDag) {
1317                 free_forest(sce->theDag);
1318                 MEM_freeN(sce->theDag);
1319                 sce->theDag = NULL;
1320         }
1321 }
1322
1323 /* sort the base list on dependency order */
1324 static void dag_scene_build(Main *bmain, Scene *sce)
1325 {
1326         DagNode *node, *rootnode;
1327         DagNodeQueue *nqueue;
1328         DagAdjList *itA;
1329         int time;
1330         int skip = 0;
1331         ListBase tempbase;
1332         Base *base;
1333
1334         tempbase.first = tempbase.last = NULL;
1335         
1336         build_dag(bmain, sce, DAG_RL_ALL_BUT_DATA);
1337         
1338         dag_check_cycle(sce->theDag);
1339
1340         nqueue = queue_create(DAGQUEUEALLOC);
1341         
1342         for (node = sce->theDag->DagNode.first; node; node = node->next) {
1343                 node->color = DAG_WHITE;
1344         }
1345         
1346         time = 1;
1347         
1348         rootnode = sce->theDag->DagNode.first;
1349         rootnode->color = DAG_GRAY;
1350         time++;
1351         push_stack(nqueue, rootnode);
1352         
1353         while (nqueue->count) {
1354                 
1355                 skip = 0;
1356                 node = get_top_node_queue(nqueue);
1357                 
1358                 itA = node->child;
1359                 while (itA != NULL) {
1360                         if (itA->node->color == DAG_WHITE) {
1361                                 itA->node->DFS_dvtm = time;
1362                                 itA->node->color = DAG_GRAY;
1363                                 
1364                                 time++;
1365                                 push_stack(nqueue, itA->node);
1366                                 skip = 1;
1367                                 break;
1368                         }
1369                         itA = itA->next;
1370                 }
1371                 
1372                 if (!skip) {
1373                         if (node) {
1374                                 node = pop_queue(nqueue);
1375                                 if (node->ob == sce)  /* we are done */
1376                                         break;
1377                                 node->color = DAG_BLACK;
1378                                 
1379                                 time++;
1380                                 base = sce->base.first;
1381                                 while (base && base->object != node->ob)
1382                                         base = base->next;
1383                                 if (base) {
1384                                         BLI_remlink(&sce->base, base);
1385                                         BLI_addhead(&tempbase, base);
1386                                 }
1387                         }
1388                 }
1389         }
1390         
1391         /* temporal correction for circular dependencies */
1392         base = sce->base.first;
1393         while (base) {
1394                 BLI_remlink(&sce->base, base);
1395                 BLI_addhead(&tempbase, base);
1396                 //if (G.debug & G_DEBUG)
1397                 printf("cyclic %s\n", base->object->id.name);
1398                 base = sce->base.first;
1399         }
1400         
1401         sce->base = tempbase;
1402         queue_delete(nqueue);
1403         
1404         /* all groups with objects in this scene gets resorted too */
1405         scene_sort_groups(bmain, sce);
1406         
1407         if (G.debug & G_DEBUG) {
1408                 printf("\nordered\n");
1409                 for (base = sce->base.first; base; base = base->next) {
1410                         printf(" %s\n", base->object->id.name);
1411                 }
1412         }
1413
1414         /* temporal...? */
1415         sce->recalc |= SCE_PRV_CHANGED; /* test for 3d preview */
1416 }
1417
1418 /* clear all dependency graphs */
1419 void DAG_relations_tag_update(Main *bmain)
1420 {
1421         Scene *sce;
1422
1423         for (sce = bmain->scene.first; sce; sce = sce->id.next)
1424                 dag_scene_free(sce);
1425 }
1426
1427 /* rebuild dependency graph only for a given scene */
1428 void DAG_scene_relations_rebuild(Main *bmain, Scene *sce)
1429 {
1430         dag_scene_free(sce);
1431         DAG_scene_relations_update(bmain, sce);
1432 }
1433
1434 /* create dependency graph if it was cleared or didn't exist yet */
1435 void DAG_scene_relations_update(Main *bmain, Scene *sce)
1436 {
1437         if (!sce->theDag)
1438                 dag_scene_build(bmain, sce);
1439 }
1440
1441 void DAG_scene_free(Scene *sce)
1442 {
1443         if (sce->theDag) {
1444                 free_forest(sce->theDag);
1445                 MEM_freeN(sce->theDag);
1446                 sce->theDag = NULL;
1447         }
1448 }
1449
1450 static void lib_id_recalc_tag(Main *bmain, ID *id)
1451 {
1452         id->flag |= LIB_ID_RECALC;
1453         DAG_id_type_tag(bmain, GS(id->name));
1454 }
1455
1456 static void lib_id_recalc_data_tag(Main *bmain, ID *id)
1457 {
1458         id->flag |= LIB_ID_RECALC_DATA;
1459         DAG_id_type_tag(bmain, GS(id->name));
1460 }
1461
1462 /* node was checked to have lasttime != curtime and is if type ID_OB */
1463 static void flush_update_node(Main *bmain, DagNode *node, unsigned int layer, int curtime)
1464 {
1465         DagAdjList *itA;
1466         Object *ob, *obc;
1467         int oldflag, changed = 0;
1468         unsigned int all_layer;
1469         
1470         node->lasttime = curtime;
1471         
1472         ob = node->ob;
1473         if (ob && (ob->recalc & OB_RECALC_ALL)) {
1474                 all_layer = node->scelay;
1475
1476                 /* got an object node that changes, now check relations */
1477                 for (itA = node->child; itA; itA = itA->next) {
1478                         all_layer |= itA->lay;
1479                         /* the relationship is visible */
1480                         if ((itA->lay & layer)) { // XXX || (itA->node->ob == obedit)
1481                                 if (itA->node->type == ID_OB) {
1482                                         obc = itA->node->ob;
1483                                         oldflag = obc->recalc;
1484                                         
1485                                         /* got a ob->obc relation, now check if flag needs flush */
1486                                         if (ob->recalc & OB_RECALC_OB) {
1487                                                 if (itA->type & DAG_RL_OB_OB) {
1488                                                         //printf("ob %s changes ob %s\n", ob->id.name, obc->id.name);
1489                                                         obc->recalc |= OB_RECALC_OB;
1490                                                         lib_id_recalc_tag(bmain, &obc->id);
1491                                                 }
1492                                                 if (itA->type & DAG_RL_OB_DATA) {
1493                                                         //printf("ob %s changes obdata %s\n", ob->id.name, obc->id.name);
1494                                                         obc->recalc |= OB_RECALC_DATA;
1495                                                         lib_id_recalc_data_tag(bmain, &obc->id);
1496                                                 }
1497                                         }
1498                                         if (ob->recalc & OB_RECALC_DATA) {
1499                                                 if (itA->type & DAG_RL_DATA_OB) {
1500                                                         //printf("obdata %s changes ob %s\n", ob->id.name, obc->id.name);
1501                                                         obc->recalc |= OB_RECALC_OB;
1502                                                         lib_id_recalc_tag(bmain, &obc->id);
1503                                                 }
1504                                                 if (itA->type & DAG_RL_DATA_DATA) {
1505                                                         //printf("obdata %s changes obdata %s\n", ob->id.name, obc->id.name);
1506                                                         obc->recalc |= OB_RECALC_DATA;
1507                                                         lib_id_recalc_data_tag(bmain, &obc->id);
1508                                                 }
1509                                         }
1510                                         if (oldflag != obc->recalc) changed = 1;
1511                                 }
1512                         }
1513                 }
1514                 /* even nicer, we can clear recalc flags...  */
1515                 if ((all_layer & layer) == 0) { // XXX && (ob != obedit)) {
1516                         /* but existing displaylists or derivedmesh should be freed */
1517                         if (ob->recalc & OB_RECALC_DATA)
1518                                 BKE_object_free_derived_caches(ob);
1519                         
1520                         ob->recalc &= ~OB_RECALC_ALL;
1521                 }
1522         }
1523         
1524         /* check case where child changes and parent forcing obdata to change */
1525         /* should be done regardless if this ob has recalc set */
1526         /* could merge this in with loop above...? (ton) */
1527         for (itA = node->child; itA; itA = itA->next) {
1528                 /* the relationship is visible */
1529                 if ((itA->lay & layer)) {       // XXX  || (itA->node->ob == obedit)
1530                         if (itA->node->type == ID_OB) {
1531                                 obc = itA->node->ob;
1532                                 /* child moves */
1533                                 if ((obc->recalc & OB_RECALC_ALL) == OB_RECALC_OB) {
1534                                         /* parent has deforming info */
1535                                         if (itA->type & (DAG_RL_OB_DATA | DAG_RL_DATA_DATA)) {
1536                                                 // printf("parent %s changes ob %s\n", ob->id.name, obc->id.name);
1537                                                 obc->recalc |= OB_RECALC_DATA;
1538                                                 lib_id_recalc_data_tag(bmain, &obc->id);
1539                                         }
1540                                 }
1541                         }
1542                 }
1543         }
1544         
1545         /* we only go deeper if node not checked or something changed  */
1546         for (itA = node->child; itA; itA = itA->next) {
1547                 if (changed || itA->node->lasttime != curtime)
1548                         flush_update_node(bmain, itA->node, layer, curtime);
1549         }
1550         
1551 }
1552
1553 /* node was checked to have lasttime != curtime, and is of type ID_OB */
1554 static unsigned int flush_layer_node(Scene *sce, DagNode *node, int curtime)
1555 {
1556         DagAdjList *itA;
1557         
1558         node->lasttime = curtime;
1559         node->lay = node->scelay;
1560         
1561         for (itA = node->child; itA; itA = itA->next) {
1562                 if (itA->node->type == ID_OB) {
1563                         if (itA->node->lasttime != curtime) {
1564                                 itA->lay = flush_layer_node(sce, itA->node, curtime);  /* lay is only set once for each relation */
1565                         }
1566                         else {
1567                                 itA->lay = itA->node->lay;
1568                         }
1569                         
1570                         node->lay |= itA->lay;
1571                 }
1572         }
1573
1574         return node->lay;
1575 }
1576
1577 /* node was checked to have lasttime != curtime, and is of type ID_OB */
1578 static void flush_pointcache_reset(Main *bmain, Scene *scene, DagNode *node, int curtime, int reset)
1579 {
1580         DagAdjList *itA;
1581         Object *ob;
1582         
1583         node->lasttime = curtime;
1584         
1585         for (itA = node->child; itA; itA = itA->next) {
1586                 if (itA->node->type == ID_OB) {
1587                         if (itA->node->lasttime != curtime) {
1588                                 ob = (Object *)(itA->node->ob);
1589
1590                                 if (reset || (ob->recalc & OB_RECALC_ALL)) {
1591                                         if (BKE_ptcache_object_reset(scene, ob, PTCACHE_RESET_DEPSGRAPH)) {
1592                                                 ob->recalc |= OB_RECALC_DATA;
1593                                                 lib_id_recalc_data_tag(bmain, &ob->id);
1594                                         }
1595
1596                                         flush_pointcache_reset(bmain, scene, itA->node, curtime, 1);
1597                                 }
1598                                 else
1599                                         flush_pointcache_reset(bmain, scene, itA->node, curtime, 0);
1600                         }
1601                 }
1602         }
1603 }
1604
1605 /* flush layer flags to dependencies */
1606 static void dag_scene_flush_layers(Scene *sce, int lay)
1607 {
1608         DagNode *node, *firstnode;
1609         DagAdjList *itA;
1610         Base *base;
1611         int lasttime;
1612
1613         firstnode = sce->theDag->DagNode.first;  /* always scene node */
1614
1615         for (itA = firstnode->child; itA; itA = itA->next)
1616                 itA->lay = 0;
1617
1618         sce->theDag->time++;  /* so we know which nodes were accessed */
1619         lasttime = sce->theDag->time;
1620
1621         /* update layer flags in nodes */
1622         for (base = sce->base.first; base; base = base->next) {
1623                 node = dag_get_node(sce->theDag, base->object);
1624                 node->scelay = base->object->lay;
1625         }
1626
1627         /* ensure cameras are set as if they are on a visible layer, because
1628          * they ared still used for rendering or setting the camera view
1629          *
1630          * XXX, this wont work for local view / unlocked camera's */
1631         if (sce->camera) {
1632                 node = dag_get_node(sce->theDag, sce->camera);
1633                 node->scelay |= lay;
1634         }
1635
1636 #ifdef DURIAN_CAMERA_SWITCH
1637         {
1638                 TimeMarker *m;
1639
1640                 for (m = sce->markers.first; m; m = m->next) {
1641                         if (m->camera) {
1642                                 node = dag_get_node(sce->theDag, m->camera);
1643                                 node->scelay |= lay;
1644                         }
1645                 }
1646         }
1647 #endif
1648
1649         /* flush layer nodes to dependencies */
1650         for (itA = firstnode->child; itA; itA = itA->next)
1651                 if (itA->node->lasttime != lasttime && itA->node->type == ID_OB)
1652                         flush_layer_node(sce, itA->node, lasttime);
1653 }
1654
1655 static void dag_tag_renderlayers(Scene *sce, unsigned int lay)
1656 {
1657         if (sce->nodetree) {
1658                 bNode *node;
1659                 Base *base;
1660                 unsigned int lay_changed = 0;
1661                 
1662                 for (base = sce->base.first; base; base = base->next)
1663                         if (base->lay & lay)
1664                                 if (base->object->recalc)
1665                                         lay_changed |= base->lay;
1666                         
1667                 for (node = sce->nodetree->nodes.first; node; node = node->next) {
1668                         if (node->id == (ID *)sce) {
1669                                 SceneRenderLayer *srl = BLI_findlink(&sce->r.layers, node->custom1);
1670                                 if (srl && (srl->lay & lay_changed))
1671                                         nodeUpdate(sce->nodetree, node);
1672                         }
1673                 }
1674         }
1675 }
1676
1677 /* flushes all recalc flags in objects down the dependency tree */
1678 void DAG_scene_flush_update(Main *bmain, Scene *sce, unsigned int lay, const short time)
1679 {
1680         DagNode *firstnode;
1681         DagAdjList *itA;
1682         Object *ob;
1683         int lasttime;
1684         
1685         if (sce->theDag == NULL) {
1686                 printf("DAG zero... not allowed to happen!\n");
1687                 DAG_scene_relations_update(bmain, sce);
1688         }
1689         
1690         firstnode = sce->theDag->DagNode.first;  /* always scene node */
1691
1692         /* first we flush the layer flags */
1693         dag_scene_flush_layers(sce, lay);
1694
1695         /* then we use the relationships + layer info to flush update events */
1696         sce->theDag->time++;  /* so we know which nodes were accessed */
1697         lasttime = sce->theDag->time;
1698         for (itA = firstnode->child; itA; itA = itA->next)
1699                 if (itA->node->lasttime != lasttime && itA->node->type == ID_OB)
1700                         flush_update_node(bmain, itA->node, lay, lasttime);
1701
1702         /* if update is not due to time change, do pointcache clears */
1703         if (!time) {
1704                 sce->theDag->time++;  /* so we know which nodes were accessed */
1705                 lasttime = sce->theDag->time;
1706                 for (itA = firstnode->child; itA; itA = itA->next) {
1707                         if (itA->node->lasttime != lasttime && itA->node->type == ID_OB) {
1708                                 ob = (Object *)(itA->node->ob);
1709
1710                                 if (ob->recalc & OB_RECALC_ALL) {
1711                                         if (BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH)) {
1712                                                 ob->recalc |= OB_RECALC_DATA;
1713                                                 lib_id_recalc_data_tag(bmain, &ob->id);
1714                                         }
1715
1716                                         flush_pointcache_reset(bmain, sce, itA->node, lasttime, 1);
1717                                 }
1718                                 else
1719                                         flush_pointcache_reset(bmain, sce, itA->node, lasttime, 0);
1720                         }
1721                 }
1722         }
1723         
1724         dag_tag_renderlayers(sce, lay);
1725 }
1726
1727 static int object_modifiers_use_time(Object *ob)
1728 {
1729         ModifierData *md;
1730         
1731         /* check if a modifier in modifier stack needs time input */
1732         for (md = ob->modifiers.first; md; md = md->next)
1733                 if (modifier_dependsOnTime(md))
1734                         return 1;
1735         
1736         /* check whether any modifiers are animated */
1737         if (ob->adt) {
1738                 AnimData *adt = ob->adt;
1739                 FCurve *fcu;
1740                 
1741                 /* action - check for F-Curves with paths containing 'modifiers[' */
1742                 if (adt->action) {
1743                         for (fcu = adt->action->curves.first; fcu; fcu = fcu->next) {
1744                                 if (fcu->rna_path && strstr(fcu->rna_path, "modifiers["))
1745                                         return 1;
1746                         }
1747                 }
1748                 
1749                 /* This here allows modifier properties to get driven and still update properly
1750                  *
1751                  * Workaround to get [#26764] (e.g. subsurf levels not updating when animated/driven)
1752                  * working, without the updating problems ([#28525] [#28690] [#28774] [#28777]) caused
1753                  * by the RNA updates cache introduced in r.38649
1754                  */
1755                 for (fcu = adt->drivers.first; fcu; fcu = fcu->next) {
1756                         if (fcu->rna_path && strstr(fcu->rna_path, "modifiers["))
1757                                 return 1;
1758                 }
1759                 
1760                 /* XXX: also, should check NLA strips, though for now assume that nobody uses
1761                  * that and we can omit that for performance reasons... */
1762         }
1763         
1764         return 0;
1765 }
1766
1767 static short animdata_use_time(AnimData *adt)
1768 {
1769         NlaTrack *nlt;
1770         
1771         if (adt == NULL) return 0;
1772         
1773         /* check action - only if assigned, and it has anim curves */
1774         if (adt->action && adt->action->curves.first)
1775                 return 1;
1776         
1777         /* check NLA tracks + strips */
1778         for (nlt = adt->nla_tracks.first; nlt; nlt = nlt->next) {
1779                 if (nlt->strips.first)
1780                         return 1;
1781         }
1782         
1783         /* If we have drivers, more likely than not, on a frame change
1784          * they'll need updating because their owner changed
1785          * 
1786          * This is kindof a hack to get around a whole host of problems
1787          * involving drivers using non-object datablock data (which the 
1788          * depsgraph currently has no way of representing let alone correctly
1789          * dependency sort+tagging). By doing this, at least we ensure that 
1790          * some commonly attempted drivers (such as scene -> current frame;
1791          * see "Driver updates fail" thread on Bf-committers dated July 2)
1792          * will work correctly, and that other non-object datablocks will have
1793          * their drivers update at least on frame change.
1794          *
1795          * -- Aligorith, July 4 2011
1796          */
1797         if (adt->drivers.first)
1798                 return 1;
1799         
1800         return 0;
1801 }
1802
1803 static void dag_object_time_update_flags(Main *bmain, Scene *scene, Object *ob)
1804 {
1805         if (ob->constraints.first) {
1806                 bConstraint *con;
1807                 for (con = ob->constraints.first; con; con = con->next) {
1808                         bConstraintTypeInfo *cti = BKE_constraint_get_typeinfo(con);
1809                         ListBase targets = {NULL, NULL};
1810                         bConstraintTarget *ct;
1811                         
1812                         if (cti) {
1813                                 /* special case for camera tracking -- it doesn't use targets to define relations */
1814                                 if (ELEM3(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER, CONSTRAINT_TYPE_OBJECTSOLVER)) {
1815                                         ob->recalc |= OB_RECALC_OB;
1816                                 }
1817                                 else if (cti->get_constraint_targets) {
1818                                         cti->get_constraint_targets(con, &targets);
1819                                         
1820                                         for (ct = targets.first; ct; ct = ct->next) {
1821                                                 if (ct->tar) {
1822                                                         ob->recalc |= OB_RECALC_OB;
1823                                                         break;
1824                                                 }
1825                                         }
1826                                         
1827                                         if (cti->flush_constraint_targets)
1828                                                 cti->flush_constraint_targets(con, &targets, 1);
1829                                 }
1830                                 
1831                         }
1832                 }
1833         }
1834         
1835         if (ob->parent) {
1836                 /* motion path or bone child */
1837                 if (ob->parent->type == OB_CURVE || ob->parent->type == OB_ARMATURE) ob->recalc |= OB_RECALC_OB;
1838         }
1839         
1840 #if 0 // XXX old animation system
1841         if (ob->nlastrips.first) {
1842                 if (ob->dup_group) {
1843                         bActionStrip *strip;
1844                         /* this case is for groups with nla, whilst nla target has no action or nla */
1845                         for (strip = ob->nlastrips.first; strip; strip = strip->next) {
1846                                 if (strip->object)
1847                                         strip->object->recalc |= OB_RECALC_ALL;
1848                         }
1849                 }
1850         }
1851 #endif // XXX old animation system
1852         
1853         if (animdata_use_time(ob->adt)) {
1854                 ob->recalc |= OB_RECALC_OB;
1855                 ob->adt->recalc |= ADT_RECALC_ANIM;
1856         }
1857         
1858         if ((ob->adt) && (ob->type == OB_ARMATURE)) ob->recalc |= OB_RECALC_DATA;
1859         
1860         if (object_modifiers_use_time(ob)) ob->recalc |= OB_RECALC_DATA;
1861         if ((ob->pose) && (ob->pose->flag & POSE_CONSTRAINTS_TIMEDEPEND)) ob->recalc |= OB_RECALC_DATA;
1862         
1863         // XXX: scene here may not be the scene that contains the rigidbody world affecting this!
1864         if (ob->rigidbody_object && BKE_scene_check_rigidbody_active(scene))
1865                 ob->recalc |= OB_RECALC_OB;
1866         
1867         {
1868                 AnimData *adt = BKE_animdata_from_id((ID *)ob->data);
1869                 Mesh *me;
1870                 Curve *cu;
1871                 Lattice *lt;
1872                 
1873                 switch (ob->type) {
1874                         case OB_MESH:
1875                                 me = ob->data;
1876                                 if (me->key) {
1877                                         if (!(ob->shapeflag & OB_SHAPE_LOCK)) {
1878                                                 ob->recalc |= OB_RECALC_DATA;
1879                                         }
1880                                 }
1881                                 if (ob->particlesystem.first)
1882                                         ob->recalc |= OB_RECALC_DATA;
1883                                 break;
1884                         case OB_CURVE:
1885                         case OB_SURF:
1886                                 cu = ob->data;
1887                                 if (cu->key) {
1888                                         if (!(ob->shapeflag & OB_SHAPE_LOCK)) {
1889                                                 ob->recalc |= OB_RECALC_DATA;
1890                                         }
1891                                 }
1892                                 break;
1893                         case OB_FONT:
1894                                 cu = ob->data;
1895                                 if (cu->nurb.first == NULL && cu->str && cu->vfont)
1896                                         ob->recalc |= OB_RECALC_DATA;
1897                                 break;
1898                         case OB_LATTICE:
1899                                 lt = ob->data;
1900                                 if (lt->key) {
1901                                         if (!(ob->shapeflag & OB_SHAPE_LOCK)) {
1902                                                 ob->recalc |= OB_RECALC_DATA;
1903                                         }
1904                                 }
1905                                 break;
1906                         case OB_MBALL:
1907                                 if (ob->transflag & OB_DUPLI) ob->recalc |= OB_RECALC_DATA;
1908                                 break;
1909                 }
1910                 
1911                 if (animdata_use_time(adt)) {
1912                         ob->recalc |= OB_RECALC_DATA;
1913                         adt->recalc |= ADT_RECALC_ANIM;
1914                 }
1915
1916                 if (ob->particlesystem.first) {
1917                         ParticleSystem *psys = ob->particlesystem.first;
1918
1919                         for (; psys; psys = psys->next) {
1920                                 if (psys_check_enabled(ob, psys)) {
1921                                         ob->recalc |= OB_RECALC_DATA;
1922                                         break;
1923                                 }
1924                         }
1925                 }
1926         }
1927
1928         if (ob->recalc & OB_RECALC_OB)
1929                 lib_id_recalc_tag(bmain, &ob->id);
1930         if (ob->recalc & OB_RECALC_DATA)
1931                 lib_id_recalc_data_tag(bmain, &ob->id);
1932
1933 }
1934 /* flag all objects that need recalc, for changes in time for example */
1935 /* do_time: make this optional because undo resets objects to their animated locations without this */
1936 void DAG_scene_update_flags(Main *bmain, Scene *scene, unsigned int lay, const short do_time)
1937 {
1938         Base *base;
1939         Object *ob;
1940         Group *group;
1941         GroupObject *go;
1942         Scene *sce_iter;
1943
1944         /* set ob flags where animated systems are */
1945         for (SETLOOPER(scene, sce_iter, base)) {
1946                 ob = base->object;
1947
1948                 if (do_time) {
1949                         /* now if DagNode were part of base, the node->lay could be checked... */
1950                         /* we do all now, since the scene_flush checks layers and clears recalc flags even */
1951                         
1952                         /* NOTE: "sce_iter" not "scene" so that rigidbodies in background scenes work 
1953                          * (i.e. muting + rbw availability can be checked and tagged properly) [#33970] 
1954                          */
1955                         dag_object_time_update_flags(bmain, sce_iter, ob);
1956                 }
1957
1958                 /* handled in next loop */
1959                 if (ob->dup_group)
1960                         ob->dup_group->id.flag |= LIB_DOIT;
1961         }
1962
1963         if (do_time) {
1964                 /* we do groups each once */
1965                 for (group = bmain->group.first; group; group = group->id.next) {
1966                         if (group->id.flag & LIB_DOIT) {
1967                                 for (go = group->gobject.first; go; go = go->next) {
1968                                         dag_object_time_update_flags(bmain, scene, go->ob);
1969                                 }
1970                         }
1971                 }
1972         }
1973
1974         for (sce_iter = scene; sce_iter; sce_iter = sce_iter->set)
1975                 DAG_scene_flush_update(bmain, sce_iter, lay, 1);
1976         
1977         if (do_time) {
1978                 /* test: set time flag, to disable baked systems to update */
1979                 for (SETLOOPER(scene, sce_iter, base)) {
1980                         ob = base->object;
1981                         if (ob->recalc)
1982                                 ob->recalc |= OB_RECALC_TIME;
1983                 }
1984
1985                 /* hrmf... an exception to look at once, for invisible camera object we do it over */
1986                 if (scene->camera)
1987                         dag_object_time_update_flags(bmain, scene, scene->camera);
1988         }
1989
1990         /* and store the info in groupobject */
1991         for (group = bmain->group.first; group; group = group->id.next) {
1992                 if (group->id.flag & LIB_DOIT) {
1993                         for (go = group->gobject.first; go; go = go->next) {
1994                                 go->recalc = go->ob->recalc;
1995                                 // printf("ob %s recalc %d\n", go->ob->id.name, go->recalc);
1996                         }
1997                         group->id.flag &= ~LIB_DOIT;
1998                 }
1999         }
2000         
2001 }
2002
2003 /* struct returned by DagSceneLayer */
2004 typedef struct DagSceneLayer {
2005         struct DagSceneLayer *next, *prev;
2006         Scene *scene;
2007         unsigned int layer;
2008 } DagSceneLayer;
2009
2010 /* returns visible scenes with valid DAG */
2011 static void dag_current_scene_layers(Main *bmain, ListBase *lb)
2012 {
2013         wmWindowManager *wm;
2014         wmWindow *win;
2015         
2016         lb->first = lb->last = NULL;
2017
2018         /* if we have a windowmanager, look into windows */
2019         if ((wm = bmain->wm.first)) {
2020                 
2021                 flag_listbase_ids(&bmain->scene, LIB_DOIT, 1);
2022
2023                 for (win = wm->windows.first; win; win = win->next) {
2024                         if (win->screen && win->screen->scene->theDag) {
2025                                 Scene *scene = win->screen->scene;
2026                                 
2027                                 if (scene->id.flag & LIB_DOIT) {
2028                                         DagSceneLayer *dsl = MEM_mallocN(sizeof(DagSceneLayer), "dag scene layer");
2029                                         
2030                                         BLI_addtail(lb, dsl);
2031                                         
2032                                         dsl->scene = scene;
2033                                         dsl->layer = BKE_screen_visible_layers(win->screen, scene);
2034                                         
2035                                         scene->id.flag &= ~LIB_DOIT;
2036                                 }
2037                         }
2038                 }
2039         }
2040         else {
2041                 /* if not, use the first sce */
2042                 DagSceneLayer *dsl = MEM_mallocN(sizeof(DagSceneLayer), "dag scene layer");
2043                 
2044                 BLI_addtail(lb, dsl);
2045                 
2046                 dsl->scene = bmain->scene.first;
2047                 dsl->layer = dsl->scene->lay;
2048
2049                 /* XXX for background mode, we should get the scene
2050                  * from somewhere, for the -S option, but it's in
2051                  * the context, how to get it here? */
2052         }
2053 }
2054
2055 void DAG_on_visible_update(Main *bmain, const short do_time)
2056 {
2057         ListBase listbase;
2058         DagSceneLayer *dsl;
2059         
2060         /* get list of visible scenes and layers */
2061         dag_current_scene_layers(bmain, &listbase);
2062         
2063         for (dsl = listbase.first; dsl; dsl = dsl->next) {
2064                 Scene *scene = dsl->scene;
2065                 Scene *sce_iter;
2066                 Base *base;
2067                 Object *ob;
2068                 Group *group;
2069                 GroupObject *go;
2070                 DagNode *node;
2071                 unsigned int lay = dsl->layer, oblay;
2072         
2073                 /* derivedmeshes and displists are not saved to file so need to be
2074                  * remade, tag them so they get remade in the scene update loop,
2075                  * note armature poses or object matrices are preserved and do not
2076                  * require updates, so we skip those */
2077                 dag_scene_flush_layers(scene, lay);
2078
2079                 for (SETLOOPER(scene, sce_iter, base)) {
2080                         ob = base->object;
2081                         node = (sce_iter->theDag) ? dag_get_node(sce_iter->theDag, ob) : NULL;
2082                         oblay = (node) ? node->lay : ob->lay;
2083
2084                         if ((oblay & lay) & ~scene->lay_updated) {
2085                                 if (ELEM6(ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2086                                         ob->recalc |= OB_RECALC_DATA;
2087                                 if (ob->dup_group) 
2088                                         ob->dup_group->id.flag |= LIB_DOIT;
2089                         }
2090                 }
2091
2092                 for (group = bmain->group.first; group; group = group->id.next) {
2093                         if (group->id.flag & LIB_DOIT) {
2094                                 for (go = group->gobject.first; go; go = go->next) {
2095                                         if (ELEM6(go->ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2096                                                 go->ob->recalc |= OB_RECALC_DATA;
2097                                         if (go->ob->proxy_from)
2098                                                 go->ob->recalc |= OB_RECALC_OB;
2099                                 }
2100                                 
2101                                 group->id.flag &= ~LIB_DOIT;
2102                         }
2103                 }
2104
2105                 /* now tag update flags, to ensure deformers get calculated on redraw */
2106                 DAG_scene_update_flags(bmain, scene, lay, do_time);
2107                 scene->lay_updated |= lay;
2108         }
2109         
2110         BLI_freelistN(&listbase);
2111
2112         /* hack to get objects updating on layer changes */
2113         DAG_id_type_tag(bmain, ID_OB);
2114
2115         /* so masks update on load */
2116         if (bmain->mask.first) {
2117                 Mask *mask;
2118
2119                 for (mask = bmain->mask.first; mask; mask = mask->id.next) {
2120                         DAG_id_tag_update(&mask->id, 0);
2121                 }
2122         }
2123 }
2124
2125 static void dag_id_flush_update__isDependentTexture(void *userData, Object *UNUSED(ob), ID **idpoin)
2126 {
2127         struct { ID *id; int is_dependent; } *data = userData;
2128         
2129         if (*idpoin && GS((*idpoin)->name) == ID_TE) {
2130                 if (data->id == (*idpoin))
2131                         data->is_dependent = 1;
2132         }
2133 }
2134
2135 static void dag_id_flush_update(Main *bmain, Scene *sce, ID *id)
2136 {
2137         Object *obt, *ob = NULL;
2138         short idtype;
2139
2140         /* here we flush a few things before actual scene wide flush, mostly
2141          * due to only objects and not other datablocks being in the depsgraph */
2142
2143         /* set flags & pointcache for object */
2144         if (GS(id->name) == ID_OB) {
2145                 ob = (Object *)id;
2146                 BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH);
2147
2148                 if (ob->recalc & OB_RECALC_DATA) {
2149                         /* all users of this ob->data should be checked */
2150                         id = ob->data;
2151
2152                         /* no point in trying in this cases */
2153                         if (id && id->us <= 1) {
2154                                 dag_editors_id_update(bmain, id);
2155                                 id = NULL;
2156                         }
2157                 }
2158         }
2159
2160         /* set flags & pointcache for object data */
2161         if (id) {
2162                 idtype = GS(id->name);
2163
2164
2165                 if (OB_DATA_SUPPORT_ID(idtype)) {
2166                         for (obt = bmain->object.first; obt; obt = obt->id.next) {
2167                                 if (!(ob && obt == ob) && obt->data == id) {
2168                                         obt->recalc |= OB_RECALC_DATA;
2169                                         lib_id_recalc_data_tag(bmain, &obt->id);
2170                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2171                                 }
2172                         }
2173                 }
2174                 
2175                 /* set flags based on textures - can influence depgraph via modifiers */
2176                 if (idtype == ID_TE) {
2177                         for (obt = bmain->object.first; obt; obt = obt->id.next) {
2178                                 struct { ID *id; int is_dependent; } data;
2179                                 data.id = id;
2180                                 data.is_dependent = 0;
2181
2182                                 modifiers_foreachIDLink(obt, dag_id_flush_update__isDependentTexture, &data);
2183                                 if (data.is_dependent) {
2184                                         obt->recalc |= OB_RECALC_DATA;
2185                                         lib_id_recalc_data_tag(bmain, &obt->id);
2186                                 }
2187
2188                                 /* particle settings can use the texture as well */
2189                                 if (obt->particlesystem.first) {
2190                                         ParticleSystem *psys = obt->particlesystem.first;
2191                                         MTex **mtexp, *mtex;
2192                                         int a;
2193                                         for (; psys; psys = psys->next) {
2194                                                 mtexp = psys->part->mtex;
2195                                                 for (a = 0; a < MAX_MTEX; a++, mtexp++) {
2196                                                         mtex = *mtexp;
2197                                                         if (mtex && mtex->tex == (Tex *)id) {
2198                                                                 obt->recalc |= OB_RECALC_DATA;
2199                                                                 lib_id_recalc_data_tag(bmain, &obt->id);
2200
2201                                                                 if (mtex->mapto & PAMAP_INIT)
2202                                                                         psys->recalc |= PSYS_RECALC_RESET;
2203                                                                 if (mtex->mapto & PAMAP_CHILD)
2204                                                                         psys->recalc |= PSYS_RECALC_CHILD;
2205
2206                                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2207                                                         }
2208                                                 }
2209                                         }
2210                                 }
2211                         }
2212                 }
2213                 
2214                 /* set flags based on ShapeKey */
2215                 if (idtype == ID_KE) {
2216                         for (obt = bmain->object.first; obt; obt = obt->id.next) {
2217                                 Key *key = BKE_key_from_object(obt);
2218                                 if (!(ob && obt == ob) && ((ID *)key == id)) {
2219                                         obt->flag |= (OB_RECALC_OB | OB_RECALC_DATA);
2220                                         lib_id_recalc_tag(bmain, &obt->id);
2221                                         lib_id_recalc_data_tag(bmain, &obt->id);
2222                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2223                                 }
2224                         }
2225                 }
2226                 
2227                 /* set flags based on particle settings */
2228                 if (idtype == ID_PA) {
2229                         ParticleSystem *psys;
2230                         for (obt = bmain->object.first; obt; obt = obt->id.next)
2231                                 for (psys = obt->particlesystem.first; psys; psys = psys->next)
2232                                         if (&psys->part->id == id)
2233                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2234                 }
2235
2236                 if (idtype == ID_MC) {
2237                         MovieClip *clip = (MovieClip *) id;
2238
2239                         BKE_tracking_dopesheet_tag_update(&clip->tracking);
2240
2241                         for (obt = bmain->object.first; obt; obt = obt->id.next) {
2242                                 bConstraint *con;
2243                                 for (con = obt->constraints.first; con; con = con->next) {
2244                                         bConstraintTypeInfo *cti = BKE_constraint_get_typeinfo(con);
2245                                         if (ELEM3(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER,
2246                                                   CONSTRAINT_TYPE_OBJECTSOLVER))
2247                                         {
2248                                                 obt->recalc |= OB_RECALC_OB;
2249                                                 break;
2250                                         }
2251                                 }
2252                         }
2253
2254                         if (sce->nodetree) {
2255                                 bNode *node;
2256
2257                                 for (node = sce->nodetree->nodes.first; node; node = node->next) {
2258                                         if (node->id == id) {
2259                                                 nodeUpdate(sce->nodetree, node);
2260                                         }
2261                                 }
2262                         }
2263                 }
2264
2265                 if (idtype == ID_MSK) {
2266                         if (sce->nodetree) {
2267                                 bNode *node;
2268
2269                                 for (node = sce->nodetree->nodes.first; node; node = node->next) {
2270                                         if (node->id == id) {
2271                                                 nodeUpdate(sce->nodetree, node);
2272                                         }
2273                                 }
2274                         }
2275                 }
2276
2277                 /* camera's matrix is used to orient reconstructed stuff,
2278                  * so it should happen tracking-related constraints recalculation
2279                  * when camera is changing (sergey) */
2280                 if (sce->camera && &sce->camera->id == id) {
2281                         MovieClip *clip = BKE_object_movieclip_get(sce, sce->camera, 1);
2282
2283                         if (clip)
2284                                 dag_id_flush_update(bmain, sce, &clip->id);
2285                 }
2286
2287                 /* update editors */
2288                 dag_editors_id_update(bmain, id);
2289         }
2290 }
2291
2292 void DAG_ids_flush_tagged(Main *bmain)
2293 {
2294         ListBase listbase;
2295         DagSceneLayer *dsl;
2296         ListBase *lbarray[MAX_LIBARRAY];
2297         int a, do_flush = FALSE;
2298         
2299         /* get list of visible scenes and layers */
2300         dag_current_scene_layers(bmain, &listbase);
2301
2302         if (listbase.first == NULL)
2303                 return;
2304
2305         /* loop over all ID types */
2306         a  = set_listbasepointers(bmain, lbarray);
2307
2308         while (a--) {
2309                 ListBase *lb = lbarray[a];
2310                 ID *id = lb->first;
2311
2312                 /* we tag based on first ID type character to avoid 
2313                  * looping over all ID's in case there are no tags */
2314                 if (id && bmain->id_tag_update[id->name[0]]) {
2315                         for (; id; id = id->next) {
2316                                 if (id->flag & (LIB_ID_RECALC | LIB_ID_RECALC_DATA)) {
2317                                         
2318                                         for (dsl = listbase.first; dsl; dsl = dsl->next)
2319                                                 dag_id_flush_update(bmain, dsl->scene, id);
2320                                         
2321                                         do_flush = TRUE;
2322                                 }
2323                         }
2324                 }
2325         }
2326
2327         /* flush changes to other objects */
2328         if (do_flush) {
2329                 for (dsl = listbase.first; dsl; dsl = dsl->next)
2330                         DAG_scene_flush_update(bmain, dsl->scene, dsl->layer, 0);
2331         }
2332         
2333         BLI_freelistN(&listbase);
2334 }
2335
2336 void DAG_ids_check_recalc(Main *bmain, Scene *scene, int time)
2337 {
2338         ListBase *lbarray[MAX_LIBARRAY];
2339         int a, updated = 0;
2340
2341         /* loop over all ID types */
2342         a  = set_listbasepointers(bmain, lbarray);
2343
2344         while (a--) {
2345                 ListBase *lb = lbarray[a];
2346                 ID *id = lb->first;
2347
2348                 /* we tag based on first ID type character to avoid 
2349                  * looping over all ID's in case there are no tags */
2350                 if (id &&
2351 #ifdef WITH_FREESTYLE
2352                     /* XXX very weak... added check for '27' to ignore freestyle added objects */
2353                     id->name[2] > 27 &&
2354 #endif
2355                     bmain->id_tag_update[id->name[0]])
2356                 {
2357                         updated = 1;
2358                         break;
2359                 }
2360         }
2361
2362         dag_editors_scene_update(bmain, scene, (updated || time));
2363 }
2364
2365 void DAG_ids_clear_recalc(Main *bmain)
2366 {
2367         ListBase *lbarray[MAX_LIBARRAY];
2368         bNodeTree *ntree;
2369         int a;
2370
2371         /* loop over all ID types */
2372         a  = set_listbasepointers(bmain, lbarray);
2373
2374         while (a--) {
2375                 ListBase *lb = lbarray[a];
2376                 ID *id = lb->first;
2377
2378                 /* we tag based on first ID type character to avoid 
2379                  * looping over all ID's in case there are no tags */
2380                 if (id && bmain->id_tag_update[id->name[0]]) {
2381                         for (; id; id = id->next) {
2382                                 if (id->flag & (LIB_ID_RECALC | LIB_ID_RECALC_DATA))
2383                                         id->flag &= ~(LIB_ID_RECALC | LIB_ID_RECALC_DATA);
2384
2385                                 /* some ID's contain semi-datablock nodetree */
2386                                 ntree = ntreeFromID(id);
2387                                 if (ntree && (ntree->id.flag & (LIB_ID_RECALC | LIB_ID_RECALC_DATA)))
2388                                         ntree->id.flag &= ~(LIB_ID_RECALC | LIB_ID_RECALC_DATA);
2389                         }
2390                 }
2391         }
2392
2393         memset(bmain->id_tag_update, 0, sizeof(bmain->id_tag_update));
2394 }
2395
2396 void DAG_id_tag_update_ex(Main *bmain, ID *id, short flag)
2397 {
2398         if (id == NULL) return;
2399
2400         /* tag ID for update */
2401         if (flag) {
2402                 if (flag & OB_RECALC_OB)
2403                         lib_id_recalc_tag(bmain, id);
2404                 if (flag & (OB_RECALC_DATA | PSYS_RECALC))
2405                         lib_id_recalc_data_tag(bmain, id);
2406         }
2407         else
2408                 lib_id_recalc_tag(bmain, id);
2409
2410         /* flag is for objects and particle systems */
2411         if (flag) {
2412                 Object *ob;
2413                 short idtype = GS(id->name);
2414
2415                 if (idtype == ID_OB) {
2416                         /* only quick tag */
2417                         ob = (Object *)id;
2418                         ob->recalc |= (flag & OB_RECALC_ALL);
2419                 }
2420                 else if (idtype == ID_PA) {
2421                         ParticleSystem *psys;
2422                         /* this is weak still, should be done delayed as well */
2423                         for (ob = bmain->object.first; ob; ob = ob->id.next) {
2424                                 for (psys = ob->particlesystem.first; psys; psys = psys->next) {
2425                                         if (&psys->part->id == id) {
2426                                                 ob->recalc |= (flag & OB_RECALC_ALL);
2427                                                 psys->recalc |= (flag & PSYS_RECALC);
2428                                                 lib_id_recalc_tag(bmain, &ob->id);
2429                                                 lib_id_recalc_data_tag(bmain, &ob->id);
2430                                         }
2431                                 }
2432                         }
2433                 }
2434                 else if (idtype == ID_VF) {
2435                         /* this is weak still, should be done delayed as well */
2436                         for (ob = bmain->object.first; ob; ob = ob->id.next) {
2437                                 if (ob->type == OB_FONT) {
2438                                         Curve *cu = ob->data;
2439
2440                                         if (ELEM4((struct VFont *)id, cu->vfont, cu->vfontb, cu->vfonti, cu->vfontbi)) {
2441                                                 ob->recalc |= (flag & OB_RECALC_ALL);
2442                                         }
2443                                 }
2444                         }
2445                 }
2446                 else {
2447                         /* disable because this is called on various ID types automatically.
2448                          * where printing warning is not useful. for now just ignore */
2449                         /* BLI_assert(!"invalid flag for this 'idtype'"); */
2450                 }
2451         }
2452 }
2453
2454 void DAG_id_tag_update(ID *id, short flag)
2455 {
2456         DAG_id_tag_update_ex(G.main, id, flag);
2457 }
2458
2459 void DAG_id_type_tag(Main *bmain, short idtype)
2460 {
2461         if (idtype == ID_NT) {
2462                 /* stupid workaround so parent datablocks of nested nodetree get looped
2463                  * over when we loop over tagged datablock types */
2464                 DAG_id_type_tag(bmain, ID_MA);
2465                 DAG_id_type_tag(bmain, ID_TE);
2466                 DAG_id_type_tag(bmain, ID_LA);
2467                 DAG_id_type_tag(bmain, ID_WO);
2468                 DAG_id_type_tag(bmain, ID_SCE);
2469         }
2470
2471         bmain->id_tag_update[((char *)&idtype)[0]] = 1;
2472 }
2473
2474 int DAG_id_type_tagged(Main *bmain, short idtype)
2475 {
2476         return bmain->id_tag_update[((char *)&idtype)[0]];
2477 }
2478
2479 #if 0 // UNUSED
2480 /* recursively descends tree, each node only checked once */
2481 /* node is checked to be of type object */
2482 static int parent_check_node(DagNode *node, int curtime)
2483 {
2484         DagAdjList *itA;
2485         
2486         node->lasttime = curtime;
2487         
2488         if (node->color == DAG_GRAY)
2489                 return DAG_GRAY;
2490         
2491         for (itA = node->child; itA; itA = itA->next) {
2492                 if (itA->node->type == ID_OB) {
2493                         
2494                         if (itA->node->color == DAG_GRAY)
2495                                 return DAG_GRAY;
2496
2497                         /* descend if not done */
2498                         if (itA->node->lasttime != curtime) {
2499                                 itA->node->color = parent_check_node(itA->node, curtime);
2500                         
2501                                 if (itA->node->color == DAG_GRAY)
2502                                         return DAG_GRAY;
2503                         }
2504                 }
2505         }
2506         
2507         return DAG_WHITE;
2508 }
2509 #endif
2510
2511 /* ******************* DAG FOR ARMATURE POSE ***************** */
2512
2513 /* we assume its an armature with pose */
2514 void DAG_pose_sort(Object *ob)
2515 {
2516         bPose *pose = ob->pose;
2517         bPoseChannel *pchan;
2518         bConstraint *con;
2519         DagNode *node;
2520         DagNode *node2, *node3;
2521         DagNode *rootnode;
2522         DagForest *dag;
2523         DagNodeQueue *nqueue;
2524         DagAdjList *itA;
2525         ListBase tempbase;
2526         int skip = 0;
2527         
2528         dag = dag_init();
2529         ugly_hack_sorry = 0;  /* no ID structs */
2530
2531         rootnode = dag_add_node(dag, NULL);  /* node->ob becomes NULL */
2532         
2533         /* we add the hierarchy and the constraints */
2534         for (pchan = pose->chanbase.first; pchan; pchan = pchan->next) {
2535                 int addtoroot = 1;
2536                 
2537                 node = dag_get_node(dag, pchan);
2538                 
2539                 if (pchan->parent) {
2540                         node2 = dag_get_node(dag, pchan->parent);
2541                         dag_add_relation(dag, node2, node, 0, "Parent Relation");
2542                         addtoroot = 0;
2543                 }
2544                 for (con = pchan->constraints.first; con; con = con->next) {
2545                         bConstraintTypeInfo *cti = BKE_constraint_get_typeinfo(con);
2546                         ListBase targets = {NULL, NULL};
2547                         bConstraintTarget *ct;
2548                         
2549                         if (cti && cti->get_constraint_targets) {
2550                                 cti->get_constraint_targets(con, &targets);
2551                                 
2552                                 for (ct = targets.first; ct; ct = ct->next) {
2553                                         if (ct->tar == ob && ct->subtarget[0]) {
2554                                                 bPoseChannel *target = BKE_pose_channel_find_name(ob->pose, ct->subtarget);
2555                                                 if (target) {
2556                                                         node2 = dag_get_node(dag, target);
2557                                                         dag_add_relation(dag, node2, node, 0, "Pose Constraint");
2558                                                         
2559                                                         if (con->type == CONSTRAINT_TYPE_KINEMATIC) {
2560                                                                 bKinematicConstraint *data = (bKinematicConstraint *)con->data;
2561                                                                 bPoseChannel *parchan;
2562                                                                 int segcount = 0;
2563                                                                 
2564                                                                 /* exclude tip from chain? */
2565                                                                 if (!(data->flag & CONSTRAINT_IK_TIP))
2566                                                                         parchan = pchan->parent;
2567                                                                 else
2568                                                                         parchan = pchan;
2569                                                                 
2570                                                                 /* Walk to the chain's root */
2571                                                                 while (parchan) {
2572                                                                         node3 = dag_get_node(dag, parchan);
2573                                                                         dag_add_relation(dag, node2, node3, 0, "IK Constraint");
2574                                                                         
2575                                                                         segcount++;
2576                                                                         if (segcount == data->rootbone || segcount > 255) break;  /* 255 is weak */
2577                                                                         parchan = parchan->parent;
2578                                                                 }
2579                                                         }
2580                                                 }
2581                                         }
2582                                 }
2583                                 
2584                                 if (cti->flush_constraint_targets)
2585                                         cti->flush_constraint_targets(con, &targets, 1);
2586                         }
2587                 }
2588                 if (addtoroot == 1) {
2589                         dag_add_relation(dag, rootnode, node, 0, "Root Bone Relation");
2590                 }
2591         }
2592
2593         dag_check_cycle(dag);
2594         
2595         /* now we try to sort... */
2596         tempbase.first = tempbase.last = NULL;
2597
2598         nqueue = queue_create(DAGQUEUEALLOC);
2599         
2600         /* tag nodes unchecked */
2601         for (node = dag->DagNode.first; node; node = node->next)
2602                 node->color = DAG_WHITE;
2603         
2604         rootnode->color = DAG_GRAY;
2605         push_stack(nqueue, rootnode);  
2606         
2607         while (nqueue->count) {
2608                 
2609                 skip = 0;
2610                 node = get_top_node_queue(nqueue);
2611                 
2612                 itA = node->child;
2613                 while (itA != NULL) {
2614                         if (itA->node->color == DAG_WHITE) {
2615                                 itA->node->color = DAG_GRAY;
2616                                 push_stack(nqueue, itA->node);
2617                                 skip = 1;
2618                                 break;
2619                         }
2620                         itA = itA->next;
2621                 }
2622                 
2623                 if (!skip) {
2624                         if (node) {
2625                                 node = pop_queue(nqueue);
2626                                 if (node->ob == NULL)  /* we are done */
2627                                         break;
2628                                 node->color = DAG_BLACK;
2629                                 
2630                                 /* put node in new list */
2631                                 BLI_remlink(&pose->chanbase, node->ob);
2632                                 BLI_addhead(&tempbase, node->ob);
2633                         }
2634                 }
2635         }
2636         
2637         /* temporal correction for circular dependencies */
2638         while (pose->chanbase.first) {
2639                 pchan = pose->chanbase.first;
2640                 BLI_remlink(&pose->chanbase, pchan);
2641                 BLI_addhead(&tempbase, pchan);
2642
2643                 printf("cyclic %s\n", pchan->name);
2644         }
2645         
2646         pose->chanbase = tempbase;
2647         queue_delete(nqueue);
2648         
2649 //      printf("\nordered\n");
2650 //      for (pchan = pose->chanbase.first; pchan; pchan = pchan->next) {
2651 //              printf(" %s\n", pchan->name);
2652 //      }
2653         
2654         free_forest(dag);
2655         MEM_freeN(dag);
2656         
2657         ugly_hack_sorry = 1;
2658 }
2659
2660 /* ************************  DAG FOR THREADED UPDATE  ********************* */
2661
2662 static SpinLock threaded_update_lock;
2663
2664 void DAG_threaded_init(void)
2665 {
2666         BLI_spin_init(&threaded_update_lock);
2667 }
2668
2669 void DAG_threaded_exit(void)
2670 {
2671         BLI_spin_end(&threaded_update_lock);
2672 }
2673
2674 /* Initialize the DAG for threaded update.
2675  *
2676  * Sets up all the data needed for faster check whether DAG node is
2677  * updatable already (whether all the dependencies are met).
2678  */
2679 void DAG_threaded_update_begin(Scene *scene)
2680 {
2681         DagNode *node;
2682
2683         /* We reset valency to zero first... */
2684         for (node = scene->theDag->DagNode.first; node; node = node->next) {
2685                 node->valency = 0;
2686                 node->color = DAG_WHITE;
2687         }
2688
2689         /* ... and then iterate over all the nodes and
2690          * increase valency for node childs.
2691          */
2692         for (node = scene->theDag->DagNode.first; node; node = node->next) {
2693                 DagAdjList *itA;
2694
2695                 for (itA = node->child; itA; itA = itA->next) {
2696                         if (itA->node != node) {
2697                                 itA->node->valency++;
2698                         }
2699                 }
2700         }
2701 }
2702
2703 /* Call functor for every node in the graph which is ready for
2704  * update (all it's dependencies are met). Quick check for this
2705  * is valency == 0.
2706  */
2707 void DAG_threaded_update_foreach_ready_node(Scene *scene,
2708                                             void (*func)(void *node, void *user_data),
2709                                             void *user_data)
2710 {
2711         DagNode *node;
2712
2713         for (node = scene->theDag->DagNode.first; node; node = node->next) {
2714                 if (node->valency == 0) {
2715                         bool need_schedule;
2716
2717                         BLI_spin_lock(&threaded_update_lock);
2718                         need_schedule = node->color == DAG_WHITE;
2719                         node->color = DAG_BLACK;
2720                         BLI_spin_unlock(&threaded_update_lock);
2721
2722                         if (need_schedule) {
2723                                 func(node, user_data);
2724                         }
2725                 }
2726         }
2727 }
2728
2729 /* Will return Object ID if node represents Object,
2730  * and will return NULL otherwise.
2731  */
2732 Object *DAG_threaded_update_get_node_object(void *node_v)
2733 {
2734         DagNode *node = node_v;
2735
2736         if (node->type == ID_OB) {
2737                 return node->ob;
2738         }
2739
2740         return NULL;
2741 }
2742
2743 /* Returns node name, used for debug output only, atm. */
2744 const char *DAG_threaded_update_get_node_name(void *node_v)
2745 {
2746         DagNode *node = node_v;
2747
2748         return dag_node_name(node);
2749 }
2750
2751 /* This function is called when handling node is done.
2752  *
2753  * This function updates valency for all childs and
2754  * schedules them if they're ready.
2755  */
2756 void DAG_threaded_update_handle_node_updated(void *node_v,
2757                                              void (*func)(void *node, void *user_data),
2758                                              void *user_data)
2759 {
2760         DagNode *node = node_v;
2761         DagAdjList *itA;
2762
2763         for (itA = node->child; itA; itA = itA->next) {
2764                 DagNode *child_node = itA->node;
2765                 if (child_node != node) {
2766                         atomic_sub_uint32(&child_node->valency, 1);
2767
2768                         if (child_node->valency == 0) {
2769                                 bool need_schedule;
2770
2771                                 BLI_spin_lock(&threaded_update_lock);
2772                                 need_schedule = child_node->color == DAG_WHITE;
2773                                 child_node->color = DAG_BLACK;
2774                                 BLI_spin_unlock(&threaded_update_lock);
2775
2776                                 if (need_schedule) {
2777                                         func(child_node, user_data);
2778                                 }
2779                         }
2780                 }
2781         }
2782 }
2783
2784 /* ************************ DAG DEBUGGING ********************* */
2785
2786 void DAG_print_dependencies(Main *bmain, Scene *scene, Object *ob)
2787 {
2788         /* utility for debugging dependencies */
2789         dag_print_dependencies = 1;
2790
2791         if (ob && (ob->mode & OB_MODE_POSE)) {
2792                 printf("\nDEPENDENCY RELATIONS for %s\n\n", ob->id.name + 2);
2793                 DAG_pose_sort(ob);
2794         }
2795         else {
2796                 printf("\nDEPENDENCY RELATIONS for %s\n\n", scene->id.name + 2);
2797                 DAG_scene_relations_rebuild(bmain, scene);
2798         }
2799         
2800         dag_print_dependencies = 0;
2801 }