8 files changed, 1412 insertions, 8 deletions

diff --git a/source/blender/blenlib/BLI_arithb.h b/source/blender/blenlib/BLI_arithb.h
index e2e71a2fb1a..e4b983d9ba3 100644
--- a/source/blender/blenlib/BLI_arithb.h
+++ b/source/blender/blenlib/BLI_arithb.h
@@ -245,6 +245,7 @@ void VecMulf(float *v1, float f);
 int VecLenCompare(float *v1, float *v2, float limit);
 int VecCompare(float *v1, float *v2, float limit);
 int VecEqual(float *v1, float *v2);
+int VecIsNull(float *v);
 
 void printvecf(char *str,float v[3]);
 void printvec4f(char *str, float v[4]);
@@ -265,6 +266,7 @@ void Vec2Copyf(float *v1, float *v2);
 void Vec2Lerpf(float *target, float *a, float *b, float t);
 
 void AxisAngleToQuat(float *q, float *axis, float angle);
+void RotationBetweenVectorsToQuat(float *q, float v1[3], float v2[3]);
 void vectoquat(float *vec, short axis, short upflag, float *q);
 
 float VecAngle2(float *v1, float *v2);
diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h
index aec77f5f385..c77e82f0a2b 100644
--- a/source/blender/blenlib/BLI_ghash.h
+++ b/source/blender/blenlib/BLI_ghash.h
@@ -34,7 +34,12 @@
 
 struct GHash;
 typedef struct GHash GHash;
-typedef struct GHashIterator GHashIterator;
+
+typedef struct GHashIterator {
+	GHash *gh;
+	int curBucket;
+	struct Entry *curEntry;
+} GHashIterator;
 
 typedef unsigned int	(*GHashHashFP)		(void *key);
 typedef int				(*GHashCmpFP)		(void *a, void *b);
@@ -63,6 +68,15 @@ int		BLI_ghash_size		(GHash *gh);
 	 */
 GHashIterator*	BLI_ghashIterator_new		(GHash *gh);
 	/**
+	 * Init an already allocated GHashIterator. The hash table must not
+	 * be mutated while the iterator is in use, and the iterator will
+	 * step exactly BLI_ghash_size(gh) times before becoming done.
+	 * 
+	 * @param ghi The GHashIterator to initialize.
+	 * @param gh The GHash to iterate over.
+	 */
+void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh);
+	/**
 	 * Free a GHashIterator.
 	 *
 	 * @param ghi The iterator to free.
diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h
new file mode 100644
index 00000000000..160c2e04cf5
--- /dev/null
+++ b/source/blender/blenlib/BLI_graph.h
@@ -0,0 +1,125 @@
+#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;
+	
+	float length;
+	
+	/* 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 subgraph_index;
+
+	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_group;
+	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_removeNode(BGraph *graph, BNode *node);
+
+void BLI_removeArc(BGraph *graph, BArc *arc);
+
+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_rebuildAdjacencyList(BGraph* rg);
+void BLI_rebuildAdjacencyListForNode(BGraph* rg, BNode *node);
+void BLI_freeAdjacencyList(BGraph *rg);
+
+int BLI_FlagSubgraphs(BGraph *graph);
+void BLI_ReflagSubgraph(BGraph *graph, int old_subgraph, int new_subgraph);
+
+#define SHAPE_RADIX 10 /* each shape level is encoded this base */
+
+int BLI_subtreeShape(BGraph *graph, BNode *node, BArc *rootArc, int include_root);
+float BLI_subtreeLength(BNode *node);
+void BLI_calcGraphLength(BGraph *graph);
+
+void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced);
+void BLI_replaceNodeInArc(BGraph *graph, BArc *arc, BNode *node_src, BNode *node_replaced);
+void BLI_removeDoubleNodes(BGraph *graph, float limit);
+BNode * BLI_FindNodeByPosition(BGraph *graph, float *p, float limit);
+
+BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v);
+
+int	BLI_isGraphCyclic(BGraph *graph);
+
+/*------------ Symmetry handling ------------*/
+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
+/* Anything higher is the order in radial symmetry */
+#define SYM_SIDE_RADIAL			3
+
+#endif /*BLI_GRAPH_H_*/
diff --git a/source/blender/blenlib/BLI_threads.h b/source/blender/blenlib/BLI_threads.h
index 39162b8bd91..5a7e84c42fb 100644
--- a/source/blender/blenlib/BLI_threads.h
+++ b/source/blender/blenlib/BLI_threads.h
@@ -39,17 +39,41 @@
 #define BLENDER_MAX_THREADS		8
 
 struct ListBase;
-
 void	BLI_init_threads	(struct ListBase *threadbase, void *(*do_thread)(void *), int tot);
 int		BLI_available_threads(struct ListBase *threadbase);
 int		BLI_available_thread_index(struct ListBase *threadbase);
 void	BLI_insert_thread	(struct ListBase *threadbase, void *callerdata);
 void	BLI_remove_thread	(struct ListBase *threadbase, void *callerdata);
+void	BLI_remove_thread_index(struct ListBase *threadbase, int index);
+void	BLI_remove_threads(struct ListBase *threadbase);
 void	BLI_end_threads		(struct ListBase *threadbase);
 
 void	BLI_lock_thread		(int type);
 void	BLI_unlock_thread	(int type);
 
 int		BLI_system_thread_count( void ); /* gets the number of threads the system can make use of */
+
+/* ThreadedWorker is a simple tool for dispatching work to a limited number of threads in a transparent
+ * fashion from the caller's perspective
+ * */
+
+struct ThreadedWorker;
+
+/* Create a new worker supporting tot parallel threads.
+ * When new work in inserted and all threads are busy, sleep(sleep_time) before checking again
+ */
+struct ThreadedWorker *BLI_create_worker(void *(*do_thread)(void *), int tot, int sleep_time);
+
+/* join all working threads */
+void BLI_end_worker(struct ThreadedWorker *worker);
+
+/* also ends all working threads */
+void BLI_destroy_worker(struct ThreadedWorker *worker);
+
+/* Spawns a new work thread if possible, sleeps until one is available otherwise
+ * NOTE: inserting work is NOT thread safe, so make sure it is only done from one thread */
+void BLI_insert_work(struct ThreadedWorker *worker, void *param);
+
+
 #endif
 
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c
index e9271ca3bb5..1967b8a88e2 100644
--- a/source/blender/blenlib/intern/BLI_ghash.c
+++ b/source/blender/blenlib/intern/BLI_ghash.c
@@ -200,12 +200,6 @@ void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreef
 
 /***/
 
-struct GHashIterator {
-	GHash *gh;
-	int curBucket;
-	Entry *curEntry;
-};
-
 GHashIterator *BLI_ghashIterator_new(GHash *gh) {
 	GHashIterator *ghi= malloc(sizeof(*ghi));
 	ghi->gh= gh;
@@ -219,6 +213,17 @@ GHashIterator *BLI_ghashIterator_new(GHash *gh) {
 	}
 	return ghi;
 }
+void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh) {
+	ghi->gh= gh;
+	ghi->curEntry= NULL;
+	ghi->curBucket= -1;
+	while (!ghi->curEntry) {
+		ghi->curBucket++;
+		if (ghi->curBucket==ghi->gh->nbuckets)
+			break;
+		ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
+	}
+}
 void BLI_ghashIterator_free(GHashIterator *ghi) {
 	free(ghi);
 }
diff --git a/source/blender/blenlib/intern/arithb.c b/source/blender/blenlib/intern/arithb.c
index 79517c4fde4..149d3cf1f8f 100644
--- a/source/blender/blenlib/intern/arithb.c
+++ b/source/blender/blenlib/intern/arithb.c
@@ -1371,6 +1371,18 @@ void NormalQuat(float *q)
 	}
 }
 
+void RotationBetweenVectorsToQuat(float *q, float v1[3], float v2[3])
+{
+	float axis[3];
+	float angle;
+	
+	Crossf(axis, v1, v2);
+	
+	angle = NormalizedVecAngle2(v1, v2);
+	
+	AxisAngleToQuat(q, axis, angle);
+}
+
 void AxisAngleToQuat(float *q, float *axis, float angle)
 {
 	float nor[3];
@@ -2219,6 +2231,11 @@ int VecEqual(float *v1, float *v2)
 	return ((v1[0]==v2[0]) && (v1[1]==v2[1]) && (v1[2]==v2[2]));
 }
 
+int VecIsNull(float *v)
+{
+	return (v[0] == 0 && v[1] == 0 && v[2] == 0);
+}
+
 void CalcNormShort( short *v1, short *v2, short *v3, float *n) /* is also cross product */
 {
 	float n1[3],n2[3];
diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c
new file mode 100644
index 00000000000..8f35b38379e
--- /dev/null
+++ b/source/blender/blenlib/intern/graph.c
@@ -0,0 +1,1087 @@
+/**
+ * $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 <float.h> 
+#include <math.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_graph.h"
+#include "BLI_blenlib.h"
+#include "BLI_arithb.h"
+
+#include "BKE_utildefines.h"
+
+static void testRadialSymmetry(BGraph *graph, BNode* root_node, RadialArc* ring, int total, float axis[3], float limit, int group);
+
+static void handleAxialSymmetry(BGraph *graph, BNode *root_node, int depth, float axis[3], float limit);
+static void testAxialSymmetry(BGraph *graph, BNode* root_node, BNode* node1, BNode* node2, BArc* arc1, BArc* arc2, float axis[3], float limit, int group);
+static void flagAxialSymmetry(BNode *root_node, BNode *end_node, BArc *arc, int group);
+
+void BLI_freeNode(BGraph *graph, BNode *node)
+{
+	if (node->arcs)
+	{
+		MEM_freeN(node->arcs);
+	}
+	
+	if (graph->free_node)
+	{
+		graph->free_node(node);
+	}
+}
+
+void BLI_removeNode(BGraph *graph, BNode *node)
+{
+	BLI_freeNode(graph, node);
+	BLI_freelinkN(&graph->nodes, node);
+}
+
+BNode *BLI_otherNode(BArc *arc, BNode *node)
+{
+	return (arc->head == node) ? arc->tail : arc->head;
+}
+
+void BLI_removeArc(BGraph *graph, BArc *arc)
+{
+	if (graph->free_arc)
+	{
+		graph->free_arc(arc);
+	}
+
+	BLI_freelinkN(&graph->arcs, arc);
+}
+
+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->flag] = arc;
+	node->flag++;
+}
+
+void BLI_buildAdjacencyList(BGraph *graph)
+{
+	BNode *node;
+	BArc *arc;
+
+	for(node = graph->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->flag = 0;
+	}
+
+	for(arc = graph->arcs.first; arc; arc= arc->next)
+	{
+		addArcToNodeAdjacencyList(arc->head, arc);
+		addArcToNodeAdjacencyList(arc->tail, arc);
+	}
+
+	for(node = graph->nodes.first; node; node = node->next)
+	{
+		if (node->degree != node->flag)
+		{
+			printf("error in node [%p]. Added only %i arcs out of %i\n", node, node->flag, node->degree);
+		}
+	}
+}
+
+void BLI_rebuildAdjacencyListForNode(BGraph* graph, BNode *node)
+{
+	BArc *arc;
+
+	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->flag = 0;
+
+	for(arc = graph->arcs.first; arc; arc= arc->next)
+	{
+		if (arc->head == node)
+		{
+			addArcToNodeAdjacencyList(arc->head, arc);
+		}
+		else if (arc->tail == node)
+		{
+			addArcToNodeAdjacencyList(arc->tail, arc);
+		}
+	}
+
+	if (node->degree != node->flag)
+	{
+		printf("error in node [%p]. Added only %i arcs out of %i\n", node, node->flag, node->degree);
+	}
+}
+
+void BLI_freeAdjacencyList(BGraph *graph)
+{
+	BNode *node;
+
+	for(node = graph->nodes.first; node; node = node->next)
+	{
+		if (node->arcs != NULL)
+		{
+			MEM_freeN(node->arcs);
+			node->arcs = NULL;
+		}
+	}
+}
+
+int BLI_hasAdjacencyList(BGraph *graph)
+{
+	BNode *node;
+	
+	for(node = graph->nodes.first; node; node = node->next)
+	{
+		if (node->arcs == NULL)
+		{
+			return 0;
+		}
+	}
+	
+	return 1;
+}
+
+void BLI_replaceNodeInArc(BGraph *graph, BArc *arc, BNode *node_src, BNode *node_replaced)
+{
+	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);
+	}
+
+	if (node_replaced->degree == 0)
+	{
+		BLI_removeNode(graph, node_replaced);
+	}
+}
+
+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_replaced->degree--;
+			node_src->degree++;
+		}
+
+		if (arc->tail == node_replaced)
+		{
+			arc->tail = node_src;
+			node_replaced->degree--;
+			node_src->degree++;
+		}
+		
+		if (arc->head == arc->tail)
+		{
+			node_src->degree -= 2;
+			
+			graph->free_arc(arc);
+			BLI_freelinkN(&graph->arcs, arc);
+		}
+	}
+	
+	if (node_replaced->degree == 0)
+	{
+		BLI_removeNode(graph, node_replaced);
+	}
+}
+
+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);
+			}
+		}
+	}
+	
+}
+
+BNode * BLI_FindNodeByPosition(BGraph *graph, float *p, float limit)
+{
+	BNode *closest_node = NULL, *node;
+	float min_distance;
+	
+	for(node = graph->nodes.first; node; node = node->next)
+	{
+		float distance = VecLenf(p, node->p); 
+		if (distance <= limit && (closest_node == NULL || distance < min_distance))
+		{
+			closest_node = node;
+			min_distance = distance;
+		}
+	}
+	
+	return closest_node;
+}
+/************************************* SUBGRAPH DETECTION **********************************************/
+
+void flagSubgraph(BNode *node, int subgraph)
+{
+	if (node->subgraph_index == 0)
+	{
+		BArc *arc;
+		int i;
+		
+		node->subgraph_index = subgraph;
+		
+		for(i = 0; i < node->degree; i++)
+		{
+			arc = node->arcs[i];
+			flagSubgraph(BLI_otherNode(arc, node), subgraph);
+		}
+	}
+} 
+
+int BLI_FlagSubgraphs(BGraph *graph)
+{
+	BNode *node;
+	int subgraph = 0;
+
+	if (BLI_hasAdjacencyList(graph) == 0)
+	{
+		BLI_buildAdjacencyList(graph);
+	}
+	
+	for(node = graph->nodes.first; node; node = node->next)
+	{
+		node->subgraph_index = 0;
+	}
+	
+	for (node = graph->nodes.first; node; node = node->next)
+	{
+		if (node->subgraph_index == 0)
+		{
+			subgraph++;
+			flagSubgraph(node, subgraph);
+		}
+	}
+	
+	return subgraph;
+}
+
+void BLI_ReflagSubgraph(BGraph *graph, int old_subgraph, int new_subgraph)
+{
+	BNode *node;
+
+	for (node = graph->nodes.first; node; node = node->next)
+	{
+		if (node->flag == old_subgraph)
+		{
+			node->flag = new_subgraph;
+		}
+	}
+}
+
+/*************************************** 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 subtreeShape(BNode *node, BArc *rootArc, int include_root)
+{
+	int depth = 0;
+	
+	node->flag = 1;
+	
+	if (include_root)
+	{
+		BNode *newNode = BLI_otherNode(rootArc, node);
+		return subtreeShape(newNode, rootArc, 0);
+	}
+	else
+	{
+		/* 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];
+				BNode *newNode = BLI_otherNode(arc, node);
+				
+				/* stop immediate and cyclic backtracking */
+				if (arc != rootArc && newNode->flag == 0)
+				{
+					depth += subtreeShape(newNode, arc, 0);
+				}
+			}
+		}
+		
+		return SHAPE_RADIX * depth + 1;
+	}
+}
+
+int BLI_subtreeShape(BGraph *graph, BNode *node, BArc *rootArc, int include_root)
+{
+	BNode *test_node;
+	
+	BLI_flagNodes(graph, 0);
+	return subtreeShape(node, rootArc, include_root);
+}
+
+float BLI_subtreeLength(BNode *node)
+{
+	float length = 0;
+	int i;
+
+	node->flag = 0; /* flag node as visited */
+
+	for(i = 0; i < node->degree; i++)
+	{
+		BArc *arc = node->arcs[i];
+		BNode *other_node = BLI_otherNode(arc, node);
+		
+		if (other_node->flag != 0)
+		{
+			float subgraph_length = arc->length + BLI_subtreeLength(other_node); 
+			length = MAX2(length, subgraph_length);
+		}
+	}
+	
+	return length;
+}
+
+void BLI_calcGraphLength(BGraph *graph)
+{
+	float length = 0;
+	int nb_subgraphs;
+	int i;
+	
+	nb_subgraphs = BLI_FlagSubgraphs(graph);
+	
+	for (i = 1; i <= nb_subgraphs; i++)
+	{
+		BNode *node;
+		
+		for (node = graph->nodes.first; node; node = node->next)
+		{
+			/* start on an external node  of the subgraph */
+			if (node->subgraph_index == i && node->degree == 1)
+			{
+				float subgraph_length = BLI_subtreeLength(node);
+				length = MAX2(length, subgraph_length);
+				break;
+			}
+		}
+	}
+	
+	graph->length = length;
+}
+
+/********************************* 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 testRadialSymmetry(BGraph *graph, BNode* root_node, RadialArc* ring, int total, float axis[3], float limit, int group)
+{
+	int symmetric = 1;
+	int i;
+	
+	/* sort ring by angle */
+	for (i = 0; i < total - 1; i++)
+	{
+		float minAngle = FLT_MAX;
+		int minIndex = -1;
+		int j;
+
+		for (j = i + 1; j < total; 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 < total && symmetric; i++)
+	{
+		BNode *node1, *node2;
+		float tangent[3];
+		float normal[3];
+		float p[3];
+		int j = (i + 1) % total; /* next arc in the circular list */
+
+		VecAddf(tangent, ring[i].n, ring[j].n);
+		Crossf(normal, tangent, axis);
+		
+		node1 = BLI_otherNode(ring[i].arc, root_node);
+		node2 = BLI_otherNode(ring[j].arc, root_node);
+
+		VECCOPY(p, node2->p);
+		BLI_mirrorAlongAxis(p, root_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(root_node->symmetry_axis, axis);
+		root_node->symmetry_flag |= SYM_PHYSICAL;
+		root_node->symmetry_flag |= SYM_RADIAL;
+		
+		/* FLAG SYMMETRY GROUP */
+		for (i = 0; i < total; i++)
+		{
+			ring[i].arc->symmetry_group = group;
+			ring[i].arc->symmetry_flag = SYM_SIDE_RADIAL + i;
+		}
+
+		if (graph->radial_symmetry)
+		{
+			graph->radial_symmetry(root_node, ring, total);
+		}
+	}
+}
+
+static void handleRadialSymmetry(BGraph *graph, BNode *root_node, int depth, float axis[3], float limit)
+{
+	RadialArc *ring = NULL;
+	RadialArc *unit;
+	int total = 0;
+	int group;
+	int first;
+	int i;
+
+	/* mark topological symmetry */
+	root_node->symmetry_flag |= SYM_TOPOLOGICAL;
+
+	/* total the number of arcs in the symmetry ring */
+	for (i = 0; i < root_node->degree; i++)
+	{
+		BArc *connectedArc = root_node->arcs[i];
+		
+		/* depth is store as a negative in flag. symmetry level is positive */
+		if (connectedArc->symmetry_level == -depth)
+		{
+			total++;
+		}
+	}
+
+	ring = MEM_callocN(sizeof(RadialArc) * total, "radial symmetry ring");
+	unit = ring;
+
+	/* fill in the ring */
+	for (unit = ring, i = 0; i < root_node->degree; i++)
+	{
+		BArc *connectedArc = root_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, root_node);
+			float vec[3];
+
+			unit->arc = connectedArc;
+
+			/* project the node to node vector on the symmetry plane */
+			VecSubf(unit->n, otherNode->p, root_node->p);
+			Projf(vec, unit->n, axis);
+			VecSubf(unit->n, unit->n, vec);
+
+			Normalize(unit->n);
+
+			unit++;
+		}
+	}
+
+	/* sort ring by arc length
+	 * using a rather bogus insertion sort
+	 * butrings will never get too big to matter
+	 * */
+	for (i = 0; i < total; i++)
+	{
+		int j;
+
+		for (j = i - 1; j >= 0; j--)
+		{
+			BArc *arc1, *arc2;
+			
+			arc1 = ring[j].arc;
+			arc2 = ring[j + 1].arc;
+			
+			if (arc1->length > arc2->length)
+			{
+				/* swap with smaller */
+				RadialArc tmp;
+				
+				tmp = ring[j + 1];
+				ring[j + 1] = ring[j];
+				ring[j] = tmp;
+			}
+			else
+			{
+				break;
+			}
+		}
+	}
+
+	/* Dispatch to specific symmetry tests */
+	first = 0;
+	group = 0;
+	
+	for (i = 1; i < total; i++)
+	{
+		int dispatch = 0;
+		int last = i - 1;
+		
+		if (fabs(ring[first].arc->length - ring[i].arc->length) > limit)
+		{
+			dispatch = 1;
+		}
+
+		/* if not dispatching already and on last arc
+		 * Dispatch using current arc as last
+		 * */		
+		if (dispatch == 0 && i == total - 1)
+		{
+			last = i;
+			dispatch = 1;
+		} 
+		
+		if (dispatch)
+		{
+			int sub_total = last - first + 1; 
+
+			group += 1;
+
+			if (sub_total == 1)
+			{
+				group -= 1; /* not really a group so decrement */
+				/* NOTHING TO DO */
+			}
+			else if (sub_total == 2)
+			{
+				BArc *arc1, *arc2;
+				BNode *node1, *node2;
+				
+				arc1 = ring[first].arc;
+				arc2 = ring[last].arc;
+				
+				node1 = BLI_otherNode(arc1, root_node);
+				node2 = BLI_otherNode(arc2, root_node);
+				
+				testAxialSymmetry(graph, root_node, node1, node2, arc1, arc2, axis, limit, group);
+			}
+			else if (sub_total != total) /* allocate a new sub ring if needed */
+			{
+				RadialArc *sub_ring = MEM_callocN(sizeof(RadialArc) * sub_total, "radial symmetry ring");
+				int sub_i;
+				
+				/* fill in the sub ring */
+				for (sub_i = 0; sub_i < sub_total; sub_i++)
+				{
+					sub_ring[sub_i] = ring[first + sub_i];
+				}
+				
+				testRadialSymmetry(graph, root_node, sub_ring, sub_total, axis, limit, group);
+			
+				MEM_freeN(sub_ring);
+			}
+			else if (sub_total == total)
+			{
+				testRadialSymmetry(graph, root_node, ring, total, axis, limit, group);
+			}
+			
+			first = i;
+		}
+	}
+
+
+	MEM_freeN(ring);
+}
+
+static void flagAxialSymmetry(BNode *root_node, BNode *end_node, BArc *arc, int group)
+{
+	float vec[3];
+	
+	arc->symmetry_group = group;
+	
+	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 testAxialSymmetry(BGraph *graph, BNode* root_node, BNode* node1, BNode* node2, BArc* arc1, BArc* arc2, float axis[3], float limit, int group)
+{
+	float nor[3], vec[3], p[3];
+
+	VecSubf(p, node1->p, root_node->p);
+	Crossf(nor, p, axis);
+
+	VecSubf(p, root_node->p, node2->p);
+	Crossf(vec, p, axis);
+	VecAddf(vec, vec, nor);
+	
+	Crossf(nor, vec, axis);
+	
+	if (abs(nor[0]) > abs(nor[1]) && abs(nor[0]) > abs(nor[2]) && nor[0] < 0)
+	{
+		VecMulf(nor, -1);
+	}
+	else if (abs(nor[1]) > abs(nor[0]) && abs(nor[1]) > abs(nor[2]) && nor[1] < 0)
+	{
+		VecMulf(nor, -1);
+	}
+	else if (abs(nor[2]) > abs(nor[1]) && abs(nor[2]) > abs(nor[0]) && nor[2] < 0)
+	{
+		VecMulf(nor, -1);
+	}
+	
+	/* mirror node2 along axis */
+	VECCOPY(p, node2->p);
+	BLI_mirrorAlongAxis(p, root_node->p, nor);
+	
+	/* check if it's within limit before continuing */
+	if (VecLenf(node1->p, p) <= limit)
+	{
+		/* mark node as symmetric physically */
+		VECCOPY(root_node->symmetry_axis, nor);
+		root_node->symmetry_flag |= SYM_PHYSICAL;
+		root_node->symmetry_flag |= SYM_AXIAL;
+
+		/* flag side on arcs */
+		flagAxialSymmetry(root_node, node1, arc1, group);
+		flagAxialSymmetry(root_node, node2, arc2, group);
+		
+		if (graph->axial_symmetry)
+		{
+			graph->axial_symmetry(root_node, node1, node2, arc1, arc2);
+		}
+	}
+	else
+	{
+		/* NOT SYMMETRIC */
+	}
+}
+
+static void handleAxialSymmetry(BGraph *graph, BNode *root_node, int depth, float axis[3], float limit)
+{
+	BArc *arc1 = NULL, *arc2 = NULL;
+	BNode *node1 = NULL, *node2 = NULL;
+	int i;
+	
+	/* mark topological symmetry */
+	root_node->symmetry_flag |= SYM_TOPOLOGICAL;
+
+	for (i = 0; i < root_node->degree; i++)
+	{
+		BArc *connectedArc = root_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, root_node);
+			}
+			else
+			{
+				arc2 = connectedArc;
+				node2 = BLI_otherNode(arc2, root_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;
+	}
+	
+	testAxialSymmetry(graph, root_node, node1, node2, arc1, arc2, axis, limit, 1);
+}
+
+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)
+	{
+		handleAxialSymmetry(graph, node, depth, axis, limit);
+	}
+	else
+	{
+		handleRadialSymmetry(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;
+
+	/* if arc is null, we start straight from a node */	
+	if (arc)
+	{
+		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_subtreeShape(graph, connectedNode, connectedArc, 0);
+		}
+	}
+
+	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; 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;
+					break;
+				} 
+			}
+		}
+		
+		/* 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 if (connectedArc->symmetry_level < arc->symmetry_level)
+			{
+				/* go with more complex subtree as symmetry arc */
+				arc = connectedArc;
+			}
+		}
+	}
+	
+	/* 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;
+	
+	/* sanity check REMOVE ME */
+	if (node->degree > 0)
+	{
+		arc = node->arcs[0];
+		
+		if (node->degree == 1)
+		{
+			markdownSymmetryArc(graph, arc, node, 1, limit);
+		}
+		else
+		{
+			markdownSymmetryArc(graph, NULL, 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/blenlib/intern/threads.c b/source/blender/blenlib/intern/threads.c
index 92fad291e83..9df8bbc81e3 100644
--- a/source/blender/blenlib/intern/threads.c
+++ b/source/blender/blenlib/intern/threads.c
@@ -38,6 +38,8 @@
 #include "BLI_blenlib.h"
 #include "BLI_threads.h"
 
+#include "PIL_time.h"
+
 /* for checking system threads - BLI_system_thread_count */
 #ifdef WIN32
 #include "Windows.h"
@@ -199,6 +201,34 @@ void BLI_remove_thread(ListBase *threadbase, void *callerdata)
 	}
 }
 
+void BLI_remove_thread_index(ListBase *threadbase, int index)
+{
+	ThreadSlot *tslot;
+	int counter=0;
+	
+	for(tslot = threadbase->first; tslot; tslot = tslot->next, counter++) {
+		if (counter == index && tslot->avail == 0) {
+			tslot->callerdata = NULL;
+			pthread_join(tslot->pthread, NULL);
+			tslot->avail = 1;
+			break;
+		}
+	}
+}
+
+void BLI_remove_threads(ListBase *threadbase)
+{
+	ThreadSlot *tslot;
+	
+	for(tslot = threadbase->first; tslot; tslot = tslot->next) {
+		if (tslot->avail == 0) {
+			tslot->callerdata = NULL;
+			pthread_join(tslot->pthread, NULL);
+			tslot->avail = 1;
+		}
+	}
+}
+
 void BLI_end_threads(ListBase *threadbase)
 {
 	ThreadSlot *tslot;
@@ -265,4 +295,104 @@ int BLI_system_thread_count( void )
 	return t;
 }
 
+/* ************************************************ */
+
+typedef struct ThreadedWorker {
+	ListBase threadbase;
+	void *(*work_fnct)(void *);
+	char	 busy[RE_MAX_THREAD];
+	int		 total;
+	int		 sleep_time;
+} ThreadedWorker;
+
+typedef struct WorkParam {
+	ThreadedWorker *worker;
+	void *param;
+	int	  index;
+} WorkParam;
+
+void *exec_work_fnct(void *v_param)
+{
+	WorkParam *p = (WorkParam*)v_param;
+	void *value;
+	
+	value = p->worker->work_fnct(p->param);
+	
+	p->worker->busy[p->index] = 0;
+	MEM_freeN(p);
+	
+	return value;
+}
+
+ThreadedWorker *BLI_create_worker(void *(*do_thread)(void *), int tot, int sleep_time)
+{
+	ThreadedWorker *worker;
+	
+	worker = MEM_callocN(sizeof(ThreadedWorker), "threadedworker");
+	
+	if (tot > RE_MAX_THREAD)
+	{
+		tot = RE_MAX_THREAD;
+	}
+	else if (tot < 1)
+	{
+		tot= 1;
+	}
+	
+	worker->total = tot;
+	worker->work_fnct = do_thread;
+	
+	BLI_init_threads(&worker->threadbase, exec_work_fnct, tot);
+	
+	return worker;
+}
+
+void BLI_end_worker(ThreadedWorker *worker)
+{
+	BLI_remove_threads(&worker->threadbase);
+}
+
+void BLI_destroy_worker(ThreadedWorker *worker)
+{
+	BLI_end_worker(worker);
+	BLI_freelistN(&worker->threadbase);
+	MEM_freeN(worker);
+}
+
+void BLI_insert_work(ThreadedWorker *worker, void *param)
+{
+	WorkParam *p = MEM_callocN(sizeof(WorkParam), "workparam");
+	int index;
+	
+	if (BLI_available_threads(&worker->threadbase) == 0)
+	{
+		index = worker->total;
+		while(index == worker->total)
+		{
+			PIL_sleep_ms(worker->sleep_time);
+			
+			for (index = 0; index < worker->total; index++)
+			{
+				if (worker->busy[index] == 0)
+				{
+					BLI_remove_thread_index(&worker->threadbase, index);
+					break;
+				}
+			}
+		}
+	}
+	else
+	{
+		index = BLI_available_thread_index(&worker->threadbase);
+	}
+	
+	worker->busy[index] = 1;
+	
+	p->param = param;
+	p->index = index;
+	p->worker = worker;
+	
+	BLI_insert_thread(&worker->threadbase, p);
+}
+
 /* eof */