Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--source/blender/blenlib/BLI_graph.h6
-rw-r--r--source/blender/blenlib/intern/graph.c45
-rw-r--r--source/blender/include/reeb.h2
-rw-r--r--source/blender/src/autoarmature.c154
-rw-r--r--source/blender/src/reeb.c45
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)
{
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-17 04:12:23 +0300