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