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