Dependency graph patch, provided by Jean-Luc Peuriere.
authorTon Roosendaal <ton@blender.org>
Sat, 30 Apr 2005 21:27:05 +0000 (21:27 +0000)
committerTon Roosendaal <ton@blender.org>
Sat, 30 Apr 2005 21:27:05 +0000 (21:27 +0000)
Works like a charm... well it now replaces the old base-sorting hack. :)
Next stage will be to define how to further integrate it. Plus some
minor code cleanups... static/internal functions versus external, etc.

13 files changed:
source/blender/blenkernel/BKE_depsgraph.h [new file with mode: 0644]
source/blender/blenkernel/SConscript
source/blender/blenkernel/depsgraph_private.h [new file with mode: 0644]
source/blender/blenkernel/intern/depsgraph.c [new file with mode: 0644]
source/blender/blenkernel/intern/scene.c
source/blender/blenloader/intern/readfile.c
source/blender/makesdna/DNA_scene_types.h
source/blender/makesdna/DNA_space_types.h
source/blender/src/SConscript
source/blender/src/drawdeps.c [new file with mode: 0644]
source/blender/src/drawoops.c
source/blender/src/header_oops.c
source/blender/src/space.c

diff --git a/source/blender/blenkernel/BKE_depsgraph.h b/source/blender/blenkernel/BKE_depsgraph.h
new file mode 100644 (file)
index 0000000..007b38b
--- /dev/null
@@ -0,0 +1,103 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2004 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+
+#ifndef DEPSGRAPH_API
+#define DEPSGRAPH_API
+
+/*
+#define DEPS_DEBUG
+*/
+
+struct Scene;
+struct DagNodeQueue;
+struct DagForest;
+struct DagNode;
+
+typedef enum { 
+       DAG_RL_SCENE                            = 1,
+       DAG_RL_DATA                                     = 2,
+       DAG_RL_PARENT                           = 4,
+       DAG_RL_TRACK                            = 8,
+       DAG_RL_PATH                                     = 16,
+       DAG_RL_CONSTRAINT                       = 32,
+       DAG_RL_HOOK                                     = 64,
+       DAG_RL_DATA_CONSTRAINT          = 128,
+       DAG_NO_RELATION                         = 256
+} dag_rel_type;
+
+
+typedef enum {
+       DAG_RL_SCENE_MASK                       = 1,
+       DAG_RL_DATA_MASK                        = 2,
+       DAG_RL_PARENT_MASK                      = 4,
+       DAG_RL_TRACK_MASK                       = 8,
+       DAG_RL_PATH_MASK                        = 16,
+       DAG_RL_CONSTRAINT_MASK          = 32,
+       DAG_RL_HOOK_MASK                        = 64,
+       DAG_RL_DATA_CONSTRAINT_MASK     = 128,
+       DAG_RL_ALL_BUT_DATA_MASK        = 253,
+       DAG_RL_ALL_MASK                         = 255
+} dag_rel_type_mask;
+
+typedef void (*graph_action_func)(void * ob, void **data);
+
+// queues are returned by all BFS & DFS queries
+// opaque type
+void   *pop_ob_queue(struct DagNodeQueue *queue);
+int            queue_count(struct DagNodeQueue *queue);
+void   queue_delete(struct DagNodeQueue *queue);
+
+// queries
+struct DagForest       *build_dag(struct Scene *sce, short mask);
+void                           free_forest(struct DagForest *Dag);
+
+// note :
+// the meanings of the 2 returning values is a bit different :
+// BFS return 1 for cross-edges and back-edges. the latter are considered harmfull, not the former
+// DFS return 1 only for back-edges
+int pre_and_post_BFS(struct DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data);
+int pre_and_post_DFS(struct DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data);
+
+int pre_and_post_source_BFS(struct DagForest *dag, short mask, struct DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data);
+int pre_and_post_source_DFS(struct DagForest *dag, short mask, struct DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data);
+
+struct DagNodeQueue *get_obparents(struct DagForest    *dag, void *ob); 
+struct DagNodeQueue *get_first_ancestors(struct DagForest      *dag, void *ob); 
+struct DagNodeQueue *get_all_childs(struct DagForest   *dag, void *ob); //
+dag_rel_type           are_obs_related(struct DagForest        *dag, void *ob1, void *ob2);
+int                                    is_acyclic(struct DagForest     *dag); //
+//int                                  get_cycles(struct DagForest     *dag, struct DagNodeQueue **queues, int *count); //
+void                           topo_sort_baselist(struct Scene *sce);
+
+void   boundbox_deps(void);
+void   draw_all_deps(void);
+
+
+#endif
\ No newline at end of file
index 3ab7dc385c7d19da9813f1f8d95643807a3233d6..0b6bf520bc4829c76f7e128d19e1500ff461c185 100644 (file)
@@ -5,6 +5,7 @@ Import ('library_env')
 blenkernel_env = library_env.Copy ()
 
 source_files = ['intern/constraint.c',
+               'intern/depsgraph.c',
                 'intern/DerivedMesh.c',
                 'intern/group.c',
                 'intern/material.c',
diff --git a/source/blender/blenkernel/depsgraph_private.h b/source/blender/blenkernel/depsgraph_private.h
new file mode 100644 (file)
index 0000000..7b3da76
--- /dev/null
@@ -0,0 +1,129 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2004 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+#ifndef DEPSGRAPH_PRIVATE
+#define DEPSGRAPH_PRIVATE
+
+#include "BKE_depsgraph.h"
+#include "DNA_constraint_types.h"
+#include "BKE_constraint.h"
+
+
+#define DEPSX  5.0
+#define DEPSY  1.8
+
+#define DAGQUEUEALLOC 50
+
+enum {
+       DAG_WHITE = 0,
+       DAG_GRAY = 1,
+       DAG_BLACK = 2
+};
+
+
+
+typedef struct DagAdjList
+{
+       struct DagNode *node;
+       dag_rel_type type;
+       int count; // number of identical arcs
+       struct DagAdjList *next;
+} DagAdjList;
+
+
+typedef struct DagNode 
+{
+       int color;
+       short type;
+       float x, y, k;  
+       void * ob;
+       void * first_ancestor;
+       int             ancestor_count;
+       int BFS_dist;           // BFS distance
+       int DFS_dist;           // DFS distance
+       int DFS_dvtm;           // DFS discovery time
+       int DFS_fntm;           // DFS Finishing time
+       struct DagAdjList *child;
+       struct DagNode *next;
+} DagNode;
+
+typedef struct DagNodeQueueElem {
+       struct DagNode *node;
+       struct DagNodeQueueElem *next;
+} DagNodeQueueElem;
+
+typedef struct DagNodeQueue
+{
+       DagNodeQueueElem *first;
+       DagNodeQueueElem *last;
+       int count;
+       int maxlevel;
+       struct DagNodeQueue *freenodes;
+} DagNodeQueue;
+
+// forest as we may have more than one DAG unnconected
+typedef struct DagForest 
+{
+       ListBase DagNode;
+       int numNodes;
+       int is_acyclic;
+} DagForest;
+
+
+// queue operations
+DagNodeQueue * queue_create (int slots);
+void queue_raz(DagNodeQueue *queue);
+void push_queue(DagNodeQueue *queue, DagNode *node);
+void push_stack(DagNodeQueue *queue, DagNode *node);
+DagNode * pop_queue(DagNodeQueue *queue);
+DagNode * get_top_node_queue(DagNodeQueue *queue);
+
+// Dag management
+DagForest *getMainDag(void);
+void setMainDag(DagForest *dag);
+DagForest * dag_init(void);
+DagNode * dag_find_node (DagForest *forest,void * fob);
+DagNode * dag_add_node (DagForest *forest,void * fob);
+DagNode * dag_get_node (DagForest *forest,void * fob);
+DagNode * dag_get_sub_node (DagForest *forest,void * fob);
+void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, dag_rel_type rel);
+
+void graph_bfs(void);
+
+DagNodeQueue * graph_dfs(void);
+
+void set_node_xy(DagNode *node, float x, float y);
+void graph_print_queue(DagNodeQueue *nqueue);
+void graph_print_queue_dist(DagNodeQueue *nqueue);
+void graph_print_adj_list(void);
+
+int build_deps(short mask);
+
+#endif
\ No newline at end of file
diff --git a/source/blender/blenkernel/intern/depsgraph.c b/source/blender/blenkernel/intern/depsgraph.c
new file mode 100644 (file)
index 0000000..7ae3f39
--- /dev/null
@@ -0,0 +1,1206 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2004 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+
+#ifdef _WIN32
+#include "BLI_winstuff.h"
+#endif
+
+//#include "BMF_Api.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_arithb.h"
+
+#include "DNA_ID.h"
+#include "DNA_object_types.h"
+#include "DNA_oops_types.h"
+#include "DNA_scene_types.h"
+#include "DNA_action_types.h"
+#include "DNA_screen_types.h"
+#include "DNA_space_types.h"
+#include "DNA_view2d_types.h"
+
+#include "BKE_utildefines.h"
+#include "BKE_global.h"
+
+#include "MEM_guardedalloc.h"
+#include "blendef.h"
+
+ #include "depsgraph_private.h"
+/* Queue and stack operations for dag traversal 
+ *
+ * the queue store a list of freenodes to avoid successives alloc/dealloc
+ */
+
+DagNodeQueue * queue_create (int slots) 
+{
+       DagNodeQueue * queue;
+       DagNodeQueueElem * elem;
+       int i;
+       
+       queue = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
+       queue->freenodes = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
+       queue->count = 0;
+       queue->maxlevel = 0;
+       queue->first = queue->last = NULL;
+       elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem3");
+       elem->node = NULL;
+       elem->next = NULL;
+       queue->freenodes->first = queue->freenodes->last = elem;
+       
+       for (i = 1; i <slots;i++) {
+               elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem4");
+               elem->node = NULL;
+               elem->next = NULL;
+               queue->freenodes->last->next = elem;
+               queue->freenodes->last = elem;
+       }
+       queue->freenodes->count = slots;
+       return queue;
+}
+
+void queue_raz(DagNodeQueue *queue)
+{
+       DagNodeQueueElem * elem;
+       
+       elem = queue->first;
+       if (queue->freenodes->last)
+               queue->freenodes->last->next = elem;
+       else
+               queue->freenodes->first = queue->freenodes->last = elem;
+       
+       elem->node = NULL;
+       queue->freenodes->count++;
+       while (elem->next) {
+               elem = elem->next;
+               elem->node = NULL;
+               queue->freenodes->count++;
+       }
+       queue->freenodes->last = elem;
+       queue->count = 0;
+}
+
+void queue_delete(DagNodeQueue *queue)
+{
+       DagNodeQueueElem * elem;
+       DagNodeQueueElem * temp;
+       
+       elem = queue->first;
+       while (elem) {
+               temp = elem;
+               elem = elem->next;
+               MEM_freeN(temp);
+       }
+       
+       elem = queue->freenodes->first;
+       while (elem) {
+               temp = elem;
+               elem = elem->next;
+               MEM_freeN(temp);
+       }
+       
+       MEM_freeN(queue->freenodes);                    
+       MEM_freeN(queue);                       
+}
+
+/* insert in queue, remove in front */
+void push_queue(DagNodeQueue *queue, DagNode *node)
+{
+       DagNodeQueueElem * elem;
+       int i;
+
+       if (node == NULL) {
+               fprintf(stderr,"pushing null node \n");
+               return;
+       }
+       /*fprintf(stderr,"BFS push : %s %d\n",((ID *) node->ob)->name, queue->count);*/
+
+       elem = queue->freenodes->first;
+       if (elem != NULL) {
+               queue->freenodes->first = elem->next;
+               if ( queue->freenodes->last == elem) {
+                       queue->freenodes->last = NULL;
+                       queue->freenodes->first = NULL;
+               }
+               queue->freenodes->count--;
+       } else { /* alllocating more */         
+               elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
+               elem->node = NULL;
+               elem->next = NULL;
+               queue->freenodes->first = queue->freenodes->last = elem;
+
+               for (i = 1; i <DAGQUEUEALLOC;i++) {
+                       elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
+                       elem->node = NULL;
+                       elem->next = NULL;
+                       queue->freenodes->last->next = elem;
+                       queue->freenodes->last = elem;
+               }
+               queue->freenodes->count = DAGQUEUEALLOC;
+                       
+               elem = queue->freenodes->first; 
+               queue->freenodes->first = elem->next;   
+       }
+       elem->next = NULL;
+       elem->node = node;
+       if (queue->last != NULL)
+               queue->last->next = elem;
+       queue->last = elem;
+       if (queue->first == NULL) {
+               queue->first = elem;
+       }
+       queue->count++;
+}
+
+
+/* insert in front, remove in front */
+void push_stack(DagNodeQueue *queue, DagNode *node)
+{
+       DagNodeQueueElem * elem;
+       int i;
+
+       elem = queue->freenodes->first; 
+       if (elem != NULL) {
+               queue->freenodes->first = elem->next;
+               if ( queue->freenodes->last == elem) {
+                       queue->freenodes->last = NULL;
+                       queue->freenodes->first = NULL;
+               }
+               queue->freenodes->count--;
+       } else { /* alllocating more */
+               elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
+               elem->node = NULL;
+               elem->next = NULL;
+               queue->freenodes->first = queue->freenodes->last = elem;
+
+               for (i = 1; i <DAGQUEUEALLOC;i++) {
+                       elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
+                       elem->node = NULL;
+                       elem->next = NULL;
+                       queue->freenodes->last->next = elem;
+                       queue->freenodes->last = elem;
+               }
+               queue->freenodes->count = DAGQUEUEALLOC;
+                       
+               elem = queue->freenodes->first; 
+               queue->freenodes->first = elem->next;   
+       }
+       elem->next = queue->first;
+       elem->node = node;
+       queue->first = elem;
+       if (queue->last == NULL)
+               queue->last = elem;
+       queue->count++;
+}
+
+
+DagNode * pop_queue(DagNodeQueue *queue)
+{
+       DagNodeQueueElem * elem;
+       DagNode *node;
+
+       elem = queue->first;
+       if (elem) {
+               queue->first = elem->next;
+               if (queue->last == elem) {
+                       queue->last=NULL;
+                       queue->first=NULL;
+               }
+               queue->count--;
+               if (queue->freenodes->last)
+                       queue->freenodes->last->next=elem;
+               queue->freenodes->last=elem;
+               if (queue->freenodes->first == NULL)
+                       queue->freenodes->first=elem;
+               node = elem->node;
+               elem->node = NULL;
+               elem->next = NULL;
+               queue->freenodes->count++;
+               return node;
+       } else {
+               fprintf(stderr,"return null \n");
+               return NULL;
+       }
+}
+
+void   *pop_ob_queue(struct DagNodeQueue *queue) {
+       return(pop_queue(queue)->ob);
+}
+
+DagNode * get_top_node_queue(DagNodeQueue *queue) 
+{
+       return queue->first->node;
+}
+
+int            queue_count(struct DagNodeQueue *queue){
+       return queue->count;
+}
+
+
+DagForest * dag_init()
+{
+       DagForest *forest;
+       
+       forest = MEM_mallocN(sizeof(DagForest),"DAG root");
+       forest->DagNode.first = NULL;
+       forest->DagNode.last = NULL;
+       forest->numNodes = 0;
+       return forest;
+}
+
+struct DagForest       *build_dag(struct Scene *sce, short mask) 
+{
+       Base *base;
+       Object *ob;
+       DagNode * node;
+       DagNode * node2;
+       DagNode * node3;
+       DagNode * scenenode;
+       DagForest *dag;
+
+       dag = sce->theDag;
+       sce->dagisvalid=1;
+       if ( dag)
+               free_forest( dag ); 
+       else {
+               dag = dag_init();
+               sce->theDag = dag;
+       }
+       
+       // add base node for scene. scene is always the first node in DAG
+       scenenode = dag_add_node(dag, sce);     
+       
+       /* targets in object struct yet to be added. should even they ?
+               struct Ipo *ipo;
+       ListBase nlastrips;
+       ListBase hooks;
+       */
+       
+       
+       base = sce->base.first;
+       while(base) { // add all objects in any case
+               int addtoroot = 1;
+               ob= (Object *) base->object;
+               
+               node = dag_get_node(dag,ob);
+               
+               if ((ob->data) && (mask&DAG_RL_DATA_MASK)) {
+                       node2 = dag_get_node(dag,ob->data);
+                       dag_add_relation(dag,node,node2,DAG_RL_DATA);
+                       node2->first_ancestor = ob;
+                       node2->ancestor_count += 1;
+                       
+                       if ((ob->type == OB_ARMATURE) && (mask&DAG_RL_DATA_CONSTRAINT_MASK)) { // add armature constraints to datas
+                               if (ob->pose){
+                                       bPoseChannel *pchan;
+                                       bConstraint *con;
+                                       Object * target;
+                                       
+                                       for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){
+                                               for (con = pchan->constraints.first; con; con=con->next){
+                                                       if (constraint_has_target(con)) {
+                                                               target = get_constraint_target(con);
+                                                               if (strcmp(target->id.name, ob->id.name) != 0) {
+                                                                       //fprintf(stderr,"armature target :%s \n", target->id.name);
+                                                                       node3 = dag_get_node(dag,target);
+                                                                       dag_add_relation(dag,node3,node2,DAG_RL_CONSTRAINT);
+                                                               }
+                                                       }
+                                               }
+                                       }
+                               }
+                       }
+                       
+                       if ((ob->hooks.first) && (mask&DAG_RL_HOOK)) {
+                               ObHook *hook;
+                               
+                               for(hook= ob->hooks.first; hook; hook= hook->next) {
+                                       if(hook->parent) {
+                                               node3 = dag_get_node(dag,hook->parent);
+                                               dag_add_relation(dag,node3,node2,DAG_RL_HOOK);
+                                       }
+                               }
+                       }
+               } else { // add armature constraints to object itself
+                       if ((ob->type == OB_ARMATURE) && (mask&DAG_RL_DATA_CONSTRAINT_MASK)) {
+                               if (ob->pose){
+                                       bPoseChannel *pchan;
+                                       bConstraint *con;
+                                       Object * target;
+                                       
+                                       for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){
+                                               for (con = pchan->constraints.first; con; con=con->next){
+                                                       if (constraint_has_target(con)) {
+                                                               target = get_constraint_target(con);
+                                                               if (strcmp(target->id.name, ob->id.name) != 0) {
+                                                                       //fprintf(stderr,"armature target :%s \n", target->id.name);
+                                                                       node3 = dag_get_node(dag,target);
+                                                                       dag_add_relation(dag,node3,node,DAG_RL_CONSTRAINT);
+                                                               }
+                                                       }
+                                               }
+                                       }
+                               }
+                       }
+                       if ((ob->hooks.first)  && (mask&DAG_RL_HOOK)) {
+                               ObHook *hook;
+                               
+                               for(hook= ob->hooks.first; hook; hook= hook->next) {
+                                       if(hook->parent) {
+                                               node3 = dag_get_node(dag,hook->parent);
+                                               dag_add_relation(dag,node3,node,DAG_RL_HOOK);
+                                       }
+                               }
+                       }                       
+               }
+               
+               if ((ob->parent) && (mask&DAG_RL_PARENT_MASK)){
+                       node2 = dag_get_node(dag,ob->parent);
+                       dag_add_relation(dag,node2,node,DAG_RL_PARENT);
+                       addtoroot = 0;
+               }
+               if ((ob->track) && (mask&DAG_RL_TRACK_MASK)){
+                       node2 = dag_get_node(dag,ob->track);
+                       dag_add_relation(dag,node2,node,DAG_RL_TRACK);
+                       addtoroot = 0;
+                       
+               }
+               if ((ob->path) && (mask&DAG_RL_PATH_MASK)){
+                       node2 = dag_get_node(dag,ob->track);
+                       dag_add_relation(dag,node2,node,DAG_RL_PATH);
+                       addtoroot = 0;
+                       
+               }
+               
+               /* Count constraints */
+               if (mask & DAG_RL_CONSTRAINT_MASK) {
+                       bConstraint *con;
+                       for (con = ob->constraints.first; con; con=con->next){
+                               if (constraint_has_target(con)) {
+                                       node2 = dag_get_node(dag,get_constraint_target(con));
+                                       dag_add_relation(dag,node2,node,DAG_RL_CONSTRAINT);
+                                       addtoroot = 0;
+                                       
+                               }
+                       }
+               }       
+               
+               
+               if (addtoroot == 1 )
+                       dag_add_relation(dag,scenenode,node,DAG_RL_SCENE);
+               
+               addtoroot = 1;
+               base= base->next;
+       }
+       
+       // cycle detection and solving
+       // solve_cycles(dag);   
+       
+       return dag;
+}
+
+
+void free_forest(DagForest *Dag) 
+{  /* remove all nodes and deps */
+       DagNode *tempN;
+       DagAdjList *tempA;      
+       DagAdjList *itA;
+       DagNode *itN = Dag->DagNode.first;
+       
+       while (itN) {
+               itA = itN->child;       
+               while (itA) {
+                       tempA = itA;
+                       itA = itA->next;
+                       MEM_freeN(tempA);                       
+               }
+               tempN = itN;
+               itN = itN->next;
+               MEM_freeN(tempN);
+       }
+       Dag->DagNode.first = NULL;
+       Dag->DagNode.last = NULL;
+       Dag->numNodes = 0;
+
+}
+
+DagNode * dag_find_node (DagForest *forest,void * fob)
+{
+               DagNode *node = forest->DagNode.first;
+               
+               while (node) {
+                       if (node->ob == fob)
+                               return node;
+                       node = node->next;
+               }
+               return NULL;
+}
+
+/* no checking of existance, use dag_find_node first or dag_get_node */
+DagNode * dag_add_node (DagForest *forest,void * fob)
+{
+       DagNode *node;
+               
+       node = MEM_mallocN(sizeof(DagNode),"DAG node");
+       if (node) {
+               node->ob = fob;
+               node->color = DAG_WHITE;
+               node->BFS_dist = 0;             
+               node->DFS_dist = 0;             
+               node->DFS_dvtm = 0;             
+               node->DFS_fntm = 0;
+               node->child = NULL;
+               node->next = NULL;
+               node->first_ancestor = NULL;
+               node->ancestor_count = 0;
+
+               node->type = GS(((ID *) fob)->name);
+               if (forest->numNodes) {
+                       ((DagNode *) forest->DagNode.last)->next = node;
+                       forest->DagNode.last = node;
+                       forest->numNodes++;
+               } else {
+                       forest->DagNode.last = node;
+                       forest->DagNode.first = node;
+                       forest->numNodes = 1;
+               }
+       }
+       return node;
+}
+
+DagNode * dag_get_node (DagForest *forest,void * fob)
+{
+       DagNode *node;
+       
+       node = dag_find_node (forest, fob);     
+       if (!node) 
+               node = dag_add_node(forest, fob);
+       return node;
+}
+
+
+
+DagNode * dag_get_sub_node (DagForest *forest,void * fob)
+{
+       DagNode *node;
+       DagAdjList *mainchild, *prev=NULL;
+       
+       mainchild = ((DagNode *) forest->DagNode.first)->child;
+       /* remove from first node (scene) adj list if present */
+       while (mainchild) {
+               if (mainchild->node == fob) {
+                       if (prev) {
+                               prev->next = mainchild->next;
+                               MEM_freeN(mainchild);
+                               break;
+                       } else {
+                               ((DagNode *) forest->DagNode.first)->child = mainchild->next;
+                               MEM_freeN(mainchild);
+                               break;
+                       }
+               }
+               prev = mainchild;
+               mainchild = mainchild->next;
+       }
+       node = dag_find_node (forest, fob);     
+       if (!node) 
+               node = dag_add_node(forest, fob);
+       return node;
+}
+
+void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, dag_rel_type rel) 
+{
+       DagAdjList *itA = fob1->child;
+       
+       while (itA) { /* search if relation exist already */
+               if (itA->node == fob2) {
+                       if (itA->type == rel) { 
+                               itA->count += 1;
+                               return;
+                       }
+               }
+               itA = itA->next;
+       }
+       /* create new relation and insert at head */
+       itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list");
+       itA->node = fob2;
+       itA->type = rel;
+       itA->count = 1;
+       itA->next = fob1->child;
+       fob1->child = itA;
+}
+
+
+/*
+ * MainDAG is the DAG of all objects in current scene
+ * used only for drawing there is one also in each scene
+ */
+static DagForest * MainDag = NULL;
+
+DagForest *getMainDag(void)
+{
+       return MainDag;
+}
+
+
+void setMainDag(DagForest *dag)
+{
+       MainDag = dag;
+}
+
+
+/*
+ * note for BFS/DFS
+ * in theory we should sweep the whole array
+ * but in our case the first node is the scene
+ * and is linked to every other object
+ *
+ * for general case we will need to add outer loop
+ */
+
+/*
+ * ToDo : change pos kludge
+ */
+
+/* adjust levels for drawing in oops space */
+void graph_bfs(void)
+{
+       DagNode *node;
+       DagNodeQueue *nqueue;
+       int pos[50];
+       int i;
+       DagAdjList *itA;
+       int minheight;
+       
+       /* fprintf(stderr,"starting BFS \n ------------\n"); */ 
+       nqueue = queue_create(DAGQUEUEALLOC);
+       for ( i=0; i<50; i++)
+               pos[i] = 0;
+       
+       /* Init
+        * dagnode.first is alway the root (scene) 
+        */
+       node = MainDag->DagNode.first;
+       while(node) {
+               node->color = DAG_WHITE;
+               node->BFS_dist = 9999;
+               node->k = 0;
+               node = node->next;
+       }
+       
+       node = MainDag->DagNode.first;
+       if (node->color == DAG_WHITE) {
+               node->color = DAG_GRAY;
+               node->BFS_dist = 1;
+               push_queue(nqueue,node);  
+               while(nqueue->count) {
+                       node = pop_queue(nqueue);
+                       
+                       minheight = pos[node->BFS_dist];
+                       itA = node->child;
+                       while(itA != NULL) {
+                               if((itA->node->color == DAG_WHITE) ) {
+                                       itA->node->color = DAG_GRAY;
+                                       itA->node->BFS_dist = node->BFS_dist + 1;
+                                       itA->node->k = minheight;
+                                       push_queue(nqueue,itA->node);
+                               }
+                               
+                                else {
+                                       fprintf(stderr,"bfs not dag tree edge color :%i \n",itA->node->color);
+                               }
+                                
+                               
+                               itA = itA->next;
+                       }
+                       if (pos[node->BFS_dist] > node->k ) {
+                               pos[node->BFS_dist] += 1;                               
+                               node->k = pos[node->BFS_dist];
+                       } else {
+                               pos[node->BFS_dist] = node->k +1;
+                       }
+                       set_node_xy(node, DEPSX*2*node->BFS_dist, pos[node->BFS_dist]*DEPSY*2);
+                       node->color = DAG_BLACK;
+                       /*
+                        fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);   
+                        */
+               }
+       }
+       queue_delete(nqueue);
+}
+
+int pre_and_post_BFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
+       DagNode *node;
+       
+       node = dag->DagNode.first;
+       return pre_and_post_source_BFS(dag, mask,  node,  pre_func,  post_func, data);
+}
+
+
+int pre_and_post_source_BFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
+{
+       DagNode *node;
+       DagNodeQueue *nqueue;
+       DagAdjList *itA;
+       int     retval = 0;
+       /* fprintf(stderr,"starting BFS \n ------------\n"); */ 
+       
+       /* Init
+               * dagnode.first is alway the root (scene) 
+               */
+       node = dag->DagNode.first;
+       nqueue = queue_create(DAGQUEUEALLOC);
+       while(node) {
+               node->color = DAG_WHITE;
+               node->BFS_dist = 9999;
+               node = node->next;
+       }
+       
+       node = source;
+       if (node->color == DAG_WHITE) {
+               node->color = DAG_GRAY;
+               node->BFS_dist = 1;
+               pre_func(node->ob,data);
+               
+               while(nqueue->count) {
+                       node = pop_queue(nqueue);
+                       
+                       itA = node->child;
+                       while(itA != NULL) {
+                               if((itA->node->color == DAG_WHITE) && (itA->type & mask)) {
+                                       itA->node->color = DAG_GRAY;
+                                       itA->node->BFS_dist = node->BFS_dist + 1;
+                                       push_queue(nqueue,itA->node);
+                                       pre_func(node->ob,data);
+                               }
+                               
+                               else { // back or cross edge
+                                       retval = 1;
+                               }
+                               itA = itA->next;
+                       }
+                       post_func(node->ob,data);
+                       node->color = DAG_BLACK;
+                       /*
+                        fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);   
+                        */
+               }
+       }
+       queue_delete(nqueue);
+       return retval;
+}
+
+/* non recursive version of DFS, return queue -- outer loop present to catch odd cases (first level cycles)*/
+DagNodeQueue * graph_dfs(void)
+{
+       DagNode *node;
+       DagNodeQueue *nqueue;
+       DagNodeQueue *retqueue;
+       int pos[50];
+       int i;
+       DagAdjList *itA;
+       int time;
+       int skip = 0;
+       int minheight;
+       int maxpos=0;
+       int     is_cycle = 0;
+       /*
+        *fprintf(stderr,"starting DFS \n ------------\n");
+        */     
+       nqueue = queue_create(DAGQUEUEALLOC);
+       retqueue = queue_create(MainDag->numNodes);
+       for ( i=0; i<50; i++)
+               pos[i] = 0;
+       
+       /* Init
+        * dagnode.first is alway the root (scene) 
+        */
+       node = MainDag->DagNode.first;
+       while(node) {
+               node->color = DAG_WHITE;
+               node->DFS_dist = 9999;
+               node->DFS_dvtm = node->DFS_fntm = 9999;
+               node->k = 0;
+               node =  node->next;
+       }
+       
+       time = 1;
+       
+       node = MainDag->DagNode.first;
+
+       do {
+       if (node->color == DAG_WHITE) {
+               node->color = DAG_GRAY;
+               node->DFS_dist = 1;
+               node->DFS_dvtm = time;
+               time++;
+               push_stack(nqueue,node);  
+                       
+               while(nqueue->count) {
+                       //graph_print_queue(nqueue);
+
+                        skip = 0;
+                       node = get_top_node_queue(nqueue);
+                       
+                       minheight = pos[node->DFS_dist];
+
+                       itA = node->child;
+                       while(itA != NULL) {
+                               if((itA->node->color == DAG_WHITE) ) {
+                                       itA->node->DFS_dvtm = time;
+                                       itA->node->color = DAG_GRAY;
+
+                                       time++;
+                                       itA->node->DFS_dist = node->DFS_dist + 1;
+                                       itA->node->k = minheight;
+                                       push_stack(nqueue,itA->node);
+                                       skip = 1;
+                                       break;
+                               } else { 
+                                       if (itA->node->color == DAG_GRAY) { // back edge
+                                               fprintf(stderr,"dfs back edge :%15s %15s \n",((ID *) node->ob)->name, ((ID *) itA->node->ob)->name);
+                                               is_cycle = 1;
+                                       } else if (itA->node->color == DAG_BLACK) {
+                                               ;
+                                               /* already processed node but we may want later to change distance either to shorter to longer.
+                                                * DFS_dist is the first encounter  
+                                               */
+                                               /*if (node->DFS_dist >= itA->node->DFS_dist)
+                                                       itA->node->DFS_dist = node->DFS_dist + 1;
+                                                       
+                                                       fprintf(stderr,"dfs forward or cross edge :%15s %i-%i %15s %i-%i \n",
+                                                               ((ID *) node->ob)->name,
+                                                               node->DFS_dvtm, 
+                                                               node->DFS_fntm, 
+                                                               ((ID *) itA->node->ob)->name, 
+                                                               itA->node->DFS_dvtm,
+                                                               itA->node->DFS_fntm);
+                                       */
+                                       } else 
+                                               fprintf(stderr,"dfs unknown edge \n");
+                               }
+                               itA = itA->next;
+                       }                       
+
+                       if (!skip) {
+                               node = pop_queue(nqueue);
+                               node->color = DAG_BLACK;
+
+                               node->DFS_fntm = time;
+                               time++;
+                               if (node->DFS_dist > maxpos)
+                                       maxpos = node->DFS_dist;
+                               if (pos[node->DFS_dist] > node->k ) {
+                                       pos[node->DFS_dist] += 1;                               
+                                       node->k = pos[node->DFS_dist];
+                               } else {
+                                       pos[node->DFS_dist] = node->k +1;
+                               }
+                               set_node_xy(node, DEPSX*2*node->DFS_dist, pos[node->DFS_dist]*DEPSY*2);
+                               
+                               /*
+                                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 );       
+                               */
+                                push_stack(retqueue,node);
+                               
+                       }
+               }
+       }
+               node = node->next;
+       } while (node);
+//       fprintf(stderr,"i size : %i \n", maxpos);
+         
+       queue_delete(nqueue);
+         return(retqueue);
+}
+
+int pre_and_post_DFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
+       DagNode *node;
+
+       node = dag->DagNode.first;
+       return pre_and_post_source_DFS(dag, mask,  node,  pre_func,  post_func, data);
+}
+
+int pre_and_post_source_DFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
+{
+       DagNode *node;
+       DagNodeQueue *nqueue;
+       DagAdjList *itA;
+       int time;
+       int skip = 0;
+       int retval = 0;
+       /*
+        *fprintf(stderr,"starting DFS \n ------------\n");
+        */     
+       nqueue = queue_create(DAGQUEUEALLOC);
+       
+       /* Init
+               * dagnode.first is alway the root (scene) 
+               */
+       node = dag->DagNode.first;
+       while(node) {
+               node->color = DAG_WHITE;
+               node->DFS_dist = 9999;
+               node->DFS_dvtm = node->DFS_fntm = 9999;
+               node->k = 0;
+               node =  node->next;
+       }
+       
+       time = 1;
+       
+       node = source;
+       do {
+               if (node->color == DAG_WHITE) {
+                       node->color = DAG_GRAY;
+                       node->DFS_dist = 1;
+                       node->DFS_dvtm = time;
+                       time++;
+                       push_stack(nqueue,node);  
+                       pre_func(node->ob,data);
+
+                       while(nqueue->count) {
+                               skip = 0;
+                               node = get_top_node_queue(nqueue);
+                                                               
+                               itA = node->child;
+                               while(itA != NULL) {
+                                       if((itA->node->color == DAG_WHITE) && (itA->type & mask) ) {
+                                               itA->node->DFS_dvtm = time;
+                                               itA->node->color = DAG_GRAY;
+                                               
+                                               time++;
+                                               itA->node->DFS_dist = node->DFS_dist + 1;
+                                               push_stack(nqueue,itA->node);
+                                               pre_func(node->ob,data);
+
+                                               skip = 1;
+                                               break;
+                                       } else {
+                                               if (itA->node->color == DAG_GRAY) {// back edge
+                                                       retval = 1;
+                                               }
+//                                             else if (itA->node->color == DAG_BLACK) { // cross or forward
+//                                                     ;
+                                       }
+                                       itA = itA->next;
+                               }                       
+                               
+                               if (!skip) {
+                                       node = pop_queue(nqueue);
+                                       node->color = DAG_BLACK;
+                                       
+                                       node->DFS_fntm = time;
+                                       time++;
+                                       post_func(node->ob,data);
+                               }
+                       }
+               }
+               node = node->next;
+       } while (node);
+       queue_delete(nqueue);
+       return(retval);
+}
+
+// sort the base list on place
+void topo_sort_baselist(struct Scene *sce){
+       DagNode *node;
+       DagNodeQueue *nqueue;
+       DagAdjList *itA;
+       int time;
+       int skip = 0;
+       ListBase tempbase;
+       Base *base;
+       
+       tempbase.first= tempbase.last= 0;
+       
+       build_dag(sce,DAG_RL_ALL_BUT_DATA_MASK);
+       
+       nqueue = queue_create(DAGQUEUEALLOC);
+       
+       node = sce->theDag->DagNode.first;
+       while(node) {
+               node->color = DAG_WHITE;
+               node =  node->next;
+       }
+       
+       time = 1;
+       
+       node = sce->theDag->DagNode.first;
+       
+       node->color = DAG_GRAY;
+       time++;
+       push_stack(nqueue,node);  
+       
+       while(nqueue->count) {
+               
+               skip = 0;
+               node = get_top_node_queue(nqueue);
+               
+               itA = node->child;
+               while(itA != NULL) {
+                       if((itA->node->color == DAG_WHITE) ) {
+                               itA->node->DFS_dvtm = time;
+                               itA->node->color = DAG_GRAY;
+                               
+                               time++;
+                               push_stack(nqueue,itA->node);
+                               skip = 1;
+                               break;
+                       } 
+                       itA = itA->next;
+               }                       
+               
+               if (!skip) {
+                       if (node) {
+                               node = pop_queue(nqueue);
+                               if (node->ob == sce)    // we are done
+                                       break ;
+                               node->color = DAG_BLACK;
+                               
+                               time++;
+                               base = sce->base.first;
+                               while (base->object != node->ob)
+                                       base = base->next;
+                               BLI_remlink(&sce->base,base);
+                               BLI_addhead(&tempbase,base);
+                       }       
+               }
+       }
+       
+       sce->base = tempbase;
+       queue_delete(nqueue);
+}
+
+
+// used to get the obs owning a datablock
+struct DagNodeQueue *get_obparents(struct DagForest    *dag, void *ob) 
+{
+       DagNode * node, *node1;
+       DagNodeQueue *nqueue;
+       DagAdjList *itA;
+
+       node = dag_find_node(dag,ob);
+       if (node->ancestor_count == 1) { // simple case
+               nqueue = queue_create(1);
+               push_queue(nqueue,node);
+       } else {        // need to go over the whole dag for adj list
+               nqueue = queue_create(node->ancestor_count);
+               
+               node1 = dag->DagNode.first;
+               do {
+                       if (node1->DFS_fntm > node->DFS_fntm) { // a parent is finished after child. must check adj list
+                               itA = node->child;
+                               while(itA != NULL) {
+                                       if ((itA->node == node) && (itA->type == DAG_RL_DATA)) {
+                                               push_queue(nqueue,node);
+                                       }
+                                       itA = itA->next;
+                               }
+                       }
+                       node1 = node1->next;
+               } while (node1);
+       }
+       return nqueue;
+}
+
+struct DagNodeQueue *get_first_ancestors(struct DagForest      *dag, void *ob)
+{
+       DagNode * node, *node1;
+       DagNodeQueue *nqueue;
+       DagAdjList *itA;
+       
+       node = dag_find_node(dag,ob);
+       
+       // need to go over the whole dag for adj list
+       nqueue = queue_create(node->ancestor_count);
+       
+       node1 = dag->DagNode.first;
+       do {
+               if (node1->DFS_fntm > node->DFS_fntm) { 
+                       itA = node->child;
+                       while(itA != NULL) {
+                               if (itA->node == node) {
+                                       push_queue(nqueue,node);
+                               }
+                               itA = itA->next;
+                       }
+               }
+               node1 = node1->next;
+       } while (node1);
+       
+       return nqueue;  
+}
+
+// standard DFS list
+struct DagNodeQueue *get_all_childs(struct DagForest   *dag, void *ob)
+{
+       DagNode *node;
+       DagNodeQueue *nqueue;
+       DagNodeQueue *retqueue;
+       DagAdjList *itA;
+       int time;
+       int skip = 0;
+
+       nqueue = queue_create(DAGQUEUEALLOC);
+       retqueue = queue_create(MainDag->numNodes);
+       
+       node = dag->DagNode.first;
+       while(node) {
+               node->color = DAG_WHITE;
+               node =  node->next;
+       }
+       
+       time = 1;
+       
+       node = dag_find_node(dag,ob);
+       
+       node->color = DAG_GRAY;
+       time++;
+       push_stack(nqueue,node);  
+       
+       while(nqueue->count) {
+               
+               skip = 0;
+               node = get_top_node_queue(nqueue);
+                               
+               itA = node->child;
+               while(itA != NULL) {
+                       if((itA->node->color == DAG_WHITE) ) {
+                               itA->node->DFS_dvtm = time;
+                               itA->node->color = DAG_GRAY;
+                               
+                               time++;
+                               push_stack(nqueue,itA->node);
+                               skip = 1;
+                               break;
+                       } 
+                       itA = itA->next;
+               }                       
+               
+               if (!skip) {
+                       node = pop_queue(nqueue);
+                       node->color = DAG_BLACK;
+                       
+                       time++;
+                       push_stack(retqueue,node);                      
+               }
+       }
+               
+       queue_delete(nqueue);
+       return(retqueue);
+}
+
+dag_rel_type   are_obs_related(struct DagForest        *dag, void *ob1, void *ob2) {
+       DagNode * node;
+       DagAdjList *itA;
+       
+       node = dag_find_node(dag,ob1);
+       
+       itA = node->child;
+       while(itA != NULL) {
+               if((itA->node->ob == ob2) ) {
+                       return itA->node->type;
+               } 
+               itA = itA->next;
+       }
+       return DAG_NO_RELATION;
+}
+
+int    is_acyclic( DagForest   *dag) {
+       return dag->is_acyclic;
+}
+
+void set_node_xy(DagNode *node, float x, float y)
+{
+       node->x = x;
+       node->y = y;
+}
+
+
+/* debug test functions */
+
+void graph_print_queue(DagNodeQueue *nqueue)
+{      
+       DagNodeQueueElem *queueElem;
+       
+       queueElem = nqueue->first;
+       while(queueElem) {
+               fprintf(stderr,"** %s %i %i-%i ",((ID *) queueElem->node->ob)->name,queueElem->node->color,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
+               queueElem = queueElem->next;            
+       }
+       fprintf(stderr,"\n");
+}
+
+void graph_print_queue_dist(DagNodeQueue *nqueue)
+{      
+       DagNodeQueueElem *queueElem;
+       int max, count;
+       
+       queueElem = nqueue->first;
+       max = queueElem->node->DFS_fntm;
+       count = 0;
+       while(queueElem) {
+               fprintf(stderr,"** %25s %2.2i-%2.2i ",((ID *) queueElem->node->ob)->name,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
+               while (count < queueElem->node->DFS_dvtm-1) { fputc(' ',stderr); count++;}
+               fputc('|',stderr); 
+               while (count < queueElem->node->DFS_fntm-2) { fputc('-',stderr); count++;}
+               fputc('|',stderr);
+               fputc('\n',stderr);
+               count = 0;
+               queueElem = queueElem->next;            
+       }
+       fprintf(stderr,"\n");
+}
+
+void graph_print_adj_list(void)
+{
+       DagNode *node;
+       DagAdjList *itA;
+       
+       node = (getMainDag())->DagNode.first;
+       while(node) {
+               fprintf(stderr,"node : %s col: %i",((ID *) node->ob)->name, node->color);               
+               itA = node->child;
+               while (itA) {
+                       fprintf(stderr,"-- %s ",((ID *) itA->node->ob)->name);
+                       
+                       itA = itA->next;
+               }
+               fprintf(stderr,"\n");
+               node = node->next;
+       }
+}
+
+
index aebfa54fe1e9cd187f88221e4adc0dccd7a1cf45..1d7bb7e5f4737a00a3d1efa15cdc8fcfb039043e 100644 (file)
 
 #include "BPY_extern.h"
 
+#include "BKE_depsgraph.h"
+
+#include <sys/time.h>
+
+
 void free_avicodecdata(AviCodecData *acd)
 {
        if (acd) {
@@ -140,6 +145,10 @@ void free_scene(Scene *sce)
                MEM_freeN(sce->r.qtcodecdata);
                sce->r.qtcodecdata = NULL;
        }
+       if (sce->theDag) {
+               free_forest(sce->theDag);
+               MEM_freeN(sce->theDag);
+       }
 }
 
 Scene *add_scene(char *name)
@@ -208,6 +217,12 @@ int object_in_scene(Object *ob, Scene *sce)
 }
 
 void sort_baselist(Scene *sce)
+{
+               topo_sort_baselist(sce);
+}
+
+#if 0
+void old_sort_baselist(Scene *sce)
 {
        /* in order of parent and track */
        ListBase tempbase, noparentbase, notyetbase;
@@ -215,7 +230,6 @@ void sort_baselist(Scene *sce)
        Object *par;
        int doit, domore= 0, lastdomore=1;
        
-       
        /* keep same order when nothing has changed! */
        
        while(domore!=lastdomore) {
@@ -287,8 +301,9 @@ void sort_baselist(Scene *sce)
                addlisttolist(&sce->base, &notyetbase);
 
        }
-}
 
+}
+#endif
 
 void set_scene_bg(Scene *sce)
 {
index ff3953296dfc4285e6648b7091be1a473fbe2708..a3d9e0e1202f5f2d85cf0fffca35b67f5600db1b 100644 (file)
@@ -2694,7 +2694,6 @@ static void lib_link_screen(FileData *fd, Main *main)
                                                                tselem->id= newlibadr(fd, NULL, tselem->id);
                                                        }
                                                }
-                                               
                                        }
                                        else if(sl->spacetype==SPACE_SOUND) {
                                                SpaceSound *ssound= (SpaceSound *)sl;
@@ -4640,7 +4639,11 @@ static void do_versions(Main *main)
                bScreen *sc;
                
                while(sce) {
+                       sce->theDag = NULL;
+                       sce->dagisvalid = 0;
+
                        if(sce->r.postsat==0.0) sce->r.postsat= 1.0;
+
                        if(sce->r.zgamma==0.0) {
                                sce->r.focus= 0.9;
                                sce->r.zgamma= 1.0;
@@ -4648,6 +4651,7 @@ static void do_versions(Main *main)
                                sce->r.zblur= 10.0;
                                sce->r.zmin= 0.8;
                        }
+
                        sce= sce->id.next;
                }
                while(cam) {
@@ -4658,6 +4662,7 @@ static void do_versions(Main *main)
                        cam= cam->id.next;
                }
                /* set manipulator type */
+               /* force oops draw if depgraph was set*/
                for (sc= main->screen.first; sc; sc= sc->id.next) {
                        ScrArea *sa;
                        for (sa= sc->areabase.first; sa; sa= sa->next) {
@@ -4667,6 +4672,12 @@ static void do_versions(Main *main)
                                                View3D *v3d= (View3D *)sl;
                                                if(v3d->twtype==0) v3d->twtype= V3D_MANIP_TRANSLATE;
                                        }
+#ifndef SHOWDEPGRAPH
+                                       if(sl->spacetype==SPACE_OOPS) {
+                                               if ( ((SpaceOops *)sl)->type==SO_DEPSGRAPH)
+                                                        ((SpaceOops *)sl)->type=SO_OOPS;
+                                       }
+#endif                                         
                                }
                        }
                }
index d285a46c3ae9f74c55c360c90a162625ea8ac496..2297c1b50aa90658486bc11b5aa52f64cfe028b3 100644 (file)
@@ -273,6 +273,11 @@ typedef struct Scene {
        struct AudioData audio; 
        
        ScriptLink scriptlink;
+       
+       /* none of the dependancy graph  vars is mean to be saved */
+       struct  DagForest *theDag;
+       short dagisvalid, dagflags;
+       int pad1;
 } Scene;
 
 
index 13047c6a7934a35c66a477aadf2ae4e9f8715ac4..ee45cf67074cd062d9e8051c4c9e28d02ac16eba 100644 (file)
@@ -199,7 +199,7 @@ typedef struct SpaceOops {
        ListBase tree;
        struct TreeStore *treestore;
        short type, outlinevis, storeflag;
-       short pad1;
+       short deps_flags;
        
 } SpaceOops;
 
@@ -451,6 +451,7 @@ typedef struct SpaceImaSel {
 /* SpaceOops->type */
 #define SO_OOPS                        0
 #define SO_OUTLINER            1
+#define SO_DEPSGRAPH    2
 
 /* SpaceOops->flag */
 #define SO_TESTBLOCKS  1
index 166c2a9b1336429c59b76c6d6aa2516da93952a1..28889f674fb13ae268d725e693cf488b19fdd286 100644 (file)
@@ -23,6 +23,7 @@ source_files = ['B.blend.c',
                 'cmovie.tga.c',
                 'cursors.c',
                 'drawaction.c',
+                'drawdeps.c',
                 'drawimage.c',
                 'drawimasel.c',
                 'drawipo.c',
diff --git a/source/blender/src/drawdeps.c b/source/blender/src/drawdeps.c
new file mode 100644 (file)
index 0000000..56445b7
--- /dev/null
@@ -0,0 +1,413 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2004 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+
+#ifdef _WIN32
+#include "BLI_winstuff.h"
+#endif
+
+#include "BMF_Api.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_arithb.h"
+
+#include "DNA_ID.h"
+#include "DNA_object_types.h"
+#include "DNA_oops_types.h"
+#include "DNA_scene_types.h"
+#include "DNA_screen_types.h"
+#include "DNA_space_types.h"
+#include "DNA_view2d_types.h"
+#include "DNA_action_types.h"
+
+#include "BKE_utildefines.h"
+#include "BKE_global.h"
+
+#include "BIF_interface.h"
+#include "BIF_gl.h"
+#include "BIF_glutil.h"
+#include "BIF_mywindow.h"
+#include "BIF_resources.h"
+#include "BIF_screen.h"
+
+#include "BIF_oops.h"
+
+#include "BSE_drawipo.h"
+#include "BSE_drawoops.h"
+#include "MEM_guardedalloc.h"
+#include "blendef.h"
+
+
+#include "depsgraph_private.h"
+
+#include <sys/time.h>
+
+
+
+void boundbox_deps()
+{
+       DagNode *node;
+       float min[2], max[2];
+       
+       if(G.soops==0) return;
+       
+       min[0]= 1000.0;
+       max[0]= -10000.0;
+       min[1]= 1000.0;
+       max[1]= -1000.0;
+       
+       node = getMainDag()->DagNode.first;
+       while(node) {
+               min[0]= MIN2(min[0], node->x);
+               max[0]= MAX2(max[0], node->x+OOPSX);
+               min[1]= MIN2(min[1], node->y);
+               max[1]= MAX2(max[1], node->y+OOPSY);
+               
+               node= node->next;
+       }
+               
+       G.v2d->tot.xmin= min[0];
+       G.v2d->tot.xmax= max[0];
+       G.v2d->tot.ymin= min[1];
+       G.v2d->tot.ymax= max[1];
+}
+
+static unsigned int get_line_color(DagAdjList *child)
+{
+       switch  (child->type) {
+               case DAG_RL_SCENE :
+                       return 0x00000;
+               case DAG_RL_DATA :
+                       return 0xFF0000;
+               case DAG_RL_PARENT :
+                       return 0x00FF00;
+               case DAG_RL_TRACK :
+                       return 0xFFFF00;
+               case DAG_RL_PATH :
+                       return 0x000000;
+               case DAG_RL_CONSTRAINT :
+                       return 0x0000FF;
+               case DAG_RL_HOOK :
+                       return 0x00FFFF;
+               case DAG_RL_DATA_CONSTRAINT :
+                       return 0x0000FF;
+               default :
+                       return 0x0000FF;
+       }
+       //return 0x00000;
+}
+
+
+static void draw_deps(DagNode *node)
+{
+       float v1[2], x1, y1, x2, y2;
+       unsigned int body, border;
+       short line= 0;
+       char str[32];
+       DagAdjList *itA = node->child;
+
+       x1= node->x; 
+       x2= node->x+DEPSX;
+       y1= node->y; 
+       y2= node->y+DEPSY;
+
+       if(x2 < G.v2d->cur.xmin || x1 > G.v2d->cur.xmax) return;
+       if(y2 < G.v2d->cur.ymin || y1 > G.v2d->cur.ymax) return;
+
+       body =  give_oops_color(node->type, 0, &border);
+
+       line= 0;
+//     border= 00;
+       cpack(body);
+
+       glRectf(x1,  y1,  x2,  y2);
+       
+       v1[0]= x1; 
+       v1[1]= (y1+y2)/2 -0.3;
+       sprintf(str, "     %s", ((ID *) node->ob)->name+2);
+       
+       calc_oopstext(str, v1);
+       
+               /* ICON */
+//     if(str[1] && oopscalex>1.1) {
+       draw_icon_oops(v1, node->type);
+//     }
+
+       
+       cpack(0x0);
+       glRasterPos3f(v1[0],  v1[1], 0.0);
+       BMF_DrawString(G.fonts, str);
+
+       
+       if(line) setlinestyle(2);
+       cpack(border);
+
+       glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
+       glRectf(x1,  y1,  x2,  y2);
+       glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
+       if(line) setlinestyle(0);
+
+       while (itA) { /* draw connection lines */
+               cpack(get_line_color(itA));
+               glBegin(GL_LINE_STRIP);
+                       glVertex2f(node->x+DEPSX, node->y+ 0.5*DEPSY);
+                       glVertex2f(itA->node->x, itA->node->y+ 0.5*DEPSY);                      
+               glEnd();
+               itA = itA->next;
+       }
+                       /* Draw the little rounded connection point */
+               glColor3ub(0, 0, 0);
+               glPushMatrix();
+
+               glTranslatef(node->x , node->y+ 0.5*DEPSY, 0.0);
+               glutil_draw_filled_arc(-M_PI/2, M_PI, 0.07*DEPSX, 7);
+
+               glPopMatrix();
+
+}
+
+void   draw_all_deps(void)
+{
+       DagNode *node;
+       DagForest *dag;
+       
+       dag = getMainDag();
+        node = dag->DagNode.first;
+       //node = node->next;
+       while(node) {
+               draw_deps(node);
+               node = node->next;
+       }
+       free_forest(dag);
+       MEM_freeN(dag);
+       setMainDag(NULL);
+}
+
+
+
+
+int build_deps(short mask)
+{
+       Base *base;
+       Object *ob = NULL;
+       DagNode * node = NULL; 
+       DagNode * node2 = NULL ;
+       DagNode * node3 = NULL;
+DagNode * scenenode;
+       DagForest *dag;
+
+#ifdef DEPS_DEBUG
+       //timers
+       struct timeval tp1, tp2, tp3, tp4;
+       
+       gettimeofday(&tp1,NULL);
+#endif
+       
+       DagNodeQueue *retqueue;
+       
+//     float y = 0;
+//     int maxlev = 0;
+
+       if(G.soops==0) return -1;
+       
+       
+       // rebuilt each time for now
+       dag = getMainDag();
+       if ( dag)
+               free_forest( dag ); 
+       else {
+               dag = dag_init();
+               setMainDag(dag);
+               }
+               
+       // add base node for scene. scene is always the first node in DAG
+       scenenode = dag_add_node(dag, G.scene);
+       set_node_xy(scenenode,0.0, 0.0);        
+               /* blocks from this scene */
+               
+               
+               /* targets in object struct yet to be added. should even they ?
+                               struct Ipo *ipo;
+                       ListBase nlastrips;
+                       ListBase hooks;
+               */
+               
+               
+       base= FIRSTBASE;
+       while(base) { // add all objects in any case
+               int addtoroot = 1;
+               
+//                              graph_print_adj_list();
+ob= (Object *) base->object;
+
+               node = dag_get_node(dag,ob);
+       
+               if ((ob->data) && (mask&DAG_RL_DATA_MASK)) {
+                       node2 = dag_get_node(dag,ob->data);
+                       dag_add_relation(dag,node,node2,DAG_RL_DATA);
+                       node2->first_ancestor = ob;
+                       node2->ancestor_count += 1;
+                       
+                       if ((ob->type == OB_ARMATURE) && (mask&DAG_RL_DATA_CONSTRAINT_MASK)) { // add armature constraints to datas
+                               if (ob->pose){
+                                       bPoseChannel *pchan;
+                                       bConstraint *con;
+                                       Object * target;
+                                       
+                                       for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){
+                                               for (con = pchan->constraints.first; con; con=con->next){
+                                                       if (constraint_has_target(con)) {
+                                                               target = get_constraint_target(con);
+                                                               if (strcmp(target->id.name, ob->id.name) != 0) {
+                                                                       //fprintf(stderr,"armature target :%s \n", target->id.name);
+                                                                       node3 = dag_get_node(dag,target);
+                                                                       dag_add_relation(dag,node3,node2,DAG_RL_CONSTRAINT);
+                                                               }
+                                                       }
+                                               }
+                                       }
+                               }
+                       }
+                       
+                       if (ob->hooks.first) {
+                               ObHook *hook;
+                               
+                               for(hook= ob->hooks.first; hook; hook= hook->next) {
+                                       if(hook->parent) {
+                                               node3 = dag_get_node(dag,hook->parent);
+                                               dag_add_relation(dag,node3,node2,DAG_RL_HOOK);
+                                       }
+                               }
+                       }
+               } else { // add armature constraints to object itself
+                       if ((ob->type == OB_ARMATURE) && (mask&DAG_RL_DATA_CONSTRAINT_MASK)) {
+                               if (ob->pose){
+                                       bPoseChannel *pchan;
+                                       bConstraint *con;
+                                       Object * target;
+                                       
+                                       for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){
+                                               for (con = pchan->constraints.first; con; con=con->next){
+                                                       if (constraint_has_target(con)) {
+                                                               target = get_constraint_target(con);
+                                                               if (strcmp(target->id.name, ob->id.name) != 0) {
+                                                                       //fprintf(stderr,"armature target :%s \n", target->id.name);
+                                                                       node3 = dag_get_node(dag,target);
+                                                                       dag_add_relation(dag,node3,node,DAG_RL_CONSTRAINT);
+                                                               }
+                                                       }
+                                               }
+                                       }
+                               }
+                       }
+                       if (ob->hooks.first) {
+                               ObHook *hook;
+                               
+                               for(hook= ob->hooks.first; hook; hook= hook->next) {
+                                       if(hook->parent) {
+                                               node3 = dag_get_node(dag,hook->parent);
+                                               dag_add_relation(dag,node3,node,DAG_RL_HOOK);
+                                       }
+                               }
+                       }                       
+               }
+
+               if ((ob->parent) && (mask&DAG_RL_PARENT_MASK)){
+                       node2 = dag_get_node(dag,ob->parent);
+                       dag_add_relation(dag,node2,node,DAG_RL_PARENT);
+                       addtoroot = 0;
+               }
+               if ((ob->track) && (mask&DAG_RL_TRACK_MASK)){
+                       node2 = dag_get_node(dag,ob->track);
+                       dag_add_relation(dag,node2,node,DAG_RL_TRACK);
+                       addtoroot = 0;
+
+               }
+               if ((ob->path) && (mask&DAG_RL_PATH_MASK)){
+                       node2 = dag_get_node(dag,ob->track);
+                       dag_add_relation(dag,node2,node,DAG_RL_PATH);
+                       addtoroot = 0;
+
+               }
+
+               /* Count constraints */
+               if (mask & DAG_RL_CONSTRAINT_MASK) {
+                       bConstraint *con;
+                       for (con = ob->constraints.first; con; con=con->next){
+                               if (constraint_has_target(con)) {
+                                       node2 = dag_get_node(dag,get_constraint_target(con));
+                                       dag_add_relation(dag,node2,node,DAG_RL_CONSTRAINT);
+                                       addtoroot = 0;
+                                       
+                               }
+                       }
+               }       
+               
+               
+               if (addtoroot == 1 )
+                       dag_add_relation(dag,scenenode,node,DAG_RL_SCENE);
+
+               addtoroot = 1;
+               base= base->next;
+       }
+
+//graph_print_adj_list();
+//fprintf(stderr,"building deps\n");
+#ifdef DEPS_DEBUG
+       gettimeofday(&tp2,NULL);
+#endif
+
+//graph_bfs(); //set levels
+
+#ifdef DEPS_DEBUG
+gettimeofday(&tp3,NULL);
+#endif
+
+
+retqueue = graph_dfs(); //set levels
+#ifdef DEPS_DEBUG
+gettimeofday(&tp4,NULL);
+fprintf(stderr,"************************************\n");
+graph_print_queue_dist(retqueue);
+//graph_print_queue(retqueue);
+
+fprintf(stderr,"TIME BUILD %d %d BFS %d %d DFS  %d %d\n",tp2.tv_sec-tp1.tv_sec ,tp2.tv_usec-tp1.tv_usec
+                                                                                                               , tp3.tv_sec-tp2.tv_sec ,tp3.tv_usec-tp2.tv_usec
+                                                                                                               , tp4.tv_sec-tp3.tv_sec ,tp4.tv_usec-tp3.tv_usec);
+#endif
+
+queue_delete(retqueue);
+
+//graph_print_adj_list();
+return 0;
+}
index ea90a4c35f1e8c7f8ed69e27340079b655d4be6b..8d18466dff99642759ab48a4436398601538c389 100644 (file)
 #include "BSE_drawipo.h"
 #include "BSE_drawoops.h"
 
+#include "BKE_depsgraph.h"
+
+extern void build_deps(short mask);
+//extern void draw_deps(DagNode *node);
+
+
 float oopscalex;
 
 void boundbox_oops()
@@ -399,7 +405,17 @@ void drawoopsspace(ScrArea *sa, void *spacedata)
        if(soops==0) return;    
        
        if(soops->type==SO_OUTLINER) draw_outliner(sa, soops);
-       else {
+       else if (soops->type==SO_DEPSGRAPH) {
+               build_deps(soops->deps_flags);
+               boundbox_deps();
+               calc_scrollrcts(sa,G.v2d, curarea->winx, curarea->winy);
+
+               myortho2(G.v2d->cur.xmin, G.v2d->cur.xmax, G.v2d->cur.ymin, G.v2d->cur.ymax);
+
+               oopscalex= .14*((float)curarea->winx)/(G.v2d->cur.xmax-G.v2d->cur.xmin);
+               calc_ipogrid(); /* for scrollvariables */
+               draw_all_deps();
+       } else {
                boundbox_oops();
                calc_scrollrcts(sa, G.v2d, curarea->winx, curarea->winy);
 
index 0ed3c440ae803ff32956ae8eb25e6c904cfdfda7..fa2386aaabd92101b71bf678029550b741e8aafc 100644 (file)
@@ -69,6 +69,8 @@
 
 #include "blendef.h"
 
+#include "BKE_depsgraph.h"
+
 static int viewmovetemp = 0;
 
 void do_oops_buttons(short event)
@@ -119,7 +121,7 @@ static void do_oops_viewmenu(void *arg, int event)
        case 4: /* show outliner */
                {
                        SpaceOops *soops= curarea->spacedata.first;
-                       if(soops->type==SO_OOPS) soops->type= SO_OUTLINER;
+                       if(soops->type==SO_OOPS || soops->type==SO_DEPSGRAPH) soops->type= SO_OUTLINER;
                        else soops->type= SO_OOPS;
                        init_v2d_oops(curarea, soops);
                        test_view2d(G.v2d, curarea->winx, curarea->winy);
@@ -141,6 +143,22 @@ static void do_oops_viewmenu(void *arg, int event)
        case 9:
                outliner_one_level(curarea, -1);
                break;
+#ifdef SHOWDEPGRAPH
+       case 10:
+               // show deps
+               {
+                       SpaceOops *soops= curarea->spacedata.first;
+                       if(soops->type==SO_OOPS) {
+                               soops->type= SO_DEPSGRAPH;
+                               soops->deps_flags = DAG_RL_ALL_BUT_DATA_MASK;
+                       } else 
+                               soops->type= SO_OOPS;
+                       init_v2d_oops(curarea, soops);
+                       test_view2d(G.v2d, curarea->winx, curarea->winy);
+                       scrarea_queue_winredraw(curarea);
+               }
+               break;
+#endif
        }
 }                      
 
@@ -155,7 +173,9 @@ static uiBlock *oops_viewmenu(void *arg_unused)
        
        if(soops->type==SO_OOPS) {
                uiDefIconTextBut(block, BUTM, 1, ICON_BLANK1, "Show Outliner", 0, yco-=20, menuwidth, 19, NULL, 0.0, 0.0, 1, 4, "");
-
+#ifdef SHOWDEPGRAPH
+               uiDefIconTextBut(block, BUTM, 1, ICON_BLANK1, "Show Dependancies", 0, yco-=20, menuwidth, 19, NULL, 0.0, 0.0, 1, 10, "");
+#endif
                uiDefBut(block, SEPR, 0, "",        0, yco-=6, menuwidth, 6, NULL, 0.0, 0.0, 0, 0, "");  
 
                uiDefIconTextBut(block, BUTM, 1, ICON_BLANK1, "Shuffle Selected Blocks|Shift S", 0, yco-=20, menuwidth, 19, NULL, 0.0, 0.0, 1, 0, "");
@@ -165,6 +185,12 @@ static uiBlock *oops_viewmenu(void *arg_unused)
 
                uiDefIconTextBut(block, BUTM, 1, ICON_BLANK1, "View All|Home", 0, yco-=20, menuwidth, 19, NULL, 0.0, 0.0, 1, 2, "");
        }
+#ifdef SHOWDEPGRAPH
+       else if(soops->type==SO_DEPSGRAPH) {
+               uiDefIconTextBut(block, BUTM, 1, ICON_BLANK1, "Show Outliner", 0, yco-=20, menuwidth, 19, NULL, 0.0, 0.0, 1, 4, "");
+               uiDefIconTextBut(block, BUTM, 1, ICON_BLANK1, "Show Oops Schematic", 0, yco-=20, menuwidth, 19, NULL, 0.0, 0.0, 1, 10, "");
+       }
+#endif
        else {
                uiDefIconTextBut(block, BUTM, 1, ICON_BLANK1, "Show Oops Schematic", 0, yco-=20, menuwidth, 19, NULL, 0.0, 0.0, 1, 4, "");
                
@@ -386,6 +412,33 @@ void oops_buttons(void)
 
                }
        }
+#ifdef SHOWDEPGRAPH
+       else if(soops->type==SO_DEPSGRAPH) {
+               // cpack colors : 0x00FF00 0xFF0000 0xFFFF00 0x000000 0x0000FF 0x00FFFF
+               static unsigned char colr[21] ={0x00, 0xFF, 0x00, 
+                                                                               0x00, 0x00, 0xFF,
+                                                                               0x00, 0xFF, 0xFF,
+                                                                               0x00, 0x00, 0x00,
+                                                                               0xFF, 0x00, 0x00,
+                                                                               0xFF, 0xFF, 0x00,
+                                                                               0xFF, 0x00, 0x00};
+               
+               uiDefButC(      block, COL, 0, "", (short)(xco+=10),0, 5,YIC, colr, 0, 1, 0, 0,  "");
+               uiDefButS(      block, TOG|BIT|2, B_REDR, "parent", (short)(xco+=7),0, 50,YIC, &soops->deps_flags, 0, 1, 0, 0,  "parent");
+               uiDefButC(      block, COL, 0, "", (short)(xco+=60),0, 5,YIC, colr+3, 0, 1, 0, 0,  "");
+               uiDefButS(      block, TOG|BIT|1, B_REDR, "data", (short)(xco+=7),0, 50,YIC, &soops->deps_flags, 0, 1, 0, 0,  "data");
+               uiDefButC(      block, COL, 0, "", (short)(xco+=60),0, 5,YIC, colr+6, 0, 1, 0, 0,  "");
+               uiDefButS(      block, TOG|BIT|3, B_REDR, "track", (short)(xco+=7),0, 50,YIC, &soops->deps_flags, 0, 1, 0, 0,  "track");
+               uiDefButC(      block, COL, 0, "", (short)(xco+=60),0, 5,YIC, colr+9, 0, 1, 0, 0,  "");
+               uiDefButS(      block, TOG|BIT|4, B_REDR, "path", (short)(xco+=7),0, 50,YIC, &soops->deps_flags, 0, 1, 0, 0,  "path");
+               uiDefButC(      block, COL, 0, "", (short)(xco+=60),0, 5,YIC, colr+12, 0, 1, 0, 0,  "");
+               uiDefButS(      block, TOG|BIT|5, B_REDR, "cons.", (short)(xco+=7),0, 50,YIC, &soops->deps_flags, 0, 1, 0, 0,  "constraint");
+               uiDefButC(      block, COL, 0, "", (short)(xco+=60),0, 5,YIC, colr+15, 0, 1, 0, 0,  "");
+               uiDefButS(      block, TOG|BIT|6, B_REDR, "hook.", (short)(xco+=7),0, 50,YIC, &soops->deps_flags, 0, 1, 0, 0,  "hook");
+               uiDefButC(      block, COL, 0, "", (short)(xco+=60),0, 5,YIC, colr+18, 0, 1, 0, 0,  "");
+               uiDefButS(      block, TOG|BIT|7, B_REDR, "d cons.", (short)(xco+=7),0, 50,YIC, &soops->deps_flags, 0, 1, 0, 0,  "d cons");
+       } 
+#endif
        else {
                uiDefButS(block, MENU, B_REDR, "Outliner Display%t|All Scenes %x0|Current Scene %x1|Visible Layers %x2|Same Types %x5|Selected %x3|Active %x4",  xco, 0, 100, 20,  &soops->outlinevis, 0, 0, 0, 0, "");
        }
index f2bf392f956d43f0e64b984dee7e30997dbd51d5..813ec2d749ee5b3a25132492b9cd99da1ca666e8 100644 (file)
 
 #include "BIF_transform.h"
 
+#include "BKE_depsgraph.h"
+
 #include "TPT_DependKludge.h"
 #ifdef NAN_TPT
 #include "BSE_trans_types.h"
@@ -4481,6 +4483,16 @@ void allqueue(unsigned short event, short val)
 
        sa= G.curscreen->areabase.first;
        while(sa) {
+//#ifdef NAN_DEP_GRAPH
+               /* dependency check.maybe not final pos */
+               if (sa->spacetype==SPACE_VIEW3D) {
+                       if (G.scene->dagisvalid == 0) {
+                               fprintf(stderr,"building dag \n");
+                               G.scene->theDag = build_dag(G.scene, DAG_RL_ALL_BUT_DATA_MASK);
+                               G.scene->dagisvalid = 1;
+                       }
+               }
+//#endif
                if(event==REDRAWALL) {
                        scrarea_queue_winredraw(sa);
                        scrarea_queue_headredraw(sa);