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