Remove some debugging prints

Better symmetry detection using subtree shapes instead of depth
Fix the bug with flipping arcs caused by internal filtering

3 files changed, 77 insertions, 128 deletions

diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h
index b1e4a9fec75..44131fbbff8 100644
--- a/source/blender/blenlib/BLI_graph.h
+++ b/source/blender/blenlib/BLI_graph.h
@@ -72,6 +72,7 @@ void BLI_flagArcs(BGraph *graph, int flag);
 
 int BLI_hasAdjacencyList(BGraph *rg);
 void BLI_buildAdjacencyList(BGraph *rg);
+void BLI_rebuildAdjacencyList(BGraph* rg);
 void BLI_freeAdjacencyList(BGraph *rg);
 
 int BLI_FlagSubgraphs(BGraph *graph);
diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c
index 44b74122371..8c7e8ce8cd6 100644
--- a/source/blender/blenlib/intern/graph.c
+++ b/source/blender/blenlib/intern/graph.c
@@ -84,6 +84,12 @@ static void addArcToNodeAdjacencyList(BNode *node, BArc *arc)
 	node->flag++;
 }
 
+void BLI_rebuildAdjacencyList(BGraph *rg)
+{
+	BLI_freeAdjacencyList(rg);
+	BLI_buildAdjacencyList(rg);
+}
+
 void BLI_buildAdjacencyList(BGraph *rg)
 {
 	BNode *node;
@@ -310,7 +316,7 @@ BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v)
 
 /*********************************** GRAPH AS TREE FUNCTIONS *******************************************/
 
-int BLI_subtreeDepth(BNode *node, BArc *rootArc)
+int BLI_subtreeShape(BNode *node, BArc *rootArc)
 {
 	int depth = 0;
 	
@@ -331,12 +337,14 @@ int BLI_subtreeDepth(BNode *node, BArc *rootArc)
 			if (arc != rootArc)
 			{
 				BNode *newNode = BLI_otherNode(arc, node);
-				depth = MAX2(depth, BLI_subtreeDepth(newNode, arc));
+				//depth = MAX2(depth, BLI_subtreeShape(newNode, arc));
+				depth += BLI_subtreeShape(newNode, arc);
 			}
 		}
 	}
 	
-	return depth + 1; //BLI_countlist(&rootArc->edges);
+	//return depth + 1;
+	return 10 * depth + 1;
 }
 
 /********************************* SYMMETRY DETECTION **************************************************/
@@ -519,11 +527,6 @@ static void handleRadialSymmetry(BGraph *graph, BNode *root_node, int depth, flo
 			}
 		}
 	}
-	
-	for (i = 0; i < total; i++)
-	{
-		printf("length %f\n", ring[i].arc->length);
-	}
 
 	/* Dispatch to specific symmetry tests */
 	first = 0;
@@ -556,7 +559,6 @@ static void handleRadialSymmetry(BGraph *graph, BNode *root_node, int depth, flo
 
 			if (sub_total == 1)
 			{
-				printf("no dispatch\n");
 				/* NOTHING TO DO */
 			}
 			else if (sub_total == 2)
@@ -564,8 +566,6 @@ static void handleRadialSymmetry(BGraph *graph, BNode *root_node, int depth, flo
 				BArc *arc1, *arc2;
 				BNode *node1, *node2;
 				
-				printf("dispatch axial\n");
-
 				arc1 = ring[first].arc;
 				arc2 = ring[last].arc;
 				
@@ -579,8 +579,6 @@ static void handleRadialSymmetry(BGraph *graph, BNode *root_node, int depth, flo
 				RadialArc *sub_ring = MEM_callocN(sizeof(RadialArc) * sub_total, "radial symmetry ring");
 				int sub_i;
 				
-				printf("dispatch radial sub ring\n");
-
 				/* fill in the sub ring */
 				for (sub_i = 0; sub_i < sub_total; sub_i++)
 				{
@@ -593,8 +591,6 @@ static void handleRadialSymmetry(BGraph *graph, BNode *root_node, int depth, flo
 			}
 			else if (sub_total == total)
 			{
-				printf("dispatch radial full ring\n");
-
 				testRadialSymmetry(graph, root_node, ring, total, axis, limit, group);
 			}
 			
@@ -660,7 +656,7 @@ static void testAxialSymmetry(BGraph *graph, BNode* root_node, BNode* node1, BNo
 	}
 	else
 	{
-		printf("not symmetric\n");
+		/* NOT SYMMETRIC */
 	}
 }
 
@@ -700,8 +696,6 @@ static void handleAxialSymmetry(BGraph *graph, BNode *root_node, int depth, floa
 		return;
 	}
 	
-	printf("symmetry length %f <> %f\n", arc1->length, arc2->length);
-	
 	testAxialSymmetry(graph, root_node, node1, node2, arc1, arc2, axis, limit, 1);
 }
 
@@ -777,7 +771,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_subtreeDepth(connectedNode, connectedArc);
+			connectedArc->symmetry_level = -BLI_subtreeShape(connectedNode, connectedArc);
 		}
 	}
 
@@ -854,7 +848,6 @@ void BLI_markdownSymmetry(BGraph *graph, BNode *root_node, float limit)
 	
 	if (BLI_isGraphCyclic(graph))
 	{
-		printf("cyclic\n");
 		return;
 	}
 	
diff --git a/source/blender/src/reeb.c b/source/blender/src/reeb.c
index 1c317f06176..610d5d83d97 100644
--- a/source/blender/src/reeb.c
+++ b/source/blender/src/reeb.c
@@ -93,6 +93,7 @@ typedef enum {
 } MergeDirection;
 
 int mergeArcs(ReebGraph *rg, ReebArc *a0, ReebArc *a1);
+void mergeArcEdges(ReebGraph *rg, ReebArc *aDst, ReebArc *aSrc, MergeDirection direction);
 int mergeConnectedArcs(ReebGraph *rg, ReebArc *a0, ReebArc *a1);
 EditEdge * NextEdgeForVert(EditMesh *em, EditVert *v);
 void mergeArcFaces(ReebGraph *rg, ReebArc *aDst, ReebArc *aSrc);
@@ -824,18 +825,20 @@ void filterArc(ReebGraph *rg, ReebNode *newNode, ReebNode *removedNode, ReebArc
 					REEB_freeArc((BArc*)arc);
 				}
 			}
-#if 0
 			// Remove flipped arcs
 			else if (((ReebNode*)arc->head)->weight > ((ReebNode*)arc->tail)->weight)
 			{
+#if 0
 				// Decrement degree from the other node
 				//BLI_otherNode((BArc*)arc, (BNode*)newNode)->degree--;
 				NodeDegreeDecrement(rg, (ReebNode*)BLI_otherNode((BArc*)arc, (BNode*)newNode));
 				
 				BLI_remlink(&rg->arcs, arc);
 				REEB_freeArc((BArc*)arc);
-			}
+#else
+				printf("flipped\n");
 #endif
+			}
 			else
 			{
 				//newNode->degree++; // incrementing degree since we're adding an arc
@@ -911,6 +914,7 @@ int filterInternalReebGraph(ReebGraph *rg, float threshold)
 			ReebNode *newNode = NULL;
 			ReebNode *removedNode = NULL;
 			
+#if 0 // Old method
 			/* Keep the node with the highestn number of connected arcs */
 			if (arc->head->degree >= arc->tail->degree)
 			{
@@ -922,6 +926,11 @@ int filterInternalReebGraph(ReebGraph *rg, float threshold)
 				newNode = arc->tail;
 				removedNode = arc->head;
 			}
+#else
+			/* Always remove lower node, so arcs don't flip */
+			newNode = arc->head;
+			removedNode = arc->tail;
+#endif
 			
 			filterArc(rg, newNode, removedNode, arc, 1);
 
@@ -1017,6 +1026,41 @@ int filterExternalReebGraph(ReebGraph *rg, float threshold)
 	return value;
 }
 
+int filterCyclesReebGraph(ReebGraph *rg, float distance_threshold)
+{
+	int filtered = 0;
+	
+	if (BLI_isGraphCyclic((BGraph*)rg))
+	{
+		ReebArc *arc1, *arc2;
+		ReebArc *next2;
+		
+		for (arc1 = rg->arcs.first; arc1; arc1 = arc1->next)
+		{
+			for (arc2 = rg->arcs.first; arc2; arc2 = next2)
+			{
+				next2 = arc2->next;
+				if (arc1 != arc2 && arc1->head == arc2->head && arc1->tail == arc2->tail)
+				{
+					mergeArcEdges(rg, arc1, arc2, MERGE_APPEND);
+					mergeArcFaces(rg, arc1, arc2);
+					mergeArcBuckets(arc1, arc2, arc1->head->weight, arc1->tail->weight);
+
+					NodeDegreeDecrement(rg, arc1->head);
+					NodeDegreeDecrement(rg, arc1->tail);
+
+					BLI_remlink(&rg->arcs, arc2);
+					REEB_freeArc((BArc*)arc2);
+					
+					filtered = 1;
+				}
+			}
+		}
+	}
+	
+	return filtered;
+}
+
 int filterSmartReebGraph(ReebGraph *rg, float threshold)
 {
 	ReebArc *arc = NULL, *nextArc = NULL;
@@ -2634,17 +2678,27 @@ ReebGraph *BIF_ReebGraphFromEditMesh(void)
 	
 	rg = generateReebGraph(em, G.scene->toolsettings->skgen_resolution);
 
+	verifyNodeDegree(rg);
+
 	REEB_exportGraph(rg, -1);
 
 	verifyBuckets(rg);
 	
 	verifyFaces(rg);
 
+	printf("GENERATED\n");
+	printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)rg));
+
 	/* Remove arcs without embedding */
 	filterNullReebGraph(rg);
 
 	verifyBuckets(rg);
 
+	BLI_freeAdjacencyList((BGraph*)rg);
+
+	printf("NULL FILTERED\n");
+	printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)rg));
+
 	i = 1;
 	/* filter until there's nothing more to do */
 	while (i == 1)
@@ -2667,6 +2721,8 @@ ReebGraph *BIF_ReebGraphFromEditMesh(void)
 	if (G.scene->toolsettings->skgen_options & SKGEN_FILTER_SMART)
 	{
 		filterSmartReebGraph(rg, 0.5);
+		BLI_rebuildAdjacencyList((BGraph*)rg);
+		filterCyclesReebGraph(rg, 0.5);
 	}
 
 #ifdef DEBUG_REEB
@@ -2690,7 +2746,7 @@ ReebGraph *BIF_ReebGraphFromEditMesh(void)
 		postprocessGraph(rg, G.scene->toolsettings->skgen_postpro);
 	}
 
-	BLI_buildAdjacencyList((BGraph*)rg);
+	BLI_rebuildAdjacencyList((BGraph*)rg);
 	
 	sortNodes(rg);
 	
@@ -2700,6 +2756,9 @@ ReebGraph *BIF_ReebGraphFromEditMesh(void)
 	
 	calculateGraphLength(rg);
 	
+	printf("DONE\n");
+	printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)rg));
+
 	return rg;
 }
 
@@ -2714,115 +2773,11 @@ void BIF_GlobalReebFree()
 
 void BIF_GlobalReebGraphFromEditMesh(void)
 {
-	EditMesh *em = G.editMesh;
-	int i;
-	
-	if (em == NULL)
-		return;
-
 	BIF_GlobalReebFree();
-
-	if (weightFromDistance(em) == 0)
-	{
-		error("No selected vertex\n");
-		return;
-	}
 	
-	renormalizeWeight(em, 1.0f);
-
-	if (G.scene->toolsettings->skgen_options & SKGEN_HARMONIC)
-	{
-		weightToHarmonic(em);
-	}
-	
-#ifdef DEBUG_REEB
-	weightToVCol(em, 0);
-#endif
-
-	GLOBAL_RG = generateReebGraph(em, G.scene->toolsettings->skgen_resolution);
-
-	verifyNodeDegree(GLOBAL_RG);
-
-	REEB_exportGraph(GLOBAL_RG, -1);
-
-	verifyBuckets(GLOBAL_RG);
-	
-	verifyFaces(GLOBAL_RG);
-
-	printf("GENERATED\n");
-	printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)GLOBAL_RG));
-
-	/* Remove arcs without embedding */
-	filterNullReebGraph(GLOBAL_RG);
-
-	verifyNodeDegree(GLOBAL_RG);
-	
-	BLI_freeAdjacencyList((BGraph*)GLOBAL_RG);
-
-	printf("NULL FILTERED\n");
-	printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)GLOBAL_RG));
-
-	verifyBuckets(GLOBAL_RG);
-
-	i = 1;
-	/* filter until there's nothing more to do */
-	while (i == 1)
-	{
-		i = 0; /* no work done yet */
-		
-		if (G.scene->toolsettings->skgen_options & SKGEN_FILTER_EXTERNAL)
-		{
-			i |= filterExternalReebGraph(GLOBAL_RG, G.scene->toolsettings->skgen_threshold_external * G.scene->toolsettings->skgen_resolution);
-		}
-	
-		verifyBuckets(GLOBAL_RG);
-	
-		if (G.scene->toolsettings->skgen_options & SKGEN_FILTER_INTERNAL)
-		{
-			i |= filterInternalReebGraph(GLOBAL_RG, G.scene->toolsettings->skgen_threshold_internal * G.scene->toolsettings->skgen_resolution);
-		}
-	}
-
-	if (G.scene->toolsettings->skgen_options & SKGEN_FILTER_SMART)
-	{
-		filterSmartReebGraph(GLOBAL_RG, 0.5);
-	}
-
-	verifyBuckets(GLOBAL_RG);
-
-	repositionNodes(GLOBAL_RG);
-	
-	verifyBuckets(GLOBAL_RG);
-
-	/* Filtering might have created degree 2 nodes, so remove them */
-	removeNormalNodes(GLOBAL_RG);
-	
-	verifyBuckets(GLOBAL_RG);
-
-#ifdef DEBUG_REEB
-	arcToVCol(GLOBAL_RG, em, 1);
-	//angleToVCol(em, 1);
-#endif
-
-	for(i = 0; i <  G.scene->toolsettings->skgen_postpro_passes; i++)
-	{
-		postprocessGraph(GLOBAL_RG, G.scene->toolsettings->skgen_postpro);
-	}
-
-	BLI_buildAdjacencyList((BGraph*)GLOBAL_RG);
-	
-	sortNodes(GLOBAL_RG);
-	
-	sortArcs(GLOBAL_RG);
-	
-	REEB_exportGraph(GLOBAL_RG, -1);
-	
-	calculateGraphLength(GLOBAL_RG);
+	GLOBAL_RG = BIF_ReebGraphFromEditMesh();
 
 	BLI_markdownSymmetry((BGraph*)GLOBAL_RG, GLOBAL_RG->nodes.first, G.scene->toolsettings->skgen_symmetry_limit);
-	
-	printf("DONE\n");
-	printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)GLOBAL_RG));
 }
 
 void REEB_draw()