Revision: 15410
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15410
Author: theeth
Date: 2008-07-02 23:36:45 +0200 (Wed, 02 Jul 2008)
Log Message:
-----------
Remove some debugging prints
Better symmetry detection using subtree shapes instead of depth
Fix the bug with flipping arcs caused by internal filtering
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-02 21:01:59 UTC (rev 15409)
+++ branches/harmonic-skeleton/source/blender/blenlib/BLI_graph.h
2008-07-02 21:36:45 UTC (rev 15410)
@@ -72,6 +72,7 @@
int BLI_hasAdjacencyList(BGraph *rg);
void BLI_buildAdjacencyList(BGraph *rg);
+void BLI_rebuildAdjacencyList(BGraph* rg);
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-02 21:01:59 UTC (rev 15409)
+++ branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c
2008-07-02 21:36:45 UTC (rev 15410)
@@ -84,6 +84,12 @@
node->flag++;
}
+void BLI_rebuildAdjacencyList(BGraph *rg)
+{
+ BLI_freeAdjacencyList(rg);
+ BLI_buildAdjacencyList(rg);
+}
+
void BLI_buildAdjacencyList(BGraph *rg)
{
BNode *node;
@@ -310,7 +316,7 @@
/*********************************** GRAPH AS TREE FUNCTIONS
*******************************************/
-int BLI_subtreeDepth(BNode *node, BArc *rootArc)
+int BLI_subtreeShape(BNode *node, BArc *rootArc)
{
int depth = 0;
@@ -331,12 +337,14 @@
if (arc != rootArc)
{
BNode *newNode = BLI_otherNode(arc, node);
- depth = MAX2(depth, BLI_subtreeDepth(newNode,
arc));
+ //depth = MAX2(depth, BLI_subtreeShape(newNode,
arc));
+ depth += BLI_subtreeShape(newNode, arc);
}
}
}
- return depth + 1; //BLI_countlist(&rootArc->edges);
+ //return depth + 1;
+ return 10 * depth + 1;
}
/********************************* SYMMETRY DETECTION
**************************************************/
@@ -519,11 +527,6 @@
}
}
}
-
- for (i = 0; i < total; i++)
- {
- printf("length %f\n", ring[i].arc->length);
- }
/* Dispatch to specific symmetry tests */
first = 0;
@@ -556,7 +559,6 @@
if (sub_total == 1)
{
- printf("no dispatch\n");
/* NOTHING TO DO */
}
else if (sub_total == 2)
@@ -564,8 +566,6 @@
BArc *arc1, *arc2;
BNode *node1, *node2;
- printf("dispatch axial\n");
-
arc1 = ring[first].arc;
arc2 = ring[last].arc;
@@ -579,8 +579,6 @@
RadialArc *sub_ring =
MEM_callocN(sizeof(RadialArc) * sub_total, "radial symmetry ring");
int sub_i;
- printf("dispatch radial sub ring\n");
-
/* fill in the sub ring */
for (sub_i = 0; sub_i < sub_total; sub_i++)
{
@@ -593,8 +591,6 @@
}
else if (sub_total == total)
{
- printf("dispatch radial full ring\n");
-
testRadialSymmetry(graph, root_node, ring,
total, axis, limit, group);
}
@@ -660,7 +656,7 @@
}
else
{
- printf("not symmetric\n");
+ /* NOT SYMMETRIC */
}
}
@@ -700,8 +696,6 @@
return;
}
- printf("symmetry length %f <> %f\n", arc1->length, arc2->length);
-
testAxialSymmetry(graph, root_node, node1, node2, arc1, arc2, axis,
limit, 1);
}
@@ -777,7 +771,7 @@
BNode *connectedNode = BLI_otherNode(connectedArc,
node);
/* symmetry level is positive value, negative values is
subtree depth */
- connectedArc->symmetry_level =
-BLI_subtreeDepth(connectedNode, connectedArc);
+ connectedArc->symmetry_level =
-BLI_subtreeShape(connectedNode, connectedArc);
}
}
@@ -854,7 +848,6 @@
if (BLI_isGraphCyclic(graph))
{
- printf("cyclic\n");
return;
}
Modified: branches/harmonic-skeleton/source/blender/src/reeb.c
===================================================================
--- branches/harmonic-skeleton/source/blender/src/reeb.c 2008-07-02
21:01:59 UTC (rev 15409)
+++ branches/harmonic-skeleton/source/blender/src/reeb.c 2008-07-02
21:36:45 UTC (rev 15410)
@@ -93,6 +93,7 @@
} MergeDirection;
int mergeArcs(ReebGraph *rg, ReebArc *a0, ReebArc *a1);
+void mergeArcEdges(ReebGraph *rg, ReebArc *aDst, ReebArc *aSrc, MergeDirection
direction);
int mergeConnectedArcs(ReebGraph *rg, ReebArc *a0, ReebArc *a1);
EditEdge * NextEdgeForVert(EditMesh *em, EditVert *v);
void mergeArcFaces(ReebGraph *rg, ReebArc *aDst, ReebArc *aSrc);
@@ -824,18 +825,20 @@
REEB_freeArc((BArc*)arc);
}
}
-#if 0
// Remove flipped arcs
else if (((ReebNode*)arc->head)->weight >
((ReebNode*)arc->tail)->weight)
{
+#if 0
// Decrement degree from the other node
//BLI_otherNode((BArc*)arc,
(BNode*)newNode)->degree--;
NodeDegreeDecrement(rg,
(ReebNode*)BLI_otherNode((BArc*)arc, (BNode*)newNode));
BLI_remlink(&rg->arcs, arc);
REEB_freeArc((BArc*)arc);
- }
+#else
+ printf("flipped\n");
#endif
+ }
else
{
//newNode->degree++; // incrementing degree
since we're adding an arc
@@ -911,6 +914,7 @@
ReebNode *newNode = NULL;
ReebNode *removedNode = NULL;
+#if 0 // Old method
/* Keep the node with the highestn number of connected
arcs */
if (arc->head->degree >= arc->tail->degree)
{
@@ -922,6 +926,11 @@
newNode = arc->tail;
removedNode = arc->head;
}
+#else
+ /* Always remove lower node, so arcs don't flip */
+ newNode = arc->head;
+ removedNode = arc->tail;
+#endif
filterArc(rg, newNode, removedNode, arc, 1);
@@ -1017,6 +1026,41 @@
return value;
}
+int filterCyclesReebGraph(ReebGraph *rg, float distance_threshold)
+{
+ int filtered = 0;
+
+ if (BLI_isGraphCyclic((BGraph*)rg))
+ {
+ ReebArc *arc1, *arc2;
+ ReebArc *next2;
+
+ for (arc1 = rg->arcs.first; arc1; arc1 = arc1->next)
+ {
+ for (arc2 = rg->arcs.first; arc2; arc2 = next2)
+ {
+ next2 = arc2->next;
+ if (arc1 != arc2 && arc1->head == arc2->head &&
arc1->tail == arc2->tail)
+ {
+ mergeArcEdges(rg, arc1, arc2,
MERGE_APPEND);
+ mergeArcFaces(rg, arc1, arc2);
+ mergeArcBuckets(arc1, arc2,
arc1->head->weight, arc1->tail->weight);
+
+ NodeDegreeDecrement(rg, arc1->head);
+ NodeDegreeDecrement(rg, arc1->tail);
+
+ BLI_remlink(&rg->arcs, arc2);
+ REEB_freeArc((BArc*)arc2);
+
+ filtered = 1;
+ }
+ }
+ }
+ }
+
+ return filtered;
+}
+
int filterSmartReebGraph(ReebGraph *rg, float threshold)
{
ReebArc *arc = NULL, *nextArc = NULL;
@@ -2634,17 +2678,27 @@
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");
+ printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)rg));
+
i = 1;
/* filter until there's nothing more to do */
while (i == 1)
@@ -2667,6 +2721,8 @@
if (G.scene->toolsettings->skgen_options & SKGEN_FILTER_SMART)
{
filterSmartReebGraph(rg, 0.5);
+ BLI_rebuildAdjacencyList((BGraph*)rg);
+ filterCyclesReebGraph(rg, 0.5);
}
#ifdef DEBUG_REEB
@@ -2690,7 +2746,7 @@
postprocessGraph(rg, G.scene->toolsettings->skgen_postpro);
}
- BLI_buildAdjacencyList((BGraph*)rg);
+ BLI_rebuildAdjacencyList((BGraph*)rg);
sortNodes(rg);
@@ -2700,6 +2756,9 @@
calculateGraphLength(rg);
+ printf("DONE\n");
+ printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)rg));
+
return rg;
}
@@ -2714,115 +2773,11 @@
void BIF_GlobalReebGraphFromEditMesh(void)
{
- EditMesh *em = G.editMesh;
- int i;
-
- if (em == NULL)
- return;
-
BIF_GlobalReebFree();
-
- if (weightFromDistance(em) == 0)
- {
- error("No selected vertex\n");
- return;
- }
- renormalizeWeight(em, 1.0f);
+ GLOBAL_RG = BIF_ReebGraphFromEditMesh();
- if (G.scene->toolsettings->skgen_options & SKGEN_HARMONIC)
- {
- weightToHarmonic(em);
- }
-
-#ifdef DEBUG_REEB
- weightToVCol(em, 0);
-#endif
-
- GLOBAL_RG = generateReebGraph(em,
G.scene->toolsettings->skgen_resolution);
-
- verifyNodeDegree(GLOBAL_RG);
-
- REEB_exportGraph(GLOBAL_RG, -1);
-
- verifyBuckets(GLOBAL_RG);
-
- verifyFaces(GLOBAL_RG);
-
- printf("GENERATED\n");
- printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)GLOBAL_RG));
-
- /* Remove arcs without embedding */
- filterNullReebGraph(GLOBAL_RG);
-
- verifyNodeDegree(GLOBAL_RG);
-
- BLI_freeAdjacencyList((BGraph*)GLOBAL_RG);
-
- printf("NULL FILTERED\n");
- printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)GLOBAL_RG));
-
- verifyBuckets(GLOBAL_RG);
-
- i = 1;
- /* filter until there's nothing more to do */
- while (i == 1)
- {
- i = 0; /* no work done yet */
-
- if (G.scene->toolsettings->skgen_options &
SKGEN_FILTER_EXTERNAL)
- {
- i |= filterExternalReebGraph(GLOBAL_RG,
G.scene->toolsettings->skgen_threshold_external *
G.scene->toolsettings->skgen_resolution);
- }
-
- verifyBuckets(GLOBAL_RG);
-
- if (G.scene->toolsettings->skgen_options &
SKGEN_FILTER_INTERNAL)
- {
- i |= filterInternalReebGraph(GLOBAL_RG,
G.scene->toolsettings->skgen_threshold_internal *
G.scene->toolsettings->skgen_resolution);
- }
- }
-
- if (G.scene->toolsettings->skgen_options & SKGEN_FILTER_SMART)
- {
- filterSmartReebGraph(GLOBAL_RG, 0.5);
- }
-
- verifyBuckets(GLOBAL_RG);
-
- repositionNodes(GLOBAL_RG);
-
- verifyBuckets(GLOBAL_RG);
-
- /* Filtering might have created degree 2 nodes, so remove them */
- removeNormalNodes(GLOBAL_RG);
-
- verifyBuckets(GLOBAL_RG);
-
-#ifdef DEBUG_REEB
- arcToVCol(GLOBAL_RG, em, 1);
- //angleToVCol(em, 1);
-#endif
-
- for(i = 0; i < G.scene->toolsettings->skgen_postpro_passes; i++)
- {
- postprocessGraph(GLOBAL_RG,
G.scene->toolsettings->skgen_postpro);
- }
-
- BLI_buildAdjacencyList((BGraph*)GLOBAL_RG);
-
- sortNodes(GLOBAL_RG);
-
- sortArcs(GLOBAL_RG);
-
- REEB_exportGraph(GLOBAL_RG, -1);
-
- calculateGraphLength(GLOBAL_RG);
-
BLI_markdownSymmetry((BGraph*)GLOBAL_RG, GLOBAL_RG->nodes.first,
G.scene->toolsettings->skgen_symmetry_limit);
-
- printf("DONE\n");
- printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)GLOBAL_RG));
}
void REEB_draw()
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
