Option to hide embedding dots on display
authorMartin Poirier <theeth@yahoo.com>
Mon, 4 Aug 2008 19:12:42 +0000 (19:12 +0000)
committerMartin Poirier <theeth@yahoo.com>
Mon, 4 Aug 2008 19:12:42 +0000 (19:12 +0000)
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
source/blender/blenlib/intern/graph.c
source/blender/makesdna/DNA_scene_types.h
source/blender/src/buttons_editing.c
source/blender/src/reeb.c

index 66cf2a2284254cded416b52990442db07701a6b2..89f21b919e293c5e0e291ad1e88dd3e5b9857e7f 100644 (file)
@@ -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);
index aa899042a58117e831135b28ff738e933f5c9c04..80d770e103477e236c24689d1e091342fcba1528 100644 (file)
@@ -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 **************************************************/
index e7376534e27f6beb4a60b144a824d492000f7d9b..55d5a68662a7b9139b977407e380d8b57af46489 100644 (file)
@@ -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
index 50c9b50c3b81db8e921a9b60fa864ddad8d0884d..517ae2b76cacd1b84545627e77542698c5798879 100644 (file)
@@ -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");
 }
index a4d2887ae04c2af3170ca8c75638138ee72e2d02..d601ec2ab769fdd6904fd6d788e89f9927580ba9 100644 (file)
@@ -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);