Revision: 15026
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15026
Author: theeth
Date: 2008-05-28 18:39:05 +0200 (Wed, 28 May 2008)
Log Message:
-----------
Generalizing the graph code used for Reeb graphs and Rig (Armature) graphs
Removing a lot of duplicated code
Modified Paths:
--------------
branches/harmonic-skeleton/source/blender/include/reeb.h
branches/harmonic-skeleton/source/blender/src/autoarmature.c
branches/harmonic-skeleton/source/blender/src/editarmature.c
branches/harmonic-skeleton/source/blender/src/reeb.c
Added Paths:
-----------
branches/harmonic-skeleton/source/blender/blenlib/BLI_graph.h
branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c
Added: branches/harmonic-skeleton/source/blender/blenlib/BLI_graph.h
===================================================================
--- branches/harmonic-skeleton/source/blender/blenlib/BLI_graph.h
(rev 0)
+++ branches/harmonic-skeleton/source/blender/blenlib/BLI_graph.h
2008-05-28 16:39:05 UTC (rev 15026)
@@ -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_*/
Added: branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c
===================================================================
--- branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c
(rev 0)
+++ branches/harmonic-skeleton/source/blender/blenlib/intern/graph.c
2008-05-28 16:39:05 UTC (rev 15026)
@@ -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)
+ {
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
