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