diff options
author | Martin Poirier <theeth@yahoo.com> | 2008-06-26 22:15:45 +0400 |
---|---|---|
committer | Martin Poirier <theeth@yahoo.com> | 2008-06-26 22:15:45 +0400 |
commit | 829b2668c50dec713fdb31ee2e3fc8f7658a68d3 (patch) | |
tree | 4f74e6ee99aa22e669f2c4e0c935fe76b66b1d1b /source | |
parent | c0daf627333b21c72ec6d120805a74a8b274b429 (diff) |
Starting to debug the elusive graph spliting bug
Better check for RigGraph head
Fix harmonic weighting for quads
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenlib/BLI_graph.h | 3 | ||||
-rw-r--r-- | source/blender/blenlib/intern/graph.c | 71 | ||||
-rw-r--r-- | source/blender/src/autoarmature.c | 22 | ||||
-rw-r--r-- | source/blender/src/buttons_editing.c | 2 | ||||
-rw-r--r-- | source/blender/src/reeb.c | 184 |
5 files changed, 210 insertions, 72 deletions
diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h index 0763c7edff0..b1e4a9fec75 100644 --- a/source/blender/blenlib/BLI_graph.h +++ b/source/blender/blenlib/BLI_graph.h @@ -72,6 +72,9 @@ void BLI_flagArcs(BGraph *graph, int flag); int BLI_hasAdjacencyList(BGraph *rg); void BLI_buildAdjacencyList(BGraph *rg); +void BLI_freeAdjacencyList(BGraph *rg); + +int BLI_FlagSubgraphs(BGraph *graph); void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced); void BLI_removeDoubleNodes(BGraph *graph, float limit); diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c index 5c398339ec8..44b74122371 100644 --- a/source/blender/blenlib/intern/graph.c +++ b/source/blender/blenlib/intern/graph.c @@ -80,8 +80,8 @@ void BLI_flagArcs(BGraph *graph, int flag) static void addArcToNodeAdjacencyList(BNode *node, BArc *arc) { - node->arcs[node->degree] = arc; - node->degree++; + node->arcs[node->flag] = arc; + node->flag++; } void BLI_buildAdjacencyList(BGraph *rg) @@ -99,7 +99,7 @@ void BLI_buildAdjacencyList(BGraph *rg) node->arcs = MEM_callocN((node->degree) * sizeof(BArc*), "adjacency list"); /* temporary use to indicate the first index available in the lists */ - node->degree = 0; + node->flag = 0; } for(arc = rg->arcs.first; arc; arc= arc->next) @@ -107,6 +107,28 @@ void BLI_buildAdjacencyList(BGraph *rg) addArcToNodeAdjacencyList(arc->head, arc); addArcToNodeAdjacencyList(arc->tail, arc); } + + for(node = rg->nodes.first; node; node = node->next) + { + if (node->degree != node->flag) + { + printf("error in node [%p]. Added only %i arcs out of %i\n", node, node->flag, node->degree); + } + } +} + +void BLI_freeAdjacencyList(BGraph *rg) +{ + BNode *node; + + for(node = rg->nodes.first; node; node = node->next) + { + if (node->arcs != NULL) + { + MEM_freeN(node->arcs); + node->arcs = NULL; + } + } } int BLI_hasAdjacencyList(BGraph *rg) @@ -173,6 +195,48 @@ void BLI_removeDoubleNodes(BGraph *graph, float limit) } } +/************************************* SUBGRAPH DETECTION **********************************************/ + +void flagSubgraph(BNode *node, int subgraph) +{ + if (node->flag == 0) + { + BArc *arc; + int i; + + node->flag = subgraph; + + for(i = 0; i < node->degree; i++) + { + arc = node->arcs[i]; + flagSubgraph(BLI_otherNode(arc, node), subgraph); + } + } +} + +int BLI_FlagSubgraphs(BGraph *graph) +{ + BNode *node; + int subgraph = 0; + + if (BLI_hasAdjacencyList(graph) == 0) + { + BLI_buildAdjacencyList(graph); + } + + BLI_flagNodes(graph, 0); + + for (node = graph->nodes.first; node; node = node->next) + { + if (node->flag == 0) + { + subgraph++; + flagSubgraph(node, subgraph); + } + } + + return subgraph; +} /*************************************** CYCLE DETECTION ***********************************************/ @@ -790,6 +854,7 @@ void BLI_markdownSymmetry(BGraph *graph, BNode *root_node, float limit) if (BLI_isGraphCyclic(graph)) { + printf("cyclic\n"); return; } diff --git a/source/blender/src/autoarmature.c b/source/blender/src/autoarmature.c index a058c67c71a..2a139137a8e 100644 --- a/source/blender/src/autoarmature.c +++ b/source/blender/src/autoarmature.c @@ -364,7 +364,7 @@ static void RIG_arcFromBoneChain(RigGraph *rg, ListBase *list, EditBone *root_bo if (contain_head) { - rg->head = (RigNode*)arc->tail; + rg->head = arc->tail; } } @@ -379,6 +379,26 @@ static void RIG_findHead(RigGraph *rg) rg->head = (RigNode*)arc->head; } + else + { + RigArc *arc; + + for (arc = rg->arcs.first; arc; arc = arc->next) + { + RigEdge *edge = arc->edges.last; + + if (edge->bone->flag & BONESEL_ANY) + { + rg->head = arc->tail; + break; + } + } + } + + if (rg->head == NULL) + { + rg->head = rg->nodes.first; + } } } diff --git a/source/blender/src/buttons_editing.c b/source/blender/src/buttons_editing.c index 58cc454424b..171856615ef 100644 --- a/source/blender/src/buttons_editing.c +++ b/source/blender/src/buttons_editing.c @@ -5000,11 +5000,13 @@ static void skgen_reorder(void *option, void *arg2) static void skgen_graphgen(void *arg1, void *arg2) { BIF_GlobalReebGraphFromEditMesh(); + allqueue(REDRAWVIEW3D, 0); } static void skgen_graphfree(void *arg1, void *arg2) { BIF_GlobalReebFree(); + allqueue(REDRAWVIEW3D, 0); } static void editing_panel_mesh_skgen_retarget(Object *ob, Mesh *me) diff --git a/source/blender/src/reeb.c b/source/blender/src/reeb.c index f889537975b..1c317f06176 100644 --- a/source/blender/src/reeb.c +++ b/source/blender/src/reeb.c @@ -779,14 +779,17 @@ void filterArc(ReebGraph *rg, ReebNode *newNode, ReebNode *removedNode, ReebArc { ReebArc *arc = NULL, *nextArc = NULL; - /* first pass, merge buckets for arcs that spawned the two nodes into the source arc*/ - for(arc = rg->arcs.first; arc; arc = arc->next) + if (merging) { - if (arc->head == srcArc->head && arc->tail == srcArc->tail && arc != srcArc) + /* first pass, merge buckets for arcs that spawned the two nodes into the source arc*/ + for(arc = rg->arcs.first; arc; arc = arc->next) { - ReebNode *head = (ReebNode*)srcArc->head; - ReebNode *tail = (ReebNode*)srcArc->tail; - mergeArcBuckets(srcArc, arc, head->weight, tail->weight); + if (arc->head == srcArc->head && arc->tail == srcArc->tail && arc != srcArc) + { + ReebNode *head = (ReebNode*)srcArc->head; + ReebNode *tail = (ReebNode*)srcArc->tail; + mergeArcBuckets(srcArc, arc, head->weight, tail->weight); + } } } @@ -814,13 +817,14 @@ void filterArc(ReebGraph *rg, ReebNode *newNode, ReebNode *removedNode, ReebArc NodeDegreeDecrement(rg, newNode); //newNode->degree--; - // If it's safeArc, it'll be removed later, so keep it for now + // If it's srcArc, it'll be removed later, so keep it for now if (arc != srcArc) { BLI_remlink(&rg->arcs, arc); REEB_freeArc((BArc*)arc); } } +#if 0 // Remove flipped arcs else if (((ReebNode*)arc->head)->weight > ((ReebNode*)arc->tail)->weight) { @@ -831,6 +835,7 @@ void filterArc(ReebGraph *rg, ReebNode *newNode, ReebNode *removedNode, ReebArc BLI_remlink(&rg->arcs, arc); REEB_freeArc((BArc*)arc); } +#endif else { //newNode->degree++; // incrementing degree since we're adding an arc @@ -1929,6 +1934,35 @@ static float cotan_weight(float *v1, float *v2, float *v3) return Inpf(a, b)/clen; } +void addTriangle(EditVert *v1, EditVert *v2, EditVert *v3, long e1, long e2, long e3) +{ + /* Angle opposite e1 */ + float t1= cotan_weight(v1->co, v2->co, v3->co) / e2; + + /* Angle opposite e2 */ + float t2 = cotan_weight(v2->co, v3->co, v1->co) / e3; + + /* Angle opposite e3 */ + float t3 = cotan_weight(v3->co, v1->co, v2->co) / e1; + + int i1 = v1->hash; + int i2 = v2->hash; + int i3 = v3->hash; + + nlMatrixAdd(i1, i1, t2+t3); + nlMatrixAdd(i2, i2, t1+t3); + nlMatrixAdd(i3, i3, t1+t2); + + nlMatrixAdd(i1, i2, -t3); + nlMatrixAdd(i2, i1, -t3); + + nlMatrixAdd(i2, i3, -t1); + nlMatrixAdd(i3, i2, -t1); + + nlMatrixAdd(i3, i1, -t2); + nlMatrixAdd(i1, i3, -t2); +} + int weightToHarmonic(EditMesh *em) { NLboolean success; @@ -1956,49 +1990,55 @@ int weightToHarmonic(EditMesh *em) /* Find local extrema */ for(index = 0, eve = em->verts.first; eve; index++, eve = eve->next) { - EditEdge *eed; - int maximum = 1; - int minimum = 1; - - eve->hash = index; /* Assign index to vertex */ - - NextEdgeForVert(NULL, NULL); /* Reset next edge */ - for(eed = NextEdgeForVert(em, eve); eed && (maximum || minimum); eed = NextEdgeForVert(em, eve)) + if (eve->h == 0) { - EditVert *eve2; + EditEdge *eed; + int maximum = 1; + int minimum = 1; - if (eed->v1 == eve) - { - eve2 = eed->v2; - } - else + eve->hash = index; /* Assign index to vertex */ + + NextEdgeForVert(NULL, NULL); /* Reset next edge */ + for(eed = NextEdgeForVert(em, eve); eed && (maximum || minimum); eed = NextEdgeForVert(em, eve)) { - eve2 = eed->v1; + EditVert *eve2; + + if (eed->v1 == eve) + { + eve2 = eed->v2; + } + else + { + eve2 = eed->v1; + } + + if (eve2->h == 0) + { + /* Adjacent vertex is bigger, not a local maximum */ + if (eve2->tmp.fp > eve->tmp.fp) + { + maximum = 0; + } + /* Adjacent vertex is smaller, not a local minimum */ + else if (eve2->tmp.fp < eve->tmp.fp) + { + minimum = 0; + } + } } - /* Adjacent vertex is bigger, not a local maximum */ - if (eve2->tmp.fp > eve->tmp.fp) + if (maximum || minimum) { - maximum = 0; + float w = eve->tmp.fp; + eve->f1 = 0; + nlSetVariable(0, index, w); + nlLockVariable(index); } - /* Adjacent vertex is smaller, not a local minimum */ - else if (eve2->tmp.fp < eve->tmp.fp) + else { - minimum = 0; + eve->f1 = 1; } } - - if (maximum || minimum) - { - float w = eve->tmp.fp; - eve->f1 = 0; - nlSetVariable(0, index, w); - nlLockVariable(index); - } - else - { - eve->f1 = 1; - } } nlBegin(NL_MATRIX); @@ -2012,39 +2052,34 @@ int weightToHarmonic(EditMesh *em) /* Add faces count to the edge weight */ for(efa = em->faces.first; efa; efa = efa->next) { - efa->e1->tmp.l++; - efa->e2->tmp.l++; - efa->e3->tmp.l++; + if (efa->h == 0) + { + efa->e1->tmp.l++; + efa->e2->tmp.l++; + efa->e3->tmp.l++; + + if (efa->e4) + { + efa->e4->tmp.l++; + } + } } /* Add faces angle to the edge weight */ for(efa = em->faces.first; efa; efa = efa->next) { - /* Angle opposite e1 */ - float t1= cotan_weight(efa->v1->co, efa->v2->co, efa->v3->co) / efa->e2->tmp.l; - - /* Angle opposite e2 */ - float t2 = cotan_weight(efa->v2->co, efa->v3->co, efa->v1->co) / efa->e3->tmp.l; - - /* Angle opposite e3 */ - float t3 = cotan_weight(efa->v3->co, efa->v1->co, efa->v2->co) / efa->e1->tmp.l; - - int i1 = efa->v1->hash; - int i2 = efa->v2->hash; - int i3 = efa->v3->hash; - - nlMatrixAdd(i1, i1, t2+t3); - nlMatrixAdd(i2, i2, t1+t3); - nlMatrixAdd(i3, i3, t1+t2); - - nlMatrixAdd(i1, i2, -t3); - nlMatrixAdd(i2, i1, -t3); - - nlMatrixAdd(i2, i3, -t1); - nlMatrixAdd(i3, i2, -t1); - - nlMatrixAdd(i3, i1, -t2); - nlMatrixAdd(i1, i3, -t2); + if (efa->h == 0) + { + if (efa->v4 == NULL) + { + addTriangle(efa->v1, efa->v2, efa->v3, efa->e1->tmp.l, efa->e2->tmp.l, efa->e3->tmp.l); + } + else + { + addTriangle(efa->v1, efa->v2, efa->v3, efa->e1->tmp.l, efa->e2->tmp.l, 2); + addTriangle(efa->v3, efa->v4, efa->v1, efa->e3->tmp.l, efa->e4->tmp.l, 2); + } + } } nlEnd(NL_MATRIX); @@ -2714,9 +2749,19 @@ void BIF_GlobalReebGraphFromEditMesh(void) verifyFaces(GLOBAL_RG); + printf("GENERATED\n"); + printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)GLOBAL_RG)); + /* Remove arcs without embedding */ filterNullReebGraph(GLOBAL_RG); + verifyNodeDegree(GLOBAL_RG); + + BLI_freeAdjacencyList((BGraph*)GLOBAL_RG); + + printf("NULL FILTERED\n"); + printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)GLOBAL_RG)); + verifyBuckets(GLOBAL_RG); i = 1; @@ -2775,6 +2820,9 @@ void BIF_GlobalReebGraphFromEditMesh(void) calculateGraphLength(GLOBAL_RG); BLI_markdownSymmetry((BGraph*)GLOBAL_RG, GLOBAL_RG->nodes.first, G.scene->toolsettings->skgen_symmetry_limit); + + printf("DONE\n"); + printf("%i subgraphs\n", BLI_FlagSubgraphs((BGraph*)GLOBAL_RG)); } void REEB_draw() |