diff options
author | Martin Poirier <theeth@yahoo.com> | 2007-11-14 04:57:17 +0300 |
---|---|---|
committer | Martin Poirier <theeth@yahoo.com> | 2007-11-14 04:57:17 +0300 |
commit | 166cc3110d6c1d3c648a99cdc56c1137b913bfe4 (patch) | |
tree | 6321f47ecb9f23c33bd26504c0889f46d0692999 /source/blender/src/reeb.c | |
parent | eeb9e1486d6babb9c64bcaa0b29236def05d9f95 (diff) |
Fixing up angle based subdivisions.
Adding symetry detection (right now, only primary symetries and only used to determine bone orientation).
Fixing bugs (infinite loops) in length based subdivisions.
Adding number of post processing passes parameter
Diffstat (limited to 'source/blender/src/reeb.c')
-rw-r--r-- | source/blender/src/reeb.c | 231 |
1 files changed, 195 insertions, 36 deletions
diff --git a/source/blender/src/reeb.c b/source/blender/src/reeb.c index 4f40c51191f..995ba7d577b 100644 --- a/source/blender/src/reeb.c +++ b/source/blender/src/reeb.c @@ -46,6 +46,7 @@ #include "BIF_editmesh.h" #include "BIF_editarmature.h" #include "BIF_interface.h" +#include "BIF_toolbox.h" #include "BKE_global.h" #include "BKE_utildefines.h" @@ -354,6 +355,8 @@ void verifyBuckets(ReebGraph *rg) } } +/************************************** ADJACENCY LIST *************************************************/ + void addArcToNodeAdjacencyList(ReebNode *node, ReebArc *arc) { ReebArc **arclist; @@ -371,6 +374,11 @@ void buildAdjacencyList(ReebGraph *rg) for(node = rg->nodes.first; node; node = node->next) { + if (node->arcs != NULL) + { + MEM_freeN(node->arcs); + } + node->arcs = MEM_callocN((node->degree + 1) * sizeof(ReebArc*), "adjacency list"); } @@ -380,6 +388,51 @@ void buildAdjacencyList(ReebGraph *rg) addArcToNodeAdjacencyList(arc->v2, arc); } } + +int hasAdjacencyList(ReebGraph *rg) +{ + ReebNode *node; + + for(node = rg->nodes.first; node; node = node->next) + { + if (node->arcs == NULL) + { + return 0; + } + } + + return 1; +} + +int countConnectedArcs(ReebGraph *rg, ReebNode *node) +{ + int count = 0; + + /* use adjacency list if present */ + if (node->arcs) + { + ReebArc **arcs; + + for(arcs = node->arcs; *arcs; arcs++) + { + count++; + } + } + else + { + ReebArc *arc; + for(arc = rg->arcs.first; arc; arc = arc->next) + { + if (arc->v1 == node || arc->v2 == node) + { + count++; + } + } + } + + return count; +} + /****************************************** SMOOTHING **************************************************/ void postprocessGraph(ReebGraph *rg, char mode) @@ -397,8 +450,8 @@ void postprocessGraph(ReebGraph *rg, char mode) fac2 = 0.5f; break; case SKGEN_SHARPEN: - fac1 = fac2 = -0.5f; - fac2 = 2.0f; + fac1 = fac2 = -0.25f; + fac2 = 1.5f; break; default: error("Unknown post processing mode"); @@ -419,6 +472,56 @@ void postprocessGraph(ReebGraph *rg, char mode) } } +/********************************************SORTING****************************************************/ + +int compareNodesWeight(void *vnode1, void *vnode2) +{ + ReebNode *node1 = (ReebNode*)vnode1; + ReebNode *node2 = (ReebNode*)vnode2; + + if (node1->weight < node2->weight) + { + return -1; + } + if (node1->weight > node2->weight) + { + return 1; + } + else + { + return 0; + } +} + +void sortNodes(ReebGraph *rg) +{ + BLI_sortlist(&rg->nodes, compareNodesWeight); +} + +int compareArcsWeight(void *varc1, void *varc2) +{ + ReebArc *arc1 = (ReebArc*)varc1; + ReebArc *arc2 = (ReebArc*)varc2; + + if (arc1->v1->weight < arc2->v1->weight) + { + return -1; + } + if (arc1->v1->weight > arc2->v1->weight) + { + return 1; + } + else + { + return 0; + } +} + +void sortArcs(ReebGraph *rg) +{ + BLI_sortlist(&rg->arcs, compareArcsWeight); +} + /****************************************** FILTERING **************************************************/ int compareArcs(void *varc1, void *varc2) @@ -489,14 +592,7 @@ void filterArc(ReebGraph *rg, ReebNode *newNode, ReebNode *removedNode, ReebArc else if (arc->v1->weight > arc->v2->weight) { // Decrement degree from the other node - if (arc->v1 == newNode) - { - arc->v2->degree--; - } - else - { - arc->v1->degree--; - } + OTHER_NODE(arc, newNode)->degree--; BLI_remlink(&rg->arcs, arc); freeArc(arc); @@ -647,8 +743,6 @@ void filterExternalReebGraph(ReebGraph *rg, float threshold) // Merging arc if (merging) { - printf("merging\n"); - printArc(arc); filterArc(rg, newNode, removedNode, arc, 1); } else @@ -731,6 +825,86 @@ void spreadWeight(EditMesh *em) MEM_freeN(verts); } +/*********************************** GRAPH AS TREE FUNCTIONS *******************************************/ + +int subtreeDepth(ReebNode *node) +{ + int depth = 0; + + /* Base case, no arcs leading away */ + if (node->arcs == NULL || *(node->arcs) == NULL) + { + return 0; + } + else + { + ReebArc ** pArc; + + for(pArc = node->arcs; *pArc; pArc++) + { + ReebArc *arc = *pArc; + + /* only arcs that go down the tree */ + if (arc->v1 == node) + { + depth = MAX2(depth, subtreeDepth(arc->v2)); + } + } + } + + return depth + 1; +} + +/*************************************** CYCLE DETECTION ***********************************************/ + +int detectCycle(ReebNode *node) +{ + int value = 0; + + if (node->flags != 0) + { + ReebArc ** pArc; + + for(pArc = node->arcs; *pArc && value == 0; pArc++) + { + ReebArc *arc = *pArc; + + value = detectCycle(OTHER_NODE(arc, node)); + } + } + else + { + value = 1; + } + + return value; +} + +int isGraphAcyclic(ReebGraph *rg) +{ + ReebNode *node; + int value = 0; + + /* NEED TO CHECK IF ADJACENCY LIST EXIST */ + + /* Mark all nodes as not visited */ + for(node = rg->nodes.first; node; node = node->next) + { + node->flags = 0; + } + + /* detectCycles in subgraphs */ + for(node = rg->nodes.first; node && value == 0; node = node->next) + { + /* only for nodes in subgraphs that haven't been visited yet */ + if (node->flags == 0) + { + value = detectCycle(node); + } + } + + return value; +} /******************************************** EXPORT ***************************************************/ @@ -1145,6 +1319,7 @@ ReebNode * addNode(ReebGraph *rg, EditVert *eve, float weight) node = MEM_callocN(sizeof(ReebNode), "reeb node"); + node->flags = 0; // clear flags on init node->arcs = NULL; node->degree = 0; node->weight = weight; @@ -1176,6 +1351,8 @@ ReebEdge * createArc(ReebGraph *rg, ReebNode *node1, ReebNode *node2) arc = MEM_callocN(sizeof(ReebArc), "reeb arc"); edge = MEM_callocN(sizeof(ReebEdge), "reeb edge"); + arc->flags = 0; // clear flags on init + if (node1->weight <= node2->weight) { v1 = node1; @@ -1747,35 +1924,13 @@ void generateSkeleton(void) { EditMesh *em = G.editMesh; ReebGraph *rg = NULL; - short val; + int i; if (em == NULL) return; -#if 0 - val= pupmenu("Orientation%t|X Axis|Y Axis|Z Axis|Distance|Harmonic"); - - if(val>0) { - switch(val) - { - case 1: - case 2: - case 3: - weightFromLoc(em, val - 1); - break; - case 4: - weightFromDistance(em); - break; - case 5: - weightFromDistance(em); - weightToHarmonic(em); - break; - } - } -#else weightFromDistance(em); weightToHarmonic(em); -#endif renormalizeWeight(em, 1.0f); weightToVCol(em); @@ -1825,13 +1980,17 @@ void generateSkeleton(void) verifyBuckets(rg); - if (G.scene->toolsettings->skgen_postpro != SKGEN_NONE) + for(i = 0; i < G.scene->toolsettings->skgen_postpro_passes; i++) { postprocessGraph(rg, G.scene->toolsettings->skgen_postpro); } buildAdjacencyList(rg); + sortNodes(rg); + + sortArcs(rg); + exportGraph(rg, -1); generateSkeletonFromReebGraph(rg); |