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);
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
