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