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