Merging trunk up to revision 41245.
[blender.git] / source / blender / blenkernel / intern / depsgraph.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2004 Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): none yet.
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 /** \file blender/blenkernel/intern/depsgraph.c
27  *  \ingroup bke
28  */
29
30  
31 #include <stdio.h>
32 #include <string.h>
33 #include <math.h>
34
35 #include "MEM_guardedalloc.h"
36
37 #include "BLI_winstuff.h"
38 #include "BLI_utildefines.h"
39 #include "BLI_listbase.h"
40 #include "BLI_ghash.h"
41
42 #include "DNA_anim_types.h"
43 #include "DNA_camera_types.h"
44 #include "DNA_group_types.h"
45 #include "DNA_lattice_types.h"
46 #include "DNA_key_types.h"
47 #include "DNA_material_types.h"
48 #include "DNA_mesh_types.h"
49 #include "DNA_node_types.h"
50 #include "DNA_scene_types.h"
51 #include "DNA_screen_types.h"
52 #include "DNA_windowmanager_types.h"
53 #include "DNA_movieclip_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)
644                         continue;
645
646                 /* special case for FollowTrack -- it doesn't use targets to define relations */
647                 if(ELEM(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER)) {
648                         if(cti->type==CONSTRAINT_TYPE_FOLLOWTRACK) {
649                                 bFollowTrackConstraint *data= (bFollowTrackConstraint *)con->data;
650
651                                 if((data->clip || data->flag&FOLLOWTRACK_ACTIVECLIP) && data->track[0]) {
652                                         if(scene->camera) {
653                                                 node2 = dag_get_node(dag, scene->camera);
654                                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_OB|DAG_RL_OB_OB, cti->name);
655                                         }
656                                 }
657                         }
658
659                         dag_add_relation(dag,scenenode,node,DAG_RL_SCENE, "Scene Relation");
660                         addtoroot = 0;
661                 }
662                 else if (cti->get_constraint_targets) {
663                         cti->get_constraint_targets(con, &targets);
664                         
665                         for (ct= targets.first; ct; ct= ct->next) {
666                                 Object *obt;
667                                 
668                                 if (ct->tar)
669                                         obt= ct->tar;
670                                 else
671                                         continue;
672                                 
673                                 node2 = dag_get_node(dag, obt);
674                                 if (ELEM(con->type, CONSTRAINT_TYPE_FOLLOWPATH, CONSTRAINT_TYPE_CLAMPTO))
675                                         dag_add_relation(dag, node2, node, DAG_RL_DATA_OB|DAG_RL_OB_OB, cti->name);
676                                 else {
677                                         if (ELEM3(obt->type, OB_ARMATURE, OB_MESH, OB_LATTICE) && (ct->subtarget[0])) {
678                                                 dag_add_relation(dag, node2, node, DAG_RL_DATA_OB|DAG_RL_OB_OB, cti->name);
679                                                 if (obt->type == OB_MESH)
680                                                         node2->customdata_mask |= CD_MASK_MDEFORMVERT;
681                                         }
682                                         else
683                                                 dag_add_relation(dag, node2, node, DAG_RL_OB_OB, cti->name);
684                                 }
685                                 addtoroot = 0;
686                         }
687                         
688                         if (cti->flush_constraint_targets)
689                                 cti->flush_constraint_targets(con, &targets, 1);
690                 }
691         }
692
693         if (addtoroot == 1 )
694                 dag_add_relation(dag,scenenode,node,DAG_RL_SCENE, "Scene Relation");
695 }
696
697 struct DagForest *build_dag(Main *bmain, Scene *sce, short mask) 
698 {
699         Base *base;
700         Object *ob;
701         Group *group;
702         GroupObject *go;
703         DagNode *node;
704         DagNode *scenenode;
705         DagForest *dag;
706         DagAdjList *itA;
707
708         dag = sce->theDag;
709         sce->dagisvalid=1;
710         if ( dag)
711                 free_forest( dag ); 
712         else {
713                 dag = dag_init();
714                 sce->theDag = dag;
715         }
716         
717         /* add base node for scene. scene is always the first node in DAG */
718         scenenode = dag_add_node(dag, sce);     
719         
720         /* add current scene objects */
721         for(base = sce->base.first; base; base= base->next) {
722                 ob= base->object;
723                 
724                 build_dag_object(dag, scenenode, sce, ob, mask);
725                 if(ob->proxy)
726                         build_dag_object(dag, scenenode, sce, ob->proxy, mask);
727                 
728                 /* handled in next loop */
729                 if(ob->dup_group) 
730                         ob->dup_group->id.flag |= LIB_DOIT;
731         }
732         
733         /* add groups used in current scene objects */
734         for(group= bmain->group.first; group; group= group->id.next) {
735                 if(group->id.flag & LIB_DOIT) {
736                         for(go= group->gobject.first; go; go= go->next) {
737                                 build_dag_object(dag, scenenode, sce, go->ob, mask);
738                         }
739                         group->id.flag &= ~LIB_DOIT;
740                 }
741         }
742         
743         /* Now all relations were built, but we need to solve 1 exceptional case;
744            When objects have multiple "parents" (for example parent + constraint working on same object)
745            the relation type has to be synced. One of the parents can change, and should give same event to child */
746         
747         /* nodes were callocced, so we can use node->color for temporal storage */
748         for(node = sce->theDag->DagNode.first; node; node= node->next) {
749                 if(node->type==ID_OB) {
750                         for(itA = node->child; itA; itA= itA->next) {
751                                 if(itA->node->type==ID_OB) {
752                                         itA->node->color |= itA->type;
753                                 }
754                         }
755
756                         /* also flush custom data mask */
757                         ((Object*)node->ob)->customdata_mask= node->customdata_mask;
758                 }
759         }
760         /* now set relations equal, so that when only one parent changes, the correct recalcs are found */
761         for(node = sce->theDag->DagNode.first; node; node= node->next) {
762                 if(node->type==ID_OB) {
763                         for(itA = node->child; itA; itA= itA->next) {
764                                 if(itA->node->type==ID_OB) {
765                                         itA->type |= itA->node->color;
766                                 }
767                         }
768                 }
769         }
770         
771         // cycle detection and solving
772         // solve_cycles(dag);   
773         
774         return dag;
775 }
776
777
778 void free_forest(DagForest *Dag) 
779 {  /* remove all nodes and deps */
780         DagNode *tempN;
781         DagAdjList *tempA;      
782         DagAdjList *itA;
783         DagNode *itN = Dag->DagNode.first;
784         
785         while (itN) {
786                 itA = itN->child;       
787                 while (itA) {
788                         tempA = itA;
789                         itA = itA->next;
790                         MEM_freeN(tempA);                       
791                 }
792                 
793                 itA = itN->parent;      
794                 while (itA) {
795                         tempA = itA;
796                         itA = itA->next;
797                         MEM_freeN(tempA);                       
798                 }
799                 
800                 tempN = itN;
801                 itN = itN->next;
802                 MEM_freeN(tempN);
803         }
804
805         BLI_ghash_free(Dag->nodeHash, NULL, NULL);
806         Dag->nodeHash= NULL;
807         Dag->DagNode.first = NULL;
808         Dag->DagNode.last = NULL;
809         Dag->numNodes = 0;
810
811 }
812
813 DagNode * dag_find_node (DagForest *forest,void * fob)
814 {
815         if(forest->nodeHash)
816                 return BLI_ghash_lookup(forest->nodeHash, fob);
817
818         return NULL;
819 }
820
821 static int ugly_hack_sorry= 1;  // prevent type check
822
823 /* no checking of existence, use dag_find_node first or dag_get_node */
824 DagNode * dag_add_node (DagForest *forest, void * fob)
825 {
826         DagNode *node;
827                 
828         node = MEM_callocN(sizeof(DagNode),"DAG node");
829         if (node) {
830                 node->ob = fob;
831                 node->color = DAG_WHITE;
832
833                 if(ugly_hack_sorry) node->type = GS(((ID *) fob)->name);        // sorry, done for pose sorting
834                 if (forest->numNodes) {
835                         ((DagNode *) forest->DagNode.last)->next = node;
836                         forest->DagNode.last = node;
837                         forest->numNodes++;
838                 } else {
839                         forest->DagNode.last = node;
840                         forest->DagNode.first = node;
841                         forest->numNodes = 1;
842                 }
843
844                 if(!forest->nodeHash)
845                         forest->nodeHash= BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "dag_add_node gh");
846                 BLI_ghash_insert(forest->nodeHash, fob, node);
847         }
848
849         return node;
850 }
851
852 DagNode * dag_get_node (DagForest *forest,void * fob)
853 {
854         DagNode *node;
855         
856         node = dag_find_node (forest, fob);     
857         if (!node) 
858                 node = dag_add_node(forest, fob);
859         return node;
860 }
861
862
863
864 DagNode * dag_get_sub_node (DagForest *forest,void * fob)
865 {
866         DagNode *node;
867         DagAdjList *mainchild, *prev=NULL;
868         
869         mainchild = ((DagNode *) forest->DagNode.first)->child;
870         /* remove from first node (scene) adj list if present */
871         while (mainchild) {
872                 if (mainchild->node == fob) {
873                         if (prev) {
874                                 prev->next = mainchild->next;
875                                 MEM_freeN(mainchild);
876                                 break;
877                         } else {
878                                 ((DagNode *) forest->DagNode.first)->child = mainchild->next;
879                                 MEM_freeN(mainchild);
880                                 break;
881                         }
882                 }
883                 prev = mainchild;
884                 mainchild = mainchild->next;
885         }
886         node = dag_find_node (forest, fob);     
887         if (!node) 
888                 node = dag_add_node(forest, fob);
889         return node;
890 }
891
892 static void dag_add_parent_relation(DagForest *UNUSED(forest), DagNode *fob1, DagNode *fob2, short rel, const char *name) 
893 {
894         DagAdjList *itA = fob2->parent;
895         
896         while (itA) { /* search if relation exist already */
897                 if (itA->node == fob1) {
898                         itA->type |= rel;
899                         itA->count += 1;
900                         return;
901                 }
902                 itA = itA->next;
903         }
904         /* create new relation and insert at head. MALLOC alert! */
905         itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list");
906         itA->node = fob1;
907         itA->type = rel;
908         itA->count = 1;
909         itA->next = fob2->parent;
910         itA->name = name;
911         fob2->parent = itA;
912 }
913
914 void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, short rel, const char *name) 
915 {
916         DagAdjList *itA = fob1->child;
917         
918         /* parent relation is for cycle checking */
919         dag_add_parent_relation(forest, fob1, fob2, rel, name);
920
921         while (itA) { /* search if relation exist already */
922                 if (itA->node == fob2) {
923                         itA->type |= rel;
924                         itA->count += 1;
925                         return;
926                 }
927                 itA = itA->next;
928         }
929         /* create new relation and insert at head. MALLOC alert! */
930         itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list");
931         itA->node = fob2;
932         itA->type = rel;
933         itA->count = 1;
934         itA->next = fob1->child;
935         itA->name = name;
936         fob1->child = itA;
937 }
938
939 static const char *dag_node_name(DagNode *node)
940 {
941         if(node->ob == NULL)
942                 return "null";
943         else if(ugly_hack_sorry)
944                 return ((ID*)(node->ob))->name+2;
945         else
946                 return ((bPoseChannel*)(node->ob))->name;
947 }
948
949 #if 0
950 static void dag_node_print_dependencies(DagNode *node)
951 {
952         DagAdjList *itA;
953
954         printf("%s depends on:\n", dag_node_name(node));
955
956         for(itA= node->parent; itA; itA= itA->next)
957                 printf("  %s through %s\n", dag_node_name(itA->node), itA->name);
958         printf("\n");
959 }
960 #endif
961
962 static int dag_node_print_dependency_recurs(DagNode *node, DagNode *endnode)
963 {
964         DagAdjList *itA;
965
966         if(node->color == DAG_BLACK)
967                 return 0;
968
969         node->color= DAG_BLACK;
970
971         if(node == endnode)
972                 return 1;
973
974         for(itA= node->parent; itA; itA= itA->next) {
975                 if(dag_node_print_dependency_recurs(itA->node, endnode)) {
976                         printf("  %s depends on %s through %s.\n", dag_node_name(node), dag_node_name(itA->node), itA->name);
977                         return 1;
978                 }
979         }
980
981         return 0;
982 }
983
984 static void dag_node_print_dependency_cycle(DagForest *dag, DagNode *startnode, DagNode *endnode, const char *name)
985 {
986         DagNode *node;
987
988         for(node = dag->DagNode.first; node; node= node->next)
989                 node->color= DAG_WHITE;
990
991         printf("  %s depends on %s through %s.\n", dag_node_name(endnode), dag_node_name(startnode), name);
992         dag_node_print_dependency_recurs(startnode, endnode);
993         printf("\n");
994 }
995
996 static int dag_node_recurs_level(DagNode *node, int level)
997 {
998         DagAdjList *itA;
999         int newlevel;
1000
1001         node->color= DAG_BLACK; /* done */
1002         newlevel= ++level;
1003         
1004         for(itA= node->parent; itA; itA= itA->next) {
1005                 if(itA->node->color==DAG_WHITE) {
1006                         itA->node->ancestor_count= dag_node_recurs_level(itA->node, level);
1007                         newlevel= MAX2(newlevel, level+itA->node->ancestor_count);
1008                 }
1009                 else
1010                         newlevel= MAX2(newlevel, level+itA->node->ancestor_count);
1011         }
1012         
1013         return newlevel;
1014 }
1015
1016 static void dag_check_cycle(DagForest *dag)
1017 {
1018         DagNode *node;
1019         DagAdjList *itA;
1020
1021         /* tag nodes unchecked */
1022         for(node = dag->DagNode.first; node; node= node->next)
1023                 node->color= DAG_WHITE;
1024         
1025         for(node = dag->DagNode.first; node; node= node->next) {
1026                 if(node->color==DAG_WHITE) {
1027                         node->ancestor_count= dag_node_recurs_level(node, 0);
1028                 }
1029         }
1030         
1031         /* check relations, and print errors */
1032         for(node = dag->DagNode.first; node; node= node->next) {
1033                 for(itA= node->parent; itA; itA= itA->next) {
1034                         if(itA->node->ancestor_count > node->ancestor_count) {
1035                                 if(node->ob && itA->node->ob) {
1036                                         printf("Dependency cycle detected:\n");
1037                                         dag_node_print_dependency_cycle(dag, itA->node, node, itA->name);
1038                                 }
1039                         }
1040                 }
1041         }
1042
1043         /* parent relations are only needed for cycle checking, so free now */
1044         for(node = dag->DagNode.first; node; node= node->next) {
1045                 while (node->parent) {
1046                         itA = node->parent->next;
1047                         MEM_freeN(node->parent);                        
1048                         node->parent = itA;
1049                 }
1050         }
1051 }
1052
1053 /*
1054  * MainDAG is the DAG of all objects in current scene
1055  * used only for drawing there is one also in each scene
1056  */
1057 static DagForest * MainDag = NULL;
1058
1059 DagForest *getMainDag(void)
1060 {
1061         return MainDag;
1062 }
1063
1064
1065 void setMainDag(DagForest *dag)
1066 {
1067         MainDag = dag;
1068 }
1069
1070
1071 /*
1072  * note for BFS/DFS
1073  * in theory we should sweep the whole array
1074  * but in our case the first node is the scene
1075  * and is linked to every other object
1076  *
1077  * for general case we will need to add outer loop
1078  */
1079
1080 /*
1081  * ToDo : change pos kludge
1082  */
1083
1084 /* adjust levels for drawing in oops space */
1085 void graph_bfs(void)
1086 {
1087         DagNode *node;
1088         DagNodeQueue *nqueue;
1089         int pos[50];
1090         int i;
1091         DagAdjList *itA;
1092         int minheight;
1093         
1094         /* fprintf(stderr,"starting BFS \n ------------\n"); */ 
1095         nqueue = queue_create(DAGQUEUEALLOC);
1096         for ( i=0; i<50; i++)
1097                 pos[i] = 0;
1098         
1099         /* Init
1100          * dagnode.first is alway the root (scene) 
1101          */
1102         node = MainDag->DagNode.first;
1103         while(node) {
1104                 node->color = DAG_WHITE;
1105                 node->BFS_dist = 9999;
1106                 node->k = 0;
1107                 node = node->next;
1108         }
1109         
1110         node = MainDag->DagNode.first;
1111         if (node->color == DAG_WHITE) {
1112                 node->color = DAG_GRAY;
1113                 node->BFS_dist = 1;
1114                 push_queue(nqueue,node);  
1115                 while(nqueue->count) {
1116                         node = pop_queue(nqueue);
1117                         
1118                         minheight = pos[node->BFS_dist];
1119                         itA = node->child;
1120                         while(itA != NULL) {
1121                                 if(itA->node->color == DAG_WHITE) {
1122                                         itA->node->color = DAG_GRAY;
1123                                         itA->node->BFS_dist = node->BFS_dist + 1;
1124                                         itA->node->k = (float) minheight;
1125                                         push_queue(nqueue,itA->node);
1126                                 }
1127                                 
1128                                 else {
1129                                         fprintf(stderr,"bfs not dag tree edge color :%i \n",itA->node->color);
1130                                 }
1131
1132                                 
1133                                 itA = itA->next;
1134                         }
1135                         if (pos[node->BFS_dist] > node->k ) {
1136                                 pos[node->BFS_dist] += 1;                               
1137                                 node->k = (float) pos[node->BFS_dist];
1138                         } else {
1139                                 pos[node->BFS_dist] = (int) node->k +1;
1140                         }
1141                         set_node_xy(node, node->BFS_dist*DEPSX*2, pos[node->BFS_dist]*DEPSY*2);
1142                         node->color = DAG_BLACK;
1143                         /*
1144                          fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);   
1145                          */
1146                 }
1147         }
1148         queue_delete(nqueue);
1149 }
1150
1151 int pre_and_post_BFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
1152         DagNode *node;
1153         
1154         node = dag->DagNode.first;
1155         return pre_and_post_source_BFS(dag, mask,  node,  pre_func,  post_func, data);
1156 }
1157
1158
1159 int pre_and_post_source_BFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
1160 {
1161         DagNode *node;
1162         DagNodeQueue *nqueue;
1163         DagAdjList *itA;
1164         int     retval = 0;
1165         /* fprintf(stderr,"starting BFS \n ------------\n"); */ 
1166         
1167         /* Init
1168                 * dagnode.first is alway the root (scene) 
1169                 */
1170         node = dag->DagNode.first;
1171         nqueue = queue_create(DAGQUEUEALLOC);
1172         while(node) {
1173                 node->color = DAG_WHITE;
1174                 node->BFS_dist = 9999;
1175                 node = node->next;
1176         }
1177         
1178         node = source;
1179         if (node->color == DAG_WHITE) {
1180                 node->color = DAG_GRAY;
1181                 node->BFS_dist = 1;
1182                 pre_func(node->ob,data);
1183                 
1184                 while(nqueue->count) {
1185                         node = pop_queue(nqueue);
1186                         
1187                         itA = node->child;
1188                         while(itA != NULL) {
1189                                 if((itA->node->color == DAG_WHITE) && (itA->type & mask)) {
1190                                         itA->node->color = DAG_GRAY;
1191                                         itA->node->BFS_dist = node->BFS_dist + 1;
1192                                         push_queue(nqueue,itA->node);
1193                                         pre_func(node->ob,data);
1194                                 }
1195                                 
1196                                 else { // back or cross edge
1197                                         retval = 1;
1198                                 }
1199                                 itA = itA->next;
1200                         }
1201                         post_func(node->ob,data);
1202                         node->color = DAG_BLACK;
1203                         /*
1204                          fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);   
1205                          */
1206                 }
1207         }
1208         queue_delete(nqueue);
1209         return retval;
1210 }
1211
1212 /* non recursive version of DFS, return queue -- outer loop present to catch odd cases (first level cycles)*/
1213 DagNodeQueue * graph_dfs(void)
1214 {
1215         DagNode *node;
1216         DagNodeQueue *nqueue;
1217         DagNodeQueue *retqueue;
1218         int pos[50];
1219         int i;
1220         DagAdjList *itA;
1221         int time;
1222         int skip = 0;
1223         int minheight;
1224         int maxpos=0;
1225         /* int  is_cycle = 0; */ /* UNUSED */
1226         /*
1227          *fprintf(stderr,"starting DFS \n ------------\n");
1228          */     
1229         nqueue = queue_create(DAGQUEUEALLOC);
1230         retqueue = queue_create(MainDag->numNodes);
1231         for ( i=0; i<50; i++)
1232                 pos[i] = 0;
1233         
1234         /* Init
1235          * dagnode.first is alway the root (scene) 
1236          */
1237         node = MainDag->DagNode.first;
1238         while(node) {
1239                 node->color = DAG_WHITE;
1240                 node->DFS_dist = 9999;
1241                 node->DFS_dvtm = node->DFS_fntm = 9999;
1242                 node->k = 0;
1243                 node =  node->next;
1244         }
1245         
1246         time = 1;
1247         
1248         node = MainDag->DagNode.first;
1249
1250         do {
1251         if (node->color == DAG_WHITE) {
1252                 node->color = DAG_GRAY;
1253                 node->DFS_dist = 1;
1254                 node->DFS_dvtm = time;
1255                 time++;
1256                 push_stack(nqueue,node);  
1257                         
1258                 while(nqueue->count) {
1259                         //graph_print_queue(nqueue);
1260
1261                         skip = 0;
1262                         node = get_top_node_queue(nqueue);
1263                         
1264                         minheight = pos[node->DFS_dist];
1265
1266                         itA = node->child;
1267                         while(itA != NULL) {
1268                                 if(itA->node->color == DAG_WHITE) {
1269                                         itA->node->DFS_dvtm = time;
1270                                         itA->node->color = DAG_GRAY;
1271
1272                                         time++;
1273                                         itA->node->DFS_dist = node->DFS_dist + 1;
1274                                         itA->node->k = (float) minheight;
1275                                         push_stack(nqueue,itA->node);
1276                                         skip = 1;
1277                                         break;
1278                                 } else { 
1279                                         if (itA->node->color == DAG_GRAY) { // back edge
1280                                                 fprintf(stderr,"dfs back edge :%15s %15s \n",((ID *) node->ob)->name, ((ID *) itA->node->ob)->name);
1281                                                 /* is_cycle = 1; */ /* UNUSED */
1282                                         } else if (itA->node->color == DAG_BLACK) {
1283                                                 ;
1284                                                 /* already processed node but we may want later to change distance either to shorter to longer.
1285                                                  * DFS_dist is the first encounter  
1286                                                 */
1287                                                 /*if (node->DFS_dist >= itA->node->DFS_dist)
1288                                                         itA->node->DFS_dist = node->DFS_dist + 1;
1289
1290                                                         fprintf(stderr,"dfs forward or cross edge :%15s %i-%i %15s %i-%i \n",
1291                                                                 ((ID *) node->ob)->name,
1292                                                                 node->DFS_dvtm, 
1293                                                                 node->DFS_fntm, 
1294                                                                 ((ID *) itA->node->ob)->name, 
1295                                                                 itA->node->DFS_dvtm,
1296                                                                 itA->node->DFS_fntm);
1297                                         */
1298                                         } else 
1299                                                 fprintf(stderr,"dfs unknown edge \n");
1300                                 }
1301                                 itA = itA->next;
1302                         }                       
1303
1304                         if (!skip) {
1305                                 node = pop_queue(nqueue);
1306                                 node->color = DAG_BLACK;
1307
1308                                 node->DFS_fntm = time;
1309                                 time++;
1310                                 if (node->DFS_dist > maxpos)
1311                                         maxpos = node->DFS_dist;
1312                                 if (pos[node->DFS_dist] > node->k ) {
1313                                         pos[node->DFS_dist] += 1;                               
1314                                         node->k = (float) pos[node->DFS_dist];
1315                                 } else {
1316                                         pos[node->DFS_dist] = (int) node->k +1;
1317                                 }
1318                                 set_node_xy(node, node->DFS_dist*DEPSX*2, pos[node->DFS_dist]*DEPSY*2);
1319                                 
1320                                 /*
1321                                  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 );       
1322                                 */
1323                                 push_stack(retqueue,node);
1324                                 
1325                         }
1326                 }
1327         }
1328                 node = node->next;
1329         } while (node);
1330 //      fprintf(stderr,"i size : %i \n", maxpos);
1331
1332         queue_delete(nqueue);
1333         return(retqueue);
1334 }
1335
1336 /* unused */
1337 int pre_and_post_DFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
1338         DagNode *node;
1339
1340         node = dag->DagNode.first;
1341         return pre_and_post_source_DFS(dag, mask,  node,  pre_func,  post_func, data);
1342 }
1343
1344 int pre_and_post_source_DFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
1345 {
1346         DagNode *node;
1347         DagNodeQueue *nqueue;
1348         DagAdjList *itA;
1349         int time;
1350         int skip = 0;
1351         int retval = 0;
1352         /*
1353          *fprintf(stderr,"starting DFS \n ------------\n");
1354          */     
1355         nqueue = queue_create(DAGQUEUEALLOC);
1356         
1357         /* Init
1358                 * dagnode.first is alway the root (scene) 
1359                 */
1360         node = dag->DagNode.first;
1361         while(node) {
1362                 node->color = DAG_WHITE;
1363                 node->DFS_dist = 9999;
1364                 node->DFS_dvtm = node->DFS_fntm = 9999;
1365                 node->k = 0;
1366                 node =  node->next;
1367         }
1368         
1369         time = 1;
1370         
1371         node = source;
1372         do {
1373                 if (node->color == DAG_WHITE) {
1374                         node->color = DAG_GRAY;
1375                         node->DFS_dist = 1;
1376                         node->DFS_dvtm = time;
1377                         time++;
1378                         push_stack(nqueue,node);  
1379                         pre_func(node->ob,data);
1380
1381                         while(nqueue->count) {
1382                                 skip = 0;
1383                                 node = get_top_node_queue(nqueue);
1384                                                                 
1385                                 itA = node->child;
1386                                 while(itA != NULL) {
1387                                         if((itA->node->color == DAG_WHITE) && (itA->type & mask) ) {
1388                                                 itA->node->DFS_dvtm = time;
1389                                                 itA->node->color = DAG_GRAY;
1390                                                 
1391                                                 time++;
1392                                                 itA->node->DFS_dist = node->DFS_dist + 1;
1393                                                 push_stack(nqueue,itA->node);
1394                                                 pre_func(node->ob,data);
1395
1396                                                 skip = 1;
1397                                                 break;
1398                                         } else {
1399                                                 if (itA->node->color == DAG_GRAY) {// back edge
1400                                                         retval = 1;
1401                                                 }
1402 //                                              else if (itA->node->color == DAG_BLACK) { // cross or forward
1403 //                                                      ;
1404                                         }
1405                                         itA = itA->next;
1406                                 }                       
1407                                 
1408                                 if (!skip) {
1409                                         node = pop_queue(nqueue);
1410                                         node->color = DAG_BLACK;
1411                                         
1412                                         node->DFS_fntm = time;
1413                                         time++;
1414                                         post_func(node->ob,data);
1415                                 }
1416                         }
1417                 }
1418                 node = node->next;
1419         } while (node);
1420         queue_delete(nqueue);
1421         return(retval);
1422 }
1423
1424
1425 // used to get the obs owning a datablock
1426 struct DagNodeQueue *get_obparents(struct DagForest     *dag, void *ob) 
1427 {
1428         DagNode * node, *node1;
1429         DagNodeQueue *nqueue;
1430         DagAdjList *itA;
1431
1432         node = dag_find_node(dag,ob);
1433         if(node==NULL) {
1434                 return NULL;
1435         }
1436         else if (node->ancestor_count == 1) { // simple case
1437                 nqueue = queue_create(1);
1438                 push_queue(nqueue,node);
1439         } else {        // need to go over the whole dag for adj list
1440                 nqueue = queue_create(node->ancestor_count);
1441                 
1442                 node1 = dag->DagNode.first;
1443                 do {
1444                         if (node1->DFS_fntm > node->DFS_fntm) { // a parent is finished after child. must check adj list
1445                                 itA = node->child;
1446                                 while(itA != NULL) {
1447                                         if ((itA->node == node) && (itA->type == DAG_RL_DATA)) {
1448                                                 push_queue(nqueue,node);
1449                                         }
1450                                         itA = itA->next;
1451                                 }
1452                         }
1453                         node1 = node1->next;
1454                 } while (node1);
1455         }
1456         return nqueue;
1457 }
1458
1459 struct DagNodeQueue *get_first_ancestors(struct DagForest       *dag, void *ob)
1460 {
1461         DagNode * node, *node1;
1462         DagNodeQueue *nqueue;
1463         DagAdjList *itA;
1464         
1465         node = dag_find_node(dag,ob);
1466         
1467         // need to go over the whole dag for adj list
1468         nqueue = queue_create(node->ancestor_count);
1469         
1470         node1 = dag->DagNode.first;
1471         do {
1472                 if (node1->DFS_fntm > node->DFS_fntm) { 
1473                         itA = node->child;
1474                         while(itA != NULL) {
1475                                 if (itA->node == node) {
1476                                         push_queue(nqueue,node);
1477                                 }
1478                                 itA = itA->next;
1479                         }
1480                 }
1481                 node1 = node1->next;
1482         } while (node1);
1483         
1484         return nqueue;  
1485 }
1486
1487 // standard DFS list
1488 struct DagNodeQueue *get_all_childs(struct DagForest    *dag, void *ob)
1489 {
1490         DagNode *node;
1491         DagNodeQueue *nqueue;
1492         DagNodeQueue *retqueue;
1493         DagAdjList *itA;
1494         int time;
1495         int skip = 0;
1496
1497         nqueue = queue_create(DAGQUEUEALLOC);
1498         retqueue = queue_create(dag->numNodes); // was MainDag... why? (ton)
1499         
1500         node = dag->DagNode.first;
1501         while(node) {
1502                 node->color = DAG_WHITE;
1503                 node =  node->next;
1504         }
1505         
1506         time = 1;
1507         
1508         node = dag_find_node(dag, ob);   // could be done in loop above (ton)
1509         if(node) { // can be null for newly added objects
1510                 
1511                 node->color = DAG_GRAY;
1512                 time++;
1513                 push_stack(nqueue,node);  
1514                 
1515                 while(nqueue->count) {
1516                         
1517                         skip = 0;
1518                         node = get_top_node_queue(nqueue);
1519                                         
1520                         itA = node->child;
1521                         while(itA != NULL) {
1522                                 if(itA->node->color == DAG_WHITE) {
1523                                         itA->node->DFS_dvtm = time;
1524                                         itA->node->color = DAG_GRAY;
1525                                         
1526                                         time++;
1527                                         push_stack(nqueue,itA->node);
1528                                         skip = 1;
1529                                         break;
1530                                 } 
1531                                 itA = itA->next;
1532                         }                       
1533                         
1534                         if (!skip) {
1535                                 node = pop_queue(nqueue);
1536                                 node->color = DAG_BLACK;
1537                                 
1538                                 time++;
1539                                 push_stack(retqueue,node);                      
1540                         }
1541                 }
1542         }
1543         queue_delete(nqueue);
1544         return(retqueue);
1545 }
1546
1547 /* unused */
1548 short   are_obs_related(struct DagForest        *dag, void *ob1, void *ob2) {
1549         DagNode * node;
1550         DagAdjList *itA;
1551         
1552         node = dag_find_node(dag, ob1);
1553         
1554         itA = node->child;
1555         while(itA != NULL) {
1556                 if(itA->node->ob == ob2) {
1557                         return itA->node->type;
1558                 } 
1559                 itA = itA->next;
1560         }
1561         return DAG_NO_RELATION;
1562 }
1563
1564 int     is_acyclic( DagForest   *dag) {
1565         return dag->is_acyclic;
1566 }
1567
1568 void set_node_xy(DagNode *node, float x, float y)
1569 {
1570          node->x = x;
1571         node->y = y;
1572 }
1573
1574
1575 /* debug test functions */
1576
1577 void graph_print_queue(DagNodeQueue *nqueue)
1578 {       
1579         DagNodeQueueElem *queueElem;
1580         
1581         queueElem = nqueue->first;
1582         while(queueElem) {
1583                 fprintf(stderr,"** %s %i %i-%i ",((ID *) queueElem->node->ob)->name,queueElem->node->color,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
1584                 queueElem = queueElem->next;            
1585         }
1586         fprintf(stderr,"\n");
1587 }
1588
1589 void graph_print_queue_dist(DagNodeQueue *nqueue)
1590 {       
1591         DagNodeQueueElem *queueElem;
1592         int count;
1593         
1594         queueElem = nqueue->first;
1595         count = 0;
1596         while(queueElem) {
1597                 fprintf(stderr,"** %25s %2.2i-%2.2i ",((ID *) queueElem->node->ob)->name,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
1598                 while (count < queueElem->node->DFS_dvtm-1) { fputc(' ',stderr); count++;}
1599                 fputc('|',stderr); 
1600                 while (count < queueElem->node->DFS_fntm-2) { fputc('-',stderr); count++;}
1601                 fputc('|',stderr);
1602                 fputc('\n',stderr);
1603                 count = 0;
1604                 queueElem = queueElem->next;            
1605         }
1606         fprintf(stderr,"\n");
1607 }
1608
1609 void graph_print_adj_list(void)
1610 {
1611         DagNode *node;
1612         DagAdjList *itA;
1613         
1614         node = (getMainDag())->DagNode.first;
1615         while(node) {
1616                 fprintf(stderr,"node : %s col: %i",((ID *) node->ob)->name, node->color);               
1617                 itA = node->child;
1618                 while (itA) {
1619                         fprintf(stderr,"-- %s ",((ID *) itA->node->ob)->name);
1620                         
1621                         itA = itA->next;
1622                 }
1623                 fprintf(stderr,"\n");
1624                 node = node->next;
1625         }
1626 }
1627
1628 /* ************************ API *********************** */
1629
1630 /* mechanism to allow editors to be informed of depsgraph updates,
1631    to do their own updates based on changes... */
1632 static void (*EditorsUpdateCb)(Main *bmain, ID *id)= NULL;
1633
1634 void DAG_editors_update_cb(void (*func)(Main *bmain, ID *id))
1635 {
1636         EditorsUpdateCb= func;
1637 }
1638
1639 static void dag_editors_update(Main *bmain, ID *id)
1640 {
1641         if(EditorsUpdateCb)
1642                 EditorsUpdateCb(bmain, id);
1643 }
1644
1645 /* groups with objects in this scene need to be put in the right order as well */
1646 static void scene_sort_groups(Main *bmain, Scene *sce)
1647 {
1648         Base *base;
1649         Group *group;
1650         GroupObject *go;
1651         Object *ob;
1652         
1653         /* test; are group objects all in this scene? */
1654         for(ob= bmain->object.first; ob; ob= ob->id.next) {
1655                 ob->id.flag &= ~LIB_DOIT;
1656                 ob->id.newid= NULL;     /* newid abuse for GroupObject */
1657         }
1658         for(base = sce->base.first; base; base= base->next)
1659                 base->object->id.flag |= LIB_DOIT;
1660         
1661         for(group= bmain->group.first; group; group= group->id.next) {
1662                 for(go= group->gobject.first; go; go= go->next) {
1663                         if((go->ob->id.flag & LIB_DOIT)==0)
1664                                 break;
1665                 }
1666                 /* this group is entirely in this scene */
1667                 if(go==NULL) {
1668                         ListBase listb= {NULL, NULL};
1669                         
1670                         for(go= group->gobject.first; go; go= go->next)
1671                                 go->ob->id.newid= (ID *)go;
1672                         
1673                         /* in order of sorted bases we reinsert group objects */
1674                         for(base = sce->base.first; base; base= base->next) {
1675                                 
1676                                 if(base->object->id.newid) {
1677                                         go= (GroupObject *)base->object->id.newid;
1678                                         base->object->id.newid= NULL;
1679                                         BLI_remlink( &group->gobject, go);
1680                                         BLI_addtail( &listb, go);
1681                                 }
1682                         }
1683                         /* copy the newly sorted listbase */
1684                         group->gobject= listb;
1685                 }
1686         }
1687 }
1688
1689 /* sort the base list on dependency order */
1690 void DAG_scene_sort(Main *bmain, Scene *sce)
1691 {
1692         DagNode *node;
1693         DagNodeQueue *nqueue;
1694         DagAdjList *itA;
1695         int time;
1696         int skip = 0;
1697         ListBase tempbase;
1698         Base *base;
1699         
1700         tempbase.first= tempbase.last= NULL;
1701         
1702         build_dag(bmain, sce, DAG_RL_ALL_BUT_DATA);
1703         
1704         dag_check_cycle(sce->theDag);
1705
1706         nqueue = queue_create(DAGQUEUEALLOC);
1707         
1708         for(node = sce->theDag->DagNode.first; node; node= node->next) {
1709                 node->color = DAG_WHITE;
1710         }
1711         
1712         time = 1;
1713         
1714         node = sce->theDag->DagNode.first;
1715         
1716         node->color = DAG_GRAY;
1717         time++;
1718         push_stack(nqueue,node);  
1719         
1720         while(nqueue->count) {
1721                 
1722                 skip = 0;
1723                 node = get_top_node_queue(nqueue);
1724                 
1725                 itA = node->child;
1726                 while(itA != NULL) {
1727                         if(itA->node->color == DAG_WHITE) {
1728                                 itA->node->DFS_dvtm = time;
1729                                 itA->node->color = DAG_GRAY;
1730                                 
1731                                 time++;
1732                                 push_stack(nqueue,itA->node);
1733                                 skip = 1;
1734                                 break;
1735                         } 
1736                         itA = itA->next;
1737                 }                       
1738                 
1739                 if (!skip) {
1740                         if (node) {
1741                                 node = pop_queue(nqueue);
1742                                 if (node->ob == sce)    // we are done
1743                                         break ;
1744                                 node->color = DAG_BLACK;
1745                                 
1746                                 time++;
1747                                 base = sce->base.first;
1748                                 while (base && base->object != node->ob)
1749                                         base = base->next;
1750                                 if(base) {
1751                                         BLI_remlink(&sce->base,base);
1752                                         BLI_addhead(&tempbase,base);
1753                                 }
1754                         }       
1755                 }
1756         }
1757         
1758         // temporal correction for circular dependancies
1759         base = sce->base.first;
1760         while (base) {
1761                 BLI_remlink(&sce->base,base);
1762                 BLI_addhead(&tempbase,base);
1763                 //if(G.f & G_DEBUG) 
1764                         printf("cyclic %s\n", base->object->id.name);
1765                 base = sce->base.first;
1766         }
1767         
1768         sce->base = tempbase;
1769         queue_delete(nqueue);
1770         
1771         /* all groups with objects in this scene gets resorted too */
1772         scene_sort_groups(bmain, sce);
1773         
1774         if(G.f & G_DEBUG) {
1775                 printf("\nordered\n");
1776                 for(base = sce->base.first; base; base= base->next) {
1777                         printf(" %s\n", base->object->id.name);
1778                 }
1779         }
1780         /* temporal...? */
1781         sce->recalc |= SCE_PRV_CHANGED; /* test for 3d preview */
1782 }
1783
1784 /* node was checked to have lasttime != curtime and is if type ID_OB */
1785 static void flush_update_node(DagNode *node, unsigned int layer, int curtime)
1786 {
1787         DagAdjList *itA;
1788         Object *ob, *obc;
1789         int oldflag, changed=0;
1790         unsigned int all_layer;
1791         
1792         node->lasttime= curtime;
1793         
1794         ob= node->ob;
1795         if(ob && (ob->recalc & OB_RECALC_ALL)) {
1796                 all_layer= node->scelay;
1797
1798                 /* got an object node that changes, now check relations */
1799                 for(itA = node->child; itA; itA= itA->next) {
1800                         all_layer |= itA->lay;
1801                         /* the relationship is visible */
1802                         if((itA->lay & layer)) { // XXX || (itA->node->ob == obedit)
1803                                 if(itA->node->type==ID_OB) {
1804                                         obc= itA->node->ob;
1805                                         oldflag= obc->recalc;
1806                                         
1807                                         /* got a ob->obc relation, now check if flag needs flush */
1808                                         if(ob->recalc & OB_RECALC_OB) {
1809                                                 if(itA->type & DAG_RL_OB_OB) {
1810                                                         //printf("ob %s changes ob %s\n", ob->id.name, obc->id.name);
1811                                                         obc->recalc |= OB_RECALC_OB;
1812                                                 }
1813                                                 if(itA->type & DAG_RL_OB_DATA) {
1814                                                         //printf("ob %s changes obdata %s\n", ob->id.name, obc->id.name);
1815                                                         obc->recalc |= OB_RECALC_DATA;
1816                                                 }
1817                                         }
1818                                         if(ob->recalc & OB_RECALC_DATA) {
1819                                                 if(itA->type & DAG_RL_DATA_OB) {
1820                                                         //printf("obdata %s changes ob %s\n", ob->id.name, obc->id.name);
1821                                                         obc->recalc |= OB_RECALC_OB;
1822                                                 }
1823                                                 if(itA->type & DAG_RL_DATA_DATA) {
1824                                                         //printf("obdata %s changes obdata %s\n", ob->id.name, obc->id.name);
1825                                                         obc->recalc |= OB_RECALC_DATA;
1826                                                 }
1827                                         }
1828                                         if(oldflag!=obc->recalc) changed= 1;
1829                                 }
1830                         }
1831                 }
1832                 /* even nicer, we can clear recalc flags...  */
1833                 if((all_layer & layer)==0) { // XXX && (ob != obedit)) {
1834                         /* but existing displaylists or derivedmesh should be freed */
1835                         if(ob->recalc & OB_RECALC_DATA)
1836                                 object_free_display(ob);
1837                         
1838                         ob->recalc &= ~OB_RECALC_ALL;
1839                 }
1840         }
1841         
1842         /* check case where child changes and parent forcing obdata to change */
1843         /* should be done regardless if this ob has recalc set */
1844         /* could merge this in with loop above...? (ton) */
1845         for(itA = node->child; itA; itA= itA->next) {
1846                 /* the relationship is visible */
1847                 if((itA->lay & layer)) {                // XXX  || (itA->node->ob == obedit)
1848                         if(itA->node->type==ID_OB) {
1849                                 obc= itA->node->ob;
1850                                 /* child moves */
1851                                 if((obc->recalc & OB_RECALC_ALL)==OB_RECALC_OB) {
1852                                         /* parent has deforming info */
1853                                         if(itA->type & (DAG_RL_OB_DATA|DAG_RL_DATA_DATA)) {
1854                                                 // printf("parent %s changes ob %s\n", ob->id.name, obc->id.name);
1855                                                 obc->recalc |= OB_RECALC_DATA;
1856                                         }
1857                                 }
1858                         }
1859                 }
1860         }
1861         
1862         /* we only go deeper if node not checked or something changed  */
1863         for(itA = node->child; itA; itA= itA->next) {
1864                 if(changed || itA->node->lasttime!=curtime) 
1865                         flush_update_node(itA->node, layer, curtime);
1866         }
1867         
1868 }
1869
1870 /* node was checked to have lasttime != curtime , and is of type ID_OB */
1871 static unsigned int flush_layer_node(Scene *sce, DagNode *node, int curtime)
1872 {
1873         DagAdjList *itA;
1874         
1875         node->lasttime= curtime;
1876         node->lay= node->scelay;
1877         
1878         for(itA = node->child; itA; itA= itA->next) {
1879                 if(itA->node->type==ID_OB) {
1880                         if(itA->node->lasttime!=curtime) {
1881                                 itA->lay= flush_layer_node(sce, itA->node, curtime);  // lay is only set once for each relation
1882                         }
1883                         else itA->lay= itA->node->lay;
1884                         
1885                         node->lay |= itA->lay;
1886                 }
1887         }
1888
1889         return node->lay;
1890 }
1891
1892 /* node was checked to have lasttime != curtime , and is of type ID_OB */
1893 static void flush_pointcache_reset(Scene *scene, DagNode *node, int curtime, int reset)
1894 {
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
1909                                         flush_pointcache_reset(scene, itA->node, curtime, 1);
1910                                 }
1911                                 else
1912                                         flush_pointcache_reset(scene, itA->node, curtime, 0);
1913                         }
1914                 }
1915         }
1916 }
1917
1918 /* flush layer flags to dependencies */
1919 static void dag_scene_flush_layers(Scene *sce, int lay)
1920 {
1921         DagNode *node, *firstnode;
1922         DagAdjList *itA;
1923         Base *base;
1924         int lasttime;
1925
1926         firstnode= sce->theDag->DagNode.first;  // always scene node
1927
1928         for(itA = firstnode->child; itA; itA= itA->next)
1929                 itA->lay= 0;
1930
1931         sce->theDag->time++;    // so we know which nodes were accessed
1932         lasttime= sce->theDag->time;
1933
1934         /* update layer flags in nodes */
1935         for(base= sce->base.first; base; base= base->next) {
1936                 node= dag_get_node(sce->theDag, base->object);
1937                 node->scelay= base->object->lay;
1938         }
1939
1940         /* ensure cameras are set as if they are on a visible layer, because
1941          * they ared still used for rendering or setting the camera view
1942          *
1943          * XXX, this wont work for local view / unlocked camera's */
1944         if(sce->camera) {
1945                 node= dag_get_node(sce->theDag, sce->camera);
1946                 node->scelay |= lay;
1947         }
1948
1949 #ifdef DURIAN_CAMERA_SWITCH
1950         {
1951                 TimeMarker *m;
1952
1953                 for(m= sce->markers.first; m; m= m->next) {
1954                         if(m->camera) {
1955                                 node= dag_get_node(sce->theDag, m->camera);
1956                                 node->scelay |= lay;
1957                         }
1958                 }
1959         }
1960 #endif
1961
1962         /* flush layer nodes to dependencies */
1963         for(itA = firstnode->child; itA; itA= itA->next)
1964                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) 
1965                         flush_layer_node(sce, itA->node, lasttime);
1966 }
1967
1968 static void dag_tag_renderlayers(Scene *sce, unsigned int lay)
1969 {
1970         if(sce->nodetree) {
1971                 bNode *node;
1972                 Base *base;
1973                 unsigned int lay_changed= 0;
1974                 
1975                 for(base= sce->base.first; base; base= base->next)
1976                         if(base->lay & lay)
1977                                 if(base->object->recalc)
1978                                         lay_changed |= base->lay;
1979                         
1980                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
1981                         if(node->id==(ID *)sce) {
1982                                 SceneRenderLayer *srl= BLI_findlink(&sce->r.layers, node->custom1);
1983                                 if(srl && (srl->lay & lay_changed))
1984                                         nodeUpdate(sce->nodetree, node);
1985                         }
1986                 }
1987         }
1988 }
1989
1990 /* flushes all recalc flags in objects down the dependency tree */
1991 void DAG_scene_flush_update(Main *bmain, Scene *sce, unsigned int lay, const short time)
1992 {
1993         DagNode *firstnode;
1994         DagAdjList *itA;
1995         Object *ob;
1996         int lasttime;
1997         
1998         if(sce->theDag==NULL) {
1999                 printf("DAG zero... not allowed to happen!\n");
2000                 DAG_scene_sort(bmain, sce);
2001         }
2002         
2003         firstnode= sce->theDag->DagNode.first;  // always scene node
2004
2005         /* first we flush the layer flags */
2006         dag_scene_flush_layers(sce, lay);
2007
2008         /* then we use the relationships + layer info to flush update events */
2009         sce->theDag->time++;    // so we know which nodes were accessed
2010         lasttime= sce->theDag->time;
2011         for(itA = firstnode->child; itA; itA= itA->next)
2012                 if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)
2013                         flush_update_node(itA->node, lay, lasttime);
2014
2015         /* if update is not due to time change, do pointcache clears */
2016         if(!time) {
2017                 sce->theDag->time++;    // so we know which nodes were accessed
2018                 lasttime= sce->theDag->time;
2019                 for(itA = firstnode->child; itA; itA= itA->next) {
2020                         if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB)  {
2021                                 ob= (Object*)(itA->node->ob);
2022
2023                                 if(ob->recalc & OB_RECALC_ALL) {
2024                                         if(BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH))
2025                                                 ob->recalc |= OB_RECALC_DATA;
2026
2027                                         flush_pointcache_reset(sce, itA->node, lasttime, 1);
2028                                 }
2029                                 else
2030                                         flush_pointcache_reset(sce, itA->node, lasttime, 0);
2031                         }
2032                 }
2033
2034                 /* also all objects which are parented to tracking data should be re-calculated */
2035                 for(ob=bmain->object.first; ob; ob= ob->id.next){
2036                         bConstraint *con;
2037                         for (con = ob->constraints.first; con; con=con->next) {
2038                                 bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2039                                 if(ELEM(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER)) {
2040                                         ob->recalc |= OB_RECALC_OB;
2041                                         break;
2042                                 }
2043                         }
2044                 }
2045         }
2046         
2047         dag_tag_renderlayers(sce, lay);
2048 }
2049
2050 static int object_modifiers_use_time(Object *ob)
2051 {
2052         ModifierData *md;
2053         
2054         /* check if a modifier in modifier stack needs time input */
2055         for (md=ob->modifiers.first; md; md=md->next)
2056                 if (modifier_dependsOnTime(md))
2057                         return 1;
2058         
2059         /* check whether any modifiers are animated */
2060         if (ob->adt) {
2061                 AnimData *adt = ob->adt;
2062                 FCurve *fcu;
2063                 
2064                 /* action - check for F-Curves with paths containing 'modifiers[' */
2065                 if (adt->action) {
2066                         for (fcu = adt->action->curves.first; fcu; fcu = fcu->next) {
2067                                 if (fcu->rna_path && strstr(fcu->rna_path, "modifiers["))
2068                                         return 1;
2069                         }
2070                 }
2071                 
2072                 /* This here allows modifier properties to get driven and still update properly
2073                  *
2074                  * Workaround to get [#26764] (e.g. subsurf levels not updating when animated/driven)
2075                  * working, without the updating problems ([#28525] [#28690] [#28774] [#28777]) caused
2076                  * by the RNA updates cache introduced in r.38649
2077                  */
2078                 for (fcu = adt->drivers.first; fcu; fcu = fcu->next) {
2079                         if (fcu->rna_path && strstr(fcu->rna_path, "modifiers["))
2080                                 return 1;
2081                 }
2082                 
2083                 // XXX: also, should check NLA strips, though for now assume that nobody uses
2084                 // that and we can omit that for performance reasons...
2085         }
2086         
2087         return 0;
2088 }
2089
2090 static short animdata_use_time(AnimData *adt)
2091 {
2092         NlaTrack *nlt;
2093         
2094         if(adt==NULL) return 0;
2095         
2096         /* check action - only if assigned, and it has anim curves */
2097         if (adt->action && adt->action->curves.first)
2098                 return 1;
2099         
2100         /* check NLA tracks + strips */
2101         for (nlt= adt->nla_tracks.first; nlt; nlt= nlt->next) {
2102                 if (nlt->strips.first)
2103                         return 1;
2104         }
2105         
2106         /* If we have drivers, more likely than not, on a frame change
2107          * they'll need updating because their owner changed
2108          * 
2109          * This is kindof a hack to get around a whole host of problems
2110          * involving drivers using non-object datablock data (which the 
2111          * depsgraph currently has no way of representing let alone correctly
2112          * dependency sort+tagging). By doing this, at least we ensure that 
2113          * some commonly attempted drivers (such as scene -> current frame;
2114          * see "Driver updates fail" thread on Bf-committers dated July 2)
2115          * will work correctly, and that other non-object datablocks will have
2116          * their drivers update at least on frame change.
2117          *
2118          * -- Aligorith, July 4 2011
2119          */
2120         if (adt->drivers.first)
2121                 return 1;
2122         
2123         return 0;
2124 }
2125
2126 static void dag_object_time_update_flags(Object *ob)
2127 {
2128         if(ob->constraints.first) {
2129                 bConstraint *con;
2130                 for (con = ob->constraints.first; con; con=con->next) {
2131                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2132                         ListBase targets = {NULL, NULL};
2133                         bConstraintTarget *ct;
2134                         
2135                         if (cti) {
2136                                 /* special case for FollowTrack -- it doesn't use targets to define relations */
2137                                 if(ELEM(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER)) {
2138                                         ob->recalc |= OB_RECALC_OB;
2139                                 }
2140                                 else if (cti->get_constraint_targets) {
2141                                         cti->get_constraint_targets(con, &targets);
2142                                         
2143                                         for (ct= targets.first; ct; ct= ct->next) {
2144                                                 if (ct->tar) {
2145                                                         ob->recalc |= OB_RECALC_OB;
2146                                                         break;
2147                                                 }
2148                                         }
2149                                         
2150                                         if (cti->flush_constraint_targets)
2151                                                 cti->flush_constraint_targets(con, &targets, 1);
2152                                 }
2153                                 
2154                         }
2155                 }
2156         }
2157         
2158         if(ob->parent) {
2159                 /* motion path or bone child */
2160                 if(ob->parent->type==OB_CURVE || ob->parent->type==OB_ARMATURE) ob->recalc |= OB_RECALC_OB;
2161         }
2162         
2163 #if 0 // XXX old animation system
2164         if(ob->nlastrips.first) {
2165                 if(ob->dup_group) {
2166                         bActionStrip *strip;
2167                         /* this case is for groups with nla, whilst nla target has no action or nla */
2168                         for(strip= ob->nlastrips.first; strip; strip= strip->next) {
2169                                 if(strip->object)
2170                                         strip->object->recalc |= OB_RECALC_ALL;
2171                         }
2172                 }
2173         }
2174 #endif // XXX old animation system
2175         
2176         if(animdata_use_time(ob->adt)) {
2177                 ob->recalc |= OB_RECALC_OB;
2178                 ob->adt->recalc |= ADT_RECALC_ANIM;
2179         }
2180         
2181         if((ob->adt) && (ob->type==OB_ARMATURE)) ob->recalc |= OB_RECALC_DATA;
2182         
2183         if(object_modifiers_use_time(ob)) ob->recalc |= OB_RECALC_DATA;
2184         if((ob->pose) && (ob->pose->flag & POSE_CONSTRAINTS_TIMEDEPEND)) ob->recalc |= OB_RECALC_DATA;
2185         
2186         {
2187                 AnimData *adt= BKE_animdata_from_id((ID *)ob->data);
2188                 Mesh *me;
2189                 Curve *cu;
2190                 Lattice *lt;
2191                 
2192                 switch(ob->type) {
2193                         case OB_MESH:
2194                                 me= ob->data;
2195                                 if(me->key) {
2196                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2197                                                 ob->recalc |= OB_RECALC_DATA;
2198                                         }
2199                                 }
2200                                 if(ob->particlesystem.first)
2201                                         ob->recalc |= OB_RECALC_DATA;
2202                                 break;
2203                         case OB_CURVE:
2204                         case OB_SURF:
2205                                 cu= ob->data;
2206                                 if(cu->key) {
2207                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2208                                                 ob->recalc |= OB_RECALC_DATA;
2209                                         }
2210                                 }
2211                                 break;
2212                         case OB_FONT:
2213                                 cu= ob->data;
2214                                 if(cu->nurb.first==NULL && cu->str && cu->vfont)
2215                                         ob->recalc |= OB_RECALC_DATA;
2216                                 break;
2217                         case OB_LATTICE:
2218                                 lt= ob->data;
2219                                 if(lt->key) {
2220                                         if(!(ob->shapeflag & OB_SHAPE_LOCK)) {
2221                                                 ob->recalc |= OB_RECALC_DATA;
2222                                         }
2223                                 }
2224                                         break;
2225                         case OB_MBALL:
2226                                 if(ob->transflag & OB_DUPLI) ob->recalc |= OB_RECALC_DATA;
2227                                 break;
2228                 }
2229                 
2230                 if(animdata_use_time(adt)) {
2231                         ob->recalc |= OB_RECALC_DATA;
2232                         adt->recalc |= ADT_RECALC_ANIM;
2233                 }
2234
2235                 if(ob->particlesystem.first) {
2236                         ParticleSystem *psys= ob->particlesystem.first;
2237
2238                         for(; psys; psys=psys->next) {
2239                                 if(psys_check_enabled(ob, psys)) {
2240                                         ob->recalc |= OB_RECALC_DATA;
2241                                         break;
2242                                 }
2243                         }
2244                 }
2245         }               
2246 }
2247 /* flag all objects that need recalc, for changes in time for example */
2248 /* do_time: make this optional because undo resets objects to their animated locations without this */
2249 void DAG_scene_update_flags(Main *bmain, Scene *scene, unsigned int lay, const short do_time)
2250 {
2251         Base *base;
2252         Object *ob;
2253         Group *group;
2254         GroupObject *go;
2255         Scene *sce_iter;
2256
2257         /* set ob flags where animated systems are */
2258         for(SETLOOPER(scene, sce_iter, base)) {
2259                 ob= base->object;
2260
2261                 if(do_time) {
2262                         /* now if DagNode were part of base, the node->lay could be checked... */
2263                         /* we do all now, since the scene_flush checks layers and clears recalc flags even */
2264                         dag_object_time_update_flags(ob);
2265                 }
2266
2267                 /* handled in next loop */
2268                 if(ob->dup_group)
2269                         ob->dup_group->id.flag |= LIB_DOIT;
2270         }
2271
2272         if(do_time) {
2273                 /* we do groups each once */
2274                 for(group= bmain->group.first; group; group= group->id.next) {
2275                         if(group->id.flag & LIB_DOIT) {
2276                                 for(go= group->gobject.first; go; go= go->next) {
2277                                         dag_object_time_update_flags(go->ob);
2278                                 }
2279                         }
2280                 }
2281         }
2282
2283         for(sce_iter= scene; sce_iter; sce_iter= sce_iter->set)
2284                 DAG_scene_flush_update(bmain, sce_iter, lay, 1);
2285         
2286         if(do_time) {
2287                 /* test: set time flag, to disable baked systems to update */
2288                 for(SETLOOPER(scene, sce_iter, base)) {
2289                         ob= base->object;
2290                         if(ob->recalc)
2291                                 ob->recalc |= OB_RECALC_TIME;
2292                 }
2293
2294                 /* hrmf... an exception to look at once, for invisible camera object we do it over */
2295                 if(scene->camera)
2296                         dag_object_time_update_flags(scene->camera);
2297         }
2298
2299         /* and store the info in groupobject */
2300         for(group= bmain->group.first; group; group= group->id.next) {
2301                 if(group->id.flag & LIB_DOIT) {
2302                         for(go= group->gobject.first; go; go= go->next) {
2303                                 go->recalc= go->ob->recalc;
2304                                 // printf("ob %s recalc %d\n", go->ob->id.name, go->recalc);
2305                         }
2306                         group->id.flag &= ~LIB_DOIT;
2307                 }
2308         }
2309         
2310 }
2311
2312 static void dag_current_scene_layers(Main *bmain, Scene **sce, unsigned int *lay)
2313 {
2314         wmWindowManager *wm;
2315         wmWindow *win;
2316
2317         /* only one scene supported currently, making more scenes work
2318            correctly requires changes beyond just the dependency graph */
2319
2320         *sce= NULL;
2321         *lay= 0;
2322
2323         if((wm= bmain->wm.first)) {
2324                 /* if we have a windowmanager, look into windows */
2325                 for(win=wm->windows.first; win; win=win->next) {
2326                         if(win->screen) {
2327                                 if(!*sce) *sce= win->screen->scene;
2328                                 *lay |= BKE_screen_visible_layers(win->screen, win->screen->scene);
2329                         }
2330                 }
2331         }
2332         else {
2333                 /* if not, use the first sce */
2334                 *sce= bmain->scene.first;
2335                 if(*sce) *lay= (*sce)->lay;
2336
2337                 /* XXX for background mode, we should get the scene
2338                    from somewhere, for the -S option, but it's in
2339                    the context, how to get it here? */
2340         }
2341 }
2342
2343 void DAG_ids_flush_update(Main *bmain, int time)
2344 {
2345         Scene *sce;
2346         unsigned int lay;
2347
2348         dag_current_scene_layers(bmain, &sce, &lay);
2349
2350         if(sce)
2351                 DAG_scene_flush_update(bmain, sce, lay, time);
2352 }
2353
2354 void DAG_on_visible_update(Main *bmain, const short do_time)
2355 {
2356         Scene *scene;
2357         Base *base;
2358         Object *ob;
2359         Group *group;
2360         GroupObject *go;
2361         DagNode *node;
2362         unsigned int lay, oblay;
2363
2364         dag_current_scene_layers(bmain, &scene, &lay);
2365
2366         if(scene && scene->theDag) {
2367                 Scene *sce_iter;
2368                 /* derivedmeshes and displists are not saved to file so need to be
2369                    remade, tag them so they get remade in the scene update loop,
2370                    note armature poses or object matrices are preserved and do not
2371                    require updates, so we skip those */
2372                 dag_scene_flush_layers(scene, lay);
2373
2374                 for(SETLOOPER(scene, sce_iter, base)) {
2375                         ob= base->object;
2376                         node= (sce_iter->theDag)? dag_get_node(sce_iter->theDag, ob): NULL;
2377                         oblay= (node)? node->lay: ob->lay;
2378
2379                         if((oblay & lay) & ~scene->lay_updated) {
2380                                 if(ELEM6(ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2381                                         ob->recalc |= OB_RECALC_DATA;
2382                                 if(ob->dup_group) 
2383                                         ob->dup_group->id.flag |= LIB_DOIT;
2384                         }
2385                 }
2386
2387                 for(group= bmain->group.first; group; group= group->id.next) {
2388                         if(group->id.flag & LIB_DOIT) {
2389                                 for(go= group->gobject.first; go; go= go->next) {
2390                                         if(ELEM6(go->ob->type, OB_MESH, OB_CURVE, OB_SURF, OB_FONT, OB_MBALL, OB_LATTICE))
2391                                                 go->ob->recalc |= OB_RECALC_DATA;
2392                                         if(go->ob->proxy_from)
2393                                                 go->ob->recalc |= OB_RECALC_OB;
2394                                 }
2395                                 
2396                                 group->id.flag &= ~LIB_DOIT;
2397                         }
2398                 }
2399
2400                 /* now tag update flags, to ensure deformers get calculated on redraw */
2401                 DAG_scene_update_flags(bmain, scene, lay, do_time);
2402                 scene->lay_updated |= lay;
2403         }
2404 }
2405
2406 static void dag_id_flush_update__isDependentTexture(void *userData, Object *UNUSED(ob), ID **idpoin)
2407 {
2408         struct { ID *id; int is_dependent; } *data = userData;
2409         
2410         if(*idpoin && GS((*idpoin)->name)==ID_TE) {
2411                 if (data->id == (*idpoin))
2412                         data->is_dependent = 1;
2413         }
2414 }
2415
2416 static void dag_id_flush_update(Scene *sce, ID *id)
2417 {
2418         Main *bmain= G.main;
2419         Object *obt, *ob= NULL;
2420         short idtype;
2421
2422         /* here we flush a few things before actual scene wide flush, mostly
2423            due to only objects and not other datablocks being in the depsgraph */
2424
2425         /* set flags & pointcache for object */
2426         if(GS(id->name) == ID_OB) {
2427                 ob= (Object*)id;
2428                 BKE_ptcache_object_reset(sce, ob, PTCACHE_RESET_DEPSGRAPH);
2429
2430                 if(ob->recalc & OB_RECALC_DATA) {
2431                         /* all users of this ob->data should be checked */
2432                         id= ob->data;
2433
2434                         /* no point in trying in this cases */
2435                         if(id && id->us <= 1) {
2436                                 dag_editors_update(bmain, id);
2437                                 id= NULL;
2438                         }
2439                 }
2440         }
2441
2442         /* set flags & pointcache for object data */
2443         if(id) {
2444                 idtype= GS(id->name);
2445
2446                 if(ELEM8(idtype, ID_ME, ID_CU, ID_MB, ID_LA, ID_LT, ID_CA, ID_AR, ID_SPK)) {
2447                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2448                                 if(!(ob && obt == ob) && obt->data == id) {
2449                                         obt->recalc |= OB_RECALC_DATA;
2450                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2451                                 }
2452                         }
2453                 }
2454                 
2455                 /* set flags based on textures - can influence depgraph via modifiers */
2456                 if(idtype == ID_TE) {
2457                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2458                                 struct { ID *id; int is_dependent; } data;
2459                                 data.id= id;
2460                                 data.is_dependent= 0;
2461
2462                                 modifiers_foreachIDLink(obt, dag_id_flush_update__isDependentTexture, &data);
2463                                 if (data.is_dependent)
2464                                         obt->recalc |= OB_RECALC_DATA;
2465
2466                                 /* particle settings can use the texture as well */
2467                                 if(obt->particlesystem.first) {
2468                                         ParticleSystem *psys = obt->particlesystem.first;
2469                                         MTex **mtexp, *mtex;
2470                                         int a;
2471                                         for(; psys; psys=psys->next) {
2472                                                 mtexp = psys->part->mtex;
2473                                                 for(a=0; a<MAX_MTEX; a++, mtexp++) {
2474                                                         mtex = *mtexp;
2475                                                         if(mtex && mtex->tex == (Tex*)id) {
2476                                                                 obt->recalc |= OB_RECALC_DATA;
2477                                                                 
2478                                                                 if(mtex->mapto & PAMAP_INIT)
2479                                                                         psys->recalc |= PSYS_RECALC_RESET;
2480                                                                 if(mtex->mapto & PAMAP_CHILD)
2481                                                                         psys->recalc |= PSYS_RECALC_CHILD;
2482
2483                                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2484                                                         }
2485                                                 }
2486                                         }
2487                                 }
2488                         }
2489                 }
2490                 
2491                 /* set flags based on ShapeKey */
2492                 if(idtype == ID_KE) {
2493                         for(obt=bmain->object.first; obt; obt= obt->id.next) {
2494                                 Key *key= ob_get_key(obt);
2495                                 if(!(ob && obt == ob) && ((ID *)key == id)) {
2496                                         obt->flag |= (OB_RECALC_OB|OB_RECALC_DATA);
2497                                         BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2498                                 }
2499                         }
2500                 }
2501                 
2502                 /* set flags based on particle settings */
2503                 if(idtype == ID_PA) {
2504                         ParticleSystem *psys;
2505                         for(obt=bmain->object.first; obt; obt= obt->id.next)
2506                                 for(psys=obt->particlesystem.first; psys; psys=psys->next)
2507                                         if(&psys->part->id == id)
2508                                                 BKE_ptcache_object_reset(sce, obt, PTCACHE_RESET_DEPSGRAPH);
2509                 }
2510
2511                 if(idtype == ID_MC) {
2512                         for(obt=bmain->object.first; obt; obt= obt->id.next){
2513                                 bConstraint *con;
2514                                 for (con = obt->constraints.first; con; con=con->next) {
2515                                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2516                                         if(ELEM(cti->type, CONSTRAINT_TYPE_FOLLOWTRACK, CONSTRAINT_TYPE_CAMERASOLVER)) {
2517                                                 obt->recalc |= OB_RECALC_OB;
2518                                                 break;
2519                                         }
2520                                 }
2521                         }
2522
2523                         if(sce->nodetree) {
2524                                 bNode *node;
2525
2526                                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
2527                                         if(node->id==id) {
2528                                                 nodeUpdate(sce->nodetree, node);
2529                                         }
2530                                 }
2531                         }
2532                 }
2533
2534                 /* camera's matrix is used to orient reconstructed stuff,
2535                    so it should happen tracking-related constraints recalculation
2536                    when camera is changing */
2537                 if(sce->camera && &sce->camera->id == id && sce->clip) {
2538                         dag_id_flush_update(sce, &sce->clip->id);
2539                 }
2540
2541                 /* update editors */
2542                 dag_editors_update(bmain, id);
2543         }
2544 }
2545
2546 void DAG_ids_flush_tagged(Main *bmain)
2547 {
2548         ListBase *lbarray[MAX_LIBARRAY];
2549         Scene *sce;
2550         unsigned int lay;
2551         int a, have_tag = 0;
2552
2553         dag_current_scene_layers(bmain, &sce, &lay);
2554
2555         if(!sce || !sce->theDag)
2556                 return;
2557
2558         /* loop over all ID types */
2559         a  = set_listbasepointers(bmain, lbarray);
2560
2561         while(a--) {
2562                 ListBase *lb = lbarray[a];
2563                 ID *id = lb->first;
2564
2565                 /* we tag based on first ID type character to avoid 
2566                    looping over all ID's in case there are no tags */
2567                 if(id && bmain->id_tag_update[id->name[0]]) {
2568                         for(; id; id=id->next) {
2569                                 if(id->flag & LIB_ID_RECALC) {
2570                                         dag_id_flush_update(sce, id);
2571                                         id->flag &= ~LIB_ID_RECALC;
2572                                 }
2573                         }
2574
2575                         have_tag = 1;
2576                 }
2577         }
2578
2579         if(have_tag) {
2580                 /* clear tags */
2581                 memset(bmain->id_tag_update, 0, sizeof(bmain->id_tag_update));
2582
2583                 /* flush changes to other objects */
2584                 DAG_scene_flush_update(bmain, sce, lay, 0);
2585         }
2586 }
2587
2588 void DAG_id_tag_update(ID *id, short flag)
2589 {
2590         Main *bmain= G.main;
2591
2592         if(id==NULL) return;
2593         
2594         /* tag ID for update */
2595         id->flag |= LIB_ID_RECALC;
2596         bmain->id_tag_update[id->name[0]] = 1;
2597
2598         /* flag is for objects and particle systems */
2599         if(flag) {
2600                 Object *ob;
2601                 ParticleSystem *psys;
2602                 short idtype = GS(id->name);
2603
2604                 if(idtype == ID_OB) {
2605                         /* only quick tag */
2606                         ob = (Object*)id;
2607                         ob->recalc |= (flag & OB_RECALC_ALL);
2608                 }
2609                 else if(idtype == ID_PA) {
2610                         /* this is weak still, should be done delayed as well */
2611                         for(ob=bmain->object.first; ob; ob=ob->id.next) {
2612                                 for(psys=ob->particlesystem.first; psys; psys=psys->next) {
2613                                         if(&psys->part->id == id) {
2614                                                 ob->recalc |= (flag & OB_RECALC_ALL);
2615                                                 psys->recalc |= (flag & PSYS_RECALC);
2616                                         }
2617                                 }
2618                         }
2619                 }
2620                 else {
2621                         /* disable because this is called on various ID types automatically.
2622                          * where printing warning is not useful. for now just ignore */
2623                         /* BLI_assert(!"invalid flag for this 'idtype'"); */
2624                 }
2625         }
2626 }
2627
2628 #if 0 // UNUSED
2629 /* recursively descends tree, each node only checked once */
2630 /* node is checked to be of type object */
2631 static int parent_check_node(DagNode *node, int curtime)
2632 {
2633         DagAdjList *itA;
2634         
2635         node->lasttime= curtime;
2636         
2637         if(node->color==DAG_GRAY)
2638                 return DAG_GRAY;
2639         
2640         for(itA = node->child; itA; itA= itA->next) {
2641                 if(itA->node->type==ID_OB) {
2642                         
2643                         if(itA->node->color==DAG_GRAY)
2644                                 return DAG_GRAY;
2645
2646                         /* descend if not done */
2647                         if(itA->node->lasttime!=curtime) {
2648                                 itA->node->color= parent_check_node(itA->node, curtime);
2649                         
2650                                 if(itA->node->color==DAG_GRAY)
2651                                         return DAG_GRAY;
2652                         }
2653                 }
2654         }
2655         
2656         return DAG_WHITE;
2657 }
2658 #endif
2659
2660 /* ******************* DAG FOR ARMATURE POSE ***************** */
2661
2662 /* we assume its an armature with pose */
2663 void DAG_pose_sort(Object *ob)
2664 {
2665         bPose *pose= ob->pose;
2666         bPoseChannel *pchan;
2667         bConstraint *con;
2668         DagNode *node;
2669         DagNode *node2, *node3;
2670         DagNode *rootnode;
2671         DagForest *dag;
2672         DagNodeQueue *nqueue;
2673         DagAdjList *itA;
2674         ListBase tempbase;
2675         int skip = 0;
2676         
2677         dag = dag_init();
2678         ugly_hack_sorry= 0;     // no ID structs
2679
2680         rootnode = dag_add_node(dag, NULL);     // node->ob becomes NULL
2681         
2682         /* we add the hierarchy and the constraints */
2683         for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
2684                 int addtoroot = 1;
2685                 
2686                 node = dag_get_node(dag, pchan);
2687                 
2688                 if(pchan->parent) {
2689                         node2 = dag_get_node(dag, pchan->parent);
2690                         dag_add_relation(dag, node2, node, 0, "Parent Relation");
2691                         addtoroot = 0;
2692                 }
2693                 for (con = pchan->constraints.first; con; con=con->next) {
2694                         bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
2695                         ListBase targets = {NULL, NULL};
2696                         bConstraintTarget *ct;
2697                         
2698                         if (cti && cti->get_constraint_targets) {
2699                                 cti->get_constraint_targets(con, &targets);
2700                                 
2701                                 for (ct= targets.first; ct; ct= ct->next) {
2702                                         if (ct->tar==ob && ct->subtarget[0]) {
2703                                                 bPoseChannel *target= get_pose_channel(ob->pose, ct->subtarget);
2704                                                 if (target) {
2705                                                         node2= dag_get_node(dag, target);
2706                                                         dag_add_relation(dag, node2, node, 0, "Pose Constraint");
2707                                                         
2708                                                         if (con->type==CONSTRAINT_TYPE_KINEMATIC) {
2709                                                                 bKinematicConstraint *data = (bKinematicConstraint *)con->data;
2710                                                                 bPoseChannel *parchan;
2711                                                                 int segcount= 0;
2712                                                                 
2713                                                                 /* exclude tip from chain? */
2714                                                                 if(!(data->flag & CONSTRAINT_IK_TIP))
2715                                                                         parchan= pchan->parent;
2716                                                                 else
2717                                                                         parchan= pchan;
2718                                                                 
2719                                                                 /* Walk to the chain's root */
2720                                                                 while (parchan) {
2721                                                                         node3= dag_get_node(dag, parchan);
2722                                                                         dag_add_relation(dag, node2, node3, 0, "IK Constraint");
2723                                                                         
2724                                                                         segcount++;
2725                                                                         if (segcount==data->rootbone || segcount>255) break; // 255 is weak
2726                                                                         parchan= parchan->parent;
2727                                                                 }
2728                                                         }
2729                                                 }
2730                                         }
2731                                 }
2732                                 
2733                                 if (cti->flush_constraint_targets)
2734                                         cti->flush_constraint_targets(con, &targets, 1);
2735                         }
2736                 }
2737                 if (addtoroot == 1 ) {
2738                         dag_add_relation(dag, rootnode, node, 0, "Root Bone Relation");
2739                 }
2740         }
2741
2742         dag_check_cycle(dag);
2743         
2744         /* now we try to sort... */
2745         tempbase.first= tempbase.last= NULL;
2746
2747         nqueue = queue_create(DAGQUEUEALLOC);
2748         
2749         /* tag nodes unchecked */
2750         for(node = dag->DagNode.first; node; node= node->next) 
2751                 node->color = DAG_WHITE;
2752         
2753         node = dag->DagNode.first;
2754         
2755         node->color = DAG_GRAY;
2756         push_stack(nqueue, node);  
2757         
2758         while(nqueue->count) {
2759                 
2760                 skip = 0;
2761                 node = get_top_node_queue(nqueue);
2762                 
2763                 itA = node->child;
2764                 while(itA != NULL) {
2765                         if(itA->node->color == DAG_WHITE) {
2766                                 itA->node->color = DAG_GRAY;
2767                                 push_stack(nqueue,itA->node);
2768                                 skip = 1;
2769                                 break;
2770                         } 
2771                         itA = itA->next;
2772                 }                       
2773                 
2774                 if (!skip) {
2775                         if (node) {
2776                                 node = pop_queue(nqueue);
2777                                 if (node->ob == NULL)   // we are done
2778                                         break ;
2779                                 node->color = DAG_BLACK;
2780                                 
2781                                 /* put node in new list */
2782                                 BLI_remlink(&pose->chanbase, node->ob);
2783                                 BLI_addhead(&tempbase, node->ob);
2784                         }       
2785                 }
2786         }
2787         
2788         // temporal correction for circular dependancies
2789         while(pose->chanbase.first) {
2790                 pchan= pose->chanbase.first;
2791                 BLI_remlink(&pose->chanbase, pchan);
2792                 BLI_addhead(&tempbase, pchan);
2793
2794                 printf("cyclic %s\n", pchan->name);
2795         }
2796         
2797         pose->chanbase = tempbase;
2798         queue_delete(nqueue);
2799         
2800 //      printf("\nordered\n");
2801 //      for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
2802 //              printf(" %s\n", pchan->name);
2803 //      }
2804         
2805         free_forest( dag );
2806         MEM_freeN( dag );
2807         
2808         ugly_hack_sorry= 1;
2809 }
2810
2811
2812