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