diff options
author | Martin Poirier <theeth@yahoo.com> | 2008-05-28 20:39:05 +0400 |
---|---|---|
committer | Martin Poirier <theeth@yahoo.com> | 2008-05-28 20:39:05 +0400 |
commit | ab787c976567f46c7fcb5fd18806903a270350b9 (patch) | |
tree | ff28311bae91e30d099c83cf13bea3f9d46791f5 | |
parent | db44a4a1a79286ed77dd34d0aaf1259a1f85d3be (diff) |
Generalizing the graph code used for Reeb graphs and Rig (Armature) graphs
Removing a lot of duplicated code
-rw-r--r-- | source/blender/blenlib/BLI_graph.h | 102 | ||||
-rw-r--r-- | source/blender/blenlib/intern/graph.c | 678 | ||||
-rw-r--r-- | source/blender/include/reeb.h | 69 | ||||
-rw-r--r-- | source/blender/src/autoarmature.c | 750 | ||||
-rw-r--r-- | source/blender/src/editarmature.c | 40 | ||||
-rw-r--r-- | source/blender/src/reeb.c | 1131 |
6 files changed, 1216 insertions, 1554 deletions
diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h new file mode 100644 index 00000000000..1d29cc88651 --- /dev/null +++ b/source/blender/blenlib/BLI_graph.h @@ -0,0 +1,102 @@ +#ifndef BLI_GRAPH_H_ +#define BLI_GRAPH_H_ + +#include "DNA_listBase.h" + +struct BGraph; +struct BNode; +struct BArc; + +struct RadialArc; + +typedef void (*FreeArc)(struct BArc*); +typedef void (*FreeNode)(struct BNode*); +typedef void (*RadialSymmetry)(struct BNode* root_node, struct RadialArc* ring, int total); +typedef void (*AxialSymmetry)(struct BNode* root_node, struct BNode* node1, struct BNode* node2, struct BArc* arc1, struct BArc* arc2); + +/* IF YOU MODIFY THOSE TYPES, YOU NEED TO UPDATE ALL THOSE THAT "INHERIT" FROM THEM + * + * RigGraph, ReebGraph + * + * */ + +typedef struct BGraph { + ListBase arcs; + ListBase nodes; + + /* function pointer to deal with custom fonctionnality */ + FreeArc free_arc; + FreeNode free_node; + RadialSymmetry radial_symmetry; + AxialSymmetry axial_symmetry; +} BGraph; + +typedef struct BNode { + void *next, *prev; + float p[3]; + int flag; + + int degree; + struct BArc **arcs; + + int symmetry_level; + int symmetry_flag; + float symmetry_axis[3]; +} BNode; + +typedef struct BArc { + void *next, *prev; + struct BNode *head, *tail; + int flag; + + float length; + + int symmetry_level; + int symmetry_flag; +} BArc; + +/* Helper structure for radial symmetry */ +typedef struct RadialArc +{ + struct BArc *arc; + float n[3]; /* normalized vector joining the nodes of the arc */ +} RadialArc; + +BNode *BLI_otherNode(BArc *arc, BNode *node); + +void BLI_freeNode(BGraph *graph, BNode *node); + +void BLI_flagNodes(BGraph *graph, int flag); +void BLI_flagArcs(BGraph *graph, int flag); + +int BLI_hasAdjacencyList(BGraph *rg); +void BLI_buildAdjacencyList(BGraph *rg); + +void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced); +void BLI_removeDoubleNodes(BGraph *graph, float limit); + +BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v); + +int BLI_isGraphCyclic(BGraph *graph); + +/*------------ Symmetry handling ------------*/ +// float limit = G.scene->toolsettings->skgen_symmetry_limit; +void BLI_markdownSymmetry(BGraph *graph, BNode *root_node, float limit); + +void BLI_mirrorAlongAxis(float v[3], float center[3], float axis[3]); + +/* BNode symmetry flags */ +#define SYM_TOPOLOGICAL 1 +#define SYM_PHYSICAL 2 + +/* the following two are exclusive */ +#define SYM_AXIAL 4 +#define SYM_RADIAL 8 + +/* BArc symmetry flags + * + * axial symetry sides */ +#define SYM_SIDE_POSITIVE 1 +#define SYM_SIDE_NEGATIVE 2 + +#endif /*BLI_GRAPH_H_*/ diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c new file mode 100644 index 00000000000..3a484e15642 --- /dev/null +++ b/source/blender/blenlib/intern/graph.c @@ -0,0 +1,678 @@ +/** + * $Id: + * + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * Contributor(s): Martin Poirier + * + * ***** END GPL LICENSE BLOCK ***** + * graph.c: Common graph interface and methods + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_graph.h" +#include "BLI_blenlib.h" +#include "BLI_arithb.h" + +#include "BKE_utildefines.h" + +void BLI_freeNode(BGraph *graph, BNode *node) +{ + if (node->arcs) + { + MEM_freeN(node->arcs); + } + + if (graph->free_node) + { + graph->free_node(node); + } +} + +BNode *BLI_otherNode(BArc *arc, BNode *node) +{ + return (arc->head == node) ? arc->tail : arc->head; +} + +void BLI_flagNodes(BGraph *graph, int flag) +{ + BNode *node; + + for(node = graph->nodes.first; node; node = node->next) + { + node->flag = flag; + } +} + +void BLI_flagArcs(BGraph *graph, int flag) +{ + BArc *arc; + + for(arc = graph->arcs.first; arc; arc = arc->next) + { + arc->flag = flag; + } +} + +static void addArcToNodeAdjacencyList(BNode *node, BArc *arc) +{ + node->arcs[node->degree] = arc; + node->degree++; +} + +void BLI_buildAdjacencyList(BGraph *rg) +{ + BNode *node; + BArc *arc; + + for(node = rg->nodes.first; node; node = node->next) + { + if (node->arcs != NULL) + { + MEM_freeN(node->arcs); + } + + node->arcs = MEM_callocN((node->degree) * sizeof(BArc*), "adjacency list"); + + /* temporary use to indicate the first index available in the lists */ + node->degree = 0; + } + + for(arc = rg->arcs.first; arc; arc= arc->next) + { + addArcToNodeAdjacencyList(arc->head, arc); + addArcToNodeAdjacencyList(arc->tail, arc); + } +} + +int BLI_hasAdjacencyList(BGraph *rg) +{ + BNode *node; + + for(node = rg->nodes.first; node; node = node->next) + { + if (node->arcs == NULL) + { + return 0; + } + } + + return 1; +} + +void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced) +{ + BArc *arc, *next_arc; + + for (arc = graph->arcs.first; arc; arc = next_arc) + { + next_arc = arc->next; + + if (arc->head == node_replaced) + { + arc->head = node_src; + node_src->degree++; + } + + if (arc->tail == node_replaced) + { + arc->tail = node_src; + node_src->degree++; + } + + if (arc->head == arc->tail) + { + node_src->degree -= 2; + + graph->free_arc(arc); + BLI_freelinkN(&graph->arcs, arc); + } + } +} + +void BLI_removeDoubleNodes(BGraph *graph, float limit) +{ + BNode *node_src, *node_replaced; + + for(node_src = graph->nodes.first; node_src; node_src = node_src->next) + { + for(node_replaced = graph->nodes.first; node_replaced; node_replaced = node_replaced->next) + { + if (node_replaced != node_src && VecLenf(node_replaced->p, node_src->p) <= limit) + { + BLI_replaceNode(graph, node_src, node_replaced); + + BLI_freeNode(graph, node_replaced); + BLI_remlink(&graph->nodes, node_replaced); + } + } + } + +} + +/*************************************** CYCLE DETECTION ***********************************************/ + +int detectCycle(BNode *node, BArc *src_arc) +{ + int value = 0; + + if (node->flag == 0) + { + int i; + + /* mark node as visited */ + node->flag = 1; + + for(i = 0; i < node->degree && value == 0; i++) + { + BArc *arc = node->arcs[i]; + + /* don't go back on the source arc */ + if (arc != src_arc) + { + value = detectCycle(BLI_otherNode(arc, node), arc); + } + } + } + else + { + value = 1; + } + + return value; +} + +int BLI_isGraphCyclic(BGraph *graph) +{ + BNode *node; + int value = 0; + + /* NEED TO CHECK IF ADJACENCY LIST EXIST */ + + /* Mark all nodes as not visited */ + BLI_flagNodes(graph, 0); + + /* detectCycles in subgraphs */ + for(node = graph->nodes.first; node && value == 0; node = node->next) + { + /* only for nodes in subgraphs that haven't been visited yet */ + if (node->flag == 0) + { + value = value || detectCycle(node, NULL); + } + } + + return value; +} + +BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v) +{ + BArc *nextArc = arc->next; + + for(nextArc = graph->arcs.first; nextArc; nextArc = nextArc->next) + { + if (arc != nextArc && (nextArc->head == v || nextArc->tail == v)) + { + break; + } + } + + return nextArc; +} + +/*********************************** GRAPH AS TREE FUNCTIONS *******************************************/ + +int BLI_subtreeDepth(BNode *node, BArc *rootArc) +{ + int depth = 0; + + /* Base case, no arcs leading away */ + if (node->arcs == NULL || *(node->arcs) == NULL) + { + return 0; + } + else + { + int i; + + for(i = 0; i < node->degree; i++) + { + BArc *arc = node->arcs[i]; + + /* only arcs that go down the tree */ + if (arc != rootArc) + { + BNode *newNode = BLI_otherNode(arc, node); + depth = MAX2(depth, BLI_subtreeDepth(newNode, arc)); + } + } + } + + return depth + 1; //BLI_countlist(&rootArc->edges); +} + +/********************************* SYMMETRY DETECTION **************************************************/ + +void markdownSymmetryArc(BGraph *graph, BArc *arc, BNode *node, int level, float limit); + +void BLI_mirrorAlongAxis(float v[3], float center[3], float axis[3]) +{ + float dv[3], pv[3]; + + VecSubf(dv, v, center); + Projf(pv, dv, axis); + VecMulf(pv, -2); + VecAddf(v, v, pv); +} + +static void markRadialSymmetry(BGraph *graph, BNode *node, int depth, float axis[3], float limit) +{ + 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++) + { + float minAngle = 3; /* arbitrary high value, higher than 2, at least */ + int minIndex = -1; + int j; + + for (j = i + 1; j < count; j++) + { + float angle = Inpf(ring[i].n, ring[j].n); + + /* map negative values to 1..2 */ + if (angle < 0) + { + angle = 1 - angle; + } + + if (angle < minAngle) + { + minIndex = j; + minAngle = angle; + } + } + + /* swap if needed */ + if (minIndex != i + 1) + { + RadialArc tmp; + tmp = ring[i + 1]; + ring[i + 1] = ring[minIndex]; + ring[minIndex] = tmp; + } + } + + for (i = 0; i < count && 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 */ + + 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); + + VECCOPY(p, node2->p); + BLI_mirrorAlongAxis(p, node->p, normal); + + /* check if it's within limit before continuing */ + if (VecLenf(node1->p, p) > limit) + { + symmetric = 0; + } + + } + + if (symmetric) + { + /* mark node as symmetric physically */ + VECCOPY(node->symmetry_axis, axis); + node->symmetry_flag |= SYM_PHYSICAL; + node->symmetry_flag |= SYM_RADIAL; + + if (graph->radial_symmetry) + { + graph->radial_symmetry(node, ring, count); + } + } + + MEM_freeN(ring); +} + +static void setSideAxialSymmetry(BNode *root_node, BNode *end_node, BArc *arc) +{ + float vec[3]; + + VecSubf(vec, end_node->p, root_node->p); + + if (Inpf(vec, root_node->symmetry_axis) < 0) + { + arc->symmetry_flag |= SYM_SIDE_NEGATIVE; + } + else + { + arc->symmetry_flag |= SYM_SIDE_POSITIVE; + } +} + +static void markAxialSymmetry(BGraph *graph, BNode *node, int depth, float axis[3], float limit) +{ + BArc *arc1 = NULL; + BArc *arc2 = NULL; + BNode *node1 = NULL, *node2 = NULL; + float nor[3], vec[3], p[3]; + int i; + + /* mark topological symmetry */ + node->symmetry_flag |= SYM_TOPOLOGICAL; + + 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) + { + if (arc1 == NULL) + { + arc1 = connectedArc; + node1 = BLI_otherNode(arc1, node); + } + else + { + arc2 = connectedArc; + node2 = BLI_otherNode(arc2, node); + break; /* Can stop now, the two arcs have been found */ + } + } + } + + /* shouldn't happen, but just to be sure */ + if (node1 == NULL || node2 == NULL) + { + 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); + + /* 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); + } + } +} + +static void markdownSecondarySymmetry(BGraph *graph, BNode *node, int depth, int level, float limit) +{ + float axis[3] = {0, 0, 0}; + int count = 0; + int i; + + /* count the number of branches in this symmetry group + * and determinte the axis of symmetry + * */ + 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++; + } + /* If arc is on the axis */ + else if (connectedArc->symmetry_level == level) + { + VecAddf(axis, axis, connectedArc->head->p); + VecSubf(axis, axis, connectedArc->tail->p); + } + } + + Normalize(axis); + + /* Split between axial and radial symmetry */ + if (count == 2) + { + markAxialSymmetry(graph, node, depth, axis, limit); + } + else + { + markRadialSymmetry(graph, node, depth, axis, limit); + } + + /* markdown secondary symetries */ + for (i = 0; i < node->degree; i++) + { + BArc *connectedArc = node->arcs[i]; + + if (connectedArc->symmetry_level == -depth) + { + /* markdown symmetry for branches corresponding to the depth */ + markdownSymmetryArc(graph, connectedArc, node, level + 1, limit); + } + } +} + +void markdownSymmetryArc(BGraph *graph, BArc *arc, BNode *node, int level, float limit) +{ + int i; + arc->symmetry_level = level; + + node = BLI_otherNode(arc, node); + + for (i = 0; i < node->degree; i++) + { + BArc *connectedArc = node->arcs[i]; + + if (connectedArc != arc) + { + BNode *connectedNode = BLI_otherNode(connectedArc, node); + + /* symmetry level is positive value, negative values is subtree depth */ + connectedArc->symmetry_level = -BLI_subtreeDepth(connectedNode, connectedArc); + } + } + + arc = NULL; + + for (i = 0; i < node->degree; i++) + { + int issymmetryAxis = 0; + BArc *connectedArc = node->arcs[i]; + + /* only arcs not already marked as symetric */ + if (connectedArc->symmetry_level < 0) + { + int j; + + /* true by default */ + issymmetryAxis = 1; + + for (j = 0; j < node->degree && issymmetryAxis == 1; j++) + { + BArc *otherArc = node->arcs[j]; + + /* different arc, same depth */ + if (otherArc != connectedArc && otherArc->symmetry_level == connectedArc->symmetry_level) + { + /* not on the symmetry axis */ + issymmetryAxis = 0; + } + } + } + + /* arc could be on the symmetry axis */ + if (issymmetryAxis == 1) + { + /* no arc as been marked previously, keep this one */ + if (arc == NULL) + { + arc = connectedArc; + } + else + { + /* there can't be more than one symmetry arc */ + arc = NULL; + break; + } + } + } + + /* go down the arc continuing the symmetry axis */ + if (arc) + { + markdownSymmetryArc(graph, arc, node, level, limit); + } + + + /* secondary symmetry */ + for (i = 0; i < node->degree; i++) + { + BArc *connectedArc = node->arcs[i]; + + /* only arcs not already marked as symetric and is not the next arc on the symmetry axis */ + if (connectedArc->symmetry_level < 0) + { + /* subtree depth is store as a negative value in the symmetry */ + markdownSecondarySymmetry(graph, node, -connectedArc->symmetry_level, level, limit); + } + } +} + +void BLI_markdownSymmetry(BGraph *graph, BNode *root_node, float limit) +{ + BNode *node; + BArc *arc; + + if (BLI_isGraphCyclic(graph)) + { + return; + } + + /* mark down all arcs as non-symetric */ + BLI_flagArcs(graph, 0); + + /* mark down all nodes as not on the symmetry axis */ + BLI_flagNodes(graph, 0); + + node = root_node; + + /* only work on acyclic graphs and if only one arc is incident on the first node */ + if (node->degree == 1) + { + arc = node->arcs[0]; + + markdownSymmetryArc(graph, arc, node, 1, limit); + + /* mark down non-symetric arcs */ + for (arc = graph->arcs.first; arc; arc = arc->next) + { + if (arc->symmetry_level < 0) + { + arc->symmetry_level = 0; + } + else + { + /* mark down nodes with the lowest level symmetry axis */ + if (arc->head->symmetry_level == 0 || arc->head->symmetry_level > arc->symmetry_level) + { + arc->head->symmetry_level = arc->symmetry_level; + } + if (arc->tail->symmetry_level == 0 || arc->tail->symmetry_level > arc->symmetry_level) + { + arc->tail->symmetry_level = arc->symmetry_level; + } + } + } + } +} + diff --git a/source/blender/include/reeb.h b/source/blender/include/reeb.h index e26b4080249..b24ba25aa5d 100644 --- a/source/blender/include/reeb.h +++ b/source/blender/include/reeb.h @@ -30,6 +30,8 @@ #include "DNA_listBase.h" +#include "BLI_graph.h" + struct GHash; struct EdgeHash; struct ReebArc; @@ -37,8 +39,15 @@ struct ReebEdge; struct ReebNode; typedef struct ReebGraph { - ListBase arcs; - ListBase nodes; + ListBase arcs; + ListBase nodes; + + FreeArc free_arc; + FreeNode free_node; + RadialSymmetry radial_symmetry; + AxialSymmetry axial_symmetry; + /*********************************/ + int totnodes; struct EdgeHash *emap; } ReebGraph; @@ -50,17 +59,20 @@ typedef struct EmbedBucket { } EmbedBucket; typedef struct ReebNode { - struct ReebNode *next, *prev; - struct ReebArc **arcs; - int index; - int degree; - float weight; + void *next, *prev; float p[3]; int flag; + int degree; + struct ReebArc **arcs; + int symmetry_level; int symmetry_flag; float symmetry_axis[3]; + /*********************************/ + + int index; + float weight; } ReebNode; typedef struct ReebEdge { @@ -72,15 +84,19 @@ typedef struct ReebEdge { } ReebEdge; typedef struct ReebArc { - struct ReebArc *next, *prev; - ListBase edges; - struct ReebNode *v1, *v2; - struct EmbedBucket *buckets; - int bcount; + void *next, *prev; + struct ReebNode *head, *tail; int flag; + float length; + int symmetry_level; int symmetry_flag; + /*********************************/ + + ListBase edges; + int bcount; + struct EmbedBucket *buckets; struct GHash *faces; float angle; @@ -107,8 +123,6 @@ void renormalizeWeight(struct EditMesh *em, float newmax); ReebGraph * generateReebGraph(struct EditMesh *me, int subdivisions); ReebGraph * newReebGraph(); -#define OTHER_NODE(arc, node) ((arc->v1 == node) ? arc->v2 : arc->v1) - void initArcIterator(struct ReebArcIterator *iter, struct ReebArc *arc, struct ReebNode *head); void initArcIterator2(struct ReebArcIterator *iter, struct ReebArc *arc, int start, int end); void initArcIteratorStart(struct ReebArcIterator *iter, struct ReebArc *arc, struct ReebNode *head, int start); @@ -129,36 +143,9 @@ void repositionNodes(ReebGraph *rg); void postprocessGraph(ReebGraph *rg, char mode); void removeNormalNodes(ReebGraph *rg); -/* Graph processing */ -void buildAdjacencyList(ReebGraph *rg); - void sortNodes(ReebGraph *rg); void sortArcs(ReebGraph *rg); -int subtreeDepth(ReebNode *node, ReebArc *rootArc); -int countConnectedArcs(ReebGraph *rg, ReebNode *node); -int hasAdjacencyList(ReebGraph *rg); -int isGraphCyclic(ReebGraph *rg); - -/*------------ Symmetry handling ------------*/ -void markdownSymmetry(ReebGraph *rg); - -/* ReebNode symmetry flags */ -#define SYM_TOPOLOGICAL 1 -#define SYM_PHYSICAL 2 - -/* the following two are exclusive */ -#define SYM_AXIAL 4 -#define SYM_RADIAL 8 - -/* ReebArc symmetry flags - * - * axial symetry sides */ -#define SYM_SIDE_POSITIVE 1 -#define SYM_SIDE_NEGATIVE 2 - - - /*------------ Sanity check ------------*/ void verifyBuckets(ReebGraph *rg); void verifyFaces(ReebGraph *rg); diff --git a/source/blender/src/autoarmature.c b/source/blender/src/autoarmature.c index d3cea1be786..741398951bf 100644 --- a/source/blender/src/autoarmature.c +++ b/source/blender/src/autoarmature.c @@ -1,5 +1,5 @@ /** - * $Id: editarmature.c 14848 2008-05-15 08:05:56Z aligorith $ + * $Id: * * ***** BEGIN GPL LICENSE BLOCK ***** * @@ -46,6 +46,7 @@ #include "BLI_arithb.h" #include "BLI_editVert.h" #include "BLI_ghash.h" +#include "BLI_graph.h" #include "BDR_editobject.h" @@ -70,37 +71,47 @@ struct RigArc; struct RigEdge; typedef struct RigGraph { - ListBase arcs; - ListBase nodes; - struct RigNode *head; + ListBase arcs; + ListBase nodes; + FreeArc free_arc; + FreeNode free_node; + RadialSymmetry radial_symmetry; + AxialSymmetry axial_symmetry; + /*********************************/ + + struct RigNode *head; ReebGraph *link; } RigGraph; typedef struct RigNode { - struct RigNode *next, *prev; + void *next, *prev; float p[3]; - int degree; - struct RigArc **arcs; int flag; - + + int degree; + struct BArc **arcs; + int symmetry_level; int symmetry_flag; float symmetry_axis[3]; + /*********************************/ ReebNode *link; } RigNode; typedef struct RigArc { - struct RigArc *next, *prev; + void *next, *prev; RigNode *head, *tail; - ListBase edges; - float length; int flag; + float length; + int symmetry_level; int symmetry_flag; + /*********************************/ + ListBase edges; int count; ReebArc *link; } RigArc; @@ -116,45 +127,7 @@ typedef struct RigEdge { /*******************************************************************************************************/ static void RIG_calculateEdgeAngle(RigEdge *edge_first, RigEdge *edge_second); -void RIG_markdownSymmetry(RigGraph *rg); -void RIG_markdownSymmetryArc(RigArc *arc, RigNode *node, int level); -void RIG_markdownSecondarySymmetry(RigNode *node, int depth, int level); - - -/*******************************************************************************************************/ -static RigNode *RIG_otherNode(RigArc *arc, RigNode *node) -{ - if (arc->head == node) - return arc->tail; - else - return arc->head; -} - -static void RIG_flagNodes(RigGraph *rg, int flag) -{ - RigNode *node; - - for(node = rg->nodes.first; node; node = node->next) - { - node->flag = flag; - } -} - -static void RIG_flagArcs(RigGraph *rg, int flag) -{ - RigArc *arc; - - for(arc = rg->arcs.first; arc; arc = arc->next) - { - arc->flag = flag; - } -} -static void RIG_addArcToNodeAdjacencyList(RigNode *node, RigArc *arc) -{ - node->arcs[node->degree] = arc; - node->degree++; -} /*********************************** EDITBONE UTILS ****************************************************/ int countEditBoneChildren(ListBase *list, EditBone *parent) @@ -192,6 +165,34 @@ EditBone* nextEditBoneChild(ListBase *list, EditBone *parent, int n) return NULL; } + +/************************************ DESTRUCTORS ******************************************************/ + +void RIG_freeRigArc(BArc *arc) +{ + BLI_freelistN(&((RigArc*)arc)->edges); +} + +void RIG_freeRigGraph(BGraph *rg) +{ + BNode *node; + BArc *arc; + + for (arc = rg->arcs.first; arc; arc = arc->next) + { + RIG_freeRigArc(arc); + } + BLI_freelistN(&rg->arcs); + + for (node = rg->nodes.first; node; node = node->next) + { + BLI_freeNode((BGraph*)rg, (BNode*)node); + } + BLI_freelistN(&rg->nodes); + + MEM_freeN(rg); +} + /************************************* ALLOCATORS ******************************************************/ static RigGraph *newRigGraph() @@ -201,6 +202,9 @@ static RigGraph *newRigGraph() rg->head = NULL; + rg->free_arc = RIG_freeRigArc; + rg->free_node = NULL; + return rg; } @@ -209,7 +213,6 @@ static RigArc *newRigArc(RigGraph *rg) RigArc *arc; arc = MEM_callocN(sizeof(RigArc), "rig arc"); - arc->length = 0; arc->count = 0; BLI_addtail(&rg->arcs, arc); @@ -279,118 +282,13 @@ static void RIG_addEdgeToArc(RigArc *arc, float tail[3], EditBone *bone) edge->length = VecLenf(edge->head, edge->tail); arc->length += edge->length; + arc->count += 1; } -/************************************ DESTRUCTORS ******************************************************/ - -static void RIG_freeRigNode(RigNode *node) -{ - if (node->arcs) - { - MEM_freeN(node->arcs); - } -} - -static void RIG_freeRigArc(RigArc *arc) -{ - BLI_freelistN(&arc->edges); -} - -static void RIG_freeRigGraph(RigGraph *rg) -{ - RigNode *node; - RigArc *arc; - - for (arc = rg->arcs.first; arc; arc = arc->next) - { - RIG_freeRigArc(arc); - } - BLI_freelistN(&rg->arcs); - - for (node = rg->nodes.first; node; node = node->next) - { - RIG_freeRigNode(node); - } - BLI_freelistN(&rg->nodes); - - MEM_freeN(rg); -} /*******************************************************************************************************/ -static void RIG_buildAdjacencyList(RigGraph *rg) -{ - RigNode *node; - RigArc *arc; - - for(node = rg->nodes.first; node; node = node->next) - { - if (node->arcs != NULL) - { - MEM_freeN(node->arcs); - } - - node->arcs = MEM_callocN((node->degree + 1) * sizeof(RigArc*), "adjacency list"); - - /* temporary use to indicate the first index available in the lists */ - node->degree = 0; - } - - for(arc = rg->arcs.first; arc; arc= arc->next) - { - RIG_addArcToNodeAdjacencyList(arc->head, arc); - RIG_addArcToNodeAdjacencyList(arc->tail, arc); - } -} - -static void RIG_replaceNode(RigGraph *rg, RigNode *node_src, RigNode *node_replaced) -{ - RigArc *arc, *next_arc; - - for (arc = rg->arcs.first; arc; arc = next_arc) - { - next_arc = arc->next; - - if (arc->head == node_replaced) - { - arc->head = node_src; - node_src->degree++; - } - - if (arc->tail == node_replaced) - { - arc->tail = node_src; - node_src->degree++; - } - - if (arc->head == arc->tail) - { - node_src->degree -= 2; - - RIG_freeRigArc(arc); - BLI_freelinkN(&rg->arcs, arc); - } - } -} - -static void RIG_removeDoubleNodes(RigGraph *rg, float limit) -{ - RigNode *node_src, *node_replaced; - - for(node_src = rg->nodes.first; node_src; node_src = node_src->next) - { - for(node_replaced = rg->nodes.first; node_replaced; node_replaced = node_replaced->next) - { - if (node_replaced != node_src && VecLenf(node_replaced->p, node_src->p) <= limit) - { - RIG_replaceNode(rg, node_src, node_replaced); - } - } - } - -} - static void RIG_calculateEdgeAngle(RigEdge *edge_first, RigEdge *edge_second) { float vec_first[3], vec_second[3]; @@ -404,483 +302,6 @@ static void RIG_calculateEdgeAngle(RigEdge *edge_first, RigEdge *edge_second) edge_first->angle = saacos(Inpf(vec_first, vec_second)); } -/*********************************** GRAPH AS TREE FUNCTIONS *******************************************/ - -int RIG_subtreeDepth(RigNode *node, RigArc *rootArc) -{ - int depth = 0; - - /* Base case, no arcs leading away */ - if (node->arcs == NULL || *(node->arcs) == NULL) - { - return 0; - } - else - { - RigArc ** pArc; - - for(pArc = node->arcs; *pArc; pArc++) - { - RigArc *arc = *pArc; - - /* only arcs that go down the tree */ - if (arc != rootArc) - { - RigNode *newNode = RIG_otherNode(arc, node); - depth = MAX2(depth, RIG_subtreeDepth(newNode, arc)); - } - } - } - - return depth + BLI_countlist(&rootArc->edges); -} - -int RIG_countConnectedArcs(RigGraph *rg, RigNode *node) -{ - int count = 0; - - /* use adjacency list if present */ - if (node->arcs) - { - RigArc **arcs; - - for(arcs = node->arcs; *arcs; arcs++) - { - count++; - } - } - else - { - RigArc *arc; - for(arc = rg->arcs.first; arc; arc = arc->next) - { - if (arc->head == node || arc->tail == node) - { - count++; - } - } - } - - return count; -} - -/********************************* SYMMETRY DETECTION **************************************************/ - -static void mirrorAlongAxis(float v[3], float center[3], float axis[3]) -{ - float dv[3], pv[3]; - - VecSubf(dv, v, center); - Projf(pv, dv, axis); - VecMulf(pv, -2); - VecAddf(v, v, pv); -} - -/* Helper structure for radial symmetry */ -typedef struct RadialArc -{ - RigArc *arc; - float n[3]; /* normalized vector joining the nodes of the arc */ -} RadialArc; - -void RIG_markRadialSymmetry(RigNode *node, int depth, float axis[3]) -{ - RadialArc *ring = NULL; - RadialArc *unit; - float limit = G.scene->toolsettings->skgen_symmetry_limit; - 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; node->arcs[i] != NULL; i++) - { - RigArc *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; node->arcs[i] != NULL; i++) - { - RigArc *connectedArc = node->arcs[i]; - - /* depth is store as a negative in flag. symmetry level is positive */ - if (connectedArc->symmetry_level == -depth) - { - RigNode *otherNode = RIG_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++) - { - float minAngle = 3; /* arbitrary high value, higher than 2, at least */ - int minIndex = -1; - int j; - - for (j = i + 1; j < count; j++) - { - float angle = Inpf(ring[i].n, ring[j].n); - - /* map negative values to 1..2 */ - if (angle < 0) - { - angle = 1 - angle; - } - - if (angle < minAngle) - { - minIndex = j; - minAngle = angle; - } - } - - /* swap if needed */ - if (minIndex != i + 1) - { - RadialArc tmp; - tmp = ring[i + 1]; - ring[i + 1] = ring[minIndex]; - ring[minIndex] = tmp; - } - } - - for (i = 0; i < count && symmetric; i++) - { - RigNode *node1, *node2; - float tangent[3]; - float normal[3]; - float p[3]; - int j = (i + 1) % count; /* next arc in the circular list */ - - VecAddf(tangent, ring[i].n, ring[j].n); - Crossf(normal, tangent, axis); - - node1 = RIG_otherNode(ring[i].arc, node); - node2 = RIG_otherNode(ring[j].arc, node); - - VECCOPY(p, node2->p); - mirrorAlongAxis(p, node->p, normal); - - /* check if it's within limit before continuing */ - if (VecLenf(node1->p, p) > limit) - { - symmetric = 0; - } - - } - - if (symmetric) - { - /* mark node as symmetric physically */ - VECCOPY(node->symmetry_axis, axis); - node->symmetry_flag |= SYM_PHYSICAL; - node->symmetry_flag |= SYM_RADIAL; - } - - MEM_freeN(ring); -} - -static void setSideAxialSymmetry(RigNode *root_node, RigNode *end_node, RigArc *arc) -{ - float vec[3]; - - VecSubf(vec, end_node->p, root_node->p); - - if (Inpf(vec, root_node->symmetry_axis) < 0) - { - arc->symmetry_flag |= SYM_SIDE_NEGATIVE; - } - else - { - arc->symmetry_flag |= SYM_SIDE_POSITIVE; - } -} - -void RIG_markAxialSymmetry(RigNode *node, int depth, float axis[3]) -{ - RigArc *arc1 = NULL; - RigArc *arc2 = NULL; - RigNode *node1 = NULL, *node2 = NULL; - float limit = G.scene->toolsettings->skgen_symmetry_limit; - float nor[3], vec[3], p[3]; - int i; - - /* mark topological symmetry */ - node->symmetry_flag |= SYM_TOPOLOGICAL; - - for (i = 0; node->arcs[i] != NULL; i++) - { - RigArc *connectedArc = node->arcs[i]; - - /* depth is store as a negative in flag. symmetry level is positive */ - if (connectedArc->symmetry_level == -depth) - { - if (arc1 == NULL) - { - arc1 = connectedArc; - node1 = RIG_otherNode(arc1, node); - } - else - { - arc2 = connectedArc; - node2 = RIG_otherNode(arc2, node); - break; /* Can stop now, the two arcs have been found */ - } - } - } - - /* shouldn't happen, but just to be sure */ - if (node1 == NULL || node2 == NULL) - { - 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); - mirrorAlongAxis(p, node->p, nor); - - /* 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); - printf("flag: %i <-> %i\n", arc1->symmetry_flag, arc2->symmetry_flag); - } - else - { - printf("NOT SYMMETRIC!\n"); - printf("%f <= %f\n", VecLenf(node1->p, p), limit); - printvecf("axis", nor); - } -} - -void RIG_markdownSecondarySymmetry(RigNode *node, int depth, int level) -{ - float axis[3] = {0, 0, 0}; - int count = 0; - int i; - - /* count the number of branches in this symmetry group - * and determinte the axis of symmetry - * */ - for (i = 0; node->arcs[i] != NULL; i++) - { - RigArc *connectedArc = node->arcs[i]; - - /* depth is store as a negative in flag. symmetry level is positive */ - if (connectedArc->symmetry_level == -depth) - { - count++; - } - /* If arc is on the axis */ - else if (connectedArc->symmetry_level == level) - { - VecAddf(axis, axis, connectedArc->head->p); - VecSubf(axis, axis, connectedArc->tail->p); - } - } - - Normalize(axis); - - /* Split between axial and radial symmetry */ - if (count == 2) - { - RIG_markAxialSymmetry(node, depth, axis); - } - else - { - RIG_markRadialSymmetry(node, depth, axis); - } - - /* markdown secondary symetries */ - for (i = 0; node->arcs[i] != NULL; i++) - { - RigArc *connectedArc = node->arcs[i]; - - if (connectedArc->symmetry_level == -depth) - { - /* markdown symmetry for branches corresponding to the depth */ - RIG_markdownSymmetryArc(connectedArc, node, level + 1); - } - } -} - -void RIG_markdownSymmetryArc(RigArc *arc, RigNode *node, int level) -{ - int i; - arc->symmetry_level = level; - - node = RIG_otherNode(arc, node); - - for (i = 0; node->arcs[i] != NULL; i++) - { - RigArc *connectedArc = node->arcs[i]; - - if (connectedArc != arc) - { - RigNode *connectedNode = RIG_otherNode(connectedArc, node); - - /* symmetry level is positive value, negative values is subtree depth */ - connectedArc->symmetry_level = -RIG_subtreeDepth(connectedNode, connectedArc); - } - } - - arc = NULL; - - for (i = 0; node->arcs[i] != NULL; i++) - { - int issymmetryAxis = 0; - RigArc *connectedArc = node->arcs[i]; - - /* only arcs not already marked as symetric */ - if (connectedArc->symmetry_level < 0) - { - int j; - - /* true by default */ - issymmetryAxis = 1; - - for (j = 0; node->arcs[j] != NULL && issymmetryAxis == 1; j++) - { - RigArc *otherArc = node->arcs[j]; - - /* different arc, same depth */ - if (otherArc != connectedArc && otherArc->symmetry_level == connectedArc->symmetry_level) - { - /* not on the symmetry axis */ - issymmetryAxis = 0; - } - } - } - - /* arc could be on the symmetry axis */ - if (issymmetryAxis == 1) - { - /* no arc as been marked previously, keep this one */ - if (arc == NULL) - { - arc = connectedArc; - } - else - { - /* there can't be more than one symmetry arc */ - arc = NULL; - break; - } - } - } - - /* go down the arc continuing the symmetry axis */ - if (arc) - { - RIG_markdownSymmetryArc(arc, node, level); - } - - - /* secondary symmetry */ - for (i = 0; node->arcs[i] != NULL; i++) - { - RigArc *connectedArc = node->arcs[i]; - - /* only arcs not already marked as symetric and is not the next arc on the symmetry axis */ - if (connectedArc->symmetry_level < 0) - { - /* subtree depth is store as a negative value in the symmetry */ - RIG_markdownSecondarySymmetry(node, -connectedArc->symmetry_level, level); - } - } -} - -void RIG_markdownSymmetry(RigGraph *rg) -{ - RigNode *node; - RigArc *arc; - - /* mark down all arcs as non-symetric */ - RIG_flagArcs(rg, 0); - - /* mark down all nodes as not on the symmetry axis */ - RIG_flagNodes(rg, 0); - - if (rg->head) - { - node = rg->head; - } - else - { - /* !TODO! DO SOMETHING SMART HERE */ - return; - } - - /* only work on acyclic graphs and if only one arc is incident on the first node */ - if (RIG_countConnectedArcs(rg, node) == 1) - { - arc = node->arcs[0]; - - RIG_markdownSymmetryArc(arc, node, 1); - - /* mark down non-symetric arcs */ - for (arc = rg->arcs.first; arc; arc = arc->next) - { - if (arc->symmetry_level < 0) - { - arc->symmetry_level = 0; - } - else - { - /* mark down nodes with the lowest level symmetry axis */ - if (arc->head->symmetry_level == 0 || arc->head->symmetry_level > arc->symmetry_level) - { - arc->head->symmetry_level = arc->symmetry_level; - } - if (arc->tail->symmetry_level == 0 || arc->tail->symmetry_level > arc->symmetry_level) - { - arc->tail->symmetry_level = arc->symmetry_level; - } - } - } - } -} - /*******************************************************************************************************/ static void RIG_arcFromBoneChain(RigGraph *rg, ListBase *list, EditBone *root_bone, RigNode *starting_node) @@ -942,7 +363,7 @@ static void RIG_arcFromBoneChain(RigGraph *rg, ListBase *list, EditBone *root_bo if (contain_head) { - rg->head = arc->tail; + rg->head = (RigNode*)arc->tail; } } @@ -955,7 +376,7 @@ static void RIG_findHead(RigGraph *rg) { RigArc *arc = rg->arcs.first; - rg->head = arc->head; + rg->head = (RigNode*)arc->head; } } } @@ -997,7 +418,7 @@ static void RIG_printArc(RigArc *arc) printf("\n"); - RIG_printNode(arc->head, "head"); + RIG_printNode((RigNode*)arc->head, "head"); for (edge = arc->edges.first; edge; edge = edge->next) { @@ -1009,7 +430,7 @@ static void RIG_printArc(RigArc *arc) } printf("symmetry level: %i\n", arc->symmetry_level); - RIG_printNode(arc->tail, "tail"); + RIG_printNode((RigNode*)arc->tail, "tail"); } void RIG_printGraph(RigGraph *rg) @@ -1048,9 +469,9 @@ static RigGraph *armatureToGraph(ListBase *list) } } - RIG_removeDoubleNodes(rg, 0); + BLI_removeDoubleNodes((BGraph*)rg, 0); - RIG_buildAdjacencyList(rg); + BLI_buildAdjacencyList((BGraph*)rg); RIG_findHead(rg); @@ -1151,6 +572,8 @@ static void retargetArctoArcAggresive(RigArc *iarc) int first_pass = 1; int must_move = nb_joints - 1; int i; + + printf("aggressive\n"); positions = MEM_callocN(sizeof(int) * nb_joints, "Aggresive positions"); best_positions = MEM_callocN(sizeof(int) * nb_joints, "Best Aggresive positions"); @@ -1161,13 +584,13 @@ static void retargetArctoArcAggresive(RigArc *iarc) if (earc->symmetry_level == 1 && iarc->symmetry_level == 1) { symmetry_axis = 1; - node_start = earc->v2; - node_end = earc->v1; + node_start = earc->tail; + node_end = earc->head; } else { - node_start = earc->v1; - node_end = earc->v2; + node_start = earc->head; + node_end = earc->tail; } /* init with first values */ @@ -1375,13 +798,13 @@ static void retargetArctoArcLength(RigArc *iarc) if (earc->symmetry_level == 1 && iarc->symmetry_level == 1) { symmetry_axis = 1; - node_start = earc->v2; - node_end = earc->v1; + node_start = (ReebNode*)earc->tail; + node_end = (ReebNode*)earc->head; } else { - node_start = earc->v1; - node_end = earc->v2; + node_start = (ReebNode*)earc->head; + node_end = (ReebNode*)earc->tail; } initArcIterator(&iter, earc, node_start); @@ -1499,14 +922,14 @@ static void retargetArctoArc(RigArc *iarc) /* symmetry axis */ if (earc->symmetry_level == 1 && iarc->symmetry_level == 1) { - VECCOPY(bone->head, earc->v2->p); - VECCOPY(bone->tail, earc->v1->p); + VECCOPY(bone->head, earc->tail->p); + VECCOPY(bone->tail, earc->head->p); } /* or not */ else { - VECCOPY(bone->head, earc->v1->p); - VECCOPY(bone->tail, earc->v2->p); + VECCOPY(bone->head, earc->head->p); + VECCOPY(bone->tail, earc->tail->p); } } else @@ -1535,8 +958,9 @@ static void findCorrespondingArc(RigArc *start_arc, RigNode *start_node, RigArc next_iarc->link = NULL; - for(i = 0, next_earc = enode->arcs[i]; next_earc; i++, next_earc = enode->arcs[i]) + for(i = 0; i < enode->degree; i++) { + next_earc = (ReebArc*)enode->arcs[i]; if (next_earc->flag == 0 && /* not already taken */ next_earc->symmetry_flag == symmetry_flag && next_earc->symmetry_level == symmetry_level) @@ -1561,8 +985,9 @@ static void findCorrespondingArc(RigArc *start_arc, RigNode *start_node, RigArc printf("flag %i -- symmetry level %i -- symmetry flag %i\n", 0, symmetry_level, symmetry_flag); printf("CANDIDATES\n"); - for(i = 0, next_earc = enode->arcs[i]; next_earc; i++, next_earc = enode->arcs[i]) + for(i = 0; i < enode->degree; i++) { + next_earc = (ReebArc*)enode->arcs[i]; printf("flag %i -- symmetry level %i -- symmetry flag %i\n", next_earc->flag, next_earc->symmetry_level, next_earc->symmetry_flag); } } @@ -1574,18 +999,19 @@ static void retargetSubgraph(RigGraph *rigg, RigArc *start_arc, RigNode *start_n ReebArc *earc = start_arc->link; RigNode *inode = start_node; ReebNode *enode = start_node->link; - RigArc *next_iarc; int i; retargetArctoArc(iarc); - enode = OTHER_NODE(earc, enode); - inode = RIG_otherNode(iarc, inode); + enode = (ReebNode*)BLI_otherNode((BArc*)earc, (BNode*)enode); + inode = (RigNode*)BLI_otherNode((BArc*)iarc, (BNode*)inode); inode->link = enode; - for(i = 0, next_iarc = inode->arcs[i]; next_iarc; i++, next_iarc = inode->arcs[i]) + for(i = 0; i < inode->degree; i++) { + RigArc *next_iarc = (RigArc*)inode->arcs[i]; + /* no back tracking */ if (next_iarc != iarc) { @@ -1613,12 +1039,12 @@ static void retargetGraphs(RigGraph *rigg) } earc = reebg->arcs.first; - iarc = rigg->head->arcs[0]; + iarc = (RigArc*)rigg->head->arcs[0]; iarc->link = earc; earc->flag = 1; - enode = earc->v1; + enode = earc->head; inode = iarc->tail; inode->link = enode; @@ -1634,7 +1060,7 @@ void BIF_retargetArmature() reebg = BIF_ReebGraphFromEditMesh(); - markdownSymmetry(reebg); + BLI_markdownSymmetry((BGraph*)reebg, reebg->nodes.first, G.scene->toolsettings->skgen_symmetry_limit); printf("Reeb Graph created\n"); @@ -1660,7 +1086,7 @@ void BIF_retargetArmature() printf("Armature graph created\n"); - RIG_markdownSymmetry(rigg); + BLI_markdownSymmetry((BGraph*)rigg, (BNode*)rigg->head, G.scene->toolsettings->skgen_symmetry_limit); RIG_printGraph(rigg); @@ -1675,7 +1101,7 @@ void BIF_retargetArmature() BLI_freelistN(&list); - RIG_freeRigGraph(rigg); + RIG_freeRigGraph((BGraph*)rigg); } } } diff --git a/source/blender/src/editarmature.c b/source/blender/src/editarmature.c index 37e6510786d..b1185a24d9f 100644 --- a/source/blender/src/editarmature.c +++ b/source/blender/src/editarmature.c @@ -4324,7 +4324,7 @@ float arcLengthRatio(ReebArc *arc) float embedLength = 0.0f; int i; - arcLength = VecLenf(arc->v1->p, arc->v2->p); + arcLength = VecLenf(arc->head->p, arc->tail->p); if (arc->bcount > 0) { @@ -4334,8 +4334,8 @@ float arcLengthRatio(ReebArc *arc) embedLength += VecLenf(arc->buckets[i - 1].p, arc->buckets[i].p); } /* Add head and tail -> embedding vectors */ - embedLength += VecLenf(arc->v1->p, arc->buckets[0].p); - embedLength += VecLenf(arc->v2->p, arc->buckets[arc->bcount - 1].p); + embedLength += VecLenf(arc->head->p, arc->buckets[0].p); + embedLength += VecLenf(arc->tail->p, arc->buckets[arc->bcount - 1].p); } else { @@ -4483,7 +4483,7 @@ void generateSkeletonFromReebGraph(ReebGraph *rg) arcBoneMap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp); - markdownSymmetry(rg); + BLI_markdownSymmetry((BGraph*)rg, rg->nodes.first, G.scene->toolsettings->skgen_symmetry_limit); for (arc = rg->arcs.first; arc; arc = arc->next) { @@ -4501,33 +4501,33 @@ void generateSkeletonFromReebGraph(ReebGraph *rg) */ /* if arc is a symmetry axis, internal bones go up the tree */ - if (arc->symmetry_level == 1 && arc->v2->degree != 1) + if (arc->symmetry_level == 1 && arc->tail->degree != 1) { - head = arc->v2; - tail = arc->v1; + head = arc->tail; + tail = arc->head; arc->flag = -1; /* mark arc direction */ } /* Bones point AWAY from the symmetry axis */ - else if (arc->v1->symmetry_level == 1) + else if (arc->head->symmetry_level == 1) { - head = arc->v1; - tail = arc->v2; + head = arc->head; + tail = arc->tail; arc->flag = 1; /* mark arc direction */ } - else if (arc->v2->symmetry_level == 1) + else if (arc->tail->symmetry_level == 1) { - head = arc->v2; - tail = arc->v1; + head = arc->tail; + tail = arc->head; arc->flag = -1; /* mark arc direction */ } /* otherwise, always go from low weight to high weight */ else { - head = arc->v1; - tail = arc->v2; + head = arc->head; + tail = arc->tail; arc->flag = 1; /* mark arc direction */ } @@ -4571,12 +4571,12 @@ void generateSkeletonFromReebGraph(ReebGraph *rg) ReebArc *incomingArc = NULL; int i; - for (i = 0; node->arcs[i] != NULL; i++) + for (i = 0; i < node->degree; i++) { - arc = node->arcs[i]; + arc = (ReebArc*)node->arcs[i]; /* if arc is incoming into the node */ - if ((arc->v1 == node && arc->flag == -1) || (arc->v2 == node && arc->flag == 1)) + if ((arc->head == node && arc->flag == -1) || (arc->tail == node && arc->flag == 1)) { if (incomingArc == NULL) { @@ -4597,12 +4597,12 @@ void generateSkeletonFromReebGraph(ReebGraph *rg) EditBone *parentBone = BLI_ghash_lookup(arcBoneMap, incomingArc); /* Look for outgoing arcs and parent their bones */ - for (i = 0; node->arcs[i] != NULL; i++) + for (i = 0; i < node->degree; i++) { arc = node->arcs[i]; /* if arc is outgoing from the node */ - if ((arc->v1 == node && arc->flag == 1) || (arc->v2 == node && arc->flag == -1)) + if ((arc->head == node && arc->flag == 1) || (arc->tail == node && arc->flag == -1)) { EditBone *childBone = BLI_ghash_lookup(arcBoneMap, arc); diff --git a/source/blender/src/reeb.c b/source/blender/src/reeb.c index 34230e6dfc2..c437379dbdb 100644 --- a/source/blender/src/reeb.c +++ b/source/blender/src/reeb.c @@ -92,6 +92,10 @@ EditEdge * NextEdgeForVert(EditMesh *em, EditVert *v); void mergeArcFaces(ReebGraph *rg, ReebArc *aDst, ReebArc *aSrc); void addFacetoArc(ReebArc *arc, EditFace *efa); +void REEB_RadialSymmetry(BNode* root_node, RadialArc* ring, int count); +void REEB_AxialSymmetry(BNode* root_node, BNode* node1, BNode* node2, struct BArc* barc1, BArc* barc2); + + /***************************************** BUCKET UTILS **********************************************/ void addVertToBucket(EmbedBucket *b, float co[3]) @@ -155,8 +159,8 @@ void mergeArcBuckets(ReebArc *aDst, ReebArc *aSrc, float start, float end) void allocArcBuckets(ReebArc *arc) { int i; - float start = ceil(arc->v1->weight); - arc->bcount = (int)(floor(arc->v2->weight) - start) + 1; + float start = ceil(((ReebNode*)arc->head)->weight); + arc->bcount = (int)(floor(((ReebNode*)arc->tail)->weight) - start) + 1; if (arc->bcount > 0) { @@ -228,7 +232,8 @@ ReebEdge * copyEdge(ReebEdge *edge) void printArc(ReebArc *arc) { ReebEdge *edge; - printf("arc: (%i)%f -> (%i)%f\n", arc->v1->index, arc->v1->weight, arc->v2->index, arc->v2->weight); + ReebNode *head = (ReebNode*)arc->head; + printf("arc: (%i)%f -> (%i)%f\n", head->index, head->weight, head->index, head->weight); for(edge = arc->edges.first; edge ; edge = edge->next) { @@ -236,8 +241,9 @@ void printArc(ReebArc *arc) } } -void freeArc(ReebArc *arc) +void REEB_freeArc(BArc *barc) { + ReebArc *arc = (ReebArc*)barc; BLI_freelistN(&arc->edges); if (arc->buckets) @@ -270,7 +276,7 @@ void REEB_freeGraph(ReebGraph *rg) while( arc ) { ReebArc *next = arc->next; - freeArc(arc); + REEB_freeArc((BArc*)arc); arc = next; } @@ -282,8 +288,8 @@ void REEB_freeGraph(ReebGraph *rg) void repositionNodes(ReebGraph *rg) { - ReebArc *arc = NULL; - ReebNode *node = NULL; + BArc *arc = NULL; + BNode *node = NULL; // Reset node positions for(node = rg->nodes.first; node; node = node->next) @@ -293,17 +299,17 @@ void repositionNodes(ReebGraph *rg) for(arc = rg->arcs.first; arc; arc = arc->next) { - if (arc->bcount > 0) + if (((ReebArc*)arc)->bcount > 0) { float p[3]; - VECCOPY(p, arc->buckets[0].p); - VecMulf(p, 1.0f / arc->v1->degree); - VecAddf(arc->v1->p, arc->v1->p, p); + VECCOPY(p, ((ReebArc*)arc)->buckets[0].p); + VecMulf(p, 1.0f / arc->head->degree); + VecAddf(arc->head->p, arc->head->p, p); - VECCOPY(p, arc->buckets[arc->bcount - 1].p); - VecMulf(p, 1.0f / arc->v2->degree); - VecAddf(arc->v2->p, arc->v2->p, p); + VECCOPY(p, ((ReebArc*)arc)->buckets[((ReebArc*)arc)->bcount - 1].p); + VecMulf(p, 1.0f / arc->tail->degree); + VecAddf(arc->tail->p, arc->tail->p, p); } } } @@ -319,7 +325,7 @@ void verifyNodeDegree(ReebGraph *rg) int count = 0; for(arc = rg->arcs.first; arc; arc = arc->next) { - if (arc->v1 == node || arc->v2 == node) + if (arc->head == node || arc->tail == node) { count++; } @@ -338,6 +344,9 @@ void verifyBuckets(ReebGraph *rg) ReebArc *arc = NULL; for(arc = rg->arcs.first; arc; arc = arc->next) { + ReebNode *head = (ReebNode*)arc->head; + ReebNode *tail = (ReebNode*)arc->tail; + if (arc->bcount > 0) { int i; @@ -350,15 +359,15 @@ void verifyBuckets(ReebGraph *rg) } } - if (ceil(arc->v1->weight) < arc->buckets[0].val) + if (ceil(head->weight) < arc->buckets[0].val) { printArc(arc); - printf("alloc error in first bucket: %f should be %f \n", arc->buckets[0].val, ceil(arc->v1->weight)); + printf("alloc error in first bucket: %f should be %f \n", arc->buckets[0].val, ceil(head->weight)); } - if (floor(arc->v2->weight) < arc->buckets[arc->bcount - 1].val) + if (floor(tail->weight) < arc->buckets[arc->bcount - 1].val) { printArc(arc); - printf("alloc error in last bucket: %f should be %f \n", arc->buckets[arc->bcount - 1].val, floor(arc->v2->weight)); + printf("alloc error in last bucket: %f should be %f \n", arc->buckets[arc->bcount - 1].val, floor(tail->weight)); } } } @@ -380,677 +389,201 @@ void verifyFaces(ReebGraph *rg) /**************************************** SYMMETRY HANDLING ******************************************/ -void markdownSymmetryArc(ReebArc *arc, ReebNode *node, int level); - -static void mirrorAlongAxis(float v[3], float center[3], float axis[3]) -{ - float dv[3], pv[3]; - - VecSubf(dv, v, center); - Projf(pv, dv, axis); - VecMulf(pv, -2); - VecAddf(v, v, pv); -} - -/* Helper structure for radial symmetry */ -typedef struct RadialArc -{ - ReebArc *arc; - float n[3]; /* normalized vector joining the nodes of the arc */ -} RadialArc; - -void reestablishRadialSymmetry(ReebNode *node, int depth, float axis[3], int reestablish) +void REEB_RadialSymmetry(BNode* root_node, RadialArc* ring, int count) { - RadialArc *ring = NULL; - RadialArc *unit; - float limit = G.scene->toolsettings->skgen_symmetry_limit; - int symmetric = 1; - int count = 0; + ReebNode *node = (ReebNode*)root_node; + float axis[3]; int i; - - /* mark topological symmetry */ - node->symmetry_flag |= SYM_TOPOLOGICAL; - - /* count the number of arcs in the symmetry ring */ - for (i = 0; node->arcs[i] != NULL; i++) - { - ReebArc *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; node->arcs[i] != NULL; i++) - { - ReebArc *connectedArc = node->arcs[i]; - - /* depth is store as a negative in flag. symmetry level is positive */ - if (connectedArc->symmetry_level == -depth) - { - ReebNode *otherNode = OTHER_NODE(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 */ + + VECCOPY(axis, root_node->symmetry_axis); + + /* first pass, merge incrementally */ for (i = 0; i < count - 1; i++) { - float minAngle = 3; /* arbitrary high value, higher than 2, at least */ - int minIndex = -1; - int j; - - for (j = i + 1; j < count; j++) - { - float angle = Inpf(ring[i].n, ring[j].n); - - /* map negative values to 1..2 */ - if (angle < 0) - { - angle = 1 - angle; - } - - if (angle < minAngle) - { - minIndex = j; - minAngle = angle; - } - } - - /* swap if needed */ - if (minIndex != i + 1) - { - RadialArc tmp; - tmp = ring[i + 1]; - ring[i + 1] = ring[minIndex]; - ring[minIndex] = tmp; - } - } - - for (i = 0; i < count && symmetric; i++) - { ReebNode *node1, *node2; + ReebArc *arc1, *arc2; float tangent[3]; float normal[3]; - float p[3]; - int j = (i + 1) % count; /* next arc in the circular list */ + int j = i + 1; VecAddf(tangent, ring[i].n, ring[j].n); Crossf(normal, tangent, axis); - node1 = OTHER_NODE(ring[i].arc, node); - node2 = OTHER_NODE(ring[j].arc, node); - - VECCOPY(p, node2->p); - mirrorAlongAxis(p, node->p, normal); + node1 = (ReebNode*)BLI_otherNode(ring[i].arc, root_node); + node2 = (ReebNode*)BLI_otherNode(ring[j].arc, root_node); - /* check if it's within limit before continuing */ - if (VecLenf(node1->p, p) > limit) - { - symmetric = 0; - } - - } + arc1 = (ReebArc*)ring[i].arc; + arc2 = (ReebArc*)ring[j].arc; - if (symmetric) - { - /* mark node as symmetric physically */ - VECCOPY(node->symmetry_axis, axis); - node->symmetry_flag |= SYM_PHYSICAL; - node->symmetry_flag |= SYM_RADIAL; + /* mirror first node and mix with the second */ + BLI_mirrorAlongAxis(node1->p, root_node->p, normal); + VecLerpf(node2->p, node2->p, node1->p, 1.0f / (j + 1)); - /* reestablish symmetry only if wanted */ - if (reestablish) + /* Merge buckets + * there shouldn't be any null arcs here, but just to be safe + * */ + if (arc1->bcount > 0 && arc2->bcount > 0) { - /* first pass, merge incrementally */ - for (i = 0; i < count - 1; i++) - { - ReebNode *node1, *node2; - float tangent[3]; - float normal[3]; - int j = i + 1; - - VecAddf(tangent, ring[i].n, ring[j].n); - Crossf(normal, tangent, axis); - - node1 = OTHER_NODE(ring[i].arc, node); - node2 = OTHER_NODE(ring[j].arc, node); - - /* mirror first node and mix with the second */ - mirrorAlongAxis(node1->p, node->p, normal); - VecLerpf(node2->p, node2->p, node1->p, 1.0f / (j + 1)); - - /* Merge buckets - * there shouldn't be any null arcs here, but just to be safe - * */ - if (ring[i].arc->bcount > 0 && ring[j].arc->bcount > 0) - { - ReebArcIterator iter1, iter2; - EmbedBucket *bucket1 = NULL, *bucket2 = NULL; - - initArcIterator(&iter1, ring[i].arc, node); - initArcIterator(&iter2, ring[j].arc, node); - - bucket1 = nextBucket(&iter1); - bucket2 = nextBucket(&iter2); - - /* Make sure they both start at the same value */ - while(bucket1 && bucket1->val < bucket2->val) - { - bucket1 = nextBucket(&iter1); - } - - while(bucket2 && bucket2->val < bucket1->val) - { - bucket2 = nextBucket(&iter2); - } + ReebArcIterator iter1, iter2; + EmbedBucket *bucket1 = NULL, *bucket2 = NULL; + initArcIterator(&iter1, arc1, (ReebNode*)root_node); + initArcIterator(&iter2, arc2, (ReebNode*)root_node); - for ( ;bucket1 && bucket2; bucket1 = nextBucket(&iter1), bucket2 = nextBucket(&iter2)) - { - bucket2->nv += bucket1->nv; /* add counts */ - - /* mirror on axis */ - mirrorAlongAxis(bucket1->p, node->p, normal); - /* add bucket2 in bucket1 */ - VecLerpf(bucket2->p, bucket2->p, bucket1->p, (float)bucket1->nv / (float)(bucket2->nv)); - } - } - } - - /* second pass, mirror back on previous arcs */ - for (i = count - 1; i > 0; i--) - { - ReebNode *node1, *node2; - float tangent[3]; - float normal[3]; - int j = i - 1; - - VecAddf(tangent, ring[i].n, ring[j].n); - Crossf(normal, tangent, axis); - - node1 = OTHER_NODE(ring[i].arc, node); - node2 = OTHER_NODE(ring[j].arc, node); - - /* copy first node than mirror */ - VECCOPY(node2->p, node1->p); - mirrorAlongAxis(node2->p, node->p, normal); - - /* Copy buckets - * there shouldn't be any null arcs here, but just to be safe - * */ - if (ring[i].arc->bcount > 0 && ring[j].arc->bcount > 0) - { - ReebArcIterator iter1, iter2; - EmbedBucket *bucket1 = NULL, *bucket2 = NULL; - - initArcIterator(&iter1, ring[i].arc, node); - initArcIterator(&iter2, ring[j].arc, node); - - bucket1 = nextBucket(&iter1); - bucket2 = nextBucket(&iter2); - - /* Make sure they both start at the same value */ - while(bucket1 && bucket1->val < bucket2->val) - { - bucket1 = nextBucket(&iter1); - } - - while(bucket2 && bucket2->val < bucket1->val) - { - bucket2 = nextBucket(&iter2); - } - - - for ( ;bucket1 && bucket2; bucket1 = nextBucket(&iter1), bucket2 = nextBucket(&iter2)) - { - /* copy and mirror back to bucket2 */ - bucket2->nv = bucket1->nv; - VECCOPY(bucket2->p, bucket1->p); - mirrorAlongAxis(bucket2->p, node->p, normal); - } - } - } - } - } - - MEM_freeN(ring); -} - -static void setSideAxialSymmetry(ReebNode *root_node, ReebNode *end_node, ReebArc *arc) -{ - float vec[3]; - - VecSubf(vec, end_node->p, root_node->p); - - if (Inpf(vec, root_node->symmetry_axis) < 0) - { - arc->symmetry_flag |= SYM_SIDE_NEGATIVE; - } - else - { - arc->symmetry_flag |= SYM_SIDE_POSITIVE; - } -} - -void reestablishAxialSymmetry(ReebNode *node, int depth, float axis[3], int reestablish) -{ - ReebArc *arc1 = NULL; - ReebArc *arc2 = NULL; - ReebNode *node1 = NULL, *node2 = NULL; - float limit = G.scene->toolsettings->skgen_symmetry_limit; - float nor[3], vec[3], p[3]; - int i; - - /* mark topological symmetry */ - node->symmetry_flag |= SYM_TOPOLOGICAL; - - for (i = 0; node->arcs[i] != NULL; i++) - { - ReebArc *connectedArc = node->arcs[i]; + bucket1 = nextBucket(&iter1); + bucket2 = nextBucket(&iter2); - /* depth is store as a negative in flag. symmetry level is positive */ - if (connectedArc->symmetry_level == -depth) - { - if (arc1 == NULL) + /* Make sure they both start at the same value */ + while(bucket1 && bucket1->val < bucket2->val) { - arc1 = connectedArc; - node1 = OTHER_NODE(arc1, node); + bucket1 = nextBucket(&iter1); } - else + + while(bucket2 && bucket2->val < bucket1->val) { - arc2 = connectedArc; - node2 = OTHER_NODE(arc2, node); - break; /* Can stop now, the two arcs have been found */ + bucket2 = nextBucket(&iter2); } - } - } - - /* shouldn't happen, but just to be sure */ - if (node1 == NULL || node2 == NULL) - { - 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); - - printvecf("p", p); - printvecf("axis", axis); - printvecf("vec", vec); - printvecf("nor", nor); - /* mirror node2 along axis */ - VECCOPY(p, node2->p); - mirrorAlongAxis(p, node->p, nor); - /* 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); - - /* reestablish symmetry only if wanted */ - if (reestablish) - { - /* average with node1 */ - VecAddf(node1->p, node1->p, p); - VecMulf(node1->p, 0.5f); - - /* mirror back on node2 */ - VECCOPY(node2->p, node1->p); - mirrorAlongAxis(node2->p, node->p, nor); - - /* Merge buckets - * there shouldn't be any null arcs here, but just to be safe - * */ - if (arc1->bcount > 0 && arc2->bcount > 0) + for ( ;bucket1 && bucket2; bucket1 = nextBucket(&iter1), bucket2 = nextBucket(&iter2)) { - ReebArcIterator iter1, iter2; - EmbedBucket *bucket1 = NULL, *bucket2 = NULL; - - initArcIterator(&iter1, arc1, node); - initArcIterator(&iter2, arc2, node); + bucket2->nv += bucket1->nv; /* add counts */ - bucket1 = nextBucket(&iter1); - bucket2 = nextBucket(&iter2); - - /* Make sure they both start at the same value */ - while(bucket1 && bucket1->val < bucket2->val) - { - bucket1 = nextBucket(&iter1); - } - - while(bucket2 && bucket2->val < bucket1->val) - { - bucket2 = nextBucket(&iter2); - } - - - for ( ;bucket1 && bucket2; bucket1 = nextBucket(&iter1), bucket2 = nextBucket(&iter2)) - { - bucket1->nv += bucket2->nv; /* add counts */ - - /* mirror on axis */ - mirrorAlongAxis(bucket2->p, node->p, nor); - /* add bucket2 in bucket1 */ - VecLerpf(bucket1->p, bucket1->p, bucket2->p, (float)bucket2->nv / (float)(bucket1->nv)); - - /* copy and mirror back to bucket2 */ - bucket2->nv = bucket1->nv; - VECCOPY(bucket2->p, bucket1->p); - mirrorAlongAxis(bucket2->p, node->p, nor); - } + /* mirror on axis */ + BLI_mirrorAlongAxis(bucket1->p, root_node->p, normal); + /* add bucket2 in bucket1 */ + VecLerpf(bucket2->p, bucket2->p, bucket1->p, (float)bucket1->nv / (float)(bucket2->nv)); } } } - else + + /* second pass, mirror back on previous arcs */ + for (i = count - 1; i > 0; i--) { - printf("NOT SYMMETRIC!\n"); - printf("%f <= %f\n", VecLenf(node1->p, p), limit); - printvecf("axis", nor); - } -} - -void markdownSecondarySymmetry(ReebNode *node, int depth, int level) -{ - float axis[3] = {0, 0, 0}; - int count = 0; - int i; - /* Only reestablish spatial symmetry if needed */ - int reestablish = G.scene->toolsettings->skgen_options & SKGEN_SYMMETRY; + ReebNode *node1, *node2; + ReebArc *arc1, *arc2; + float tangent[3]; + float normal[3]; + int j = i - 1; - /* count the number of branches in this symmetry group - * and determinte the axis of symmetry - * */ - for (i = 0; node->arcs[i] != NULL; i++) - { - ReebArc *connectedArc = node->arcs[i]; + VecAddf(tangent, ring[i].n, ring[j].n); + Crossf(normal, tangent, axis); - /* depth is store as a negative in flag. symmetry level is positive */ - if (connectedArc->symmetry_level == -depth) - { - count++; - } - /* If arc is on the axis */ - else if (connectedArc->symmetry_level == level) - { - VecAddf(axis, axis, connectedArc->v1->p); - VecSubf(axis, axis, connectedArc->v2->p); - } - } - - Normalize(axis); - - /* Split between axial and radial symmetry */ - if (count == 2) - { - reestablishAxialSymmetry(node, depth, axis, reestablish); - } - else - { - reestablishRadialSymmetry(node, depth, axis, reestablish); - } - - /* markdown secondary symetries */ - for (i = 0; node->arcs[i] != NULL; i++) - { - ReebArc *connectedArc = node->arcs[i]; + node1 = (ReebNode*)BLI_otherNode(ring[i].arc, root_node); + node2 = (ReebNode*)BLI_otherNode(ring[j].arc, root_node); - if (connectedArc->symmetry_level == -depth) - { - /* markdown symmetry for branches corresponding to the depth */ - markdownSymmetryArc(connectedArc, node, level + 1); - } - } -} + arc1 = (ReebArc*)ring[i].arc; + arc2 = (ReebArc*)ring[j].arc; -void markdownSymmetryArc(ReebArc *arc, ReebNode *node, int level) -{ - int i; - arc->symmetry_level = level; - - node = OTHER_NODE(arc, node); - - for (i = 0; node->arcs[i] != NULL; i++) - { - ReebArc *connectedArc = node->arcs[i]; + /* copy first node than mirror */ + VECCOPY(node2->p, node1->p); + BLI_mirrorAlongAxis(node2->p, root_node->p, normal); - if (connectedArc != arc) + /* Copy buckets + * there shouldn't be any null arcs here, but just to be safe + * */ + if (arc1->bcount > 0 && arc2->bcount > 0) { - ReebNode *connectedNode = OTHER_NODE(connectedArc, node); + ReebArcIterator iter1, iter2; + EmbedBucket *bucket1 = NULL, *bucket2 = NULL; - /* symmetry level is positive value, negative values is subtree depth */ - connectedArc->symmetry_level = -subtreeDepth(connectedNode, connectedArc); - } - } - - arc = NULL; - - for (i = 0; node->arcs[i] != NULL; i++) - { - int issymmetryAxis = 0; - ReebArc *connectedArc = node->arcs[i]; - - /* only arcs not already marked as symetric */ - if (connectedArc->symmetry_level < 0) - { - int j; - - /* true by default */ - issymmetryAxis = 1; + initArcIterator(&iter1, arc1, node); + initArcIterator(&iter2, arc2, node); - for (j = 0; node->arcs[j] != NULL && issymmetryAxis == 1; j++) - { - ReebArc *otherArc = node->arcs[j]; - - /* different arc, same depth */ - if (otherArc != connectedArc && otherArc->symmetry_level == connectedArc->symmetry_level) - { - /* not on the symmetry axis */ - issymmetryAxis = 0; - } - } - } + bucket1 = nextBucket(&iter1); + bucket2 = nextBucket(&iter2); - /* arc could be on the symmetry axis */ - if (issymmetryAxis == 1) - { - /* no arc as been marked previously, keep this one */ - if (arc == NULL) + /* Make sure they both start at the same value */ + while(bucket1 && bucket1->val < bucket2->val) { - arc = connectedArc; + bucket1 = nextBucket(&iter1); } - else + + while(bucket2 && bucket2->val < bucket1->val) { - /* there can't be more than one symmetry arc */ - arc = NULL; - break; + bucket2 = nextBucket(&iter2); } - } - } - - /* go down the arc continuing the symmetry axis */ - if (arc) - { - markdownSymmetryArc(arc, node, level); - } - - /* secondary symmetry */ - for (i = 0; node->arcs[i] != NULL; i++) - { - ReebArc *connectedArc = node->arcs[i]; - - /* only arcs not already marked as symetric and is not the next arc on the symmetry axis */ - if (connectedArc->symmetry_level < 0) - { - /* subtree depth is store as a negative value in the flag */ - markdownSecondarySymmetry(node, -connectedArc->symmetry_level, level); - } - } -} - -void markdownSymmetry(ReebGraph *rg) -{ - ReebNode *node; - ReebArc *arc; - /* only for Acyclic graphs */ - int cyclic = isGraphCyclic(rg); - - /* mark down all arcs as non-symetric */ - for (arc = rg->arcs.first; arc; arc = arc->next) - { - arc->symmetry_level = 0; - } - - /* mark down all nodes as not on the symmetry axis */ - for (node = rg->nodes.first; node; node = node->next) - { - node->symmetry_level = 0; - } - - /* node list is sorted, so lowest node is always the head (by design) */ - node = rg->nodes.first; - /* only work on acyclic graphs and if only one arc is incident on the first node */ - if (cyclic == 0 && countConnectedArcs(rg, node) == 1) - { - arc = node->arcs[0]; - - markdownSymmetryArc(arc, node, 1); - - /* mark down non-symetric arcs */ - for (arc = rg->arcs.first; arc; arc = arc->next) - { - if (arc->symmetry_level < 0) + for ( ;bucket1 && bucket2; bucket1 = nextBucket(&iter1), bucket2 = nextBucket(&iter2)) { - arc->symmetry_level = 0; - } - else - { - /* mark down nodes with the lowest level symmetry axis */ - if (arc->v1->symmetry_level == 0 || arc->v1->symmetry_level > arc->symmetry_level) - { - arc->v1->symmetry_level = arc->symmetry_level; - } - if (arc->v2->symmetry_level == 0 || arc->v2->symmetry_level > arc->symmetry_level) - { - arc->v2->symmetry_level = arc->symmetry_level; - } + /* copy and mirror back to bucket2 */ + bucket2->nv = bucket1->nv; + VECCOPY(bucket2->p, bucket1->p); + BLI_mirrorAlongAxis(bucket2->p, node->p, normal); } } } } -/************************************** ADJACENCY LIST *************************************************/ - -static void addArcToNodeAdjacencyList(ReebNode *node, ReebArc *arc) +void REEB_AxialSymmetry(BNode* root_node, BNode* node1, BNode* node2, struct BArc* barc1, BArc* barc2) { - ReebArc **arclist; + ReebArc *arc1, *arc2; + float nor[3], p[3]; - for(arclist = node->arcs; *arclist; arclist++) - { } - - *arclist = arc; -} + arc1 = (ReebArc*)barc1; + arc2 = (ReebArc*)barc2; -void buildAdjacencyList(ReebGraph *rg) -{ - ReebNode *node = NULL; - ReebArc *arc = NULL; + VECCOPY(nor, root_node->symmetry_axis); + + /* mirror node2 along axis */ + VECCOPY(p, node2->p); + BLI_mirrorAlongAxis(p, root_node->p, nor); - for(node = rg->nodes.first; node; node = node->next) + /* average with node1 */ + VecAddf(node1->p, node1->p, p); + VecMulf(node1->p, 0.5f); + + /* mirror back on node2 */ + VECCOPY(node2->p, node1->p); + BLI_mirrorAlongAxis(node2->p, root_node->p, nor); + + /* Merge buckets + * there shouldn't be any null arcs here, but just to be safe + * */ + if (arc1->bcount > 0 && arc2->bcount > 0) { - if (node->arcs != NULL) - { - MEM_freeN(node->arcs); - } + ReebArcIterator iter1, iter2; + EmbedBucket *bucket1 = NULL, *bucket2 = NULL; - node->arcs = MEM_callocN((node->degree + 1) * sizeof(ReebArc*), "adjacency list"); - } - - for(arc = rg->arcs.first; arc; arc= arc->next) - { - addArcToNodeAdjacencyList(arc->v1, arc); - addArcToNodeAdjacencyList(arc->v2, arc); - } -} - -int hasAdjacencyList(ReebGraph *rg) -{ - ReebNode *node; + initArcIterator(&iter1, arc1, (ReebNode*)root_node); + initArcIterator(&iter2, arc2, (ReebNode*)root_node); + + bucket1 = nextBucket(&iter1); + bucket2 = nextBucket(&iter2); - for(node = rg->nodes.first; node; node = node->next) - { - if (node->arcs == NULL) + /* Make sure they both start at the same value */ + while(bucket1 && bucket1->val < bucket2->val) { - return 0; + bucket1 = nextBucket(&iter1); } - } - - return 1; -} - -int countConnectedArcs(ReebGraph *rg, ReebNode *node) -{ - int count = 0; - - /* use adjacency list if present */ - if (node->arcs) - { - ReebArc **arcs; - - for(arcs = node->arcs; *arcs; arcs++) + + while(bucket2 && bucket2->val < bucket1->val) { - count++; + bucket2 = nextBucket(&iter2); } - } - else - { - ReebArc *arc; - for(arc = rg->arcs.first; arc; arc = arc->next) + + + for ( ;bucket1 && bucket2; bucket1 = nextBucket(&iter1), bucket2 = nextBucket(&iter2)) { - if (arc->v1 == node || arc->v2 == node) - { - count++; - } + bucket1->nv += bucket2->nv; /* add counts */ + + /* mirror on axis */ + BLI_mirrorAlongAxis(bucket2->p, root_node->p, nor); + /* add bucket2 in bucket1 */ + VecLerpf(bucket1->p, bucket1->p, bucket2->p, (float)bucket2->nv / (float)(bucket1->nv)); + + /* copy and mirror back to bucket2 */ + bucket2->nv = bucket1->nv; + VECCOPY(bucket2->p, bucket1->p); + BLI_mirrorAlongAxis(bucket2->p, root_node->p, nor); } } - - return count; } +/************************************** ADJACENCY LIST *************************************************/ + + /****************************************** SMOOTHING **************************************************/ void postprocessGraph(ReebGraph *rg, char mode) @@ -1120,12 +653,14 @@ int compareArcsWeight(void *varc1, void *varc2) { ReebArc *arc1 = (ReebArc*)varc1; ReebArc *arc2 = (ReebArc*)varc2; + ReebNode *node1 = (ReebNode*)arc1->head; + ReebNode *node2 = (ReebNode*)arc2->head; - if (arc1->v1->weight < arc2->v1->weight) + if (node1->weight < node2->weight) { return -1; } - if (arc1->v1->weight > arc2->v1->weight) + if (node1->weight > node2->weight) { return 1; } @@ -1142,12 +677,20 @@ void sortArcs(ReebGraph *rg) /****************************************** FILTERING **************************************************/ +float lengthArc(ReebArc *arc) +{ + ReebNode *head = (ReebNode*)arc->head; + ReebNode *tail = (ReebNode*)arc->tail; + + return tail->weight - head->weight; +} + int compareArcs(void *varc1, void *varc2) { ReebArc *arc1 = (ReebArc*)varc1; ReebArc *arc2 = (ReebArc*)varc2; - float len1 = arc1->v2->weight - arc1->v1->weight; - float len2 = arc2->v2->weight - arc2->v1->weight; + float len1 = lengthArc(arc1); + float len2 = lengthArc(arc2); if (len1 < len2) { @@ -1170,9 +713,11 @@ void filterArc(ReebGraph *rg, ReebNode *newNode, ReebNode *removedNode, ReebArc /* 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 (arc->v1 == srcArc->v1 && arc->v2 == srcArc->v2 && arc != srcArc) + if (arc->head == srcArc->head && arc->tail == srcArc->tail && arc != srcArc) { - mergeArcBuckets(srcArc, arc, srcArc->v1->weight, srcArc->v2->weight); + ReebNode *head = (ReebNode*)srcArc->head; + ReebNode *tail = (ReebNode*)srcArc->tail; + mergeArcBuckets(srcArc, arc, head->weight, tail->weight); } } @@ -1182,19 +727,19 @@ void filterArc(ReebGraph *rg, ReebNode *newNode, ReebNode *removedNode, ReebArc { nextArc = arc->next; - if (arc->v1 == removedNode || arc->v2 == removedNode) + if (arc->head == removedNode || arc->tail == removedNode) { - if (arc->v1 == removedNode) + if (arc->head == removedNode) { - arc->v1 = newNode; + arc->head = newNode; } else { - arc->v2 = newNode; + arc->tail = newNode; } // Remove looped arcs - if (arc->v1 == arc->v2) + if (arc->head == arc->tail) { // v1 or v2 was already newNode, since we're removing an arc, decrement degree newNode->degree--; @@ -1203,17 +748,17 @@ void filterArc(ReebGraph *rg, ReebNode *newNode, ReebNode *removedNode, ReebArc if (arc != srcArc) { BLI_remlink(&rg->arcs, arc); - freeArc(arc); + REEB_freeArc((BArc*)arc); } } // Remove flipped arcs - else if (arc->v1->weight > arc->v2->weight) + else if (((ReebNode*)arc->head)->weight > ((ReebNode*)arc->tail)->weight) { // Decrement degree from the other node - OTHER_NODE(arc, newNode)->degree--; + BLI_otherNode((BArc*)arc, (BNode*)newNode)->degree--; BLI_remlink(&rg->arcs, arc); - freeArc(arc); + REEB_freeArc((BArc*)arc); } else { @@ -1222,9 +767,12 @@ void filterArc(ReebGraph *rg, ReebNode *newNode, ReebNode *removedNode, ReebArc if (merging) { + ReebNode *head = (ReebNode*)arc->head; + ReebNode *tail = (ReebNode*)arc->tail; + // resize bucket list resizeArcBuckets(arc); - mergeArcBuckets(arc, srcArc, arc->v1->weight, arc->v2->weight); + mergeArcBuckets(arc, srcArc, head->weight, tail->weight); } } } @@ -1244,8 +792,8 @@ void filterNullReebGraph(ReebGraph *rg) // Only collapse arcs too short to have any embed bucket if (arc->bcount == 0) { - ReebNode *newNode = arc->v1; - ReebNode *removedNode = arc->v2; + ReebNode *newNode = (ReebNode*)arc->head; + ReebNode *removedNode = (ReebNode*)arc->tail; float blend; blend = (float)newNode->degree / (float)(newNode->degree + removedNode->degree); // blending factors @@ -1259,7 +807,7 @@ void filterNullReebGraph(ReebGraph *rg) nextArc = arc->next; BLI_remlink(&rg->arcs, arc); - freeArc(arc); + REEB_freeArc((BArc*)arc); BLI_freelinkN(&rg->nodes, removedNode); } @@ -1281,21 +829,21 @@ int filterInternalReebGraph(ReebGraph *rg, float threshold) nextArc = arc->next; // Only collapse non-terminal arcs that are shorter than threshold - if ((arc->v1->degree > 1 && arc->v2->degree > 1 && arc->v2->weight - arc->v1->weight < threshold)) + if ((arc->head->degree > 1 && arc->tail->degree > 1 && ((ReebNode*)arc->tail)->weight - ((ReebNode*)arc->head)->weight < threshold)) { ReebNode *newNode = NULL; ReebNode *removedNode = NULL; /* Keep the node with the highestn number of connected arcs */ - if (arc->v1->degree >= arc->v2->degree) + if (arc->head->degree >= arc->tail->degree) { - newNode = arc->v1; - removedNode = arc->v2; + newNode = arc->head; + removedNode = arc->tail; } else { - newNode = arc->v2; - removedNode = arc->v1; + newNode = arc->tail; + removedNode = arc->head; } filterArc(rg, newNode, removedNode, arc, 1); @@ -1304,7 +852,7 @@ int filterInternalReebGraph(ReebGraph *rg, float threshold) nextArc = arc->next; BLI_remlink(&rg->arcs, arc); - freeArc(arc); + REEB_freeArc((BArc*)arc); BLI_freelinkN(&rg->nodes, removedNode); value = 1; @@ -1329,7 +877,7 @@ int filterExternalReebGraph(ReebGraph *rg, float threshold) nextArc = arc->next; // Only collapse terminal arcs that are shorter than threshold - if ((arc->v1->degree == 1 || arc->v2->degree == 1) && arc->v2->weight - arc->v1->weight < threshold) + if ((arc->head->degree == 1 || arc->tail->degree == 1) && ((ReebNode*)arc->tail)->weight - ((ReebNode*)arc->head)->weight < threshold) { ReebNode *terminalNode = NULL; ReebNode *middleNode = NULL; @@ -1338,15 +886,15 @@ int filterExternalReebGraph(ReebGraph *rg, float threshold) int merging = 0; // Assign terminal and middle nodes - if (arc->v1->degree == 1) + if (arc->head->degree == 1) { - terminalNode = arc->v1; - middleNode = arc->v2; + terminalNode = arc->head; + middleNode = arc->tail; } else { - terminalNode = arc->v2; - middleNode = arc->v1; + terminalNode = arc->tail; + middleNode = arc->head; } // If middle node is a normal node, merge to terminal node @@ -1379,7 +927,7 @@ int filterExternalReebGraph(ReebGraph *rg, float threshold) nextArc = arc->next; BLI_remlink(&rg->arcs, arc); - freeArc(arc); + REEB_freeArc((BArc*)arc); BLI_freelinkN(&rg->nodes, removedNode); value = 1; @@ -1416,7 +964,7 @@ int filterSmartReebGraph(ReebGraph *rg, float threshold) recalc_editnormals(); // Only test terminal arcs - if (arc->v1->degree == 1 || arc->v2->degree == 1) + if (arc->head->degree == 1 || arc->tail->degree == 1) { GHashIterator ghi; int merging = 0; @@ -1437,7 +985,7 @@ int filterSmartReebGraph(ReebGraph *rg, float threshold) float min_distance = -1; float angle = 0; - initArcIterator(&iter, arc, arc->v1); + initArcIterator(&iter, arc, arc->head); bucket = nextBucket(&iter); @@ -1451,7 +999,7 @@ int filterSmartReebGraph(ReebGraph *rg, float threshold) /* first bucket. Previous is head */ if (previous == NULL) { - vec0 = arc->v1->p; + vec0 = arc->head->p; } /* Previous is a valid bucket */ else @@ -1512,15 +1060,15 @@ int filterSmartReebGraph(ReebGraph *rg, float threshold) int merging = 0; // Assign terminal and middle nodes - if (arc->v1->degree == 1) + if (arc->head->degree == 1) { - terminalNode = arc->v1; - middleNode = arc->v2; + terminalNode = arc->head; + middleNode = arc->tail; } else { - terminalNode = arc->v2; - middleNode = arc->v1; + terminalNode = arc->tail; + middleNode = arc->head; } // If middle node is a normal node, merge to terminal node @@ -1553,7 +1101,7 @@ int filterSmartReebGraph(ReebGraph *rg, float threshold) nextArc = arc->next; BLI_remlink(&rg->arcs, arc); - freeArc(arc); + REEB_freeArc((BArc*)arc); BLI_freelinkN(&rg->nodes, removedNode); value = 1; @@ -1625,94 +1173,6 @@ void spreadWeight(EditMesh *em) MEM_freeN(verts); } -/*********************************** GRAPH AS TREE FUNCTIONS *******************************************/ - -int subtreeDepth(ReebNode *node, ReebArc *rootArc) -{ - int depth = 0; - - /* Base case, no arcs leading away */ - if (node->arcs == NULL || *(node->arcs) == NULL) - { - return 0; - } - else - { - ReebArc ** pArc; - - for(pArc = node->arcs; *pArc; pArc++) - { - ReebArc *arc = *pArc; - - /* only arcs that go down the tree */ - if (arc != rootArc) - { - ReebNode *newNode = OTHER_NODE(arc, node); - depth = MAX2(depth, subtreeDepth(newNode, arc)); - } - } - } - - return depth + 1; -} - -/*************************************** CYCLE DETECTION ***********************************************/ - -int detectCycle(ReebNode *node, ReebArc *srcArc) -{ - int value = 0; - - if (node->flag == 0) - { - ReebArc ** pArc; - - /* mark node as visited */ - node->flag = 1; - - for(pArc = node->arcs; *pArc && value == 0; pArc++) - { - ReebArc *arc = *pArc; - - /* don't go back on the source arc */ - if (arc != srcArc) - { - value = detectCycle(OTHER_NODE(arc, node), arc); - } - } - } - else - { - value = 1; - } - - return value; -} - -int isGraphCyclic(ReebGraph *rg) -{ - ReebNode *node; - int value = 0; - - /* NEED TO CHECK IF ADJACENCY LIST EXIST */ - - /* Mark all nodes as not visited */ - for(node = rg->nodes.first; node; node = node->next) - { - node->flag = 0; - } - - /* detectCycles in subgraphs */ - for(node = rg->nodes.first; node && value == 0; node = node->next) - { - /* only for nodes in subgraphs that haven't been visited yet */ - if (node->flag == 0) - { - value = value || detectCycle(node, NULL); - } - } - - return value; -} /******************************************** EXPORT ***************************************************/ @@ -1742,18 +1202,18 @@ void REEB_exportGraph(ReebGraph *rg, int count) int i; float p[3]; - exportNode(f, "v1", arc->v1); + exportNode(f, "v1", arc->head); for(i = 0; i < arc->bcount; i++) { fprintf(f, "b nv:%i %f %f %f\n", arc->buckets[i].nv, arc->buckets[i].p[0], arc->buckets[i].p[1], arc->buckets[i].p[2]); } - VecAddf(p, arc->v2->p, arc->v1->p); + VecAddf(p, arc->tail->p, arc->head->p); VecMulf(p, 0.5f); fprintf(f, "angle %0.3f %0.3f %0.3f %0.3f %i\n", p[0], p[1], p[2], arc->angle, BLI_ghash_size(arc->faces)); - exportNode(f, "v2", arc->v2); + exportNode(f, "v2", arc->tail); } fclose(f); @@ -1767,7 +1227,7 @@ ReebArc * findConnectedArc(ReebGraph *rg, ReebArc *arc, ReebNode *v) for(nextArc = rg->arcs.first; nextArc; nextArc = nextArc->next) { - if (arc != nextArc && (nextArc->v1 == v || nextArc->v2 == v)) + if (arc != nextArc && (nextArc->head == v || nextArc->tail == v)) { break; } @@ -1784,39 +1244,39 @@ void removeNormalNodes(ReebGraph *rg) // Merge degree 2 nodes for(arc = rg->arcs.first; arc; arc = arc->next) { - while (arc->v1->degree == 2 || arc->v2->degree == 2) + while (arc->head->degree == 2 || arc->tail->degree == 2) { // merge at v1 - if (arc->v1->degree == 2) + if (arc->head->degree == 2) { - ReebArc *nextArc = findConnectedArc(rg, arc, arc->v1); + ReebArc *nextArc = (ReebArc*)BLI_findConnectedArc((BGraph*)rg, (BArc*)arc, (BNode*)arc->head); // Merge arc only if needed - if (arc->v1 == nextArc->v2) + if (arc->head == nextArc->tail) { mergeConnectedArcs(rg, arc, nextArc); } // Otherwise, mark down vert else { - arc->v1->degree = 3; + arc->head->degree = 3; } } // merge at v2 - if (arc->v2->degree == 2) + if (arc->tail->degree == 2) { - ReebArc *nextArc = findConnectedArc(rg, arc, arc->v2); + ReebArc *nextArc = (ReebArc*)BLI_findConnectedArc((BGraph*)rg, (BArc*)arc, (BNode*)arc->tail); // Merge arc only if needed - if (arc->v2 == nextArc->v1) + if (arc->tail == nextArc->head) { mergeConnectedArcs(rg, arc, nextArc); } // Otherwise, mark down vert else { - arc->v2->degree = 3; + arc->tail->degree = 3; } } } @@ -1933,24 +1393,24 @@ int mergeConnectedArcs(ReebGraph *rg, ReebArc *a0, ReebArc *a1) mergeArcFaces(rg, a0, a1); // Bring a0 to the combine length of both arcs - if (a0->v2 == a1->v1) + if (a0->tail == a1->head) { - removedNode = a0->v2; - a0->v2 = a1->v2; + removedNode = a0->tail; + a0->tail = a1->tail; } - else if (a0->v1 == a1->v2) + else if (a0->head == a1->tail) { - removedNode = a0->v1; - a0->v1 = a1->v1; + removedNode = a0->head; + a0->head = a1->head; } resizeArcBuckets(a0); // Merge a1 in a0 - mergeArcBuckets(a0, a1, a0->v1->weight, a0->v2->weight); + mergeArcBuckets(a0, a1, a0->head->weight, a0->tail->weight); // remove a1 from graph BLI_remlink(&rg->arcs, a1); - freeArc(a1); + REEB_freeArc((BArc*)a1); BLI_freelinkN(&rg->nodes, removedNode); result = 1; @@ -1962,36 +1422,36 @@ int mergeArcs(ReebGraph *rg, ReebArc *a0, ReebArc *a1) { int result = 0; // TRIANGLE POINTS DOWN - if (a0->v1->weight == a1->v1->weight) // heads are the same + if (a0->head->weight == a1->head->weight) // heads are the same { - if (a0->v2->weight == a1->v2->weight) // tails also the same, arcs can be totally merge together + if (a0->tail->weight == a1->tail->weight) // tails also the same, arcs can be totally merge together { mergeArcEdges(rg, a0, a1, MERGE_APPEND); mergeArcFaces(rg, a0, a1); - mergeArcBuckets(a0, a1, a0->v1->weight, a0->v2->weight); + mergeArcBuckets(a0, a1, a0->head->weight, a0->tail->weight); // Adjust node degree - a1->v1->degree--; - a1->v2->degree--; + a1->head->degree--; + a1->tail->degree--; // remove a1 from graph BLI_remlink(&rg->arcs, a1); - freeArc(a1); + REEB_freeArc((BArc*)a1); result = 1; } - else if (a0->v2->weight > a1->v2->weight) // a1->v2->weight is in the middle + else if (a0->tail->weight > a1->tail->weight) // a1->tail->weight is in the middle { mergeArcEdges(rg, a1, a0, MERGE_LOWER); mergeArcFaces(rg, a1, a0); // Adjust node degree - a0->v1->degree--; - a1->v2->degree++; + a0->head->degree--; + a1->tail->degree++; - mergeArcBuckets(a1, a0, a1->v1->weight, a1->v2->weight); - a0->v1 = a1->v2; + mergeArcBuckets(a1, a0, a1->head->weight, a1->tail->weight); + a0->head = a1->tail; resizeArcBuckets(a0); } else // a0>n2 is in the middle @@ -2000,41 +1460,41 @@ int mergeArcs(ReebGraph *rg, ReebArc *a0, ReebArc *a1) mergeArcFaces(rg, a0, a1); // Adjust node degree - a1->v1->degree--; - a0->v2->degree++; + a1->head->degree--; + a0->tail->degree++; - mergeArcBuckets(a0, a1, a0->v1->weight, a0->v2->weight); - a1->v1 = a0->v2; + mergeArcBuckets(a0, a1, a0->head->weight, a0->tail->weight); + a1->head = a0->tail; resizeArcBuckets(a1); } } // TRIANGLE POINTS UP - else if (a0->v2->weight == a1->v2->weight) // tails are the same + else if (a0->tail->weight == a1->tail->weight) // tails are the same { - if (a0->v1->weight > a1->v1->weight) // a0->v1->weight is in the middle + if (a0->head->weight > a1->head->weight) // a0->head->weight is in the middle { mergeArcEdges(rg, a0, a1, MERGE_HIGHER); mergeArcFaces(rg, a0, a1); // Adjust node degree - a1->v2->degree--; - a0->v1->degree++; + a1->tail->degree--; + a0->head->degree++; - mergeArcBuckets(a0, a1, a0->v1->weight, a0->v2->weight); - a1->v2 = a0->v1; + mergeArcBuckets(a0, a1, a0->head->weight, a0->tail->weight); + a1->tail = a0->head; resizeArcBuckets(a1); } - else // a1->v1->weight is in the middle + else // a1->head->weight is in the middle { mergeArcEdges(rg, a1, a0, MERGE_HIGHER); mergeArcFaces(rg, a1, a0); // Adjust node degree - a0->v2->degree--; - a1->v1->degree++; + a0->tail->degree--; + a1->head->degree++; - mergeArcBuckets(a1, a0, a1->v1->weight, a1->v2->weight); - a0->v2 = a1->v1; + mergeArcBuckets(a1, a0, a1->head->weight, a1->tail->weight); + a0->tail = a1->head; resizeArcBuckets(a0); } } @@ -2055,7 +1515,7 @@ void glueByMergeSort(ReebGraph *rg, ReebArc *a0, ReebArc *a1, ReebEdge *e0, Reeb if (total == 0) // if it wasn't a total merge, go forward { - if (a0->v2->weight < a1->v2->weight) + if (a0->tail->weight < a1->tail->weight) { a0 = nextArcMappedToEdge(a0, e0); } @@ -2130,8 +1590,8 @@ ReebEdge * createArc(ReebGraph *rg, ReebNode *node1, ReebNode *node2) v2 = node1; } - arc->v1 = v1; - arc->v2 = v2; + arc->head = v1; + arc->tail = v2; // increase node degree v1->degree++; @@ -2150,8 +1610,8 @@ ReebEdge * createArc(ReebGraph *rg, ReebNode *node1, ReebNode *node2) /* adding buckets for embedding */ allocArcBuckets(arc); - offset = arc->v1->weight; - len = arc->v2->weight - arc->v1->weight; + offset = arc->head->weight; + len = arc->tail->weight - arc->head->weight; #if 0 /* This is the actual embedding filling described in the paper @@ -2159,8 +1619,8 @@ ReebEdge * createArc(ReebGraph *rg, ReebNode *node1, ReebNode *node2) */ if (arc->bcount > 0) { - addVertToBucket(&(arc->buckets[0]), arc->v1->co); - addVertToBucket(&(arc->buckets[arc->bcount - 1]), arc->v2->co); + addVertToBucket(&(arc->buckets[0]), arc->head->co); + addVertToBucket(&(arc->buckets[arc->bcount - 1]), arc->tail->co); } #else for(i = 0; i < arc->bcount; i++) @@ -2239,6 +1699,12 @@ ReebGraph * newReebGraph() rg->totnodes = 0; rg->emap = BLI_edgehash_new(); + + rg->free_arc = REEB_freeArc; + rg->free_node = NULL; + rg->radial_symmetry = REEB_RadialSymmetry; + rg->axial_symmetry = REEB_AxialSymmetry; + return rg; } @@ -2282,29 +1748,30 @@ ReebGraph * generateReebGraph(EditMesh *em, int subdivisions) /* Adding face, edge per edge */ for(efa = em->faces.first; efa; efa = efa->next) { - ReebNode *n1, *n2, *n3; - - n1 = (ReebNode*)BLI_dlist_find_link(dlist, efa->v1->hash); - n2 = (ReebNode*)BLI_dlist_find_link(dlist, efa->v2->hash); - n3 = (ReebNode*)BLI_dlist_find_link(dlist, efa->v3->hash); - - addTriangleToGraph(rg, n1, n2, n3, efa); - - if (efa->v4) + if (efa->h == 0) { - ReebNode *n4 = (ReebNode*)efa->v4->tmp.p; - addTriangleToGraph(rg, n1, n3, n4, efa); - } - + ReebNode *n1, *n2, *n3; + + n1 = (ReebNode*)BLI_dlist_find_link(dlist, efa->v1->hash); + n2 = (ReebNode*)BLI_dlist_find_link(dlist, efa->v2->hash); + n3 = (ReebNode*)BLI_dlist_find_link(dlist, efa->v3->hash); + + addTriangleToGraph(rg, n1, n2, n3, efa); + + if (efa->v4) + { + ReebNode *n4 = (ReebNode*)efa->v4->tmp.p; + addTriangleToGraph(rg, n1, n3, n4, efa); + } #ifdef DEBUG_REEB - countfaces++; - if (countfaces % 100 == 0) - { - printf("face %i of %i\n", countfaces, totfaces); - verifyFaces(rg); - } + countfaces++; + if (countfaces % 100 == 0) + { + printf("face %i of %i\n", countfaces, totfaces); + verifyFaces(rg); + } #endif - + } } BLI_listbase_from_dlist(dlist, &rg->nodes); @@ -2543,7 +2010,7 @@ EditEdge * NextEdgeForVert(EditMesh *em, EditVert *v) for( ; e ; e = e->next) { - if (e->v1 == v || e->v2 == v) + if ((e->v1 == v || e->v2 == v) && (e->h == 0)) { break; } @@ -2850,7 +2317,7 @@ void initArcIterator(ReebArcIterator *iter, ReebArc *arc, ReebNode *head) { iter->arc = arc; - if (head == arc->v1) + if (head == arc->head) { iter->start = 0; iter->end = arc->bcount - 1; @@ -2870,7 +2337,7 @@ void initArcIteratorStart(struct ReebArcIterator *iter, struct ReebArc *arc, str { iter->arc = arc; - if (head == arc->v1) + if (head == arc->head) { iter->start = start; iter->end = arc->bcount - 1; @@ -3011,6 +2478,8 @@ ReebGraph *BIF_ReebGraphFromEditMesh(void) rg = generateReebGraph(em, G.scene->toolsettings->skgen_resolution); + REEB_exportGraph(rg, -1); + verifyBuckets(rg); verifyFaces(rg); @@ -3062,7 +2531,7 @@ ReebGraph *BIF_ReebGraphFromEditMesh(void) postprocessGraph(rg, G.scene->toolsettings->skgen_postpro); } - buildAdjacencyList(rg); + BLI_buildAdjacencyList((BGraph*)rg); sortNodes(rg); |