Make subgraph tagging use own index, to not interfere with flagging used to prevent backtracking in different other functions

Better deal with chains starting with control bones

2 files changed, 38 insertions, 13 deletions

diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h
index 59e73004b8b..0f75701a284 100644
--- a/source/blender/blenlib/BLI_graph.h
+++ b/source/blender/blenlib/BLI_graph.h
@@ -40,6 +40,8 @@ typedef struct BNode {
 
 	int degree;
 	struct BArc **arcs;
+	
+	int subgraph_index;
 
 	int symmetry_level;
 	int symmetry_flag;
@@ -70,6 +72,8 @@ BNode *BLI_otherNode(BArc *arc, BNode *node);
 void BLI_freeNode(BGraph *graph, BNode *node);
 void BLI_removeNode(BGraph *graph, BNode *node);
 
+void BLI_removeArc(BGraph *graph, BArc *arc);
+
 void BLI_flagNodes(BGraph *graph, int flag);
 void BLI_flagArcs(BGraph *graph, int flag);
 
@@ -84,7 +88,7 @@ void BLI_ReflagSubgraph(BGraph *graph, int old_subgraph, int new_subgraph);
 
 #define SHAPE_RADIX 10 /* each shape level is encoded this base */
 
-int BLI_subtreeShape(BNode *node, BArc *rootArc, int include_root);
+int BLI_subtreeShape(BGraph *graph, BNode *node, BArc *rootArc, int include_root);
 float BLI_subtreeLength(BNode *node);
 void BLI_calcGraphLength(BGraph *graph);
 
diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c
index 80d770e1034..277a9300f5b 100644
--- a/source/blender/blenlib/intern/graph.c
+++ b/source/blender/blenlib/intern/graph.c
@@ -64,6 +64,16 @@ BNode *BLI_otherNode(BArc *arc, BNode *node)
 	return (arc->head == node) ? arc->tail : arc->head;
 }
 
+void BLI_removeArc(BGraph *graph, BArc *arc)
+{
+	if (graph->free_arc)
+	{
+		graph->free_arc(arc);
+	}
+
+	BLI_freelinkN(&graph->arcs, arc);
+}
+
 void BLI_flagNodes(BGraph *graph, int flag)
 {
 	BNode *node;
@@ -236,12 +246,12 @@ void BLI_removeDoubleNodes(BGraph *graph, float limit)
 
 void flagSubgraph(BNode *node, int subgraph)
 {
-	if (node->flag == 0)
+	if (node->subgraph_index == 0)
 	{
 		BArc *arc;
 		int i;
 		
-		node->flag = subgraph;
+		node->subgraph_index = subgraph;
 		
 		for(i = 0; i < node->degree; i++)
 		{
@@ -261,11 +271,14 @@ int BLI_FlagSubgraphs(BGraph *graph)
 		BLI_buildAdjacencyList(graph);
 	}
 	
-	BLI_flagNodes(graph, 0);
+	for(node = graph->nodes.first; node; node = node->next)
+	{
+		node->subgraph_index = 0;
+	}
 	
 	for (node = graph->nodes.first; node; node = node->next)
 	{
-		if (node->flag == 0)
+		if (node->subgraph_index == 0)
 		{
 			subgraph++;
 			flagSubgraph(node, subgraph);
@@ -360,14 +373,16 @@ BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v)
 
 /*********************************** GRAPH AS TREE FUNCTIONS *******************************************/
 
-int BLI_subtreeShape(BNode *node, BArc *rootArc, int include_root)
+int subtreeShape(BNode *node, BArc *rootArc, int include_root)
 {
 	int depth = 0;
 	
+	node->flag = 1;
+	
 	if (include_root)
 	{
 		BNode *newNode = BLI_otherNode(rootArc, node);
-		return BLI_subtreeShape(newNode, rootArc, 0);
+		return subtreeShape(newNode, rootArc, 0);
 	}
 	else
 	{
@@ -383,12 +398,12 @@ int BLI_subtreeShape(BNode *node, BArc *rootArc, int include_root)
 			for(i = 0; i < node->degree; i++)
 			{
 				BArc *arc = node->arcs[i];
+				BNode *newNode = BLI_otherNode(arc, node);
 				
-				/* only arcs that go down the tree */
-				if (arc != rootArc)
+				/* stop immediate and cyclic backtracking */
+				if (arc != rootArc && newNode->flag == 0)
 				{
-					BNode *newNode = BLI_otherNode(arc, node);
-					depth += BLI_subtreeShape(newNode, arc, 0);
+					depth += subtreeShape(newNode, arc, 0);
 				}
 			}
 		}
@@ -397,6 +412,12 @@ int BLI_subtreeShape(BNode *node, BArc *rootArc, int include_root)
 	}
 }
 
+int BLI_subtreeShape(BGraph *graph, BNode *node, BArc *rootArc, int include_root)
+{
+	BLI_flagNodes(graph, 0);
+	return subtreeShape(node, rootArc, include_root);
+}
+
 float BLI_subtreeLength(BNode *node)
 {
 	float length = 0;
@@ -434,7 +455,7 @@ void BLI_calcGraphLength(BGraph *graph)
 		for (node = graph->nodes.first; node; node = node->next)
 		{
 			/* start on an external node  of the subgraph */
-			if (node->flag == i && node->degree == 1)
+			if (node->subgraph_index == i && node->degree == 1)
 			{
 				float subgraph_length = BLI_subtreeLength(node);
 				length = MAX2(length, subgraph_length);
@@ -883,7 +904,7 @@ void markdownSymmetryArc(BGraph *graph, BArc *arc, BNode *node, int level, float
 			BNode *connectedNode = BLI_otherNode(connectedArc, node);
 			
 			/* symmetry level is positive value, negative values is subtree depth */
-			connectedArc->symmetry_level = -BLI_subtreeShape(connectedNode, connectedArc, 0);
+			connectedArc->symmetry_level = -BLI_subtreeShape(graph, connectedNode, connectedArc, 0);
 		}
 	}