source/blender/blenkernel/intern/depsgraph.c

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