From 18bce23a6052540c2ded4bdc548f83106c71c117 Mon Sep 17 00:00:00 2001 From: Martin Poirier Date: Mon, 18 Aug 2008 22:22:56 +0000 Subject: Make subgraph tagging use own index, to not interfere with flagging used to prevent backtracking in different other functions Better deal with chains starting with control bones --- source/blender/blenlib/BLI_graph.h | 6 +- source/blender/blenlib/intern/graph.c | 45 +++++++--- source/blender/include/reeb.h | 2 + source/blender/src/autoarmature.c | 154 +++++++++++++++++++++++++++------- source/blender/src/reeb.c | 45 +++++----- 5 files changed, 185 insertions(+), 67 deletions(-) diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h index 59e73004b8b..0f75701a284 100644 --- a/source/blender/blenlib/BLI_graph.h +++ b/source/blender/blenlib/BLI_graph.h @@ -40,6 +40,8 @@ typedef struct BNode { int degree; struct BArc **arcs; + + int subgraph_index; int symmetry_level; int symmetry_flag; @@ -70,6 +72,8 @@ BNode *BLI_otherNode(BArc *arc, BNode *node); void BLI_freeNode(BGraph *graph, BNode *node); void BLI_removeNode(BGraph *graph, BNode *node); +void BLI_removeArc(BGraph *graph, BArc *arc); + void BLI_flagNodes(BGraph *graph, int flag); void BLI_flagArcs(BGraph *graph, int flag); @@ -84,7 +88,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); +int BLI_subtreeShape(BGraph *graph, BNode *node, BArc *rootArc, int include_root); float BLI_subtreeLength(BNode *node); void BLI_calcGraphLength(BGraph *graph); diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c index 80d770e1034..277a9300f5b 100644 --- a/source/blender/blenlib/intern/graph.c +++ b/source/blender/blenlib/intern/graph.c @@ -64,6 +64,16 @@ BNode *BLI_otherNode(BArc *arc, BNode *node) return (arc->head == node) ? arc->tail : arc->head; } +void BLI_removeArc(BGraph *graph, BArc *arc) +{ + if (graph->free_arc) + { + graph->free_arc(arc); + } + + BLI_freelinkN(&graph->arcs, arc); +} + void BLI_flagNodes(BGraph *graph, int flag) { BNode *node; @@ -236,12 +246,12 @@ void BLI_removeDoubleNodes(BGraph *graph, float limit) void flagSubgraph(BNode *node, int subgraph) { - if (node->flag == 0) + if (node->subgraph_index == 0) { BArc *arc; int i; - node->flag = subgraph; + node->subgraph_index = subgraph; for(i = 0; i < node->degree; i++) { @@ -261,11 +271,14 @@ int BLI_FlagSubgraphs(BGraph *graph) BLI_buildAdjacencyList(graph); } - BLI_flagNodes(graph, 0); + for(node = graph->nodes.first; node; node = node->next) + { + node->subgraph_index = 0; + } for (node = graph->nodes.first; node; node = node->next) { - if (node->flag == 0) + if (node->subgraph_index == 0) { subgraph++; flagSubgraph(node, subgraph); @@ -360,14 +373,16 @@ BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v) /*********************************** GRAPH AS TREE FUNCTIONS *******************************************/ -int BLI_subtreeShape(BNode *node, BArc *rootArc, int include_root) +int subtreeShape(BNode *node, BArc *rootArc, int include_root) { int depth = 0; + node->flag = 1; + if (include_root) { BNode *newNode = BLI_otherNode(rootArc, node); - return BLI_subtreeShape(newNode, rootArc, 0); + return subtreeShape(newNode, rootArc, 0); } else { @@ -383,12 +398,12 @@ int BLI_subtreeShape(BNode *node, BArc *rootArc, int include_root) for(i = 0; i < node->degree; i++) { BArc *arc = node->arcs[i]; + BNode *newNode = BLI_otherNode(arc, node); - /* only arcs that go down the tree */ - if (arc != rootArc) + /* stop immediate and cyclic backtracking */ + if (arc != rootArc && newNode->flag == 0) { - BNode *newNode = BLI_otherNode(arc, node); - depth += BLI_subtreeShape(newNode, arc, 0); + depth += subtreeShape(newNode, arc, 0); } } } @@ -397,6 +412,12 @@ int BLI_subtreeShape(BNode *node, BArc *rootArc, int include_root) } } +int BLI_subtreeShape(BGraph *graph, BNode *node, BArc *rootArc, int include_root) +{ + BLI_flagNodes(graph, 0); + return subtreeShape(node, rootArc, include_root); +} + float BLI_subtreeLength(BNode *node) { float length = 0; @@ -434,7 +455,7 @@ void BLI_calcGraphLength(BGraph *graph) for (node = graph->nodes.first; node; node = node->next) { /* start on an external node of the subgraph */ - if (node->flag == i && node->degree == 1) + if (node->subgraph_index == i && node->degree == 1) { float subgraph_length = BLI_subtreeLength(node); length = MAX2(length, subgraph_length); @@ -883,7 +904,7 @@ void markdownSymmetryArc(BGraph *graph, BArc *arc, BNode *node, int level, float BNode *connectedNode = BLI_otherNode(connectedArc, node); /* symmetry level is positive value, negative values is subtree depth */ - connectedArc->symmetry_level = -BLI_subtreeShape(connectedNode, connectedArc, 0); + connectedArc->symmetry_level = -BLI_subtreeShape(graph, connectedNode, connectedArc, 0); } } diff --git a/source/blender/include/reeb.h b/source/blender/include/reeb.h index 815afed6dfa..76a7bfefe2f 100644 --- a/source/blender/include/reeb.h +++ b/source/blender/include/reeb.h @@ -70,6 +70,8 @@ typedef struct ReebNode { int degree; struct ReebArc **arcs; + int subgraph_index; + int symmetry_level; int symmetry_flag; float symmetry_axis[3]; diff --git a/source/blender/src/autoarmature.c b/source/blender/src/autoarmature.c index 41e727d83f7..ffb82d4b704 100644 --- a/source/blender/src/autoarmature.c +++ b/source/blender/src/autoarmature.c @@ -78,7 +78,7 @@ struct RigArc; struct RigEdge; #define NB_THREADS 4 -#define USE_THREADS +//#define USE_THREADS typedef struct RigGraph { ListBase arcs; @@ -111,6 +111,8 @@ typedef struct RigNode { int degree; struct BArc **arcs; + int subgraph_index; + int symmetry_level; int symmetry_flag; float symmetry_axis[3]; @@ -242,6 +244,8 @@ void RIG_freeRigGraph(BGraph *rg) } BLI_freelistN(&rg->nodes); + BLI_freelistN(&((RigGraph*)rg)->controls); + BLI_ghash_free(((RigGraph*)rg)->bones_map, NULL, NULL); MEM_freeN(rg); @@ -336,17 +340,10 @@ static RigNode *newRigNodeTail(RigGraph *rg, RigArc *arc, float p[3]) return node; } -static void RIG_addEdgeToArc(RigArc *arc, float tail[3], EditBone *bone) +static void RIG_appendEdgeToArc(RigArc *arc, RigEdge *edge) { - RigEdge *edge; - - edge = MEM_callocN(sizeof(RigEdge), "rig edge"); BLI_addtail(&arc->edges, edge); - - VECCOPY(edge->tail, tail); - edge->bone = bone; - if (edge->prev == NULL) { VECCOPY(edge->head, arc->head->p); @@ -365,6 +362,17 @@ static void RIG_addEdgeToArc(RigArc *arc, float tail[3], EditBone *bone) arc->count += 1; } +static void RIG_addEdgeToArc(RigArc *arc, float tail[3], EditBone *bone) +{ + RigEdge *edge; + + edge = MEM_callocN(sizeof(RigEdge), "rig edge"); + + VECCOPY(edge->tail, tail); + edge->bone = bone; + + RIG_appendEdgeToArc(arc, edge); +} /*******************************************************************************************************/ @@ -484,6 +492,73 @@ static void RIG_reconnectControlBones(RigGraph *rg) /*******************************************************************************************************/ +static void RIG_joinArcs(RigGraph *rg, RigNode *node, RigArc *joined_arc1, RigArc *joined_arc2) +{ + RigEdge *edge, *next_edge; + + /* ignore cases where joint is at start or end */ + if (joined_arc1->head == joined_arc2->head || joined_arc1->tail == joined_arc2->tail) + { + return; + } + + /* swap arcs to make sure arc1 is before arc2 */ + if (joined_arc1->head == joined_arc2->tail) + { + RigArc *tmp = joined_arc1; + joined_arc1 = joined_arc2; + joined_arc2 = tmp; + } + + for (edge = joined_arc2->edges.first; edge; edge = next_edge) + { + next_edge = edge->next; + + RIG_appendEdgeToArc(joined_arc1, edge); + } + + joined_arc1->tail = joined_arc2->tail; + + joined_arc2->edges.first = joined_arc2->edges.last = NULL; + + BLI_removeArc((BGraph*)rg, (BArc*)joined_arc2); + + BLI_removeNode((BGraph*)rg, (BNode*)node); +} + +static void RIG_removeNormalNodes(RigGraph *rg) +{ + RigNode *node, *next_node; + + for (node = rg->nodes.first; node; node = next_node) + { + next_node = node->next; + + if (node->degree == 2) + { + RigArc *arc, *joined_arc1 = NULL, *joined_arc2 = NULL; + + for (arc = rg->arcs.first; arc; arc = arc->next) + { + if (arc->head == node || arc->tail == node) + { + if (joined_arc1 == NULL) + { + joined_arc1 = arc; + } + else + { + joined_arc2 = arc; + break; + } + } + } + + RIG_joinArcs(rg, node, joined_arc1, joined_arc2); + } + } +} + static void RIG_arcFromBoneChain(RigGraph *rg, ListBase *list, EditBone *root_bone, RigNode *starting_node) { EditBone *bone, *last_bone = root_bone; @@ -512,7 +587,7 @@ static void RIG_arcFromBoneChain(RigGraph *rg, ListBase *list, EditBone *root_bo } } - if (bone->parent && (bone->flag & BONE_CONNECTED) == 0) + if (bone->parent && (bone->flag & BONE_CONNECTED) == 0 && (bone->parent->flag & BONE_NO_DEFORM) == 0) { RIG_addEdgeToArc(arc, bone->head, NULL); } @@ -534,14 +609,15 @@ static void RIG_arcFromBoneChain(RigGraph *rg, ListBase *list, EditBone *root_bo nb_children = countEditBoneChildren(list, bone); if (nb_children > 1) { - RigNode *end_node; + RigNode *end_node = NULL; int i; if (arc != NULL) { end_node = newRigNodeTail(rg, arc, bone->tail); } - else + /* only create a new node if the parent was a deform bone */ + else if ((bone->flag & BONE_NO_DEFORM) == 0) { end_node = newRigNode(rg, bone->tail); } @@ -650,7 +726,7 @@ void RIG_printArc(RigArc *arc) if (edge->bone) printf("\t\t%s\n", edge->bone->name); } - printf("symmetry level: %i\n", arc->symmetry_level); + printf("symmetry level: %i flag: %i group %i\n", arc->symmetry_level, arc->symmetry_flag, arc->symmetry_group); RIG_printNode((RigNode*)arc->tail, "tail"); } @@ -695,6 +771,8 @@ static RigGraph *armatureToGraph(Object *ob, ListBase *list) BLI_removeDoubleNodes((BGraph*)rg, 0.001); + RIG_removeNormalNodes(rg); + BLI_buildAdjacencyList((BGraph*)rg); RIG_findHead(rg); @@ -703,6 +781,11 @@ static RigGraph *armatureToGraph(Object *ob, ListBase *list) RIG_reconnectControlBones(rg); /* after symmetry, because we use levels to find best match */ + if (BLI_isGraphCyclic((BGraph*)rg)) + { + printf("armature cyclic\n"); + } + return rg; } @@ -1649,15 +1732,15 @@ void *exec_retargetArctoArc(void *param) return NULL; } -static void matchMultiResolutionNode(RigNode *inode, ReebNode *top_node) +static void matchMultiResolutionNode(RigGraph *rigg, RigNode *inode, ReebNode *top_node) { ReebNode *enode; int ishape, eshape; enode = top_node; - ishape = BLI_subtreeShape((BNode*)inode, NULL, 0) % SHAPE_LEVELS; - eshape = BLI_subtreeShape((BNode*)enode, NULL, 0) % SHAPE_LEVELS; + ishape = BLI_subtreeShape((BGraph*)rigg, (BNode*)inode, NULL, 0) % SHAPE_LEVELS; + eshape = BLI_subtreeShape((BGraph*)rigg->link_mesh, (BNode*)enode, NULL, 0) % SHAPE_LEVELS; inode->link_mesh = enode; @@ -1666,17 +1749,17 @@ static void matchMultiResolutionNode(RigNode *inode, ReebNode *top_node) inode->link_mesh = enode; enode = enode->link_down; - eshape = BLI_subtreeShape((BNode*)enode, NULL, 0) % SHAPE_LEVELS; + eshape = BLI_subtreeShape((BGraph*)rigg->link_mesh, (BNode*)enode, NULL, 0) % SHAPE_LEVELS; } } -static void matchMultiResolutionArc(RigNode *start_node, RigArc *next_iarc, ReebArc *next_earc) +static void matchMultiResolutionArc(RigGraph *rigg, RigNode *start_node, RigArc *next_iarc, ReebArc *next_earc) { ReebNode *enode = next_earc->head; int ishape, eshape; - ishape = BLI_subtreeShape((BNode*)start_node, (BArc*)next_iarc, 1) % SHAPE_LEVELS; - eshape = BLI_subtreeShape((BNode*)enode, (BArc*)next_earc, 1) % SHAPE_LEVELS; + ishape = BLI_subtreeShape((BGraph*)rigg, (BNode*)start_node, (BArc*)next_iarc, 1) % SHAPE_LEVELS; + eshape = BLI_subtreeShape((BGraph*)rigg->link_mesh, (BNode*)enode, (BArc*)next_earc, 1) % SHAPE_LEVELS; while (ishape != eshape && next_earc->link_up) { @@ -1684,7 +1767,7 @@ static void matchMultiResolutionArc(RigNode *start_node, RigArc *next_iarc, Reeb next_earc = next_earc->link_up; enode = next_earc->head; - eshape = BLI_subtreeShape((BNode*)enode, (BArc*)next_earc, 1) % SHAPE_LEVELS; + eshape = BLI_subtreeShape((BGraph*)rigg->link_mesh, (BNode*)enode, (BArc*)next_earc, 1) % SHAPE_LEVELS; } next_earc->flag = 1; // mark as taken @@ -1698,15 +1781,15 @@ static void matchMultiResolutionArc(RigNode *start_node, RigArc *next_iarc, Reeb } } -static void matchMultiResolutionStartingNode(ReebGraph *reebg, RigNode *inode) +static void matchMultiResolutionStartingNode(RigGraph *rigg, ReebGraph *reebg, RigNode *inode) { ReebNode *enode; int ishape, eshape; enode = reebg->nodes.first; - ishape = BLI_subtreeShape((BNode*)inode, NULL, 0) % SHAPE_LEVELS; - eshape = BLI_subtreeShape((BNode*)enode, NULL, 0) % SHAPE_LEVELS; + ishape = BLI_subtreeShape((BGraph*)rigg, (BNode*)inode, NULL, 0) % SHAPE_LEVELS; + eshape = BLI_subtreeShape((BGraph*)rigg->link_mesh, (BNode*)enode, NULL, 0) % SHAPE_LEVELS; while (ishape != eshape && reebg->link_up) { @@ -1714,13 +1797,13 @@ static void matchMultiResolutionStartingNode(ReebGraph *reebg, RigNode *inode) enode = reebg->nodes.first; - eshape = BLI_subtreeShape((BNode*)enode, NULL, 0) % SHAPE_LEVELS; + eshape = BLI_subtreeShape((BGraph*)rigg, (BNode*)enode, NULL, 0) % SHAPE_LEVELS; } inode->link_mesh = enode; } -static void findCorrespondingArc(RigArc *start_arc, RigNode *start_node, RigArc *next_iarc) +static void findCorrespondingArc(RigGraph *rigg, RigArc *start_arc, RigNode *start_node, RigArc *next_iarc) { ReebNode *enode = start_node->link_mesh; ReebArc *next_earc; @@ -1734,6 +1817,15 @@ static void findCorrespondingArc(RigArc *start_arc, RigNode *start_node, RigArc for(i = 0; i < enode->degree; i++) { next_earc = (ReebArc*)enode->arcs[i]; + + if (next_earc->flag == 0) + { + printf("candidate (flag %i == %i) (group %i == %i) (level %i == %i)\n", + next_earc->symmetry_flag, symmetry_flag, + next_earc->symmetry_group, symmetry_group, + next_earc->symmetry_level, symmetry_level); + } + if (next_earc->flag == 0 && /* not already taken */ next_earc->symmetry_flag == symmetry_flag && next_earc->symmetry_group == symmetry_group && @@ -1744,7 +1836,7 @@ static void findCorrespondingArc(RigArc *start_arc, RigNode *start_node, RigArc RIG_printArcBones(next_iarc); printf("flag %i -- symmetry level %i -- symmetry flag %i\n", next_earc->flag, next_earc->symmetry_level, next_earc->symmetry_flag); - matchMultiResolutionArc(start_node, next_iarc, next_earc); + matchMultiResolutionArc(rigg, start_node, next_iarc, next_earc); break; } } @@ -1755,7 +1847,7 @@ static void findCorrespondingArc(RigArc *start_arc, RigNode *start_node, RigArc if (enode->link_up) { start_node->link_mesh = enode->link_up; - findCorrespondingArc(start_arc, start_node, next_iarc); + findCorrespondingArc(rigg, start_arc, start_node, next_iarc); } } @@ -1796,7 +1888,7 @@ static void retargetSubgraph(RigGraph *rigg, RigArc *start_arc, RigNode *start_n inode = (RigNode*)BLI_otherNode((BArc*)start_arc, (BNode*)inode); /* match with lowest node with correct shape */ - matchMultiResolutionNode(inode, enode); + matchMultiResolutionNode(rigg, inode, enode); } for(i = 0; i < inode->degree; i++) @@ -1806,7 +1898,7 @@ static void retargetSubgraph(RigGraph *rigg, RigArc *start_arc, RigNode *start_n /* no back tracking */ if (next_iarc != start_arc) { - findCorrespondingArc(start_arc, inode, next_iarc); + findCorrespondingArc(rigg, start_arc, inode, next_iarc); if (next_iarc->link_mesh) { retargetSubgraph(rigg, next_iarc, inode); @@ -1828,7 +1920,7 @@ static void retargetGraphs(RigGraph *rigg) inode = rigg->head; - matchMultiResolutionStartingNode(reebg, inode); + matchMultiResolutionStartingNode(rigg, reebg, inode); retargetSubgraph(rigg, NULL, inode); diff --git a/source/blender/src/reeb.c b/source/blender/src/reeb.c index bc727b19b4b..6f3ab5e8561 100644 --- a/source/blender/src/reeb.c +++ b/source/blender/src/reeb.c @@ -1161,13 +1161,12 @@ void reweightArc(ReebGraph *rg, ReebArc *arc, ReebNode *start_node, float start_ ReebNode *node; float old_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) + if (node->flag == 1) { return; } @@ -1177,7 +1176,7 @@ void reweightArc(ReebGraph *rg, ReebArc *arc, ReebNode *start_node, float start_ flipArc(arc); } - start_node->flag = 0; + start_node->flag = 1; for (i = 0; i < node->degree; i++) { @@ -1185,8 +1184,6 @@ void reweightArc(ReebGraph *rg, ReebArc *arc, ReebNode *start_node, float start_ reweightArc(rg, next_arc, node, end_weight); } - - start_node->flag = flag; /* update only if needed */ if (arc->head->weight != start_weight || arc->tail->weight != end_weight) @@ -1208,6 +1205,8 @@ void reweightSubgraph(ReebGraph *rg, ReebNode *start_node, float start_weight) { int i; + BLI_flagNodes((BGraph*)rg, 0); + for (i = 0; i < start_node->degree; i++) { ReebArc *next_arc = start_node->arcs[i]; @@ -1230,12 +1229,12 @@ int joinSubgraphsEnds(ReebGraph *rg, float threshold, int nb_subgraphs) for (start_node = rg->nodes.first; start_node; start_node = start_node->next) { - if (start_node->flag == subgraph && start_node->degree == 1) + if (start_node->subgraph_index == subgraph && start_node->degree == 1) { for (end_node = rg->nodes.first; end_node; end_node = end_node->next) { - if (end_node->flag != subgraph) + if (end_node->subgraph_index != subgraph) { float distance = VecLenf(start_node->p, end_node->p); @@ -1311,7 +1310,7 @@ void fixSubgraphsOrientation(ReebGraph *rg, int nb_subgraphs) for (node = rg->nodes.first; node; node = node->next) { - if (node->flag == subgraph) + if (node->subgraph_index == subgraph) { if (start_node == NULL || node->weight < start_node->weight) { @@ -3578,26 +3577,26 @@ void REEB_draw() glEnd(); } - VecLerpf(vec, arc->head->p, arc->tail->p, 0.5f); - if (G.scene->toolsettings->skgen_options & SKGEN_DISP_INDEX) { - s += sprintf(s, "%i ", i); - } + VecLerpf(vec, arc->head->p, arc->tail->p, 0.5f); - if (G.scene->toolsettings->skgen_options & SKGEN_DISP_WEIGHT) - { - s += sprintf(s, "w:%0.3f ", arc->tail->weight - arc->head->weight); - } + s += sprintf(s, "%i ", i); - if (G.scene->toolsettings->skgen_options & SKGEN_DISP_LENGTH) - { - s += sprintf(s, "l:%0.3f", arc->length); + if (G.scene->toolsettings->skgen_options & SKGEN_DISP_WEIGHT) + { + s += sprintf(s, "w:%0.3f ", arc->tail->weight - arc->head->weight); + } + + if (G.scene->toolsettings->skgen_options & SKGEN_DISP_LENGTH) + { + s += sprintf(s, "l:%0.3f", arc->length); + } + + glColor3f(0, 1, 0); + glRasterPos3fv(vec); + BMF_DrawString( G.fonts, text); } - - glColor3f(0, 1, 0); - glRasterPos3fv(vec); - BMF_DrawString( G.fonts, text); if (G.scene->toolsettings->skgen_options & SKGEN_DISP_INDEX) { -- cgit v1.2.3