f786f842be37f65e938fd104eac9844fa165d913
[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 DagForest *build_dag(Main *bmain, Scene *sce, short mask)
824 {
825         Base *base;
826         Object *ob;
827         Group *group;
828         GroupObject *go;
829         DagNode *node;
830         DagNode *scenenode;
831         DagForest *dag;
832         DagAdjList *itA;
833
834         dag = sce->theDag;
835         if (dag)
836                 free_forest(dag);
837         else {
838                 dag = dag_init();
839                 sce->theDag = dag;
840         }
841         
842         /* clear "LIB_DOIT" flag from all materials, to prevent infinite recursion problems later [#32017] */
843         tag_main_idcode(bmain, ID_MA, FALSE);
844         tag_main_idcode(bmain, ID_LA, FALSE);
845         
846         /* add base node for scene. scene is always the first node in DAG */
847         scenenode = dag_add_node(dag, sce);
848         
849         /* add current scene objects */
850         for (base = sce->base.first; base; base = base->next) {
851                 ob = base->object;
852                 
853                 build_dag_object(dag, scenenode, sce, ob, mask);
854                 if (ob->proxy)
855                         build_dag_object(dag, scenenode, sce, ob->proxy, mask);
856                 
857                 /* handled in next loop */
858                 if (ob->dup_group) 
859                         ob->dup_group->id.flag |= LIB_DOIT;
860         }
861         
862         /* add groups used in current scene objects */
863         for (group = bmain->group.first; group; group = group->id.next) {
864                 if (group->id.flag & LIB_DOIT) {
865                         for (go = group->gobject.first; go; go = go->next) {
866                                 build_dag_object(dag, scenenode, sce, go->ob, mask);
867                         }
868                         group->id.flag &= ~LIB_DOIT;
869                 }
870         }
871         
872         /* Now all relations were built, but we need to solve 1 exceptional case;
873          * When objects have multiple "parents" (for example parent + constraint working on same object)
874          * the relation type has to be synced. One of the parents can change, and should give same event to child */
875         
876         /* nodes were callocced, so we can use node->color for temporal storage */
877         for (node = sce->theDag->DagNode.first; node; node = node->next) {
878                 if (node->type == ID_OB) {
879                         for (itA = node->child; itA; itA = itA->next) {
880                                 if (itA->node->type == ID_OB) {
881                                         itA->node->color |= itA->type;
882                                 }
883                         }
884
885                         /* also flush custom data mask */
886                         ((Object *)node->ob)->customdata_mask = node->customdata_mask;
887                 }
888         }
889         /* now set relations equal, so that when only one parent changes, the correct recalcs are found */
890         for (node = sce->theDag->DagNode.first; node; node = node->next) {
891                 if (node->type == ID_OB) {
892                         for (itA = node->child; itA; itA = itA->next) {
893                                 if (itA->node->type == ID_OB) {
894                                         itA->type |= itA->node->color;
895                                 }
896                         }
897                 }
898         }
899         
900         /* cycle detection and solving */
901         // solve_cycles(dag);
902         
903         return dag;
904 }
905
906
907 void free_forest(DagForest *Dag) 
908 {  /* remove all nodes and deps */
909         DagNode *tempN;
910         DagAdjList *tempA;
911         DagAdjList *itA;
912         DagNode *itN = Dag->DagNode.first;
913         
914         while (itN) {
915                 itA = itN->child;
916                 while (itA) {
917                         tempA = itA;
918                         itA = itA->next;
919                         MEM_freeN(tempA);
920                 }
921                 
922                 itA = itN->parent;
923                 while (itA) {
924                         tempA = itA;
925                         itA = itA->next;
926                         MEM_freeN(tempA);
927                 }
928                 
929                 tempN = itN;
930                 itN = itN->next;
931                 MEM_freeN(tempN);
932         }
933
934         BLI_ghash_free(Dag->nodeHash, NULL, NULL);
935         Dag->nodeHash = NULL;
936         Dag->DagNode.first = NULL;
937         Dag->DagNode.last = NULL;
938         Dag->numNodes = 0;
939
940 }
941
942 DagNode *dag_find_node(DagForest *forest, void *fob)
943 {
944         if (forest->nodeHash)
945                 return BLI_ghash_lookup(forest->nodeHash, fob);
946
947         return NULL;
948 }
949
950 static int ugly_hack_sorry = 1;         /* prevent type check */
951 static int dag_print_dependencies = 0;  /* debugging */
952
953 /* no checking of existence, use dag_find_node first or dag_get_node */
954 DagNode *dag_add_node(DagForest *forest, void *fob)
955 {
956         DagNode *node;
957                 
958         node = MEM_callocN(sizeof(DagNode), "DAG node");
959         if (node) {
960                 node->ob = fob;
961                 node->color = DAG_WHITE;
962
963                 if (ugly_hack_sorry) node->type = GS(((ID *) fob)->name);  /* sorry, done for pose sorting */
964                 if (forest->numNodes) {
965                         ((DagNode *) forest->DagNode.last)->next = node;
966                         forest->DagNode.last = node;
967                         forest->numNodes++;
968                 }
969                 else {
970                         forest->DagNode.last = node;
971                         forest->DagNode.first = node;
972                         forest->numNodes = 1;
973                 }
974
975                 if (!forest->nodeHash)
976                         forest->nodeHash = BLI_ghash_ptr_new("dag_add_node gh");
977                 BLI_ghash_insert(forest->nodeHash, fob, node);
978         }
979
980         return node;
981 }
982
983 DagNode *dag_get_node(DagForest *forest, void *fob)
984 {
985         DagNode *node;
986         
987         node = dag_find_node(forest, fob);
988         if (!node) 
989                 node = dag_add_node(forest, fob);
990         return node;
991 }
992
993
994
995 DagNode *dag_get_sub_node(DagForest *forest, void *fob)
996 {
997         DagNode *node;
998         DagAdjList *mainchild, *prev = NULL;
999         
1000         mainchild = ((DagNode *) forest->DagNode.first)->child;
1001         /* remove from first node (scene) adj list if present */
1002         while (mainchild) {
1003                 if (mainchild->node == fob) {
1004                         if (prev) {
1005                                 prev->next = mainchild->next;
1006                                 MEM_freeN(mainchild);
1007                                 break;
1008                         }
1009                         else {
1010                                 ((DagNode *) forest->DagNode.first)->child = mainchild->next;
1011                                 MEM_freeN(mainchild);
1012                                 break;
1013                         }
1014                 }
1015                 prev = mainchild;
1016                 mainchild = mainchild->next;
1017         }
1018         node = dag_find_node(forest, fob);
1019         if (!node) 
1020                 node = dag_add_node(forest, fob);
1021         return node;
1022 }
1023
1024 static void dag_add_parent_relation(DagForest *UNUSED(forest), DagNode *fob1, DagNode *fob2, short rel, const char *name) 
1025 {
1026         DagAdjList *itA = fob2->parent;
1027         
1028         while (itA) { /* search if relation exist already */
1029                 if (itA->node == fob1) {
1030                         itA->type |= rel;
1031                         itA->count += 1;
1032                         return;
1033                 }
1034                 itA = itA->next;
1035         }
1036         /* create new relation and insert at head. MALLOC alert! */
1037         itA = MEM_mallocN(sizeof(DagAdjList), "DAG adj list");
1038         itA->node = fob1;
1039         itA->type = rel;
1040         itA->count = 1;
1041         itA->next = fob2->parent;
1042         itA->name = name;
1043         fob2->parent = itA;
1044 }
1045
1046 void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, short rel, const char *name) 
1047 {
1048         DagAdjList *itA = fob1->child;
1049         
1050         /* parent relation is for cycle checking */
1051         dag_add_parent_relation(forest, fob1, fob2, rel, name);
1052
1053         while (itA) { /* search if relation exist already */
1054                 if (itA->node == fob2) {
1055                         itA->type |= rel;
1056                         itA->count += 1;
1057                         return;
1058                 }
1059                 itA = itA->next;
1060         }
1061         /* create new relation and insert at head. MALLOC alert! */
1062         itA = MEM_mallocN(sizeof(DagAdjList), "DAG adj list");
1063         itA->node = fob2;
1064         itA->type = rel;
1065         itA->count = 1;
1066         itA->next = fob1->child;
1067         itA->name = name;
1068         fob1->child = itA;
1069 }
1070
1071 static const char *dag_node_name(DagNode *node)
1072 {
1073         if (node->ob == NULL)
1074                 return "null";
1075         else if (ugly_hack_sorry)
1076                 return ((ID *)(node->ob))->name + 2;
1077         else
1078                 return ((bPoseChannel *)(node->ob))->name;
1079 }
1080
1081 static void dag_node_print_dependencies(DagNode *node)
1082 {
1083         DagAdjList *itA;
1084
1085         printf("%s depends on:\n", dag_node_name(node));
1086
1087         for (itA = node->parent; itA; itA = itA->next)
1088                 printf("  %s through %s\n", dag_node_name(itA->node), itA->name);
1089         printf("\n");
1090 }
1091
1092 static int dag_node_print_dependency_recurs(DagNode *node, DagNode *endnode)
1093 {
1094         DagAdjList *itA;
1095
1096         if (node->color == DAG_BLACK)
1097                 return 0;
1098
1099         node->color = DAG_BLACK;
1100
1101         if (node == endnode)
1102                 return 1;
1103
1104         for (itA = node->parent; itA; itA = itA->next) {
1105                 if (dag_node_print_dependency_recurs(itA->node, endnode)) {
1106                         printf("  %s depends on %s through %s.\n", dag_node_name(node), dag_node_name(itA->node), itA->name);
1107                         return 1;
1108                 }
1109         }
1110
1111         return 0;
1112 }
1113
1114 static void dag_node_print_dependency_cycle(DagForest *dag, DagNode *startnode, DagNode *endnode, const char *name)
1115 {
1116         DagNode *node;
1117
1118         for (node = dag->DagNode.first; node; node = node->next)
1119                 node->color = DAG_WHITE;
1120
1121         printf("  %s depends on %s through %s.\n", dag_node_name(endnode), dag_node_name(startnode), name);
1122         dag_node_print_dependency_recurs(startnode, endnode);
1123         printf("\n");
1124 }
1125
1126 static int dag_node_recurs_level(DagNode *node, int level)
1127 {
1128         DagAdjList *itA;
1129         int newlevel;
1130
1131         node->color = DAG_BLACK; /* done */
1132         newlevel = ++level;
1133         
1134         for (itA = node->parent; itA; itA = itA->next) {
1135                 if (itA->node->color == DAG_WHITE) {
1136                         itA->node->ancestor_count = dag_node_recurs_level(itA->node, level);
1137                         newlevel = MAX2(newlevel, level + itA->node->ancestor_count);
1138                 }
1139                 else
1140                         newlevel = MAX2(newlevel, level + itA->node->ancestor_count);
1141         }
1142         
1143         return newlevel;
1144 }
1145
1146 static void dag_check_cycle(DagForest *dag)
1147 {
1148         DagNode *node;
1149         DagAdjList *itA;
1150
1151         /* debugging print */
1152         if (dag_print_dependencies)
1153                 for (node = dag->DagNode.first; node; node = node->next)
1154                         dag_node_print_dependencies(node);
1155
1156         /* tag nodes unchecked */
1157         for (node = dag->DagNode.first; node; node = node->next)
1158                 node->color = DAG_WHITE;
1159         
1160         for (node = dag->DagNode.first; node; node = node->next) {
1161                 if (node->color == DAG_WHITE) {
1162                         node->ancestor_count = dag_node_recurs_level(node, 0);
1163                 }
1164         }
1165         
1166         /* check relations, and print errors */
1167         for (node = dag->DagNode.first; node; node = node->next) {
1168                 for (itA = node->parent; itA; itA = itA->next) {
1169                         if (itA->node->ancestor_count > node->ancestor_count) {
1170                                 if (node->ob && itA->node->ob) {
1171                                         printf("Dependency cycle detected:\n");
1172                                         dag_node_print_dependency_cycle(dag, itA->node, node, itA->name);
1173                                 }
1174                         }
1175                 }
1176         }
1177
1178         /* parent relations are only needed for cycle checking, so free now */
1179         for (node = dag->DagNode.first; node; node = node->next) {
1180                 while (node->parent) {
1181                         itA = node->parent->next;
1182                         MEM_freeN(node->parent);
1183                         node->parent = itA;
1184                 }
1185         }
1186 }
1187
1188 /* debug test functions */
1189
1190 void graph_print_queue(DagNodeQueue *nqueue)
1191 {       
1192         DagNodeQueueElem *queueElem;
1193         
1194         queueElem = nqueue->first;
1195         while (queueElem) {
1196                 fprintf(stderr, "** %s %i %i-%i ", ((ID *) queueElem->node->ob)->name, queueElem->node->color, queueElem->node->DFS_dvtm, queueElem->node->DFS_fntm);
1197                 queueElem = queueElem->next;
1198         }
1199         fprintf(stderr, "\n");
1200 }
1201
1202 void graph_print_queue_dist(DagNodeQueue *nqueue)
1203 {       
1204         DagNodeQueueElem *queueElem;
1205         int count;
1206         
1207         queueElem = nqueue->first;
1208         count = 0;
1209         while (queueElem) {
1210                 fprintf(stderr, "** %25s %2.2i-%2.2i ", ((ID *) queueElem->node->ob)->name, queueElem->node->DFS_dvtm, queueElem->node->DFS_fntm);
1211                 while (count < queueElem->node->DFS_dvtm - 1) { fputc(' ', stderr); count++; }
1212                 fputc('|', stderr);
1213                 while (count < queueElem->node->DFS_fntm - 2) { fputc('-', stderr); count++; }
1214                 fputc('|', stderr);
1215                 fputc('\n', stderr);
1216                 count = 0;
1217                 queueElem = queueElem->next;
1218         }
1219         fprintf(stderr, "\n");
1220 }
1221
1222 void graph_print_adj_list(DagForest *dag)
1223 {
1224         DagNode *node;
1225         DagAdjList *itA;
1226         
1227         node = dag->DagNode.first;
1228         while (node) {
1229                 fprintf(stderr, "node : %s col: %i", ((ID *) node->ob)->name, node->color);
1230                 itA = node->child;
1231                 while (itA) {
1232                         fprintf(stderr, "-- %s ", ((ID *) itA->node->ob)->name);
1233                         
1234                         itA = itA->next;
1235                 }
1236                 fprintf(stderr, "\n");
1237                 node = node->next;
1238         }
1239 }
1240
1241 /* ************************ API *********************** */
1242
1243 /* mechanism to allow editors to be informed of depsgraph updates,
1244  * to do their own updates based on changes... */
1245 static void (*EditorsUpdateIDCb)(Main *bmain, ID *id) = NULL;
1246 static void (*EditorsUpdateSceneCb)(Main *bmain, Scene *scene, int updated) = NULL;
1247
1248 void DAG_editors_update_cb(void (*id_func)(Main *bmain, ID *id), void (*scene_func)(Main *bmain, Scene *scene, int updated))
1249 {
1250         EditorsUpdateIDCb = id_func;
1251         EditorsUpdateSceneCb = scene_func;
1252 }
1253
1254 static void dag_editors_id_update(Main *bmain, ID *id)
1255 {
1256         if (EditorsUpdateIDCb)
1257                 EditorsUpdateIDCb(bmain, id);
1258 }
1259
1260 static void dag_editors_scene_update(Main *bmain, Scene *scene, int updated)
1261 {
1262         if (EditorsUpdateSceneCb)
1263                 EditorsUpdateSceneCb(bmain, scene, updated);
1264 }
1265
1266 /* groups with objects in this scene need to be put in the right order as well */
1267 static void scene_sort_groups(Main *bmain, Scene *sce)
1268 {
1269         Base *base;
1270         Group *group;
1271         GroupObject *go;
1272         Object *ob;
1273         
1274         /* test; are group objects all in this scene? */
1275         for (ob = bmain->object.first; ob; ob = ob->id.next) {
1276                 ob->id.flag &= ~LIB_DOIT;
1277                 ob->id.newid = NULL; /* newid abuse for GroupObject */
1278         }
1279         for (base = sce->base.first; base; base = base->next)
1280                 base->object->id.flag |= LIB_DOIT;
1281         
1282         for (group = bmain->group.first; group; group = group->id.next) {
1283                 for (go = group->gobject.first; go; go = go->next) {
1284                         if ((go->ob->id.flag & LIB_DOIT) == 0)
1285                                 break;
1286                 }
1287                 /* this group is entirely in this scene */
1288                 if (go == NULL) {
1289                         ListBase listb = {NULL, NULL};
1290                         
1291                         for (go = group->gobject.first; go; go = go->next)
1292                                 go->ob->id.newid = (ID *)go;
1293                         
1294                         /* in order of sorted bases we reinsert group objects */
1295                         for (base = sce->base.first; base; base = base->next) {
1296                                 
1297                                 if (base->object->id.newid) {
1298                                         go = (GroupObject *)base->object->id.newid;
1299                                         base->object->id.newid = NULL;
1300                                         BLI_remlink(&group->gobject, go);
1301                                         BLI_addtail(&listb, go);
1302                                 }
1303                         }
1304                         /* copy the newly sorted listbase */
1305                         group->gobject = listb;
1306                 }
1307         }
1308 }
1309
1310 /* free the depency graph */
1311 static void dag_scene_free(Scene *sce)
1312 {
1313         if (sce->theDag) {
1314                 free_forest(sce->theDag);
1315                 MEM_freeN(sce->theDag);
1316                 sce->theDag = NULL;
1317         }
1318 }
1319
1320 /* sort the base list on dependency order */
1321 static void dag_scene_build(Main *bmain, Scene *sce)
1322 {
1323         DagNode *node, *rootnode;
1324         DagNodeQueue *nqueue;
1325         DagAdjList *itA;
1326         int time;
1327         int skip = 0;
1328         ListBase tempbase;
1329         Base *base;
1330
1331         tempbase.first = tempbase.last = NULL;
1332         
1333         build_dag(bmain, sce, DAG_RL_ALL_BUT_DATA);
1334         
1335         dag_check_cycle(sce->theDag);
1336
1337         nqueue = queue_create(DAGQUEUEALLOC);
1338         
1339         for (node = sce->theDag->DagNode.first; node; node = node->next) {
1340                 node->color = DAG_WHITE;
1341         }
1342         
1343         time = 1;
1344         
1345         rootnode = sce->theDag->DagNode.first;
1346         rootnode->color = DAG_GRAY;
1347         time++;
1348         push_stack(nqueue, rootnode);
1349         
1350         while (nqueue->count) {
1351                 
1352                 skip = 0;
1353                 node = get_top_node_queue(nqueue);
1354                 
1355                 itA = node->child;
1356                 while (itA != NULL) {
1357                         if (itA->node->color == DAG_WHITE) {
1358                                 itA->node->DFS_dvtm = time;
1359                                 itA->node->color = DAG_GRAY;
1360                                 
1361                                 time++;
1362                                 push_stack(nqueue, itA->node);
1363                                 skip = 1;
1364                                 break;
1365                         }
1366                         itA = itA->next;
1367                 }
1368                 
1369                 if (!skip) {
1370                         if (node) {
1371                                 node = pop_queue(nqueue);
1372                                 if (node->ob == sce)  /* we are done */
1373                                         break;
1374                                 node->color = DAG_BLACK;
1375                                 
1376                                 time++;
1377                                 base = sce->base.first;
1378                                 while (base && base->object != node->ob)
1379                                         base = base->next;
1380                                 if (base) {
1381                                         BLI_remlink(&sce->base, base);
1382                                         BLI_addhead(&tempbase, base);
1383                                 }
1384                         }
1385                 }
1386         }
1387         
1388         /* temporal correction for circular dependencies */
1389         base = sce->base.first;
1390         while (base) {
1391                 BLI_remlink(&sce->base, base);
1392                 BLI_addhead(&tempbase, base);
1393                 //if (G.debug & G_DEBUG)
1394                 printf("cyclic %s\n", base->object->id.name);
1395                 base = sce->base.first;
1396         }
1397         
1398         sce->base = tempbase;
1399         queue_delete(nqueue);
1400         
1401         /* all groups with objects in this scene gets resorted too */
1402         scene_sort_groups(bmain, sce);
1403         
1404         if (G.debug & G_DEBUG) {
1405                 printf("\nordered\n");
1406                 for (base = sce->base.first; base; base = base->next) {
1407                         printf(" %s\n", base->object->id.name);
1408                 }
1409         }
1410
1411         /* temporal...? */
1412         sce->recalc |= SCE_PRV_CHANGED; /* test for 3d preview */
1413 }
1414
1415 /* clear all dependency graphs */
1416 void DAG_relations_tag_update(Main *bmain)
1417 {
1418         Scene *sce;
1419
1420         for (sce = bmain->scene.first; sce; sce = sce->id.next)
1421                 dag_scene_free(sce);
1422 }
1423
1424 /* rebuild dependency graph only for a given scene */
1425 void DAG_scene_relations_rebuild(Main *bmain, Scene *sce)
1426 {
1427         dag_scene_free(sce);
1428         DAG_scene_relations_update(bmain, sce);
1429 }
1430
1431 /* create dependency graph if it was cleared or didn't exist yet */
1432 void DAG_scene_relations_update(Main *bmain, Scene *sce)
1433 {
1434         if (!sce->theDag)
1435                 dag_scene_build(bmain, sce);
1436 }
1437
1438 void DAG_scene_free(Scene *sce)
1439 {
1440         if (sce->theDag) {
1441                 free_forest(sce->theDag);
1442                 MEM_freeN(sce->theDag);
1443                 sce->theDag = NULL;
1444         }
1445 }
1446
1447 static void lib_id_recalc_tag(Main *bmain, ID *id)
1448 {
1449         id->flag |= LIB_ID_RECALC;
1450         DAG_id_type_tag(bmain, GS(id->name));
1451 }
1452
1453 static void lib_id_recalc_data_tag(Main *bmain, ID *id)
1454 {
1455         id->flag |= LIB_ID_RECALC_DATA;
1456         DAG_id_type_tag(bmain, GS(id->name));
1457 }
1458
1459 /* node was checked to have lasttime != curtime and is if type ID_OB */
1460 static void flush_update_node(Main *bmain, DagNode *node, unsigned int layer, int curtime)
1461 {
1462         DagAdjList *itA;
1463         Object *ob, *obc;
1464         int oldflag, changed = 0;
1465         unsigned int all_layer;
1466         
1467         node->lasttime = curtime;
1468         
1469         ob = node->ob;
1470         if (ob && (ob->recalc & OB_RECALC_ALL)) {
1471                 all_layer = node->scelay;
1472
1473                 /* got an object node that changes, now check relations */
1474                 for (itA = node->child; itA; itA = itA->next) {
1475                         all_layer |= itA->lay;
1476                         /* the relationship is visible */
1477                         if ((itA->lay & layer)) { // XXX || (itA->node->ob == obedit)
1478                                 if (itA->node->type == ID_OB) {
1479                                         obc = itA->node->ob;
1480                                         oldflag = obc->recalc;
1481                                         
1482                                         /* got a ob->obc relation, now check if flag needs flush */
1483                                         if (ob->recalc & OB_RECALC_OB) {
1484                                                 if (itA->type & DAG_RL_OB_OB) {
1485                                                         //printf("ob %s changes ob %s\n", ob->id.name, obc->id.name);
1486                                                         obc->recalc |= OB_RECALC_OB;
1487                                                         lib_id_recalc_tag(bmain, &obc->id);
1488                                                 }
1489                                                 if (itA->type & DAG_RL_OB_DATA) {
1490                                                         //printf("ob %s changes obdata %s\n", ob->id.name, obc->id.name);
1491                                                         obc->recalc |= OB_RECALC_DATA;
1492                                                         lib_id_recalc_data_tag(bmain, &obc->id);
1493                                                 }
1494                                         }
1495                                         if (ob->recalc & OB_RECALC_DATA) {
1496                                                 if (itA->type & DAG_RL_DATA_OB) {
1497                                                         //printf("obdata %s changes ob %s\n", ob->id.name, obc->id.name);
1498                                                         obc->recalc |= OB_RECALC_OB;
1499                                                         lib_id_recalc_tag(bmain, &obc->id);
1500                                                 }
1501                                                 if (itA->type & DAG_RL_DATA_DATA) {
1502                                                         //printf("obdata %s changes obdata %s\n", ob->id.name, obc->id.name);
1503                                                         obc->recalc |= OB_RECALC_DATA;
1504                                                         lib_id_recalc_data_tag(bmain, &obc->id);
1505                                                 }
1506                                         }
1507                                         if (oldflag != obc->recalc) changed = 1;
1508                                 }
1509                         }
1510                 }
1511                 /* even nicer, we can clear recalc flags...  */
1512                 if ((all_layer & layer) == 0) { // XXX && (ob != obedit)) {
1513                         /* but existing displaylists or derivedmesh should be freed */
1514                         if (ob->recalc & OB_RECALC_DATA)
1515                                 BKE_object_free_derived_caches(ob);
1516                         
1517                         ob->recalc &= ~OB_RECALC_ALL;
1518                 }
1519         }
1520         
1521         /* check case where child changes and parent forcing obdata to change */
1522         /* should be done regardless if this ob has recalc set */
1523         /* could merge this in with loop above...? (ton) */
1524         for (itA = node->child; itA; itA = itA->next) {
1525                 /* the relationship is visible */
1526                 if ((itA->lay & layer)) {       // XXX  || (itA->node->ob == obedit)
1527                         if (itA->node->type == ID_OB) {
1528                                 obc = itA->node->ob;
1529                                 /* child moves */
1530                                 if ((obc->recalc & OB_RECALC_ALL) == OB_RECALC_OB) {
1531                                         /* parent has deforming info */
1532                                         if (itA->type & (DAG_RL_OB_DATA | DAG_RL_DATA_DATA)) {
1533                                                 // printf("parent %s changes ob %s\n", ob->id.name, obc->id.name);
1534                                                 obc->recalc |= OB_RECALC_DATA;
1535                                                 lib_id_recalc_data_tag(bmain, &obc->id);
1536                                         }
1537                                 }
1538                         }
1539                 }
1540         }
1541         
1542         /* we only go deeper if node not checked or something changed  */
1543         for (itA = node->child; itA; itA = itA->next) {
1544                 if (changed || itA->node->lasttime != curtime)
1545                         flush_update_node(bmain, itA->node, layer, curtime);
1546         }
1547         
1548 }
1549
1550 /* node was checked to have lasttime != curtime, and is of type ID_OB */
1551 static unsigned int flush_layer_node(Scene *sce, DagNode *node, int curtime)
1552 {
1553         DagAdjList *itA;
1554         
1555         node->lasttime = curtime;
1556         node->lay = node->scelay;
1557         
1558         for (itA = node->child; itA; itA = itA->next) {
1559                 if (itA->node->type == ID_OB) {
1560                         if (itA->node->lasttime != curtime) {
1561                                 itA->lay = flush_layer_node(sce, itA->node, curtime);  /* lay is only set once for each relation */
1562                         }
1563                         else {
1564                                 itA->lay = itA->node->lay;
1565                         }
1566                         
1567                         node->lay |= itA->lay;
1568                 }
1569         }
1570
1571         return node->lay;
1572 }
1573
1574 /* node was checked to have lasttime != curtime, and is of type ID_OB */
1575 static void flush_pointcache_reset(Main *bmain, Scene *scene, DagNode *node, int curtime, int reset)
1576 {
1577         DagAdjList *itA;
1578         Object *ob;
1579         
1580         node->lasttime = curtime;
1581         
1582         for (itA = node->child; itA; itA = itA->next) {
1583                 if (itA->node->type == ID_OB) {
1584                         if (itA->node->lasttime != curtime) {
1585                                 ob = (Object *)(itA->node->ob);
1586
1587                                 if (reset || (ob->recalc & OB_RECALC_ALL)) {
1588                                         if (BKE_ptcache_object_reset(scene, ob, PTCACHE_RESET_DEPSGRAPH)) {
1589                                                 ob->recalc |= OB_RECALC_DATA;
1590                                                 lib_id_recalc_data_tag(bmain, &ob->id);
1591                                         }
1592
1593                                         flush_pointcache_reset(bmain, scene, itA->node, curtime, 1);
1594                                 }
1595                                 else
1596                                         flush_pointcache_reset(bmain, scene, itA->node, curtime, 0);
1597                         }
1598                 }
1599         }
1600 }
1601
1602 /* flush layer flags to dependencies */
1603 static void dag_scene_flush_layers(Scene *sce, int lay)
1604 {
1605         DagNode *node, *firstnode;
1606         DagAdjList *itA;
1607         Base *base;
1608         int lasttime;
1609
1610         firstnode = sce->theDag->DagNode.first;  /* always scene node */
1611
1612         for (itA = firstnode->child; itA; itA = itA->next)
1613                 itA->lay = 0;
1614
1615         sce->theDag->time++;  /* so we know which nodes were accessed */
1616         lasttime = sce->theDag->time;
1617
1618         /* update layer flags in nodes */
1619         for (base = sce->base.first; base; base = base->next) {
1620                 node = dag_get_node(sce->theDag, base->object);
1621                 node->scelay = base->object->lay;
1622         }
1623
1624         /* ensure cameras are set as if they are on a visible layer, because
1625          * they ared still used for rendering or setting the camera view
1626          *
1627          * XXX, this wont work for local view / unlocked camera's */
1628         if (sce->camera) {
1629                 node = dag_get_node(sce->theDag, sce->camera);
1630                 node->scelay |= lay;
1631         }
1632
1633 #ifdef DURIAN_CAMERA_SWITCH
1634         {
1635                 TimeMarker *m;
1636
1637                 for (m = sce->markers.first; m; m = m->next) {
1638                         if (m->camera) {
1639                                 node = dag_get_node(sce->theDag, m->camera);
1640                                 node->scelay |= lay;
1641                         }
1642                 }
1643         }
1644 #endif
1645
1646         /* flush layer nodes to dependencies */
1647         for (itA = firstnode->child; itA; itA = itA->next)
1648                 if (itA->node->lasttime != lasttime && itA->node->type == ID_OB)
1649                         flush_layer_node(sce, itA->node, lasttime);
1650 }
1651
1652 static void dag_tag_renderlayers(Scene *sce, unsigned int lay)
1653 {
1654         if (sce->nodetree) {
1655                 bNode *node;
1656                 Base *base;
1657                 unsigned int lay_changed = 0;
1658                 
1659                 for (base = sce->base.first; base; base = base->next)
1660                         if (base->lay & lay)
1661                                 if (base->object->recalc)
1662                                         lay_changed |= base->lay;
1663                         
1664                 for (node = sce->nodetree->nodes.first; node; node = node->next) {
1665                         if (node->id == (ID *)sce) {
1666                                 SceneRenderLayer *srl = BLI_findlink(&sce->r.layers, node->custom1);
1667                                 if (srl && (srl->lay & lay_changed))
1668                                         nodeUpdate(sce->nodetree, node);
1669                         }
1670                 }
1671         }
1672 }
1673
1674 /* flushes all recalc flags in objects down the dependency tree */
1675 void DAG_scene_flush_update(Main *bmain, Scene *sce, unsigned int lay, const short time)
1676 {
1677         DagNode *firstnode;
1678         DagAdjList *itA;
1679         Object *ob;
1680         int lasttime;
1681         
1682         if (sce->theDag == NULL) {
1683                 printf("DAG zero... not allowed to happen!\n");
1684                 DAG_scene_relations_update(bmain, sce);
1685         }
1686         
1687         firstnode = sce->theDag->DagNode.first;  /* always scene node */
1688
1689         /* first we flush the layer flags */
1690         dag_scene_flush_layers(sce, lay);
1691
1692         /* then we use the relationships + layer info to flush update events */
1693         sce->theDag->time++;  /* so we know which nodes were accessed */
1694         lasttime = sce->theDag->time;
1695         for (itA = firstnode->child; itA; itA = itA->next)
1696                 if (itA->node->lasttime != lasttime && itA->node->type == ID_OB)
1697                         flush_update_node(bmain, itA->node, lay, lasttime);
1698
1699         /* if update is not due to time change, do pointcache clears */
1700         if (!time) {
1701                 sce->theDag->time++;  /* so we know which nodes were accessed */
1702                 lasttime = sce->theDag->time;
1703                 for (itA = firstnode->child; itA; itA = itA->next) {
1704                         if (itA->node->lasttime != lasttime && itA->node->type == ID_OB) {
1705                                 ob = (Object *)(itA->node->ob);
1706
1707                                 if (ob->recalc & OB_RECALC_ALL) {
1708                                         if (BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH)) {
1709                                                 ob->recalc |= OB_RECALC_DATA;
1710                                                 lib_id_recalc_data_tag(bmain, &ob->id);
1711                                         }
1712
1713                                         flush_pointcache_reset(bmain, sce, itA->node, lasttime, 1);
1714                                 }
1715                                 else
1716                                         flush_pointcache_reset(bmain, sce, itA->node, lasttime, 0);
1717                         }
1718                 }
1719         }
1720         
1721         dag_tag_renderlayers(sce, lay);
1722 }
1723
1724 static int object_modifiers_use_time(Object *ob)
1725 {
1726         ModifierData *md;
1727         
1728         /* check if a modifier in modifier stack needs time input */
1729         for (md = ob->modifiers.first; md; md = md->next)
1730                 if (modifier_dependsOnTime(md))
1731                         return 1;
1732         
1733         /* check whether any modifiers are animated */
1734         if (ob->adt) {
1735                 AnimData *adt = ob->adt;
1736                 FCurve *fcu;
1737                 
1738                 /* action - check for F-Curves with paths containing 'modifiers[' */
1739                 if (adt->action) {
1740                         for (fcu = adt->action->curves.first; fcu; fcu = fcu->next) {
1741                                 if (fcu->rna_path && strstr(fcu->rna_path, "modifiers["))
1742                                         return 1;
1743                         }
1744                 }
1745                 
1746                 /* This here allows modifier properties to get driven and still update properly
1747                  *
1748                  * Workaround to get [#26764] (e.g. subsurf levels not updating when animated/driven)
1749                  * working, without the updating problems ([#28525] [#28690] [#28774] [#28777]) caused
1750                  * by the RNA updates cache introduced in r.38649
1751                  */
1752                 for (fcu = adt->drivers.first; fcu; fcu = fcu->next) {
1753                         if (fcu->rna_path && strstr(fcu->rna_path, "modifiers["))
1754                                 return 1;
1755                 }
1756                 
1757                 /* XXX: also, should check NLA strips, though for now assume that nobody uses
1758                  * that and we can omit that for performance reasons... */
1759         }
1760         
1761         return 0;
1762 }
1763
1764 static short animdata_use_time(AnimData *adt)
1765 {
1766         NlaTrack *nlt;
1767         
1768         if (adt == NULL) return 0;
1769         
1770         /* check action - only if assigned, and it has anim curves */
1771         if (adt->action && adt->action->curves.first)
1772                 return 1;
1773         
1774         /* check NLA tracks + strips */
1775         for (nlt = adt->nla_tracks.first; nlt; nlt = nlt->next) {
1776                 if (nlt->strips.first)
1777                         return 1;
1778         }
1779         
1780         /* If we have drivers, more likely than not, on a frame change
1781          * they'll need updating because their owner changed
1782          * 
1783          * This is kindof a hack to get around a whole host of problems
1784          * involving drivers using non-object datablock data (which the 
1785          * depsgraph currently has no way of representing let alone correctly
1786          * dependency sort+tagging). By doing this, at least we ensure that 
1787          * some commonly attempted drivers (such as scene -> current frame;
1788          * see "Driver updates fail" thread on Bf-committers dated July 2)
1789          * will work correctly, and that other non-object datablocks will have
1790          * their drivers update at least on frame change.
1791          *
1792          * -- Aligorith, July 4 2011
1793          */
1794         if (adt->drivers.first)
1795                 return 1;
1796         
1797         return 0;
1798 }
1799
1800 static void dag_object_time_update_flags(Main *bmain, Scene *scene, Object *ob)
1801 {
1802         if (ob->constraints.first) {
1803                 bConstraint *con;
1804                 for (con = ob->constraints.first; con; con = con->next) {
1805                         bConstraintTypeInfo *cti = BKE_constraint_get_typeinfo(con);
1806                         ListBase targets = {NULL, NULL};
1807                         bConstraintTarget *ct;
1808                         
1809                         if (cti) {
1810                                 /* special case for camera tracking -- it doesn't use targets to define relations */
1811                                 if (ELEM3(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER, CONSTRAINT_TYPE_OBJECTSOLVER)) {
1812                                         ob->recalc |= OB_RECALC_OB;
1813                                 }
1814                                 else if (cti->get_constraint_targets) {
1815                                         cti->get_constraint_targets(con, &targets);
1816                                         
1817                                         for (ct = targets.first; ct; ct = ct->next) {
1818                                                 if (ct->tar) {
1819                                                         ob->recalc |= OB_RECALC_OB;
1820                                                         break;
1821                                                 }
1822                                         }
1823                                         
1824                                         if (cti->flush_constraint_targets)
1825                                                 cti->flush_constraint_targets(con, &targets, 1);
1826                                 }
1827                                 
1828                         }
1829                 }
1830         }
1831         
1832         if (ob->parent) {
1833                 /* motion path or bone child */
1834                 if (ob->parent->type == OB_CURVE || ob->parent->type == OB_ARMATURE) ob->recalc |= OB_RECALC_OB;
1835         }
1836         
1837 #if 0 // XXX old animation system
1838         if (ob->nlastrips.first) {
1839                 if (ob->dup_group) {
1840                         bActionStrip *strip;
1841                         /* this case is for groups with nla, whilst nla target has no action or nla */
1842                         for (strip = ob->nlastrips.first; strip; strip = strip->next) {
1843                                 if (strip->object)
1844                                         strip->object->recalc |= OB_RECALC_ALL;
1845                         }
1846                 }
1847         }
1848 #endif // XXX old animation system
1849         
1850         if (animdata_use_time(ob->adt)) {
1851                 ob->recalc |= OB_RECALC_OB;
1852                 ob->adt->recalc |= ADT_RECALC_ANIM;
1853         }
1854         
1855         if ((ob->adt) && (ob->type == OB_ARMATURE)) ob->recalc |= OB_RECALC_DATA;
1856         
1857         if (object_modifiers_use_time(ob)) ob->recalc |= OB_RECALC_DATA;
1858         if ((ob->pose) && (ob->pose->flag & POSE_CONSTRAINTS_TIMEDEPEND)) ob->recalc |= OB_RECALC_DATA;
1859         
1860         // XXX: scene here may not be the scene that contains the rigidbody world affecting this!
1861         if (ob->rigidbody_object && BKE_scene_check_rigidbody_active(scene))
1862                 ob->recalc |= OB_RECALC_OB;
1863         
1864         {
1865                 AnimData *adt = BKE_animdata_from_id((ID *)ob->data);
1866                 Mesh *me;
1867                 Curve *cu;
1868                 Lattice *lt;
1869                 
1870                 switch (ob->type) {
1871                         case OB_MESH:
1872                                 me = ob->data;
1873                                 if (me->key) {
1874                                         if (!(ob->shapeflag & OB_SHAPE_LOCK)) {
1875                                                 ob->recalc |= OB_RECALC_DATA;
1876                                         }
1877                                 }
1878                                 if (ob->particlesystem.first)
1879                                         ob->recalc |= OB_RECALC_DATA;
1880                                 break;
1881                         case OB_CURVE:
1882                         case OB_SURF:
1883                                 cu = ob->data;
1884                                 if (cu->key) {
1885                                         if (!(ob->shapeflag & OB_SHAPE_LOCK)) {
1886                                                 ob->recalc |= OB_RECALC_DATA;
1887                                         }
1888                                 }
1889                                 break;
1890                         case OB_FONT:
1891                                 cu = ob->data;
1892                                 if (cu->nurb.first == NULL && cu->str && cu->vfont)
1893                                         ob->recalc |= OB_RECALC_DATA;
1894                                 break;
1895                         case OB_LATTICE:
1896                                 lt = ob->data;
1897                                 if (lt->key) {
1898                                         if (!(ob->shapeflag & OB_SHAPE_LOCK)) {
1899                                                 ob->recalc |= OB_RECALC_DATA;
1900                                         }
1901                                 }
1902                                 break;
1903                         case OB_MBALL:
1904                                 if (ob->transflag & OB_DUPLI) ob->recalc |= OB_RECALC_DATA;
1905                                 break;
1906                 }
1907                 
1908                 if (animdata_use_time(adt)) {
1909                         ob->recalc |= OB_RECALC_DATA;
1910                         adt->recalc |= ADT_RECALC_ANIM;
1911                 }
1912
1913                 if (ob->particlesystem.first) {
1914                         ParticleSystem *psys = ob->particlesystem.first;
1915
1916                         for (; psys; psys = psys->next) {
1917                                 if (psys_check_enabled(ob, psys)) {
1918                                         ob->recalc |= OB_RECALC_DATA;
1919                                         break;
1920                                 }
1921                         }
1922                 }
1923         }
1924
1925         if (ob->recalc & OB_RECALC_OB)
1926                 lib_id_recalc_tag(bmain, &ob->id);
1927         if (ob->recalc & OB_RECALC_DATA)
1928                 lib_id_recalc_data_tag(bmain, &ob->id);
1929
1930 }
1931 /* flag all objects that need recalc, for changes in time for example */
1932 /* do_time: make this optional because undo resets objects to their animated locations without this */
1933 void DAG_scene_update_flags(Main *bmain, Scene *scene, unsigned int lay, const short do_time)
1934 {
1935         Base *base;
1936         Object *ob;
1937         Group *group;
1938         GroupObject *go;
1939         Scene *sce_iter;
1940
1941         /* set ob flags where animated systems are */
1942         for (SETLOOPER(scene, sce_iter, base)) {
1943                 ob = base->object;
1944
1945                 if (do_time) {
1946                         /* now if DagNode were part of base, the node->lay could be checked... */
1947                         /* we do all now, since the scene_flush checks layers and clears recalc flags even */
1948                         
1949                         /* NOTE: "sce_iter" not "scene" so that rigidbodies in background scenes work 
1950                          * (i.e. muting + rbw availability can be checked and tagged properly) [#33970] 
1951                          */
1952                         dag_object_time_update_flags(bmain, sce_iter, ob);
1953                 }
1954
1955                 /* handled in next loop */
1956                 if (ob->dup_group)
1957                         ob->dup_group->id.flag |= LIB_DOIT;
1958         }
1959
1960         if (do_time) {
1961                 /* we do groups each once */
1962                 for (group = bmain->group.first; group; group = group->id.next) {
1963                         if (group->id.flag & LIB_DOIT) {
1964                                 for (go = group->gobject.first; go; go = go->next) {
1965                                         dag_object_time_update_flags(bmain, scene, go->ob);
1966                                 }
1967                         }
1968                 }
1969         }
1970
1971         for (sce_iter = scene; sce_iter; sce_iter = sce_iter->set)
1972                 DAG_scene_flush_update(bmain, sce_iter, lay, 1);
1973         
1974         if (do_time) {
1975                 /* test: set time flag, to disable baked systems to update */
1976                 for (SETLOOPER(scene, sce_iter, base)) {
1977                         ob = base->object;
1978                         if (ob->recalc)
1979                                 ob->recalc |= OB_RECALC_TIME;
1980                 }
1981
1982                 /* hrmf... an exception to look at once, for invisible camera object we do it over */
1983                 if (scene->camera)
1984                         dag_object_time_update_flags(bmain, scene, scene->camera);
1985         }
1986
1987         /* and store the info in groupobject */
1988         for (group = bmain->group.first; group; group = group->id.next) {
1989                 if (group->id.flag & LIB_DOIT) {
1990                         for (go = group->gobject.first; go; go = go->next) {
1991                                 go->recalc = go->ob->recalc;
1992                                 // printf("ob %s recalc %d\n", go->ob->id.name, go->recalc);
1993                         }
1994                         group->id.flag &= ~LIB_DOIT;
1995                 }
1996         }
1997         
1998 }
1999
2000 /* struct returned by DagSceneLayer */
2001 typedef struct DagSceneLayer {
2002         struct DagSceneLayer *next, *prev;
2003         Scene *scene;
2004         unsigned int layer;
2005 } DagSceneLayer;
2006
2007 /* returns visible scenes with valid DAG */
2008 static void dag_current_scene_layers(Main *bmain, ListBase *lb)
2009 {
2010         wmWindowManager *wm;
2011         wmWindow *win;
2012         
2013         lb->first = lb->last = NULL;
2014
2015         /* if we have a windowmanager, look into windows */
2016         if ((wm = bmain->wm.first)) {
2017                 
2018                 flag_listbase_ids(&bmain->scene, LIB_DOIT, 1);
2019
2020                 for (win = wm->windows.first; win; win = win->next) {
2021                         if (win->screen && win->screen->scene->theDag) {
2022                                 Scene *scene = win->screen->scene;
2023                                 
2024                                 if (scene->id.flag & LIB_DOIT) {
2025                                         DagSceneLayer *dsl = MEM_mallocN(sizeof(DagSceneLayer), "dag scene layer");
2026                                         
2027                                         BLI_addtail(lb, dsl);
2028                                         
2029                                         dsl->scene = scene;
2030                                         dsl->layer = BKE_screen_visible_layers(win->screen, scene);
2031                                         
2032                                         scene->id.flag &= ~LIB_DOIT;
2033                                 }
2034                         }
2035                 }
2036         }
2037         else {
2038                 /* if not, use the first sce */
2039                 DagSceneLayer *dsl = MEM_mallocN(sizeof(DagSceneLayer), "dag scene layer");
2040                 
2041                 BLI_addtail(lb, dsl);
2042                 
2043                 dsl->scene = bmain->scene.first;
2044                 dsl->layer = dsl->scene->lay;
2045
2046                 /* XXX for background mode, we should get the scene
2047                  * from somewhere, for the -S option, but it's in
2048                  * the context, how to get it here? */
2049         }
2050 }
2051
2052 void DAG_on_visible_update(Main *bmain, const short do_time)
2053 {
2054         ListBase listbase;
2055         DagSceneLayer *dsl;
2056         
2057         /* get list of visible scenes and layers */
2058         dag_current_scene_layers(bmain, &listbase);
2059         
2060         for (dsl = listbase.first; dsl; dsl = dsl->next) {
2061                 Scene *scene = dsl->scene;
2062                 Scene *sce_iter;
2063                 Base *base;
2064                 Object *ob;
2065                 Group *group;
2066                 GroupObject *go;
2067                 DagNode *node;
2068                 unsigned int lay = dsl->layer, oblay;
2069         
2070                 /* derivedmeshes and displists are not saved to file so need to be
2071                  * remade, tag them so they get remade in the scene update loop,
2072                  * note armature poses or object matrices are preserved and do not
2073                  * require updates, so we skip those */
2074                 dag_scene_flush_layers(scene, lay);
2075
2076                 for (SETLOOPER(scene, sce_iter, base)) {
2077                         ob = base->object;
2078                         node = (sce_iter->theDag) ? dag_get_node(sce_iter->theDag, ob) : NULL;
2079                         oblay = (node) ? node->lay : ob->lay;
2080
2081                         if ((oblay & lay) & ~scene->lay_updated) {
2082                                 if (ELEM6(ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2083                                         ob->recalc |= OB_RECALC_DATA;
2084                                 if (ob->dup_group) 
2085                                         ob->dup_group->id.flag |= LIB_DOIT;
2086                         }
2087                 }
2088
2089                 for (group = bmain->group.first; group; group = group->id.next) {
2090                         if (group->id.flag & LIB_DOIT) {
2091                                 for (go = group->gobject.first; go; go = go->next) {
2092                                         if (ELEM6(go->ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2093                                                 go->ob->recalc |= OB_RECALC_DATA;
2094                                         if (go->ob->proxy_from)
2095                                                 go->ob->recalc |= OB_RECALC_OB;
2096                                 }
2097                                 
2098                                 group->id.flag &= ~LIB_DOIT;
2099                         }
2100                 }
2101
2102                 /* now tag update flags, to ensure deformers get calculated on redraw */
2103                 DAG_scene_update_flags(bmain, scene, lay, do_time);
2104                 scene->lay_updated |= lay;
2105         }
2106         
2107         BLI_freelistN(&listbase);
2108
2109         /* hack to get objects updating on layer changes */
2110         DAG_id_type_tag(bmain, ID_OB);
2111
2112         /* so masks update on load */
2113         if (bmain->mask.first) {
2114                 Mask *mask;
2115
2116                 for (mask = bmain->mask.first; mask; mask = mask->id.next) {
2117                         DAG_id_tag_update(&mask->id, 0);
2118                 }
2119         }
2120 }
2121
2122 static void dag_id_flush_update__isDependentTexture(void *userData, Object *UNUSED(ob), ID **idpoin)
2123 {
2124         struct { ID *id; int is_dependent; } *data = userData;
2125         
2126         if (*idpoin && GS((*idpoin)->name) == ID_TE) {
2127                 if (data->id == (*idpoin))
2128                         data->is_dependent = 1;
2129         }
2130 }
2131
2132 static void dag_id_flush_update(Main *bmain, Scene *sce, ID *id)
2133 {
2134         Object *obt, *ob = NULL;
2135         short idtype;
2136
2137         /* here we flush a few things before actual scene wide flush, mostly
2138          * due to only objects and not other datablocks being in the depsgraph */
2139
2140         /* set flags & pointcache for object */
2141         if (GS(id->name) == ID_OB) {
2142                 ob = (Object *)id;
2143                 BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH);
2144
2145                 if (ob->recalc & OB_RECALC_DATA) {
2146                         /* all users of this ob->data should be checked */
2147                         id = ob->data;
2148
2149                         /* no point in trying in this cases */
2150                         if (id && id->us <= 1) {
2151                                 dag_editors_id_update(bmain, id);
2152                                 id = NULL;
2153                         }
2154                 }
2155         }
2156
2157         /* set flags & pointcache for object data */
2158         if (id) {
2159                 idtype = GS(id->name);
2160
2161
2162                 if (OB_DATA_SUPPORT_ID(idtype)) {
2163                         for (obt = bmain->object.first; obt; obt = obt->id.next) {
2164                                 if (!(ob && obt == ob) && obt->data == id) {
2165                                         obt->recalc |= OB_RECALC_DATA;
2166                                         lib_id_recalc_data_tag(bmain, &obt->id);
2167                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2168                                 }
2169                         }
2170                 }
2171                 
2172                 /* set flags based on textures - can influence depgraph via modifiers */
2173                 if (idtype == ID_TE) {
2174                         for (obt = bmain->object.first; obt; obt = obt->id.next) {
2175                                 struct { ID *id; int is_dependent; } data;
2176                                 data.id = id;
2177                                 data.is_dependent = 0;
2178
2179                                 modifiers_foreachIDLink(obt, dag_id_flush_update__isDependentTexture, &data);
2180                                 if (data.is_dependent) {
2181                                         obt->recalc |= OB_RECALC_DATA;
2182                                         lib_id_recalc_data_tag(bmain, &obt->id);
2183                                 }
2184
2185                                 /* particle settings can use the texture as well */
2186                                 if (obt->particlesystem.first) {
2187                                         ParticleSystem *psys = obt->particlesystem.first;
2188                                         MTex **mtexp, *mtex;
2189                                         int a;
2190                                         for (; psys; psys = psys->next) {
2191                                                 mtexp = psys->part->mtex;
2192                                                 for (a = 0; a < MAX_MTEX; a++, mtexp++) {
2193                                                         mtex = *mtexp;
2194                                                         if (mtex && mtex->tex == (Tex *)id) {
2195                                                                 obt->recalc |= OB_RECALC_DATA;
2196                                                                 lib_id_recalc_data_tag(bmain, &obt->id);
2197
2198                                                                 if (mtex->mapto & PAMAP_INIT)
2199                                                                         psys->recalc |= PSYS_RECALC_RESET;
2200                                                                 if (mtex->mapto & PAMAP_CHILD)
2201                                                                         psys->recalc |= PSYS_RECALC_CHILD;
2202
2203                                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2204                                                         }
2205                                                 }
2206                                         }
2207                                 }
2208                         }
2209                 }
2210                 
2211                 /* set flags based on ShapeKey */
2212                 if (idtype == ID_KE) {
2213                         for (obt = bmain->object.first; obt; obt = obt->id.next) {
2214                                 Key *key = BKE_key_from_object(obt);
2215                                 if (!(ob && obt == ob) && ((ID *)key == id)) {
2216                                         obt->flag |= (OB_RECALC_OB | OB_RECALC_DATA);
2217                                         lib_id_recalc_tag(bmain, &obt->id);
2218                                         lib_id_recalc_data_tag(bmain, &obt->id);
2219                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2220                                 }
2221                         }
2222                 }
2223                 
2224                 /* set flags based on particle settings */
2225                 if (idtype == ID_PA) {
2226                         ParticleSystem *psys;
2227                         for (obt = bmain->object.first; obt; obt = obt->id.next)
2228                                 for (psys = obt->particlesystem.first; psys; psys = psys->next)
2229                                         if (&psys->part->id == id)
2230                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2231                 }
2232
2233                 if (idtype == ID_MC) {
2234                         MovieClip *clip = (MovieClip *) id;
2235
2236                         BKE_tracking_dopesheet_tag_update(&clip->tracking);
2237
2238                         for (obt = bmain->object.first; obt; obt = obt->id.next) {
2239                                 bConstraint *con;
2240                                 for (con = obt->constraints.first; con; con = con->next) {
2241                                         bConstraintTypeInfo *cti = BKE_constraint_get_typeinfo(con);
2242                                         if (ELEM3(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER,
2243                                                   CONSTRAINT_TYPE_OBJECTSOLVER))
2244                                         {
2245                                                 obt->recalc |= OB_RECALC_OB;
2246                                                 break;
2247                                         }
2248                                 }
2249                         }
2250
2251                         if (sce->nodetree) {
2252                                 bNode *node;
2253
2254                                 for (node = sce->nodetree->nodes.first; node; node = node->next) {
2255                                         if (node->id == id) {
2256                                                 nodeUpdate(sce->nodetree, node);
2257                                         }
2258                                 }
2259                         }
2260                 }
2261
2262                 if (idtype == ID_MSK) {
2263                         if (sce->nodetree) {
2264                                 bNode *node;
2265
2266                                 for (node = sce->nodetree->nodes.first; node; node = node->next) {
2267                                         if (node->id == id) {
2268                                                 nodeUpdate(sce->nodetree, node);
2269                                         }
2270                                 }
2271                         }
2272                 }
2273
2274                 /* camera's matrix is used to orient reconstructed stuff,
2275                  * so it should happen tracking-related constraints recalculation
2276                  * when camera is changing (sergey) */
2277                 if (sce->camera && &sce->camera->id == id) {
2278                         MovieClip *clip = BKE_object_movieclip_get(sce, sce->camera, 1);
2279
2280                         if (clip)
2281                                 dag_id_flush_update(bmain, sce, &clip->id);
2282                 }
2283
2284                 /* update editors */
2285                 dag_editors_id_update(bmain, id);
2286         }
2287 }
2288
2289 void DAG_ids_flush_tagged(Main *bmain)
2290 {
2291         ListBase listbase;
2292         DagSceneLayer *dsl;
2293         ListBase *lbarray[MAX_LIBARRAY];
2294         int a, do_flush = FALSE;
2295         
2296         /* get list of visible scenes and layers */
2297         dag_current_scene_layers(bmain, &listbase);
2298
2299         if (listbase.first == NULL)
2300                 return;
2301
2302         /* loop over all ID types */
2303         a  = set_listbasepointers(bmain, lbarray);
2304
2305         while (a--) {
2306                 ListBase *lb = lbarray[a];
2307                 ID *id = lb->first;
2308
2309                 /* we tag based on first ID type character to avoid 
2310                  * looping over all ID's in case there are no tags */
2311                 if (id && bmain->id_tag_update[id->name[0]]) {
2312                         for (; id; id = id->next) {
2313                                 if (id->flag & (LIB_ID_RECALC | LIB_ID_RECALC_DATA)) {
2314                                         
2315                                         for (dsl = listbase.first; dsl; dsl = dsl->next)
2316                                                 dag_id_flush_update(bmain, dsl->scene, id);
2317                                         
2318                                         do_flush = TRUE;
2319                                 }
2320                         }
2321                 }
2322         }
2323
2324         /* flush changes to other objects */
2325         if (do_flush) {
2326                 for (dsl = listbase.first; dsl; dsl = dsl->next)
2327                         DAG_scene_flush_update(bmain, dsl->scene, dsl->layer, 0);
2328         }
2329         
2330         BLI_freelistN(&listbase);
2331 }
2332
2333 void DAG_ids_check_recalc(Main *bmain, Scene *scene, int time)
2334 {
2335         ListBase *lbarray[MAX_LIBARRAY];
2336         int a, updated = 0;
2337
2338         /* loop over all ID types */
2339         a  = set_listbasepointers(bmain, lbarray);
2340
2341         while (a--) {
2342                 ListBase *lb = lbarray[a];
2343                 ID *id = lb->first;
2344
2345                 /* we tag based on first ID type character to avoid 
2346                  * looping over all ID's in case there are no tags */
2347                 if (id &&
2348 #ifdef WITH_FREESTYLE
2349                     /* XXX very weak... added check for '27' to ignore freestyle added objects */
2350                     id->name[2] > 27 &&
2351 #endif
2352                     bmain->id_tag_update[id->name[0]])
2353                 {
2354                         updated = 1;
2355                         break;
2356                 }
2357         }
2358
2359         dag_editors_scene_update(bmain, scene, (updated || time));
2360 }
2361
2362 void DAG_ids_clear_recalc(Main *bmain)
2363 {
2364         ListBase *lbarray[MAX_LIBARRAY];
2365         bNodeTree *ntree;
2366         int a;
2367
2368         /* loop over all ID types */
2369         a  = set_listbasepointers(bmain, lbarray);
2370
2371         while (a--) {
2372                 ListBase *lb = lbarray[a];
2373                 ID *id = lb->first;
2374
2375                 /* we tag based on first ID type character to avoid 
2376                  * looping over all ID's in case there are no tags */
2377                 if (id && bmain->id_tag_update[id->name[0]]) {
2378                         for (; id; id = id->next) {
2379                                 if (id->flag & (LIB_ID_RECALC | LIB_ID_RECALC_DATA))
2380                                         id->flag &= ~(LIB_ID_RECALC | LIB_ID_RECALC_DATA);
2381
2382                                 /* some ID's contain semi-datablock nodetree */
2383                                 ntree = ntreeFromID(id);
2384                                 if (ntree && (ntree->id.flag & (LIB_ID_RECALC | LIB_ID_RECALC_DATA)))
2385                                         ntree->id.flag &= ~(LIB_ID_RECALC | LIB_ID_RECALC_DATA);
2386                         }
2387                 }
2388         }
2389
2390         memset(bmain->id_tag_update, 0, sizeof(bmain->id_tag_update));
2391 }
2392
2393 void DAG_id_tag_update_ex(Main *bmain, ID *id, short flag)
2394 {
2395         if (id == NULL) return;
2396
2397         /* tag ID for update */
2398         if (flag) {
2399                 if (flag & OB_RECALC_OB)
2400                         lib_id_recalc_tag(bmain, id);
2401                 if (flag & (OB_RECALC_DATA | PSYS_RECALC))
2402                         lib_id_recalc_data_tag(bmain, id);
2403         }
2404         else
2405                 lib_id_recalc_tag(bmain, id);
2406
2407         /* flag is for objects and particle systems */
2408         if (flag) {
2409                 Object *ob;
2410                 short idtype = GS(id->name);
2411
2412                 if (idtype == ID_OB) {
2413                         /* only quick tag */
2414                         ob = (Object *)id;
2415                         ob->recalc |= (flag & OB_RECALC_ALL);
2416                 }
2417                 else if (idtype == ID_PA) {
2418                         ParticleSystem *psys;
2419                         /* this is weak still, should be done delayed as well */
2420                         for (ob = bmain->object.first; ob; ob = ob->id.next) {
2421                                 for (psys = ob->particlesystem.first; psys; psys = psys->next) {
2422                                         if (&psys->part->id == id) {
2423                                                 ob->recalc |= (flag & OB_RECALC_ALL);
2424                                                 psys->recalc |= (flag & PSYS_RECALC);
2425                                                 lib_id_recalc_tag(bmain, &ob->id);
2426                                                 lib_id_recalc_data_tag(bmain, &ob->id);
2427                                         }
2428                                 }
2429                         }
2430                 }
2431                 else if (idtype == ID_VF) {
2432                         /* this is weak still, should be done delayed as well */
2433                         for (ob = bmain->object.first; ob; ob = ob->id.next) {
2434                                 if (ob->type == OB_FONT) {
2435                                         Curve *cu = ob->data;
2436
2437                                         if (ELEM4((struct VFont *)id, cu->vfont, cu->vfontb, cu->vfonti, cu->vfontbi)) {
2438                                                 ob->recalc |= (flag & OB_RECALC_ALL);
2439                                         }
2440                                 }
2441                         }
2442                 }
2443                 else {
2444                         /* disable because this is called on various ID types automatically.
2445                          * where printing warning is not useful. for now just ignore */
2446                         /* BLI_assert(!"invalid flag for this 'idtype'"); */
2447                 }
2448         }
2449 }
2450
2451 void DAG_id_tag_update(ID *id, short flag)
2452 {
2453         DAG_id_tag_update_ex(G.main, id, flag);
2454 }
2455
2456 void DAG_id_type_tag(Main *bmain, short idtype)
2457 {
2458         if (idtype == ID_NT) {
2459                 /* stupid workaround so parent datablocks of nested nodetree get looped
2460                  * over when we loop over tagged datablock types */
2461                 DAG_id_type_tag(bmain, ID_MA);
2462                 DAG_id_type_tag(bmain, ID_TE);
2463                 DAG_id_type_tag(bmain, ID_LA);
2464                 DAG_id_type_tag(bmain, ID_WO);
2465                 DAG_id_type_tag(bmain, ID_SCE);
2466         }
2467
2468         bmain->id_tag_update[((char *)&idtype)[0]] = 1;
2469 }
2470
2471 int DAG_id_type_tagged(Main *bmain, short idtype)
2472 {
2473         return bmain->id_tag_update[((char *)&idtype)[0]];
2474 }
2475
2476 #if 0 // UNUSED
2477 /* recursively descends tree, each node only checked once */
2478 /* node is checked to be of type object */
2479 static int parent_check_node(DagNode *node, int curtime)
2480 {
2481         DagAdjList *itA;
2482         
2483         node->lasttime = curtime;
2484         
2485         if (node->color == DAG_GRAY)
2486                 return DAG_GRAY;
2487         
2488         for (itA = node->child; itA; itA = itA->next) {
2489                 if (itA->node->type == ID_OB) {
2490                         
2491                         if (itA->node->color == DAG_GRAY)
2492                                 return DAG_GRAY;
2493
2494                         /* descend if not done */
2495                         if (itA->node->lasttime != curtime) {
2496                                 itA->node->color = parent_check_node(itA->node, curtime);
2497                         
2498                                 if (itA->node->color == DAG_GRAY)
2499                                         return DAG_GRAY;
2500                         }
2501                 }
2502         }
2503         
2504         return DAG_WHITE;
2505 }
2506 #endif
2507
2508 /* ******************* DAG FOR ARMATURE POSE ***************** */
2509
2510 /* we assume its an armature with pose */
2511 void DAG_pose_sort(Object *ob)
2512 {
2513         bPose *pose = ob->pose;
2514         bPoseChannel *pchan;
2515         bConstraint *con;
2516         DagNode *node;
2517         DagNode *node2, *node3;
2518         DagNode *rootnode;
2519         DagForest *dag;
2520         DagNodeQueue *nqueue;
2521         DagAdjList *itA;
2522         ListBase tempbase;
2523         int skip = 0;
2524         
2525         dag = dag_init();
2526         ugly_hack_sorry = 0;  /* no ID structs */
2527
2528         rootnode = dag_add_node(dag, NULL);  /* node->ob becomes NULL */
2529         
2530         /* we add the hierarchy and the constraints */
2531         for (pchan = pose->chanbase.first; pchan; pchan = pchan->next) {
2532                 int addtoroot = 1;
2533                 
2534                 node = dag_get_node(dag, pchan);
2535                 
2536                 if (pchan->parent) {
2537                         node2 = dag_get_node(dag, pchan->parent);
2538                         dag_add_relation(dag, node2, node, 0, "Parent Relation");
2539                         addtoroot = 0;
2540                 }
2541                 for (con = pchan->constraints.first; con; con = con->next) {
2542                         bConstraintTypeInfo *cti = BKE_constraint_get_typeinfo(con);
2543                         ListBase targets = {NULL, NULL};
2544                         bConstraintTarget *ct;
2545                         
2546                         if (cti && cti->get_constraint_targets) {
2547                                 cti->get_constraint_targets(con, &targets);
2548                                 
2549                                 for (ct = targets.first; ct; ct = ct->next) {
2550                                         if (ct->tar == ob && ct->subtarget[0]) {
2551                                                 bPoseChannel *target = BKE_pose_channel_find_name(ob->pose, ct->subtarget);
2552                                                 if (target) {
2553                                                         node2 = dag_get_node(dag, target);
2554                                                         dag_add_relation(dag, node2, node, 0, "Pose Constraint");
2555                                                         
2556                                                         if (con->type == CONSTRAINT_TYPE_KINEMATIC) {
2557                                                                 bKinematicConstraint *data = (bKinematicConstraint *)con->data;
2558                                                                 bPoseChannel *parchan;
2559                                                                 int segcount = 0;
2560                                                                 
2561                                                                 /* exclude tip from chain? */
2562                                                                 if (!(data->flag & CONSTRAINT_IK_TIP))
2563                                                                         parchan = pchan->parent;
2564                                                                 else
2565                                                                         parchan = pchan;
2566                                                                 
2567                                                                 /* Walk to the chain's root */
2568                                                                 while (parchan) {
2569                                                                         node3 = dag_get_node(dag, parchan);
2570                                                                         dag_add_relation(dag, node2, node3, 0, "IK Constraint");
2571                                                                         
2572                                                                         segcount++;
2573                                                                         if (segcount == data->rootbone || segcount > 255) break;  /* 255 is weak */
2574                                                                         parchan = parchan->parent;
2575                                                                 }
2576                                                         }
2577                                                 }
2578                                         }
2579                                 }
2580                                 
2581                                 if (cti->flush_constraint_targets)
2582                                         cti->flush_constraint_targets(con, &targets, 1);
2583                         }
2584                 }
2585                 if (addtoroot == 1) {
2586                         dag_add_relation(dag, rootnode, node, 0, "Root Bone Relation");
2587                 }
2588         }
2589
2590         dag_check_cycle(dag);
2591         
2592         /* now we try to sort... */
2593         tempbase.first = tempbase.last = NULL;
2594
2595         nqueue = queue_create(DAGQUEUEALLOC);
2596         
2597         /* tag nodes unchecked */
2598         for (node = dag->DagNode.first; node; node = node->next)
2599                 node->color = DAG_WHITE;
2600         
2601         rootnode->color = DAG_GRAY;
2602         push_stack(nqueue, rootnode);  
2603         
2604         while (nqueue->count) {
2605                 
2606                 skip = 0;
2607                 node = get_top_node_queue(nqueue);
2608                 
2609                 itA = node->child;
2610                 while (itA != NULL) {
2611                         if (itA->node->color == DAG_WHITE) {
2612                                 itA->node->color = DAG_GRAY;
2613                                 push_stack(nqueue, itA->node);
2614                                 skip = 1;
2615                                 break;
2616                         }
2617                         itA = itA->next;
2618                 }
2619                 
2620                 if (!skip) {
2621                         if (node) {
2622                                 node = pop_queue(nqueue);
2623                                 if (node->ob == NULL)  /* we are done */
2624                                         break;
2625                                 node->color = DAG_BLACK;
2626                                 
2627                                 /* put node in new list */
2628                                 BLI_remlink(&pose->chanbase, node->ob);
2629                                 BLI_addhead(&tempbase, node->ob);
2630                         }
2631                 }
2632         }
2633         
2634         /* temporal correction for circular dependencies */
2635         while (pose->chanbase.first) {
2636                 pchan = pose->chanbase.first;
2637                 BLI_remlink(&pose->chanbase, pchan);
2638                 BLI_addhead(&tempbase, pchan);
2639
2640                 printf("cyclic %s\n", pchan->name);
2641         }
2642         
2643         pose->chanbase = tempbase;
2644         queue_delete(nqueue);
2645         
2646 //      printf("\nordered\n");
2647 //      for (pchan = pose->chanbase.first; pchan; pchan = pchan->next) {
2648 //              printf(" %s\n", pchan->name);
2649 //      }
2650         
2651         free_forest(dag);
2652         MEM_freeN(dag);
2653         
2654         ugly_hack_sorry = 1;
2655 }
2656
2657 /* ************************ DAG DEBUGGING ********************* */
2658
2659 void DAG_print_dependencies(Main *bmain, Scene *scene, Object *ob)
2660 {
2661         /* utility for debugging dependencies */
2662         dag_print_dependencies = 1;
2663
2664         if (ob && (ob->mode & OB_MODE_POSE)) {
2665                 printf("\nDEPENDENCY RELATIONS for %s\n\n", ob->id.name + 2);
2666                 DAG_pose_sort(ob);
2667         }
2668         else {
2669                 printf("\nDEPENDENCY RELATIONS for %s\n\n", scene->id.name + 2);
2670                 DAG_scene_relations_rebuild(bmain, scene);
2671         }
2672         
2673         dag_print_dependencies = 0;
2674 }
2675