Code cleanup and recursive symmetry detection.

5 files changed, 231 insertions, 157 deletions

diff --git a/source/blender/include/BIF_editarmature.h b/source/blender/include/BIF_editarmature.h
index e836b98585e..6c17bf885ad 100644
--- a/source/blender/include/BIF_editarmature.h
+++ b/source/blender/include/BIF_editarmature.h
@@ -79,8 +79,6 @@ void	add_primitiveArmature(int type);
 void	apply_rot_armature (struct Object *ob, float mat[3][3]);
 void 	docenter_armature (struct Object *ob, int centermode);
 
-void generateSkeletonFromReebGraph(struct ReebGraph *rg);
-
 void	clear_armature(struct Object *ob, char mode);
 
 void	delete_armature(void);
@@ -104,6 +102,8 @@ void	make_trans_bones (char mode);
 
 int		do_pose_selectbuffer(struct Base *base, unsigned int *buffer, short hits);
 
+void generateSkeleton(void);
+
 void	mouse_armature(void);
 void	remake_editArmature(void);
 void	selectconnected_armature(void);
diff --git a/source/blender/include/BSE_edit.h b/source/blender/include/BSE_edit.h
index 25ca4cc1065..93ebd0ffa77 100644
--- a/source/blender/include/BSE_edit.h
+++ b/source/blender/include/BSE_edit.h
@@ -51,8 +51,6 @@ void snap_curs_to_grid(void);
 void snap_curs_to_sel(void);
 void snap_to_center(void);
 
-void generateSkeleton(void);
-
 #endif /*  BSE_EDIT_H */
 
 
diff --git a/source/blender/include/reeb.h b/source/blender/include/reeb.h
index c46d430c21d..53044d73eba 100644
--- a/source/blender/include/reeb.h
+++ b/source/blender/include/reeb.h
@@ -90,6 +90,8 @@ int weightFromLoc(struct EditMesh *me, int axis);
 void renormalizeWeight(struct EditMesh *em, float newmax);
 
 ReebGraph * generateReebGraph(struct EditMesh *me, int subdivisions);
+void freeGraph(ReebGraph *rg);
+void exportGraph(ReebGraph *rg, int count);
 
 #define OTHER_NODE(arc, node) ((arc->v1 == node) ? arc->v2 : arc->v1)
 
@@ -97,9 +99,28 @@ void initArcIterator(struct ReebArcIterator *iter, struct ReebArc *arc, struct R
 void initArcIterator2(struct ReebArcIterator *iter, struct ReebArc *arc, int start, int end);
 struct EmbedBucket * nextBucket(struct ReebArcIterator *iter);
 
+/* Filtering */
+void filterNullReebGraph(ReebGraph *rg);
+void filterExternalReebGraph(ReebGraph *rg, float threshold);
+void filterInternalReebGraph(ReebGraph *rg, float threshold);
+
+/* Post-Build processing */
+void repositionNodes(ReebGraph *rg);
+void postprocessGraph(ReebGraph *rg, char mode);
+void removeNormalNodes(ReebGraph *rg);
+
+/* Graph processing */
+void buildAdjacencyList(ReebGraph *rg);
+
+void sortNodes(ReebGraph *rg);
+void sortArcs(ReebGraph *rg);
+
 int subtreeDepth(ReebNode *node);
 int countConnectedArcs(ReebGraph *rg, ReebNode *node);
 int hasAdjacencyList(ReebGraph *rg); 
 int	isGraphAcyclic(ReebGraph *rg);
 
+/* Sanity check */
+void verifyBuckets(ReebGraph *rg);
+
 #endif /*REEB_H_*/
diff --git a/source/blender/src/editarmature.c b/source/blender/src/editarmature.c
index ff7f2c88114..593322ac0e1 100644
--- a/source/blender/src/editarmature.c
+++ b/source/blender/src/editarmature.c
@@ -3148,102 +3148,115 @@ void transform_armature_mirror_update(void)
 
 /*****************************************************************************************************/
 
-float arcLengthRatio(ReebArc *arc)
+void markdownSymetryArc(ReebArc *arc, ReebNode *node, int level);
+
+void reestablishSymetry(ReebNode *node, int depth, int level)
 {
-	float arcLength = 0.0f;
-	float embedLength = 0.0f;
 	int i;
 	
-	arcLength = VecLenf(arc->v1->p, arc->v2->p);
-	
-	if (arc->bcount > 0)
+	/* detect spatial symetry */
+
+
+	/* markdown secondary symetries */	
+	for(i = 0; node->arcs[i] != NULL; i++)
 	{
-		// Add the embedding
-		for( i = 1; i < arc->bcount; i++)
+		ReebArc *connectedArc = node->arcs[i];
+		
+		/* depth is store as a negative in flag. symetry level is positive */
+		if (connectedArc->flags == -depth)
 		{
-			embedLength += VecLenf(arc->buckets[i - 1].p, arc->buckets[i].p);
+			/* markdown symetry for branches corresponding to the depth */
+			markdownSymetryArc(connectedArc, node, level + 1);
 		}
-		// Add head and tail -> embedding vectors
-		embedLength += VecLenf(arc->v1->p, arc->buckets[0].p);
-		embedLength += VecLenf(arc->v2->p, arc->buckets[arc->bcount - 1].p);
-	}
-	else
-	{
-		embedLength = arcLength;
 	}
-	
-	return embedLength / arcLength;	
 }
 
-void symetryMarkdownArc(ReebArc *arc, ReebNode *node, int level)
+void markdownSymetryArc(ReebArc *arc, ReebNode *node, int level)
 {
-	while(arc)
+	int i;
+	arc->flags = level;
+	
+	node = OTHER_NODE(arc, node);
+	
+	for(i = 0; node->arcs[i] != NULL; i++)
 	{
-		int i;
-		arc->flags = level;
+		ReebArc *connectedArc = node->arcs[i];
 		
-		node = OTHER_NODE(arc, node);
+		if (connectedArc != arc)
+		{
+			ReebNode *connectedNode = OTHER_NODE(connectedArc, node);
+			
+			/* symetry level is positive value, negative values is subtree depth */
+			connectedArc->flags = -subtreeDepth(connectedNode);
+		}
+	}
+	
+	arc = NULL;
+
+	for(i = 0; node->arcs[i] != NULL; i++)
+	{
+		int isSymetryAxis = 0;
+		ReebArc *connectedArc = node->arcs[i];
 		
-		for(i = 0; node->arcs[i] != NULL; i++)
+		/* only arcs not already marked as symetric */
+		if (connectedArc->flags < 0)
 		{
-			ReebArc *connectedArc = node->arcs[i];
+			int j;
 			
-			if (connectedArc != arc)
+			/* true by default */
+			isSymetryAxis = 1;
+			
+			for(j = 0; node->arcs[j] != NULL && isSymetryAxis == 1; j++)
 			{
-				ReebNode *connectedNode = OTHER_NODE(connectedArc, node);
+				ReebArc *otherArc = node->arcs[j];
 				
-				connectedArc->flags = -subtreeDepth(connectedNode);
+				/* different arc, same depth */
+				if (otherArc != connectedArc && otherArc->flags == connectedArc->flags)
+				{
+					/* not on the symetry axis */
+					isSymetryAxis = 0;
+				} 
 			}
 		}
 		
-		arc = NULL;
-
-		for(i = 0; node->arcs[i] != NULL; i++)
+		/* arc could be on the symetry axis */
+		if (isSymetryAxis == 1)
 		{
-			int isSymetryAxis = 0;
-			ReebArc *connectedArc = node->arcs[i];
-			
-			/* only arcs not already marked as symetric */
-			if (connectedArc->flags < 0)
+			/* no arc as been marked previously, keep this one */
+			if (arc == NULL)
 			{
-				int j;
-				
-				/* true by default */
-				isSymetryAxis = 1;
-				
-				for(j = 0; node->arcs[j] != NULL && isSymetryAxis == 1; j++)
-				{
-					ReebArc *otherArc = node->arcs[j];
-					
-					/* different arc, same depth */
-					if (otherArc != connectedArc && otherArc->flags == connectedArc->flags)
-					{
-						/* not on the symetry axis */
-						isSymetryAxis = 0;
-					} 
-				}
+				arc = connectedArc;
 			}
-			
-			/* arc could be on the symetry axis */
-			if (isSymetryAxis == 1)
+			else
 			{
-				/* no arc as been marked previously, keep this one */
-				if (arc == NULL)
-				{
-					arc = connectedArc;
-				}
-				else
-				{
-					/* there can't be more than one symetry arc */
-					arc = NULL;
-					break;
-				}
+				/* there can't be more than one symetry arc */
+				arc = NULL;
+				break;
 			}
 		}
 	}
+	
+	/* go down the arc continuing the symetry axis */
+	if (arc)
+	{
+		markdownSymetryArc(arc, node, level);
+	}
+	
+	/* restore symetry */
+	for(i = 0; node->arcs[i] != NULL; i++)
+	{
+		ReebArc *connectedArc = node->arcs[i];
+		
+		/* only arcs not already marked as symetric and is not the next arc on the symetry axis */
+		if (connectedArc->flags < 0)
+		{
+			/* subtree depth is store as a negative value in the flag */
+			reestablishSymetry(node, -connectedArc->flags, level);
+		}
+	}
 }
 
-void symetryMarkdown(ReebGraph *rg)
+void markdownSymetry(ReebGraph *rg)
 {
 	ReebNode *node;
 	ReebArc *arc;
@@ -3268,7 +3281,7 @@ void symetryMarkdown(ReebGraph *rg)
 	{
 		arc = node->arcs[0];
 		
-		symetryMarkdownArc(arc, node, 1);
+		markdownSymetryArc(arc, node, 1);
 	}
 
 	/* mark down non-symetric arcs */
@@ -3280,9 +3293,15 @@ void symetryMarkdown(ReebGraph *rg)
 		}
 		else
 		{
-			/* mark down nodes that are on the symetry axis */
-			arc->v1->flags = 1;
-			arc->v2->flags = 1;
+			/* mark down nodes with the lowest level symetry axis */
+			if (arc->v1->flags == 0 || arc->v1->flags > arc->flags)
+			{
+				arc->v1->flags = arc->flags;
+			}
+			if (arc->v2->flags == 0 || arc->v2->flags > arc->flags)
+			{
+				arc->v2->flags = arc->flags;
+			}
 		}
 		
 	}
@@ -3299,11 +3318,14 @@ EditBone * subdivideByAngle(ReebArc *arc, ReebNode *head, ReebNode *tail)
 		EmbedBucket *previous = NULL;
 		EditBone *child = NULL;
 		EditBone *parent = NULL;
+		EditBone *root = NULL;
 		float angleLimit = (float)cos(G.scene->toolsettings->skgen_angle_limit * M_PI / 180.0f);
 		
 		parent = add_editbone("Bone");
 		VECCOPY(parent->head, head->p);
 		
+		root = parent;
+		
 		for(initArcIterator(&iter, arc, head), previous = nextBucket(&iter), current = nextBucket(&iter); current; previous = current, current = nextBucket(&iter))
 		{
 			float vec1[3], vec2[3];
@@ -3315,8 +3337,6 @@ EditBone * subdivideByAngle(ReebArc *arc, ReebNode *head, ReebNode *tail)
 			len1 = Normalize(vec1);
 			len2 = Normalize(vec2);
 
-			//printf("%f < %f\n", Inpf(vec1, vec2), angleLimit);
-
 			if (len1 > 0.0f && len2 > 0.0f && Inpf(vec1, vec2) < angleLimit)
 			{
 				VECCOPY(parent->tail, previous->p);
@@ -3326,11 +3346,20 @@ EditBone * subdivideByAngle(ReebArc *arc, ReebNode *head, ReebNode *tail)
 				child->parent = parent;
 				child->flag |= BONE_CONNECTED;
 				
-				parent = child; // new child is next parent
+				parent = child; /* new child is next parent */
 			}
 		}
 		VECCOPY(parent->tail, tail->p);
 		
+		/* If the bone wasn't subdivided, delete it and return NULL
+		 * to let subsequent subdivision methods do their thing. 
+		 * */
+		if (parent == root)
+		{
+			delete_bone(parent);
+			parent = NULL;
+		}
+		
 		lastBone = parent; /* set last bone in the chain */
 	}
 	
@@ -3441,6 +3470,33 @@ EditBone * subdivideByCorrelation(ReebArc *arc, ReebNode *head, ReebNode *tail)
 	return lastBone;
 }
 
+float arcLengthRatio(ReebArc *arc)
+{
+	float arcLength = 0.0f;
+	float embedLength = 0.0f;
+	int i;
+	
+	arcLength = VecLenf(arc->v1->p, arc->v2->p);
+	
+	if (arc->bcount > 0)
+	{
+		/* Add the embedding */
+		for( i = 1; i < arc->bcount; i++)
+		{
+			embedLength += VecLenf(arc->buckets[i - 1].p, arc->buckets[i].p);
+		}
+		/* Add head and tail -> embedding vectors */
+		embedLength += VecLenf(arc->v1->p, arc->buckets[0].p);
+		embedLength += VecLenf(arc->v2->p, arc->buckets[arc->bcount - 1].p);
+	}
+	else
+	{
+		embedLength = arcLength;
+	}
+	
+	return embedLength / arcLength;	
+}
+
 EditBone * subdivideByLength(ReebArc *arc, ReebNode *head, ReebNode *tail)
 {
 	EditBone *lastBone = NULL;
@@ -3577,12 +3633,13 @@ void generateSkeletonFromReebGraph(ReebGraph *rg)
 
 	arcBoneMap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
 	
-	symetryMarkdown(rg);
+	markdownSymetry(rg);
+
+	exportGraph(rg, -1);
 	
 	for (arc = rg->arcs.first; arc; arc = arc->next) 
 	{
 		EditBone *lastBone = NULL;
-		EditBone *firstBone = NULL;
 		ReebNode *head, *tail;
 		int i;
 
@@ -3720,3 +3777,75 @@ void generateSkeletonFromReebGraph(ReebGraph *rg)
 	BIF_undo_push("Generate Skeleton");
 }
 
+void generateSkeleton(void)
+{
+	EditMesh *em = G.editMesh;
+	ReebGraph *rg = NULL;
+	int i;
+	
+	if (em == NULL)
+		return;
+
+	setcursor_space(SPACE_VIEW3D, CURSOR_WAIT);
+
+	weightFromDistance(em);
+	weightToHarmonic(em);
+		
+	renormalizeWeight(em, 1.0f);
+
+#ifdef DEBUG_REEB
+	weightToVCol(em);
+#endif
+	
+	rg = generateReebGraph(em, G.scene->toolsettings->skgen_resolution);
+	
+	verifyBuckets(rg);
+	
+	/* Remove arcs without embedding */
+	filterNullReebGraph(rg);
+
+	verifyBuckets(rg);
+
+	if (G.scene->toolsettings->skgen_options & SKGEN_FILTER_EXTERNAL)
+	{
+		filterExternalReebGraph(rg, G.scene->toolsettings->skgen_threshold_external * G.scene->toolsettings->skgen_resolution);
+	}
+
+	verifyBuckets(rg);
+
+	if (G.scene->toolsettings->skgen_options & SKGEN_FILTER_INTERNAL)
+	{
+		filterInternalReebGraph(rg, G.scene->toolsettings->skgen_threshold_internal * G.scene->toolsettings->skgen_resolution);
+	}
+
+	verifyBuckets(rg);
+
+	if (G.scene->toolsettings->skgen_options & SKGEN_REPOSITION)
+	{
+		repositionNodes(rg);
+	}
+	
+	verifyBuckets(rg);
+
+	/* Filtering might have created degree 2 nodes, so remove them */
+	removeNormalNodes(rg);
+	
+	verifyBuckets(rg);
+
+	for(i = 0; i <  G.scene->toolsettings->skgen_postpro_passes; i++)
+	{
+		postprocessGraph(rg, G.scene->toolsettings->skgen_postpro);
+	}
+
+	buildAdjacencyList(rg);
+	
+	sortNodes(rg);
+	
+	sortArcs(rg);
+	
+//	exportGraph(rg, -1);
+
+	generateSkeletonFromReebGraph(rg);
+	
+	freeGraph(rg);
+}
diff --git a/source/blender/src/reeb.c b/source/blender/src/reeb.c
index f661e849f83..c35f3ad766b 100644
--- a/source/blender/src/reeb.c
+++ b/source/blender/src/reeb.c
@@ -1404,7 +1404,10 @@ ReebGraph * generateReebGraph(EditMesh *em, int subdivisions)
 	int index;
 	int totvert;
 	int totfaces;
+	
+#ifdef DEBUG_REEB
 	int countfaces = 0;
+#endif
  	
 	rg = MEM_callocN(sizeof(ReebGraph), "reeb graph");
 	
@@ -1900,80 +1903,3 @@ EmbedBucket * nextBucket(ReebArcIterator *iter)
 	
 	return result;
 }
-
-/****************************************** MAIN EDIT METHOD **************************************************/
-
-void generateSkeleton(void)
-{
-	EditMesh *em = G.editMesh;
-	ReebGraph *rg = NULL;
-	int i;
-	
-	if (em == NULL)
-		return;
-
-	setcursor_space(SPACE_VIEW3D, CURSOR_WAIT);
-
-	weightFromDistance(em);
-	weightToHarmonic(em);
-		
-	renormalizeWeight(em, 1.0f);
-
-#ifdef DEBUG_REEB
-	weightToVCol(em);
-#endif
-	
-	rg = generateReebGraph(em, G.scene->toolsettings->skgen_resolution);
-	
-	verifyBuckets(rg);
-	
-	/* Remove arcs without embedding */
-	filterNullReebGraph(rg);
-
-	verifyBuckets(rg);
-
-	if (G.scene->toolsettings->skgen_options & SKGEN_FILTER_EXTERNAL)
-	{
-		filterExternalReebGraph(rg, G.scene->toolsettings->skgen_threshold_external * G.scene->toolsettings->skgen_resolution);
-	}
-
-	verifyBuckets(rg);
-
-	if (G.scene->toolsettings->skgen_options & SKGEN_FILTER_INTERNAL)
-	{
-		filterInternalReebGraph(rg, G.scene->toolsettings->skgen_threshold_internal * G.scene->toolsettings->skgen_resolution);
-	}
-
-	verifyBuckets(rg);
-
-	if (G.scene->toolsettings->skgen_options & SKGEN_REPOSITION)
-	{
-		repositionNodes(rg);
-	}
-	
-	verifyBuckets(rg);
-
-	/* Filtering might have created degree 2 nodes, so remove them */
-	removeNormalNodes(rg);
-	
-	verifyBuckets(rg);
-
-	for(i = 0; i <  G.scene->toolsettings->skgen_postpro_passes; i++)
-	{
-		postprocessGraph(rg, G.scene->toolsettings->skgen_postpro);
-	}
-
-	buildAdjacencyList(rg);
-	
-	sortNodes(rg);
-	
-	sortArcs(rg);
-	
-#ifdef DEBUG_REEB
-	exportGraph(rg, -1);
-#endif
-
-	generateSkeletonFromReebGraph(rg);
-	
-	freeGraph(rg);
-}