Control bone commit from yesterday broke root bones. This is now fixed in a much more elegant way.

Remove yeh ol' primary symmetry axis flipping and replace by a smarter check on both armature and mesh arcs (works better for partial retargetting).

5 files changed, 192 insertions, 27 deletions

diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h
index 0f75701a284..160c2e04cf5 100644
--- a/source/blender/blenlib/BLI_graph.h
+++ b/source/blender/blenlib/BLI_graph.h
@@ -93,7 +93,9 @@ float BLI_subtreeLength(BNode *node);
 void BLI_calcGraphLength(BGraph *graph);
 
 void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced);
+void BLI_replaceNodeInArc(BGraph *graph, BArc *arc, BNode *node_src, BNode *node_replaced);
 void BLI_removeDoubleNodes(BGraph *graph, float limit);
+BNode * BLI_FindNodeByPosition(BGraph *graph, float *p, float limit);
 
 BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v);
 
diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c
index 277a9300f5b..cb8f4b59d8b 100644
--- a/source/blender/blenlib/intern/graph.c
+++ b/source/blender/blenlib/intern/graph.c
@@ -194,6 +194,34 @@ int BLI_hasAdjacencyList(BGraph *rg)
 	return 1;
 }
 
+void BLI_replaceNodeInArc(BGraph *graph, BArc *arc, BNode *node_src, BNode *node_replaced)
+{
+	if (arc->head == node_replaced)
+	{
+		arc->head = node_src;
+		node_src->degree++;
+	}
+
+	if (arc->tail == node_replaced)
+	{
+		arc->tail = node_src;
+		node_src->degree++;
+	}
+	
+	if (arc->head == arc->tail)
+	{
+		node_src->degree -= 2;
+		
+		graph->free_arc(arc);
+		BLI_freelinkN(&graph->arcs, arc);
+	}
+
+	if (node_replaced->degree == 0)
+	{
+		BLI_removeNode(graph, node_replaced);
+	}
+}
+
 void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced)
 {
 	BArc *arc, *next_arc;
@@ -222,6 +250,11 @@ void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced)
 			BLI_freelinkN(&graph->arcs, arc);
 		}
 	}
+	
+	if (node_replaced->degree == 0)
+	{
+		BLI_removeNode(graph, node_replaced);
+	}
 }
 
 void BLI_removeDoubleNodes(BGraph *graph, float limit)
@@ -235,13 +268,29 @@ void BLI_removeDoubleNodes(BGraph *graph, float limit)
 			if (node_replaced != node_src && VecLenf(node_replaced->p, node_src->p) <= limit)
 			{
 				BLI_replaceNode(graph, node_src, node_replaced);
-				
-				BLI_removeNode(graph, node_replaced);
 			}
 		}
 	}
 	
 }
+
+BNode * BLI_FindNodeByPosition(BGraph *graph, float *p, float limit)
+{
+	BNode *closest_node = NULL, *node;
+	float min_distance;
+	
+	for(node = graph->nodes.first; node; node = node->next)
+	{
+		float distance = VecLenf(p, node->p); 
+		if (distance <= limit && (closest_node == NULL || distance < min_distance))
+		{
+			closest_node = node;
+			min_distance = distance;
+		}
+	}
+	
+	return closest_node;
+}
 /************************************* SUBGRAPH DETECTION **********************************************/
 
 void flagSubgraph(BNode *node, int subgraph)
@@ -556,7 +605,7 @@ static void testRadialSymmetry(BGraph *graph, BNode* root_node, RadialArc* ring,
 		for (i = 0; i < total; i++)
 		{
 			ring[i].arc->symmetry_group = group;
-			ring[i].arc->symmetry_flag = i;
+			ring[i].arc->symmetry_flag = SYM_SIDE_RADIAL + i;
 		}
 
 		if (graph->radial_symmetry)
@@ -837,7 +886,7 @@ static void markdownSecondarySymmetry(BGraph *graph, BNode *node, int depth, int
 	float axis[3] = {0, 0, 0};
 	int count = 0;
 	int i;
-
+	
 	/* count the number of branches in this symmetry group
 	 * and determinte the axis of symmetry
 	 *  */	
@@ -869,7 +918,7 @@ static void markdownSecondarySymmetry(BGraph *graph, BNode *node, int depth, int
 	{
 		handleRadialSymmetry(graph, node, depth, axis, limit);
 	}
-	
+		
 	/* markdown secondary symetries */	
 	for (i = 0; i < node->degree; i++)
 	{
diff --git a/source/blender/include/reeb.h b/source/blender/include/reeb.h
index 76a7bfefe2f..675e1b099c8 100644
--- a/source/blender/include/reeb.h
+++ b/source/blender/include/reeb.h
@@ -174,6 +174,7 @@ void BIF_GlobalReebGraphFromEditMesh(void);
 void BIF_GlobalReebFree(void);
 
 ReebNode *BIF_otherNodeFromIndex(ReebArc *arc, ReebNode *node);
+ReebNode *BIF_NodeFromIndex(ReebArc *arc, ReebNode *node);
 ReebNode *BIF_lowestLevelNode(ReebNode *node);
 
 void REEB_freeGraph(ReebGraph *rg);
diff --git a/source/blender/src/autoarmature.c b/source/blender/src/autoarmature.c
index ffb82d4b704..ca9443522a2 100644
--- a/source/blender/src/autoarmature.c
+++ b/source/blender/src/autoarmature.c
@@ -78,7 +78,7 @@ struct RigArc;
 struct RigEdge;
 
 #define NB_THREADS 4
-//#define USE_THREADS
+#define USE_THREADS
 
 typedef struct RigGraph {
 	ListBase	arcs;
@@ -159,6 +159,7 @@ typedef struct RigControl {
 typedef struct RetargetParam {
 	RigGraph	*rigg;
 	RigArc		*iarc;
+	RigNode		*inode_start;
 } RetargetParam;
 
 typedef enum 
@@ -401,6 +402,28 @@ static int RIG_parentControl(RigControl *ctrl, EditBone *parent)
 {
 	if (parent)
 	{
+		/* if there's already a parent, overwrite only if new parent is higher in the chain */
+		if (ctrl->parent)
+		{
+			EditBone *bone = NULL;
+			
+			for (bone = ctrl->parent; bone; bone = bone->parent)
+			{
+				/* if parent is in the chain, break and use that one */
+				if (bone == parent)
+				{
+					break;
+				}
+			}
+			
+			/* not in chain, don't update parent */
+			if (bone == NULL)
+			{
+				return 0;
+			}
+		}
+		
+		
 		ctrl->parent = parent;
 		
 		VecSubf(ctrl->offset, ctrl->bone->head, ctrl->parent->tail);
@@ -559,6 +582,61 @@ static void RIG_removeNormalNodes(RigGraph *rg)
 	}
 }
 
+static void RIG_removeUneededOffsets(RigGraph *rg)
+{
+	RigArc *arc;
+	
+	for (arc = rg->arcs.first; arc; arc = arc->next)
+	{
+		RigEdge *first_edge, *last_edge;
+		
+		first_edge = arc->edges.first;
+		last_edge = arc->edges.last;
+		
+		if (first_edge->bone == NULL && VecLenf(first_edge->tail, arc->head->p) <= 0.001)
+		{
+			BLI_remlink(&arc->edges, first_edge);
+			MEM_freeN(first_edge);
+		}
+		else if (arc->head->degree == 1 && first_edge->bone == NULL)
+		{
+			RigNode *new_node = (RigNode*)BLI_FindNodeByPosition((BGraph*)rg, first_edge->tail, 0.001);
+			
+			if (new_node)
+			{
+				BLI_remlink(&arc->edges, first_edge);
+				MEM_freeN(first_edge);
+				BLI_replaceNodeInArc((BGraph*)rg, (BArc*)arc, (BNode*)arc->head, (BNode*)new_node);
+			}
+		}
+		
+		if (last_edge->bone == NULL && VecLenf(last_edge->head, arc->tail->p) <= 0.001)
+		{
+			BLI_remlink(&arc->edges, last_edge);
+			MEM_freeN(last_edge);
+		}
+		else if (arc->tail->degree == 1 && last_edge->bone == NULL)
+		{
+			RigNode *new_node = (RigNode*)BLI_FindNodeByPosition((BGraph*)rg, last_edge->head, 0.001);
+			
+			if (new_node)
+			{
+				RigEdge *previous_edge = last_edge->prev;
+				
+				BLI_remlink(&arc->edges, last_edge);
+				MEM_freeN(last_edge);
+				BLI_replaceNodeInArc((BGraph*)rg, (BArc*)arc, (BNode*)arc->tail, (BNode*)new_node);
+				
+				/* set previous angle to 0, since there's no following edges */
+				if (previous_edge)
+				{
+					previous_edge->angle = 0;
+				}
+			}
+		}
+	}
+}
+
 static void RIG_arcFromBoneChain(RigGraph *rg, ListBase *list, EditBone *root_bone, RigNode *starting_node)
 {
 	EditBone *bone, *last_bone = root_bone;
@@ -587,7 +665,7 @@ static void RIG_arcFromBoneChain(RigGraph *rg, ListBase *list, EditBone *root_bo
 				}
 			}
 			
-			if (bone->parent && (bone->flag & BONE_CONNECTED) == 0 && (bone->parent->flag & BONE_NO_DEFORM) == 0)
+			if (bone->parent && (bone->flag & BONE_CONNECTED) == 0)
 			{
 				RIG_addEdgeToArc(arc, bone->head, NULL);
 			}
@@ -616,8 +694,7 @@ static void RIG_arcFromBoneChain(RigGraph *rg, ListBase *list, EditBone *root_bo
 			{
 				end_node = newRigNodeTail(rg, arc, bone->tail);
 			}
-			/* only create a new node if the parent was a deform bone */
-			else if ((bone->flag & BONE_NO_DEFORM) == 0)
+			else
 			{
 				end_node = newRigNode(rg, bone->tail);
 			}
@@ -773,6 +850,8 @@ static RigGraph *armatureToGraph(Object *ob, ListBase *list)
 	
 	RIG_removeNormalNodes(rg);
 	
+	RIG_removeUneededOffsets(rg);
+	
 	BLI_buildAdjacencyList((BGraph*)rg);
 	
 	RIG_findHead(rg);
@@ -857,7 +936,7 @@ static void repositionBone(RigGraph *rigg, EditBone *bone, float vec0[3], float
 }
 
 static RetargetMode detectArcRetargetMode(RigArc *arc);
-static void retargetArctoArcLength(RigGraph *rigg, RigArc *iarc);
+static void retargetArctoArcLength(RigGraph *rigg, RigArc *iarc, RigNode *inode_start);
 
 
 static RetargetMode detectArcRetargetMode(RigArc *iarc)
@@ -1223,7 +1302,23 @@ static int neighbour(int nb_joints, float *cost_cube, int *moving_joint, int *mo
 	return 1;
 }
 
-static void retargetArctoArcAggresive(RigGraph *rigg, RigArc *iarc)
+static int testFlipArc(RigArc *iarc, RigNode *inode_start)
+{
+	ReebArc *earc = iarc->link_mesh;
+	ReebNode *enode_start = BIF_NodeFromIndex(earc, inode_start->link_mesh);
+	
+	/* no flip needed if both nodes are the same */
+	if ((enode_start == earc->head && inode_start == iarc->head) || (enode_start == earc->tail && inode_start == iarc->tail))
+	{
+		return 0;
+	}
+	else
+	{
+		return 1;
+	}
+}
+
+static void retargetArctoArcAggresive(RigGraph *rigg, RigArc *iarc, RigNode *inode_start)
 {
 	ReebArcIterator iter;
 	RigEdge *edge;
@@ -1238,7 +1333,6 @@ static void retargetArctoArcAggresive(RigGraph *rigg, RigArc *iarc)
 	int *positions;
 	int nb_edges = BLI_countlist(&iarc->edges);
 	int nb_joints = nb_edges - 1;
-	int symmetry_axis = 0;
 	RetargetMethod method = METHOD_ANNEALING; //G.scene->toolsettings->skgen_optimisation_method;
 	int i;
 
@@ -1247,10 +1341,10 @@ static void retargetArctoArcAggresive(RigGraph *rigg, RigArc *iarc)
 	cost_cache = MEM_callocN(sizeof(float) * nb_edges, "Cost cache");
 	vec_cache = MEM_callocN(sizeof(float*) * (nb_edges + 1), "Vec cache");
 	
-	/* symmetry axis */
-	if (earc->symmetry_level == 1 && iarc->symmetry_level == 1)
+//	/* symmetry axis */
+//	if (earc->symmetry_level == 1 && iarc->symmetry_level == 1)
+	if (testFlipArc(iarc, inode_start))
 	{
-		symmetry_axis = 1;
 		node_start = earc->tail;
 		node_end = earc->head;
 	}
@@ -1586,7 +1680,7 @@ static void retargetArctoArcAggresive(RigGraph *rigg, RigArc *iarc)
 	MEM_freeN(vec_cache);
 }
 
-static void retargetArctoArcLength(RigGraph *rigg, RigArc *iarc)
+static void retargetArctoArcLength(RigGraph *rigg, RigArc *iarc, RigNode *inode_start)
 {
 	ReebArcIterator iter;
 	ReebArc *earc = iarc->link_mesh;
@@ -1597,13 +1691,12 @@ static void retargetArctoArcLength(RigGraph *rigg, RigArc *iarc)
 	float *vec0 = NULL;
 	float *vec1 = NULL;
 	float *previous_vec = NULL;
-	int symmetry_axis = 0;
 
 	
-	/* symmetry axis */
-	if (earc->symmetry_level == 1 && iarc->symmetry_level == 1)
+//	/* symmetry axis */
+//	if (earc->symmetry_level == 1 && iarc->symmetry_level == 1)
+	if (testFlipArc(iarc, inode_start))
 	{
-		symmetry_axis = 1;
 		node_start = (ReebNode*)earc->tail;
 		node_end = (ReebNode*)earc->head;
 	}
@@ -1671,19 +1764,23 @@ static void retargetArctoArcLength(RigGraph *rigg, RigArc *iarc)
 	}
 }
 
-static void retargetArctoArc(RigGraph *rigg, RigArc *iarc)
+static void retargetArctoArc(RigGraph *rigg, RigArc *iarc, RigNode *inode_start)
 {
 #ifdef USE_THREADS
 	RetargetParam *p = MEM_callocN(sizeof(RetargetParam), "RetargetParam");
 	
 	p->rigg = rigg;
 	p->iarc = iarc;
+	p->inode_start = inode_start;
 	
 	BLI_insert_work(rigg->worker, p);
 #else
 	RetargetParam p;
+
 	p.rigg = rigg;
 	p.iarc = iarc;
+	p.inode_start = inode_start;
+	
 	exec_retargetArctoArc(&p);
 #endif
 }
@@ -1693,6 +1790,7 @@ void *exec_retargetArctoArc(void *param)
 	RetargetParam *p = (RetargetParam*)param;
 	RigGraph *rigg = p->rigg;
 	RigArc *iarc = p->iarc;	
+	RigNode *inode_start = p->inode_start;
 	ReebArc *earc = iarc->link_mesh;
 	
 	if (BLI_countlist(&iarc->edges) == 1)
@@ -1700,8 +1798,9 @@ void *exec_retargetArctoArc(void *param)
 		RigEdge *edge = iarc->edges.first;
 		EditBone *bone = edge->bone;
 		
-		/* symmetry axis */
-		if (earc->symmetry_level == 1 && iarc->symmetry_level == 1)
+//		/* symmetry axis */
+//		if (earc->symmetry_level == 1 && iarc->symmetry_level == 1)
+		if (testFlipArc(iarc, inode_start))
 		{
 			repositionBone(rigg, bone, earc->tail->p, earc->head->p);
 		}
@@ -1717,11 +1816,11 @@ void *exec_retargetArctoArc(void *param)
 		
 		if (mode == RETARGET_AGGRESSIVE)
 		{
-			retargetArctoArcAggresive(rigg, iarc);
+			retargetArctoArcAggresive(rigg, iarc, inode_start);
 		}
 		else
 		{		
-			retargetArctoArcLength(rigg, iarc);
+			retargetArctoArcLength(rigg, iarc, inode_start);
 		}
 	}
 
@@ -1882,7 +1981,7 @@ static void retargetSubgraph(RigGraph *rigg, RigArc *start_arc, RigNode *start_n
 		ReebNode *enode = start_node->link_mesh;
 		ReebArc *earc = start_arc->link_mesh;
 		
-		retargetArctoArc(rigg, start_arc);
+		retargetArctoArc(rigg, start_arc, start_node);
 		
 		enode = BIF_otherNodeFromIndex(earc, enode);
 		inode = (RigNode*)BLI_otherNode((BArc*)start_arc, (BNode*)inode);
@@ -1934,6 +2033,9 @@ void BIF_retargetArmature()
 	Object *ob;
 	Base *base;
 	ReebGraph *reebg;
+	double start_time, end_time;
+	
+	start_time = PIL_check_seconds_timer();
 	
 	reebg = BIF_ReebGraphMultiFromEditMesh();
 	
@@ -1982,6 +2084,12 @@ void BIF_retargetArmature()
 
 	REEB_freeGraph(reebg);
 	
+	end_time = PIL_check_seconds_timer();
+
+	printf("-----------\n");
+	printf("runtime: %.3f\n", end_time - start_time);
+	printf("-----------\n");
+	
 	BIF_undo_push("Retarget Skeleton");
 	
 	exit_editmode(EM_FREEDATA|EM_FREEUNDO|EM_WAITCURSOR); // freedata, and undo
diff --git a/source/blender/src/reeb.c b/source/blender/src/reeb.c
index 6f3ab5e8561..97c05a74380 100644
--- a/source/blender/src/reeb.c
+++ b/source/blender/src/reeb.c
@@ -250,6 +250,11 @@ ReebNode *BIF_otherNodeFromIndex(ReebArc *arc, ReebNode *node)
 	return (arc->head->index == node->index) ? arc->tail : arc->head;
 }
 
+ReebNode *BIF_NodeFromIndex(ReebArc *arc, ReebNode *node)
+{
+	return (arc->head->index == node->index) ? arc->head : arc->tail;
+}
+
 ReebNode *BIF_lowestLevelNode(ReebNode *node)
 {
 	while (node->link_down)
@@ -3581,7 +3586,7 @@ void REEB_draw()
 		{
 			VecLerpf(vec, arc->head->p, arc->tail->p, 0.5f);
 		
-			s += sprintf(s, "%i ", i);
+			s += sprintf(s, "%i (%i-%i-%i) ", i, arc->symmetry_level, arc->symmetry_flag, arc->symmetry_group);
 		
 			if (G.scene->toolsettings->skgen_options & SKGEN_DISP_WEIGHT)
 			{