Result of 2 weeks of quiet coding work in Greece :)

Aim was to get a total refresh of the animation system. This
is needed because;
- we need to upgrade it with 21st century features
- current code is spaghetti/hack combo, and hides good design
- it should become lag-free with using dependency graphs

A full log, with complete code API/structure/design explanation
will follow, that's a load of work... so here below the list with
hot changes;

- The entire object update system (matrices, geometry) is now
  centralized. Calls to where_is_object and makeDispList are
  forbidden, instead we tag objects 'changed' and let the
  depgraph code sort it out
- Removed all old "Ika" code
- Depgraph is aware of all relationships, including meta balls,
  constraints, bevelcurve, and so on.
- Made depgraph aware of relation types and layers, to do smart
  flushing of 'changed' events. Nothing gets calculated too often!
- Transform uses depgraph to detect changes
- On frame-advance, depgraph flushes animated changes

Armatures;

Almost all armature related code has been fully built from scratch.
It now reveils the original design much better, with a very clean
implementation, lag free without even calculating each Bone more than
once. Result is quite a speedup yes!

Important to note is;

1) Armature is data containing the 'rest position'
2) Pose is the changes of rest position, and always on object level.
   That way more Objects can use same Pose. Also constraints are in Pose
3) Actions only contain the Ipos to change values in Poses.

- Bones draw unrotated now
- Drawing bones speedup enormously (10-20 times)
- Bone selecting in EditMode, selection state is saved for PoseMode,
  and vice-versa
- Undo in editmode
- Bone renaming does vertexgroups, constraints, posechannels, actions,
  for all users of Armature in entire file
- Added Bone renaming in NKey panel
- Nkey PoseMode shows eulers now
- EditMode and PoseMode now have 'active' bone too (last clicked)
- Parenting in EditMode' CTRL+P, ALT+P, with nice options!
- Pose is added in Outliner now, with showing that constraints are in
  the Pose, not Armature
- Disconnected IK solving from constraints. It's a separate phase now,
  on top of the full Pose calculations
- Pose itself has a dependency graph too, so evaluation order is lag free.

TODO NOW;

- Rotating in Posemode has incorrect inverse transform (Martin will fix)
- Python Bone/Armature/Pose API disabled... needs full recode too
  (wait for my doc!)
- Game engine will need upgrade too
- Depgraph code needs revision, cleanup, can be much faster!
  (But, compliments for Jean-Luc, it works like a charm!)
- IK changed, it now doesnt use previous position to advance to next
  position anymore. That system looks nice (no flips) but is not well
  suited for NLA and background render.

TODO LATER;

We now can do loadsa new nifty features as well; like:

- Kill PoseMode (can be option for armatures itself)
- Make B-Bones (Bezier, Bspline, like for spines)
- Move all silly button level edit to 3d window (like CTRL+I = add
  IK)
- Much better & informative drawing
- Fix action/nla editors
- Put all ipos in Actions (object, mesh key, lamp color)
- Add hooks
- Null bones
- Much more advanced constraints...


Bugfixes;

- OGL render (view3d header) had wrong first frame on anim render
- Ipo 'recording' mode had wrong playback speed
- Vertex-key mode now sticks to show 'active key', until frame change

-Ton-

1 files changed, 582 insertions, 220 deletions

diff --git a/source/blender/blenkernel/intern/depsgraph.c b/source/blender/blenkernel/intern/depsgraph.c
index 668b18c0913..9f0501d54fc 100644
--- a/source/blender/blenkernel/intern/depsgraph.c
+++ b/source/blender/blenkernel/intern/depsgraph.c
@@ -41,17 +41,25 @@
 #include "BLI_blenlib.h"
 #include "BLI_arithb.h"
 
+#include "DNA_action_types.h"
+#include "DNA_armature_types.h"
+#include "DNA_curve_types.h"
 #include "DNA_ID.h"
+#include "DNA_effect_types.h"
+#include "DNA_lattice_types.h"
+#include "DNA_mesh_types.h"
 #include "DNA_object_types.h"
+#include "DNA_object_force.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_action.h"
 #include "BKE_global.h"
+#include "BKE_mball.h"
+#include "BKE_utildefines.h"
 
 #include "MEM_guardedalloc.h"
 #include "blendef.h"
@@ -272,18 +280,16 @@ int		queue_count(struct DagNodeQueue *queue){
 DagForest * dag_init()
 {
 	DagForest *forest;
-	
-	forest = MEM_mallocN(sizeof(DagForest),"DAG root");
-	forest->DagNode.first = NULL;
-	forest->DagNode.last = NULL;
-	forest->numNodes = 0;
+	/* use callocN to init all zero */
+	forest = MEM_callocN(sizeof(DagForest),"DAG root");
 	return forest;
 }
 
-struct DagForest	*build_dag(struct Scene *sce, short mask) 
+struct DagForest *build_dag(struct Scene *sce, short mask) 
 {
 	Base *base;
 	Object *ob;
+	bConstraint *con;
 	DagNode * node;
 	DagNode * node2;
 	DagNode * node3;
@@ -299,130 +305,126 @@ struct DagForest	*build_dag(struct Scene *sce, short mask)
 		sce->theDag = dag;
 	}
 	
-	// add base node for scene. scene is always the first node in 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
+	for(base = sce->base.first; base; base= base->next) {
 		int addtoroot = 1;
 		ob= (Object *) base->object;
 		
 		node = dag_get_node(dag,ob);
 		
-		if ((ob->data) && (mask&DAG_RL_DATA_MASK)) {
+		if ((ob->data) && (mask&DAG_RL_DATA)) {
 			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;
+		}
+		if (ob->type == OB_ARMATURE) {
+			if (ob->pose){
+				bPoseChannel *pchan;
+				bConstraint *con;
+				Object * target;
+				char *subtarget;
 				
-				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);
-								}
+				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, &subtarget);
+							if (target!=ob) {
+								// fprintf(stderr,"armature %s target :%s \n", ob->id.name, target->id.name);
+								node3 = dag_get_node(dag, target);
+								
+								dag_add_relation(dag,node3,node,DAG_RL_OB_DATA);
+								
 							}
 						}
 					}
 				}
 			}
-			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->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_OB_DATA);
 				}
-			}			
+			}
 		}
-		
-		if ((ob->parent) && (mask&DAG_RL_PARENT_MASK)){
+		if (ob->parent) {
 			node2 = dag_get_node(dag,ob->parent);
-			dag_add_relation(dag,node2,node,DAG_RL_PARENT);
+			
+			switch(ob->partype) {
+			case PARSKEL:
+				dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB);
+				break;
+			case PARVERT1: case PARVERT3: case PARBONE:
+				dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB);
+				break;
+			default:
+				if(ob->parent->type==OB_LATTICE) 
+					dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_OB);
+				else if(ob->parent->type==OB_CURVE) {
+					Curve *cu= ob->parent->data;
+					if(cu->flag & CU_PATH) 
+						dag_add_relation(dag,node2,node,DAG_RL_DATA_OB|DAG_RL_OB_OB);
+					else
+						dag_add_relation(dag,node2,node,DAG_RL_OB_OB);
+				}
+				else
+					dag_add_relation(dag,node2,node,DAG_RL_OB_OB);
+			}
 			addtoroot = 0;
 		}
-		if ((ob->track) && (mask&DAG_RL_TRACK_MASK)){
+		if (ob->track) {
 			node2 = dag_get_node(dag,ob->track);
-			dag_add_relation(dag,node2,node,DAG_RL_TRACK);
+			dag_add_relation(dag,node2,node,DAG_RL_OB_OB);
 			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;
-			
+		if (ob->type==OB_MBALL) {
+			Object *mom= find_basis_mball(ob);
+			if(mom!=ob) {
+				node2 = dag_get_node(dag, mom);
+				dag_add_relation(dag,node,node2,DAG_RL_DATA_DATA|DAG_RL_OB_DATA);  // mom depends on children!
+			}
 		}
-		
-		/* 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;
-					
-				}
+		else if (ob->type==OB_CURVE) {
+			Curve *cu= ob->data;
+			if(cu->bevobj) {
+				node2 = dag_get_node(dag, cu->bevobj);
+				dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
 			}
-		}	
+			if(cu->taperobj) {
+				node2 = dag_get_node(dag, cu->taperobj);
+				dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
+			}
+		}
+		else if(ob->type==OB_FONT) {
+			Curve *cu= ob->data;
+			if(cu->textoncurve) {
+				node2 = dag_get_node(dag, cu->textoncurve);
+				dag_add_relation(dag,node2,node,DAG_RL_DATA_DATA|DAG_RL_OB_DATA);
+			}
+		}
 		
+		for (con = ob->constraints.first; con; con=con->next){
+			if (constraint_has_target(con)) {
+				char *str;
+				node2 = dag_get_node(dag, get_constraint_target(con, &str));
+				if(con->type==CONSTRAINT_TYPE_FOLLOWPATH)
+					dag_add_relation(dag, node2, node, DAG_RL_DATA_OB|DAG_RL_OB_OB);
+				else
+					dag_add_relation(dag, node2, node, DAG_RL_OB_OB);
+				addtoroot = 0;
+			}
+		}
 		
 		if (addtoroot == 1 )
 			dag_add_relation(dag,scenenode,node,DAG_RL_SCENE);
-		
-		addtoroot = 1;
-		base= base->next;
 	}
 	
 	// cycle detection and solving
@@ -458,18 +460,20 @@ void free_forest(DagForest *Dag)
 
 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;
+	DagNode *node = forest->DagNode.first;
+	
+	while (node) {
+		if (node->ob == fob)
+			return node;
+		node = node->next;
+	}
+	return NULL;
 }
 
+static int ugly_hack_sorry= 1;	// prevent type check
+
 /* no checking of existance, use dag_find_node first or dag_get_node */
-DagNode * dag_add_node (DagForest *forest,void * fob)
+DagNode * dag_add_node (DagForest *forest, void * fob)
 {
 	DagNode *node;
 		
@@ -486,7 +490,7 @@ DagNode * dag_add_node (DagForest *forest,void * fob)
 		node->first_ancestor = NULL;
 		node->ancestor_count = 0;
 
-		node->type = GS(((ID *) fob)->name);
+		if(ugly_hack_sorry) node->type = GS(((ID *) fob)->name);	// sorry, done for pose sorting
 		if (forest->numNodes) {
 			((DagNode *) forest->DagNode.last)->next = node;
 			forest->DagNode.last = node;
@@ -540,7 +544,7 @@ DagNode * dag_get_sub_node (DagForest *forest,void * fob)
 	return node;
 }
 
-void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, dag_rel_type rel) 
+void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, short rel) 
 {
 	DagAdjList *itA = fob1->child;
 	
@@ -846,6 +850,7 @@ DagNodeQueue * graph_dfs(void)
 	  return(retqueue);
 }
 
+/* unused */
 int pre_and_post_DFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
 	DagNode *node;
 
@@ -933,84 +938,6 @@ int pre_and_post_source_DFS(DagForest *dag, short mask, DagNode *source, graph_a
 	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);
-			}	
-		}
-	}
-	
-	// temporal correction for circular dependancies
-	base = sce->base.first;
-	while (base) {
-		BLI_remlink(&sce->base,base);
-		BLI_addhead(&tempbase,base);
-		base = sce->base.first;
-	}
-	
-	sce->base = tempbase;
-	queue_delete(nqueue);
-}
-
 
 // used to get the obs owning a datablock
 struct DagNodeQueue *get_obparents(struct DagForest	*dag, void *ob) 
@@ -1020,7 +947,10 @@ struct DagNodeQueue *get_obparents(struct DagForest	*dag, void *ob)
 	DagAdjList *itA;
 
 	node = dag_find_node(dag,ob);
-	if (node->ancestor_count == 1) { // simple case
+	if(node==NULL) {
+		return NULL;
+	}
+	else 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
@@ -1082,7 +1012,7 @@ struct DagNodeQueue *get_all_childs(struct DagForest	*dag, void *ob)
 	int skip = 0;
 
 	nqueue = queue_create(DAGQUEUEALLOC);
-	retqueue = queue_create(MainDag->numNodes);
+	retqueue = queue_create(dag->numNodes); // was MainDag... why? (ton)
 	
 	node = dag->DagNode.first;
 	while(node) {
@@ -1092,45 +1022,47 @@ struct DagNodeQueue *get_all_childs(struct DagForest	*dag, void *ob)
 	
 	time = 1;
 	
-	node = dag_find_node(dag,ob);
-	
-	node->color = DAG_GRAY;
-	time++;
-	push_stack(nqueue,node);  
-	
-	while(nqueue->count) {
+	node = dag_find_node(dag,ob);   // could be done in loop above (ton)
+	if(node) { // can be null for newly added objects
 		
-		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;
-		}			
+		node->color = DAG_GRAY;
+		time++;
+		push_stack(nqueue,node);  
 		
-		if (!skip) {
-			node = pop_queue(nqueue);
-			node->color = DAG_BLACK;
+		while(nqueue->count) {
 			
-			time++;
-			push_stack(retqueue,node);			
+			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) {
+/* unused */
+short	are_obs_related(struct DagForest	*dag, void *ob1, void *ob2) {
 	DagNode * node;
 	DagAdjList *itA;
 	
@@ -1211,4 +1143,434 @@ void graph_print_adj_list(void)
 	}
 }
 
+/* ************************ API *********************** */
+
+/* sort the base list on dependency order */
+void DAG_scene_sort(struct Scene *sce)
+{
+	DagNode *node;
+	DagNodeQueue *nqueue;
+	DagAdjList *itA;
+	int time;
+	int skip = 0;
+	ListBase tempbase;
+	Base *base;
+	
+	tempbase.first= tempbase.last= NULL;
+	
+	build_dag(sce, DAG_RL_ALL_BUT_DATA);
+	
+	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);
+			}	
+		}
+	}
+	
+	// temporal correction for circular dependancies
+	base = sce->base.first;
+	while (base) {
+		BLI_remlink(&sce->base,base);
+		BLI_addhead(&tempbase,base);
+		//if(G.f & G_DEBUG) 
+			printf("cyclic %s\n", base->object->id.name);
+		base = sce->base.first;
+	}
+	
+	sce->base = tempbase;
+	queue_delete(nqueue);
+	
+	if(G.f & G_DEBUG) {
+		printf("\nordered\n");
+		for(base = sce->base.first; base; base= base->next) {
+			printf(" %s\n", base->object->id.name);
+		}
+	}
+}
+
+/* node was checked to have lasttime != curtime and is if type ID_OB */
+static void flush_update_node(DagNode *node, unsigned int layer, int curtime)
+{
+	DagAdjList *itA;
+	Object *ob, *obc;
+	int oldflag, changed=0;
+	unsigned int all_layer;
+	
+	node->lasttime= curtime;
+	
+	ob= node->ob;
+	if(ob->recalc & OB_RECALC) {
+		all_layer= ob->lay;
+		/* got an object node that changes, now check relations */
+		for(itA = node->child; itA; itA= itA->next) {
+			all_layer |= itA->lay;
+			/* the relationship is visible */
+			if(itA->lay & layer) {
+				if(itA->node->type==ID_OB) {
+					obc= itA->node->ob;
+					oldflag= obc->recalc;
+					
+					/* got a ob->obc relation, now check if flag needs flush */
+					if(ob->recalc & OB_RECALC_OB) {
+						if(itA->type & DAG_RL_OB_OB) {
+							//printf("ob %s changes ob %s\n", ob->id.name, obc->id.name);
+							obc->recalc |= OB_RECALC_OB;
+						}
+						if(itA->type & DAG_RL_OB_DATA) {
+							//printf("ob %s changes obdata %s\n", ob->id.name, obc->id.name);
+							obc->recalc |= OB_RECALC_DATA;
+						}
+					}
+					if(ob->recalc & OB_RECALC_DATA) {
+						if(itA->type & DAG_RL_DATA_OB) {
+							//printf("obdata %s changes ob %s\n", ob->id.name, obc->id.name);
+							obc->recalc |= OB_RECALC_OB;
+						}
+						if(itA->type & DAG_RL_DATA_DATA) {
+							//printf("obdata %s changes obdata %s\n", ob->id.name, obc->id.name);
+							obc->recalc |= OB_RECALC_DATA;
+						}
+					}
+					if(oldflag!=obc->recalc) changed= 1;
+				}
+			}
+		}
+		/* even nicer, we can clear recalc flags... but we don't for armatures, these can have poses that need pointer checks (read old file issue) */
+		if(ob->type!=OB_ARMATURE)
+			if((all_layer & layer)==0)
+				ob->recalc &= ~OB_RECALC;
+	}
+	else{
+		/* Object has not RECALC flag */
+		/* check case where child changes and parent forcing obdata to change */
+		/* could merge this in with loop above... (ton) */
+		for(itA = node->child; itA; itA= itA->next) {
+			/* the relationship is visible */
+			if(itA->lay & layer) {
+				if(itA->node->type==ID_OB) {
+					obc= itA->node->ob;
+					/* child moves */
+					if((obc->recalc & OB_RECALC)==OB_RECALC_OB) {
+						/* parent has deforming info */
+						if(itA->type & (DAG_RL_OB_DATA|DAG_RL_DATA_DATA)) {
+							// printf("parent %s changes ob %s\n", ob->id.name, obc->id.name);
+							obc->recalc |= OB_RECALC_DATA;
+						}
+					}
+				}
+			}
+		}
+	}
+	/* we only go deeper if node not checked or something changed  */
+	for(itA = node->child; itA; itA= itA->next) {
+		if(changed || itA->node->lasttime!=curtime) 
+			flush_update_node(itA->node, layer, curtime);
+	}
+}
+
+/* node was checked to have lasttime != curtime , and is of type ID_OB */
+static unsigned int flush_layer_node(DagNode *node, int curtime)
+{
+	DagAdjList *itA;
+	
+	node->lasttime= curtime;
+	node->lay= ((Object *)node->ob)->lay;
+	
+	for(itA = node->child; itA; itA= itA->next) {
+		if(itA->node->type==ID_OB) {
+			if(itA->node->lasttime!=curtime) {
+				itA->lay= flush_layer_node(itA->node, curtime);  // lay is only set once for each relation
+				//printf("layer %d for relation %s to %s\n", itA->lay, ((Object *)node->ob)->id.name, ((Object *)itA->node->ob)->id.name);
+			}
+			else itA->lay= itA->node->lay;
+			
+			node->lay |= itA->lay;
+		}
+	}
+
+	return node->lay;
+}
+
+/* flushes all recalc flags in objects down the dependency tree */
+void DAG_scene_flush_update(Scene *sce)
+{
+	DagNode *firstnode;
+	DagAdjList *itA;
+	int lasttime;
+	
+	firstnode= sce->theDag->DagNode.first;  // always scene node
+	
+	/* first we flush the layer flags */
+	sce->theDag->time++;	// so we know which nodes were accessed
+	lasttime= sce->theDag->time;
+	for(itA = firstnode->child; itA; itA= itA->next) {
+		if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) 
+			flush_layer_node(itA->node, lasttime);
+	}
+	
+	/* then we use the relationships + layer info to flush update events */
+	sce->theDag->time++;	// so we know which nodes were accessed
+	lasttime= sce->theDag->time;
+	for(itA = firstnode->child; itA; itA= itA->next) {
+		if(itA->node->lasttime!=lasttime && itA->node->type==ID_OB) 
+			flush_update_node(itA->node, sce->lay, lasttime);
+	}
+}
+
+/* flag all objects that need recalc, for changes in time for example */
+void DAG_scene_update_flags(Scene *sce, unsigned int lay)
+{
+	Base *base;
+	Object *ob;
+	
+	/* set ob flags where animated systems are */
+	for(base= sce->base.first; base; base= base->next) {
+		
+		/* now if DagNode were part of base, the node->lay could be checked... */
+		/* we do all now, since the scene_flush checks layers */
+		//if((base->lay & lay))  {
+			ob= base->object;
+			
+			if(ob->ipo) ob->recalc |= OB_RECALC_OB;
+			else if(ob->constraints.first) ob->recalc |= OB_RECALC_OB;
+			else if(ob->scriptlink.totscript) ob->recalc |= OB_RECALC_OB;
+			else if(ob->parent) {
+				if(ob->parent->type==OB_CURVE) ob->recalc |= OB_RECALC_OB;
+			}
+			
+			if(ob->action) ob->recalc |= OB_RECALC_DATA;
+			else if(ob->nlastrips.first) ob->recalc |= OB_RECALC_DATA;
+			else if(ob->softflag & OB_SB_ENABLE) ob->recalc |= OB_RECALC_DATA;
+			else {
+				Mesh *me;
+				Curve *cu;
+				Lattice *lt;
+				
+				switch(ob->type) {
+					case OB_MESH:
+						me= ob->data;
+						if(me->key) ob->recalc |= OB_RECALC_DATA;
+						else if(ob->effect.first) {
+							Effect *eff= ob->effect.first;
+							if(eff->type==EFF_WAVE) ob->recalc |= OB_RECALC_DATA;
+						}
+						break;
+					case OB_CURVE:
+					case OB_SURF:
+						cu= ob->data;
+						if(cu->key) ob->recalc |= OB_RECALC_DATA;
+						break;
+					case OB_LATTICE:
+						lt= ob->data;
+						if(lt->key) ob->recalc |= OB_RECALC_DATA;
+						break;
+				}
+			}
+		//}
+	}
+	DAG_scene_flush_update(sce);
+}
+
+/* flag this object and all its relations to recalc */
+/* if you need to do more objects, tag object yourself and
+   use DAG_scene_flush_update() in end */
+void DAG_object_flush_update(Scene *sce, Object *ob, short flag)
+{
+	Base *base;
+	
+	if(ob==NULL) return;
+	ob->recalc |= flag;
+	
+	/* all users of this ob->data should be checked */
+	if(flag & OB_RECALC_DATA) {
+		ID *id= ob->data;
+		if(id && id->us>1) {
+			for (base= sce->base.first; base; base= base->next) {
+				if (ob->data==base->object->data) {
+					base->object->recalc |= OB_RECALC_DATA;
+				}
+			}
+		}
+	}
+	
+	DAG_scene_flush_update(sce);
+}
+
+/* ******************* DAG FOR ARMATURE POSE ***************** */
+
+/* we assume its an armature with pose */
+void DAG_pose_sort(Object *ob)
+{
+	bPose *pose= ob->pose;
+	bPoseChannel *pchan;
+	bConstraint *con;
+	DagNode *node;
+	DagNode *node2, *node3;
+	DagNode *rootnode;
+	DagForest *dag;
+	DagNodeQueue *nqueue;
+	DagAdjList *itA;
+	ListBase tempbase;
+	int skip = 0;
+	
+	dag = dag_init();
+	ugly_hack_sorry= 0;	// no ID structs
+
+	rootnode = dag_add_node(dag, NULL);	// node->ob becomes NULL
+	
+	/* we add the hierarchy and the constraints */
+	for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
+		int addtoroot = 1;
+		
+		node = dag_get_node(dag, pchan);
+		
+		if(pchan->parent) {
+			node2 = dag_get_node(dag, pchan->parent);
+			dag_add_relation(dag, node2, node, 0);
+			addtoroot = 0;
+		}
+		for (con = pchan->constraints.first; con; con=con->next){
+			if (constraint_has_target(con)) {
+				char *subtarget;
+				Object *target = get_constraint_target(con, &subtarget);
+				
+				if (target==ob && subtarget) {
+					bPoseChannel *target= get_pose_channel(ob->pose, subtarget);
+					if(target) {
+						node2= dag_get_node(dag, target);
+						dag_add_relation(dag, node2, node, 0);
+						
+						if(con->type==CONSTRAINT_TYPE_KINEMATIC) {
+							bPoseChannel *par= pchan->parent;
+							
+							while(par) {
+								node3= dag_get_node(dag, par);
+								dag_add_relation(dag, node2, node3, 0);
+								
+								if(par->bone->flag & BONE_IK_TOPARENT)
+									par= par->parent;
+								else break;
+							}
+						}
+					}
+				}
+			}
+		}
+		if (addtoroot == 1 )
+			dag_add_relation(dag, rootnode, node, 0);
+	}
+
+	/* now we try to sort... */
+	tempbase.first= tempbase.last= NULL;
+
+	nqueue = queue_create(DAGQUEUEALLOC);
+	
+	/* tag nodes unchecked */
+	for(node = dag->DagNode.first; node; node= node->next) 
+		node->color = DAG_WHITE;
+	
+	node = dag->DagNode.first;
+	
+	node->color = DAG_GRAY;
+	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->color = DAG_GRAY;
+				push_stack(nqueue,itA->node);
+				skip = 1;
+				break;
+			} 
+			itA = itA->next;
+		}			
+		
+		if (!skip) {
+			if (node) {
+				node = pop_queue(nqueue);
+				if (node->ob == NULL)	// we are done
+					break ;
+				node->color = DAG_BLACK;
+				
+				/* put node in new list */
+				BLI_remlink(&pose->chanbase, node->ob);
+				BLI_addhead(&tempbase, node->ob);
+			}	
+		}
+	}
+	
+	// temporal correction for circular dependancies
+	while(pose->chanbase.first) {
+		pchan= pose->chanbase.first;
+		BLI_remlink(&pose->chanbase, pchan);
+		BLI_addhead(&tempbase, pchan);
+
+		printf("cyclic %s\n", pchan->name);
+	}
+	
+	pose->chanbase = tempbase;
+	queue_delete(nqueue);
+	
+//	printf("\nordered\n");
+//	for(pchan = pose->chanbase.first; pchan; pchan= pchan->next) {
+//		printf(" %s\n", pchan->name);
+//	}
+	
+	free_forest( dag );
+	MEM_freeN( dag );
+	
+	ugly_hack_sorry= 1;
+}
+
+