45c9d0b874eebb623f1e23a72e0e6ca0ec9b11a3
[blender.git] / source / blender / blenkernel / intern / depsgraph.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL/BL DUAL 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. The Blender
10  * Foundation also sells licenses for use in proprietary software under
11  * the Blender License.  See http://www.blender.org/BL/ for information
12  * about this.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2004 Blender Foundation.
24  * All rights reserved.
25  *
26  * Contributor(s): none yet.
27  *
28  * ***** END GPL/BL DUAL LICENSE BLOCK *****
29  */
30  
31 #include <stdio.h>
32 #include <string.h>
33 #include <math.h>
34
35 #ifdef _WIN32
36 #include "BLI_winstuff.h"
37 #endif
38
39 //#include "BMF_Api.h"
40
41 #include "BLI_blenlib.h"
42 #include "BLI_arithb.h"
43
44 #include "DNA_action_types.h"
45 #include "DNA_armature_types.h"
46 #include "DNA_curve_types.h"
47 #include "DNA_ID.h"
48 #include "DNA_effect_types.h"
49 #include "DNA_lattice_types.h"
50 #include "DNA_key_types.h"
51 #include "DNA_mesh_types.h"
52 #include "DNA_modifier_types.h"
53 #include "DNA_object_types.h"
54 #include "DNA_object_force.h"
55 #include "DNA_object_fluidsim.h"
56 #include "DNA_oops_types.h"
57 #include "DNA_scene_types.h"
58 #include "DNA_screen_types.h"
59 #include "DNA_space_types.h"
60 #include "DNA_view2d_types.h"
61
62 #include "BKE_action.h"
63 #include "BKE_global.h"
64 #include "BKE_key.h"
65 #include "BKE_mball.h"
66 #include "BKE_modifier.h"
67 #include "BKE_utildefines.h"
68
69 #include "MEM_guardedalloc.h"
70 #include "blendef.h"
71
72  
73  #include "depsgraph_private.h"
74  
75 /* Queue and stack operations for dag traversal 
76  *
77  * the queue store a list of freenodes to avoid successives alloc/dealloc
78  */
79
80 DagNodeQueue * queue_create (int slots) 
81 {
82         DagNodeQueue * queue;
83         DagNodeQueueElem * elem;
84         int i;
85         
86         queue = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
87         queue->freenodes = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
88         queue->count = 0;
89         queue->maxlevel = 0;
90         queue->first = queue->last = NULL;
91         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem3");
92         elem->node = NULL;
93         elem->next = NULL;
94         queue->freenodes->first = queue->freenodes->last = elem;
95         
96         for (i = 1; i <slots;i++) {
97                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem4");
98                 elem->node = NULL;
99                 elem->next = NULL;
100                 queue->freenodes->last->next = elem;
101                 queue->freenodes->last = elem;
102         }
103         queue->freenodes->count = slots;
104         return queue;
105 }
106
107 void queue_raz(DagNodeQueue *queue)
108 {
109         DagNodeQueueElem * elem;
110         
111         elem = queue->first;
112         if (queue->freenodes->last)
113                 queue->freenodes->last->next = elem;
114         else
115                 queue->freenodes->first = queue->freenodes->last = elem;
116         
117         elem->node = NULL;
118         queue->freenodes->count++;
119         while (elem->next) {
120                 elem = elem->next;
121                 elem->node = NULL;
122                 queue->freenodes->count++;
123         }
124         queue->freenodes->last = elem;
125         queue->count = 0;
126 }
127
128 void queue_delete(DagNodeQueue *queue)
129 {
130         DagNodeQueueElem * elem;
131         DagNodeQueueElem * temp;
132         
133         elem = queue->first;
134         while (elem) {
135                 temp = elem;
136                 elem = elem->next;
137                 MEM_freeN(temp);
138         }
139         
140         elem = queue->freenodes->first;
141         while (elem) {
142                 temp = elem;
143                 elem = elem->next;
144                 MEM_freeN(temp);
145         }
146         
147         MEM_freeN(queue->freenodes);                    
148         MEM_freeN(queue);                       
149 }
150
151 /* insert in queue, remove in front */
152 void push_queue(DagNodeQueue *queue, DagNode *node)
153 {
154         DagNodeQueueElem * elem;
155         int i;
156
157         if (node == NULL) {
158                 fprintf(stderr,"pushing null node \n");
159                 return;
160         }
161         /*fprintf(stderr,"BFS push : %s %d\n",((ID *) node->ob)->name, queue->count);*/
162
163         elem = queue->freenodes->first;
164         if (elem != NULL) {
165                 queue->freenodes->first = elem->next;
166                 if ( queue->freenodes->last == elem) {
167                         queue->freenodes->last = NULL;
168                         queue->freenodes->first = NULL;
169                 }
170                 queue->freenodes->count--;
171         } else { /* alllocating more */         
172                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
173                 elem->node = NULL;
174                 elem->next = NULL;
175                 queue->freenodes->first = queue->freenodes->last = elem;
176
177                 for (i = 1; i <DAGQUEUEALLOC;i++) {
178                         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
179                         elem->node = NULL;
180                         elem->next = NULL;
181                         queue->freenodes->last->next = elem;
182                         queue->freenodes->last = elem;
183                 }
184                 queue->freenodes->count = DAGQUEUEALLOC;
185                         
186                 elem = queue->freenodes->first; 
187                 queue->freenodes->first = elem->next;   
188         }
189         elem->next = NULL;
190         elem->node = node;
191         if (queue->last != NULL)
192                 queue->last->next = elem;
193         queue->last = elem;
194         if (queue->first == NULL) {
195                 queue->first = elem;
196         }
197         queue->count++;
198 }
199
200
201 /* insert in front, remove in front */
202 void push_stack(DagNodeQueue *queue, DagNode *node)
203 {
204         DagNodeQueueElem * elem;
205         int i;
206
207         elem = queue->freenodes->first; 
208         if (elem != NULL) {
209                 queue->freenodes->first = elem->next;
210                 if ( queue->freenodes->last == elem) {
211                         queue->freenodes->last = NULL;
212                         queue->freenodes->first = NULL;
213                 }
214                 queue->freenodes->count--;
215         } else { /* alllocating more */
216                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
217                 elem->node = NULL;
218                 elem->next = NULL;
219                 queue->freenodes->first = queue->freenodes->last = elem;
220
221                 for (i = 1; i <DAGQUEUEALLOC;i++) {
222                         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
223                         elem->node = NULL;
224                         elem->next = NULL;
225                         queue->freenodes->last->next = elem;
226                         queue->freenodes->last = elem;
227                 }
228                 queue->freenodes->count = DAGQUEUEALLOC;
229                         
230                 elem = queue->freenodes->first; 
231                 queue->freenodes->first = elem->next;   
232         }
233         elem->next = queue->first;
234         elem->node = node;
235         queue->first = elem;
236         if (queue->last == NULL)
237                 queue->last = elem;
238         queue->count++;
239 }
240
241
242 DagNode * pop_queue(DagNodeQueue *queue)
243 {
244         DagNodeQueueElem * elem;
245         DagNode *node;
246
247         elem = queue->first;
248         if (elem) {
249                 queue->first = elem->next;
250                 if (queue->last == elem) {
251                         queue->last=NULL;
252                         queue->first=NULL;
253                 }
254                 queue->count--;
255                 if (queue->freenodes->last)
256                         queue->freenodes->last->next=elem;
257                 queue->freenodes->last=elem;
258                 if (queue->freenodes->first == NULL)
259                         queue->freenodes->first=elem;
260                 node = elem->node;
261                 elem->node = NULL;
262                 elem->next = NULL;
263                 queue->freenodes->count++;
264                 return node;
265         } else {
266                 fprintf(stderr,"return null \n");
267                 return NULL;
268         }
269 }
270
271 void    *pop_ob_queue(struct DagNodeQueue *queue) {
272         return(pop_queue(queue)->ob);
273 }
274
275 DagNode * get_top_node_queue(DagNodeQueue *queue) 
276 {
277         return queue->first->node;
278 }
279
280 int             queue_count(struct DagNodeQueue *queue){
281         return queue->count;
282 }
283
284
285 DagForest * dag_init()
286 {
287         DagForest *forest;
288         /* use callocN to init all zero */
289         forest = MEM_callocN(sizeof(DagForest),"DAG root");
290         return forest;
291 }
292
293 static void dag_add_driver_relation(Ipo *ipo, DagForest *dag, DagNode *node, int isdata)
294 {
295         IpoCurve *icu;
296         DagNode *node1;
297         
298         for(icu= ipo->curve.first; icu; icu= icu->next) {
299                 if(icu->driver && icu->driver->ob) {
300                         node1 = dag_get_node(dag, icu->driver->ob);
301                         if(icu->driver->blocktype==ID_AR)
302                                 dag_add_relation(dag, node1, node, isdata?DAG_RL_DATA_DATA:DAG_RL_DATA_OB);
303                         else
304                                 dag_add_relation(dag, node1, node, isdata?DAG_RL_OB_DATA:DAG_RL_OB_OB);
305                 }
306         }
307 }
308
309
310 struct DagForest *build_dag(struct Scene *sce, short mask) 
311 {
312         Base *base;
313         Object *ob;
314         bConstraint *con;
315         DagNode * node;
316         DagNode * node2;
317         DagNode * node3;
318         DagNode * scenenode;
319         DagForest *dag;
320         DagAdjList *itA;
321         Key *key;
322
323         dag = sce->theDag;
324         sce->dagisvalid=1;
325         if ( dag)
326                 free_forest( dag ); 
327         else {
328                 dag = dag_init();
329                 sce->theDag = dag;
330         }
331         
332         /* add base node for scene. scene is always the first node in DAG */
333         scenenode = dag_add_node(dag, sce);     
334         
335         for(base = sce->base.first; base; base= base->next) {
336                 int addtoroot = 1;
337                 ob= (Object *) base->object;
338                 
339                 node = dag_get_node(dag,ob);
340                 
341                 if ((ob->data) && (mask&DAG_RL_DATA)) {
342                         node2 = dag_get_node(dag,ob->data);
343                         dag_add_relation(dag,node,node2,DAG_RL_DATA);
344                         node2->first_ancestor = ob;
345                         node2->ancestor_count += 1;
346                 }
347                 
348                 if (ob->type == OB_ARMATURE) {
349                         if (ob->pose){
350                                 bPoseChannel *pchan;
351                                 bConstraint *con;
352                                 Object * target;
353                                 char *subtarget;
354                                 
355                                 for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){
356                                         for (con = pchan->constraints.first; con; con=con->next){
357                                                 if (constraint_has_target(con)) {
358                                                         
359                                                         target = get_constraint_target(con, &subtarget);
360                                                         if (target!=ob) {
361                                                                 // fprintf(stderr,"armature %s target :%s \n", ob->id.name, target->id.name);
362                                                                 node3 = dag_get_node(dag, target);
363                                                                 
364                                                                 if(subtarget && subtarget[0])
365                                                                         dag_add_relation(dag,node3,node, DAG_RL_OB_DATA|DAG_RL_DATA_DATA);
366                                                                 else
367                                                                         dag_add_relation(dag,node3,node, DAG_RL_OB_DATA);
368                                                                         
369                                                         }
370                                                 }
371                                         }
372                                 }
373                         }
374                 }
375                 
376                 /* driver dependencies */
377                 if(ob->ipo) 
378                         dag_add_driver_relation(ob->ipo, dag, node, 0);
379                 
380                 key= ob_get_key(ob);
381                 if(key && key->ipo)
382                         dag_add_driver_relation(key->ipo, dag, node, 1);
383                 
384                 if(ob->action) {
385                         bActionChannel *chan;
386                         for (chan = ob->action->chanbase.first; chan; chan=chan->next){
387                                 if(chan->ipo)
388                                         dag_add_driver_relation(chan->ipo, dag, node, 1);
389                         }
390                 }
391                 
392                 if (ob->modifiers.first) {
393                         ModifierData *md;
394
395                         for(md=ob->modifiers.first; md; md=md->next) {
396                                 ModifierTypeInfo *mti = modifierType_getInfo(md->type);
397
398                                 if (mti->updateDepgraph) mti->updateDepgraph(md, dag, ob, node);
399                         }
400                 }
401                 if (ob->parent) {
402                         node2 = dag_get_node(dag,ob->parent);
403                         
404                         switch(ob->partype) {
405                         case PARSKEL:
406                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB);
407                                 break;
408                         case PARVERT1: case PARVERT3: case PARBONE:
409                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB);
410                                 break;
411                         default:
412                                 if(ob->parent->type==OB_LATTICE) 
413                                         dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB);
414                                 else if(ob->parent->type==OB_CURVE) {
415                                         Curve *cu= ob->parent->data;
416                                         if(cu->flag & CU_PATH) 
417                                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB);
418                                         else
419                                                 dag_add_relation(dag,node2,node,DAG_RL_OB_OB);
420                                 }
421                                 else
422                                         dag_add_relation(dag,node2,node,DAG_RL_OB_OB);
423                         }
424                         addtoroot = 0;
425                 }
426                 if (ob->track) {
427                         node2 = dag_get_node(dag,ob->track);
428                         dag_add_relation(dag,node2,node,DAG_RL_OB_OB);
429                         addtoroot = 0;
430                 }
431                 if (ob->type==OB_MBALL) {
432                         Object *mom= find_basis_mball(ob);
433                         if(mom!=ob) {
434                                 node2 = dag_get_node(dag, mom);
435                                 dag_add_relation(dag,node,node2,DAG_RL_DATA_DATA|DAG_RL_OB_DATA);  // mom depends on children!
436                         }
437                 }
438                 else if (ob->type==OB_CURVE) {
439                         Curve *cu= ob->data;
440                         if(cu->bevobj) {
441                                 node2 = dag_get_node(dag, cu->bevobj);
442                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
443                         }
444                         if(cu->taperobj) {
445                                 node2 = dag_get_node(dag, cu->taperobj);
446                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
447                         }
448                 }
449                 else if(ob->type==OB_FONT) {
450                         Curve *cu= ob->data;
451                         if(cu->textoncurve) {
452                                 node2 = dag_get_node(dag, cu->textoncurve);
453                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
454                         }
455                 }
456                 
457                 for (con = ob->constraints.first; con; con=con->next){
458                         if (constraint_has_target(con)) {
459                                 char *str;
460                                 node2 = dag_get_node(dag, get_constraint_target(con, &str));
461                                 if(con->type==CONSTRAINT_TYPE_FOLLOWPATH)
462                                         dag_add_relation(dag, node2, node, DAG_RL_DATA_OB|DAG_RL_OB_OB);
463                                 else
464                                         dag_add_relation(dag, node2, node, DAG_RL_OB_OB);
465                                 addtoroot = 0;
466                         }
467                 }
468                 
469                 if (addtoroot == 1 )
470                         dag_add_relation(dag,scenenode,node,DAG_RL_SCENE);
471         }
472         
473         /* Now all relations were built, but we need to solve 1 exceptional case;
474            When objects have multiple "parents" (for example parent + constraint working on same object)
475            the relation type has to be synced. One of the parents can change, and should give same event to child */
476         
477         /* nodes were callocced, so we can use node->color for temporal storage */
478         for(node = sce->theDag->DagNode.first; node; node= node->next) {
479                 if(node->type==ID_OB) {
480                         for(itA = node->child; itA; itA= itA->next) {
481                                 if(itA->node->type==ID_OB) {
482                                         itA->node->color |= itA->type;
483                                 }
484                         }
485                 }
486         }
487         /* now set relations equal, so that when only one parent changes, the correct recalcs are found */
488         for(node = sce->theDag->DagNode.first; node; node= node->next) {
489                 if(node->type==ID_OB) {
490                         for(itA = node->child; itA; itA= itA->next) {
491                                 if(itA->node->type==ID_OB) {
492                                         itA->type |= itA->node->color;
493                                 }
494                         }
495                 }
496         }
497         
498         // cycle detection and solving
499         // solve_cycles(dag);   
500         
501         return dag;
502 }
503
504
505 void free_forest(DagForest *Dag) 
506 {  /* remove all nodes and deps */
507         DagNode *tempN;
508         DagAdjList *tempA;      
509         DagAdjList *itA;
510         DagNode *itN = Dag->DagNode.first;
511         
512         while (itN) {
513                 itA = itN->child;       
514                 while (itA) {
515                         tempA = itA;
516                         itA = itA->next;
517                         MEM_freeN(tempA);                       
518                 }
519                 tempN = itN;
520                 itN = itN->next;
521                 MEM_freeN(tempN);
522         }
523         Dag->DagNode.first = NULL;
524         Dag->DagNode.last = NULL;
525         Dag->numNodes = 0;
526
527 }
528
529 DagNode * dag_find_node (DagForest *forest,void * fob)
530 {
531         DagNode *node = forest->DagNode.first;
532         
533         while (node) {
534                 if (node->ob == fob)
535                         return node;
536                 node = node->next;
537         }
538         return NULL;
539 }
540
541 static int ugly_hack_sorry= 1;  // prevent type check
542
543 /* no checking of existance, use dag_find_node first or dag_get_node */
544 DagNode * dag_add_node (DagForest *forest, void * fob)
545 {
546         DagNode *node;
547                 
548         node = MEM_mallocN(sizeof(DagNode),"DAG node");
549         if (node) {
550                 node->ob = fob;
551                 node->color = DAG_WHITE;
552                 node->BFS_dist = 0;             
553                 node->DFS_dist = 0;             
554                 node->DFS_dvtm = 0;             
555                 node->DFS_fntm = 0;
556                 node->child = NULL;
557                 node->next = NULL;
558                 node->first_ancestor = NULL;
559                 node->ancestor_count = 0;
560
561                 if(ugly_hack_sorry) node->type = GS(((ID *) fob)->name);        // sorry, done for pose sorting
562                 if (forest->numNodes) {
563                         ((DagNode *) forest->DagNode.last)->next = node;
564                         forest->DagNode.last = node;
565                         forest->numNodes++;
566                 } else {
567                         forest->DagNode.last = node;
568                         forest->DagNode.first = node;
569                         forest->numNodes = 1;
570                 }
571         }
572         return node;
573 }
574
575 DagNode * dag_get_node (DagForest *forest,void * fob)
576 {
577         DagNode *node;
578         
579         node = dag_find_node (forest, fob);     
580         if (!node) 
581                 node = dag_add_node(forest, fob);
582         return node;
583 }
584
585
586
587 DagNode * dag_get_sub_node (DagForest *forest,void * fob)
588 {
589         DagNode *node;
590         DagAdjList *mainchild, *prev=NULL;
591         
592         mainchild = ((DagNode *) forest->DagNode.first)->child;
593         /* remove from first node (scene) adj list if present */
594         while (mainchild) {
595                 if (mainchild->node == fob) {
596                         if (prev) {
597                                 prev->next = mainchild->next;
598                                 MEM_freeN(mainchild);
599                                 break;
600                         } else {
601                                 ((DagNode *) forest->DagNode.first)->child = mainchild->next;
602                                 MEM_freeN(mainchild);
603                                 break;
604                         }
605                 }
606                 prev = mainchild;
607                 mainchild = mainchild->next;
608         }
609         node = dag_find_node (forest, fob);     
610         if (!node) 
611                 node = dag_add_node(forest, fob);
612         return node;
613 }
614
615 void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, short rel) 
616 {
617         DagAdjList *itA = fob1->child;
618         
619         while (itA) { /* search if relation exist already */
620                 if (itA->node == fob2) {
621                         if (itA->type == rel) { 
622                                 itA->count += 1;
623                                 return;
624                         }
625                 }
626                 itA = itA->next;
627         }
628         /* create new relation and insert at head */
629         itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list");
630         itA->node = fob2;
631         itA->type = rel;
632         itA->count = 1;
633         itA->next = fob1->child;
634         fob1->child = itA;
635 }
636
637
638 /*
639  * MainDAG is the DAG of all objects in current scene
640  * used only for drawing there is one also in each scene
641  */
642 static DagForest * MainDag = NULL;
643
644 DagForest *getMainDag(void)
645 {
646         return MainDag;
647 }
648
649
650 void setMainDag(DagForest *dag)
651 {
652         MainDag = dag;
653 }
654
655
656 /*
657  * note for BFS/DFS
658  * in theory we should sweep the whole array
659  * but in our case the first node is the scene
660  * and is linked to every other object
661  *
662  * for general case we will need to add outer loop
663  */
664
665 /*
666  * ToDo : change pos kludge
667  */
668
669 /* adjust levels for drawing in oops space */
670 void graph_bfs(void)
671 {
672         DagNode *node;
673         DagNodeQueue *nqueue;
674         int pos[50];
675         int i;
676         DagAdjList *itA;
677         int minheight;
678         
679         /* fprintf(stderr,"starting BFS \n ------------\n"); */ 
680         nqueue = queue_create(DAGQUEUEALLOC);
681         for ( i=0; i<50; i++)
682                 pos[i] = 0;
683         
684         /* Init
685          * dagnode.first is alway the root (scene) 
686          */
687         node = MainDag->DagNode.first;
688         while(node) {
689                 node->color = DAG_WHITE;
690                 node->BFS_dist = 9999;
691                 node->k = 0;
692                 node = node->next;
693         }
694         
695         node = MainDag->DagNode.first;
696         if (node->color == DAG_WHITE) {
697                 node->color = DAG_GRAY;
698                 node->BFS_dist = 1;
699                 push_queue(nqueue,node);  
700                 while(nqueue->count) {
701                         node = pop_queue(nqueue);
702                         
703                         minheight = pos[node->BFS_dist];
704                         itA = node->child;
705                         while(itA != NULL) {
706                                 if((itA->node->color == DAG_WHITE) ) {
707                                         itA->node->color = DAG_GRAY;
708                                         itA->node->BFS_dist = node->BFS_dist + 1;
709                                         itA->node->k = (float) minheight;
710                                         push_queue(nqueue,itA->node);
711                                 }
712                                 
713                                  else {
714                                         fprintf(stderr,"bfs not dag tree edge color :%i \n",itA->node->color);
715                                 }
716                                  
717                                 
718                                 itA = itA->next;
719                         }
720                         if (pos[node->BFS_dist] > node->k ) {
721                                 pos[node->BFS_dist] += 1;                               
722                                 node->k = (float) pos[node->BFS_dist];
723                         } else {
724                                 pos[node->BFS_dist] = (int) node->k +1;
725                         }
726                         set_node_xy(node, node->BFS_dist*DEPSX*2, pos[node->BFS_dist]*DEPSY*2);
727                         node->color = DAG_BLACK;
728                         /*
729                          fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);   
730                          */
731                 }
732         }
733         queue_delete(nqueue);
734 }
735
736 int pre_and_post_BFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
737         DagNode *node;
738         
739         node = dag->DagNode.first;
740         return pre_and_post_source_BFS(dag, mask,  node,  pre_func,  post_func, data);
741 }
742
743
744 int pre_and_post_source_BFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
745 {
746         DagNode *node;
747         DagNodeQueue *nqueue;
748         DagAdjList *itA;
749         int     retval = 0;
750         /* fprintf(stderr,"starting BFS \n ------------\n"); */ 
751         
752         /* Init
753                 * dagnode.first is alway the root (scene) 
754                 */
755         node = dag->DagNode.first;
756         nqueue = queue_create(DAGQUEUEALLOC);
757         while(node) {
758                 node->color = DAG_WHITE;
759                 node->BFS_dist = 9999;
760                 node = node->next;
761         }
762         
763         node = source;
764         if (node->color == DAG_WHITE) {
765                 node->color = DAG_GRAY;
766                 node->BFS_dist = 1;
767                 pre_func(node->ob,data);
768                 
769                 while(nqueue->count) {
770                         node = pop_queue(nqueue);
771                         
772                         itA = node->child;
773                         while(itA != NULL) {
774                                 if((itA->node->color == DAG_WHITE) && (itA->type & mask)) {
775                                         itA->node->color = DAG_GRAY;
776                                         itA->node->BFS_dist = node->BFS_dist + 1;
777                                         push_queue(nqueue,itA->node);
778                                         pre_func(node->ob,data);
779                                 }
780                                 
781                                 else { // back or cross edge
782                                         retval = 1;
783                                 }
784                                 itA = itA->next;
785                         }
786                         post_func(node->ob,data);
787                         node->color = DAG_BLACK;
788                         /*
789                          fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);   
790                          */
791                 }
792         }
793         queue_delete(nqueue);
794         return retval;
795 }
796
797 /* non recursive version of DFS, return queue -- outer loop present to catch odd cases (first level cycles)*/
798 DagNodeQueue * graph_dfs(void)
799 {
800         DagNode *node;
801         DagNodeQueue *nqueue;
802         DagNodeQueue *retqueue;
803         int pos[50];
804         int i;
805         DagAdjList *itA;
806         int time;
807         int skip = 0;
808         int minheight;
809         int maxpos=0;
810         int     is_cycle = 0;
811         /*
812          *fprintf(stderr,"starting DFS \n ------------\n");
813          */     
814         nqueue = queue_create(DAGQUEUEALLOC);
815         retqueue = queue_create(MainDag->numNodes);
816         for ( i=0; i<50; i++)
817                 pos[i] = 0;
818         
819         /* Init
820          * dagnode.first is alway the root (scene) 
821          */
822         node = MainDag->DagNode.first;
823         while(node) {
824                 node->color = DAG_WHITE;
825                 node->DFS_dist = 9999;
826                 node->DFS_dvtm = node->DFS_fntm = 9999;
827                 node->k = 0;
828                 node =  node->next;
829         }
830         
831         time = 1;
832         
833         node = MainDag->DagNode.first;
834
835         do {
836         if (node->color == DAG_WHITE) {
837                 node->color = DAG_GRAY;
838                 node->DFS_dist = 1;
839                 node->DFS_dvtm = time;
840                 time++;
841                 push_stack(nqueue,node);  
842                         
843                 while(nqueue->count) {
844                         //graph_print_queue(nqueue);
845
846                          skip = 0;
847                         node = get_top_node_queue(nqueue);
848                         
849                         minheight = pos[node->DFS_dist];
850
851                         itA = node->child;
852                         while(itA != NULL) {
853                                 if((itA->node->color == DAG_WHITE) ) {
854                                         itA->node->DFS_dvtm = time;
855                                         itA->node->color = DAG_GRAY;
856
857                                         time++;
858                                         itA->node->DFS_dist = node->DFS_dist + 1;
859                                         itA->node->k = (float) minheight;
860                                         push_stack(nqueue,itA->node);
861                                         skip = 1;
862                                         break;
863                                 } else { 
864                                         if (itA->node->color == DAG_GRAY) { // back edge
865                                                 fprintf(stderr,"dfs back edge :%15s %15s \n",((ID *) node->ob)->name, ((ID *) itA->node->ob)->name);
866                                                 is_cycle = 1;
867                                         } else if (itA->node->color == DAG_BLACK) {
868                                                 ;
869                                                 /* already processed node but we may want later to change distance either to shorter to longer.
870                                                  * DFS_dist is the first encounter  
871                                                 */
872                                                 /*if (node->DFS_dist >= itA->node->DFS_dist)
873                                                         itA->node->DFS_dist = node->DFS_dist + 1;
874                                                         
875                                                         fprintf(stderr,"dfs forward or cross edge :%15s %i-%i %15s %i-%i \n",
876                                                                 ((ID *) node->ob)->name,
877                                                                 node->DFS_dvtm, 
878                                                                 node->DFS_fntm, 
879                                                                 ((ID *) itA->node->ob)->name, 
880                                                                 itA->node->DFS_dvtm,
881                                                                 itA->node->DFS_fntm);
882                                         */
883                                         } else 
884                                                 fprintf(stderr,"dfs unknown edge \n");
885                                 }
886                                 itA = itA->next;
887                         }                       
888
889                         if (!skip) {
890                                 node = pop_queue(nqueue);
891                                 node->color = DAG_BLACK;
892
893                                 node->DFS_fntm = time;
894                                 time++;
895                                 if (node->DFS_dist > maxpos)
896                                         maxpos = node->DFS_dist;
897                                 if (pos[node->DFS_dist] > node->k ) {
898                                         pos[node->DFS_dist] += 1;                               
899                                         node->k = (float) pos[node->DFS_dist];
900                                 } else {
901                                         pos[node->DFS_dist] = (int) node->k +1;
902                                 }
903                                 set_node_xy(node, node->DFS_dist*DEPSX*2, pos[node->DFS_dist]*DEPSY*2);
904                                 
905                                 /*
906                                  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 );       
907                                 */
908                                  push_stack(retqueue,node);
909                                 
910                         }
911                 }
912         }
913                 node = node->next;
914         } while (node);
915 //        fprintf(stderr,"i size : %i \n", maxpos);
916           
917         queue_delete(nqueue);
918           return(retqueue);
919 }
920
921 /* unused */
922 int pre_and_post_DFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
923         DagNode *node;
924
925         node = dag->DagNode.first;
926         return pre_and_post_source_DFS(dag, mask,  node,  pre_func,  post_func, data);
927 }
928
929 int pre_and_post_source_DFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
930 {
931         DagNode *node;
932         DagNodeQueue *nqueue;
933         DagAdjList *itA;
934         int time;
935         int skip = 0;
936         int retval = 0;
937         /*
938          *fprintf(stderr,"starting DFS \n ------------\n");
939          */     
940         nqueue = queue_create(DAGQUEUEALLOC);
941         
942         /* Init
943                 * dagnode.first is alway the root (scene) 
944                 */
945         node = dag->DagNode.first;
946         while(node) {
947                 node->color = DAG_WHITE;
948                 node->DFS_dist = 9999;
949                 node->DFS_dvtm = node->DFS_fntm = 9999;
950                 node->k = 0;
951                 node =  node->next;
952         }
953         
954         time = 1;
955         
956         node = source;
957         do {
958                 if (node->color == DAG_WHITE) {
959                         node->color = DAG_GRAY;
960                         node->DFS_dist = 1;
961                         node->DFS_dvtm = time;
962                         time++;
963                         push_stack(nqueue,node);  
964                         pre_func(node->ob,data);
965
966                         while(nqueue->count) {
967                                 skip = 0;
968                                 node = get_top_node_queue(nqueue);
969                                                                 
970                                 itA = node->child;
971                                 while(itA != NULL) {
972                                         if((itA->node->color == DAG_WHITE) && (itA->type & mask) ) {
973                                                 itA->node->DFS_dvtm = time;
974                                                 itA->node->color = DAG_GRAY;
975                                                 
976                                                 time++;
977                                                 itA->node->DFS_dist = node->DFS_dist + 1;
978                                                 push_stack(nqueue,itA->node);
979                                                 pre_func(node->ob,data);
980
981                                                 skip = 1;
982                                                 break;
983                                         } else {
984                                                 if (itA->node->color == DAG_GRAY) {// back edge
985                                                         retval = 1;
986                                                 }
987 //                                              else if (itA->node->color == DAG_BLACK) { // cross or forward
988 //                                                      ;
989                                         }
990                                         itA = itA->next;
991                                 }                       
992                                 
993                                 if (!skip) {
994                                         node = pop_queue(nqueue);
995                                         node->color = DAG_BLACK;
996                                         
997                                         node->DFS_fntm = time;
998                                         time++;
999                                         post_func(node->ob,data);
1000                                 }
1001                         }
1002                 }
1003                 node = node->next;
1004         } while (node);
1005         queue_delete(nqueue);
1006         return(retval);
1007 }
1008
1009
1010 // used to get the obs owning a datablock
1011 struct DagNodeQueue *get_obparents(struct DagForest     *dag, void *ob) 
1012 {
1013         DagNode * node, *node1;
1014         DagNodeQueue *nqueue;
1015         DagAdjList *itA;
1016
1017         node = dag_find_node(dag,ob);
1018         if(node==NULL) {
1019                 return NULL;
1020         }
1021         else if (node->ancestor_count == 1) { // simple case
1022                 nqueue = queue_create(1);
1023                 push_queue(nqueue,node);
1024         } else {        // need to go over the whole dag for adj list
1025                 nqueue = queue_create(node->ancestor_count);
1026                 
1027                 node1 = dag->DagNode.first;
1028                 do {
1029                         if (node1->DFS_fntm > node->DFS_fntm) { // a parent is finished after child. must check adj list
1030                                 itA = node->child;
1031                                 while(itA != NULL) {
1032                                         if ((itA->node == node) && (itA->type == DAG_RL_DATA)) {
1033                                                 push_queue(nqueue,node);
1034                                         }
1035                                         itA = itA->next;
1036                                 }
1037                         }
1038                         node1 = node1->next;
1039                 } while (node1);
1040         }
1041         return nqueue;
1042 }
1043
1044 struct DagNodeQueue *get_first_ancestors(struct DagForest       *dag, void *ob)
1045 {
1046         DagNode * node, *node1;
1047         DagNodeQueue *nqueue;
1048         DagAdjList *itA;
1049         
1050         node = dag_find_node(dag,ob);
1051         
1052         // need to go over the whole dag for adj list
1053         nqueue = queue_create(node->ancestor_count);
1054         
1055         node1 = dag->DagNode.first;
1056         do {
1057                 if (node1->DFS_fntm > node->DFS_fntm) { 
1058                         itA = node->child;
1059                         while(itA != NULL) {
1060                                 if (itA->node == node) {
1061                                         push_queue(nqueue,node);
1062                                 }
1063                                 itA = itA->next;
1064                         }
1065                 }
1066                 node1 = node1->next;
1067         } while (node1);
1068         
1069         return nqueue;  
1070 }
1071
1072 // standard DFS list
1073 struct DagNodeQueue *get_all_childs(struct DagForest    *dag, void *ob)
1074 {
1075         DagNode *node;
1076         DagNodeQueue *nqueue;
1077         DagNodeQueue *retqueue;
1078         DagAdjList *itA;
1079         int time;
1080         int skip = 0;
1081
1082         nqueue = queue_create(DAGQUEUEALLOC);
1083         retqueue = queue_create(dag->numNodes); // was MainDag... why? (ton)
1084         
1085         node = dag->DagNode.first;
1086         while(node) {
1087                 node->color = DAG_WHITE;
1088                 node =  node->next;
1089         }
1090         
1091         time = 1;
1092         
1093         node = dag_find_node(dag,ob);   // could be done in loop above (ton)
1094         if(node) { // can be null for newly added objects
1095                 
1096                 node->color = DAG_GRAY;
1097                 time++;
1098                 push_stack(nqueue,node);  
1099                 
1100                 while(nqueue->count) {
1101                         
1102                         skip = 0;
1103                         node = get_top_node_queue(nqueue);
1104                                         
1105                         itA = node->child;
1106                         while(itA != NULL) {
1107                                 if((itA->node->color == DAG_WHITE) ) {
1108                                         itA->node->DFS_dvtm = time;
1109                                         itA->node->color = DAG_GRAY;
1110                                         
1111                                         time++;
1112                                         push_stack(nqueue,itA->node);
1113                                         skip = 1;
1114                                         break;
1115                                 } 
1116                                 itA = itA->next;
1117                         }                       
1118                         
1119                         if (!skip) {
1120                                 node = pop_queue(nqueue);
1121                                 node->color = DAG_BLACK;
1122                                 
1123                                 time++;
1124                                 push_stack(retqueue,node);                      
1125                         }
1126                 }
1127         }
1128         queue_delete(nqueue);
1129         return(retqueue);
1130 }
1131
1132 /* unused */
1133 short   are_obs_related(struct DagForest        *dag, void *ob1, void *ob2) {
1134         DagNode * node;
1135         DagAdjList *itA;
1136         
1137         node = dag_find_node(dag,ob1);
1138         
1139         itA = node->child;
1140         while(itA != NULL) {
1141                 if((itA->node->ob == ob2) ) {
1142                         return itA->node->type;
1143                 } 
1144                 itA = itA->next;
1145         }
1146         return DAG_NO_RELATION;
1147 }
1148
1149 int     is_acyclic( DagForest   *dag) {
1150         return dag->is_acyclic;
1151 }
1152
1153 void set_node_xy(DagNode *node, float x, float y)
1154 {
1155         node->x = x;
1156         node->y = y;
1157 }
1158
1159
1160 /* debug test functions */
1161
1162 void graph_print_queue(DagNodeQueue *nqueue)
1163 {       
1164         DagNodeQueueElem *queueElem;
1165         
1166         queueElem = nqueue->first;
1167         while(queueElem) {
1168                 fprintf(stderr,"** %s %i %i-%i ",((ID *) queueElem->node->ob)->name,queueElem->node->color,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
1169                 queueElem = queueElem->next;            
1170         }
1171         fprintf(stderr,"\n");
1172 }
1173
1174 void graph_print_queue_dist(DagNodeQueue *nqueue)
1175 {       
1176         DagNodeQueueElem *queueElem;
1177         int max, count;
1178         
1179         queueElem = nqueue->first;
1180         max = queueElem->node->DFS_fntm;
1181         count = 0;
1182         while(queueElem) {
1183                 fprintf(stderr,"** %25s %2.2i-%2.2i ",((ID *) queueElem->node->ob)->name,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
1184                 while (count < queueElem->node->DFS_dvtm-1) { fputc(' ',stderr); count++;}
1185                 fputc('|',stderr); 
1186                 while (count < queueElem->node->DFS_fntm-2) { fputc('-',stderr); count++;}
1187                 fputc('|',stderr);
1188                 fputc('\n',stderr);
1189                 count = 0;
1190                 queueElem = queueElem->next;            
1191         }
1192         fprintf(stderr,"\n");
1193 }
1194
1195 void graph_print_adj_list(void)
1196 {
1197         DagNode *node;
1198         DagAdjList *itA;
1199         
1200         node = (getMainDag())->DagNode.first;
1201         while(node) {
1202                 fprintf(stderr,"node : %s col: %i",((ID *) node->ob)->name, node->color);               
1203                 itA = node->child;
1204                 while (itA) {
1205                         fprintf(stderr,"-- %s ",((ID *) itA->node->ob)->name);
1206                         
1207                         itA = itA->next;
1208                 }
1209                 fprintf(stderr,"\n");
1210                 node = node->next;
1211         }
1212 }
1213
1214 /* ************************ API *********************** */
1215
1216 /* sort the base list on dependency order */
1217 void DAG_scene_sort(struct Scene *sce)
1218 {
1219         DagNode *node;
1220         DagNodeQueue *nqueue;
1221         DagAdjList *itA;
1222         int time;
1223         int skip = 0;
1224         ListBase tempbase;
1225         Base *base;
1226         
1227         tempbase.first= tempbase.last= NULL;
1228         
1229         build_dag(sce, DAG_RL_ALL_BUT_DATA);
1230         
1231         nqueue = queue_create(DAGQUEUEALLOC);
1232         
1233         for(node = sce->theDag->DagNode.first; node; node= node->next) {
1234                 node->color = DAG_WHITE;
1235         }
1236         
1237         time = 1;
1238         
1239         node = sce->theDag->DagNode.first;
1240         
1241         node->color = DAG_GRAY;
1242         time++;
1243         push_stack(nqueue,node);  
1244         
1245         while(nqueue->count) {
1246                 
1247                 skip = 0;
1248                 node = get_top_node_queue(nqueue);
1249                 
1250                 itA = node->child;
1251                 while(itA != NULL) {
1252                         if((itA->node->color == DAG_WHITE) ) {
1253                                 itA->node->DFS_dvtm = time;
1254                                 itA->node->color = DAG_GRAY;
1255                                 
1256                                 time++;
1257                                 push_stack(nqueue,itA->node);
1258                                 skip = 1;
1259                                 break;
1260                         } 
1261                         itA = itA->next;
1262                 }                       
1263                 
1264                 if (!skip) {
1265                         if (node) {
1266                                 node = pop_queue(nqueue);
1267                                 if (node->ob == sce)    // we are done
1268                                         break ;
1269                                 node->color = DAG_BLACK;
1270                                 
1271                                 time++;
1272                                 base = sce->base.first;
1273                                 while (base->object != node->ob)
1274                                         base = base->next;
1275                                 BLI_remlink(&sce->base,base);
1276                                 BLI_addhead(&tempbase,base);
1277                         }       
1278                 }
1279         }
1280         
1281         // temporal correction for circular dependancies
1282         base = sce->base.first;
1283         while (base) {
1284                 BLI_remlink(&sce->base,base);
1285                 BLI_addhead(&tempbase,base);
1286                 //if(G.f & G_DEBUG) 
1287                         printf("cyclic %s\n", base->object->id.name);
1288                 base = sce->base.first;
1289         }
1290         
1291         sce->base = tempbase;
1292         queue_delete(nqueue);
1293         
1294         if(G.f & G_DEBUG) {
1295                 printf("\nordered\n");
1296                 for(base = sce->base.first; base; base= base->next) {
1297                         printf(" %s\n", base->object->id.name);
1298                 }
1299         }
1300 }
1301
1302 /* node was checked to have lasttime != curtime and is if type ID_OB */
1303 static void flush_update_node(DagNode *node, unsigned int layer, int curtime)
1304 {
1305         DagAdjList *itA;
1306         Object *ob, *obc;
1307         int oldflag, changed=0;
1308         unsigned int all_layer;
1309         
1310         node->lasttime= curtime;
1311         
1312         ob= node->ob;
1313         if(ob->recalc & OB_RECALC) {
1314                 all_layer= ob->lay;
1315                 /* got an object node that changes, now check relations */
1316                 for(itA = node->child; itA; itA= itA->next) {
1317                         all_layer |= itA->lay;
1318                         /* the relationship is visible */
1319                         if(itA->lay & layer) {
1320                                 if(itA->node->type==ID_OB) {
1321                                         obc= itA->node->ob;
1322                                         oldflag= obc->recalc;
1323                                         
1324                                         /* got a ob->obc relation, now check if flag needs flush */
1325                                         if(ob->recalc & OB_RECALC_OB) {
1326                                                 if(itA->type & DAG_RL_OB_OB) {
1327                                                         //printf("ob %s changes ob %s\n", ob->id.name, obc->id.name);
1328                                                         obc->recalc |= OB_RECALC_OB;
1329                                                 }
1330                                                 if(itA->type & DAG_RL_OB_DATA) {
1331                                                         //printf("ob %s changes obdata %s\n", ob->id.name, obc->id.name);
1332                                                         obc->recalc |= OB_RECALC_DATA;
1333                                                 }
1334                                         }
1335                                         if(ob->recalc & OB_RECALC_DATA) {
1336                                                 if(itA->type & DAG_RL_DATA_OB) {
1337                                                         //printf("obdata %s changes ob %s\n", ob->id.name, obc->id.name);
1338                                                         obc->recalc |= OB_RECALC_OB;
1339                                                 }
1340                                                 if(itA->type & DAG_RL_DATA_DATA) {
1341                                                         //printf("obdata %s changes obdata %s\n", ob->id.name, obc->id.name);
1342                                                         obc->recalc |= OB_RECALC_DATA;
1343                                                 }
1344                                         }
1345                                         if(oldflag!=obc->recalc) changed= 1;
1346                                 }
1347                         }
1348                 }
1349                 /* even nicer, we can clear recalc flags...  */
1350                 if((all_layer & layer)==0)
1351                         ob->recalc &= ~OB_RECALC;
1352                 
1353         }
1354         else{
1355                 /* Object has not RECALC flag */
1356                 /* check case where child changes and parent forcing obdata to change */
1357                 /* could merge this in with loop above...? (ton) */
1358                 for(itA = node->child; itA; itA= itA->next) {
1359                         /* the relationship is visible */
1360                         if(itA->lay & layer) {
1361                                 if(itA->node->type==ID_OB) {
1362                                         obc= itA->node->ob;
1363                                         /* child moves */
1364                                         if((obc->recalc & OB_RECALC)==OB_RECALC_OB) {
1365                                                 /* parent has deforming info */
1366                                                 if(itA->type & (DAG_RL_OB_DATA|DAG_RL_DATA_DATA)) {
1367                                                         // printf("parent %s changes ob %s\n", ob->id.name, obc->id.name);
1368                                                         obc->recalc |= OB_RECALC_DATA;
1369                                                 }
1370                                         }
1371                                 }
1372                         }
1373                 }
1374         }
1375         
1376         /* we only go deeper if node not checked or something changed  */
1377         for(itA = node->child; itA; itA= itA->next) {
1378                 if(changed || itA->node->lasttime!=curtime) 
1379                         flush_update_node(itA->node, layer, curtime);
1380         }
1381         
1382 }
1383
1384 /* node was checked to have lasttime != curtime , and is of type ID_OB */
1385 static unsigned int flush_layer_node(DagNode *node, int curtime)
1386 {
1387         DagAdjList *itA;
1388         
1389         node->lasttime= curtime;
1390         node->lay= ((Object *)node->ob)->lay;
1391         
1392         for(itA = node->child; itA; itA= itA->next) {
1393                 if(itA->node->type==ID_OB) {
1394                         if(itA->node->lasttime!=curtime) {
1395                                 itA->lay= flush_layer_node(itA->node, curtime);  // lay is only set once for each relation
1396                                 //printf("layer %d for relation %s to %s\n", itA->lay, ((Object *)node->ob)->id.name, ((Object *)itA->node->ob)->id.name);
1397                         }
1398                         else itA->lay= itA->node->lay;
1399                         
1400                         node->lay |= itA->lay;
1401                 }
1402         }
1403
1404         return node->lay;
1405 }
1406
1407 /* flushes all recalc flags in objects down the dependency tree */
1408 void DAG_scene_flush_update(Scene *sce)
1409 {
1410         DagNode *firstnode;
1411         DagAdjList *itA;
1412         int lasttime;
1413         
1414         firstnode= sce->theDag->DagNode.first;  // always scene node
1415         
1416         /* first we flush the layer flags */
1417         sce->theDag->time++;    // so we know which nodes were accessed
1418         lasttime= sce->theDag->time;
1419         for(itA = firstnode->child; itA; itA= itA->next) {
1420                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) 
1421                         flush_layer_node(itA->node, lasttime);
1422         }
1423         
1424         /* then we use the relationships + layer info to flush update events */
1425         sce->theDag->time++;    // so we know which nodes were accessed
1426         lasttime= sce->theDag->time;
1427         for(itA = firstnode->child; itA; itA= itA->next) {
1428                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) 
1429                         flush_update_node(itA->node, sce->lay, lasttime);
1430         }
1431 }
1432
1433 static int object_modifiers_use_time(Object *ob)
1434 {
1435         ModifierData *md;
1436
1437         for (md=ob->modifiers.first; md; md=md->next)
1438                 if (modifier_dependsOnTime(md))
1439                         return 1;
1440
1441         return 0;
1442 }
1443
1444 /* flag all objects that need recalc, for changes in time for example */
1445 void DAG_scene_update_flags(Scene *sce, unsigned int lay)
1446 {
1447         Base *base;
1448         Object *ob;
1449         
1450         /* set ob flags where animated systems are */
1451         for(base= sce->base.first; base; base= base->next) {
1452                 
1453                 /* now if DagNode were part of base, the node->lay could be checked... */
1454                 /* we do all now, since the scene_flush checks layers and clears recalc flags even */
1455                 ob= base->object;
1456                 
1457                 if(ob->ipo) ob->recalc |= OB_RECALC_OB;
1458                 else if(ob->constraints.first) ob->recalc |= OB_RECALC_OB;
1459                 else if(ob->scriptlink.totscript) ob->recalc |= OB_RECALC_OB;
1460                 else if(ob->parent) {
1461                         if(ob->parent->type==OB_CURVE) ob->recalc |= OB_RECALC_OB;
1462                 }
1463                 
1464                 if(ob->action) ob->recalc |= OB_RECALC_DATA;
1465                 else if(ob->nlastrips.first) ob->recalc |= OB_RECALC_DATA;
1466                 else if(modifiers_isSoftbodyEnabled(ob)) ob->recalc |= OB_RECALC_DATA;
1467                 else if(object_modifiers_use_time(ob)) ob->recalc |= OB_RECALC_DATA;
1468                 else {
1469                         Mesh *me;
1470                         Curve *cu;
1471                         Lattice *lt;
1472                         
1473                         switch(ob->type) {
1474                                 case OB_MESH:
1475                                         me= ob->data;
1476                                         if(me->key) {
1477                                                 if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
1478                                                         ob->recalc |= OB_RECALC_DATA;
1479                                                         ob->shapeflag &= ~OB_SHAPE_TEMPLOCK;
1480                                                 }
1481                                         }
1482                                         else if(ob->effect.first) {
1483                                                 Effect *eff= ob->effect.first;
1484                                                 if(eff->type==EFF_WAVE) ob->recalc |= OB_RECALC_DATA;
1485                                         }
1486                                         if((ob->fluidsimFlag & OB_FLUIDSIM_ENABLE) && (ob->fluidsimSettings)) {
1487                                                 // fluidsimSettings might not be initialized during load...
1488                                                 if(ob->fluidsimSettings->type & OB_FLUIDSIM_DOMAIN) {
1489                                                         ob->recalc |= OB_RECALC_DATA; // NT
1490                                                 }
1491                                         }
1492                                         break;
1493                                 case OB_CURVE:
1494                                 case OB_SURF:
1495                                         cu= ob->data;
1496                                         if(cu->key) {
1497                                                 if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
1498                                                         ob->recalc |= OB_RECALC_DATA;
1499                                                         ob->shapeflag &= ~OB_SHAPE_TEMPLOCK;
1500                                                 }
1501                                         }
1502                                         break;
1503                                 case OB_LATTICE:
1504                                         lt= ob->data;
1505                                         if(lt->key) {
1506                                                 if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
1507                                                         ob->recalc |= OB_RECALC_DATA;
1508                                                         ob->shapeflag &= ~OB_SHAPE_TEMPLOCK;
1509                                                 }
1510                                         }
1511                                         break;
1512                                 case OB_MBALL:
1513                                         if(ob->transflag & OB_DUPLI) ob->recalc |= OB_RECALC_DATA;
1514                                         break;
1515                         }
1516                 }
1517         }
1518         DAG_scene_flush_update(sce);
1519 }
1520
1521 /* flag this object and all its relations to recalc */
1522 /* if you need to do more objects, tag object yourself and
1523    use DAG_scene_flush_update() in end */
1524 void DAG_object_flush_update(Scene *sce, Object *ob, short flag)
1525 {
1526         Base *base;
1527         
1528         if(ob==NULL || sce->theDag==NULL) return;
1529         ob->recalc |= flag;
1530         
1531         /* all users of this ob->data should be checked */
1532         if(flag & OB_RECALC_DATA) {
1533                 ID *id= ob->data;
1534                 if(id && id->us>1) {
1535                         /* except when there's a key and shapes are locked */
1536                         if(ob_get_key(ob) && (ob->shapeflag & (OB_SHAPE_LOCK|OB_SHAPE_TEMPLOCK)));
1537                         else {
1538                                 for (base= sce->base.first; base; base= base->next) {
1539                                         if (ob->data==base->object->data) {
1540                                                 base->object->recalc |= OB_RECALC_DATA;
1541                                         }
1542                                 }
1543                         }
1544                 }
1545         }
1546         
1547         DAG_scene_flush_update(sce);
1548 }
1549
1550 /* ******************* DAG FOR ARMATURE POSE ***************** */
1551
1552 /* we assume its an armature with pose */
1553 void DAG_pose_sort(Object *ob)
1554 {
1555         bPose *pose= ob->pose;
1556         bPoseChannel *pchan;
1557         bConstraint *con;
1558         DagNode *node;
1559         DagNode *node2, *node3;
1560         DagNode *rootnode;
1561         DagForest *dag;
1562         DagNodeQueue *nqueue;
1563         DagAdjList *itA;
1564         ListBase tempbase;
1565         int skip = 0;
1566         
1567         dag = dag_init();
1568         ugly_hack_sorry= 0;     // no ID structs
1569
1570         rootnode = dag_add_node(dag, NULL);     // node->ob becomes NULL
1571         
1572         /* we add the hierarchy and the constraints */
1573         for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
1574                 int addtoroot = 1;
1575                 
1576                 node = dag_get_node(dag, pchan);
1577                 
1578                 if(pchan->parent) {
1579                         node2 = dag_get_node(dag, pchan->parent);
1580                         dag_add_relation(dag, node2, node, 0);
1581                         addtoroot = 0;
1582                 }
1583                 for (con = pchan->constraints.first; con; con=con->next){
1584                         if (constraint_has_target(con)) {
1585                                 char *subtarget;
1586                                 Object *target = get_constraint_target(con, &subtarget);
1587                                 
1588                                 if (target==ob && subtarget) {
1589                                         bPoseChannel *target= get_pose_channel(ob->pose, subtarget);
1590                                         if(target) {
1591                                                 node2= dag_get_node(dag, target);
1592                                                 dag_add_relation(dag, node2, node, 0);
1593                                                 
1594                                                 if(con->type==CONSTRAINT_TYPE_KINEMATIC) {
1595                                                         bKinematicConstraint *data = (bKinematicConstraint*)con->data;
1596                                                         bPoseChannel *parchan;
1597                                                         int segcount= 0;
1598                                                         
1599                                                         /* exclude tip from chain? */
1600                                                         if(!(data->flag & CONSTRAINT_IK_TIP))
1601                                                                 parchan= pchan->parent;
1602                                                         else
1603                                                                 parchan= pchan;
1604                                                         
1605                                                         /* Walk to the chain's root */
1606                                                         while (parchan){
1607                                                                 node3= dag_get_node(dag, parchan);
1608                                                                 dag_add_relation(dag, node2, node3, 0);
1609                                                                 
1610                                                                 segcount++;
1611                                                                 if(segcount==data->rootbone || segcount>255) break; // 255 is weak
1612                                                                 parchan= parchan->parent;
1613                                                         }
1614                                                 }
1615                                         }
1616                                 }
1617                         }
1618                 }
1619                 if (addtoroot == 1 )
1620                         dag_add_relation(dag, rootnode, node, 0);
1621         }
1622
1623         /* now we try to sort... */
1624         tempbase.first= tempbase.last= NULL;
1625
1626         nqueue = queue_create(DAGQUEUEALLOC);
1627         
1628         /* tag nodes unchecked */
1629         for(node = dag->DagNode.first; node; node= node->next) 
1630                 node->color = DAG_WHITE;
1631         
1632         node = dag->DagNode.first;
1633         
1634         node->color = DAG_GRAY;
1635         push_stack(nqueue, node);  
1636         
1637         while(nqueue->count) {
1638                 
1639                 skip = 0;
1640                 node = get_top_node_queue(nqueue);
1641                 
1642                 itA = node->child;
1643                 while(itA != NULL) {
1644                         if((itA->node->color == DAG_WHITE) ) {
1645                                 itA->node->color = DAG_GRAY;
1646                                 push_stack(nqueue,itA->node);
1647                                 skip = 1;
1648                                 break;
1649                         } 
1650                         itA = itA->next;
1651                 }                       
1652                 
1653                 if (!skip) {
1654                         if (node) {
1655                                 node = pop_queue(nqueue);
1656                                 if (node->ob == NULL)   // we are done
1657                                         break ;
1658                                 node->color = DAG_BLACK;
1659                                 
1660                                 /* put node in new list */
1661                                 BLI_remlink(&pose->chanbase, node->ob);
1662                                 BLI_addhead(&tempbase, node->ob);
1663                         }       
1664                 }
1665         }
1666         
1667         // temporal correction for circular dependancies
1668         while(pose->chanbase.first) {
1669                 pchan= pose->chanbase.first;
1670                 BLI_remlink(&pose->chanbase, pchan);
1671                 BLI_addhead(&tempbase, pchan);
1672
1673                 printf("cyclic %s\n", pchan->name);
1674         }
1675         
1676         pose->chanbase = tempbase;
1677         queue_delete(nqueue);
1678         
1679 //      printf("\nordered\n");
1680 //      for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
1681 //              printf(" %s\n", pchan->name);
1682 //      }
1683         
1684         free_forest( dag );
1685         MEM_freeN( dag );
1686         
1687         ugly_hack_sorry= 1;
1688 }
1689
1690
1691