Cycles: svn merge -r39870:r40266 https://svn.blender.org/svnroot/bf-blender/trunk...
[blender-staging.git] / source / blender / blenkernel / intern / depsgraph.c
1 /*
2  * $Id$
3  *
4  * ***** BEGIN GPL 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.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2004 Blender Foundation.
21  * All rights reserved.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/depsgraph.c
29  *  \ingroup bke
30  */
31
32  
33 #include <stdio.h>
34 #include <string.h>
35 #include <math.h>
36
37 #include "MEM_guardedalloc.h"
38
39 #include "BLI_winstuff.h"
40 #include "BLI_utildefines.h"
41 #include "BLI_ghash.h"
42
43 #include "DNA_anim_types.h"
44 #include "DNA_camera_types.h"
45 #include "DNA_group_types.h"
46 #include "DNA_lattice_types.h"
47 #include "DNA_key_types.h"
48 #include "DNA_material_types.h"
49 #include "DNA_mesh_types.h"
50 #include "DNA_node_types.h"
51 #include "DNA_scene_types.h"
52 #include "DNA_screen_types.h"
53 #include "DNA_windowmanager_types.h"
54
55 #include "BKE_animsys.h"
56 #include "BKE_action.h"
57 #include "BKE_effect.h"
58 #include "BKE_fcurve.h"
59 #include "BKE_global.h"
60 #include "BKE_group.h"
61 #include "BKE_key.h"
62 #include "BKE_library.h"
63 #include "BKE_main.h"
64 #include "BKE_node.h"
65 #include "BKE_mball.h"
66 #include "BKE_modifier.h"
67 #include "BKE_object.h"
68 #include "BKE_particle.h"
69 #include "BKE_pointcache.h"
70 #include "BKE_scene.h"
71 #include "BKE_screen.h"
72 #include "BKE_utildefines.h"
73
74 #include "depsgraph_private.h"
75  
76 /* Queue and stack operations for dag traversal 
77  *
78  * the queue store a list of freenodes to avoid successives alloc/dealloc
79  */
80
81 DagNodeQueue * queue_create (int slots) 
82 {
83         DagNodeQueue * queue;
84         DagNodeQueueElem * elem;
85         int i;
86         
87         queue = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
88         queue->freenodes = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
89         queue->count = 0;
90         queue->maxlevel = 0;
91         queue->first = queue->last = NULL;
92         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem3");
93         elem->node = NULL;
94         elem->next = NULL;
95         queue->freenodes->first = queue->freenodes->last = elem;
96         
97         for (i = 1; i <slots;i++) {
98                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem4");
99                 elem->node = NULL;
100                 elem->next = NULL;
101                 queue->freenodes->last->next = elem;
102                 queue->freenodes->last = elem;
103         }
104         queue->freenodes->count = slots;
105         return queue;
106 }
107
108 void queue_raz(DagNodeQueue *queue)
109 {
110         DagNodeQueueElem * elem;
111         
112         elem = queue->first;
113         if (queue->freenodes->last)
114                 queue->freenodes->last->next = elem;
115         else
116                 queue->freenodes->first = queue->freenodes->last = elem;
117         
118         elem->node = NULL;
119         queue->freenodes->count++;
120         while (elem->next) {
121                 elem = elem->next;
122                 elem->node = NULL;
123                 queue->freenodes->count++;
124         }
125         queue->freenodes->last = elem;
126         queue->count = 0;
127 }
128
129 void queue_delete(DagNodeQueue *queue)
130 {
131         DagNodeQueueElem * elem;
132         DagNodeQueueElem * temp;
133         
134         elem = queue->first;
135         while (elem) {
136                 temp = elem;
137                 elem = elem->next;
138                 MEM_freeN(temp);
139         }
140         
141         elem = queue->freenodes->first;
142         while (elem) {
143                 temp = elem;
144                 elem = elem->next;
145                 MEM_freeN(temp);
146         }
147         
148         MEM_freeN(queue->freenodes);                    
149         MEM_freeN(queue);                       
150 }
151
152 /* insert in queue, remove in front */
153 void push_queue(DagNodeQueue *queue, DagNode *node)
154 {
155         DagNodeQueueElem * elem;
156         int i;
157
158         if (node == NULL) {
159                 fprintf(stderr,"pushing null node \n");
160                 return;
161         }
162         /*fprintf(stderr,"BFS push : %s %d\n",((ID *) node->ob)->name, queue->count);*/
163
164         elem = queue->freenodes->first;
165         if (elem != NULL) {
166                 queue->freenodes->first = elem->next;
167                 if ( queue->freenodes->last == elem) {
168                         queue->freenodes->last = NULL;
169                         queue->freenodes->first = NULL;
170                 }
171                 queue->freenodes->count--;
172         } else { /* alllocating more */         
173                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
174                 elem->node = NULL;
175                 elem->next = NULL;
176                 queue->freenodes->first = queue->freenodes->last = elem;
177
178                 for (i = 1; i <DAGQUEUEALLOC;i++) {
179                         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
180                         elem->node = NULL;
181                         elem->next = NULL;
182                         queue->freenodes->last->next = elem;
183                         queue->freenodes->last = elem;
184                 }
185                 queue->freenodes->count = DAGQUEUEALLOC;
186                         
187                 elem = queue->freenodes->first; 
188                 queue->freenodes->first = elem->next;   
189         }
190         elem->next = NULL;
191         elem->node = node;
192         if (queue->last != NULL)
193                 queue->last->next = elem;
194         queue->last = elem;
195         if (queue->first == NULL) {
196                 queue->first = elem;
197         }
198         queue->count++;
199 }
200
201
202 /* insert in front, remove in front */
203 void push_stack(DagNodeQueue *queue, DagNode *node)
204 {
205         DagNodeQueueElem * elem;
206         int i;
207
208         elem = queue->freenodes->first; 
209         if (elem != NULL) {
210                 queue->freenodes->first = elem->next;
211                 if ( queue->freenodes->last == elem) {
212                         queue->freenodes->last = NULL;
213                         queue->freenodes->first = NULL;
214                 }
215                 queue->freenodes->count--;
216         } else { /* alllocating more */
217                 elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
218                 elem->node = NULL;
219                 elem->next = NULL;
220                 queue->freenodes->first = queue->freenodes->last = elem;
221
222                 for (i = 1; i <DAGQUEUEALLOC;i++) {
223                         elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
224                         elem->node = NULL;
225                         elem->next = NULL;
226                         queue->freenodes->last->next = elem;
227                         queue->freenodes->last = elem;
228                 }
229                 queue->freenodes->count = DAGQUEUEALLOC;
230                         
231                 elem = queue->freenodes->first; 
232                 queue->freenodes->first = elem->next;   
233         }
234         elem->next = queue->first;
235         elem->node = node;
236         queue->first = elem;
237         if (queue->last == NULL)
238                 queue->last = elem;
239         queue->count++;
240 }
241
242
243 DagNode * pop_queue(DagNodeQueue *queue)
244 {
245         DagNodeQueueElem * elem;
246         DagNode *node;
247
248         elem = queue->first;
249         if (elem) {
250                 queue->first = elem->next;
251                 if (queue->last == elem) {
252                         queue->last=NULL;
253                         queue->first=NULL;
254                 }
255                 queue->count--;
256                 if (queue->freenodes->last)
257                         queue->freenodes->last->next=elem;
258                 queue->freenodes->last=elem;
259                 if (queue->freenodes->first == NULL)
260                         queue->freenodes->first=elem;
261                 node = elem->node;
262                 elem->node = NULL;
263                 elem->next = NULL;
264                 queue->freenodes->count++;
265                 return node;
266         } else {
267                 fprintf(stderr,"return null \n");
268                 return NULL;
269         }
270 }
271
272 void    *pop_ob_queue(struct DagNodeQueue *queue) {
273         return(pop_queue(queue)->ob);
274 }
275
276 DagNode * get_top_node_queue(DagNodeQueue *queue) 
277 {
278         return queue->first->node;
279 }
280
281 int             queue_count(struct DagNodeQueue *queue){
282         return queue->count;
283 }
284
285
286 DagForest *dag_init(void)
287 {
288         DagForest *forest;
289         /* use callocN to init all zero */
290         forest = MEM_callocN(sizeof(DagForest),"DAG root");
291         return forest;
292 }
293
294 /* isdata = object data... */
295 // XXX this needs to be extended to be more flexible (so that not only objects are evaluated via depsgraph)...
296 static void dag_add_driver_relation(AnimData *adt, DagForest *dag, DagNode *node, int isdata)
297 {
298         FCurve *fcu;
299         DagNode *node1;
300         
301         for (fcu= adt->drivers.first; fcu; fcu= fcu->next) {
302                 ChannelDriver *driver= fcu->driver;
303                 DriverVar *dvar;
304                 int isdata_fcu = isdata || (fcu->rna_path && strstr(fcu->rna_path, "modifiers["));
305                 
306                 /* loop over variables to get the target relationships */
307                 for (dvar= driver->variables.first; dvar; dvar= dvar->next) {
308                         /* only used targets */
309                         DRIVER_TARGETS_USED_LOOPER(dvar) 
310                         {
311                                 if (dtar->id) {
312                                         // FIXME: other data types need to be added here so that they can work!
313                                         if (GS(dtar->id->name)==ID_OB) {
314                                                 Object *ob= (Object *)dtar->id;
315                                                 
316                                                 /* normal channel-drives-channel */
317                                                 node1 = dag_get_node(dag, dtar->id);
318                                                 
319                                                 /* check if bone... */
320                                                 if ((ob->type==OB_ARMATURE) && 
321                                                         ( ((dtar->rna_path) && strstr(dtar->rna_path, "pose.bones[")) || 
322                                                           ((dtar->flag & DTAR_FLAG_STRUCT_REF) && (dtar->pchan_name[0])) )) 
323                                                 {
324                                                         dag_add_relation(dag, node1, node, isdata_fcu?DAG_RL_DATA_DATA:DAG_RL_DATA_OB, "Driver");
325                                                 }
326                                                 /* check if ob data */
327                                                 else if (dtar->rna_path && strstr(dtar->rna_path, "data."))
328                                                         dag_add_relation(dag, node1, node, isdata_fcu?DAG_RL_DATA_DATA:DAG_RL_DATA_OB, "Driver");
329                                                 /* normal */
330                                                 else
331                                                         dag_add_relation(dag, node1, node, isdata_fcu?DAG_RL_OB_DATA:DAG_RL_OB_OB, "Driver");
332                                         }
333                                 }
334                         }
335                         DRIVER_TARGETS_LOOPER_END
336                 }
337         }
338 }
339
340 static void dag_add_collision_field_relation(DagForest *dag, Scene *scene, Object *ob, DagNode *node)
341 {
342         Base *base;
343         DagNode *node2;
344
345         // would be nice to have a list of colliders here
346         // so for now walk all objects in scene check 'same layer rule'
347         for(base = scene->base.first; base; base= base->next) {
348                 if((base->lay & ob->lay) && base->object->pd) {
349                         Object *ob1= base->object;
350                         if((ob1->pd->deflect || ob1->pd->forcefield) && (ob1 != ob))  {
351                                 node2 = dag_get_node(dag, ob1);                                 
352                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Field Collision");
353                         }
354                 }
355         }
356 }
357
358 static void build_dag_object(DagForest *dag, DagNode *scenenode, Scene *scene, Object *ob, int mask)
359 {
360         bConstraint *con;
361         DagNode * node;
362         DagNode * node2;
363         DagNode * node3;
364         Key *key;
365         ParticleSystem *psys;
366         int addtoroot= 1;
367         
368         node = dag_get_node(dag, ob);
369         
370         if ((ob->data) && (mask&DAG_RL_DATA)) {
371                 node2 = dag_get_node(dag,ob->data);
372                 dag_add_relation(dag,node,node2,DAG_RL_DATA, "Object-Data Relation");
373                 node2->first_ancestor = ob;
374                 node2->ancestor_count += 1;
375         }
376
377         /* also build a custom data mask for dependencies that need certain layers */
378         node->customdata_mask= 0;
379         
380         if (ob->type == OB_ARMATURE) {
381                 if (ob->pose){
382                         bPoseChannel *pchan;
383                         bConstraint *con;
384                         
385                         for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next) {
386                                 for (con = pchan->constraints.first; con; con=con->next) {
387                                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
388                                         ListBase targets = {NULL, NULL};
389                                         bConstraintTarget *ct;
390                                         
391                                         if (cti && cti->get_constraint_targets) {
392                                                 cti->get_constraint_targets(con, &targets);
393                                                 
394                                                 for (ct= targets.first; ct; ct= ct->next) {
395                                                         if (ct->tar && ct->tar != ob) {
396                                                                 // fprintf(stderr,"armature %s target :%s \n", ob->id.name, target->id.name);
397                                                                 node3 = dag_get_node(dag, ct->tar);
398                                                                 
399                                                                 if (ct->subtarget[0])
400                                                                         dag_add_relation(dag,node3,node, DAG_RL_OB_DATA|DAG_RL_DATA_DATA, cti->name);
401                                                                 else if(ELEM3(con->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO, CONSTRAINT_TYPE_SPLINEIK))        
402                                                                         dag_add_relation(dag,node3,node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, cti->name);
403                                                                 else
404                                                                         dag_add_relation(dag,node3,node, DAG_RL_OB_DATA, cti->name);
405                                                         }
406                                                 }
407                                                 
408                                                 if (cti->flush_constraint_targets)
409                                                         cti->flush_constraint_targets(con, &targets, 1);
410                                         }
411                                         
412                                 }
413                         }
414                 }
415         }
416         
417         /* driver dependencies, nla modifiers */
418 #if 0 // XXX old animation system
419         if(ob->nlastrips.first) {
420                 bActionStrip *strip;
421                 bActionChannel *chan;
422                 for(strip= ob->nlastrips.first; strip; strip= strip->next) {
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, "NLA Strip Modifier");
429                                         }
430                                 }
431                         }
432                 }
433         }
434 #endif // XXX old animation system
435         if (ob->adt)
436                 dag_add_driver_relation(ob->adt, dag, node, (ob->type == OB_ARMATURE)); // XXX isdata arg here doesn't give an accurate picture of situation
437                 
438         key= ob_get_key(ob);
439         if (key && key->adt)
440                 dag_add_driver_relation(key->adt, dag, node, 1);
441
442         if (ob->modifiers.first) {
443                 ModifierData *md;
444                 
445                 for(md=ob->modifiers.first; md; md=md->next) {
446                         ModifierTypeInfo *mti = modifierType_getInfo(md->type);
447                         
448                         if (mti->updateDepgraph) mti->updateDepgraph(md, dag, scene, ob, node);
449                 }
450         }
451         if (ob->parent) {
452                 node2 = dag_get_node(dag,ob->parent);
453                 
454                 switch(ob->partype) {
455                         case PARSKEL:
456                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Parent");
457                                 break;
458                         case PARVERT1: case PARVERT3:
459                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB, "Vertex Parent");
460                                 node2->customdata_mask |= CD_MASK_ORIGINDEX;
461                                 break;
462                         case PARBONE:
463                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB, "Bone Parent");
464                                 break;
465                         default:
466                                 if(ob->parent->type==OB_LATTICE) 
467                                         dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Lattice Parent");
468                                 else if(ob->parent->type==OB_CURVE) {
469                                         Curve *cu= ob->parent->data;
470                                         if(cu->flag & CU_PATH) 
471                                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB, "Curve Parent");
472                                         else
473                                                 dag_add_relation(dag,node2,node,DAG_RL_OB_OB, "Curve Parent");
474                                 }
475                                 else
476                                         dag_add_relation(dag,node2,node,DAG_RL_OB_OB, "Parent");
477                 }
478                 /* exception case: parent is duplivert */
479                 if(ob->type==OB_MBALL && (ob->parent->transflag & OB_DUPLIVERTS)) {
480                         dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Duplivert");
481                 }
482                 
483                 addtoroot = 0;
484         }
485         if (ob->proxy) {
486                 node2 = dag_get_node(dag, ob->proxy);
487                 dag_add_relation(dag, node, node2, DAG_RL_DATA_DATA|DAG_RL_OB_OB, "Proxy");
488                 /* inverted relation, so addtoroot shouldn't be set to zero */
489         }
490         
491         if (ob->transflag & OB_DUPLI) {
492                 if((ob->transflag & OB_DUPLIGROUP) && ob->dup_group) {
493                         GroupObject *go;
494                         for(go= ob->dup_group->gobject.first; go; go= go->next) {
495                                 if(go->ob) {
496                                         node2 = dag_get_node(dag, go->ob);
497                                         /* node2 changes node1, this keeps animations updated in groups?? not logical? */
498                                         dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Dupligroup");
499                                 }
500                         }
501                 }
502         }
503
504         /* softbody collision  */
505         if ((ob->type==OB_MESH) || (ob->type==OB_CURVE) || (ob->type==OB_LATTICE)) {
506                 if(modifiers_isSoftbodyEnabled(ob) || modifiers_isClothEnabled(ob) || ob->particlesystem.first)
507                         dag_add_collision_field_relation(dag, scene, ob, node); /* TODO: use effectorweight->group */
508         }
509         
510         /* object data drivers */
511         if (ob->data) {
512                 AnimData *adt= BKE_animdata_from_id((ID *)ob->data);
513                 if (adt)
514                         dag_add_driver_relation(adt, dag, node, 1);
515         }
516         
517         /* object type/data relationships */
518         switch (ob->type) {
519                 case OB_CAMERA:
520                 {
521                         Camera *cam = (Camera *)ob->data;
522                         
523                         if (cam->dof_ob) {
524                                 node2 = dag_get_node(dag, cam->dof_ob);
525                                 dag_add_relation(dag,node2,node,DAG_RL_OB_OB, "Camera DoF");
526                         }
527                 }
528                         break;
529                 case OB_MBALL: 
530                 {
531                         Object *mom= find_basis_mball(scene, ob);
532                         
533                         if(mom!=ob) {
534                                 node2 = dag_get_node(dag, mom);
535                                 dag_add_relation(dag,node,node2,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Metaball");  // mom depends on children!
536                         }
537                 }
538                         break;
539                 case OB_CURVE:
540                 {
541                         Curve *cu= ob->data;
542                         
543                         if(cu->bevobj) {
544                                 node2 = dag_get_node(dag, cu->bevobj);
545                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Curve Bevel");
546                         }
547                         if(cu->taperobj) {
548                                 node2 = dag_get_node(dag, cu->taperobj);
549                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Curve Taper");
550                         }
551                 }
552                         break;
553                 case OB_FONT: 
554                 {
555                         Curve *cu= ob->data;
556                         
557                         if(cu->textoncurve) {
558                                 node2 = dag_get_node(dag, cu->textoncurve);
559                                 dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Texture On Curve");
560                         }
561                 }
562                         break;
563         }
564         
565         /* particles */
566         psys= ob->particlesystem.first;
567         if(psys) {
568                 GroupObject *go;
569
570                 for(; psys; psys=psys->next) {
571                         BoidRule *rule = NULL;
572                         BoidState *state = NULL;
573                         ParticleSettings *part= psys->part;
574                         ListBase *effectors = NULL;
575                         EffectorCache *eff;
576
577                         dag_add_relation(dag, node, node, DAG_RL_OB_DATA, "Particle-Object Relation");
578
579                         if(!psys_check_enabled(ob, psys))
580                                 continue;
581
582                         if(ELEM(part->phystype,PART_PHYS_KEYED,PART_PHYS_BOIDS)) {
583                                 ParticleTarget *pt = psys->targets.first;
584
585                                 for(; pt; pt=pt->next) {
586                                         if(pt->ob && BLI_findlink(&pt->ob->particlesystem, pt->psys-1)) {
587                                                 node2 = dag_get_node(dag, pt->ob);
588                                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Particle Targets");
589                                         }
590                            }
591                         }
592
593                         if(part->ren_as == PART_DRAW_OB && part->dup_ob) {
594                                 node2 = dag_get_node(dag, part->dup_ob);
595                                 dag_add_relation(dag, node, node2, DAG_RL_OB_OB, "Particle Object Visualisation");
596                                 if(part->dup_ob->type == OB_MBALL)
597                                         dag_add_relation(dag, node, node2, DAG_RL_DATA_DATA, "Particle Object Visualisation");
598                         }
599
600                         if(part->ren_as == PART_DRAW_GR && part->dup_group) {
601                                 for(go=part->dup_group->gobject.first; go; go=go->next) {
602                                         node2 = dag_get_node(dag, go->ob);
603                                         dag_add_relation(dag, node2, node, DAG_RL_OB_OB, "Particle Group Visualisation");
604                                 }
605                         }
606
607                         effectors = pdInitEffectors(scene, ob, psys, part->effector_weights);
608
609                         if(effectors) for(eff = effectors->first; eff; eff=eff->next) {
610                                 if(eff->psys) {
611                                         node2 = dag_get_node(dag, eff->ob);
612                                         dag_add_relation(dag, node2, node, DAG_RL_DATA_DATA|DAG_RL_OB_DATA, "Particle Field");
613                                 }
614                         }
615
616                         pdEndEffectors(&effectors);
617
618                         if(part->boids) {
619                                 for(state = part->boids->states.first; state; state=state->next) {
620                                         for(rule = state->rules.first; rule; rule=rule->next) {
621                                                 Object *ruleob = NULL;
622                                                 if(rule->type==eBoidRuleType_Avoid)
623                                                         ruleob = ((BoidRuleGoalAvoid*)rule)->ob;
624                                                 else if(rule->type==eBoidRuleType_FollowLeader)
625                                                         ruleob = ((BoidRuleFollowLeader*)rule)->ob;
626
627                                                 if(ruleob) {
628                                                         node2 = dag_get_node(dag, ruleob);
629                                                         dag_add_relation(dag, node2, node, DAG_RL_OB_DATA, "Boid Rule");
630                                                 }
631                                         }
632                                 }
633                         }
634                 }
635         }
636         
637         /* object constraints */
638         for (con = ob->constraints.first; con; con=con->next) {
639                 bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
640                 ListBase targets = {NULL, NULL};
641                 bConstraintTarget *ct;
642                 
643                 if (cti && cti->get_constraint_targets) {
644                         cti->get_constraint_targets(con, &targets);
645                         
646                         for (ct= targets.first; ct; ct= ct->next) {
647                                 Object *obt;
648                                 
649                                 if (ct->tar)
650                                         obt= ct->tar;
651                                 else
652                                         continue;
653                                 
654                                 node2 = dag_get_node(dag, obt);
655                                 if (ELEM(con->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO))
656                                         dag_add_relation(dag, node2, node, DAG_RL_DATA_OB|DAG_RL_OB_OB, cti->name);
657                                 else {
658                                         if (ELEM3(obt->type, OB_ARMATURE, OB_MESH, OB_LATTICE) && (ct->subtarget[0])) {
659                                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_OB|DAG_RL_OB_OB, cti->name);
660                                                 if (obt->type == OB_MESH)
661                                                         node2->customdata_mask |= CD_MASK_MDEFORMVERT;
662                                         }
663                                         else
664                                                 dag_add_relation(dag, node2, node, DAG_RL_OB_OB, cti->name);
665                                 }
666                                 addtoroot = 0;
667                         }
668                         
669                         if (cti->flush_constraint_targets)
670                                 cti->flush_constraint_targets(con, &targets, 1);
671                 }
672         }
673
674         if (addtoroot == 1 )
675                 dag_add_relation(dag,scenenode,node,DAG_RL_SCENE, "Scene Relation");
676 }
677
678 struct DagForest *build_dag(Main *bmain, Scene *sce, short mask) 
679 {
680         Base *base;
681         Object *ob;
682         Group *group;
683         GroupObject *go;
684         DagNode *node;
685         DagNode *scenenode;
686         DagForest *dag;
687         DagAdjList *itA;
688
689         dag = sce->theDag;
690         sce->dagisvalid=1;
691         if ( dag)
692                 free_forest( dag ); 
693         else {
694                 dag = dag_init();
695                 sce->theDag = dag;
696         }
697         
698         /* add base node for scene. scene is always the first node in DAG */
699         scenenode = dag_add_node(dag, sce);     
700         
701         /* add current scene objects */
702         for(base = sce->base.first; base; base= base->next) {
703                 ob= base->object;
704                 
705                 build_dag_object(dag, scenenode, sce, ob, mask);
706                 if(ob->proxy)
707                         build_dag_object(dag, scenenode, sce, ob->proxy, mask);
708                 
709                 /* handled in next loop */
710                 if(ob->dup_group) 
711                         ob->dup_group->id.flag |= LIB_DOIT;
712         }
713         
714         /* add groups used in current scene objects */
715         for(group= bmain->group.first; group; group= group->id.next) {
716                 if(group->id.flag & LIB_DOIT) {
717                         for(go= group->gobject.first; go; go= go->next) {
718                                 build_dag_object(dag, scenenode, sce, go->ob, mask);
719                         }
720                         group->id.flag &= ~LIB_DOIT;
721                 }
722         }
723         
724         /* Now all relations were built, but we need to solve 1 exceptional case;
725            When objects have multiple "parents" (for example parent + constraint working on same object)
726            the relation type has to be synced. One of the parents can change, and should give same event to child */
727         
728         /* nodes were callocced, so we can use node->color for temporal storage */
729         for(node = sce->theDag->DagNode.first; node; node= node->next) {
730                 if(node->type==ID_OB) {
731                         for(itA = node->child; itA; itA= itA->next) {
732                                 if(itA->node->type==ID_OB) {
733                                         itA->node->color |= itA->type;
734                                 }
735                         }
736
737                         /* also flush custom data mask */
738                         ((Object*)node->ob)->customdata_mask= node->customdata_mask;
739                 }
740         }
741         /* now set relations equal, so that when only one parent changes, the correct recalcs are found */
742         for(node = sce->theDag->DagNode.first; node; node= node->next) {
743                 if(node->type==ID_OB) {
744                         for(itA = node->child; itA; itA= itA->next) {
745                                 if(itA->node->type==ID_OB) {
746                                         itA->type |= itA->node->color;
747                                 }
748                         }
749                 }
750         }
751         
752         // cycle detection and solving
753         // solve_cycles(dag);   
754         
755         return dag;
756 }
757
758
759 void free_forest(DagForest *Dag) 
760 {  /* remove all nodes and deps */
761         DagNode *tempN;
762         DagAdjList *tempA;      
763         DagAdjList *itA;
764         DagNode *itN = Dag->DagNode.first;
765         
766         while (itN) {
767                 itA = itN->child;       
768                 while (itA) {
769                         tempA = itA;
770                         itA = itA->next;
771                         MEM_freeN(tempA);                       
772                 }
773                 
774                 itA = itN->parent;      
775                 while (itA) {
776                         tempA = itA;
777                         itA = itA->next;
778                         MEM_freeN(tempA);                       
779                 }
780                 
781                 tempN = itN;
782                 itN = itN->next;
783                 MEM_freeN(tempN);
784         }
785
786         BLI_ghash_free(Dag->nodeHash, NULL, NULL);
787         Dag->nodeHash= NULL;
788         Dag->DagNode.first = NULL;
789         Dag->DagNode.last = NULL;
790         Dag->numNodes = 0;
791
792 }
793
794 DagNode * dag_find_node (DagForest *forest,void * fob)
795 {
796         if(forest->nodeHash)
797                 return BLI_ghash_lookup(forest->nodeHash, fob);
798
799         return NULL;
800 }
801
802 static int ugly_hack_sorry= 1;  // prevent type check
803
804 /* no checking of existence, use dag_find_node first or dag_get_node */
805 DagNode * dag_add_node (DagForest *forest, void * fob)
806 {
807         DagNode *node;
808                 
809         node = MEM_callocN(sizeof(DagNode),"DAG node");
810         if (node) {
811                 node->ob = fob;
812                 node->color = DAG_WHITE;
813
814                 if(ugly_hack_sorry) node->type = GS(((ID *) fob)->name);        // sorry, done for pose sorting
815                 if (forest->numNodes) {
816                         ((DagNode *) forest->DagNode.last)->next = node;
817                         forest->DagNode.last = node;
818                         forest->numNodes++;
819                 } else {
820                         forest->DagNode.last = node;
821                         forest->DagNode.first = node;
822                         forest->numNodes = 1;
823                 }
824
825                 if(!forest->nodeHash)
826                         forest->nodeHash= BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "dag_add_node gh");
827                 BLI_ghash_insert(forest->nodeHash, fob, node);
828         }
829
830         return node;
831 }
832
833 DagNode * dag_get_node (DagForest *forest,void * fob)
834 {
835         DagNode *node;
836         
837         node = dag_find_node (forest, fob);     
838         if (!node) 
839                 node = dag_add_node(forest, fob);
840         return node;
841 }
842
843
844
845 DagNode * dag_get_sub_node (DagForest *forest,void * fob)
846 {
847         DagNode *node;
848         DagAdjList *mainchild, *prev=NULL;
849         
850         mainchild = ((DagNode *) forest->DagNode.first)->child;
851         /* remove from first node (scene) adj list if present */
852         while (mainchild) {
853                 if (mainchild->node == fob) {
854                         if (prev) {
855                                 prev->next = mainchild->next;
856                                 MEM_freeN(mainchild);
857                                 break;
858                         } else {
859                                 ((DagNode *) forest->DagNode.first)->child = mainchild->next;
860                                 MEM_freeN(mainchild);
861                                 break;
862                         }
863                 }
864                 prev = mainchild;
865                 mainchild = mainchild->next;
866         }
867         node = dag_find_node (forest, fob);     
868         if (!node) 
869                 node = dag_add_node(forest, fob);
870         return node;
871 }
872
873 static void dag_add_parent_relation(DagForest *UNUSED(forest), DagNode *fob1, DagNode *fob2, short rel, const char *name) 
874 {
875         DagAdjList *itA = fob2->parent;
876         
877         while (itA) { /* search if relation exist already */
878                 if (itA->node == fob1) {
879                         itA->type |= rel;
880                         itA->count += 1;
881                         return;
882                 }
883                 itA = itA->next;
884         }
885         /* create new relation and insert at head. MALLOC alert! */
886         itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list");
887         itA->node = fob1;
888         itA->type = rel;
889         itA->count = 1;
890         itA->next = fob2->parent;
891         itA->name = name;
892         fob2->parent = itA;
893 }
894
895 void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, short rel, const char *name) 
896 {
897         DagAdjList *itA = fob1->child;
898         
899         /* parent relation is for cycle checking */
900         dag_add_parent_relation(forest, fob1, fob2, rel, name);
901
902         while (itA) { /* search if relation exist already */
903                 if (itA->node == fob2) {
904                         itA->type |= rel;
905                         itA->count += 1;
906                         return;
907                 }
908                 itA = itA->next;
909         }
910         /* create new relation and insert at head. MALLOC alert! */
911         itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list");
912         itA->node = fob2;
913         itA->type = rel;
914         itA->count = 1;
915         itA->next = fob1->child;
916         itA->name = name;
917         fob1->child = itA;
918 }
919
920 static const char *dag_node_name(DagNode *node)
921 {
922         if(node->ob == NULL)
923                 return "null";
924         else if(ugly_hack_sorry)
925                 return ((ID*)(node->ob))->name+2;
926         else
927                 return ((bPoseChannel*)(node->ob))->name;
928 }
929
930 #if 0
931 static void dag_node_print_dependencies(DagNode *node)
932 {
933         DagAdjList *itA;
934
935         printf("%s depends on:\n", dag_node_name(node));
936
937         for(itA= node->parent; itA; itA= itA->next)
938                 printf("  %s through %s\n", dag_node_name(itA->node), itA->name);
939         printf("\n");
940 }
941 #endif
942
943 static int dag_node_print_dependency_recurs(DagNode *node, DagNode *endnode)
944 {
945         DagAdjList *itA;
946
947         if(node->color == DAG_BLACK)
948                 return 0;
949
950         node->color= DAG_BLACK;
951
952         if(node == endnode)
953                 return 1;
954
955         for(itA= node->parent; itA; itA= itA->next) {
956                 if(dag_node_print_dependency_recurs(itA->node, endnode)) {
957                         printf("  %s depends on %s through %s.\n", dag_node_name(node), dag_node_name(itA->node), itA->name);
958                         return 1;
959                 }
960         }
961
962         return 0;
963 }
964
965 static void dag_node_print_dependency_cycle(DagForest *dag, DagNode *startnode, DagNode *endnode, const char *name)
966 {
967         DagNode *node;
968
969         for(node = dag->DagNode.first; node; node= node->next)
970                 node->color= DAG_WHITE;
971
972         printf("  %s depends on %s through %s.\n", dag_node_name(endnode), dag_node_name(startnode), name);
973         dag_node_print_dependency_recurs(startnode, endnode);
974         printf("\n");
975 }
976
977 static int dag_node_recurs_level(DagNode *node, int level)
978 {
979         DagAdjList *itA;
980         int newlevel;
981
982         node->color= DAG_BLACK; /* done */
983         newlevel= ++level;
984         
985         for(itA= node->parent; itA; itA= itA->next) {
986                 if(itA->node->color==DAG_WHITE) {
987                         itA->node->ancestor_count= dag_node_recurs_level(itA->node, level);
988                         newlevel= MAX2(newlevel, level+itA->node->ancestor_count);
989                 }
990                 else
991                         newlevel= MAX2(newlevel, level+itA->node->ancestor_count);
992         }
993         
994         return newlevel;
995 }
996
997 static void dag_check_cycle(DagForest *dag)
998 {
999         DagNode *node;
1000         DagAdjList *itA;
1001
1002         /* tag nodes unchecked */
1003         for(node = dag->DagNode.first; node; node= node->next)
1004                 node->color= DAG_WHITE;
1005         
1006         for(node = dag->DagNode.first; node; node= node->next) {
1007                 if(node->color==DAG_WHITE) {
1008                         node->ancestor_count= dag_node_recurs_level(node, 0);
1009                 }
1010         }
1011         
1012         /* check relations, and print errors */
1013         for(node = dag->DagNode.first; node; node= node->next) {
1014                 for(itA= node->parent; itA; itA= itA->next) {
1015                         if(itA->node->ancestor_count > node->ancestor_count) {
1016                                 if(node->ob && itA->node->ob) {
1017                                         printf("Dependency cycle detected:\n");
1018                                         dag_node_print_dependency_cycle(dag, itA->node, node, itA->name);
1019                                 }
1020                         }
1021                 }
1022         }
1023
1024         /* parent relations are only needed for cycle checking, so free now */
1025         for(node = dag->DagNode.first; node; node= node->next) {
1026                 while (node->parent) {
1027                         itA = node->parent->next;
1028                         MEM_freeN(node->parent);                        
1029                         node->parent = itA;
1030                 }
1031         }
1032 }
1033
1034 /*
1035  * MainDAG is the DAG of all objects in current scene
1036  * used only for drawing there is one also in each scene
1037  */
1038 static DagForest * MainDag = NULL;
1039
1040 DagForest *getMainDag(void)
1041 {
1042         return MainDag;
1043 }
1044
1045
1046 void setMainDag(DagForest *dag)
1047 {
1048         MainDag = dag;
1049 }
1050
1051
1052 /*
1053  * note for BFS/DFS
1054  * in theory we should sweep the whole array
1055  * but in our case the first node is the scene
1056  * and is linked to every other object
1057  *
1058  * for general case we will need to add outer loop
1059  */
1060
1061 /*
1062  * ToDo : change pos kludge
1063  */
1064
1065 /* adjust levels for drawing in oops space */
1066 void graph_bfs(void)
1067 {
1068         DagNode *node;
1069         DagNodeQueue *nqueue;
1070         int pos[50];
1071         int i;
1072         DagAdjList *itA;
1073         int minheight;
1074         
1075         /* fprintf(stderr,"starting BFS \n ------------\n"); */ 
1076         nqueue = queue_create(DAGQUEUEALLOC);
1077         for ( i=0; i<50; i++)
1078                 pos[i] = 0;
1079         
1080         /* Init
1081          * dagnode.first is alway the root (scene) 
1082          */
1083         node = MainDag->DagNode.first;
1084         while(node) {
1085                 node->color = DAG_WHITE;
1086                 node->BFS_dist = 9999;
1087                 node->k = 0;
1088                 node = node->next;
1089         }
1090         
1091         node = MainDag->DagNode.first;
1092         if (node->color == DAG_WHITE) {
1093                 node->color = DAG_GRAY;
1094                 node->BFS_dist = 1;
1095                 push_queue(nqueue,node);  
1096                 while(nqueue->count) {
1097                         node = pop_queue(nqueue);
1098                         
1099                         minheight = pos[node->BFS_dist];
1100                         itA = node->child;
1101                         while(itA != NULL) {
1102                                 if(itA->node->color == DAG_WHITE) {
1103                                         itA->node->color = DAG_GRAY;
1104                                         itA->node->BFS_dist = node->BFS_dist + 1;
1105                                         itA->node->k = (float) minheight;
1106                                         push_queue(nqueue,itA->node);
1107                                 }
1108                                 
1109                                 else {
1110                                         fprintf(stderr,"bfs not dag tree edge color :%i \n",itA->node->color);
1111                                 }
1112
1113                                 
1114                                 itA = itA->next;
1115                         }
1116                         if (pos[node->BFS_dist] > node->k ) {
1117                                 pos[node->BFS_dist] += 1;                               
1118                                 node->k = (float) pos[node->BFS_dist];
1119                         } else {
1120                                 pos[node->BFS_dist] = (int) node->k +1;
1121                         }
1122                         set_node_xy(node, node->BFS_dist*DEPSX*2, pos[node->BFS_dist]*DEPSY*2);
1123                         node->color = DAG_BLACK;
1124                         /*
1125                          fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);   
1126                          */
1127                 }
1128         }
1129         queue_delete(nqueue);
1130 }
1131
1132 int pre_and_post_BFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
1133         DagNode *node;
1134         
1135         node = dag->DagNode.first;
1136         return pre_and_post_source_BFS(dag, mask,  node,  pre_func,  post_func, data);
1137 }
1138
1139
1140 int pre_and_post_source_BFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
1141 {
1142         DagNode *node;
1143         DagNodeQueue *nqueue;
1144         DagAdjList *itA;
1145         int     retval = 0;
1146         /* fprintf(stderr,"starting BFS \n ------------\n"); */ 
1147         
1148         /* Init
1149                 * dagnode.first is alway the root (scene) 
1150                 */
1151         node = dag->DagNode.first;
1152         nqueue = queue_create(DAGQUEUEALLOC);
1153         while(node) {
1154                 node->color = DAG_WHITE;
1155                 node->BFS_dist = 9999;
1156                 node = node->next;
1157         }
1158         
1159         node = source;
1160         if (node->color == DAG_WHITE) {
1161                 node->color = DAG_GRAY;
1162                 node->BFS_dist = 1;
1163                 pre_func(node->ob,data);
1164                 
1165                 while(nqueue->count) {
1166                         node = pop_queue(nqueue);
1167                         
1168                         itA = node->child;
1169                         while(itA != NULL) {
1170                                 if((itA->node->color == DAG_WHITE) && (itA->type & mask)) {
1171                                         itA->node->color = DAG_GRAY;
1172                                         itA->node->BFS_dist = node->BFS_dist + 1;
1173                                         push_queue(nqueue,itA->node);
1174                                         pre_func(node->ob,data);
1175                                 }
1176                                 
1177                                 else { // back or cross edge
1178                                         retval = 1;
1179                                 }
1180                                 itA = itA->next;
1181                         }
1182                         post_func(node->ob,data);
1183                         node->color = DAG_BLACK;
1184                         /*
1185                          fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);   
1186                          */
1187                 }
1188         }
1189         queue_delete(nqueue);
1190         return retval;
1191 }
1192
1193 /* non recursive version of DFS, return queue -- outer loop present to catch odd cases (first level cycles)*/
1194 DagNodeQueue * graph_dfs(void)
1195 {
1196         DagNode *node;
1197         DagNodeQueue *nqueue;
1198         DagNodeQueue *retqueue;
1199         int pos[50];
1200         int i;
1201         DagAdjList *itA;
1202         int time;
1203         int skip = 0;
1204         int minheight;
1205         int maxpos=0;
1206         /* int  is_cycle = 0; */ /* UNUSED */
1207         /*
1208          *fprintf(stderr,"starting DFS \n ------------\n");
1209          */     
1210         nqueue = queue_create(DAGQUEUEALLOC);
1211         retqueue = queue_create(MainDag->numNodes);
1212         for ( i=0; i<50; i++)
1213                 pos[i] = 0;
1214         
1215         /* Init
1216          * dagnode.first is alway the root (scene) 
1217          */
1218         node = MainDag->DagNode.first;
1219         while(node) {
1220                 node->color = DAG_WHITE;
1221                 node->DFS_dist = 9999;
1222                 node->DFS_dvtm = node->DFS_fntm = 9999;
1223                 node->k = 0;
1224                 node =  node->next;
1225         }
1226         
1227         time = 1;
1228         
1229         node = MainDag->DagNode.first;
1230
1231         do {
1232         if (node->color == DAG_WHITE) {
1233                 node->color = DAG_GRAY;
1234                 node->DFS_dist = 1;
1235                 node->DFS_dvtm = time;
1236                 time++;
1237                 push_stack(nqueue,node);  
1238                         
1239                 while(nqueue->count) {
1240                         //graph_print_queue(nqueue);
1241
1242                         skip = 0;
1243                         node = get_top_node_queue(nqueue);
1244                         
1245                         minheight = pos[node->DFS_dist];
1246
1247                         itA = node->child;
1248                         while(itA != NULL) {
1249                                 if(itA->node->color == DAG_WHITE) {
1250                                         itA->node->DFS_dvtm = time;
1251                                         itA->node->color = DAG_GRAY;
1252
1253                                         time++;
1254                                         itA->node->DFS_dist = node->DFS_dist + 1;
1255                                         itA->node->k = (float) minheight;
1256                                         push_stack(nqueue,itA->node);
1257                                         skip = 1;
1258                                         break;
1259                                 } else { 
1260                                         if (itA->node->color == DAG_GRAY) { // back edge
1261                                                 fprintf(stderr,"dfs back edge :%15s %15s \n",((ID *) node->ob)->name, ((ID *) itA->node->ob)->name);
1262                                                 /* is_cycle = 1; */ /* UNUSED */
1263                                         } else if (itA->node->color == DAG_BLACK) {
1264                                                 ;
1265                                                 /* already processed node but we may want later to change distance either to shorter to longer.
1266                                                  * DFS_dist is the first encounter  
1267                                                 */
1268                                                 /*if (node->DFS_dist >= itA->node->DFS_dist)
1269                                                         itA->node->DFS_dist = node->DFS_dist + 1;
1270
1271                                                         fprintf(stderr,"dfs forward or cross edge :%15s %i-%i %15s %i-%i \n",
1272                                                                 ((ID *) node->ob)->name,
1273                                                                 node->DFS_dvtm, 
1274                                                                 node->DFS_fntm, 
1275                                                                 ((ID *) itA->node->ob)->name, 
1276                                                                 itA->node->DFS_dvtm,
1277                                                                 itA->node->DFS_fntm);
1278                                         */
1279                                         } else 
1280                                                 fprintf(stderr,"dfs unknown edge \n");
1281                                 }
1282                                 itA = itA->next;
1283                         }                       
1284
1285                         if (!skip) {
1286                                 node = pop_queue(nqueue);
1287                                 node->color = DAG_BLACK;
1288
1289                                 node->DFS_fntm = time;
1290                                 time++;
1291                                 if (node->DFS_dist > maxpos)
1292                                         maxpos = node->DFS_dist;
1293                                 if (pos[node->DFS_dist] > node->k ) {
1294                                         pos[node->DFS_dist] += 1;                               
1295                                         node->k = (float) pos[node->DFS_dist];
1296                                 } else {
1297                                         pos[node->DFS_dist] = (int) node->k +1;
1298                                 }
1299                                 set_node_xy(node, node->DFS_dist*DEPSX*2, pos[node->DFS_dist]*DEPSY*2);
1300                                 
1301                                 /*
1302                                  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 );       
1303                                 */
1304                                 push_stack(retqueue,node);
1305                                 
1306                         }
1307                 }
1308         }
1309                 node = node->next;
1310         } while (node);
1311 //      fprintf(stderr,"i size : %i \n", maxpos);
1312
1313         queue_delete(nqueue);
1314         return(retqueue);
1315 }
1316
1317 /* unused */
1318 int pre_and_post_DFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
1319         DagNode *node;
1320
1321         node = dag->DagNode.first;
1322         return pre_and_post_source_DFS(dag, mask,  node,  pre_func,  post_func, data);
1323 }
1324
1325 int pre_and_post_source_DFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
1326 {
1327         DagNode *node;
1328         DagNodeQueue *nqueue;
1329         DagAdjList *itA;
1330         int time;
1331         int skip = 0;
1332         int retval = 0;
1333         /*
1334          *fprintf(stderr,"starting DFS \n ------------\n");
1335          */     
1336         nqueue = queue_create(DAGQUEUEALLOC);
1337         
1338         /* Init
1339                 * dagnode.first is alway the root (scene) 
1340                 */
1341         node = dag->DagNode.first;
1342         while(node) {
1343                 node->color = DAG_WHITE;
1344                 node->DFS_dist = 9999;
1345                 node->DFS_dvtm = node->DFS_fntm = 9999;
1346                 node->k = 0;
1347                 node =  node->next;
1348         }
1349         
1350         time = 1;
1351         
1352         node = source;
1353         do {
1354                 if (node->color == DAG_WHITE) {
1355                         node->color = DAG_GRAY;
1356                         node->DFS_dist = 1;
1357                         node->DFS_dvtm = time;
1358                         time++;
1359                         push_stack(nqueue,node);  
1360                         pre_func(node->ob,data);
1361
1362                         while(nqueue->count) {
1363                                 skip = 0;
1364                                 node = get_top_node_queue(nqueue);
1365                                                                 
1366                                 itA = node->child;
1367                                 while(itA != NULL) {
1368                                         if((itA->node->color == DAG_WHITE) && (itA->type & mask) ) {
1369                                                 itA->node->DFS_dvtm = time;
1370                                                 itA->node->color = DAG_GRAY;
1371                                                 
1372                                                 time++;
1373                                                 itA->node->DFS_dist = node->DFS_dist + 1;
1374                                                 push_stack(nqueue,itA->node);
1375                                                 pre_func(node->ob,data);
1376
1377                                                 skip = 1;
1378                                                 break;
1379                                         } else {
1380                                                 if (itA->node->color == DAG_GRAY) {// back edge
1381                                                         retval = 1;
1382                                                 }
1383 //                                              else if (itA->node->color == DAG_BLACK) { // cross or forward
1384 //                                                      ;
1385                                         }
1386                                         itA = itA->next;
1387                                 }                       
1388                                 
1389                                 if (!skip) {
1390                                         node = pop_queue(nqueue);
1391                                         node->color = DAG_BLACK;
1392                                         
1393                                         node->DFS_fntm = time;
1394                                         time++;
1395                                         post_func(node->ob,data);
1396                                 }
1397                         }
1398                 }
1399                 node = node->next;
1400         } while (node);
1401         queue_delete(nqueue);
1402         return(retval);
1403 }
1404
1405
1406 // used to get the obs owning a datablock
1407 struct DagNodeQueue *get_obparents(struct DagForest     *dag, void *ob) 
1408 {
1409         DagNode * node, *node1;
1410         DagNodeQueue *nqueue;
1411         DagAdjList *itA;
1412
1413         node = dag_find_node(dag,ob);
1414         if(node==NULL) {
1415                 return NULL;
1416         }
1417         else if (node->ancestor_count == 1) { // simple case
1418                 nqueue = queue_create(1);
1419                 push_queue(nqueue,node);
1420         } else {        // need to go over the whole dag for adj list
1421                 nqueue = queue_create(node->ancestor_count);
1422                 
1423                 node1 = dag->DagNode.first;
1424                 do {
1425                         if (node1->DFS_fntm > node->DFS_fntm) { // a parent is finished after child. must check adj list
1426                                 itA = node->child;
1427                                 while(itA != NULL) {
1428                                         if ((itA->node == node) && (itA->type == DAG_RL_DATA)) {
1429                                                 push_queue(nqueue,node);
1430                                         }
1431                                         itA = itA->next;
1432                                 }
1433                         }
1434                         node1 = node1->next;
1435                 } while (node1);
1436         }
1437         return nqueue;
1438 }
1439
1440 struct DagNodeQueue *get_first_ancestors(struct DagForest       *dag, void *ob)
1441 {
1442         DagNode * node, *node1;
1443         DagNodeQueue *nqueue;
1444         DagAdjList *itA;
1445         
1446         node = dag_find_node(dag,ob);
1447         
1448         // need to go over the whole dag for adj list
1449         nqueue = queue_create(node->ancestor_count);
1450         
1451         node1 = dag->DagNode.first;
1452         do {
1453                 if (node1->DFS_fntm > node->DFS_fntm) { 
1454                         itA = node->child;
1455                         while(itA != NULL) {
1456                                 if (itA->node == node) {
1457                                         push_queue(nqueue,node);
1458                                 }
1459                                 itA = itA->next;
1460                         }
1461                 }
1462                 node1 = node1->next;
1463         } while (node1);
1464         
1465         return nqueue;  
1466 }
1467
1468 // standard DFS list
1469 struct DagNodeQueue *get_all_childs(struct DagForest    *dag, void *ob)
1470 {
1471         DagNode *node;
1472         DagNodeQueue *nqueue;
1473         DagNodeQueue *retqueue;
1474         DagAdjList *itA;
1475         int time;
1476         int skip = 0;
1477
1478         nqueue = queue_create(DAGQUEUEALLOC);
1479         retqueue = queue_create(dag->numNodes); // was MainDag... why? (ton)
1480         
1481         node = dag->DagNode.first;
1482         while(node) {
1483                 node->color = DAG_WHITE;
1484                 node =  node->next;
1485         }
1486         
1487         time = 1;
1488         
1489         node = dag_find_node(dag, ob);   // could be done in loop above (ton)
1490         if(node) { // can be null for newly added objects
1491                 
1492                 node->color = DAG_GRAY;
1493                 time++;
1494                 push_stack(nqueue,node);  
1495                 
1496                 while(nqueue->count) {
1497                         
1498                         skip = 0;
1499                         node = get_top_node_queue(nqueue);
1500                                         
1501                         itA = node->child;
1502                         while(itA != NULL) {
1503                                 if(itA->node->color == DAG_WHITE) {
1504                                         itA->node->DFS_dvtm = time;
1505                                         itA->node->color = DAG_GRAY;
1506                                         
1507                                         time++;
1508                                         push_stack(nqueue,itA->node);
1509                                         skip = 1;
1510                                         break;
1511                                 } 
1512                                 itA = itA->next;
1513                         }                       
1514                         
1515                         if (!skip) {
1516                                 node = pop_queue(nqueue);
1517                                 node->color = DAG_BLACK;
1518                                 
1519                                 time++;
1520                                 push_stack(retqueue,node);                      
1521                         }
1522                 }
1523         }
1524         queue_delete(nqueue);
1525         return(retqueue);
1526 }
1527
1528 /* unused */
1529 short   are_obs_related(struct DagForest        *dag, void *ob1, void *ob2) {
1530         DagNode * node;
1531         DagAdjList *itA;
1532         
1533         node = dag_find_node(dag, ob1);
1534         
1535         itA = node->child;
1536         while(itA != NULL) {
1537                 if(itA->node->ob == ob2) {
1538                         return itA->node->type;
1539                 } 
1540                 itA = itA->next;
1541         }
1542         return DAG_NO_RELATION;
1543 }
1544
1545 int     is_acyclic( DagForest   *dag) {
1546         return dag->is_acyclic;
1547 }
1548
1549 void set_node_xy(DagNode *node, float x, float y)
1550 {
1551          node->x = x;
1552         node->y = y;
1553 }
1554
1555
1556 /* debug test functions */
1557
1558 void graph_print_queue(DagNodeQueue *nqueue)
1559 {       
1560         DagNodeQueueElem *queueElem;
1561         
1562         queueElem = nqueue->first;
1563         while(queueElem) {
1564                 fprintf(stderr,"** %s %i %i-%i ",((ID *) queueElem->node->ob)->name,queueElem->node->color,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
1565                 queueElem = queueElem->next;            
1566         }
1567         fprintf(stderr,"\n");
1568 }
1569
1570 void graph_print_queue_dist(DagNodeQueue *nqueue)
1571 {       
1572         DagNodeQueueElem *queueElem;
1573         int count;
1574         
1575         queueElem = nqueue->first;
1576         count = 0;
1577         while(queueElem) {
1578                 fprintf(stderr,"** %25s %2.2i-%2.2i ",((ID *) queueElem->node->ob)->name,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
1579                 while (count < queueElem->node->DFS_dvtm-1) { fputc(' ',stderr); count++;}
1580                 fputc('|',stderr); 
1581                 while (count < queueElem->node->DFS_fntm-2) { fputc('-',stderr); count++;}
1582                 fputc('|',stderr);
1583                 fputc('\n',stderr);
1584                 count = 0;
1585                 queueElem = queueElem->next;            
1586         }
1587         fprintf(stderr,"\n");
1588 }
1589
1590 void graph_print_adj_list(void)
1591 {
1592         DagNode *node;
1593         DagAdjList *itA;
1594         
1595         node = (getMainDag())->DagNode.first;
1596         while(node) {
1597                 fprintf(stderr,"node : %s col: %i",((ID *) node->ob)->name, node->color);               
1598                 itA = node->child;
1599                 while (itA) {
1600                         fprintf(stderr,"-- %s ",((ID *) itA->node->ob)->name);
1601                         
1602                         itA = itA->next;
1603                 }
1604                 fprintf(stderr,"\n");
1605                 node = node->next;
1606         }
1607 }
1608
1609 /* ************************ API *********************** */
1610
1611 /* mechanism to allow editors to be informed of depsgraph updates,
1612    to do their own updates based on changes... */
1613 static void (*EditorsUpdateCb)(Main *bmain, ID *id)= NULL;
1614
1615 void DAG_editors_update_cb(void (*func)(Main *bmain, ID *id))
1616 {
1617         EditorsUpdateCb= func;
1618 }
1619
1620 static void dag_editors_update(Main *bmain, ID *id)
1621 {
1622         if(EditorsUpdateCb)
1623                 EditorsUpdateCb(bmain, id);
1624 }
1625
1626 /* groups with objects in this scene need to be put in the right order as well */
1627 static void scene_sort_groups(Main *bmain, Scene *sce)
1628 {
1629         Base *base;
1630         Group *group;
1631         GroupObject *go;
1632         Object *ob;
1633         
1634         /* test; are group objects all in this scene? */
1635         for(ob= bmain->object.first; ob; ob= ob->id.next) {
1636                 ob->id.flag &= ~LIB_DOIT;
1637                 ob->id.newid= NULL;     /* newid abuse for GroupObject */
1638         }
1639         for(base = sce->base.first; base; base= base->next)
1640                 base->object->id.flag |= LIB_DOIT;
1641         
1642         for(group= bmain->group.first; group; group= group->id.next) {
1643                 for(go= group->gobject.first; go; go= go->next) {
1644                         if((go->ob->id.flag & LIB_DOIT)==0)
1645                                 break;
1646                 }
1647                 /* this group is entirely in this scene */
1648                 if(go==NULL) {
1649                         ListBase listb= {NULL, NULL};
1650                         
1651                         for(go= group->gobject.first; go; go= go->next)
1652                                 go->ob->id.newid= (ID *)go;
1653                         
1654                         /* in order of sorted bases we reinsert group objects */
1655                         for(base = sce->base.first; base; base= base->next) {
1656                                 
1657                                 if(base->object->id.newid) {
1658                                         go= (GroupObject *)base->object->id.newid;
1659                                         base->object->id.newid= NULL;
1660                                         BLI_remlink( &group->gobject, go);
1661                                         BLI_addtail( &listb, go);
1662                                 }
1663                         }
1664                         /* copy the newly sorted listbase */
1665                         group->gobject= listb;
1666                 }
1667         }
1668 }
1669
1670 /* sort the base list on dependency order */
1671 void DAG_scene_sort(Main *bmain, Scene *sce)
1672 {
1673         DagNode *node;
1674         DagNodeQueue *nqueue;
1675         DagAdjList *itA;
1676         int time;
1677         int skip = 0;
1678         ListBase tempbase;
1679         Base *base;
1680         
1681         tempbase.first= tempbase.last= NULL;
1682         
1683         build_dag(bmain, sce, DAG_RL_ALL_BUT_DATA);
1684         
1685         dag_check_cycle(sce->theDag);
1686
1687         nqueue = queue_create(DAGQUEUEALLOC);
1688         
1689         for(node = sce->theDag->DagNode.first; node; node= node->next) {
1690                 node->color = DAG_WHITE;
1691         }
1692         
1693         time = 1;
1694         
1695         node = sce->theDag->DagNode.first;
1696         
1697         node->color = DAG_GRAY;
1698         time++;
1699         push_stack(nqueue,node);  
1700         
1701         while(nqueue->count) {
1702                 
1703                 skip = 0;
1704                 node = get_top_node_queue(nqueue);
1705                 
1706                 itA = node->child;
1707                 while(itA != NULL) {
1708                         if(itA->node->color == DAG_WHITE) {
1709                                 itA->node->DFS_dvtm = time;
1710                                 itA->node->color = DAG_GRAY;
1711                                 
1712                                 time++;
1713                                 push_stack(nqueue,itA->node);
1714                                 skip = 1;
1715                                 break;
1716                         } 
1717                         itA = itA->next;
1718                 }                       
1719                 
1720                 if (!skip) {
1721                         if (node) {
1722                                 node = pop_queue(nqueue);
1723                                 if (node->ob == sce)    // we are done
1724                                         break ;
1725                                 node->color = DAG_BLACK;
1726                                 
1727                                 time++;
1728                                 base = sce->base.first;
1729                                 while (base && base->object != node->ob)
1730                                         base = base->next;
1731                                 if(base) {
1732                                         BLI_remlink(&sce->base,base);
1733                                         BLI_addhead(&tempbase,base);
1734                                 }
1735                         }       
1736                 }
1737         }
1738         
1739         // temporal correction for circular dependancies
1740         base = sce->base.first;
1741         while (base) {
1742                 BLI_remlink(&sce->base,base);
1743                 BLI_addhead(&tempbase,base);
1744                 //if(G.f & G_DEBUG) 
1745                         printf("cyclic %s\n", base->object->id.name);
1746                 base = sce->base.first;
1747         }
1748         
1749         sce->base = tempbase;
1750         queue_delete(nqueue);
1751         
1752         /* all groups with objects in this scene gets resorted too */
1753         scene_sort_groups(bmain, sce);
1754         
1755         if(G.f & G_DEBUG) {
1756                 printf("\nordered\n");
1757                 for(base = sce->base.first; base; base= base->next) {
1758                         printf(" %s\n", base->object->id.name);
1759                 }
1760         }
1761         /* temporal...? */
1762         sce->recalc |= SCE_PRV_CHANGED; /* test for 3d preview */
1763 }
1764
1765 static void lib_id_recalc_tag(Main *bmain, ID *id)
1766 {
1767         id->flag |= LIB_ID_RECALC;
1768         bmain->id_tag_update[id->name[0]] = 1;
1769 }
1770
1771 static void lib_id_recalc_data_tag(Main *bmain, ID *id)
1772 {
1773         id->flag |= LIB_ID_RECALC_DATA;
1774         bmain->id_tag_update[id->name[0]] = 1;
1775 }
1776
1777 /* node was checked to have lasttime != curtime and is if type ID_OB */
1778 static void flush_update_node(DagNode *node, unsigned int layer, int curtime)
1779 {
1780         Main *bmain= G.main;
1781         DagAdjList *itA;
1782         Object *ob, *obc;
1783         int oldflag, changed=0;
1784         unsigned int all_layer;
1785         
1786         node->lasttime= curtime;
1787         
1788         ob= node->ob;
1789         if(ob && (ob->recalc & OB_RECALC_ALL)) {
1790                 all_layer= node->scelay;
1791
1792                 /* got an object node that changes, now check relations */
1793                 for(itA = node->child; itA; itA= itA->next) {
1794                         all_layer |= itA->lay;
1795                         /* the relationship is visible */
1796                         if((itA->lay & layer)) { // XXX || (itA->node->ob == obedit)
1797                                 if(itA->node->type==ID_OB) {
1798                                         obc= itA->node->ob;
1799                                         oldflag= obc->recalc;
1800                                         
1801                                         /* got a ob->obc relation, now check if flag needs flush */
1802                                         if(ob->recalc & OB_RECALC_OB) {
1803                                                 if(itA->type & DAG_RL_OB_OB) {
1804                                                         //printf("ob %s changes ob %s\n", ob->id.name, obc->id.name);
1805                                                         obc->recalc |= OB_RECALC_OB;
1806                                                         lib_id_recalc_tag(bmain, &obc->id);
1807                                                 }
1808                                                 if(itA->type & DAG_RL_OB_DATA) {
1809                                                         //printf("ob %s changes obdata %s\n", ob->id.name, obc->id.name);
1810                                                         obc->recalc |= OB_RECALC_DATA;
1811                                                         lib_id_recalc_data_tag(bmain, &obc->id);
1812                                                 }
1813                                         }
1814                                         if(ob->recalc & OB_RECALC_DATA) {
1815                                                 if(itA->type & DAG_RL_DATA_OB) {
1816                                                         //printf("obdata %s changes ob %s\n", ob->id.name, obc->id.name);
1817                                                         obc->recalc |= OB_RECALC_OB;
1818                                                         lib_id_recalc_tag(bmain, &obc->id);
1819                                                 }
1820                                                 if(itA->type & DAG_RL_DATA_DATA) {
1821                                                         //printf("obdata %s changes obdata %s\n", ob->id.name, obc->id.name);
1822                                                         obc->recalc |= OB_RECALC_DATA;
1823                                                         lib_id_recalc_data_tag(bmain, &obc->id);
1824                                                 }
1825                                         }
1826                                         if(oldflag!=obc->recalc) changed= 1;
1827                                 }
1828                         }
1829                 }
1830                 /* even nicer, we can clear recalc flags...  */
1831                 if((all_layer & layer)==0) { // XXX && (ob != obedit)) {
1832                         /* but existing displaylists or derivedmesh should be freed */
1833                         if(ob->recalc & OB_RECALC_DATA)
1834                                 object_free_display(ob);
1835                         
1836                         ob->recalc &= ~OB_RECALC_ALL;
1837                 }
1838         }
1839         
1840         /* check case where child changes and parent forcing obdata to change */
1841         /* should be done regardless if this ob has recalc set */
1842         /* could merge this in with loop above...? (ton) */
1843         for(itA = node->child; itA; itA= itA->next) {
1844                 /* the relationship is visible */
1845                 if((itA->lay & layer)) {                // XXX  || (itA->node->ob == obedit)
1846                         if(itA->node->type==ID_OB) {
1847                                 obc= itA->node->ob;
1848                                 /* child moves */
1849                                 if((obc->recalc & OB_RECALC_ALL)==OB_RECALC_OB) {
1850                                         /* parent has deforming info */
1851                                         if(itA->type & (DAG_RL_OB_DATA|DAG_RL_DATA_DATA)) {
1852                                                 // printf("parent %s changes ob %s\n", ob->id.name, obc->id.name);
1853                                                 obc->recalc |= OB_RECALC_DATA;
1854                                                 lib_id_recalc_data_tag(bmain, &obc->id);
1855                                         }
1856                                 }
1857                         }
1858                 }
1859         }
1860         
1861         /* we only go deeper if node not checked or something changed  */
1862         for(itA = node->child; itA; itA= itA->next) {
1863                 if(changed || itA->node->lasttime!=curtime) 
1864                         flush_update_node(itA->node, layer, curtime);
1865         }
1866         
1867 }
1868
1869 /* node was checked to have lasttime != curtime , and is of type ID_OB */
1870 static unsigned int flush_layer_node(Scene *sce, DagNode *node, int curtime)
1871 {
1872         DagAdjList *itA;
1873         
1874         node->lasttime= curtime;
1875         node->lay= node->scelay;
1876         
1877         for(itA = node->child; itA; itA= itA->next) {
1878                 if(itA->node->type==ID_OB) {
1879                         if(itA->node->lasttime!=curtime) {
1880                                 itA->lay= flush_layer_node(sce, itA->node, curtime);  // lay is only set once for each relation
1881                         }
1882                         else itA->lay= itA->node->lay;
1883                         
1884                         node->lay |= itA->lay;
1885                 }
1886         }
1887
1888         return node->lay;
1889 }
1890
1891 /* node was checked to have lasttime != curtime , and is of type ID_OB */
1892 static void flush_pointcache_reset(Scene *scene, DagNode *node, int curtime, int reset)
1893 {
1894         Main *bmain= G.main;
1895         DagAdjList *itA;
1896         Object *ob;
1897         
1898         node->lasttime= curtime;
1899         
1900         for(itA = node->child; itA; itA= itA->next) {
1901                 if(itA->node->type==ID_OB) {
1902                         if(itA->node->lasttime!=curtime) {
1903                                 ob= (Object*)(itA->node->ob);
1904
1905                                 if(reset || (ob->recalc & OB_RECALC_ALL)) {
1906                                         if(BKE_ptcache_object_reset(scene, ob, PTCACHE_RESET_DEPSGRAPH)) {
1907                                                 ob->recalc |= OB_RECALC_DATA;
1908                                                 lib_id_recalc_data_tag(bmain, &ob->id);
1909                                         }
1910
1911                                         flush_pointcache_reset(scene, itA->node, curtime, 1);
1912                                 }
1913                                 else
1914                                         flush_pointcache_reset(scene, itA->node, curtime, 0);
1915                         }
1916                 }
1917         }
1918 }
1919
1920 /* flush layer flags to dependencies */
1921 static void dag_scene_flush_layers(Scene *sce, int lay)
1922 {
1923         DagNode *node, *firstnode;
1924         DagAdjList *itA;
1925         Base *base;
1926         int lasttime;
1927
1928         firstnode= sce->theDag->DagNode.first;  // always scene node
1929
1930         for(itA = firstnode->child; itA; itA= itA->next)
1931                 itA->lay= 0;
1932
1933         sce->theDag->time++;    // so we know which nodes were accessed
1934         lasttime= sce->theDag->time;
1935
1936         /* update layer flags in nodes */
1937         for(base= sce->base.first; base; base= base->next) {
1938                 node= dag_get_node(sce->theDag, base->object);
1939                 node->scelay= base->object->lay;
1940         }
1941
1942         /* ensure cameras are set as if they are on a visible layer, because
1943          * they ared still used for rendering or setting the camera view
1944          *
1945          * XXX, this wont work for local view / unlocked camera's */
1946         if(sce->camera) {
1947                 node= dag_get_node(sce->theDag, sce->camera);
1948                 node->scelay |= lay;
1949         }
1950
1951 #ifdef DURIAN_CAMERA_SWITCH
1952         {
1953                 TimeMarker *m;
1954
1955                 for(m= sce->markers.first; m; m= m->next) {
1956                         if(m->camera) {
1957                                 node= dag_get_node(sce->theDag, m->camera);
1958                                 node->scelay |= lay;
1959                         }
1960                 }
1961         }
1962 #endif
1963
1964         /* flush layer nodes to dependencies */
1965         for(itA = firstnode->child; itA; itA= itA->next)
1966                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) 
1967                         flush_layer_node(sce, itA->node, lasttime);
1968 }
1969
1970 static void dag_tag_renderlayers(Scene *sce, unsigned int lay)
1971 {
1972         if(sce->nodetree) {
1973                 bNode *node;
1974                 Base *base;
1975                 unsigned int lay_changed= 0;
1976                 
1977                 for(base= sce->base.first; base; base= base->next)
1978                         if(base->lay & lay)
1979                                 if(base->object->recalc)
1980                                         lay_changed |= base->lay;
1981                         
1982                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
1983                         if(node->id==(ID *)sce) {
1984                                 SceneRenderLayer *srl= BLI_findlink(&sce->r.layers, node->custom1);
1985                                 if(srl && (srl->lay & lay_changed))
1986                                         NodeTagChanged(sce->nodetree, node);
1987                         }
1988                 }
1989         }
1990 }
1991
1992 /* flushes all recalc flags in objects down the dependency tree */
1993 void DAG_scene_flush_update(Main *bmain, Scene *sce, unsigned int lay, const short time)
1994 {
1995         DagNode *firstnode;
1996         DagAdjList *itA;
1997         Object *ob;
1998         int lasttime;
1999         
2000         if(sce->theDag==NULL) {
2001                 printf("DAG zero... not allowed to happen!\n");
2002                 DAG_scene_sort(bmain, sce);
2003         }
2004         
2005         firstnode= sce->theDag->DagNode.first;  // always scene node
2006
2007         /* first we flush the layer flags */
2008         dag_scene_flush_layers(sce, lay);
2009
2010         /* then we use the relationships + layer info to flush update events */
2011         sce->theDag->time++;    // so we know which nodes were accessed
2012         lasttime= sce->theDag->time;
2013         for(itA = firstnode->child; itA; itA= itA->next)
2014                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)
2015                         flush_update_node(itA->node, lay, lasttime);
2016
2017         /* if update is not due to time change, do pointcache clears */
2018         if(!time) {
2019                 sce->theDag->time++;    // so we know which nodes were accessed
2020                 lasttime= sce->theDag->time;
2021                 for(itA = firstnode->child; itA; itA= itA->next) {
2022                         if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)  {
2023                                 ob= (Object*)(itA->node->ob);
2024
2025                                 if(ob->recalc & OB_RECALC_ALL) {
2026                                         if(BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH)) {
2027                                                 ob->recalc |= OB_RECALC_DATA;
2028                                                 lib_id_recalc_data_tag(bmain, &ob->id);
2029                                         }
2030
2031                                         flush_pointcache_reset(sce, itA->node, lasttime, 1);
2032                                 }
2033                                 else
2034                                         flush_pointcache_reset(sce, itA->node, lasttime, 0);
2035                         }
2036                 }
2037         }
2038         
2039         dag_tag_renderlayers(sce, lay);
2040 }
2041
2042 static int object_modifiers_use_time(Object *ob)
2043 {
2044         ModifierData *md;
2045         
2046         /* check if a modifier in modifier stack needs time input */
2047         for (md=ob->modifiers.first; md; md=md->next)
2048                 if (modifier_dependsOnTime(md))
2049                         return 1;
2050         
2051         /* check whether any modifiers are animated */
2052         if (ob->adt) {
2053                 AnimData *adt = ob->adt;
2054                 
2055                 /* action - check for F-Curves with paths containing 'modifiers[' */
2056                 if (adt->action) {
2057                         FCurve *fcu;
2058                         
2059                         for (fcu = adt->action->curves.first; fcu; fcu = fcu->next) {
2060                                 if (fcu->rna_path && strstr(fcu->rna_path, "modifiers["))
2061                                         return 1;
2062                         }
2063                 }
2064                 
2065                 // XXX: also, should check NLA strips, though for now assume that nobody uses
2066                 // that and we can omit that for performance reasons...
2067         }
2068         
2069         return 0;
2070 }
2071
2072 static short animdata_use_time(AnimData *adt)
2073 {
2074         NlaTrack *nlt;
2075         
2076         if(adt==NULL) return 0;
2077         
2078         /* check action - only if assigned, and it has anim curves */
2079         if (adt->action && adt->action->curves.first)
2080                 return 1;
2081         
2082         /* check NLA tracks + strips */
2083         for (nlt= adt->nla_tracks.first; nlt; nlt= nlt->next) {
2084                 if (nlt->strips.first)
2085                         return 1;
2086         }
2087         
2088         /* If we have drivers, more likely than not, on a frame change
2089          * they'll need updating because their owner changed
2090          * 
2091          * This is kindof a hack to get around a whole host of problems
2092          * involving drivers using non-object datablock data (which the 
2093          * depsgraph currently has no way of representing let alone correctly
2094          * dependency sort+tagging). By doing this, at least we ensure that 
2095          * some commonly attempted drivers (such as scene -> current frame;
2096          * see "Driver updates fail" thread on Bf-committers dated July 2)
2097          * will work correctly, and that other non-object datablocks will have
2098          * their drivers update at least on frame change.
2099          *
2100          * -- Aligorith, July 4 2011
2101          */
2102         if (adt->drivers.first)
2103                 return 1;
2104         
2105         return 0;
2106 }
2107
2108 static void dag_object_time_update_flags(Object *ob)
2109 {
2110         if(ob->constraints.first) {
2111                 bConstraint *con;
2112                 for (con = ob->constraints.first; con; con=con->next) {
2113                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2114                         ListBase targets = {NULL, NULL};
2115                         bConstraintTarget *ct;
2116                         
2117                         if (cti && cti->get_constraint_targets) {
2118                                 cti->get_constraint_targets(con, &targets);
2119                                 
2120                                 for (ct= targets.first; ct; ct= ct->next) {
2121                                         if (ct->tar) {
2122                                                 ob->recalc |= OB_RECALC_OB;
2123                                                 break;
2124                                         }
2125                                 }
2126                                 
2127                                 if (cti->flush_constraint_targets)
2128                                         cti->flush_constraint_targets(con, &targets, 1);
2129                         }
2130                 }
2131         }
2132         
2133         if(ob->parent) {
2134                 /* motion path or bone child */
2135                 if(ob->parent->type==OB_CURVE || ob->parent->type==OB_ARMATURE) ob->recalc |= OB_RECALC_OB;
2136         }
2137         
2138 #if 0 // XXX old animation system
2139         if(ob->nlastrips.first) {
2140                 if(ob->dup_group) {
2141                         bActionStrip *strip;
2142                         /* this case is for groups with nla, whilst nla target has no action or nla */
2143                         for(strip= ob->nlastrips.first; strip; strip= strip->next) {
2144                                 if(strip->object)
2145                                         strip->object->recalc |= OB_RECALC_ALL;
2146                         }
2147                 }
2148         }
2149 #endif // XXX old animation system
2150         
2151         if(animdata_use_time(ob->adt)) {
2152                 ob->recalc |= OB_RECALC_OB;
2153                 ob->adt->recalc |= ADT_RECALC_ANIM;
2154         }
2155         
2156         if((ob->adt) && (ob->type==OB_ARMATURE)) ob->recalc |= OB_RECALC_DATA;
2157         
2158         if(object_modifiers_use_time(ob)) ob->recalc |= OB_RECALC_DATA;
2159         if((ob->pose) && (ob->pose->flag & POSE_CONSTRAINTS_TIMEDEPEND)) ob->recalc |= OB_RECALC_DATA;
2160         
2161         {
2162                 AnimData *adt= BKE_animdata_from_id((ID *)ob->data);
2163                 Mesh *me;
2164                 Curve *cu;
2165                 Lattice *lt;
2166                 
2167                 switch(ob->type) {
2168                         case OB_MESH:
2169                                 me= ob->data;
2170                                 if(me->key) {
2171                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2172                                                 ob->recalc |= OB_RECALC_DATA;
2173                                         }
2174                                 }
2175                                 if(ob->particlesystem.first)
2176                                         ob->recalc |= OB_RECALC_DATA;
2177                                 break;
2178                         case OB_CURVE:
2179                         case OB_SURF:
2180                                 cu= ob->data;
2181                                 if(cu->key) {
2182                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2183                                                 ob->recalc |= OB_RECALC_DATA;
2184                                         }
2185                                 }
2186                                 break;
2187                         case OB_FONT:
2188                                 cu= ob->data;
2189                                 if(cu->nurb.first==NULL && cu->str && cu->vfont)
2190                                         ob->recalc |= OB_RECALC_DATA;
2191                                 break;
2192                         case OB_LATTICE:
2193                                 lt= ob->data;
2194                                 if(lt->key) {
2195                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2196                                                 ob->recalc |= OB_RECALC_DATA;
2197                                         }
2198                                 }
2199                                         break;
2200                         case OB_MBALL:
2201                                 if(ob->transflag & OB_DUPLI) ob->recalc |= OB_RECALC_DATA;
2202                                 break;
2203                 }
2204                 
2205                 if(animdata_use_time(adt)) {
2206                         ob->recalc |= OB_RECALC_DATA;
2207                         adt->recalc |= ADT_RECALC_ANIM;
2208                 }
2209
2210                 if(ob->particlesystem.first) {
2211                         ParticleSystem *psys= ob->particlesystem.first;
2212
2213                         for(; psys; psys=psys->next) {
2214                                 if(psys_check_enabled(ob, psys)) {
2215                                         ob->recalc |= OB_RECALC_DATA;
2216                                         break;
2217                                 }
2218                         }
2219                 }
2220         }               
2221
2222         if(ob->recalc & OB_RECALC_OB)
2223                 lib_id_recalc_tag(G.main, &ob->id);
2224         if(ob->recalc & OB_RECALC_DATA)
2225                 lib_id_recalc_data_tag(G.main, &ob->id);
2226
2227 }
2228 /* flag all objects that need recalc, for changes in time for example */
2229 /* do_time: make this optional because undo resets objects to their animated locations without this */
2230 void DAG_scene_update_flags(Main *bmain, Scene *scene, unsigned int lay, const short do_time)
2231 {
2232         Base *base;
2233         Object *ob;
2234         Group *group;
2235         GroupObject *go;
2236         Scene *sce_iter;
2237
2238         /* set ob flags where animated systems are */
2239         for(SETLOOPER(scene, sce_iter, base)) {
2240                 ob= base->object;
2241
2242                 if(do_time) {
2243                         /* now if DagNode were part of base, the node->lay could be checked... */
2244                         /* we do all now, since the scene_flush checks layers and clears recalc flags even */
2245                         dag_object_time_update_flags(ob);
2246                 }
2247
2248                 /* handled in next loop */
2249                 if(ob->dup_group)
2250                         ob->dup_group->id.flag |= LIB_DOIT;
2251         }
2252
2253         if(do_time) {
2254                 /* we do groups each once */
2255                 for(group= bmain->group.first; group; group= group->id.next) {
2256                         if(group->id.flag & LIB_DOIT) {
2257                                 for(go= group->gobject.first; go; go= go->next) {
2258                                         dag_object_time_update_flags(go->ob);
2259                                 }
2260                         }
2261                 }
2262         }
2263
2264         for(sce_iter= scene; sce_iter; sce_iter= sce_iter->set)
2265                 DAG_scene_flush_update(bmain, sce_iter, lay, 1);
2266         
2267         if(do_time) {
2268                 /* test: set time flag, to disable baked systems to update */
2269                 for(SETLOOPER(scene, sce_iter, base)) {
2270                         ob= base->object;
2271                         if(ob->recalc)
2272                                 ob->recalc |= OB_RECALC_TIME;
2273                 }
2274
2275                 /* hrmf... an exception to look at once, for invisible camera object we do it over */
2276                 if(scene->camera)
2277                         dag_object_time_update_flags(scene->camera);
2278         }
2279
2280         /* and store the info in groupobject */
2281         for(group= bmain->group.first; group; group= group->id.next) {
2282                 if(group->id.flag & LIB_DOIT) {
2283                         for(go= group->gobject.first; go; go= go->next) {
2284                                 go->recalc= go->ob->recalc;
2285                                 // printf("ob %s recalc %d\n", go->ob->id.name, go->recalc);
2286                         }
2287                         group->id.flag &= ~LIB_DOIT;
2288                 }
2289         }
2290         
2291 }
2292
2293 static void dag_current_scene_layers(Main *bmain, Scene **sce, unsigned int *lay)
2294 {
2295         wmWindowManager *wm;
2296         wmWindow *win;
2297
2298         /* only one scene supported currently, making more scenes work
2299            correctly requires changes beyond just the dependency graph */
2300
2301         *sce= NULL;
2302         *lay= 0;
2303
2304         if((wm= bmain->wm.first)) {
2305                 /* if we have a windowmanager, look into windows */
2306                 for(win=wm->windows.first; win; win=win->next) {
2307                         if(win->screen) {
2308                                 if(!*sce) *sce= win->screen->scene;
2309                                 *lay |= BKE_screen_visible_layers(win->screen, win->screen->scene);
2310                         }
2311                 }
2312         }
2313         else {
2314                 /* if not, use the first sce */
2315                 *sce= bmain->scene.first;
2316                 if(*sce) *lay= (*sce)->lay;
2317
2318                 /* XXX for background mode, we should get the scene
2319                    from somewhere, for the -S option, but it's in
2320                    the context, how to get it here? */
2321         }
2322 }
2323
2324 void DAG_ids_flush_update(Main *bmain, int time)
2325 {
2326         Scene *sce;
2327         unsigned int lay;
2328
2329         dag_current_scene_layers(bmain, &sce, &lay);
2330
2331         if(sce)
2332                 DAG_scene_flush_update(bmain, sce, lay, time);
2333 }
2334
2335 void DAG_on_visible_update(Main *bmain, const short do_time)
2336 {
2337         Scene *scene;
2338         Base *base;
2339         Object *ob;
2340         Group *group;
2341         GroupObject *go;
2342         DagNode *node;
2343         unsigned int lay, oblay;
2344
2345         dag_current_scene_layers(bmain, &scene, &lay);
2346
2347         if(scene && scene->theDag) {
2348                 Scene *sce_iter;
2349                 /* derivedmeshes and displists are not saved to file so need to be
2350                    remade, tag them so they get remade in the scene update loop,
2351                    note armature poses or object matrices are preserved and do not
2352                    require updates, so we skip those */
2353                 dag_scene_flush_layers(scene, lay);
2354
2355                 for(SETLOOPER(scene, sce_iter, base)) {
2356                         ob= base->object;
2357                         node= (sce_iter->theDag)? dag_get_node(sce_iter->theDag, ob): NULL;
2358                         oblay= (node)? node->lay: ob->lay;
2359
2360                         if((oblay & lay) & ~scene->lay_updated) {
2361                                 if(ELEM6(ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2362                                         ob->recalc |= OB_RECALC_DATA;
2363                                 if(ob->dup_group) 
2364                                         ob->dup_group->id.flag |= LIB_DOIT;
2365                         }
2366                 }
2367
2368                 for(group= bmain->group.first; group; group= group->id.next) {
2369                         if(group->id.flag & LIB_DOIT) {
2370                                 for(go= group->gobject.first; go; go= go->next) {
2371                                         if(ELEM6(go->ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2372                                                 go->ob->recalc |= OB_RECALC_DATA;
2373                                         if(go->ob->proxy_from)
2374                                                 go->ob->recalc |= OB_RECALC_OB;
2375                                 }
2376                                 
2377                                 group->id.flag &= ~LIB_DOIT;
2378                         }
2379                 }
2380
2381                 /* now tag update flags, to ensure deformers get calculated on redraw */
2382                 DAG_scene_update_flags(bmain, scene, lay, do_time);
2383                 scene->lay_updated |= lay;
2384         }
2385
2386         /* hack to get objects updating on layer changes */
2387         DAG_id_type_tag(bmain, ID_OB);
2388 }
2389
2390 static void dag_id_flush_update__isDependentTexture(void *userData, Object *UNUSED(ob), ID **idpoin)
2391 {
2392         struct { ID *id; int is_dependent; } *data = userData;
2393         
2394         if(*idpoin && GS((*idpoin)->name)==ID_TE) {
2395                 if (data->id == (*idpoin))
2396                         data->is_dependent = 1;
2397         }
2398 }
2399
2400 static void dag_id_flush_update(Scene *sce, ID *id)
2401 {
2402         Main *bmain= G.main;
2403         Object *obt, *ob= NULL;
2404         short idtype;
2405
2406         /* here we flush a few things before actual scene wide flush, mostly
2407            due to only objects and not other datablocks being in the depsgraph */
2408
2409         /* set flags & pointcache for object */
2410         if(GS(id->name) == ID_OB) {
2411                 ob= (Object*)id;
2412                 BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH);
2413
2414                 if(ob->recalc & OB_RECALC_DATA) {
2415                         /* all users of this ob->data should be checked */
2416                         id= ob->data;
2417
2418                         /* no point in trying in this cases */
2419                         if(id && id->us <= 1) {
2420                                 dag_editors_update(bmain, id);
2421                                 id= NULL;
2422                         }
2423                 }
2424         }
2425
2426         /* set flags & pointcache for object data */
2427         if(id) {
2428                 idtype= GS(id->name);
2429
2430                 if(ELEM8(idtype, ID_ME, ID_CU, ID_MB, ID_LA, ID_LT, ID_CA, ID_AR, ID_SPK)) {
2431                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2432                                 if(!(ob && obt == ob) && obt->data == id) {
2433                                         obt->recalc |= OB_RECALC_DATA;
2434                                         lib_id_recalc_data_tag(bmain, &obt->id);
2435                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2436                                 }
2437                         }
2438                 }
2439                 
2440                 /* set flags based on textures - can influence depgraph via modifiers */
2441                 if(idtype == ID_TE) {
2442                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2443                                 struct { ID *id; int is_dependent; } data;
2444                                 data.id= id;
2445                                 data.is_dependent= 0;
2446
2447                                 modifiers_foreachIDLink(obt, dag_id_flush_update__isDependentTexture, &data);
2448                                 if (data.is_dependent) {
2449                                         obt->recalc |= OB_RECALC_DATA;
2450                                         lib_id_recalc_data_tag(bmain, &obt->id);
2451                                 }
2452
2453                                 /* particle settings can use the texture as well */
2454                                 if(obt->particlesystem.first) {
2455                                         ParticleSystem *psys = obt->particlesystem.first;
2456                                         MTex **mtexp, *mtex;
2457                                         int a;
2458                                         for(; psys; psys=psys->next) {
2459                                                 mtexp = psys->part->mtex;
2460                                                 for(a=0; a<MAX_MTEX; a++, mtexp++) {
2461                                                         mtex = *mtexp;
2462                                                         if(mtex && mtex->tex == (Tex*)id) {
2463                                                                 obt->recalc |= OB_RECALC_DATA;
2464                                                                 lib_id_recalc_data_tag(bmain, &obt->id);
2465
2466                                                                 if(mtex->mapto & PAMAP_INIT)
2467                                                                         psys->recalc |= PSYS_RECALC_RESET;
2468                                                                 if(mtex->mapto & PAMAP_CHILD)
2469                                                                         psys->recalc |= PSYS_RECALC_CHILD;
2470
2471                                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2472                                                         }
2473                                                 }
2474                                         }
2475                                 }
2476                         }
2477                 }
2478                 
2479                 /* set flags based on ShapeKey */
2480                 if(idtype == ID_KE) {
2481                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2482                                 Key *key= ob_get_key(obt);
2483                                 if(!(ob && obt == ob) && ((ID *)key == id)) {
2484                                         obt->flag |= (OB_RECALC_OB|OB_RECALC_DATA);
2485                                         lib_id_recalc_tag(bmain, &obt->id);
2486                                         lib_id_recalc_data_tag(bmain, &obt->id);
2487                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2488                                 }
2489                         }
2490                 }
2491                 
2492                 /* set flags based on particle settings */
2493                 if(idtype == ID_PA) {
2494                         ParticleSystem *psys;
2495                         for(obt=bmain->object.first; obt; obt= obt->id.next)
2496                                 for(psys=obt->particlesystem.first; psys; psys=psys->next)
2497                                         if(&psys->part->id == id)
2498                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2499                 }
2500
2501                 /* update editors */
2502                 dag_editors_update(bmain, id);
2503         }
2504 }
2505
2506 void DAG_ids_flush_tagged(Main *bmain)
2507 {
2508         ListBase *lbarray[MAX_LIBARRAY];
2509         Scene *sce;
2510         unsigned int lay;
2511         int a, do_flush = 0;
2512
2513         dag_current_scene_layers(bmain, &sce, &lay);
2514
2515         if(!sce || !sce->theDag)
2516                 return;
2517
2518         /* loop over all ID types */
2519         a  = set_listbasepointers(bmain, lbarray);
2520
2521         while(a--) {
2522                 ListBase *lb = lbarray[a];
2523                 ID *id = lb->first;
2524
2525                 /* we tag based on first ID type character to avoid 
2526                    looping over all ID's in case there are no tags */
2527                 if(id && bmain->id_tag_update[id->name[0]]) {
2528                         for(; id; id=id->next) {
2529                                 if(id->flag & (LIB_ID_RECALC|LIB_ID_RECALC_DATA)) {
2530                                         dag_id_flush_update(sce, id);
2531                                         do_flush = 1;
2532                                 }
2533                         }
2534                 }
2535         }
2536
2537         /* flush changes to other objects */
2538         if(do_flush)
2539                 DAG_scene_flush_update(bmain, sce, lay, 0);
2540 }
2541
2542 void DAG_ids_check_recalc(Main *bmain)
2543 {
2544         ListBase *lbarray[MAX_LIBARRAY];
2545         int a;
2546
2547         /* loop over all ID types */
2548         a  = set_listbasepointers(bmain, lbarray);
2549
2550         while(a--) {
2551                 ListBase *lb = lbarray[a];
2552                 ID *id = lb->first;
2553
2554                 /* we tag based on first ID type character to avoid 
2555                    looping over all ID's in case there are no tags */
2556                 if(id && bmain->id_tag_update[id->name[0]]) {
2557                         /* do editors update */
2558                         dag_editors_update(bmain, NULL);
2559                         return;
2560                 }
2561         }
2562 }
2563
2564
2565 void DAG_ids_clear_recalc(Main *bmain)
2566 {
2567         ListBase *lbarray[MAX_LIBARRAY];
2568         int a;
2569
2570         /* loop over all ID types */
2571         a  = set_listbasepointers(bmain, lbarray);
2572
2573         while(a--) {
2574                 ListBase *lb = lbarray[a];
2575                 ID *id = lb->first;
2576
2577                 /* we tag based on first ID type character to avoid 
2578                    looping over all ID's in case there are no tags */
2579                 if(id && bmain->id_tag_update[id->name[0]]) {
2580                         for(; id; id=id->next)
2581                                 if(id->flag & (LIB_ID_RECALC|LIB_ID_RECALC_DATA))
2582                                         id->flag &= ~(LIB_ID_RECALC|LIB_ID_RECALC_DATA);
2583                 }
2584         }
2585
2586         memset(bmain->id_tag_update, 0, sizeof(bmain->id_tag_update));
2587 }
2588
2589 void DAG_id_tag_update(ID *id, short flag)
2590 {
2591         Main *bmain= G.main;
2592
2593         if(id==NULL) return;
2594         
2595         /* tag ID for update */
2596         if(flag) {
2597                 if(flag & OB_RECALC_OB)
2598                         lib_id_recalc_tag(bmain, id);
2599                 if(flag & (OB_RECALC_DATA|PSYS_RECALC))
2600                         lib_id_recalc_data_tag(bmain, id);
2601         }
2602         else
2603                 lib_id_recalc_tag(bmain, id);
2604
2605         /* flag is for objects and particle systems */
2606         if(flag) {
2607                 Object *ob;
2608                 ParticleSystem *psys;
2609                 short idtype = GS(id->name);
2610
2611                 if(idtype == ID_OB) {
2612                         /* only quick tag */
2613                         ob = (Object*)id;
2614                         ob->recalc |= (flag & OB_RECALC_ALL);
2615                 }
2616                 else if(idtype == ID_PA) {
2617                         /* this is weak still, should be done delayed as well */
2618                         for(ob=bmain->object.first; ob; ob=ob->id.next) {
2619                                 for(psys=ob->particlesystem.first; psys; psys=psys->next) {
2620                                         if(&psys->part->id == id) {
2621                                                 ob->recalc |= (flag & OB_RECALC_ALL);
2622                                                 psys->recalc |= (flag & PSYS_RECALC);
2623                                         }
2624                                 }
2625                         }
2626                 }
2627                 else {
2628                         /* disable because this is called on various ID types automatically.
2629                          * where printing warning is not useful. for now just ignore */
2630                         /* BLI_assert(!"invalid flag for this 'idtype'"); */
2631                 }
2632         }
2633 }
2634
2635 void DAG_id_type_tag(struct Main *bmain, short idtype)
2636 {
2637         bmain->id_tag_update[((char*)&idtype)[0]] = 1;
2638 }
2639
2640 int DAG_id_type_tagged(Main *bmain, short idtype)
2641 {
2642         return bmain->id_tag_update[((char*)&idtype)[0]];
2643 }
2644
2645 #if 0 // UNUSED
2646 /* recursively descends tree, each node only checked once */
2647 /* node is checked to be of type object */
2648 static int parent_check_node(DagNode *node, int curtime)
2649 {
2650         DagAdjList *itA;
2651         
2652         node->lasttime= curtime;
2653         
2654         if(node->color==DAG_GRAY)
2655                 return DAG_GRAY;
2656         
2657         for(itA = node->child; itA; itA= itA->next) {
2658                 if(itA->node->type==ID_OB) {
2659                         
2660                         if(itA->node->color==DAG_GRAY)
2661                                 return DAG_GRAY;
2662
2663                         /* descend if not done */
2664                         if(itA->node->lasttime!=curtime) {
2665                                 itA->node->color= parent_check_node(itA->node, curtime);
2666                         
2667                                 if(itA->node->color==DAG_GRAY)
2668                                         return DAG_GRAY;
2669                         }
2670                 }
2671         }
2672         
2673         return DAG_WHITE;
2674 }
2675 #endif
2676
2677 /* ******************* DAG FOR ARMATURE POSE ***************** */
2678
2679 /* we assume its an armature with pose */
2680 void DAG_pose_sort(Object *ob)
2681 {
2682         bPose *pose= ob->pose;
2683         bPoseChannel *pchan;
2684         bConstraint *con;
2685         DagNode *node;
2686         DagNode *node2, *node3;
2687         DagNode *rootnode;
2688         DagForest *dag;
2689         DagNodeQueue *nqueue;
2690         DagAdjList *itA;
2691         ListBase tempbase;
2692         int skip = 0;
2693         
2694         dag = dag_init();
2695         ugly_hack_sorry= 0;     // no ID structs
2696
2697         rootnode = dag_add_node(dag, NULL);     // node->ob becomes NULL
2698         
2699         /* we add the hierarchy and the constraints */
2700         for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
2701                 int addtoroot = 1;
2702                 
2703                 node = dag_get_node(dag, pchan);
2704                 
2705                 if(pchan->parent) {
2706                         node2 = dag_get_node(dag, pchan->parent);
2707                         dag_add_relation(dag, node2, node, 0, "Parent Relation");
2708                         addtoroot = 0;
2709                 }
2710                 for (con = pchan->constraints.first; con; con=con->next) {
2711                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2712                         ListBase targets = {NULL, NULL};
2713                         bConstraintTarget *ct;
2714                         
2715                         if (cti && cti->get_constraint_targets) {
2716                                 cti->get_constraint_targets(con, &targets);
2717                                 
2718                                 for (ct= targets.first; ct; ct= ct->next) {
2719                                         if (ct->tar==ob && ct->subtarget[0]) {
2720                                                 bPoseChannel *target= get_pose_channel(ob->pose, ct->subtarget);
2721                                                 if (target) {
2722                                                         node2= dag_get_node(dag, target);
2723                                                         dag_add_relation(dag, node2, node, 0, "Pose Constraint");
2724                                                         
2725                                                         if (con->type==CONSTRAINT_TYPE_KINEMATIC) {
2726                                                                 bKinematicConstraint *data = (bKinematicConstraint *)con->data;
2727                                                                 bPoseChannel *parchan;
2728                                                                 int segcount= 0;
2729                                                                 
2730                                                                 /* exclude tip from chain? */
2731                                                                 if(!(data->flag & CONSTRAINT_IK_TIP))
2732                                                                         parchan= pchan->parent;
2733                                                                 else
2734                                                                         parchan= pchan;
2735                                                                 
2736                                                                 /* Walk to the chain's root */
2737                                                                 while (parchan) {
2738                                                                         node3= dag_get_node(dag, parchan);
2739                                                                         dag_add_relation(dag, node2, node3, 0, "IK Constraint");
2740                                                                         
2741                                                                         segcount++;
2742                                                                         if (segcount==data->rootbone || segcount>255) break; // 255 is weak
2743                                                                         parchan= parchan->parent;
2744                                                                 }
2745                                                         }
2746                                                 }
2747                                         }
2748                                 }
2749                                 
2750                                 if (cti->flush_constraint_targets)
2751                                         cti->flush_constraint_targets(con, &targets, 1);
2752                         }
2753                 }
2754                 if (addtoroot == 1 ) {
2755                         dag_add_relation(dag, rootnode, node, 0, "Root Bone Relation");
2756                 }
2757         }
2758
2759         dag_check_cycle(dag);
2760         
2761         /* now we try to sort... */
2762         tempbase.first= tempbase.last= NULL;
2763
2764         nqueue = queue_create(DAGQUEUEALLOC);
2765         
2766         /* tag nodes unchecked */
2767         for(node = dag->DagNode.first; node; node= node->next) 
2768                 node->color = DAG_WHITE;
2769         
2770         node = dag->DagNode.first;
2771         
2772         node->color = DAG_GRAY;
2773         push_stack(nqueue, node);  
2774         
2775         while(nqueue->count) {
2776                 
2777                 skip = 0;
2778                 node = get_top_node_queue(nqueue);
2779                 
2780                 itA = node->child;
2781                 while(itA != NULL) {
2782                         if(itA->node->color == DAG_WHITE) {
2783                                 itA->node->color = DAG_GRAY;
2784                                 push_stack(nqueue,itA->node);
2785                                 skip = 1;
2786                                 break;
2787                         } 
2788                         itA = itA->next;
2789                 }                       
2790                 
2791                 if (!skip) {
2792                         if (node) {
2793                                 node = pop_queue(nqueue);
2794                                 if (node->ob == NULL)   // we are done
2795                                         break ;
2796                                 node->color = DAG_BLACK;
2797                                 
2798                                 /* put node in new list */
2799                                 BLI_remlink(&pose->chanbase, node->ob);
2800                                 BLI_addhead(&tempbase, node->ob);
2801                         }       
2802                 }
2803         }
2804         
2805         // temporal correction for circular dependancies
2806         while(pose->chanbase.first) {
2807                 pchan= pose->chanbase.first;
2808                 BLI_remlink(&pose->chanbase, pchan);
2809                 BLI_addhead(&tempbase, pchan);
2810
2811                 printf("cyclic %s\n", pchan->name);
2812         }
2813         
2814         pose->chanbase = tempbase;
2815         queue_delete(nqueue);
2816         
2817 //      printf("\nordered\n");
2818 //      for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
2819 //              printf(" %s\n", pchan->name);
2820 //      }
2821         
2822         free_forest( dag );
2823         MEM_freeN( dag );
2824         
2825         ugly_hack_sorry= 1;
2826 }
2827
2828
2829