More merging goodness
authorMartin Poirier <theeth@yahoo.com>
Tue, 15 Jul 2008 21:07:13 +0000 (21:07 +0000)
committerMartin Poirier <theeth@yahoo.com>
Tue, 15 Jul 2008 21:07:13 +0000 (21:07 +0000)
fix adjacency list inline instead of having to rebuild fully
reweight joined graphs properly

source/blender/blenlib/BLI_graph.h
source/blender/blenlib/intern/graph.c
source/blender/src/reeb.c

index dba02932e02817b626f87f9bb5b5af60531cc2e5..be5d1f5d10c9a753f420d0c456ab59ef245162b6 100644 (file)
@@ -76,6 +76,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_rebuildAdjacencyListForNode(BGraph* rg, BNode *node);
 void BLI_freeAdjacencyList(BGraph *rg);
 
 int BLI_FlagSubgraphs(BGraph *graph);
index fce9d0b6d95112878c1711fbf498e97e0cddd708..32d9f3b91b7d2cc3c1b7ff88c93f768701d27d64 100644 (file)
@@ -90,12 +90,6 @@ 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;
@@ -129,6 +123,38 @@ void BLI_buildAdjacencyList(BGraph *rg)
        }
 }
 
+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;
index 71eb550fd214c84f24cd044ed94161c96d99ea24..b3fe465830af8ee181a99a5142e5b723862abc89 100644 (file)
@@ -328,7 +328,7 @@ ReebGraph * copyReebGraph(ReebGraph *rg)
                copyArc(cp_rg, arc);
        }
        
-       BLI_rebuildAdjacencyList((BGraph*)cp_rg);
+       BLI_buildAdjacencyList((BGraph*)cp_rg);
        
        return cp_rg;
 }
@@ -1063,30 +1063,51 @@ void sortArcs(ReebGraph *rg)
 
 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 @@ int joinSubgraphsEnds(ReebGraph *rg, float threshold, int nb_subgraphs)
                                                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 joinSubgraphs(ReebGraph *rg, float threshold)
        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 @@ void filterGraph(ReebGraph *rg, short options, float threshold_internal, float t
        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 @@ void finalizeGraph(ReebGraph *rg, char passes, char method)
 {
        int i;
        
-       BLI_rebuildAdjacencyList((BGraph*)rg);
+       BLI_buildAdjacencyList((BGraph*)rg);
 
        sortNodes(rg);
        
@@ -3162,9 +3188,7 @@ ReebGraph *BIF_ReebGraphMultiFromEditMesh(void)
        /* Filtering might have created degree 2 nodes, so remove them */
        removeNormalNodes(rg);
        
-       joinSubgraphs(rg, 1.5);
-       
-       BLI_rebuildAdjacencyList((BGraph*)rg);
+       joinSubgraphs(rg, 1.0);
        
        /* calc length before copy, so we have same length on all levels */
        BLI_calcGraphLength((BGraph*)rg);