[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15593] branches/harmonic-skeleton/source/ blender: More merging goodness

[Martin Poirier]

Revision: 15593
          http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15593
Author:   theeth
Date:     2008-07-15 23:07:13 +0200 (Tue, 15 Jul 2008)

Log Message:
-----------
More merging goodness
	fix adjacency list inline instead of having to rebuild fully
	reweight joined graphs properly

Modified Paths:
--------------
    branches/harmonic-skeleton/source/blender/blenlib/BLI_graph.h
    branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c
    branches/harmonic-skeleton/source/blender/src/reeb.c

Modified: branches/harmonic-skeleton/source/blender/blenlib/BLI_graph.h
===================================================================
--- branches/harmonic-skeleton/source/blender/blenlib/BLI_graph.h	2008-07-15 20:05:23 UTC (rev 15592)
+++ branches/harmonic-skeleton/source/blender/blenlib/BLI_graph.h	2008-07-15 21:07:13 UTC (rev 15593)
@@ -76,6 +76,7 @@
 int BLI_hasAdjacencyList(BGraph *rg);
 void BLI_buildAdjacencyList(BGraph *rg);
 void BLI_rebuildAdjacencyList(BGraph* rg);
+void BLI_rebuildAdjacencyListForNode(BGraph* rg, BNode *node);
 void BLI_freeAdjacencyList(BGraph *rg);
 
 int BLI_FlagSubgraphs(BGraph *graph);

Modified: branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c
===================================================================
--- branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c	2008-07-15 20:05:23 UTC (rev 15592)
+++ branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c	2008-07-15 21:07:13 UTC (rev 15593)
@@ -90,12 +90,6 @@
 	node->flag++;
 }
 
-void BLI_rebuildAdjacencyList(BGraph *rg)
-{
-	BLI_freeAdjacencyList(rg);
-	BLI_buildAdjacencyList(rg);
-}
-
 void BLI_buildAdjacencyList(BGraph *rg)
 {
 	BNode *node;
@@ -129,6 +123,38 @@
 	}
 }
 
+void BLI_rebuildAdjacencyListForNode(BGraph* rg, BNode *node)
+{
+	BArc *arc;
+
+	if (node->arcs != NULL)
+	{
+		MEM_freeN(node->arcs);
+	}
+	
+	node->arcs = MEM_callocN((node->degree) * sizeof(BArc*), "adjacency list");
+	
+	/* temporary use to indicate the first index available in the lists */
+	node->flag = 0;
+
+	for(arc = rg->arcs.first; arc; arc= arc->next)
+	{
+		if (arc->head == node)
+		{
+			addArcToNodeAdjacencyList(arc->head, arc);
+		}
+		else if (arc->tail == node)
+		{
+			addArcToNodeAdjacencyList(arc->tail, arc);
+		}
+	}
+
+	if (node->degree != node->flag)
+	{
+		printf("error in node [%p]. Added only %i arcs out of %i\n", node, node->flag, node->degree);
+	}
+}
+
 void BLI_freeAdjacencyList(BGraph *rg)
 {
 	BNode *node;

Modified: branches/harmonic-skeleton/source/blender/src/reeb.c
===================================================================
--- branches/harmonic-skeleton/source/blender/src/reeb.c	2008-07-15 20:05:23 UTC (rev 15592)
+++ branches/harmonic-skeleton/source/blender/src/reeb.c	2008-07-15 21:07:13 UTC (rev 15593)
@@ -328,7 +328,7 @@
 		copyArc(cp_rg, arc);
 	}
 	
-	BLI_rebuildAdjacencyList((BGraph*)cp_rg);
+	BLI_buildAdjacencyList((BGraph*)cp_rg);
 	
 	return cp_rg;
 }
@@ -1063,30 +1063,51 @@
 
 void reweightArc(ReebArc *arc, ReebNode *start_node, float start_weight)
 {
-	float delta_weight = arc->tail->weight - arc->head->weight;
+	ReebNode *node;
+	float old_weight;
+	float end_weight = start_weight + (arc->tail->weight - arc->head->weight);
+	int i;
 	
 	if (arc->tail == start_node)
 	{
 		flipArc(arc);
 	}
 	
+	node = arc->tail;
+	
+	for (i = 0; i < node->degree; i++)
+	{
+		ReebArc *next_arc = node->arcs[i];
+		
+		if (next_arc != arc) /* prevent backtracking */
+		{
+			reweightArc(next_arc, node, end_weight);
+		}
+	}
+	
+	old_weight = arc->head->weight; /* backup head weight, other arcs need it intact, it will be fixed by the source arc */
+	
 	arc->head->weight = start_weight;
-	arc->tail->weight = start_weight + delta_weight;
+	arc->tail->weight = end_weight;
 	
 	reweightBuckets(arc);
 	resizeArcBuckets(arc);
 	fillArcEmptyBuckets(arc);
 	
-	/* recurse here */
+	arc->head->weight = old_weight;
 } 
 
 void reweightSubgraph(ReebGraph *rg, ReebNode *start_node, float start_weight)
 {
-	ReebArc *arc;
-	
-	arc = start_node->arcs[0];
-	
-	reweightArc(arc, start_node, start_weight);
+	int i;
+		
+	for (i = 0; i < start_node->degree; i++)
+	{
+		ReebArc *next_arc = start_node->arcs[i];
+		
+		reweightArc(next_arc, start_node, start_weight);
+	}
+	start_node->weight = start_weight;
 }
 
 int joinSubgraphsEnds(ReebGraph *rg, float threshold, int nb_subgraphs)
@@ -1144,6 +1165,7 @@
 						fillArcEmptyBuckets(start_arc);
 						
 						NodeDegreeIncrement(rg, end_node);
+						BLI_rebuildAdjacencyListForNode((BGraph*)rg, (BNode*)end_node);
 						
 						BLI_removeNode((BGraph*)rg, (BNode*)start_node);
 					}
@@ -1163,16 +1185,20 @@
 	int nb_subgraphs;
 	int joined = 0;
 	
-	BLI_rebuildAdjacencyList((BGraph*)rg);
+	BLI_buildAdjacencyList((BGraph*)rg);
 	
 	nb_subgraphs = BLI_FlagSubgraphs((BGraph*)rg);
 	
-	joined |= joinSubgraphsEnds(rg, threshold, nb_subgraphs);
-	
-	if (joined)
+	if (nb_subgraphs > 1)
 	{
-		removeNormalNodes(rg);
-		BLI_rebuildAdjacencyList((BGraph*)rg);
+		joined |= joinSubgraphsEnds(rg, threshold, nb_subgraphs);
+		
+		if (joined)
+		{
+			verifyNodeDegree(rg);
+			removeNormalNodes(rg);
+			BLI_buildAdjacencyList((BGraph*)rg);
+		}
 	}
 	
 	return joined;
@@ -1682,7 +1708,7 @@
 	if (options & SKGEN_FILTER_SMART)
 	{
 		filterSmartReebGraph(rg, 0.5);
-		BLI_rebuildAdjacencyList((BGraph*)rg);
+		BLI_buildAdjacencyList((BGraph*)rg);
 		filterCyclesReebGraph(rg, 0.5);
 	}
 	
@@ -1698,7 +1724,7 @@
 {
 	int i;
 	
-	BLI_rebuildAdjacencyList((BGraph*)rg);
+	BLI_buildAdjacencyList((BGraph*)rg);
 
 	sortNodes(rg);
 	
@@ -3162,10 +3188,8 @@
 	/* Filtering might have created degree 2 nodes, so remove them */
 	removeNormalNodes(rg);
 	
-	joinSubgraphs(rg, 1.5);
+	joinSubgraphs(rg, 1.0);
 	
-	BLI_rebuildAdjacencyList((BGraph*)rg);
-	
 	/* calc length before copy, so we have same length on all levels */
 	BLI_calcGraphLength((BGraph*)rg);