From d4b646103a6cae433d58bf7e2f4953f81358835b Mon Sep 17 00:00:00 2001 From: Martin Poirier Date: Mon, 4 Aug 2008 19:12:42 +0000 Subject: Option to hide embedding dots on display Merge internal and external filtering in a single loop (solve problems caused by order of filtering) Made graph length calculations work on cyclic graphs (it unrolls them) --- source/blender/blenlib/BLI_graph.h | 2 +- source/blender/blenlib/intern/graph.c | 50 +++++----- source/blender/makesdna/DNA_scene_types.h | 1 + source/blender/src/buttons_editing.c | 9 +- source/blender/src/reeb.c | 149 +++++++++++++----------------- 5 files changed, 94 insertions(+), 117 deletions(-) diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h index 66cf2a22842..89f21b919e2 100644 --- a/source/blender/blenlib/BLI_graph.h +++ b/source/blender/blenlib/BLI_graph.h @@ -85,7 +85,7 @@ void BLI_ReflagSubgraph(BGraph *graph, int old_subgraph, int new_subgraph); #define SHAPE_RADIX 10 /* each shape level is encoded this base */ int BLI_subtreeShape(BNode *node, BArc *rootArc, int include_root); -float BLI_subtreeLength(BNode *node, BArc *rootArc); +float BLI_subtreeLength(BNode *node); void BLI_calcGraphLength(BGraph *graph); void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced); diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c index aa899042a58..80d770e1034 100644 --- a/source/blender/blenlib/intern/graph.c +++ b/source/blender/blenlib/intern/graph.c @@ -397,57 +397,53 @@ int BLI_subtreeShape(BNode *node, BArc *rootArc, int include_root) } } -float BLI_subtreeLength(BNode *node, BArc *rootArc) +float BLI_subtreeLength(BNode *node) { float length = 0; int i; + node->flag = 0; /* flag node as visited */ + for(i = 0; i < node->degree; i++) { BArc *arc = node->arcs[i]; + BNode *other_node = BLI_otherNode(arc, node); - /* don't go back on the root arc */ - if (arc != rootArc) + if (other_node->flag != 0) { - length = MAX2(length, BLI_subtreeLength(BLI_otherNode(arc, node), arc)); + float subgraph_length = arc->length + BLI_subtreeLength(other_node); + length = MAX2(length, subgraph_length); } } - if (rootArc) - { - length += rootArc->length; - } - return length; } void BLI_calcGraphLength(BGraph *graph) { - if (BLI_isGraphCyclic(graph) == 0) + float length = 0; + int nb_subgraphs; + int i; + + nb_subgraphs = BLI_FlagSubgraphs(graph); + + for (i = 1; i <= nb_subgraphs; i++) { - float length = 0; - int nb_subgraphs; - int i; + BNode *node; - nb_subgraphs = BLI_FlagSubgraphs(graph); - - for (i = 1; i <= nb_subgraphs; i++) + for (node = graph->nodes.first; node; node = node->next) { - BNode *node; - - for (node = graph->nodes.first; node; node = node->next) + /* start on an external node of the subgraph */ + if (node->flag == i && node->degree == 1) { - /* start on an external node of the subgraph */ - if (node->flag == i && node->degree == 1) - { - length = MAX2(length, BLI_subtreeLength(node, NULL)); - break; - } + float subgraph_length = BLI_subtreeLength(node); + length = MAX2(length, subgraph_length); + break; } } - - graph->length = length; } + + graph->length = length; } /********************************* SYMMETRY DETECTION **************************************************/ diff --git a/source/blender/makesdna/DNA_scene_types.h b/source/blender/makesdna/DNA_scene_types.h index e7376534e27..55d5a68662a 100644 --- a/source/blender/makesdna/DNA_scene_types.h +++ b/source/blender/makesdna/DNA_scene_types.h @@ -849,6 +849,7 @@ typedef struct Scene { #define SKGEN_DISP_LENGTH (1 << 10) #define SKGEN_DISP_WEIGHT (1 << 11) #define SKGEN_DISP_ORIG (1 << 12) +#define SKGEN_DISP_EMBED (1 << 13) #define SKGEN_SUB_LENGTH 0 #define SKGEN_SUB_ANGLE 1 diff --git a/source/blender/src/buttons_editing.c b/source/blender/src/buttons_editing.c index 50c9b50c3b8..517ae2b76ca 100644 --- a/source/blender/src/buttons_editing.c +++ b/source/blender/src/buttons_editing.c @@ -5046,9 +5046,12 @@ static void editing_panel_mesh_skgen_display(Object *ob, Mesh *me) skgen_graph_block(block); - uiDefButBitS(block, TOG, SKGEN_DISP_LENGTH, REDRAWVIEW3D, "Length", 1025, 40, 83,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0, "Show Length"); - uiDefButBitS(block, TOG, SKGEN_DISP_WEIGHT, REDRAWVIEW3D, "Weight", 1108, 40, 83,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0, "Show Weight"); - uiDefButBitS(block, TOG, SKGEN_DISP_ORIG, REDRAWVIEW3D, "Original", 1191, 40, 84,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0, "Show Original Graph"); + uiBlockBeginAlign(block); + uiDefButBitS(block, TOG, SKGEN_DISP_LENGTH, REDRAWVIEW3D, "Length", 1025, 40, 63,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0, "Show Length"); + uiDefButBitS(block, TOG, SKGEN_DISP_WEIGHT, REDRAWVIEW3D, "Weight", 1088, 40, 63,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0, "Show Weight"); + uiDefButBitS(block, TOG, SKGEN_DISP_EMBED, REDRAWVIEW3D, "Embed", 1151, 40, 62,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0, "Show Arc Embedings"); + uiDefButBitS(block, TOG, SKGEN_DISP_ORIG, REDRAWVIEW3D, "Original", 1213, 40, 62,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0, "Show Original Graph"); + uiBlockEndAlign(block); uiDefButC(block, NUM, REDRAWVIEW3D, "Level:", 1025, 20, 125,19, &G.scene->toolsettings->skgen_multi_level, 0, REEB_MAX_MULTI_LEVEL, 1, 0,"Specify the level to draw"); } diff --git a/source/blender/src/reeb.c b/source/blender/src/reeb.c index a4d2887ae04..d601ec2ab76 100644 --- a/source/blender/src/reeb.c +++ b/source/blender/src/reeb.c @@ -744,6 +744,11 @@ static void ExtendArcBuckets(ReebArc *arc) float average_length = 0, length; int padding_head = 0, padding_tail = 0; + if (arc->bcount == 0) + { + return; /* failsafe, shouldn't happen */ + } + initArcIterator(&iter, arc, arc->head); for ( previous = nextBucket(&iter), bucket = nextBucket(&iter); @@ -778,6 +783,8 @@ static void ExtendArcBuckets(ReebArc *arc) memcpy(arc->buckets + padding_head, old_buckets, arc->bcount * sizeof(EmbedBucket)); arc->bcount = padding_head + arc->bcount + padding_tail; + + MEM_freeN(old_buckets); } if (padding_head > 0) @@ -1437,41 +1444,27 @@ void filterNullReebGraph(ReebGraph *rg) } } -int filterInternalReebGraph(ReebGraph *rg, float threshold) +int filterInternalExternalReebGraph(ReebGraph *rg, float threshold_internal, float threshold_external) { ReebArc *arc = NULL, *nextArc = NULL; int value = 0; BLI_sortlist(&rg->arcs, compareArcs); - arc = rg->arcs.first; - while(arc) + + for (arc = rg->arcs.first; arc; arc = nextArc) { nextArc = arc->next; // Only collapse non-terminal arcs that are shorter than threshold - if (arc->head->degree > 1 && arc->tail->degree > 1 && (lengthArc(arc) < threshold)) + if (threshold_internal > 0 && arc->head->degree > 1 && arc->tail->degree > 1 && (lengthArc(arc) < threshold_internal)) { 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) - { - newNode = arc->head; - removedNode = arc->tail; - } - else - { - 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); @@ -1485,26 +1478,8 @@ int filterInternalReebGraph(ReebGraph *rg, float threshold) value = 1; } - arc = nextArc; - } - - return value; -} - -int filterExternalReebGraph(ReebGraph *rg, float threshold) -{ - ReebArc *arc = NULL, *nextArc = NULL; - int value = 0; - - BLI_sortlist(&rg->arcs, compareArcs); - - - for (arc = rg->arcs.first; arc; arc = nextArc) - { - nextArc = arc->next; - // Only collapse terminal arcs that are shorter than threshold - if ((arc->head->degree == 1 || arc->tail->degree == 1) && (lengthArc(arc) < threshold)) + else if (threshold_external > 0 && (arc->head->degree == 1 || arc->tail->degree == 1) && (lengthArc(arc) < threshold_external)) { ReebNode *terminalNode = NULL; ReebNode *middleNode = NULL; @@ -1552,32 +1527,28 @@ int filterExternalReebGraph(ReebGraph *rg, float threshold) int filterCyclesReebGraph(ReebGraph *rg, float distance_threshold) { + ReebArc *arc1, *arc2; + ReebArc *next2; int filtered = 0; - if (BLI_isGraphCyclic((BGraph*)rg)) + for (arc1 = rg->arcs.first; arc1; arc1 = arc1->next) { - ReebArc *arc1, *arc2; - ReebArc *next2; - - for (arc1 = rg->arcs.first; arc1; arc1 = arc1->next) + for (arc2 = arc1->next; arc2; arc2 = next2) { - for (arc2 = rg->arcs.first; arc2; arc2 = next2) + next2 = arc2->next; + if (arc1 != arc2 && arc1->head == arc2->head && arc1->tail == arc2->tail) { - 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); + 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); + NodeDegreeDecrement(rg, arc1->head); + NodeDegreeDecrement(rg, arc1->tail); - BLI_remlink(&rg->arcs, arc2); - REEB_freeArc((BArc*)arc2); - - filtered = 1; - } + BLI_remlink(&rg->arcs, arc2); + REEB_freeArc((BArc*)arc2); + + filtered = 1; } } } @@ -1765,22 +1736,24 @@ void filterGraph(ReebGraph *rg, short options, float threshold_internal, float t verifyNodeDegree(rg); - /* filter until there's nothing more to do */ - while (done == 1) + if ((options & SKGEN_FILTER_EXTERNAL) == 0) { - done = 0; /* no work done yet */ - - if (options & SKGEN_FILTER_INTERNAL) - { -// done |= filterInternalReebGraph(rg, threshold_internal * rg->resolution); - done |= filterInternalReebGraph(rg, threshold_internal); - verifyNodeDegree(rg); - } + threshold_external = 0; + } + + if ((options & SKGEN_FILTER_INTERNAL) == 0) + { + threshold_internal = 0; + } - if (options & SKGEN_FILTER_EXTERNAL) + if (threshold_internal > 0 || threshold_external > 0) + { + /* filter until there's nothing more to do */ + while (done == 1) { -// done |= filterExternalReebGraph(rg, threshold_external * rg->resolution); - done |= filterExternalReebGraph(rg, threshold_external); + done = 0; /* no work done yet */ + + done = filterInternalExternalReebGraph(rg, threshold_internal, threshold_external); verifyNodeDegree(rg); } } @@ -1788,7 +1761,6 @@ void filterGraph(ReebGraph *rg, short options, float threshold_internal, float t if (options & SKGEN_FILTER_SMART) { filterSmartReebGraph(rg, 0.5); - BLI_buildAdjacencyList((BGraph*)rg); filterCyclesReebGraph(rg, 0.5); } @@ -3338,6 +3310,8 @@ ReebGraph *BIF_ReebGraphMultiFromEditMesh(void) joinSubgraphs(rg, 1.0); + BLI_buildAdjacencyList((BGraph*)rg); + /* calc length before copy, so we have same length on all levels */ BLI_calcGraphLength((BGraph*)rg); @@ -3351,8 +3325,8 @@ ReebGraph *BIF_ReebGraphMultiFromEditMesh(void) /* don't filter last level */ if (rgi->link_up) { - float internal_threshold = rg->length * G.scene->toolsettings->skgen_threshold_internal * (i / (float)nb_levels); - float external_threshold = rg->length * G.scene->toolsettings->skgen_threshold_external * (i / (float)nb_levels); + float internal_threshold; + float external_threshold; /* filter internal progressively in second half only*/ if (i > nb_levels / 2) @@ -3530,22 +3504,25 @@ void REEB_draw() glVertex3fv(arc->tail->p); glEnd(); - - glColor3f(1, 1, 1); - glBegin(GL_POINTS); - glVertex3fv(arc->head->p); - glVertex3fv(arc->tail->p); - - glColor3f(0.5f, 0.5f, 1); - if (arc->bcount) - { - initArcIterator(&iter, arc, arc->head); - for (bucket = nextBucket(&iter); bucket; bucket = nextBucket(&iter)) + + if (G.scene->toolsettings->skgen_options & SKGEN_DISP_EMBED) + { + glColor3f(1, 1, 1); + glBegin(GL_POINTS); + glVertex3fv(arc->head->p); + glVertex3fv(arc->tail->p); + + glColor3f(0.5f, 0.5f, 1); + if (arc->bcount) { - glVertex3fv(bucket->p); + initArcIterator(&iter, arc, arc->head); + for (bucket = nextBucket(&iter); bucket; bucket = nextBucket(&iter)) + { + glVertex3fv(bucket->p); + } } - } - glEnd(); + glEnd(); + } VecLerpf(vec, arc->head->p, arc->tail->p, 0.5f); -- cgit v1.2.3