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