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