Use tree length as parameter for multi resolution filtering.

This is the begining of the simplification phase (meaning less parameters to mess up users)

2 files changed, 57 insertions, 1 deletions

diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h
index ae99ad5f5c7..d309d73fbee 100644
--- a/source/blender/blenlib/BLI_graph.h
+++ b/source/blender/blenlib/BLI_graph.h
@@ -24,6 +24,8 @@ typedef struct BGraph {
 	ListBase	arcs;
 	ListBase	nodes;
 	
+	float length;
+	
 	/* function pointer to deal with custom fonctionnality */
 	FreeArc			free_arc;
 	FreeNode		free_node;
@@ -79,6 +81,8 @@ void BLI_freeAdjacencyList(BGraph *rg);
 int BLI_FlagSubgraphs(BGraph *graph);
 
 int BLI_subtreeShape(BNode *node, BArc *rootArc, int include_root);
+float BLI_subtreeLength(BNode *node, BArc *rootArc);
+void BLI_calcGraphLength(BGraph *graph);
 
 void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced);
 void BLI_removeDoubleNodes(BGraph *graph, float limit);
@@ -88,7 +92,6 @@ BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v);
 int	BLI_isGraphCyclic(BGraph *graph);
 
 /*------------ Symmetry handling ------------*/
-//	float limit = G.scene->toolsettings->skgen_symmetry_limit;
 void BLI_markdownSymmetry(BGraph *graph, BNode *root_node, float limit);
 
 void BLI_mirrorAlongAxis(float v[3], float center[3], float axis[3]);
diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c
index 9bdf286d248..a3089369c22 100644
--- a/source/blender/blenlib/intern/graph.c
+++ b/source/blender/blenlib/intern/graph.c
@@ -358,6 +358,59 @@ int BLI_subtreeShape(BNode *node, BArc *rootArc, int include_root)
 	}
 }
 
+float BLI_subtreeLength(BNode *node, BArc *rootArc)
+{
+	float length = 0;
+	int i;
+
+	for(i = 0; i < node->degree; i++)
+	{
+		BArc *arc = node->arcs[i];
+		
+		/* don't go back on the root arc */
+		if (arc != rootArc)
+		{
+			length = MAX2(length, BLI_subtreeLength(BLI_otherNode(arc, node), arc));
+		}
+	}
+	
+	if (rootArc)
+	{
+		length += rootArc->length;
+	}
+	
+	return length;
+}
+
+void BLI_calcGraphLength(BGraph *graph)
+{
+	if (BLI_isGraphCyclic(graph) == 0)
+	{
+		float length = 0;
+		int nb_subgraphs;
+		int i;
+		
+		nb_subgraphs = BLI_FlagSubgraphs(graph);
+		
+		for (i = 1; i <= nb_subgraphs; i++)
+		{
+			BNode *node;
+			
+			for (node = graph->nodes.first; node; node = node->next)
+			{
+				/* start on an external node  of the subgraph */
+				if (node->flag == i && node->degree == 1)
+				{
+					length = MAX2(length, BLI_subtreeLength(node, NULL));
+					break;
+				}
+			}
+		}
+		
+		graph->length = length;
+	}
+}
+
 /********************************* SYMMETRY DETECTION **************************************************/
 
 void markdownSymmetryArc(BGraph *graph, BArc *arc, BNode *node, int level, float limit);