[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15363] branches/harmonic-skeleton/source/ blender: Starting to debug the elusive graph spliting bug
Martin Poirier
theeth at yahoo.com
Thu Jun 26 20:16:59 CEST 2008
Revision: 15363
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15363
Author: theeth
Date: 2008-06-26 20:15:45 +0200 (Thu, 26 Jun 2008)
Log Message:
-----------
Starting to debug the elusive graph spliting bug
Better check for RigGraph head
Fix harmonic weighting for quads
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/src/autoarmature.c
branches/harmonic-skeleton/source/blender/src/buttons_editing.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-06-26 17:08:07 UTC (rev 15362)
+++ branches/harmonic-skeleton/source/blender/blenlib/BLI_graph.h 2008-06-26 18:15:45 UTC (rev 15363)
@@ -72,7 +72,10 @@
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);
Modified: branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c
===================================================================
--- branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c 2008-06-26 17:08:07 UTC (rev 15362)
+++ branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c 2008-06-26 18:15:45 UTC (rev 15363)
@@ -80,8 +80,8 @@
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 @@
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,8 +107,30 @@
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)
{
BNode *node;
@@ -173,7 +195,49 @@
}
}
+/************************************* 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 ***********************************************/
int detectCycle(BNode *node, BArc *src_arc)
@@ -790,6 +854,7 @@
if (BLI_isGraphCyclic(graph))
{
+ printf("cyclic\n");
return;
}
Modified: branches/harmonic-skeleton/source/blender/src/autoarmature.c
===================================================================
--- branches/harmonic-skeleton/source/blender/src/autoarmature.c 2008-06-26 17:08:07 UTC (rev 15362)
+++ branches/harmonic-skeleton/source/blender/src/autoarmature.c 2008-06-26 18:15:45 UTC (rev 15363)
@@ -364,7 +364,7 @@
if (contain_head)
{
- rg->head = (RigNode*)arc->tail;
+ rg->head = arc->tail;
}
}
@@ -379,6 +379,26 @@
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;
+ }
}
}
Modified: branches/harmonic-skeleton/source/blender/src/buttons_editing.c
===================================================================
--- branches/harmonic-skeleton/source/blender/src/buttons_editing.c 2008-06-26 17:08:07 UTC (rev 15362)
+++ branches/harmonic-skeleton/source/blender/src/buttons_editing.c 2008-06-26 18:15:45 UTC (rev 15363)
@@ -5000,11 +5000,13 @@
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)
Modified: branches/harmonic-skeleton/source/blender/src/reeb.c
===================================================================
--- branches/harmonic-skeleton/source/blender/src/reeb.c 2008-06-26 17:08:07 UTC (rev 15362)
+++ branches/harmonic-skeleton/source/blender/src/reeb.c 2008-06-26 18:15:45 UTC (rev 15363)
@@ -779,14 +779,17 @@
{
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 @@
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 @@
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 @@
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 @@
/* 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)
+ 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->v2;
+ 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;
+ }
+ }
}
- else
- {
- eve2 = eed->v1;
- }
- /* 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 @@
/* 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);
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list