diff options
author | Martin Poirier <theeth@yahoo.com> | 2008-05-30 21:42:02 +0400 |
---|---|---|
committer | Martin Poirier <theeth@yahoo.com> | 2008-05-30 21:42:02 +0400 |
commit | 08750f66a46979cf6f5830068fba69f61e31fe2d (patch) | |
tree | 69719650194f38e7166f185a31a1dfad21609fc4 | |
parent | ab787c976567f46c7fcb5fd18806903a270350b9 (diff) |
Retargetting
More refined symmetry grouping (can take care of tails properly) and better matching between symmetry groups (based on relative length of arcs)
-rw-r--r-- | source/blender/blenlib/BLI_graph.h | 2 | ||||
-rw-r--r-- | source/blender/blenlib/intern/graph.c | 342 | ||||
-rw-r--r-- | source/blender/include/reeb.h | 1 | ||||
-rw-r--r-- | source/blender/src/autoarmature.c | 16 | ||||
-rw-r--r-- | source/blender/src/reeb.c | 40 |
5 files changed, 295 insertions, 106 deletions
diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h index 1d29cc88651..0763c7edff0 100644 --- a/source/blender/blenlib/BLI_graph.h +++ b/source/blender/blenlib/BLI_graph.h @@ -52,6 +52,7 @@ typedef struct BArc { float length; int symmetry_level; + int symmetry_group; int symmetry_flag; } BArc; @@ -98,5 +99,6 @@ void BLI_mirrorAlongAxis(float v[3], float center[3], float axis[3]); * axial symetry sides */ #define SYM_SIDE_POSITIVE 1 #define SYM_SIDE_NEGATIVE 2 +/* Anything higher is the order in radial symmetry */ #endif /*BLI_GRAPH_H_*/ diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c index 3a484e15642..6e9dcc66ffc 100644 --- a/source/blender/blenlib/intern/graph.c +++ b/source/blender/blenlib/intern/graph.c @@ -23,6 +23,9 @@ * graph.c: Common graph interface and methods */ +#include <float.h> +#include <math.h> + #include "MEM_guardedalloc.h" #include "BLI_graph.h" @@ -31,6 +34,12 @@ #include "BKE_utildefines.h" +static void testRadialSymmetry(BGraph *graph, BNode* root_node, RadialArc* ring, int total, float axis[3], float limit, int group); + +static void handleAxialSymmetry(BGraph *graph, BNode *root_node, int depth, float axis[3], float limit); +static void testAxialSymmetry(BGraph *graph, BNode* root_node, BNode* node1, BNode* node2, BArc* arc1, BArc* arc2, float axis[3], float limit, int group); +static void flagAxialSymmetry(BNode *root_node, BNode *end_node, BArc *arc, int group); + void BLI_freeNode(BGraph *graph, BNode *node) { if (node->arcs) @@ -280,64 +289,19 @@ void BLI_mirrorAlongAxis(float v[3], float center[3], float axis[3]) VecAddf(v, v, pv); } -static void markRadialSymmetry(BGraph *graph, BNode *node, int depth, float axis[3], float limit) +static void testRadialSymmetry(BGraph *graph, BNode* root_node, RadialArc* ring, int total, float axis[3], float limit, int group) { - RadialArc *ring = NULL; - RadialArc *unit; int symmetric = 1; - int count = 0; int i; - - /* mark topological symmetry */ - node->symmetry_flag |= SYM_TOPOLOGICAL; - - /* count the number of arcs in the symmetry ring */ - for (i = 0; i < node->degree; i++) - { - BArc *connectedArc = node->arcs[i]; - - /* depth is store as a negative in flag. symmetry level is positive */ - if (connectedArc->symmetry_level == -depth) - { - count++; - } - } - - ring = MEM_callocN(sizeof(RadialArc) * count, "radial symmetry ring"); - unit = ring; - - /* fill in the ring */ - for (unit = ring, i = 0; i < node->degree; i++) - { - BArc *connectedArc = node->arcs[i]; - - /* depth is store as a negative in flag. symmetry level is positive */ - if (connectedArc->symmetry_level == -depth) - { - BNode *otherNode = BLI_otherNode(connectedArc, node); - float vec[3]; - - unit->arc = connectedArc; - - /* project the node to node vector on the symmetry plane */ - VecSubf(unit->n, otherNode->p, node->p); - Projf(vec, unit->n, axis); - VecSubf(unit->n, unit->n, vec); - - Normalize(unit->n); - - unit++; - } - } - - /* sort ring */ - for (i = 0; i < count - 1; i++) + + /* sort ring by angle */ + for (i = 0; i < total - 1; i++) { - float minAngle = 3; /* arbitrary high value, higher than 2, at least */ + float minAngle = FLT_MAX; int minIndex = -1; int j; - for (j = i + 1; j < count; j++) + for (j = i + 1; j < total; j++) { float angle = Inpf(ring[i].n, ring[j].n); @@ -364,22 +328,22 @@ static void markRadialSymmetry(BGraph *graph, BNode *node, int depth, float axis } } - for (i = 0; i < count && symmetric; i++) + for (i = 0; i < total && symmetric; i++) { BNode *node1, *node2; float tangent[3]; float normal[3]; float p[3]; - int j = (i + 1) % count; /* next arc in the circular list */ + int j = (i + 1) % total; /* next arc in the circular list */ VecAddf(tangent, ring[i].n, ring[j].n); Crossf(normal, tangent, axis); - node1 = BLI_otherNode(ring[i].arc, node); - node2 = BLI_otherNode(ring[j].arc, node); + node1 = BLI_otherNode(ring[i].arc, root_node); + node2 = BLI_otherNode(ring[j].arc, root_node); VECCOPY(p, node2->p); - BLI_mirrorAlongAxis(p, node->p, normal); + BLI_mirrorAlongAxis(p, root_node->p, normal); /* check if it's within limit before continuing */ if (VecLenf(node1->p, p) > limit) @@ -392,23 +356,192 @@ static void markRadialSymmetry(BGraph *graph, BNode *node, int depth, float axis if (symmetric) { /* mark node as symmetric physically */ - VECCOPY(node->symmetry_axis, axis); - node->symmetry_flag |= SYM_PHYSICAL; - node->symmetry_flag |= SYM_RADIAL; + VECCOPY(root_node->symmetry_axis, axis); + root_node->symmetry_flag |= SYM_PHYSICAL; + root_node->symmetry_flag |= SYM_RADIAL; + /* FLAG SYMMETRY GROUP */ + for (i = 0; i < total; i++) + { + ring[i].arc->symmetry_group = group; + ring[i].arc->symmetry_flag = i; + } + if (graph->radial_symmetry) { - graph->radial_symmetry(node, ring, count); + graph->radial_symmetry(root_node, ring, total); + } + } +} + +static void handleRadialSymmetry(BGraph *graph, BNode *root_node, int depth, float axis[3], float limit) +{ + RadialArc *ring = NULL; + RadialArc *unit; + int total = 0; + int group; + int first; + int i; + + /* mark topological symmetry */ + root_node->symmetry_flag |= SYM_TOPOLOGICAL; + + /* total the number of arcs in the symmetry ring */ + for (i = 0; i < root_node->degree; i++) + { + BArc *connectedArc = root_node->arcs[i]; + + /* depth is store as a negative in flag. symmetry level is positive */ + if (connectedArc->symmetry_level == -depth) + { + total++; + } + } + + ring = MEM_callocN(sizeof(RadialArc) * total, "radial symmetry ring"); + unit = ring; + + /* fill in the ring */ + for (unit = ring, i = 0; i < root_node->degree; i++) + { + BArc *connectedArc = root_node->arcs[i]; + + /* depth is store as a negative in flag. symmetry level is positive */ + if (connectedArc->symmetry_level == -depth) + { + BNode *otherNode = BLI_otherNode(connectedArc, root_node); + float vec[3]; + + unit->arc = connectedArc; + + /* project the node to node vector on the symmetry plane */ + VecSubf(unit->n, otherNode->p, root_node->p); + Projf(vec, unit->n, axis); + VecSubf(unit->n, unit->n, vec); + + Normalize(unit->n); + + unit++; } } + /* sort ring by arc length + * using a rather bogus insertion sort + * butrings will never get too big to matter + * */ + for (i = 0; i < total; i++) + { + int j; + + for (j = i - 1; j >= 0; j--) + { + BArc *arc1, *arc2; + + arc1 = ring[j].arc; + arc2 = ring[j + 1].arc; + + if (arc1->length > arc2->length) + { + /* swap with smaller */ + RadialArc tmp; + tmp = ring[j + 1]; + ring[j + 1] = ring[j]; + ring[j] = tmp; + } + else + { + break; + } + } + } + + /* Dispatch to specific symmetry tests */ + first = 0; + group = 0; + + for (i = 1; i < total; i++) + { + int dispatch = 0; + int last = i - 1; + + if (fabs(ring[first].arc->length - ring[i].arc->length) > limit) + { + dispatch = 1; + } + + /* if not dispatching already and on last arc + * Dispatch using current arc as last + * */ + if (dispatch == 0 && i == total - 1) + { + last = i; + dispatch = 1; + } + + if (dispatch) + { + int sub_total = last - first + 1; + + group += 1; + + if (sub_total == 1) + { + printf("no dispatch\n"); + /* NOTHING TO DO */ + } + else if (sub_total == 2) + { + BArc *arc1, *arc2; + BNode *node1, *node2; + + printf("dispatch axial\n"); + + arc1 = ring[first].arc; + arc2 = ring[last].arc; + + node1 = BLI_otherNode(arc1, root_node); + node2 = BLI_otherNode(arc2, root_node); + + testAxialSymmetry(graph, root_node, node1, node2, arc1, arc2, axis, limit, group); + } + else if (sub_total != total) /* allocate a new sub ring if needed */ + { + 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++) + { + sub_ring[sub_i] = ring[first + sub_i]; + } + + testRadialSymmetry(graph, root_node, sub_ring, sub_total, axis, limit, group); + + MEM_freeN(sub_ring); + } + else if (sub_total == total) + { + printf("dispatch radial full ring\n"); + + testRadialSymmetry(graph, root_node, ring, total, axis, limit, group); + } + + first = i; + } + } + + MEM_freeN(ring); } -static void setSideAxialSymmetry(BNode *root_node, BNode *end_node, BArc *arc) +static void flagAxialSymmetry(BNode *root_node, BNode *end_node, BArc *arc, int group) { float vec[3]; + arc->symmetry_group = group; + VecSubf(vec, end_node->p, root_node->p); if (Inpf(vec, root_node->symmetry_axis) < 0) @@ -421,20 +554,54 @@ static void setSideAxialSymmetry(BNode *root_node, BNode *end_node, BArc *arc) } } -static void markAxialSymmetry(BGraph *graph, BNode *node, int depth, float axis[3], float limit) +static void testAxialSymmetry(BGraph *graph, BNode* root_node, BNode* node1, BNode* node2, BArc* arc1, BArc* arc2, float axis[3], float limit, int group) { - BArc *arc1 = NULL; - BArc *arc2 = NULL; - BNode *node1 = NULL, *node2 = NULL; float nor[3], vec[3], p[3]; + + VecSubf(vec, node1->p, root_node->p); + Normalize(vec); + VecSubf(p, root_node->p, node2->p); + Normalize(p); + VecAddf(p, p, vec); + + Crossf(vec, p, axis); + Crossf(nor, vec, axis); + + /* mirror node2 along axis */ + VECCOPY(p, node2->p); + BLI_mirrorAlongAxis(p, root_node->p, nor); + + /* check if it's within limit before continuing */ + if (VecLenf(node1->p, p) <= limit) + { + /* mark node as symmetric physically */ + VECCOPY(root_node->symmetry_axis, nor); + root_node->symmetry_flag |= SYM_PHYSICAL; + root_node->symmetry_flag |= SYM_AXIAL; + + /* flag side on arcs */ + flagAxialSymmetry(root_node, node1, arc1, group); + flagAxialSymmetry(root_node, node2, arc2, group); + + if (graph->axial_symmetry) + { + graph->axial_symmetry(root_node, node1, node2, arc1, arc2); + } + } +} + +static void handleAxialSymmetry(BGraph *graph, BNode *root_node, int depth, float axis[3], float limit) +{ + BArc *arc1 = NULL, *arc2 = NULL; + BNode *node1 = NULL, *node2 = NULL; int i; /* mark topological symmetry */ - node->symmetry_flag |= SYM_TOPOLOGICAL; + root_node->symmetry_flag |= SYM_TOPOLOGICAL; - for (i = 0; i < node->degree; i++) + for (i = 0; i < root_node->degree; i++) { - BArc *connectedArc = node->arcs[i]; + BArc *connectedArc = root_node->arcs[i]; /* depth is store as a negative in flag. symmetry level is positive */ if (connectedArc->symmetry_level == -depth) @@ -442,12 +609,12 @@ static void markAxialSymmetry(BGraph *graph, BNode *node, int depth, float axis[ if (arc1 == NULL) { arc1 = connectedArc; - node1 = BLI_otherNode(arc1, node); + node1 = BLI_otherNode(arc1, root_node); } else { arc2 = connectedArc; - node2 = BLI_otherNode(arc2, node); + node2 = BLI_otherNode(arc2, root_node); break; /* Can stop now, the two arcs have been found */ } } @@ -459,36 +626,9 @@ static void markAxialSymmetry(BGraph *graph, BNode *node, int depth, float axis[ return; } - VecSubf(vec, node1->p, node->p); - Normalize(vec); - VecSubf(p, node->p, node2->p); - Normalize(p); - VecAddf(p, p, vec); - - Crossf(vec, p, axis); - Crossf(nor, vec, axis); - - /* mirror node2 along axis */ - VECCOPY(p, node2->p); - BLI_mirrorAlongAxis(p, node->p, nor); + printf("symmetry length %f <> %f\n", arc1->length, arc2->length); - /* check if it's within limit before continuing */ - if (VecLenf(node1->p, p) <= limit) - { - /* mark node as symmetric physically */ - VECCOPY(node->symmetry_axis, nor); - node->symmetry_flag |= SYM_PHYSICAL; - node->symmetry_flag |= SYM_AXIAL; - - /* set side on arcs */ - setSideAxialSymmetry(node, node1, arc1); - setSideAxialSymmetry(node, node2, arc2); - - if (graph->axial_symmetry) - { - graph->axial_symmetry(node, node1, node2, arc1, arc2); - } - } + testAxialSymmetry(graph, root_node, node1, node2, arc1, arc2, axis, limit, 1); } static void markdownSecondarySymmetry(BGraph *graph, BNode *node, int depth, int level, float limit) @@ -522,11 +662,11 @@ static void markdownSecondarySymmetry(BGraph *graph, BNode *node, int depth, int /* Split between axial and radial symmetry */ if (count == 2) { - markAxialSymmetry(graph, node, depth, axis, limit); + handleAxialSymmetry(graph, node, depth, axis, limit); } else { - markRadialSymmetry(graph, node, depth, axis, limit); + handleRadialSymmetry(graph, node, depth, axis, limit); } /* markdown secondary symetries */ diff --git a/source/blender/include/reeb.h b/source/blender/include/reeb.h index b24ba25aa5d..2395e294b85 100644 --- a/source/blender/include/reeb.h +++ b/source/blender/include/reeb.h @@ -91,6 +91,7 @@ typedef struct ReebArc { float length; int symmetry_level; + int symmetry_group; int symmetry_flag; /*********************************/ diff --git a/source/blender/src/autoarmature.c b/source/blender/src/autoarmature.c index 741398951bf..a852a3fb82d 100644 --- a/source/blender/src/autoarmature.c +++ b/source/blender/src/autoarmature.c @@ -108,6 +108,7 @@ typedef struct RigArc { float length; int symmetry_level; + int symmetry_group; int symmetry_flag; /*********************************/ @@ -383,7 +384,7 @@ static void RIG_findHead(RigGraph *rg) /*******************************************************************************************************/ -static void RIG_printNode(RigNode *node, char name[]) +void RIG_printNode(RigNode *node, char name[]) { printf("%s %p %i <%0.3f, %0.3f, %0.3f>\n", name, node, node->degree, node->p[0], node->p[1], node->p[2]); @@ -398,7 +399,7 @@ static void RIG_printNode(RigNode *node, char name[]) } } -static void RIG_printArcBones(RigArc *arc) +void RIG_printArcBones(RigArc *arc) { RigEdge *edge; @@ -412,7 +413,7 @@ static void RIG_printArcBones(RigArc *arc) printf("\n"); } -static void RIG_printArc(RigArc *arc) +void RIG_printArc(RigArc *arc) { RigEdge *edge; @@ -938,7 +939,6 @@ static void retargetArctoArc(RigArc *iarc) if (mode == RETARGET_AGGRESSIVE) { - printf("aggresive\n"); retargetArctoArcAggresive(iarc); } else @@ -953,6 +953,7 @@ static void findCorrespondingArc(RigArc *start_arc, RigNode *start_node, RigArc ReebNode *enode = start_node->link; ReebArc *next_earc; int symmetry_level = next_iarc->symmetry_level; + int symmetry_group = next_iarc->symmetry_group; int symmetry_flag = next_iarc->symmetry_flag; int i; @@ -963,18 +964,22 @@ static void findCorrespondingArc(RigArc *start_arc, RigNode *start_node, RigArc next_earc = (ReebArc*)enode->arcs[i]; if (next_earc->flag == 0 && /* not already taken */ next_earc->symmetry_flag == symmetry_flag && + next_earc->symmetry_group == symmetry_group && next_earc->symmetry_level == symmetry_level) { +/* printf("-----------------------\n"); printf("CORRESPONDING ARC FOUND\n"); 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); +*/ next_earc->flag = 1; // mark as taken next_iarc->link = next_earc; break; } } +/* if (next_iarc->link == NULL) { printf("--------------------------\n"); @@ -991,6 +996,7 @@ static void findCorrespondingArc(RigArc *start_arc, RigNode *start_node, RigArc printf("flag %i -- symmetry level %i -- symmetry flag %i\n", next_earc->flag, next_earc->symmetry_level, next_earc->symmetry_flag); } } +*/ } static void retargetSubgraph(RigGraph *rigg, RigArc *start_arc, RigNode *start_node) diff --git a/source/blender/src/reeb.c b/source/blender/src/reeb.c index c437379dbdb..bd105e114ef 100644 --- a/source/blender/src/reeb.c +++ b/source/blender/src/reeb.c @@ -214,6 +214,44 @@ void resizeArcBuckets(ReebArc *arc) MEM_freeN(oldBuckets); } } + +void calculateArcLength(ReebArc *arc) +{ + ReebArcIterator iter; + EmbedBucket *bucket = NULL; + float *vec0, *vec1; + + arc->length = 0; + + initArcIterator(&iter, arc, arc->head); + + bucket = nextBucket(&iter); + + vec0 = arc->head->p; + + while (bucket != NULL) + { + vec1 = bucket->p; + + arc->length += VecLenf(vec0, vec1); + + vec0 = vec1; + bucket = nextBucket(&iter); + } + + arc->length += VecLenf(arc->tail->p, vec1); +} + +void calculateGraphLength(ReebGraph *rg) +{ + ReebArc *arc; + + for (arc = rg->arcs.first; arc; arc = arc->next) + { + calculateArcLength(arc); + } +} + /***************************************** UTILS **********************************************/ ReebEdge * copyEdge(ReebEdge *edge) @@ -2539,5 +2577,7 @@ ReebGraph *BIF_ReebGraphFromEditMesh(void) REEB_exportGraph(rg, -1); + calculateGraphLength(rg); + return rg; } |