[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [16161] branches/harmonic-skeleton/source/ blender/src/reeb.c: For now, don't join subgraphs if graphs are cyclic ( this causes problem when reweighting because it uses a depth first method which doesn 't work with cycles properly)
Martin Poirier
theeth at yahoo.com
Mon Aug 18 02:08:22 CEST 2008
Revision: 16161
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=16161
Author: theeth
Date: 2008-08-18 02:08:22 +0200 (Mon, 18 Aug 2008)
Log Message:
-----------
For now, don't join subgraphs if graphs are cyclic (this causes problem when reweighting because it uses a depth first method which doesn't work with cycles properly)
Modified Paths:
--------------
branches/harmonic-skeleton/source/blender/src/reeb.c
Modified: branches/harmonic-skeleton/source/blender/src/reeb.c
===================================================================
--- branches/harmonic-skeleton/source/blender/src/reeb.c 2008-08-17 23:48:16 UTC (rev 16160)
+++ branches/harmonic-skeleton/source/blender/src/reeb.c 2008-08-18 00:08:22 UTC (rev 16161)
@@ -451,39 +451,44 @@
#endif
}
-void verifyBuckets(ReebGraph *rg)
+void verifyBucketsArc(ReebGraph *rg, ReebArc *arc)
{
-#ifdef DEBUG_REEB
- ReebArc *arc = NULL;
- for(arc = rg->arcs.first; arc; arc = arc->next)
+ ReebNode *head = (ReebNode*)arc->head;
+ ReebNode *tail = (ReebNode*)arc->tail;
+
+ if (arc->bcount > 0)
{
- ReebNode *head = (ReebNode*)arc->head;
- ReebNode *tail = (ReebNode*)arc->tail;
-
- if (arc->bcount > 0)
+ int i;
+ for(i = 0; i < arc->bcount; i++)
{
- int i;
- for(i = 0; i < arc->bcount; i++)
+ if (arc->buckets[i].nv == 0)
{
- if (arc->buckets[i].nv == 0)
- {
- printArc(arc);
- printf("count error in bucket %i/%i\n", i+1, arc->bcount);
- }
- }
-
- if (ceil(head->weight) < arc->buckets[0].val)
- {
printArc(arc);
- printf("alloc error in first bucket: %f should be %f \n", arc->buckets[0].val, ceil(head->weight));
+ printf("count error in bucket %i/%i\n", i+1, arc->bcount);
}
- if (floor(tail->weight) < arc->buckets[arc->bcount - 1].val)
- {
- printArc(arc);
- printf("alloc error in last bucket: %f should be %f \n", arc->buckets[arc->bcount - 1].val, floor(tail->weight));
- }
}
+
+ if (ceil(head->weight) != arc->buckets[0].val)
+ {
+ printArc(arc);
+ printf("alloc error in first bucket: %f should be %f \n", arc->buckets[0].val, ceil(head->weight));
+ }
+ if (floor(tail->weight) != arc->buckets[arc->bcount - 1].val)
+ {
+ printArc(arc);
+ printf("alloc error in last bucket: %f should be %f \n", arc->buckets[arc->bcount - 1].val, floor(tail->weight));
+ }
}
+}
+
+void verifyBuckets(ReebGraph *rg)
+{
+#ifdef DEBUG_REEB
+ ReebArc *arc = NULL;
+ for(arc = rg->arcs.first; arc; arc = arc->next)
+ {
+ verifyBucketsArc(rg, arc);
+ }
#endif
}
@@ -500,6 +505,19 @@
#endif
}
+void verifyArcs(ReebGraph *rg)
+{
+ ReebArc *arc;
+
+ for (arc = rg->arcs.first; arc; arc = arc->next)
+ {
+ if (arc->head->weight > arc->tail->weight)
+ {
+ printf("FLIPPED ARC!\n");
+ }
+ }
+}
+
void verifyMultiResolutionLinks(ReebGraph *rg, int level)
{
#ifdef DEBUG_REEB
@@ -1138,32 +1156,40 @@
}
/******************************************* JOINING ***************************************************/
-void reweightArc(ReebArc *arc, ReebNode *start_node, float start_weight)
+void reweightArc(ReebGraph *rg, ReebArc *arc, ReebNode *start_node, float start_weight)
{
ReebNode *node;
float old_weight;
- float end_weight = start_weight + (arc->tail->weight - arc->head->weight);
+ float end_weight = start_weight + ABS(arc->tail->weight - arc->head->weight);
+ int flag = start_node->flag;
int i;
+ node = (ReebNode*)BLI_otherNode((BArc*)arc, (BNode*)start_node);
+
+ /* prevent backtracking */
+ if (node->flag == 0)
+ {
+ return;
+ }
+
if (arc->tail == start_node)
{
flipArc(arc);
}
- node = arc->tail;
+ start_node->flag = 0;
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);
- }
+ reweightArc(rg, next_arc, node, end_weight);
}
+
+ start_node->flag = flag;
/* update only if needed */
- if (arc->head->weight != start_weight)
+ if (arc->head->weight != start_weight || arc->tail->weight != end_weight)
{
old_weight = arc->head->weight; /* backup head weight, other arcs need it intact, it will be fixed by the source arc */
@@ -1186,7 +1212,7 @@
{
ReebArc *next_arc = start_node->arcs[i];
- reweightArc(next_arc, start_node, start_weight);
+ reweightArc(rg, next_arc, start_node, start_weight);
}
start_node->weight = start_weight;
}
@@ -1249,7 +1275,7 @@
start_arc->head = end_node;
- merging = 1;
+ merging = 2;
}
@@ -1308,6 +1334,11 @@
BLI_buildAdjacencyList((BGraph*)rg);
+ if (BLI_isGraphCyclic((BGraph*)rg))
+ {
+ /* don't deal with cyclic graphs YET */
+ return 0;
+ }
/* sort nodes before flagging subgraphs to make sure root node is subgraph 0 */
sortNodes(rg);
@@ -1326,7 +1357,6 @@
if (joined)
{
- verifyNodeDegree(rg);
removeNormalNodes(rg);
BLI_buildAdjacencyList((BGraph*)rg);
}
@@ -1503,7 +1533,7 @@
/* Always remove lower node, so arcs don't flip */
newNode = arc->head;
removedNode = arc->tail;
-
+
filterArc(rg, newNode, removedNode, arc, 1);
// Reset nextArc, it might have changed
@@ -1772,8 +1802,6 @@
calculateGraphLength(rg);
- verifyNodeDegree(rg);
-
if ((options & SKGEN_FILTER_EXTERNAL) == 0)
{
threshold_external = 0;
@@ -1792,7 +1820,6 @@
done = 0; /* no work done yet */
done = filterInternalExternalReebGraph(rg, threshold_internal, threshold_external);
- verifyNodeDegree(rg);
}
}
@@ -1801,8 +1828,6 @@
filterSmartReebGraph(rg, 0.5);
filterCyclesReebGraph(rg, 0.5);
}
-
- verifyNodeDegree(rg);
repositionNodes(rg);
@@ -2489,7 +2514,6 @@
if (countfaces % 100 == 0)
{
printf("\rface %i of %i", countfaces, totfaces);
- verifyFaces(rg);
}
#endif
}
@@ -3347,7 +3371,7 @@
removeNormalNodes(rg);
joinSubgraphs(rg, 1.0);
-
+
BLI_buildAdjacencyList((BGraph*)rg);
/* calc length before copy, so we have same length on all levels */
@@ -3420,22 +3444,14 @@
rg = generateReebGraph(em, G.scene->toolsettings->skgen_resolution);
- verifyNodeDegree(rg);
-
REEB_exportGraph(rg, -1);
- verifyBuckets(rg);
-
- verifyFaces(rg);
-
printf("GENERATED\n");
printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)rg));
/* Remove arcs without embedding */
filterNullReebGraph(rg);
- verifyBuckets(rg);
-
BLI_freeAdjacencyList((BGraph*)rg);
printf("NULL FILTERED\n");
More information about the Bf-blender-cvs
mailing list