Pydrivers: Ipo Drivers controlled by Python expressions
[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_group_types.h"
50 #include "DNA_lattice_types.h"
51 #include "DNA_key_types.h"
52 #include "DNA_mesh_types.h"
53 #include "DNA_modifier_types.h"
54 #include "DNA_nla_types.h"
55 #include "DNA_object_types.h"
56 #include "DNA_object_force.h"
57 #include "DNA_object_fluidsim.h"
58 #include "DNA_oops_types.h"
59 #include "DNA_scene_types.h"
60 #include "DNA_screen_types.h"
61 #include "DNA_space_types.h"
62 #include "DNA_view2d_types.h"
63 #include "DNA_view3d_types.h"
64
65 #include "BKE_action.h"
66 #include "BKE_effect.h"
67 #include "BKE_global.h"
68 #include "BKE_key.h"
69 #include "BKE_main.h"
70 #include "BKE_mball.h"
71 #include "BKE_modifier.h"
72 #include "BKE_object.h"
73 #include "BKE_utildefines.h"
74
75 #include "MEM_guardedalloc.h"
76 #include "blendef.h"
77
78 #include "BPY_extern.h"
79
80  #include "depsgraph_private.h"
81  
82 /* Queue and stack operations for dag traversal 
83  *
84  * the queue store a list of freenodes to avoid successives alloc/dealloc
85  */
86
87 DagNodeQueue * queue_create (int slots) 
88 {
89         DagNodeQueue * queue;
90         DagNodeQueueElem * elem;
91         int i;
92         
93         queue = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
94         queue->freenodes = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
95         queue->count = 0;
96         queue->maxlevel = 0;
97         queue->first = queue->last = NULL;
98         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem3");
99         elem->node = NULL;
100         elem->next = NULL;
101         queue->freenodes->first = queue->freenodes->last = elem;
102         
103         for (i = 1; i <slots;i++) {
104                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem4");
105                 elem->node = NULL;
106                 elem->next = NULL;
107                 queue->freenodes->last->next = elem;
108                 queue->freenodes->last = elem;
109         }
110         queue->freenodes->count = slots;
111         return queue;
112 }
113
114 void queue_raz(DagNodeQueue *queue)
115 {
116         DagNodeQueueElem * elem;
117         
118         elem = queue->first;
119         if (queue->freenodes->last)
120                 queue->freenodes->last->next = elem;
121         else
122                 queue->freenodes->first = queue->freenodes->last = elem;
123         
124         elem->node = NULL;
125         queue->freenodes->count++;
126         while (elem->next) {
127                 elem = elem->next;
128                 elem->node = NULL;
129                 queue->freenodes->count++;
130         }
131         queue->freenodes->last = elem;
132         queue->count = 0;
133 }
134
135 void queue_delete(DagNodeQueue *queue)
136 {
137         DagNodeQueueElem * elem;
138         DagNodeQueueElem * temp;
139         
140         elem = queue->first;
141         while (elem) {
142                 temp = elem;
143                 elem = elem->next;
144                 MEM_freeN(temp);
145         }
146         
147         elem = queue->freenodes->first;
148         while (elem) {
149                 temp = elem;
150                 elem = elem->next;
151                 MEM_freeN(temp);
152         }
153         
154         MEM_freeN(queue->freenodes);                    
155         MEM_freeN(queue);                       
156 }
157
158 /* insert in queue, remove in front */
159 void push_queue(DagNodeQueue *queue, DagNode *node)
160 {
161         DagNodeQueueElem * elem;
162         int i;
163
164         if (node == NULL) {
165                 fprintf(stderr,"pushing null node \n");
166                 return;
167         }
168         /*fprintf(stderr,"BFS push : %s %d\n",((ID *) node->ob)->name, queue->count);*/
169
170         elem = queue->freenodes->first;
171         if (elem != NULL) {
172                 queue->freenodes->first = elem->next;
173                 if ( queue->freenodes->last == elem) {
174                         queue->freenodes->last = NULL;
175                         queue->freenodes->first = NULL;
176                 }
177                 queue->freenodes->count--;
178         } else { /* alllocating more */         
179                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
180                 elem->node = NULL;
181                 elem->next = NULL;
182                 queue->freenodes->first = queue->freenodes->last = elem;
183
184                 for (i = 1; i <DAGQUEUEALLOC;i++) {
185                         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
186                         elem->node = NULL;
187                         elem->next = NULL;
188                         queue->freenodes->last->next = elem;
189                         queue->freenodes->last = elem;
190                 }
191                 queue->freenodes->count = DAGQUEUEALLOC;
192                         
193                 elem = queue->freenodes->first; 
194                 queue->freenodes->first = elem->next;   
195         }
196         elem->next = NULL;
197         elem->node = node;
198         if (queue->last != NULL)
199                 queue->last->next = elem;
200         queue->last = elem;
201         if (queue->first == NULL) {
202                 queue->first = elem;
203         }
204         queue->count++;
205 }
206
207
208 /* insert in front, remove in front */
209 void push_stack(DagNodeQueue *queue, DagNode *node)
210 {
211         DagNodeQueueElem * elem;
212         int i;
213
214         elem = queue->freenodes->first; 
215         if (elem != NULL) {
216                 queue->freenodes->first = elem->next;
217                 if ( queue->freenodes->last == elem) {
218                         queue->freenodes->last = NULL;
219                         queue->freenodes->first = NULL;
220                 }
221                 queue->freenodes->count--;
222         } else { /* alllocating more */
223                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
224                 elem->node = NULL;
225                 elem->next = NULL;
226                 queue->freenodes->first = queue->freenodes->last = elem;
227
228                 for (i = 1; i <DAGQUEUEALLOC;i++) {
229                         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
230                         elem->node = NULL;
231                         elem->next = NULL;
232                         queue->freenodes->last->next = elem;
233                         queue->freenodes->last = elem;
234                 }
235                 queue->freenodes->count = DAGQUEUEALLOC;
236                         
237                 elem = queue->freenodes->first; 
238                 queue->freenodes->first = elem->next;   
239         }
240         elem->next = queue->first;
241         elem->node = node;
242         queue->first = elem;
243         if (queue->last == NULL)
244                 queue->last = elem;
245         queue->count++;
246 }
247
248
249 DagNode * pop_queue(DagNodeQueue *queue)
250 {
251         DagNodeQueueElem * elem;
252         DagNode *node;
253
254         elem = queue->first;
255         if (elem) {
256                 queue->first = elem->next;
257                 if (queue->last == elem) {
258                         queue->last=NULL;
259                         queue->first=NULL;
260                 }
261                 queue->count--;
262                 if (queue->freenodes->last)
263                         queue->freenodes->last->next=elem;
264                 queue->freenodes->last=elem;
265                 if (queue->freenodes->first == NULL)
266                         queue->freenodes->first=elem;
267                 node = elem->node;
268                 elem->node = NULL;
269                 elem->next = NULL;
270                 queue->freenodes->count++;
271                 return node;
272         } else {
273                 fprintf(stderr,"return null \n");
274                 return NULL;
275         }
276 }
277
278 void    *pop_ob_queue(struct DagNodeQueue *queue) {
279         return(pop_queue(queue)->ob);
280 }
281
282 DagNode * get_top_node_queue(DagNodeQueue *queue) 
283 {
284         return queue->first->node;
285 }
286
287 int             queue_count(struct DagNodeQueue *queue){
288         return queue->count;
289 }
290
291
292 DagForest * dag_init()
293 {
294         DagForest *forest;
295         /* use callocN to init all zero */
296         forest = MEM_callocN(sizeof(DagForest),"DAG root");
297         return forest;
298 }
299
300 static void dag_add_driver_relation(Ipo *ipo, DagForest *dag, DagNode *node, int isdata)
301 {
302         IpoCurve *icu;
303         DagNode *node1;
304         
305         for(icu= ipo->curve.first; icu; icu= icu->next) {
306                 if(icu->driver) {
307
308                         if (icu->driver->type == IPO_DRIVER_TYPE_PYTHON) {
309
310                                 if ((icu->driver->flag & IPO_DRIVER_FLAG_INVALID) || (icu->driver->name[0] == '\0'))
311                                         continue; /* empty or invalid expression */
312                                 else {
313                                         /* now we need refs to all objects mentioned in this
314                                          * pydriver expression, to call 'dag_add_relation'
315                                          * for each of them */
316                                         Object **obarray = BPY_pydriver_get_objects(icu->driver);
317                                         if (obarray) {
318                                                 Object *ob, **oba = obarray;
319
320                                                 while (*oba) {
321                                                         ob = *oba;
322                                                         node1 = dag_get_node(dag, ob);
323                                                         if (ob->type == OB_ARMATURE)
324                                                                 dag_add_relation(dag, node1, node, isdata?DAG_RL_DATA_DATA:DAG_RL_DATA_OB);
325                                                         else
326                                                                 dag_add_relation(dag, node1, node, isdata?DAG_RL_OB_DATA:DAG_RL_OB_OB);
327                                                         oba++;
328                                                 }
329
330                                                 MEM_freeN(obarray);
331                                         }
332                                 }
333                         }
334                         else if (icu->driver->ob) {
335                                 node1 = dag_get_node(dag, icu->driver->ob);
336                                 if(icu->driver->blocktype==ID_AR)
337                                         dag_add_relation(dag, node1, node, isdata?DAG_RL_DATA_DATA:DAG_RL_DATA_OB);
338                                 else
339                                         dag_add_relation(dag, node1, node, isdata?DAG_RL_OB_DATA:DAG_RL_OB_OB);
340                         }
341                 }
342         }
343 }
344
345 static void build_dag_object(DagForest *dag, DagNode *scenenode, Object *ob, int mask)
346 {
347         bConstraint *con;
348         DagNode * node;
349         DagNode * node2;
350         DagNode * node3;
351         Key *key;
352         int addtoroot= 1;
353         
354         node = dag_get_node(dag, ob);
355         
356         if ((ob->data) && (mask&DAG_RL_DATA)) {
357                 node2 = dag_get_node(dag,ob->data);
358                 dag_add_relation(dag,node,node2,DAG_RL_DATA);
359                 node2->first_ancestor = ob;
360                 node2->ancestor_count += 1;
361         }
362         
363         if (ob->type == OB_ARMATURE) {
364                 if (ob->pose){
365                         bPoseChannel *pchan;
366                         bConstraint *con;
367                         Object * target;
368                         char *subtarget;
369                         
370                         for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){
371                                 for (con = pchan->constraints.first; con; con=con->next){
372                                         if (constraint_has_target(con)) {
373                                                 
374                                                 target = get_constraint_target(con, &subtarget);
375                                                 if (target!=ob) {
376                                                         // fprintf(stderr,"armature %s target :%s \n", ob->id.name, target->id.name);
377                                                         node3 = dag_get_node(dag, target);
378                                                         
379                                                         if(subtarget && subtarget[0])
380                                                                 dag_add_relation(dag,node3,node, DAG_RL_OB_DATA|DAG_RL_DATA_DATA);
381                                                         else
382                                                                 dag_add_relation(dag,node3,node, DAG_RL_OB_DATA);
383                                                         
384                                                 }
385                                         }
386                                 }
387                         }
388                 }
389         }
390         
391         /* driver dependencies */
392         if(ob->ipo) 
393                 dag_add_driver_relation(ob->ipo, dag, node, 0);
394         
395         key= ob_get_key(ob);
396         if(key && key->ipo)
397                 dag_add_driver_relation(key->ipo, dag, node, 1);
398         
399         if(ob->action) {
400                 bActionChannel *chan;
401                 for (chan = ob->action->chanbase.first; chan; chan=chan->next){
402                         if(chan->ipo)
403                                 dag_add_driver_relation(chan->ipo, dag, node, 1);
404                 }
405         }
406         if(ob->nlastrips.first) {
407                 bActionStrip *strip;
408                 bActionChannel *chan;
409                 for(strip= ob->nlastrips.first; strip; strip= strip->next) {
410                         if(strip->act && strip->act!=ob->action)
411                                 for (chan = strip->act->chanbase.first; chan; chan=chan->next)
412                                         if(chan->ipo)
413                                                 dag_add_driver_relation(chan->ipo, dag, node, 1);
414                 }
415         }
416         if (ob->modifiers.first) {
417                 ModifierData *md;
418                 
419                 for(md=ob->modifiers.first; md; md=md->next) {
420                         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
421                         
422                         if (mti->updateDepgraph) mti->updateDepgraph(md, dag, ob, node);
423                 }
424         }
425         if (ob->parent) {
426                 node2 = dag_get_node(dag,ob->parent);
427                 
428                 switch(ob->partype) {
429                         case PARSKEL:
430                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB);
431                                 break;
432                         case PARVERT1: case PARVERT3: case PARBONE:
433                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB);
434                                 break;
435                         default:
436                                 if(ob->parent->type==OB_LATTICE) 
437                                         dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB);
438                                 else if(ob->parent->type==OB_CURVE) {
439                                         Curve *cu= ob->parent->data;
440                                         if(cu->flag & CU_PATH) 
441                                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB);
442                                         else
443                                                 dag_add_relation(dag,node2,node,DAG_RL_OB_OB);
444                                 }
445                                         else
446                                                 dag_add_relation(dag,node2,node,DAG_RL_OB_OB);
447                 }
448                 addtoroot = 0;
449         }
450         if (ob->track) {
451                 node2 = dag_get_node(dag,ob->track);
452                 dag_add_relation(dag,node2,node,DAG_RL_OB_OB);
453                 addtoroot = 0;
454         }
455         
456         if (ob->transflag & OB_DUPLI) {
457                 if((ob->transflag & OB_DUPLIGROUP) && ob->dup_group) {
458                         GroupObject *go;
459                         for(go= ob->dup_group->gobject.first; go; go= go->next) {
460                                 if(go->ob) {
461                                         node2 = dag_get_node(dag, go->ob);
462                                         /* node2 changes node1, this keeps animations updated in groups?? not logical? */
463                                         dag_add_relation(dag, node2, node, DAG_RL_OB_OB);
464                                 }
465                         }
466                 }
467         }
468         
469         if (ob->type==OB_MBALL) {
470                 Object *mom= find_basis_mball(ob);
471                 if(mom!=ob) {
472                         node2 = dag_get_node(dag, mom);
473                         dag_add_relation(dag,node,node2,DAG_RL_DATA_DATA|DAG_RL_OB_DATA);  // mom depends on children!
474                 }
475         }
476         else if (ob->type==OB_CURVE) {
477                 Curve *cu= ob->data;
478                 if(cu->bevobj) {
479                         node2 = dag_get_node(dag, cu->bevobj);
480                         dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
481                 }
482                 if(cu->taperobj) {
483                         node2 = dag_get_node(dag, cu->taperobj);
484                         dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
485                 }
486                 if(cu->ipo)
487                         dag_add_driver_relation(cu->ipo, dag, node, 1);
488
489         }
490         else if(ob->type==OB_FONT) {
491                 Curve *cu= ob->data;
492                 if(cu->textoncurve) {
493                         node2 = dag_get_node(dag, cu->textoncurve);
494                         dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
495                 }
496         }
497         else if(ob->type==OB_MESH) {
498                 PartEff *paf= give_parteff(ob);
499                 if(paf) {
500                         ListBase *listb;
501                         pEffectorCache *ec;
502                         
503                         /* ob location depends on itself */
504                         if((paf->flag & PAF_STATIC)==0)
505                                 dag_add_relation(dag, node, node, DAG_RL_OB_DATA);
506                         
507                         listb= pdInitEffectors(ob, paf->group);         /* note, makes copy... */
508                         if(listb) {
509                                 for(ec= listb->first; ec; ec= ec->next) {
510                                         Object *ob1= ec->ob;
511                                         PartDeflect *pd= ob1->pd;
512                                                 
513                                         if(pd->forcefield) {
514                                                 node2 = dag_get_node(dag, ob1);
515                                                 if(pd->forcefield==PFIELD_GUIDE)
516                                                         dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
517                                                 else
518                                                         dag_add_relation(dag, node2, node, DAG_RL_OB_DATA);
519                                         }
520                                 }
521                                 
522                                 pdEndEffectors(listb);  /* restores copy... */
523                         }
524                 }
525         }
526         
527         for (con = ob->constraints.first; con; con=con->next){
528                 if (constraint_has_target(con)) {
529                         char *str;
530                         Object *obt= get_constraint_target(con, &str);
531                         
532                         node2 = dag_get_node(dag, obt);
533                         if(con->type==CONSTRAINT_TYPE_FOLLOWPATH)
534                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_OB|DAG_RL_OB_OB);
535                         else {
536                                 if(obt->type==OB_ARMATURE && str[0])
537                                         dag_add_relation(dag, node2, node, DAG_RL_DATA_OB|DAG_RL_OB_OB);
538                                 else
539                                         dag_add_relation(dag, node2, node, DAG_RL_OB_OB);
540                         }
541                         addtoroot = 0;
542                 }
543         }
544
545         if (addtoroot == 1 )
546                 dag_add_relation(dag,scenenode,node,DAG_RL_SCENE);
547 }
548
549 struct DagForest *build_dag(struct Scene *sce, short mask) 
550 {
551         Base *base;
552         Object *ob;
553         Group *group;
554         GroupObject *go;
555         DagNode *node;
556         DagNode *scenenode;
557         DagForest *dag;
558         DagAdjList *itA;
559
560         dag = sce->theDag;
561         sce->dagisvalid=1;
562         if ( dag)
563                 free_forest( dag ); 
564         else {
565                 dag = dag_init();
566                 sce->theDag = dag;
567         }
568         
569         /* add base node for scene. scene is always the first node in DAG */
570         scenenode = dag_add_node(dag, sce);     
571         
572         /* add current scene objects */
573         for(base = sce->base.first; base; base= base->next) {
574                 ob= base->object;
575                 
576                 build_dag_object(dag, scenenode, ob, mask);
577                 
578                 /* handled in next loop */
579                 if(ob->dup_group) 
580                         ob->dup_group->id.flag |= LIB_DOIT;
581         }
582         
583         /* add groups used in current scene objects */
584         for(group= G.main->group.first; group; group= group->id.next) {
585                 if(group->id.flag & LIB_DOIT) {
586                         for(go= group->gobject.first; go; go= go->next) {
587                                 build_dag_object(dag, scenenode, go->ob, mask);
588                         }
589                         group->id.flag &= ~LIB_DOIT;
590                 }
591         }
592         
593         /* Now all relations were built, but we need to solve 1 exceptional case;
594            When objects have multiple "parents" (for example parent + constraint working on same object)
595            the relation type has to be synced. One of the parents can change, and should give same event to child */
596         
597         /* nodes were callocced, so we can use node->color for temporal storage */
598         for(node = sce->theDag->DagNode.first; node; node= node->next) {
599                 if(node->type==ID_OB) {
600                         for(itA = node->child; itA; itA= itA->next) {
601                                 if(itA->node->type==ID_OB) {
602                                         itA->node->color |= itA->type;
603                                 }
604                         }
605                 }
606         }
607         /* now set relations equal, so that when only one parent changes, the correct recalcs are found */
608         for(node = sce->theDag->DagNode.first; node; node= node->next) {
609                 if(node->type==ID_OB) {
610                         for(itA = node->child; itA; itA= itA->next) {
611                                 if(itA->node->type==ID_OB) {
612                                         itA->type |= itA->node->color;
613                                 }
614                         }
615                 }
616         }
617         
618         // cycle detection and solving
619         // solve_cycles(dag);   
620         
621         return dag;
622 }
623
624
625 void free_forest(DagForest *Dag) 
626 {  /* remove all nodes and deps */
627         DagNode *tempN;
628         DagAdjList *tempA;      
629         DagAdjList *itA;
630         DagNode *itN = Dag->DagNode.first;
631         
632         while (itN) {
633                 itA = itN->child;       
634                 while (itA) {
635                         tempA = itA;
636                         itA = itA->next;
637                         MEM_freeN(tempA);                       
638                 }
639                 tempN = itN;
640                 itN = itN->next;
641                 MEM_freeN(tempN);
642         }
643         Dag->DagNode.first = NULL;
644         Dag->DagNode.last = NULL;
645         Dag->numNodes = 0;
646
647 }
648
649 DagNode * dag_find_node (DagForest *forest,void * fob)
650 {
651         DagNode *node = forest->DagNode.first;
652         
653         while (node) {
654                 if (node->ob == fob)
655                         return node;
656                 node = node->next;
657         }
658         return NULL;
659 }
660
661 static int ugly_hack_sorry= 1;  // prevent type check
662
663 /* no checking of existance, use dag_find_node first or dag_get_node */
664 DagNode * dag_add_node (DagForest *forest, void * fob)
665 {
666         DagNode *node;
667                 
668         node = MEM_mallocN(sizeof(DagNode),"DAG node");
669         if (node) {
670                 node->ob = fob;
671                 node->color = DAG_WHITE;
672                 node->BFS_dist = 0;             
673                 node->DFS_dist = 0;             
674                 node->DFS_dvtm = 0;             
675                 node->DFS_fntm = 0;
676                 node->child = NULL;
677                 node->next = NULL;
678                 node->first_ancestor = NULL;
679                 node->ancestor_count = 0;
680
681                 if(ugly_hack_sorry) node->type = GS(((ID *) fob)->name);        // sorry, done for pose sorting
682                 if (forest->numNodes) {
683                         ((DagNode *) forest->DagNode.last)->next = node;
684                         forest->DagNode.last = node;
685                         forest->numNodes++;
686                 } else {
687                         forest->DagNode.last = node;
688                         forest->DagNode.first = node;
689                         forest->numNodes = 1;
690                 }
691         }
692         return node;
693 }
694
695 DagNode * dag_get_node (DagForest *forest,void * fob)
696 {
697         DagNode *node;
698         
699         node = dag_find_node (forest, fob);     
700         if (!node) 
701                 node = dag_add_node(forest, fob);
702         return node;
703 }
704
705
706
707 DagNode * dag_get_sub_node (DagForest *forest,void * fob)
708 {
709         DagNode *node;
710         DagAdjList *mainchild, *prev=NULL;
711         
712         mainchild = ((DagNode *) forest->DagNode.first)->child;
713         /* remove from first node (scene) adj list if present */
714         while (mainchild) {
715                 if (mainchild->node == fob) {
716                         if (prev) {
717                                 prev->next = mainchild->next;
718                                 MEM_freeN(mainchild);
719                                 break;
720                         } else {
721                                 ((DagNode *) forest->DagNode.first)->child = mainchild->next;
722                                 MEM_freeN(mainchild);
723                                 break;
724                         }
725                 }
726                 prev = mainchild;
727                 mainchild = mainchild->next;
728         }
729         node = dag_find_node (forest, fob);     
730         if (!node) 
731                 node = dag_add_node(forest, fob);
732         return node;
733 }
734
735 void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, short rel) 
736 {
737         DagAdjList *itA = fob1->child;
738         
739         while (itA) { /* search if relation exist already */
740                 if (itA->node == fob2) {
741                         itA->type |= rel;
742                         itA->count += 1;
743                         return;
744                 }
745                 itA = itA->next;
746         }
747         /* create new relation and insert at head */
748         itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list");
749         itA->node = fob2;
750         itA->type = rel;
751         itA->count = 1;
752         itA->next = fob1->child;
753         fob1->child = itA;
754 }
755
756
757 /*
758  * MainDAG is the DAG of all objects in current scene
759  * used only for drawing there is one also in each scene
760  */
761 static DagForest * MainDag = NULL;
762
763 DagForest *getMainDag(void)
764 {
765         return MainDag;
766 }
767
768
769 void setMainDag(DagForest *dag)
770 {
771         MainDag = dag;
772 }
773
774
775 /*
776  * note for BFS/DFS
777  * in theory we should sweep the whole array
778  * but in our case the first node is the scene
779  * and is linked to every other object
780  *
781  * for general case we will need to add outer loop
782  */
783
784 /*
785  * ToDo : change pos kludge
786  */
787
788 /* adjust levels for drawing in oops space */
789 void graph_bfs(void)
790 {
791         DagNode *node;
792         DagNodeQueue *nqueue;
793         int pos[50];
794         int i;
795         DagAdjList *itA;
796         int minheight;
797         
798         /* fprintf(stderr,"starting BFS \n ------------\n"); */ 
799         nqueue = queue_create(DAGQUEUEALLOC);
800         for ( i=0; i<50; i++)
801                 pos[i] = 0;
802         
803         /* Init
804          * dagnode.first is alway the root (scene) 
805          */
806         node = MainDag->DagNode.first;
807         while(node) {
808                 node->color = DAG_WHITE;
809                 node->BFS_dist = 9999;
810                 node->k = 0;
811                 node = node->next;
812         }
813         
814         node = MainDag->DagNode.first;
815         if (node->color == DAG_WHITE) {
816                 node->color = DAG_GRAY;
817                 node->BFS_dist = 1;
818                 push_queue(nqueue,node);  
819                 while(nqueue->count) {
820                         node = pop_queue(nqueue);
821                         
822                         minheight = pos[node->BFS_dist];
823                         itA = node->child;
824                         while(itA != NULL) {
825                                 if((itA->node->color == DAG_WHITE) ) {
826                                         itA->node->color = DAG_GRAY;
827                                         itA->node->BFS_dist = node->BFS_dist + 1;
828                                         itA->node->k = (float) minheight;
829                                         push_queue(nqueue,itA->node);
830                                 }
831                                 
832                                  else {
833                                         fprintf(stderr,"bfs not dag tree edge color :%i \n",itA->node->color);
834                                 }
835                                  
836                                 
837                                 itA = itA->next;
838                         }
839                         if (pos[node->BFS_dist] > node->k ) {
840                                 pos[node->BFS_dist] += 1;                               
841                                 node->k = (float) pos[node->BFS_dist];
842                         } else {
843                                 pos[node->BFS_dist] = (int) node->k +1;
844                         }
845                         set_node_xy(node, node->BFS_dist*DEPSX*2, pos[node->BFS_dist]*DEPSY*2);
846                         node->color = DAG_BLACK;
847                         /*
848                          fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);   
849                          */
850                 }
851         }
852         queue_delete(nqueue);
853 }
854
855 int pre_and_post_BFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
856         DagNode *node;
857         
858         node = dag->DagNode.first;
859         return pre_and_post_source_BFS(dag, mask,  node,  pre_func,  post_func, data);
860 }
861
862
863 int pre_and_post_source_BFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
864 {
865         DagNode *node;
866         DagNodeQueue *nqueue;
867         DagAdjList *itA;
868         int     retval = 0;
869         /* fprintf(stderr,"starting BFS \n ------------\n"); */ 
870         
871         /* Init
872                 * dagnode.first is alway the root (scene) 
873                 */
874         node = dag->DagNode.first;
875         nqueue = queue_create(DAGQUEUEALLOC);
876         while(node) {
877                 node->color = DAG_WHITE;
878                 node->BFS_dist = 9999;
879                 node = node->next;
880         }
881         
882         node = source;
883         if (node->color == DAG_WHITE) {
884                 node->color = DAG_GRAY;
885                 node->BFS_dist = 1;
886                 pre_func(node->ob,data);
887                 
888                 while(nqueue->count) {
889                         node = pop_queue(nqueue);
890                         
891                         itA = node->child;
892                         while(itA != NULL) {
893                                 if((itA->node->color == DAG_WHITE) && (itA->type & mask)) {
894                                         itA->node->color = DAG_GRAY;
895                                         itA->node->BFS_dist = node->BFS_dist + 1;
896                                         push_queue(nqueue,itA->node);
897                                         pre_func(node->ob,data);
898                                 }
899                                 
900                                 else { // back or cross edge
901                                         retval = 1;
902                                 }
903                                 itA = itA->next;
904                         }
905                         post_func(node->ob,data);
906                         node->color = DAG_BLACK;
907                         /*
908                          fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);   
909                          */
910                 }
911         }
912         queue_delete(nqueue);
913         return retval;
914 }
915
916 /* non recursive version of DFS, return queue -- outer loop present to catch odd cases (first level cycles)*/
917 DagNodeQueue * graph_dfs(void)
918 {
919         DagNode *node;
920         DagNodeQueue *nqueue;
921         DagNodeQueue *retqueue;
922         int pos[50];
923         int i;
924         DagAdjList *itA;
925         int time;
926         int skip = 0;
927         int minheight;
928         int maxpos=0;
929         int     is_cycle = 0;
930         /*
931          *fprintf(stderr,"starting DFS \n ------------\n");
932          */     
933         nqueue = queue_create(DAGQUEUEALLOC);
934         retqueue = queue_create(MainDag->numNodes);
935         for ( i=0; i<50; i++)
936                 pos[i] = 0;
937         
938         /* Init
939          * dagnode.first is alway the root (scene) 
940          */
941         node = MainDag->DagNode.first;
942         while(node) {
943                 node->color = DAG_WHITE;
944                 node->DFS_dist = 9999;
945                 node->DFS_dvtm = node->DFS_fntm = 9999;
946                 node->k = 0;
947                 node =  node->next;
948         }
949         
950         time = 1;
951         
952         node = MainDag->DagNode.first;
953
954         do {
955         if (node->color == DAG_WHITE) {
956                 node->color = DAG_GRAY;
957                 node->DFS_dist = 1;
958                 node->DFS_dvtm = time;
959                 time++;
960                 push_stack(nqueue,node);  
961                         
962                 while(nqueue->count) {
963                         //graph_print_queue(nqueue);
964
965                          skip = 0;
966                         node = get_top_node_queue(nqueue);
967                         
968                         minheight = pos[node->DFS_dist];
969
970                         itA = node->child;
971                         while(itA != NULL) {
972                                 if((itA->node->color == DAG_WHITE) ) {
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                                         itA->node->k = (float) minheight;
979                                         push_stack(nqueue,itA->node);
980                                         skip = 1;
981                                         break;
982                                 } else { 
983                                         if (itA->node->color == DAG_GRAY) { // back edge
984                                                 fprintf(stderr,"dfs back edge :%15s %15s \n",((ID *) node->ob)->name, ((ID *) itA->node->ob)->name);
985                                                 is_cycle = 1;
986                                         } else if (itA->node->color == DAG_BLACK) {
987                                                 ;
988                                                 /* already processed node but we may want later to change distance either to shorter to longer.
989                                                  * DFS_dist is the first encounter  
990                                                 */
991                                                 /*if (node->DFS_dist >= itA->node->DFS_dist)
992                                                         itA->node->DFS_dist = node->DFS_dist + 1;
993                                                         
994                                                         fprintf(stderr,"dfs forward or cross edge :%15s %i-%i %15s %i-%i \n",
995                                                                 ((ID *) node->ob)->name,
996                                                                 node->DFS_dvtm, 
997                                                                 node->DFS_fntm, 
998                                                                 ((ID *) itA->node->ob)->name, 
999                                                                 itA->node->DFS_dvtm,
1000                                                                 itA->node->DFS_fntm);
1001                                         */
1002                                         } else 
1003                                                 fprintf(stderr,"dfs unknown edge \n");
1004                                 }
1005                                 itA = itA->next;
1006                         }                       
1007
1008                         if (!skip) {
1009                                 node = pop_queue(nqueue);
1010                                 node->color = DAG_BLACK;
1011
1012                                 node->DFS_fntm = time;
1013                                 time++;
1014                                 if (node->DFS_dist > maxpos)
1015                                         maxpos = node->DFS_dist;
1016                                 if (pos[node->DFS_dist] > node->k ) {
1017                                         pos[node->DFS_dist] += 1;                               
1018                                         node->k = (float) pos[node->DFS_dist];
1019                                 } else {
1020                                         pos[node->DFS_dist] = (int) node->k +1;
1021                                 }
1022                                 set_node_xy(node, node->DFS_dist*DEPSX*2, pos[node->DFS_dist]*DEPSY*2);
1023                                 
1024                                 /*
1025                                  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 );       
1026                                 */
1027                                  push_stack(retqueue,node);
1028                                 
1029                         }
1030                 }
1031         }
1032                 node = node->next;
1033         } while (node);
1034 //        fprintf(stderr,"i size : %i \n", maxpos);
1035           
1036         queue_delete(nqueue);
1037           return(retqueue);
1038 }
1039
1040 /* unused */
1041 int pre_and_post_DFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
1042         DagNode *node;
1043
1044         node = dag->DagNode.first;
1045         return pre_and_post_source_DFS(dag, mask,  node,  pre_func,  post_func, data);
1046 }
1047
1048 int pre_and_post_source_DFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
1049 {
1050         DagNode *node;
1051         DagNodeQueue *nqueue;
1052         DagAdjList *itA;
1053         int time;
1054         int skip = 0;
1055         int retval = 0;
1056         /*
1057          *fprintf(stderr,"starting DFS \n ------------\n");
1058          */     
1059         nqueue = queue_create(DAGQUEUEALLOC);
1060         
1061         /* Init
1062                 * dagnode.first is alway the root (scene) 
1063                 */
1064         node = dag->DagNode.first;
1065         while(node) {
1066                 node->color = DAG_WHITE;
1067                 node->DFS_dist = 9999;
1068                 node->DFS_dvtm = node->DFS_fntm = 9999;
1069                 node->k = 0;
1070                 node =  node->next;
1071         }
1072         
1073         time = 1;
1074         
1075         node = source;
1076         do {
1077                 if (node->color == DAG_WHITE) {
1078                         node->color = DAG_GRAY;
1079                         node->DFS_dist = 1;
1080                         node->DFS_dvtm = time;
1081                         time++;
1082                         push_stack(nqueue,node);  
1083                         pre_func(node->ob,data);
1084
1085                         while(nqueue->count) {
1086                                 skip = 0;
1087                                 node = get_top_node_queue(nqueue);
1088                                                                 
1089                                 itA = node->child;
1090                                 while(itA != NULL) {
1091                                         if((itA->node->color == DAG_WHITE) && (itA->type & mask) ) {
1092                                                 itA->node->DFS_dvtm = time;
1093                                                 itA->node->color = DAG_GRAY;
1094                                                 
1095                                                 time++;
1096                                                 itA->node->DFS_dist = node->DFS_dist + 1;
1097                                                 push_stack(nqueue,itA->node);
1098                                                 pre_func(node->ob,data);
1099
1100                                                 skip = 1;
1101                                                 break;
1102                                         } else {
1103                                                 if (itA->node->color == DAG_GRAY) {// back edge
1104                                                         retval = 1;
1105                                                 }
1106 //                                              else if (itA->node->color == DAG_BLACK) { // cross or forward
1107 //                                                      ;
1108                                         }
1109                                         itA = itA->next;
1110                                 }                       
1111                                 
1112                                 if (!skip) {
1113                                         node = pop_queue(nqueue);
1114                                         node->color = DAG_BLACK;
1115                                         
1116                                         node->DFS_fntm = time;
1117                                         time++;
1118                                         post_func(node->ob,data);
1119                                 }
1120                         }
1121                 }
1122                 node = node->next;
1123         } while (node);
1124         queue_delete(nqueue);
1125         return(retval);
1126 }
1127
1128
1129 // used to get the obs owning a datablock
1130 struct DagNodeQueue *get_obparents(struct DagForest     *dag, void *ob) 
1131 {
1132         DagNode * node, *node1;
1133         DagNodeQueue *nqueue;
1134         DagAdjList *itA;
1135
1136         node = dag_find_node(dag,ob);
1137         if(node==NULL) {
1138                 return NULL;
1139         }
1140         else if (node->ancestor_count == 1) { // simple case
1141                 nqueue = queue_create(1);
1142                 push_queue(nqueue,node);
1143         } else {        // need to go over the whole dag for adj list
1144                 nqueue = queue_create(node->ancestor_count);
1145                 
1146                 node1 = dag->DagNode.first;
1147                 do {
1148                         if (node1->DFS_fntm > node->DFS_fntm) { // a parent is finished after child. must check adj list
1149                                 itA = node->child;
1150                                 while(itA != NULL) {
1151                                         if ((itA->node == node) && (itA->type == DAG_RL_DATA)) {
1152                                                 push_queue(nqueue,node);
1153                                         }
1154                                         itA = itA->next;
1155                                 }
1156                         }
1157                         node1 = node1->next;
1158                 } while (node1);
1159         }
1160         return nqueue;
1161 }
1162
1163 struct DagNodeQueue *get_first_ancestors(struct DagForest       *dag, void *ob)
1164 {
1165         DagNode * node, *node1;
1166         DagNodeQueue *nqueue;
1167         DagAdjList *itA;
1168         
1169         node = dag_find_node(dag,ob);
1170         
1171         // need to go over the whole dag for adj list
1172         nqueue = queue_create(node->ancestor_count);
1173         
1174         node1 = dag->DagNode.first;
1175         do {
1176                 if (node1->DFS_fntm > node->DFS_fntm) { 
1177                         itA = node->child;
1178                         while(itA != NULL) {
1179                                 if (itA->node == node) {
1180                                         push_queue(nqueue,node);
1181                                 }
1182                                 itA = itA->next;
1183                         }
1184                 }
1185                 node1 = node1->next;
1186         } while (node1);
1187         
1188         return nqueue;  
1189 }
1190
1191 // standard DFS list
1192 struct DagNodeQueue *get_all_childs(struct DagForest    *dag, void *ob)
1193 {
1194         DagNode *node;
1195         DagNodeQueue *nqueue;
1196         DagNodeQueue *retqueue;
1197         DagAdjList *itA;
1198         int time;
1199         int skip = 0;
1200
1201         nqueue = queue_create(DAGQUEUEALLOC);
1202         retqueue = queue_create(dag->numNodes); // was MainDag... why? (ton)
1203         
1204         node = dag->DagNode.first;
1205         while(node) {
1206                 node->color = DAG_WHITE;
1207                 node =  node->next;
1208         }
1209         
1210         time = 1;
1211         
1212         node = dag_find_node(dag,ob);   // could be done in loop above (ton)
1213         if(node) { // can be null for newly added objects
1214                 
1215                 node->color = DAG_GRAY;
1216                 time++;
1217                 push_stack(nqueue,node);  
1218                 
1219                 while(nqueue->count) {
1220                         
1221                         skip = 0;
1222                         node = get_top_node_queue(nqueue);
1223                                         
1224                         itA = node->child;
1225                         while(itA != NULL) {
1226                                 if((itA->node->color == DAG_WHITE) ) {
1227                                         itA->node->DFS_dvtm = time;
1228                                         itA->node->color = DAG_GRAY;
1229                                         
1230                                         time++;
1231                                         push_stack(nqueue,itA->node);
1232                                         skip = 1;
1233                                         break;
1234                                 } 
1235                                 itA = itA->next;
1236                         }                       
1237                         
1238                         if (!skip) {
1239                                 node = pop_queue(nqueue);
1240                                 node->color = DAG_BLACK;
1241                                 
1242                                 time++;
1243                                 push_stack(retqueue,node);                      
1244                         }
1245                 }
1246         }
1247         queue_delete(nqueue);
1248         return(retqueue);
1249 }
1250
1251 /* unused */
1252 short   are_obs_related(struct DagForest        *dag, void *ob1, void *ob2) {
1253         DagNode * node;
1254         DagAdjList *itA;
1255         
1256         node = dag_find_node(dag,ob1);
1257         
1258         itA = node->child;
1259         while(itA != NULL) {
1260                 if((itA->node->ob == ob2) ) {
1261                         return itA->node->type;
1262                 } 
1263                 itA = itA->next;
1264         }
1265         return DAG_NO_RELATION;
1266 }
1267
1268 int     is_acyclic( DagForest   *dag) {
1269         return dag->is_acyclic;
1270 }
1271
1272 void set_node_xy(DagNode *node, float x, float y)
1273 {
1274         node->x = x;
1275         node->y = y;
1276 }
1277
1278
1279 /* debug test functions */
1280
1281 void graph_print_queue(DagNodeQueue *nqueue)
1282 {       
1283         DagNodeQueueElem *queueElem;
1284         
1285         queueElem = nqueue->first;
1286         while(queueElem) {
1287                 fprintf(stderr,"** %s %i %i-%i ",((ID *) queueElem->node->ob)->name,queueElem->node->color,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
1288                 queueElem = queueElem->next;            
1289         }
1290         fprintf(stderr,"\n");
1291 }
1292
1293 void graph_print_queue_dist(DagNodeQueue *nqueue)
1294 {       
1295         DagNodeQueueElem *queueElem;
1296         int max, count;
1297         
1298         queueElem = nqueue->first;
1299         max = queueElem->node->DFS_fntm;
1300         count = 0;
1301         while(queueElem) {
1302                 fprintf(stderr,"** %25s %2.2i-%2.2i ",((ID *) queueElem->node->ob)->name,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
1303                 while (count < queueElem->node->DFS_dvtm-1) { fputc(' ',stderr); count++;}
1304                 fputc('|',stderr); 
1305                 while (count < queueElem->node->DFS_fntm-2) { fputc('-',stderr); count++;}
1306                 fputc('|',stderr);
1307                 fputc('\n',stderr);
1308                 count = 0;
1309                 queueElem = queueElem->next;            
1310         }
1311         fprintf(stderr,"\n");
1312 }
1313
1314 void graph_print_adj_list(void)
1315 {
1316         DagNode *node;
1317         DagAdjList *itA;
1318         
1319         node = (getMainDag())->DagNode.first;
1320         while(node) {
1321                 fprintf(stderr,"node : %s col: %i",((ID *) node->ob)->name, node->color);               
1322                 itA = node->child;
1323                 while (itA) {
1324                         fprintf(stderr,"-- %s ",((ID *) itA->node->ob)->name);
1325                         
1326                         itA = itA->next;
1327                 }
1328                 fprintf(stderr,"\n");
1329                 node = node->next;
1330         }
1331 }
1332
1333 /* ************************ API *********************** */
1334
1335 /* sort the base list on dependency order */
1336 void DAG_scene_sort(struct Scene *sce)
1337 {
1338         DagNode *node;
1339         DagNodeQueue *nqueue;
1340         DagAdjList *itA;
1341         int time;
1342         int skip = 0;
1343         ListBase tempbase;
1344         Base *base;
1345         
1346         tempbase.first= tempbase.last= NULL;
1347         
1348         build_dag(sce, DAG_RL_ALL_BUT_DATA);
1349         
1350         nqueue = queue_create(DAGQUEUEALLOC);
1351         
1352         for(node = sce->theDag->DagNode.first; node; node= node->next) {
1353                 node->color = DAG_WHITE;
1354         }
1355         
1356         time = 1;
1357         
1358         node = sce->theDag->DagNode.first;
1359         
1360         node->color = DAG_GRAY;
1361         time++;
1362         push_stack(nqueue,node);  
1363         
1364         while(nqueue->count) {
1365                 
1366                 skip = 0;
1367                 node = get_top_node_queue(nqueue);
1368                 
1369                 itA = node->child;
1370                 while(itA != NULL) {
1371                         if((itA->node->color == DAG_WHITE) ) {
1372                                 itA->node->DFS_dvtm = time;
1373                                 itA->node->color = DAG_GRAY;
1374                                 
1375                                 time++;
1376                                 push_stack(nqueue,itA->node);
1377                                 skip = 1;
1378                                 break;
1379                         } 
1380                         itA = itA->next;
1381                 }                       
1382                 
1383                 if (!skip) {
1384                         if (node) {
1385                                 node = pop_queue(nqueue);
1386                                 if (node->ob == sce)    // we are done
1387                                         break ;
1388                                 node->color = DAG_BLACK;
1389                                 
1390                                 time++;
1391                                 base = sce->base.first;
1392                                 while (base && base->object != node->ob)
1393                                         base = base->next;
1394                                 if(base) {
1395                                         BLI_remlink(&sce->base,base);
1396                                         BLI_addhead(&tempbase,base);
1397                                 }
1398                         }       
1399                 }
1400         }
1401         
1402         // temporal correction for circular dependancies
1403         base = sce->base.first;
1404         while (base) {
1405                 BLI_remlink(&sce->base,base);
1406                 BLI_addhead(&tempbase,base);
1407                 //if(G.f & G_DEBUG) 
1408                         printf("cyclic %s\n", base->object->id.name);
1409                 base = sce->base.first;
1410         }
1411         
1412         sce->base = tempbase;
1413         queue_delete(nqueue);
1414         
1415         if(G.f & G_DEBUG) {
1416                 printf("\nordered\n");
1417                 for(base = sce->base.first; base; base= base->next) {
1418                         printf(" %s\n", base->object->id.name);
1419                 }
1420         }
1421         /* temporal...? */
1422         G.scene->recalc |= SCE_PRV_CHANGED;     /* test for 3d preview */
1423 }
1424
1425 /* node was checked to have lasttime != curtime and is if type ID_OB */
1426 static void flush_update_node(DagNode *node, unsigned int layer, int curtime)
1427 {
1428         DagAdjList *itA;
1429         Object *ob, *obc;
1430         int oldflag, changed=0;
1431         unsigned int all_layer;
1432         
1433         node->lasttime= curtime;
1434         
1435         ob= node->ob;
1436         if(ob->recalc & OB_RECALC) {
1437                 all_layer= ob->lay;
1438                 /* got an object node that changes, now check relations */
1439                 for(itA = node->child; itA; itA= itA->next) {
1440                         all_layer |= itA->lay;
1441                         /* the relationship is visible */
1442                         if(itA->lay & layer) {
1443                                 if(itA->node->type==ID_OB) {
1444                                         obc= itA->node->ob;
1445                                         oldflag= obc->recalc;
1446                                         
1447                                         /* got a ob->obc relation, now check if flag needs flush */
1448                                         if(ob->recalc & OB_RECALC_OB) {
1449                                                 if(itA->type & DAG_RL_OB_OB) {
1450                                                         //printf("ob %s changes ob %s\n", ob->id.name, obc->id.name);
1451                                                         obc->recalc |= OB_RECALC_OB;
1452                                                 }
1453                                                 if(itA->type & DAG_RL_OB_DATA) {
1454                                                         //printf("ob %s changes obdata %s\n", ob->id.name, obc->id.name);
1455                                                         obc->recalc |= OB_RECALC_DATA;
1456                                                 }
1457                                         }
1458                                         if(ob->recalc & OB_RECALC_DATA) {
1459                                                 if(itA->type & DAG_RL_DATA_OB) {
1460                                                         //printf("obdata %s changes ob %s\n", ob->id.name, obc->id.name);
1461                                                         obc->recalc |= OB_RECALC_OB;
1462                                                 }
1463                                                 if(itA->type & DAG_RL_DATA_DATA) {
1464                                                         //printf("obdata %s changes obdata %s\n", ob->id.name, obc->id.name);
1465                                                         obc->recalc |= OB_RECALC_DATA;
1466                                                 }
1467                                         }
1468                                         if(oldflag!=obc->recalc) changed= 1;
1469                                 }
1470                         }
1471                 }
1472                 /* even nicer, we can clear recalc flags...  */
1473                 if((all_layer & layer)==0) {
1474                         /* but existing displaylists or derivedmesh should be freed */
1475                         if(ob->recalc & OB_RECALC_DATA)
1476                                 object_free_display(ob);
1477                         
1478                         ob->recalc &= ~OB_RECALC;
1479                 }
1480         }
1481         
1482         /* check case where child changes and parent forcing obdata to change */
1483         /* should be done regardless if this ob has recalc set */
1484         /* could merge this in with loop above...? (ton) */
1485         for(itA = node->child; itA; itA= itA->next) {
1486                 /* the relationship is visible */
1487                 if(itA->lay & layer) {
1488                         if(itA->node->type==ID_OB) {
1489                                 obc= itA->node->ob;
1490                                 /* child moves */
1491                                 if((obc->recalc & OB_RECALC)==OB_RECALC_OB) {
1492                                         /* parent has deforming info */
1493                                         if(itA->type & (DAG_RL_OB_DATA|DAG_RL_DATA_DATA)) {
1494                                                 // printf("parent %s changes ob %s\n", ob->id.name, obc->id.name);
1495                                                 obc->recalc |= OB_RECALC_DATA;
1496                                         }
1497                                 }
1498                         }
1499                 }
1500         }
1501         
1502         /* we only go deeper if node not checked or something changed  */
1503         for(itA = node->child; itA; itA= itA->next) {
1504                 if(changed || itA->node->lasttime!=curtime) 
1505                         flush_update_node(itA->node, layer, curtime);
1506         }
1507         
1508 }
1509
1510 /* node was checked to have lasttime != curtime , and is of type ID_OB */
1511 static unsigned int flush_layer_node(DagNode *node, int curtime)
1512 {
1513         DagAdjList *itA;
1514         
1515         node->lasttime= curtime;
1516         node->lay= ((Object *)node->ob)->lay;
1517         
1518         for(itA = node->child; itA; itA= itA->next) {
1519                 if(itA->node->type==ID_OB) {
1520                         if(itA->node->lasttime!=curtime) {
1521                                 itA->lay= flush_layer_node(itA->node, curtime);  // lay is only set once for each relation
1522                                 //printf("layer %d for relation %s to %s\n", itA->lay, ((Object *)node->ob)->id.name, ((Object *)itA->node->ob)->id.name);
1523                         }
1524                         else itA->lay= itA->node->lay;
1525                         
1526                         node->lay |= itA->lay;
1527                 }
1528         }
1529
1530         return node->lay;
1531 }
1532
1533 /* flushes all recalc flags in objects down the dependency tree */
1534 void DAG_scene_flush_update(Scene *sce, unsigned int lay)
1535 {
1536         DagNode *firstnode;
1537         DagAdjList *itA;
1538         int lasttime;
1539         
1540         if(sce->theDag==NULL) {
1541                 printf("DAG zero... not allowed to happen!\n");
1542                 DAG_scene_sort(sce);
1543         }
1544         
1545         firstnode= sce->theDag->DagNode.first;  // always scene node
1546         
1547         /* first we flush the layer flags */
1548         sce->theDag->time++;    // so we know which nodes were accessed
1549         lasttime= sce->theDag->time;
1550         for(itA = firstnode->child; itA; itA= itA->next) {
1551                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) 
1552                         flush_layer_node(itA->node, lasttime);
1553         }
1554         
1555         /* then we use the relationships + layer info to flush update events */
1556         sce->theDag->time++;    // so we know which nodes were accessed
1557         lasttime= sce->theDag->time;
1558         for(itA = firstnode->child; itA; itA= itA->next) {
1559                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) 
1560                         flush_update_node(itA->node, lay, lasttime);
1561         }
1562 }
1563
1564 static int object_modifiers_use_time(Object *ob)
1565 {
1566         ModifierData *md;
1567
1568         for (md=ob->modifiers.first; md; md=md->next)
1569                 if (modifier_dependsOnTime(md))
1570                         return 1;
1571
1572         return 0;
1573 }
1574
1575 static int exists_channel(Object *ob, char *name)
1576 {
1577         bActionStrip *strip;
1578         
1579         if(ob->action)
1580                 if(get_action_channel(ob->action, name))
1581                         return 1;
1582         
1583         for (strip=ob->nlastrips.first; strip; strip=strip->next)
1584                 if(get_action_channel(strip->act, name))
1585                         return 1;
1586         return 0;
1587 }
1588
1589 static void dag_object_time_update_flags(Object *ob)
1590 {
1591         
1592         if(ob->ipo) ob->recalc |= OB_RECALC_OB;
1593         else if(ob->constraints.first) {
1594                 bConstraint *con;
1595                 for (con = ob->constraints.first; con; con=con->next){
1596                         if (constraint_has_target(con)) {
1597                                 ob->recalc |= OB_RECALC_OB;
1598                                 break;
1599                         }
1600                 }
1601         }
1602         else if(ob->scriptlink.totscript) ob->recalc |= OB_RECALC_OB;
1603         else if(ob->parent) {
1604                 /* motion path or bone child */
1605                 if(ob->parent->type==OB_CURVE || ob->parent->type==OB_ARMATURE) ob->recalc |= OB_RECALC_OB;
1606         }
1607         
1608         if(ob->action || ob->nlastrips.first) {
1609                 /* since actions now are mixed, we set the recalcs on the safe side */
1610                 ob->recalc |= OB_RECALC_OB;
1611                 if(ob->type==OB_ARMATURE)
1612                         ob->recalc |= OB_RECALC_DATA;
1613                 else if(exists_channel(ob, "Shape"))
1614                         ob->recalc |= OB_RECALC_DATA;
1615                 else if(ob->dup_group) {
1616                         bActionStrip *strip;
1617                         /* this case is for groups with nla, whilst nla target has no action or nla */
1618                         for(strip= ob->nlastrips.first; strip; strip= strip->next) {
1619                                 if(strip->object)
1620                                         strip->object->recalc |= OB_RECALC;
1621                         }
1622                 }
1623         }
1624         else if(modifiers_isSoftbodyEnabled(ob)) ob->recalc |= OB_RECALC_DATA;
1625         else if(object_modifiers_use_time(ob)) ob->recalc |= OB_RECALC_DATA;
1626         else {
1627                 Mesh *me;
1628                 Curve *cu;
1629                 Lattice *lt;
1630                 
1631                 switch(ob->type) {
1632                         case OB_MESH:
1633                                 me= ob->data;
1634                                 if(me->key) {
1635                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
1636                                                 ob->recalc |= OB_RECALC_DATA;
1637                                                 ob->shapeflag &= ~OB_SHAPE_TEMPLOCK;
1638                                         }
1639                                 }
1640                                 else if(ob->effect.first) {
1641                                         Effect *eff= ob->effect.first;
1642                                         PartEff *paf= give_parteff(ob);
1643                                         
1644                                         if(eff->type==EFF_WAVE) 
1645                                                 ob->recalc |= OB_RECALC_DATA;
1646                                         else if(paf && paf->keys==NULL)
1647                                                 ob->recalc |= OB_RECALC_DATA;
1648                                         else if((paf->flag & PAF_STATIC)==0)
1649                                                 ob->recalc &= ~OB_RECALC;       /* NOTE! this is because particles are baked... depsgraph doesnt understand it */
1650                                 }
1651                                 if((ob->fluidsimFlag & OB_FLUIDSIM_ENABLE) && (ob->fluidsimSettings)) {
1652                                         // fluidsimSettings might not be initialized during load...
1653                                         if(ob->fluidsimSettings->type & (OB_FLUIDSIM_DOMAIN|OB_FLUIDSIM_PARTICLE)) {
1654                                                 ob->recalc |= OB_RECALC_DATA; // NT FSPARTICLE
1655                                         }
1656                                 }
1657                                 break;
1658                         case OB_CURVE:
1659                         case OB_SURF:
1660                                 cu= ob->data;
1661                                 if(cu->key) {
1662                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
1663                                                 ob->recalc |= OB_RECALC_DATA;
1664                                                 ob->shapeflag &= ~OB_SHAPE_TEMPLOCK;
1665                                         }
1666                                 }
1667                                 break;
1668                         case OB_FONT:
1669                                 cu= ob->data;
1670                                 if(cu->nurb.first==NULL && cu->str && cu->vfont)
1671                                         ob->recalc |= OB_RECALC_DATA;
1672                                 break;
1673                         case OB_LATTICE:
1674                                 lt= ob->data;
1675                                 if(lt->key) {
1676                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
1677                                                 ob->recalc |= OB_RECALC_DATA;
1678                                                 ob->shapeflag &= ~OB_SHAPE_TEMPLOCK;
1679                                         }
1680                                 }
1681                                         break;
1682                         case OB_MBALL:
1683                                 if(ob->transflag & OB_DUPLI) ob->recalc |= OB_RECALC_DATA;
1684                                 break;
1685                 }
1686         }               
1687 }
1688
1689 /* flag all objects that need recalc, for changes in time for example */
1690 void DAG_scene_update_flags(Scene *sce, unsigned int lay)
1691 {
1692         Base *base;
1693         Object *ob;
1694         Group *group;
1695         GroupObject *go;
1696         
1697         /* set ob flags where animated systems are */
1698         for(base= sce->base.first; base; base= base->next) {
1699                 ob= base->object;
1700                 
1701                 /* now if DagNode were part of base, the node->lay could be checked... */
1702                 /* we do all now, since the scene_flush checks layers and clears recalc flags even */
1703                 dag_object_time_update_flags(ob);
1704                 
1705                 /* handled in next loop */
1706                 if(ob->dup_group) 
1707                         ob->dup_group->id.flag |= LIB_DOIT;
1708                 
1709         }
1710         
1711         /* we do groups each once */
1712         for(group= G.main->group.first; group; group= group->id.next) {
1713                 if(group->id.flag & LIB_DOIT) {
1714                         for(go= group->gobject.first; go; go= go->next) {
1715                                 dag_object_time_update_flags(go->ob);
1716                         }
1717                 }
1718         }
1719         
1720         DAG_scene_flush_update(sce, lay);
1721         
1722         /* hrmf... an exception to look at once, for invisible camera object we do it over */
1723         if(sce->camera)
1724                 dag_object_time_update_flags(sce->camera);
1725         
1726         /* and store the info in groupobject */
1727         for(group= G.main->group.first; group; group= group->id.next) {
1728                 if(group->id.flag & LIB_DOIT) {
1729                         for(go= group->gobject.first; go; go= go->next) {
1730                                 go->recalc= go->ob->recalc;
1731 //                              printf("ob %s recalc %d\n", go->ob->id.name, go->recalc);
1732                         }
1733                         group->id.flag &= ~LIB_DOIT;
1734                 }
1735         }
1736         
1737 }
1738
1739 /* for depgraph updating, all layers visible in a screen */
1740 /* this is a copy from editscreen.c... I need to think over a more proper solution for this */
1741 /* probably the DAG_object_flush_update() should give layer too? */
1742 /* or some kind of dag context... (DAG_set_layer) */
1743 static unsigned int dag_screen_view3d_layers(void)
1744 {
1745         ScrArea *sa;
1746         int layer= 0;
1747         
1748         for(sa= G.curscreen->areabase.first; sa; sa= sa->next) {
1749                 if(sa->spacetype==SPACE_VIEW3D)
1750                         layer |= ((View3D *)sa->spacedata.first)->lay;
1751         }
1752         return layer;
1753 }
1754
1755
1756 /* flag this object and all its relations to recalc */
1757 /* if you need to do more objects, tag object yourself and
1758    use DAG_scene_flush_update() in end */
1759 void DAG_object_flush_update(Scene *sce, Object *ob, short flag)
1760 {
1761         Base *base;
1762         
1763         if(ob==NULL || sce->theDag==NULL) return;
1764         ob->recalc |= flag;
1765         
1766         /* all users of this ob->data should be checked */
1767         /* BUT! displists for curves are still only on cu */
1768         if(flag & OB_RECALC_DATA) {
1769                 if(ob->type!=OB_CURVE && ob->type!=OB_SURF) {
1770                         ID *id= ob->data;
1771                         if(id && id->us>1) {
1772                                 /* except when there's a key and shapes are locked */
1773                                 if(ob_get_key(ob) && (ob->shapeflag & (OB_SHAPE_LOCK|OB_SHAPE_TEMPLOCK)));
1774                                 else {
1775                                         for (base= sce->base.first; base; base= base->next) {
1776                                                 if (ob->data==base->object->data) {
1777                                                         base->object->recalc |= OB_RECALC_DATA;
1778                                                 }
1779                                         }
1780                                 }
1781                         }
1782                 }
1783         }
1784         
1785         if(G.curscreen)
1786                 DAG_scene_flush_update(sce, dag_screen_view3d_layers());
1787         else
1788                 DAG_scene_flush_update(sce, sce->lay);
1789 }
1790
1791 /* recursively descends tree, each node only checked once */
1792 /* node is checked to be of type object */
1793 static int parent_check_node(DagNode *node, int curtime)
1794 {
1795         DagAdjList *itA;
1796         
1797         node->lasttime= curtime;
1798         
1799         if(node->color==DAG_GRAY)
1800                 return DAG_GRAY;
1801         
1802         for(itA = node->child; itA; itA= itA->next) {
1803                 if(itA->node->type==ID_OB) {
1804                         
1805                         if(itA->node->color==DAG_GRAY)
1806                                 return DAG_GRAY;
1807
1808                         /* descend if not done */
1809                         if(itA->node->lasttime!=curtime) {
1810                                 itA->node->color= parent_check_node(itA->node, curtime);
1811                         
1812                                 if(itA->node->color==DAG_GRAY)
1813                                         return DAG_GRAY;
1814                         }
1815                 }
1816         }
1817         
1818         return DAG_WHITE;
1819 }
1820
1821 /* all nodes that influence this object get tagged, for calculating the exact
1822    position of this object at a given timeframe */
1823 void DAG_object_update_flags(Scene *sce, Object *ob, unsigned int lay)
1824 {
1825         DagNode *node;
1826         DagAdjList *itA;
1827         
1828         /* tag nodes unchecked */
1829         for(node = sce->theDag->DagNode.first; node; node= node->next) 
1830                 node->color = DAG_WHITE;
1831         
1832         node = dag_get_node(sce->theDag, ob);
1833         node->color = DAG_GRAY;
1834         
1835         sce->theDag->time++;
1836         node= sce->theDag->DagNode.first;
1837         for(itA = node->child; itA; itA= itA->next) {
1838                 if(itA->node->type==ID_OB && itA->node->lasttime!=sce->theDag->time)
1839                         itA->node->color= parent_check_node(itA->node, sce->theDag->time);
1840         }
1841         
1842         /* set recalcs and flushes */
1843         DAG_scene_update_flags(sce, lay);
1844         
1845         /* now we clear recalcs, unless color is set */
1846         for(node = sce->theDag->DagNode.first; node; node= node->next) {
1847                 if(node->type==ID_OB && node->color==DAG_WHITE) {
1848                         Object *ob= node->ob;
1849                         ob->recalc= 0;
1850                 }
1851         }
1852 }
1853
1854 /* ******************* DAG FOR ARMATURE POSE ***************** */
1855
1856 /* we assume its an armature with pose */
1857 void DAG_pose_sort(Object *ob)
1858 {
1859         bPose *pose= ob->pose;
1860         bPoseChannel *pchan;
1861         bConstraint *con;
1862         DagNode *node;
1863         DagNode *node2, *node3;
1864         DagNode *rootnode;
1865         DagForest *dag;
1866         DagNodeQueue *nqueue;
1867         DagAdjList *itA;
1868         ListBase tempbase;
1869         int skip = 0;
1870         
1871         dag = dag_init();
1872         ugly_hack_sorry= 0;     // no ID structs
1873
1874         rootnode = dag_add_node(dag, NULL);     // node->ob becomes NULL
1875         
1876         /* we add the hierarchy and the constraints */
1877         for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
1878                 int addtoroot = 1;
1879                 
1880                 node = dag_get_node(dag, pchan);
1881                 
1882                 if(pchan->parent) {
1883                         node2 = dag_get_node(dag, pchan->parent);
1884                         dag_add_relation(dag, node2, node, 0);
1885                         addtoroot = 0;
1886                 }
1887                 for (con = pchan->constraints.first; con; con=con->next){
1888                         if (constraint_has_target(con)) {
1889                                 char *subtarget;
1890                                 Object *target = get_constraint_target(con, &subtarget);
1891                                 
1892                                 if (target==ob && subtarget) {
1893                                         bPoseChannel *target= get_pose_channel(ob->pose, subtarget);
1894                                         if(target) {
1895                                                 node2= dag_get_node(dag, target);
1896                                                 dag_add_relation(dag, node2, node, 0);
1897                                                 
1898                                                 if(con->type==CONSTRAINT_TYPE_KINEMATIC) {
1899                                                         bKinematicConstraint *data = (bKinematicConstraint*)con->data;
1900                                                         bPoseChannel *parchan;
1901                                                         int segcount= 0;
1902                                                         
1903                                                         /* exclude tip from chain? */
1904                                                         if(!(data->flag & CONSTRAINT_IK_TIP))
1905                                                                 parchan= pchan->parent;
1906                                                         else
1907                                                                 parchan= pchan;
1908                                                         
1909                                                         /* Walk to the chain's root */
1910                                                         while (parchan){
1911                                                                 node3= dag_get_node(dag, parchan);
1912                                                                 dag_add_relation(dag, node2, node3, 0);
1913                                                                 
1914                                                                 segcount++;
1915                                                                 if(segcount==data->rootbone || segcount>255) break; // 255 is weak
1916                                                                 parchan= parchan->parent;
1917                                                         }
1918                                                 }
1919                                         }
1920                                 }
1921                         }
1922                 }
1923                 if (addtoroot == 1 )
1924                         dag_add_relation(dag, rootnode, node, 0);
1925         }
1926
1927         /* now we try to sort... */
1928         tempbase.first= tempbase.last= NULL;
1929
1930         nqueue = queue_create(DAGQUEUEALLOC);
1931         
1932         /* tag nodes unchecked */
1933         for(node = dag->DagNode.first; node; node= node->next) 
1934                 node->color = DAG_WHITE;
1935         
1936         node = dag->DagNode.first;
1937         
1938         node->color = DAG_GRAY;
1939         push_stack(nqueue, node);  
1940         
1941         while(nqueue->count) {
1942                 
1943                 skip = 0;
1944                 node = get_top_node_queue(nqueue);
1945                 
1946                 itA = node->child;
1947                 while(itA != NULL) {
1948                         if((itA->node->color == DAG_WHITE) ) {
1949                                 itA->node->color = DAG_GRAY;
1950                                 push_stack(nqueue,itA->node);
1951                                 skip = 1;
1952                                 break;
1953                         } 
1954                         itA = itA->next;
1955                 }                       
1956                 
1957                 if (!skip) {
1958                         if (node) {
1959                                 node = pop_queue(nqueue);
1960                                 if (node->ob == NULL)   // we are done
1961                                         break ;
1962                                 node->color = DAG_BLACK;
1963                                 
1964                                 /* put node in new list */
1965                                 BLI_remlink(&pose->chanbase, node->ob);
1966                                 BLI_addhead(&tempbase, node->ob);
1967                         }       
1968                 }
1969         }
1970         
1971         // temporal correction for circular dependancies
1972         while(pose->chanbase.first) {
1973                 pchan= pose->chanbase.first;
1974                 BLI_remlink(&pose->chanbase, pchan);
1975                 BLI_addhead(&tempbase, pchan);
1976
1977                 printf("cyclic %s\n", pchan->name);
1978         }
1979         
1980         pose->chanbase = tempbase;
1981         queue_delete(nqueue);
1982         
1983 //      printf("\nordered\n");
1984 //      for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
1985 //              printf(" %s\n", pchan->name);
1986 //      }
1987         
1988         free_forest( dag );
1989         MEM_freeN( dag );
1990         
1991         ugly_hack_sorry= 1;
1992 }
1993
1994
1995