[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15026] branches/harmonic-skeleton/source/ blender: Generalizing the graph code used for Reeb graphs and Rig (Armature ) graphs

Martin Poirier theeth at yahoo.com
Wed May 28 18:39:06 CEST 2008


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. @@




More information about the Bf-blender-cvs mailing list