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