[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [16183] branches/harmonic-skeleton/source/ blender: Make subgraph tagging use own index, to not interfere with flagging used to prevent backtracking in different other functions
Martin Poirier
theeth at yahoo.com
Tue Aug 19 00:22:56 CEST 2008
Revision: 16183
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=16183
Author: theeth
Date: 2008-08-19 00:22:56 +0200 (Tue, 19 Aug 2008)
Log Message:
-----------
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
Modified Paths:
--------------
branches/harmonic-skeleton/source/blender/blenlib/BLI_graph.h
branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c
branches/harmonic-skeleton/source/blender/include/reeb.h
branches/harmonic-skeleton/source/blender/src/autoarmature.c
branches/harmonic-skeleton/source/blender/src/reeb.c
Modified: branches/harmonic-skeleton/source/blender/blenlib/BLI_graph.h
===================================================================
--- branches/harmonic-skeleton/source/blender/blenlib/BLI_graph.h 2008-08-18 19:32:21 UTC (rev 16182)
+++ branches/harmonic-skeleton/source/blender/blenlib/BLI_graph.h 2008-08-18 22:22:56 UTC (rev 16183)
@@ -40,6 +40,8 @@
int degree;
struct BArc **arcs;
+
+ int subgraph_index;
int symmetry_level;
int symmetry_flag;
@@ -70,6 +72,8 @@
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 @@
#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);
Modified: branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c
===================================================================
--- branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c 2008-08-18 19:32:21 UTC (rev 16182)
+++ branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c 2008-08-18 22:22:56 UTC (rev 16183)
@@ -64,6 +64,16 @@
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 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 @@
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 @@
/*********************************** 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 @@
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(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 @@
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 @@
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);
}
}
Modified: branches/harmonic-skeleton/source/blender/include/reeb.h
===================================================================
--- branches/harmonic-skeleton/source/blender/include/reeb.h 2008-08-18 19:32:21 UTC (rev 16182)
+++ branches/harmonic-skeleton/source/blender/include/reeb.h 2008-08-18 22:22:56 UTC (rev 16183)
@@ -70,6 +70,8 @@
int degree;
struct ReebArc **arcs;
+ int subgraph_index;
+
int symmetry_level;
int symmetry_flag;
float symmetry_axis[3];
Modified: branches/harmonic-skeleton/source/blender/src/autoarmature.c
===================================================================
--- branches/harmonic-skeleton/source/blender/src/autoarmature.c 2008-08-18 19:32:21 UTC (rev 16182)
+++ branches/harmonic-skeleton/source/blender/src/autoarmature.c 2008-08-18 22:22:56 UTC (rev 16183)
@@ -78,7 +78,7 @@
struct RigEdge;
#define NB_THREADS 4
-#define USE_THREADS
+//#define USE_THREADS
typedef struct RigGraph {
ListBase arcs;
@@ -111,6 +111,8 @@
int degree;
struct BArc **arcs;
+ int subgraph_index;
+
int symmetry_level;
int symmetry_flag;
float symmetry_axis[3];
@@ -242,6 +244,8 @@
}
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 @@
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,7 +362,18 @@
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);
+}
+
/*******************************************************************************************************/
static void RIG_calculateEdgeAngle(RigEdge *edge_first, RigEdge *edge_second)
@@ -484,6 +492,73 @@
/*******************************************************************************************************/
+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 @@
}
}
- 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 @@
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 @@
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 @@
BLI_removeDoubleNodes((BGraph*)rg, 0.001);
+ RIG_removeNormalNodes(rg);
+
BLI_buildAdjacencyList((BGraph*)rg);
RIG_findHead(rg);
@@ -703,6 +781,11 @@
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 @@
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 @@
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)
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list