Generalizing the graph code used for Reeb graphs and Rig (Armature) graphs

Removing a lot of duplicated code

1 files changed, 102 insertions, 0 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_*/