diff options
author | Martin Poirier <theeth@yahoo.com> | 2008-07-16 01:07:13 +0400 |
---|---|---|
committer | Martin Poirier <theeth@yahoo.com> | 2008-07-16 01:07:13 +0400 |
commit | db5a83d083c1517316ff94a011c4a21e0ada7d34 (patch) | |
tree | 57f4c45185a2c8ac998134c820c083352505ec60 | |
parent | 08039ef38fa6d39f756860032659cc3678137ced (diff) |
More merging goodness
fix adjacency list inline instead of having to rebuild fully
reweight joined graphs properly
-rw-r--r-- | source/blender/blenlib/BLI_graph.h | 1 | ||||
-rw-r--r-- | source/blender/blenlib/intern/graph.c | 38 | ||||
-rw-r--r-- | source/blender/src/reeb.c | 64 |
3 files changed, 77 insertions, 26 deletions
diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h index dba02932e02..be5d1f5d10c 100644 --- a/source/blender/blenlib/BLI_graph.h +++ b/source/blender/blenlib/BLI_graph.h @@ -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); diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c index fce9d0b6d95..32d9f3b91b7 100644 --- a/source/blender/blenlib/intern/graph.c +++ b/source/blender/blenlib/intern/graph.c @@ -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; diff --git a/source/blender/src/reeb.c b/source/blender/src/reeb.c index 71eb550fd21..b3fe465830a 100644 --- a/source/blender/src/reeb.c +++ b/source/blender/src/reeb.c @@ -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); |