Dependency graph patch, provided by Jean-Luc Peuriere.

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.

5 files changed, 1456 insertions, 2 deletions

diff --git a/source/blender/blenkernel/BKE_depsgraph.h b/source/blender/blenkernel/BKE_depsgraph.h
new file mode 100644
index 00000000000..007b38b984c
--- /dev/null
+++ b/source/blender/blenkernel/BKE_depsgraph.h
@@ -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
diff --git a/source/blender/blenkernel/SConscript b/source/blender/blenkernel/SConscript
index 3ab7dc385c7..0b6bf520bc4 100644
--- a/source/blender/blenkernel/SConscript
+++ b/source/blender/blenkernel/SConscript
@@ -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
index 00000000000..7b3da76c652
--- /dev/null
+++ b/source/blender/blenkernel/depsgraph_private.h
@@ -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
index 00000000000..7ae3f39e197
--- /dev/null
+++ b/source/blender/blenkernel/intern/depsgraph.c
@@ -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;
+	}
+}
+
+
diff --git a/source/blender/blenkernel/intern/scene.c b/source/blender/blenkernel/intern/scene.c
index aebfa54fe1e..1d7bb7e5f47 100644
--- a/source/blender/blenkernel/intern/scene.c
+++ b/source/blender/blenkernel/intern/scene.c
@@ -85,6 +85,11 @@
 
 #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)
@@ -209,13 +218,18 @@ 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;
 	Base *base, *test=NULL;
 	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)
 {