merging harmonic-skeleton branch into trunk. All changes are hidden behind a disabled...
authorMartin Poirier <theeth@yahoo.com>
Tue, 28 Oct 2008 22:53:48 +0000 (22:53 +0000)
committerMartin Poirier <theeth@yahoo.com>
Tue, 28 Oct 2008 22:53:48 +0000 (22:53 +0000)
20 files changed:
source/blender/blenkernel/intern/scene.c
source/blender/blenlib/BLI_arithb.h
source/blender/blenlib/BLI_ghash.h
source/blender/blenlib/BLI_graph.h [new file with mode: 0644]
source/blender/blenlib/BLI_threads.h
source/blender/blenlib/intern/BLI_ghash.c
source/blender/blenlib/intern/arithb.c
source/blender/blenlib/intern/graph.c [new file with mode: 0644]
source/blender/blenlib/intern/threads.c
source/blender/blenloader/intern/readfile.c
source/blender/include/BIF_editarmature.h
source/blender/include/butspace.h
source/blender/include/reeb.h
source/blender/makesdna/DNA_scene_types.h
source/blender/src/autoarmature.c [new file with mode: 0644]
source/blender/src/buttons_editing.c
source/blender/src/drawview.c
source/blender/src/editarmature.c
source/blender/src/reeb.c
source/blender/src/usiblender.c

index c71d3c7fdd2bede1fca0386ce4a712ee450d52c2..1727edc10fce3735c32401c34952683b1a500fe5 100644 (file)
@@ -259,6 +259,21 @@ Scene *add_scene(char *name)
        sce->toolsettings->select_thresh= 0.01f;
        sce->toolsettings->jointrilimit = 0.8f;
 
+       sce->toolsettings->skgen_resolution = 100;
+       sce->toolsettings->skgen_threshold_internal     = 0.01f;
+       sce->toolsettings->skgen_threshold_external     = 0.01f;
+       sce->toolsettings->skgen_angle_limit                    = 45.0f;
+       sce->toolsettings->skgen_length_ratio                   = 1.3f;
+       sce->toolsettings->skgen_length_limit                   = 1.5f;
+       sce->toolsettings->skgen_correlation_limit              = 0.98f;
+       sce->toolsettings->skgen_symmetry_limit                 = 0.1f;
+       sce->toolsettings->skgen_postpro = SKGEN_SMOOTH;
+       sce->toolsettings->skgen_postpro_passes = 1;
+       sce->toolsettings->skgen_options = SKGEN_FILTER_INTERNAL|SKGEN_FILTER_EXTERNAL|SKGEN_FILTER_SMART|SKGEN_HARMONIC|SKGEN_SUB_CORRELATION|SKGEN_STICK_TO_EMBEDDING;
+       sce->toolsettings->skgen_subdivisions[0] = SKGEN_SUB_CORRELATION;
+       sce->toolsettings->skgen_subdivisions[1] = SKGEN_SUB_LENGTH;
+       sce->toolsettings->skgen_subdivisions[2] = SKGEN_SUB_ANGLE;
+
        pset= &sce->toolsettings->particle;
        pset->flag= PE_KEEP_LENGTHS|PE_LOCK_FIRST|PE_DEFLECT_EMITTER;
        pset->emitterdist= 0.25f;
index e2e71a2fb1a7e67cde095a0f5886eee2e2f78bd9..e4b983d9ba307f2bf78132d204e388b45762855b 100644 (file)
@@ -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);
index aec77f5f3859ddcd684cc31c3af321cc18b5e25a..c77e82f0a2bbcb3ea6fc8830bcadf660cbd3dde1 100644 (file)
 
 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);
@@ -62,6 +67,15 @@ int          BLI_ghash_size          (GHash *gh);
         * @return Pointer to a new DynStr.
         */
 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.
         *
diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h
new file mode 100644 (file)
index 0000000..160c2e0
--- /dev/null
@@ -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_*/
index 39162b8bd91f934b040307b718943fd4c91ab214..5a7e84c42fb0818c92aea4b9e7497459b59824df 100644 (file)
 #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
 
index e9271ca3bb57ec1978344a88f43cdb5c4440edab..1967b8a88e2376b34c19ceaeb9abe49e8cf1c127 100644 (file)
@@ -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);
 }
index 79517c4fde4038819f4cfd3e0035415ec5b22bb3..149d3cf1f8f5bc65413d18a6346fae0a008657c0 100644 (file)
@@ -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 (file)
index 0000000..8f35b38
--- /dev/null
@@ -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;
+                               }
+                       }
+               }
+       }
+}
+
index 92fad291e83e886446e9631a33cbd4f63369f107..9df8bbc81e3628de740c200463a093e76e8e46f3 100644 (file)
@@ -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 */
index edb9c3ff898dfe109e61c0fdaeeeb1b7a636d13c..3a9d0a6ae6a16cd611658fe33c86cf2886cb4df8 100644 (file)
@@ -7379,6 +7379,24 @@ static void do_versions(FileData *fd, Library *lib, Main *main)
                        }
                }
        }
+       
+       /* sanity check for skgen
+        * */
+       {
+               Scene *sce;
+               for(sce=main->scene.first; sce; sce = sce->id.next)
+               {
+                       if (sce->toolsettings->skgen_subdivisions[0] == sce->toolsettings->skgen_subdivisions[1] ||
+                               sce->toolsettings->skgen_subdivisions[0] == sce->toolsettings->skgen_subdivisions[2] ||
+                               sce->toolsettings->skgen_subdivisions[1] == sce->toolsettings->skgen_subdivisions[2])
+                       {
+                                       sce->toolsettings->skgen_subdivisions[0] = SKGEN_SUB_CORRELATION;
+                                       sce->toolsettings->skgen_subdivisions[1] = SKGEN_SUB_LENGTH;
+                                       sce->toolsettings->skgen_subdivisions[2] = SKGEN_SUB_ANGLE;
+                       }
+               }
+       }
+       
 
        if ((main->versionfile < 245) || (main->versionfile == 245 && main->subversionfile < 2)) {
                Image *ima;
index d390b96f61f5bccc4dd103ff9ae9db3b274a9480..02d736808188b2826ca2103519b3df37126f8ffe 100644 (file)
@@ -68,6 +68,8 @@ typedef struct EditBone
 
 } EditBone;
 
+void   make_boneList(struct ListBase *list, struct ListBase *bones, EditBone *parent);
+void   editbones_to_armature (struct ListBase *list, struct Object *ob);
 
 void   adduplicate_armature(void);
 void   addvert_armature(void);
@@ -148,6 +150,15 @@ void       align_selected_bones(void);
 
 #define BONESEL_NOSEL  0x80000000      /* Indicates a negative number */
 
+/* from autoarmature */
+void BIF_retargetArmature();
+void BIF_adjustRetarget();
+void BIF_freeRetarget();
+
+struct ReebArc;
+float calcVariance(struct ReebArc *arc, int start, int end, float v0[3], float n[3]);
+float calcDistance(struct ReebArc *arc, int start, int end, float head[3], float tail[3]);
+
 /* useful macros */
 #define EBONE_VISIBLE(arm, ebone) ((arm->layer & ebone->layer) && !(ebone->flag & BONE_HIDDEN_A))
 #define EBONE_EDITABLE(ebone) ((ebone->flag & BONE_SELECTED) && !(ebone->flag & BONE_EDITMODE_LOCKED)) 
index 3de427476b9419b812718465d54c693de8c2776f..8cac5a074ab54916c39505c6f0682c108c5a3c47 100644 (file)
@@ -443,7 +443,8 @@ void curvemap_buttons(struct uiBlock *block, struct CurveMapping *cumap, char la
 #define B_SETMCOL_RND          2083
 #define B_DRAWBWEIGHTS         2084
 
-#define B_GEN_SKELETON         2090
+#define B_GEN_SKELETON         2085
+#define B_RETARGET_SKELETON    2086
 
 /* *********************** */
 #define B_VGROUPBUTS           2100
index c8352aedec54e63710c5fba10cff01ea4e8b0982..57f7d1b60cf599814fb4c0f64642e18d3e2db6d6 100644 (file)
 #ifndef REEB_H_
 #define REEB_H_
 
+//#define WITH_BF_REEB
+
 #include "DNA_listBase.h"
 
+#include "BLI_graph.h"
+
+struct GHash;
 struct EdgeHash;
 struct ReebArc;
 struct ReebEdge;
 struct ReebNode;
 
 typedef struct ReebGraph {
-       ListBase arcs;
-       ListBase nodes;
+       ListBase        arcs;
+       ListBase        nodes;
+       
+       float length;
+       
+       FreeArc                 free_arc;
+       FreeNode                free_node;
+       RadialSymmetry  radial_symmetry;
+       AxialSymmetry   axial_symmetry;
+       /*********************************/
+       
+       int resolution;
        int totnodes;
        struct EdgeHash *emap;
+       int multi_level;
+       struct ReebGraph *link_up; /* for multi resolution filtering, points to higher levels */
 } ReebGraph;
 
 typedef struct EmbedBucket {
@@ -49,13 +66,25 @@ typedef struct EmbedBucket {
 } EmbedBucket;
 
 typedef struct ReebNode {
-       struct ReebNode *next, *prev;
+       void *next, *prev;
+       float p[3];
+       int flag;
+
+       int degree;
        struct ReebArc **arcs;
+
+       int subgraph_index;
+
+       int symmetry_level;
+       int symmetry_flag;
+       float symmetry_axis[3];
+       /*********************************/
+
        int index;
-       int degree;
        float weight;
-       float p[3];
-       int flags;
+       int     multi_level;
+       struct ReebNode *link_down; /* for multi resolution filtering, points to lower levels, if present */
+       struct ReebNode *link_up;
 } ReebNode;
 
 typedef struct ReebEdge {
@@ -63,15 +92,28 @@ typedef struct ReebEdge {
        struct ReebArc  *arc;
        struct ReebNode *v1, *v2;
        struct ReebEdge *nextEdge;
+       int flag;
 } ReebEdge;
 
 typedef struct ReebArc {
-       struct ReebArc *next, *prev;
+       void *next, *prev;
+       struct ReebNode *head, *tail;
+       int flag;
+
+       float length;
+
+       int symmetry_level;
+       int symmetry_group;
+       int symmetry_flag;
+       /*********************************/
+
        ListBase edges;
-       struct ReebNode *v1, *v2;
+       int bcount;
        struct EmbedBucket *buckets;
-       int     bcount;
-       int flags;
+
+       struct GHash *faces;    
+       float angle;
+       struct ReebArc *link_up; /* for multi resolution filtering, points to higher levels */
 } ReebArc;
 
 typedef struct ReebArcIterator {
@@ -79,29 +121,37 @@ typedef struct ReebArcIterator {
        int index;
        int start;
        int end;
-       int stride;
+       int stride; 
+       int length;
 } ReebArcIterator;
 
 struct EditMesh;
+struct EdgeIndex;
 
-int weightToHarmonic(struct EditMesh *em);
-int weightFromDistance(struct EditMesh *em);
+int weightToHarmonic(struct EditMesh *em, struct EdgeIndex *indexed_edges);
+int weightFromDistance(struct EditMesh *em, struct EdgeIndex *indexed_edges);
 int weightFromLoc(struct EditMesh *me, int axis);
-void weightToVCol(struct EditMesh *em);
+void weightToVCol(struct EditMesh *em, int index);
+void arcToVCol(struct ReebGraph *rg, struct EditMesh *em, int index);
+void angleToVCol(struct EditMesh *em, int index);
 void renormalizeWeight(struct EditMesh *em, float newmax);
 
 ReebGraph * generateReebGraph(struct EditMesh *me, int subdivisions);
-void freeGraph(ReebGraph *rg);
-void exportGraph(ReebGraph *rg, int count);
-
-#define OTHER_NODE(arc, node) ((arc->v1 == node) ? arc->v2 : arc->v1)
+ReebGraph * newReebGraph();
 
 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);
 struct EmbedBucket * nextBucket(struct ReebArcIterator *iter);
+struct EmbedBucket * nextNBucket(ReebArcIterator *iter, int n);
+struct EmbedBucket * peekBucket(ReebArcIterator *iter, int n);
+struct EmbedBucket * currentBucket(struct ReebArcIterator *iter);
+struct EmbedBucket * previousBucket(struct ReebArcIterator *iter);
+int iteratorStopped(struct ReebArcIterator *iter);
 
 /* Filtering */
 void filterNullReebGraph(ReebGraph *rg);
+int filterSmartReebGraph(ReebGraph *rg, float threshold);
 int filterExternalReebGraph(ReebGraph *rg, float threshold);
 int filterInternalReebGraph(ReebGraph *rg, float threshold);
 
@@ -110,18 +160,33 @@ 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);
-
-/* Sanity check */
+/*------------ Sanity check ------------*/
 void verifyBuckets(ReebGraph *rg);
+void verifyFaces(ReebGraph *rg);
+
+/*********************** PUBLIC *********************************/
+
+#define REEB_MAX_MULTI_LEVEL   10
+
+ReebGraph *BIF_ReebGraphFromEditMesh(void);
+ReebGraph *BIF_ReebGraphMultiFromEditMesh(void);
+void BIF_flagMultiArcs(ReebGraph *rg, int flag);
+
+void BIF_GlobalReebGraphFromEditMesh(void);
+void BIF_GlobalReebFree(void);
+
+ReebNode *BIF_otherNodeFromIndex(ReebArc *arc, ReebNode *node);
+ReebNode *BIF_NodeFromIndex(ReebArc *arc, ReebNode *node);
+ReebNode *BIF_lowestLevelNode(ReebNode *node);
+
+ReebGraph *BIF_graphForMultiNode(ReebGraph *rg, ReebNode *node);
+
+void REEB_freeGraph(ReebGraph *rg);
+void REEB_exportGraph(ReebGraph *rg, int count);
+void REEB_draw();
+
 
 #endif /*REEB_H_*/
index a5eaf222941eee3bf93a4b90a77c6aecf4646287..c1c164f136f4427708581acfaa031be5be1af20a 100644 (file)
@@ -433,14 +433,20 @@ typedef struct ToolSettings {
        float skgen_angle_limit;
        float skgen_correlation_limit;
        float skgen_symmetry_limit;
+       float skgen_retarget_angle_weight;
+       float skgen_retarget_length_weight;
+       float skgen_retarget_distance_weight;
        short skgen_options;
        char  skgen_postpro;
        char  skgen_postpro_passes;
        char  skgen_subdivisions[3];
+       char  skgen_multi_level;
+       char  skgen_optimisation_method;
+       
+       char tpad[6];
        
        /* Alt+RMB option */
        char edge_mode;
-       char pad3[4];
 } ToolSettings;
 
 /* Used by all brushes to store their properties, which can be directly set
@@ -837,12 +843,21 @@ typedef struct Scene {
 #define RETOPO_ELLIPSE 4
 
 /* toolsettings->skgen_options */
-#define SKGEN_FILTER_INTERNAL  1
-#define SKGEN_FILTER_EXTERNAL  2
-#define        SKGEN_SYMMETRY                  4
-#define        SKGEN_CUT_LENGTH                8
-#define        SKGEN_CUT_ANGLE                 16
-#define        SKGEN_CUT_CORRELATION   32
+#define SKGEN_FILTER_INTERNAL  (1 << 0)
+#define SKGEN_FILTER_EXTERNAL  (1 << 1)
+#define        SKGEN_SYMMETRY                  (1 << 2)
+#define        SKGEN_CUT_LENGTH                (1 << 3)
+#define        SKGEN_CUT_ANGLE                 (1 << 4)
+#define        SKGEN_CUT_CORRELATION   (1 << 5)
+#define        SKGEN_HARMONIC                  (1 << 6)
+#define        SKGEN_STICK_TO_EMBEDDING        (1 << 7)
+#define        SKGEN_ADAPTIVE_DISTANCE         (1 << 8)
+#define SKGEN_FILTER_SMART             (1 << 9)
+#define SKGEN_DISP_LENGTH              (1 << 10)
+#define SKGEN_DISP_WEIGHT              (1 << 11)
+#define SKGEN_DISP_ORIG                        (1 << 12)
+#define SKGEN_DISP_EMBED               (1 << 13)
+#define SKGEN_DISP_INDEX               (1 << 14)
 
 #define        SKGEN_SUB_LENGTH                0
 #define        SKGEN_SUB_ANGLE                 1
diff --git a/source/blender/src/autoarmature.c b/source/blender/src/autoarmature.c
new file mode 100644 (file)
index 0000000..b0a7a2a
--- /dev/null
@@ -0,0 +1,2968 @@
+/**
+ * $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 *****
+ * autoarmature.c: Interface for automagically manipulating armature (retarget, created, ...)
+ */
+
+#include <ctype.h>
+#include <stdlib.h>
+#include <string.h>
+#include <math.h> 
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include "MEM_guardedalloc.h"
+
+#include "PIL_time.h"
+
+#include "DNA_ID.h"
+#include "DNA_action_types.h"
+#include "DNA_armature_types.h"
+#include "DNA_constraint_types.h"
+#include "DNA_mesh_types.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_object_types.h"
+#include "DNA_scene_types.h"
+#include "DNA_view3d_types.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_arithb.h"
+#include "BLI_editVert.h"
+#include "BLI_ghash.h"
+#include "BLI_graph.h"
+#include "BLI_rand.h"
+#include "BLI_threads.h"
+
+#include "BDR_editobject.h"
+
+#include "BKE_global.h"
+#include "BKE_utildefines.h"
+#include "BKE_constraint.h"
+#include "BKE_armature.h"
+
+#include "BIF_editarmature.h"
+#include "BIF_space.h"
+
+#include "PIL_time.h"
+
+#include "mydevice.h"
+#include "reeb.h" // FIX ME
+#include "blendef.h"
+
+/************ RIG RETARGET DATA STRUCTURES ***************/
+
+struct RigJoint;
+struct RigGraph;
+struct RigNode;
+struct RigArc;
+struct RigEdge;
+
+//#define USE_THREADS
+
+typedef struct RigGraph {
+       ListBase        arcs;
+       ListBase        nodes;
+       
+       float length;
+       
+       FreeArc                 free_arc;
+       FreeNode                free_node;
+       RadialSymmetry  radial_symmetry;
+       AxialSymmetry   axial_symmetry;
+       /*********************************/
+
+       struct RigNode *head;
+       ReebGraph *link_mesh;
+       
+       ListBase editbones;
+       
+       ListBase controls;
+       struct ThreadedWorker *worker;
+       
+       GHash *bones_map;       /* map of editbones by name */
+       GHash *controls_map;    /* map of rigcontrols by bone pointer */
+       
+       Object *ob;
+} RigGraph;
+
+typedef struct RigNode {
+       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];
+       /*********************************/
+
+       ReebNode *link_mesh;
+} RigNode;
+
+typedef struct RigArc {
+       void *next, *prev;
+       RigNode *head, *tail;
+       int flag;
+
+       float length;
+
+       int symmetry_level;
+       int symmetry_group;
+       int symmetry_flag;
+       /*********************************/
+       
+       ListBase edges;
+       int count;
+       ReebArc *link_mesh;
+} RigArc;
+
+typedef struct RigEdge {
+       struct RigEdge *next, *prev;
+       float head[3], tail[3];
+       float length;
+       float angle;
+       EditBone *bone;
+       float up_axis[3];
+} RigEdge;
+
+/* Control flags */
+#define RIG_CTRL_DONE                  1
+#define RIG_CTRL_PARENT_DEFORM 2
+#define RIG_CTRL_FIT_ROOT              4
+#define RIG_CTRL_FIT_BONE              8
+
+typedef struct RigControl {
+       struct RigControl *next, *prev;
+       float head[3], tail[3];
+       EditBone *bone;
+       EditBone *link;
+       float   up_axis[3];
+       float   offset[3];
+       int             flag;
+} RigControl;
+
+typedef struct MemoNode {
+       float   weight;
+       int     next;
+} MemoNode;
+
+typedef struct RetargetParam {
+       RigGraph        *rigg;
+       RigArc          *iarc;
+       RigNode         *inode_start;
+} RetargetParam;
+
+typedef enum 
+{
+       RETARGET_LENGTH,
+       RETARGET_AGGRESSIVE
+} RetargetMode; 
+
+typedef enum
+{
+       METHOD_BRUTE_FORCE = 0,
+       METHOD_MEMOIZE = 1,
+       METHOD_ANNEALING = 2
+} RetargetMethod;
+
+typedef enum
+{
+       ARC_FREE = 0,
+       ARC_TAKEN = 1,
+       ARC_USED = 2
+} ArcUsageFlags;
+
+
+RigGraph *GLOBAL_RIGG = NULL;
+
+/*******************************************************************************************************/
+
+void *exec_retargetArctoArc(void *param);
+
+static void RIG_calculateEdgeAngle(RigEdge *edge_first, RigEdge *edge_second);
+
+/* two levels */
+#define SHAPE_LEVELS (SHAPE_RADIX * SHAPE_RADIX) 
+
+/*********************************** EDITBONE UTILS ****************************************************/
+
+int countEditBoneChildren(ListBase *list, EditBone *parent)
+{
+       EditBone *ebone;
+       int count = 0;
+       
+       for (ebone = list->first; ebone; ebone = ebone->next)
+       {
+               if (ebone->parent == parent)
+               {
+                       count++;
+               }
+       }
+       
+       return count;
+}
+
+EditBone* nextEditBoneChild(ListBase *list, EditBone *parent, int n)
+{
+       EditBone *ebone;
+       
+       for (ebone = list->first; ebone; ebone = ebone->next)
+       {
+               if (ebone->parent == parent)
+               {
+                       if (n == 0)
+                       {
+                               return ebone;
+                       }
+                       n--;
+               }
+       }
+       
+       return NULL;
+}
+
+void getEditBoneRollUpAxis(EditBone *bone, float roll, float up_axis[3])
+{
+       float mat[3][3], nor[3];
+
+       VecSubf(nor, bone->tail, bone->head);
+       
+       vec_roll_to_mat3(nor, roll, mat);
+       VECCOPY(up_axis, mat[2]);
+}
+
+float getNewBoneRoll(EditBone *bone, float old_up_axis[3], float quat[4])
+{
+       float mat[3][3];
+       float nor[3], up_axis[3], new_up_axis[3], vec[3];
+       float roll;
+       
+       VECCOPY(new_up_axis, old_up_axis);
+       QuatMulVecf(quat, new_up_axis);
+
+       VecSubf(nor, bone->tail, bone->head);
+       
+       vec_roll_to_mat3(nor, 0, mat);
+       VECCOPY(up_axis, mat[2]);
+       
+       roll = NormalizedVecAngle2(new_up_axis, up_axis);
+       
+       Crossf(vec, up_axis, new_up_axis);
+       
+       if (Inpf(vec, nor) < 0)
+       {
+               roll = -roll;
+       }
+       
+       return roll;
+}
+
+/************************************ DESTRUCTORS ******************************************************/
+
+void RIG_freeRigArc(BArc *arc)
+{
+       BLI_freelistN(&((RigArc*)arc)->edges);
+}
+
+void RIG_freeRigGraph(BGraph *rg)
+{
+       BNode *node;
+       BArc *arc;
+       
+#ifdef USE_THREADS
+       BLI_destroy_worker(((RigGraph*)rg)->worker);
+#endif
+       
+       REEB_freeGraph(((RigGraph*)rg)->link_mesh);
+       
+       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(rg, (BNode*)node);
+       }
+       BLI_freelistN(&rg->nodes);
+       
+       BLI_freelistN(&((RigGraph*)rg)->controls);
+
+       BLI_ghash_free(((RigGraph*)rg)->bones_map, NULL, NULL);
+       BLI_ghash_free(((RigGraph*)rg)->controls_map, NULL, NULL);
+       
+       BLI_freelistN(&((RigGraph*)rg)->editbones);
+       
+       MEM_freeN(rg);
+}
+
+/************************************* ALLOCATORS ******************************************************/
+
+static RigGraph *newRigGraph()
+{
+       RigGraph *rg;
+       int totthread;
+       
+       rg = MEM_callocN(sizeof(RigGraph), "rig graph");
+       
+       rg->head = NULL;
+       
+       rg->bones_map = BLI_ghash_new(BLI_ghashutil_strhash, BLI_ghashutil_strcmp);
+       rg->controls_map = BLI_ghash_new(BLI_ghashutil_strhash, BLI_ghashutil_strcmp);
+       
+       rg->free_arc = RIG_freeRigArc;
+       rg->free_node = NULL;
+       
+#ifdef USE_THREADS
+       if(G.scene->r.mode & R_FIXED_THREADS)
+       {
+               totthread = G.scene->r.threads;
+       }
+       else
+       {
+               totthread = BLI_system_thread_count();
+       }
+       
+       rg->worker = BLI_create_worker(exec_retargetArctoArc, totthread, 20); /* fix number of threads */
+#endif
+       
+       return rg;
+}
+
+static RigArc *newRigArc(RigGraph *rg)
+{
+       RigArc *arc;
+       
+       arc = MEM_callocN(sizeof(RigArc), "rig arc");
+       arc->count = 0;
+       BLI_addtail(&rg->arcs, arc);
+       
+       return arc;
+}
+
+static RigControl *newRigControl(RigGraph *rg)
+{
+       RigControl *ctrl;
+       
+       ctrl = MEM_callocN(sizeof(RigControl), "rig control");
+       
+       BLI_addtail(&rg->controls, ctrl);
+       
+       return ctrl;
+}
+
+static RigNode *newRigNodeHead(RigGraph *rg, RigArc *arc, float p[3])
+{
+       RigNode *node;
+       node = MEM_callocN(sizeof(RigNode), "rig node");
+       BLI_addtail(&rg->nodes, node);
+
+       VECCOPY(node->p, p);
+       node->degree = 1;
+       node->arcs = NULL;
+       
+       arc->head = node;
+       
+       return node;
+}
+
+static void addRigNodeHead(RigGraph *rg, RigArc *arc, RigNode *node)
+{
+       node->degree++;
+
+       arc->head = node;
+}
+
+static RigNode *newRigNode(RigGraph *rg, float p[3])
+{
+       RigNode *node;
+       node = MEM_callocN(sizeof(RigNode), "rig node");
+       BLI_addtail(&rg->nodes, node);
+
+       VECCOPY(node->p, p);
+       node->degree = 0;
+       node->arcs = NULL;
+       
+       return node;
+}
+
+static RigNode *newRigNodeTail(RigGraph *rg, RigArc *arc, float p[3])
+{
+       RigNode *node = newRigNode(rg, p);
+       
+       node->degree = 1;
+       arc->tail = node;
+
+       return node;
+}
+
+static void RIG_appendEdgeToArc(RigArc *arc, RigEdge *edge)
+{
+       BLI_addtail(&arc->edges, edge);
+
+       if (edge->prev == NULL)
+       {
+               VECCOPY(edge->head, arc->head->p);
+       }
+       else
+       {
+               RigEdge *last_edge = edge->prev;
+               VECCOPY(edge->head, last_edge->tail);
+               RIG_calculateEdgeAngle(last_edge, edge);
+       }
+       
+       edge->length = VecLenf(edge->head, edge->tail);
+       
+       arc->length += edge->length;
+       
+       arc->count += 1;
+}
+
+static void RIG_addEdgeToArc(RigArc *arc, float tail[3], EditBone *bone)
+{
+       RigEdge *edge;
+
+       edge = MEM_callocN(sizeof(RigEdge), "rig edge");
+
+       VECCOPY(edge->tail, tail);
+       edge->bone = bone;
+       
+       if (bone)
+       {
+               getEditBoneRollUpAxis(bone, bone->roll, edge->up_axis);
+       }
+       
+       RIG_appendEdgeToArc(arc, edge);
+}
+
+/*******************************************************************************************************/
+
+static void RIG_calculateEdgeAngle(RigEdge *edge_first, RigEdge *edge_second)
+{
+       float vec_first[3], vec_second[3];
+       
+       VecSubf(vec_first, edge_first->tail, edge_first->head); 
+       VecSubf(vec_second, edge_second->tail, edge_second->head);
+
+       Normalize(vec_first);
+       Normalize(vec_second);
+       
+       edge_first->angle = saacos(Inpf(vec_first, vec_second));
+}
+
+/************************************ CONTROL BONES ****************************************************/
+
+static void RIG_addControlBone(RigGraph *rg, EditBone *bone)
+{
+       RigControl *ctrl = newRigControl(rg);
+       ctrl->bone = bone;
+       VECCOPY(ctrl->head, bone->head);
+       VECCOPY(ctrl->tail, bone->tail);
+       getEditBoneRollUpAxis(bone, bone->roll, ctrl->up_axis);
+       
+       BLI_ghash_insert(rg->controls_map, bone->name, ctrl);
+}
+
+static int RIG_parentControl(RigControl *ctrl, EditBone *link)
+{
+       if (link)
+       {
+               float offset[3];
+               int flag = 0;
+               
+               VecSubf(offset, ctrl->bone->head, link->head);
+
+               /* if root matches, check for direction too */          
+               if (Inpf(offset, offset) < 0.0001)
+               {
+                       float vbone[3], vparent[3];
+                       
+                       flag |= RIG_CTRL_FIT_ROOT;
+                       
+                       VecSubf(vbone, ctrl->bone->tail, ctrl->bone->head);
+                       VecSubf(vparent, link->tail, link->head);
+                       
+                       /* test for opposite direction */
+                       if (Inpf(vbone, vparent) > 0)
+                       {
+                               float nor[3];
+                               float len;
+                               
+                               Crossf(nor, vbone, vparent);
+                               
+                               len = Inpf(nor, nor);
+                               if (len < 0.0001)
+                               {
+                                       flag |= RIG_CTRL_FIT_BONE;
+                               }
+                       }
+               }
+               
+               /* Bail out if old one is automatically better */
+               if (flag < ctrl->flag)
+               {
+                       return 0;
+               }
+               
+               /* if there's already a link
+                *      overwrite only if new link is higher in the chain */
+               if (ctrl->link && flag == ctrl->flag)
+               {
+                       EditBone *bone = NULL;
+                       
+                       for (bone = ctrl->link; bone; bone = bone->parent)
+                       {
+                               /* if link is in the chain, break and use that one */
+                               if (bone == link)
+                               {
+                                       break;
+                               }
+                       }
+                       
+                       /* not in chain, don't update link */
+                       if (bone == NULL)
+                       {
+                               return 0;
+                       }
+               }
+               
+               
+               ctrl->link = link;
+               ctrl->flag = flag;
+               
+               VECCOPY(ctrl->offset, offset);
+               
+               return 1;
+       }
+       
+       return 0;
+}
+
+static void RIG_reconnectControlBones(RigGraph *rg)
+{
+       RigControl *ctrl;
+       int change = 1;
+       
+       /* first pass, link to deform bones */
+       for (ctrl = rg->controls.first; ctrl; ctrl = ctrl->next)
+       {
+               bPoseChannel *pchan;
+               bConstraint *con;
+               int found = 0;
+               
+               /* DO SOME MAGIC HERE */
+               for (pchan= rg->ob->pose->chanbase.first; pchan; pchan= pchan->next)
+               {
+                       for (con= pchan->constraints.first; con; con= con->next) 
+                       {
+                               bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
+                               ListBase targets = {NULL, NULL};
+                               bConstraintTarget *ct;
+                               
+                               /* constraint targets */
+                               if (cti && cti->get_constraint_targets)
+                               {
+                                       cti->get_constraint_targets(con, &targets);
+                                       
+                                       for (ct= targets.first; ct; ct= ct->next)
+                                       {
+                                               if ((ct->tar == rg->ob) && strcmp(ct->subtarget, ctrl->bone->name) == 0)
+                                               {
+                                                       /* SET bone link to bone corresponding to pchan */
+                                                       EditBone *link = BLI_ghash_lookup(rg->bones_map, pchan->name);
+                                                       
+                                                       found = RIG_parentControl(ctrl, link);
+                                               }
+                                       }
+                                       
+                                       if (cti->flush_constraint_targets)
+                                               cti->flush_constraint_targets(con, &targets, 0);
+                               }
+                       }
+               }
+
+               /* if not found yet, check parent */
+               if (found == 0)
+               {               
+                       if (ctrl->bone->parent)
+                       {
+                               /* make sure parent is a deforming bone
+                                * NULL if not
+                                *  */
+                               EditBone *link = BLI_ghash_lookup(rg->bones_map, ctrl->bone->parent->name);
+                               
+                               found = RIG_parentControl(ctrl, link);
+                       }
+                       
+                       /* check if bone is not superposed on another one */
+                       {
+                               RigArc *arc;
+                               RigArc *best_arc = NULL;
+                               EditBone *link = NULL;
+                               
+                               for (arc = rg->arcs.first; arc; arc = arc->next)
+                               {
+                                       RigEdge *edge;
+                                       for (edge = arc->edges.first; edge; edge = edge->next)
+                                       {
+                                               if (edge->bone)
+                                               {
+                                                       int fit = 0;
+                                                       
+                                                       fit = VecLenf(ctrl->bone->head, edge->bone->head) < 0.0001;
+                                                       fit = fit || VecLenf(ctrl->bone->tail, edge->bone->tail) < 0.0001;
+                                                       
+                                                       if (fit)
+                                                       {
+                                                               /* pick the bone on the arc with the lowest symmetry level
+                                                                * means you connect control to the trunk of the skeleton */
+                                                               if (best_arc == NULL || arc->symmetry_level < best_arc->symmetry_level)
+                                                               {
+                                                                       best_arc = arc;
+                                                                       link = edge->bone;
+                                                               }
+                                                       }
+                                               }
+                                       }
+                               }
+                               
+                               found = RIG_parentControl(ctrl, link);
+                       }
+               }
+               
+               /* if not found yet, check child */             
+               if (found == 0)
+               {
+                       RigArc *arc;
+                       RigArc *best_arc = NULL;
+                       EditBone *link = NULL;
+                       
+                       for (arc = rg->arcs.first; arc; arc = arc->next)
+                       {
+                               RigEdge *edge;
+                               for (edge = arc->edges.first; edge; edge = edge->next)
+                               {
+                                       if (edge->bone && edge->bone->parent == ctrl->bone)
+                                       {
+                                               /* pick the bone on the arc with the lowest symmetry level
+                                                * means you connect control to the trunk of the skeleton */
+                                               if (best_arc == NULL || arc->symmetry_level < best_arc->symmetry_level)
+                                               {
+                                                       best_arc = arc;
+                                                       link = edge->bone;
+                                               }
+                                       }
+                               }
+                       }
+                       
+                       found = RIG_parentControl(ctrl, link);
+               }
+
+       }
+       
+       
+       /* second pass, make chains in control bones */
+       while (change)
+       {
+               change = 0;
+               
+               printf("-------------------------\n");
+               
+               for (ctrl = rg->controls.first; ctrl; ctrl = ctrl->next)
+               {
+                       /* if control is not linked yet */
+                       if (ctrl->link == NULL)
+                       {
+                               bPoseChannel *pchan;
+                               bConstraint *con;
+                               RigControl *ctrl_parent = NULL;
+                               RigControl *ctrl_child;
+                               int found = 0;
+
+                               if (ctrl->bone->parent)
+                               {
+                                       ctrl_parent = BLI_ghash_lookup(rg->controls_map, ctrl->bone->parent->name);
+                               }
+
+                               /* check constraints first */
+                               
+                               /* DO SOME MAGIC HERE */
+                               for (pchan= rg->ob->pose->chanbase.first; pchan; pchan= pchan->next)
+                               {
+                                       for (con= pchan->constraints.first; con; con= con->next) 
+                                       {
+                                               bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
+                                               ListBase targets = {NULL, NULL};
+                                               bConstraintTarget *ct;
+                                               
+                                               /* constraint targets */
+                                               if (cti && cti->get_constraint_targets)
+                                               {
+                                                       cti->get_constraint_targets(con, &targets);
+                                                       
+                                                       for (ct= targets.first; ct; ct= ct->next)
+                                                       {
+                                                               if ((ct->tar == rg->ob) && strcmp(ct->subtarget, ctrl->bone->name) == 0)
+                                                               {
+                                                                       /* SET bone link to ctrl corresponding to pchan */
+                                                                       RigControl *link = BLI_ghash_lookup(rg->controls_map, pchan->name);
+
+                                                                       /* if owner is a control bone, link with it */                                                                  
+                                                                       if (link && link->link)
+                                                                       {
+                                                                               printf("%s -constraint- %s\n", ctrl->bone->name, link->bone->name);
+                                                                               RIG_parentControl(ctrl, link->bone);
+                                                                               found = 1;
+                                                                               break;
+                                                                       }
+                                                               }
+                                                       }
+                                                       
+                                                       if (cti->flush_constraint_targets)
+                                                               cti->flush_constraint_targets(con, &targets, 0);
+                                               }
+                                       }
+                               }                       
+
+                               if (found == 0)
+                               {
+                                       /* check if parent is already linked */
+                                       if (ctrl_parent && ctrl_parent->link)
+                                       {
+                                               printf("%s -parent- %s\n", ctrl->bone->name, ctrl_parent->bone->name);
+                                               RIG_parentControl(ctrl, ctrl_parent->bone);
+                                               change = 1;
+                                       }
+                                       else
+                                       {
+                                               /* check childs */
+                                               for (ctrl_child = rg->controls.first; ctrl_child; ctrl_child = ctrl_child->next)
+                                               {
+                                                       /* if a child is linked, link to that one */
+                                                       if (ctrl_child->link && ctrl_child->bone->parent == ctrl->bone)
+                                                       {
+                                                               printf("%s -child- %s\n", ctrl->bone->name, ctrl_child->bone->name);
+                                                               RIG_parentControl(ctrl, ctrl_child->bone);
+                                                               change = 1;
+                                                               break;
+                                                       }
+                                               }
+                                       }
+                               }
+                       }
+               }
+               
+       }
+}
+
+/*******************************************************************************************************/
+
+static void RIG_joinArcs(RigGraph *rg, RigNode *node, RigArc *joined_arc1, RigArc *joined_arc2)
+{
+       RigEdge *edge, *next_edge;
+       
+       /* ignore cases where joint is at start or end */
+       if (joined_arc1->head == joined_arc2->head || joined_arc1->tail == joined_arc2->tail)
+       {
+               return;
+       }
+       
+       /* swap arcs to make sure arc1 is before arc2 */
+       if (joined_arc1->head == joined_arc2->tail)
+       {
+               RigArc *tmp = joined_arc1;
+               joined_arc1 = joined_arc2;
+               joined_arc2 = tmp;
+       }
+       
+       for (edge = joined_arc2->edges.first; edge; edge = next_edge)
+       {
+               next_edge = edge->next;
+               
+               RIG_appendEdgeToArc(joined_arc1, edge);
+       }
+       
+       joined_arc1->tail = joined_arc2->tail;
+       
+       joined_arc2->edges.first = joined_arc2->edges.last = NULL;
+       
+       BLI_removeArc((BGraph*)rg, (BArc*)joined_arc2);
+       
+       BLI_removeNode((BGraph*)rg, (BNode*)node);
+}
+
+static void RIG_removeNormalNodes(RigGraph *rg)
+{
+       RigNode *node, *next_node;
+       
+       for (node = rg->nodes.first; node; node = next_node)
+       {
+               next_node = node->next;
+               
+               if (node->degree == 2)
+               {
+                       RigArc *arc, *joined_arc1 = NULL, *joined_arc2 = NULL;
+                       
+                       for (arc = rg->arcs.first; arc; arc = arc->next)
+                       {
+                               if (arc->head == node || arc->tail == node)
+                               {
+                                       if (joined_arc1 == NULL)
+                                       {
+                                               joined_arc1 = arc;
+                                       }
+                                       else
+                                       {
+                                               joined_arc2 = arc;
+                                               break;
+                                       }
+                               }
+                       }
+                       
+                       RIG_joinArcs(rg, node, joined_arc1, joined_arc2);
+               }
+       }
+}
+
+static void RIG_removeUneededOffsets(RigGraph *rg)
+{
+       RigArc *arc;
+       
+       for (arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               RigEdge *first_edge, *last_edge;
+               
+               first_edge = arc->edges.first;
+               last_edge = arc->edges.last;
+               
+               if (first_edge->bone == NULL)
+               {
+                       if (first_edge->bone == NULL && VecLenf(first_edge->tail, arc->head->p) <= 0.001)
+                       {
+                               BLI_remlink(&arc->edges, first_edge);
+                               MEM_freeN(first_edge);
+                       }
+                       else if (arc->head->degree == 1)
+                       {
+                               RigNode *new_node = (RigNode*)BLI_FindNodeByPosition((BGraph*)rg, first_edge->tail, 0.001);
+                               
+                               if (new_node)
+                               {
+                                       BLI_remlink(&arc->edges, first_edge);
+                                       MEM_freeN(first_edge);
+                                       BLI_replaceNodeInArc((BGraph*)rg, (BArc*)arc, (BNode*)new_node, (BNode*)arc->head);
+                               }
+                               else
+                               {
+                                       RigEdge *next_edge = first_edge->next;
+       
+                                       if (next_edge)
+                                       {
+                                               BLI_remlink(&arc->edges, first_edge);
+                                               MEM_freeN(first_edge);
+                                               
+                                               VECCOPY(arc->head->p, next_edge->head);
+                                       }
+                               }
+                       }
+                       else
+                       {
+                               /* check if all arc connected start with a null edge */
+                               RigArc *other_arc;
+                               for (other_arc = rg->arcs.first; other_arc; other_arc = other_arc->next)
+                               {
+                                       if (other_arc != arc)
+                                       {
+                                               RigEdge *test_edge;
+                                               if (other_arc->head == arc->head)
+                                               {
+                                                       test_edge = other_arc->edges.first;
+                                                       
+                                                       if (test_edge->bone != NULL)
+                                                       {
+                                                               break;
+                                                       }
+                                               }
+                                               else if (other_arc->tail == arc->head)
+                                               {
+                                                       test_edge = other_arc->edges.last;
+                                                       
+                                                       if (test_edge->bone != NULL)
+                                                       {
+                                                               break;
+                                                       }
+                                               }
+                                       }
+                               }
+                               
+                               if (other_arc == NULL)
+                               {
+                                       RigNode *new_node = (RigNode*)BLI_FindNodeByPosition((BGraph*)rg, first_edge->tail, 0.001);
+                                       
+                                       if (new_node)
+                                       {
+                                               /* remove null edge in other arcs too */
+                                               for (other_arc = rg->arcs.first; other_arc; other_arc = other_arc->next)
+                                               {
+                                                       if (other_arc != arc)
+                                                       {
+                                                               RigEdge *test_edge;
+                                                               if (other_arc->head == arc->head)
+                                                               {
+                                                                       BLI_replaceNodeInArc((BGraph*)rg, (BArc*)other_arc, (BNode*)new_node, (BNode*)other_arc->head);
+                                                                       test_edge = other_arc->edges.first;
+                                                                       BLI_remlink(&other_arc->edges, test_edge);
+                                                                       MEM_freeN(test_edge);
+                                                               }
+                                                               else if (other_arc->tail == arc->head)
+                                                               {
+                                                                       BLI_replaceNodeInArc((BGraph*)rg, (BArc*)other_arc, (BNode*)new_node, (BNode*)other_arc->tail);
+                                                                       test_edge = other_arc->edges.last;
+                                                                       BLI_remlink(&other_arc->edges, test_edge);
+                                                                       MEM_freeN(test_edge);
+                                                               }
+                                                       }
+                                               }
+                                               
+                                               BLI_remlink(&arc->edges, first_edge);
+                                               MEM_freeN(first_edge);
+                                               BLI_replaceNodeInArc((BGraph*)rg, (BArc*)arc, (BNode*)new_node, (BNode*)arc->head);
+                                       }
+                                       else
+                                       {
+                                               RigEdge *next_edge = first_edge->next;
+               
+                                               if (next_edge)
+                                               {
+                                                       BLI_remlink(&arc->edges, first_edge);
+                                                       MEM_freeN(first_edge);
+                                                       
+                                                       VECCOPY(arc->head->p, next_edge->head);
+                                                       
+                                                       /* remove null edge in other arcs too */
+                                                       for (other_arc = rg->arcs.first; other_arc; other_arc = other_arc->next)
+                                                       {
+                                                               if (other_arc != arc)
+                                                               {
+                                                                       RigEdge *test_edge;
+                                                                       if (other_arc->head == arc->head)
+                                                                       {
+                                                                               test_edge = other_arc->edges.first;
+                                                                               BLI_remlink(&other_arc->edges, test_edge);
+                                                                               MEM_freeN(test_edge);
+                                                                       }
+                                                                       else if (other_arc->tail == arc->head)
+                                                                       {
+                                                                               test_edge = other_arc->edges.last;
+                                                                               BLI_remlink(&other_arc->edges, test_edge);
+                                                                               MEM_freeN(test_edge);
+                                                                       }
+                                                               }
+                                                       }
+                                               }
+                                       }
+                               }
+                       }
+               }
+               
+               if (last_edge->bone == NULL)
+               {
+                       if (VecLenf(last_edge->head, arc->tail->p) <= 0.001)
+                       {
+                               BLI_remlink(&arc->edges, last_edge);
+                               MEM_freeN(last_edge);
+                       }
+                       else if (arc->tail->degree == 1)
+                       {
+                               RigNode *new_node = (RigNode*)BLI_FindNodeByPosition((BGraph*)rg, last_edge->head, 0.001);
+                               
+                               if (new_node)
+                               {
+                                       RigEdge *previous_edge = last_edge->prev;
+                                       
+                                       BLI_remlink(&arc->edges, last_edge);
+                                       MEM_freeN(last_edge);
+                                       BLI_replaceNodeInArc((BGraph*)rg, (BArc*)arc, (BNode*)new_node, (BNode*)arc->tail);
+                                       
+                                       /* set previous angle to 0, since there's no following edges */
+                                       if (previous_edge)
+                                       {
+                                               previous_edge->angle = 0;
+                                       }
+                               }
+                               else
+                               {
+                                       RigEdge *previous_edge = last_edge->prev;
+       
+                                       if (previous_edge)
+                                       {
+                                               BLI_remlink(&arc->edges, last_edge);
+                                               MEM_freeN(last_edge);
+                                               
+                                               VECCOPY(arc->tail->p, previous_edge->tail);
+                                               previous_edge->angle = 0;
+                                       }
+                               }
+                       }
+               }
+       }
+}
+
+static void RIG_arcFromBoneChain(RigGraph *rg, ListBase *list, EditBone *root_bone, RigNode *starting_node)
+{
+       EditBone *bone, *last_bone = root_bone;
+       RigArc *arc = NULL;
+       int contain_head = 0;
+       
+       for(bone = root_bone; bone; bone = nextEditBoneChild(list, bone, 0))
+       {
+               int nb_children;
+               
+               if ((bone->flag & BONE_NO_DEFORM) == 0)
+               {
+                       BLI_ghash_insert(rg->bones_map, bone->name, bone);
+               
+                       if (arc == NULL)
+                       {
+                               arc = newRigArc(rg);
+                               
+                               if (starting_node == NULL)
+                               {
+                                       starting_node = newRigNodeHead(rg, arc, root_bone->head);
+                               }
+                               else
+                               {
+                                       addRigNodeHead(rg, arc, starting_node);
+                               }
+                       }
+                       
+                       if (bone->parent && (bone->flag & BONE_CONNECTED) == 0)
+                       {
+                               RIG_addEdgeToArc(arc, bone->head, NULL);
+                       }
+                       
+                       RIG_addEdgeToArc(arc, bone->tail, bone);
+                       
+                       last_bone = bone;
+                       
+                       if (strcmp(bone->name, "head") == 0)
+                       {
+                               contain_head = 1;
+                       }
+               }
+               else if ((bone->flag & BONE_EDITMODE_LOCKED) == 0) /* ignore locked bones */
+               {
+                       RIG_addControlBone(rg, bone);
+               }
+               
+               nb_children = countEditBoneChildren(list, bone);
+               if (nb_children > 1)
+               {
+                       RigNode *end_node = NULL;
+                       int i;
+                       
+                       if (arc != NULL)
+                       {
+                               end_node = newRigNodeTail(rg, arc, bone->tail);
+                       }
+                       else
+                       {
+                               end_node = newRigNode(rg, bone->tail);
+                       }
+
+                       for (i = 0; i < nb_children; i++)
+                       {
+                               root_bone = nextEditBoneChild(list, bone, i);
+                               RIG_arcFromBoneChain(rg, list, root_bone, end_node);
+                       }
+                       
+                       /* arc ends here, break */
+                       break;
+               }
+       }
+       
+       /* If the loop exited without forking */
+       if (arc != NULL && bone == NULL)
+       {
+               newRigNodeTail(rg, arc, last_bone->tail);
+       }
+
+       if (contain_head)
+       {
+               rg->head = arc->tail;
+       }
+}
+
+/*******************************************************************************************************/
+static void RIG_findHead(RigGraph *rg)
+{
+       if (rg->head == NULL)
+       {
+               if (BLI_countlist(&rg->arcs) == 1)
+               {
+                       RigArc *arc = rg->arcs.first;
+                       
+                       rg->head = (RigNode*)arc->head;
+               }
+               else
+               {
+                       RigArc *arc;
+                       
+                       for (arc = rg->arcs.first; arc; arc = arc->next)
+                       {
+                               RigEdge *edge = arc->edges.last;
+                               
+                               if (edge->bone->flag & (BONE_TIPSEL|BONE_SELECTED))
+                               {
+                                       rg->head = arc->tail;
+                                       break;
+                               }
+                       }
+               }
+               
+               if (rg->head == NULL)
+               {
+                       rg->head = rg->nodes.first;
+               }
+       }
+}
+
+/*******************************************************************************************************/
+
+void RIG_printNode(RigNode *node, char name[])
+{
+       printf("%s %p %i <%0.3f, %0.3f, %0.3f>\n", name, node, node->degree, node->p[0], node->p[1], node->p[2]);
+       
+       if (node->symmetry_flag & SYM_TOPOLOGICAL)
+       {
+               if (node->symmetry_flag & SYM_AXIAL)
+                       printf("Symmetry AXIAL\n");
+               else if (node->symmetry_flag & SYM_RADIAL)
+                       printf("Symmetry RADIAL\n");
+                       
+               printvecf("symmetry axis", node->symmetry_axis);
+       }
+}
+
+void RIG_printArcBones(RigArc *arc)
+{
+       RigEdge *edge;
+
+       for (edge = arc->edges.first; edge; edge = edge->next)
+       {
+               if (edge->bone)
+                       printf("%s ", edge->bone->name);
+               else
+                       printf("---- ");
+       }
+       printf("\n");
+}
+
+void RIG_printCtrl(RigControl *ctrl, char *indent)
+{
+       char text[128];
+       
+       printf("%sBone: %s\n", indent, ctrl->bone->name);
+       printf("%sLink: %s\n", indent, ctrl->link ? ctrl->link->name : "!NONE!");
+       
+       sprintf(text, "%soffset", indent);
+       printvecf(text, ctrl->offset);
+       
+       printf("%sFlag: %i\n", indent, ctrl->flag);
+}
+
+void RIG_printLinkedCtrl(RigGraph *rg, EditBone *bone, int tabs)
+{
+       RigControl *ctrl;
+       char indent[64];
+       char *s = indent;
+       int i;
+       
+       for (i = 0; i < tabs; i++)
+       {
+               s[0] = '\t';
+               s++;
+       }
+       s[0] = 0;
+       
+       for (ctrl = rg->controls.first; ctrl; ctrl = ctrl->next)
+       {
+               if (ctrl->link == bone)
+               {
+                       RIG_printCtrl(ctrl, indent);
+                       RIG_printLinkedCtrl(rg, ctrl->bone, tabs + 1);
+               }
+       }
+}
+
+void RIG_printArc(RigGraph *rg, RigArc *arc)
+{
+       RigEdge *edge;
+
+       RIG_printNode((RigNode*)arc->head, "head");
+
+       for (edge = arc->edges.first; edge; edge = edge->next)
+       {
+               printf("\tinner joints %0.3f %0.3f %0.3f\n", edge->tail[0], edge->tail[1], edge->tail[2]);
+               printf("\t\tlength %f\n", edge->length);
+               printf("\t\tangle %f\n", edge->angle * 180 / M_PI);
+               if (edge->bone)
+               {
+                       printf("\t\t%s\n", edge->bone->name);
+                       RIG_printLinkedCtrl(rg, edge->bone, 3);
+               }
+       }       
+       printf("symmetry level: %i flag: %i group %i\n", arc->symmetry_level, arc->symmetry_flag, arc->symmetry_group);
+
+       RIG_printNode((RigNode*)arc->tail, "tail");
+}
+
+void RIG_printGraph(RigGraph *rg)
+{
+       RigArc *arc;
+
+       printf("---- ARCS ----\n");
+       for (arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               RIG_printArc(rg, arc);  
+               printf("\n");
+       }
+
+       if (rg->head)
+       {
+               RIG_printNode(rg->head, "HEAD NODE:");
+       }
+       else
+       {
+               printf("HEAD NODE: NONE\n");
+       }       
+}
+
+/*******************************************************************************************************/
+
+static RigGraph *armatureToGraph(Object *ob, bArmature *arm)
+{
+       EditBone *ebone;
+       RigGraph *rg;
+       
+       rg = newRigGraph();
+       
+       make_boneList(&rg->editbones, &arm->bonebase, NULL);
+       rg->ob = ob;
+
+       /* Do the rotations */
+       for (ebone = rg->editbones.first; ebone; ebone=ebone->next){
+               if (ebone->parent == NULL)
+               {
+                       RIG_arcFromBoneChain(rg, &rg->editbones, ebone, NULL);
+               }
+       }
+       
+       BLI_removeDoubleNodes((BGraph*)rg, 0.001);
+       
+       RIG_removeNormalNodes(rg);
+       
+       RIG_removeUneededOffsets(rg);
+       
+       BLI_buildAdjacencyList((BGraph*)rg);
+       
+       RIG_findHead(rg);
+
+       BLI_markdownSymmetry((BGraph*)rg, (BNode*)rg->head, G.scene->toolsettings->skgen_symmetry_limit);
+       
+       RIG_reconnectControlBones(rg); /* after symmetry, because we use levels to find best match */
+       
+       if (BLI_isGraphCyclic((BGraph*)rg))
+       {
+               printf("armature cyclic\n");
+       }
+       
+       return rg;
+}
+
+/************************************ GENERATING *****************************************************/
+
+static EditBone *add_editbonetolist(char *name, ListBase *list)
+{
+       EditBone *bone= MEM_callocN(sizeof(EditBone), "eBone");
+       
+       BLI_strncpy(bone->name, name, 32);
+       unique_editbone_name(list, bone->name);
+       
+       BLI_addtail(list, bone);
+       
+       bone->flag |= BONE_TIPSEL;
+       bone->weight= 1.0F;
+       bone->dist= 0.25F;
+       bone->xwidth= 0.1;
+       bone->zwidth= 0.1;
+       bone->ease1= 1.0;
+       bone->ease2= 1.0;
+       bone->rad_head= 0.10;
+       bone->rad_tail= 0.05;
+       bone->segments= 1;
+       bone->layer=  1;//arm->layer;
+       
+       return bone;
+}
+
+EditBone * generateBonesForArc(RigGraph *rigg, ReebArc *arc, ReebNode *head, ReebNode *tail)
+{
+       ReebArcIterator iter;
+       float n[3];
+       float ADAPTIVE_THRESHOLD = G.scene->toolsettings->skgen_correlation_limit;
+       EditBone *lastBone = NULL;
+       
+       /* init iterator to get start and end from head */
+       initArcIterator(&iter, arc, head);
+       
+       /* Calculate overall */
+       VecSubf(n, arc->buckets[iter.end].p, head->p);
+       
+       if (1 /* G.scene->toolsettings->skgen_options & SKGEN_CUT_CORRELATION */ )
+       {
+               EmbedBucket *bucket = NULL;
+               EmbedBucket *previous = NULL;
+               EditBone *child = NULL;
+               EditBone *parent = NULL;
+               float normal[3] = {0, 0, 0};
+               float avg_normal[3];
+               int total = 0;
+               int boneStart = iter.start;
+               
+               parent = add_editbonetolist("Bone", &rigg->editbones);
+               parent->flag = BONE_SELECTED|BONE_TIPSEL|BONE_ROOTSEL;
+               VECCOPY(parent->head, head->p);
+               
+               for (previous = nextBucket(&iter), bucket = nextBucket(&iter);
+                       bucket;
+                       previous = bucket, bucket = nextBucket(&iter))
+               {
+                       float btail[3];
+                       float value = 0;
+
+                       if (G.scene->toolsettings->skgen_options & SKGEN_STICK_TO_EMBEDDING)
+                       {
+                               VECCOPY(btail, bucket->p);
+                       }
+                       else
+                       {
+                               float length;
+                               
+                               /* Calculate normal */
+                               VecSubf(n, bucket->p, parent->head);
+                               length = Normalize(n);
+                               
+                               total += 1;
+                               VecAddf(normal, normal, n);
+                               VECCOPY(avg_normal, normal);
+                               VecMulf(avg_normal, 1.0f / total);
+                                
+                               VECCOPY(btail, avg_normal);
+                               VecMulf(btail, length);
+                               VecAddf(btail, btail, parent->head);
+                       }
+
+                       if (G.scene->toolsettings->skgen_options & SKGEN_ADAPTIVE_DISTANCE)
+                       {
+                               value = calcDistance(arc, boneStart, iter.index, parent->head, btail);
+                       }
+                       else
+                       {
+                               float n[3];
+                               
+                               VecSubf(n, btail, parent->head);
+                               value = calcVariance(arc, boneStart, iter.index, parent->head, n);
+                       }
+
+                       if (value > ADAPTIVE_THRESHOLD)
+                       {
+                               VECCOPY(parent->tail, btail);
+
+                               child = add_editbonetolist("Bone", &rigg->editbones);
+                               VECCOPY(child->head, parent->tail);
+                               child->parent = parent;
+                               child->flag |= BONE_CONNECTED|BONE_SELECTED|BONE_TIPSEL|BONE_ROOTSEL;
+                               
+                               parent = child; // new child is next parent
+                               boneStart = iter.index; // start from end
+                               
+                               normal[0] = normal[1] = normal[2] = 0;
+                               total = 0;
+                       }
+               }
+
+               VECCOPY(parent->tail, tail->p);
+               
+               lastBone = parent; /* set last bone in the chain */
+       }
+       
+       return lastBone;
+}
+
+void generateMissingArcsFromNode(RigGraph *rigg, ReebNode *node, int multi_level_limit)
+{
+       while (node->multi_level > multi_level_limit && node->link_up)
+       {
+               node = node->link_up;
+       }
+       
+       while (node->multi_level < multi_level_limit && node->link_down)
+       {
+               node = node->link_down;
+       }
+       
+       if (node->multi_level == multi_level_limit)
+       {
+               int i;
+               
+               for (i = 0; i < node->degree; i++)
+               {
+                       ReebArc *earc = node->arcs[i];
+                       
+                       if (earc->flag == ARC_FREE && earc->head == node)
+                       {
+                               ReebNode *other = BIF_otherNodeFromIndex(earc, node);
+                               
+                               earc->flag = ARC_USED;
+                               
+                               generateBonesForArc(rigg, earc, node, other);
+                               generateMissingArcsFromNode(rigg, other, multi_level_limit);
+                       }
+               }
+       }
+}
+
+void generateMissingArcs(RigGraph *rigg)
+{
+       ReebGraph *reebg = rigg->link_mesh;
+       int multi_level_limit = 5;
+       
+       for (reebg = rigg->link_mesh; reebg; reebg = reebg->link_up)
+       {
+               ReebArc *earc;
+               
+               for (earc = reebg->arcs.first; earc; earc = earc->next)
+               {
+                       if (earc->flag == ARC_USED)
+                       {
+                               generateMissingArcsFromNode(rigg, earc->head, multi_level_limit);
+                               generateMissingArcsFromNode(rigg, earc->tail, multi_level_limit);
+                       }
+               }
+       }
+}
+
+/************************************ RETARGETTING *****************************************************/
+
+static void repositionControl(RigGraph *rigg, RigControl *ctrl, float head[3], float tail[3], float qrot[4], float resize)
+{
+       RigControl *ctrl_child;
+       float parent_offset[3], tail_offset[3];
+       
+       VecSubf(tail_offset, ctrl->tail, ctrl->head);
+       VecMulf(tail_offset, resize);
+       
+       VECCOPY(parent_offset, ctrl->offset);
+       VecMulf(parent_offset, resize);
+       
+       QuatMulVecf(qrot, parent_offset);
+       QuatMulVecf(qrot, tail_offset);
+       
+       VecAddf(ctrl->bone->head, head, parent_offset); 
+       VecAddf(ctrl->bone->tail, ctrl->bone->head, tail_offset);
+       ctrl->bone->roll = getNewBoneRoll(ctrl->bone, ctrl->up_axis, qrot);
+       
+       ctrl->flag |= RIG_CTRL_DONE;
+
+       /* Cascade to connected control bones */
+       for (ctrl_child = rigg->controls.first; ctrl_child; ctrl_child = ctrl_child->next)
+       {
+               if (ctrl_child->link == ctrl->bone)
+               {
+                       repositionControl(rigg, ctrl_child, ctrl->bone->head, ctrl->bone->tail, qrot, resize);
+               }
+       }
+
+}
+
+static void repositionBone(RigGraph *rigg, RigEdge *edge, float vec0[3], float vec1[3])
+{
+       EditBone *bone;
+       RigControl *ctrl;
+       float qrot[4], resize;
+       float v1[3], v2[3];
+       float l1, l2;
+       
+       bone = edge->bone;
+       
+       VecSubf(v1, edge->tail, edge->head);
+       VecSubf(v2, vec1, vec0);
+       
+       l1 = Normalize(v1);
+       l2 = Normalize(v2);
+
+       resize = l2 / l1;
+       
+       RotationBetweenVectorsToQuat(qrot, v1, v2);
+       
+       for (ctrl = rigg->controls.first; ctrl; ctrl = ctrl->next)
+       {
+               if (ctrl->link == bone)
+               {
+                       repositionControl(rigg, ctrl, vec0, vec1, qrot, resize);
+               }
+       }
+       
+       VECCOPY(bone->head, vec0);
+       VECCOPY(bone->tail, vec1);
+       bone->roll = getNewBoneRoll(bone, edge->up_axis, qrot);
+}
+
+static RetargetMode detectArcRetargetMode(RigArc *arc);
+static void retargetArctoArcLength(RigGraph *rigg, RigArc *iarc, RigNode *inode_start);
+
+
+static RetargetMode detectArcRetargetMode(RigArc *iarc)
+{
+       RetargetMode mode = RETARGET_AGGRESSIVE;
+       ReebArc *earc = iarc->link_mesh;
+       RigEdge *edge;
+       int large_angle = 0;
+       float avg_angle = 0;
+       float avg_length = 0;
+       int nb_edges = 0;
+       
+       
+       for (edge = iarc->edges.first; edge; edge = edge->next)
+       {
+               avg_angle += edge->angle;
+               nb_edges++;
+       }
+       
+       avg_angle /= nb_edges - 1; /* -1 because last edge doesn't have an angle */
+
+       avg_length = iarc->length / nb_edges;
+       
+       
+       if (nb_edges > 2)
+       {
+               for (edge = iarc->edges.first; edge; edge = edge->next)
+               {
+                       if (fabs(edge->angle - avg_angle) > M_PI / 6)
+                       {
+                               large_angle = 1;
+                       }
+               }
+       }
+       else if (nb_edges == 2 && avg_angle > 0)
+       {
+               large_angle = 1;
+       }
+               
+       
+       if (large_angle == 0)
+       {
+               mode = RETARGET_LENGTH;
+       }
+       
+       if (earc->bcount <= (iarc->count - 1))
+       {
+               mode = RETARGET_LENGTH;
+       }
+       
+       mode = RETARGET_AGGRESSIVE;
+       
+       return mode;
+}
+
+#ifndef USE_THREADS
+static void printCostCube(float *cost_cube, int nb_joints)
+{
+       int i;
+       
+       for (i = 0; i < nb_joints; i++)
+       {
+               printf("%0.3f ", cost_cube[3 * i]);
+       }
+       printf("\n");
+
+       for (i = 0; i < nb_joints; i++)
+       {
+               printf("%0.3f ", cost_cube[3 * i + 1]);
+       }
+       printf("\n");
+
+       for (i = 0; i < nb_joints; i++)
+       {
+               printf("%0.3f ", cost_cube[3 * i + 2]);
+       }
+       printf("\n");
+}
+
+static void printMovesNeeded(int *positions, int nb_positions)
+{
+       int moves = 0;
+       int i;
+       
+       for (i = 0; i < nb_positions; i++)
+       {
+               moves += positions[i] - (i + 1);
+       }
+       
+       printf("%i moves needed\n", moves);
+}
+
+static void printPositions(int *positions, int nb_positions)
+{
+       int i;
+       
+       for (i = 0; i < nb_positions; i++)
+       {
+               printf("%i ", positions[i]);
+       }
+       printf("\n");
+}
+#endif
+
+#define MAX_COST 100 /* FIX ME */
+
+static float costDistance(ReebArcIterator *iter, float *vec0, float *vec1, int i0, int i1)
+{
+       EmbedBucket *bucket = NULL;
+       float max_dist = 0;
+       float v1[3], v2[3], c[3];
+       float v1_inpf;
+
+       if (G.scene->toolsettings->skgen_retarget_distance_weight > 0)
+       {
+               VecSubf(v1, vec0, vec1);
+               
+               v1_inpf = Inpf(v1, v1);
+               
+               if (v1_inpf > 0)
+               {
+                       int j;
+                       for (j = i0 + 1; j < i1 - 1; j++)
+                       {
+                               float dist;
+                               
+                               bucket = peekBucket(iter, j);
+       
+                               VecSubf(v2, bucket->p, vec1);
+               
+                               Crossf(c, v1, v2);
+                               
+                               dist = Inpf(c, c) / v1_inpf;
+                               
+                               max_dist = dist > max_dist ? dist : max_dist;
+                       }
+                       
+                       return G.scene->toolsettings->skgen_retarget_distance_weight * max_dist;
+               }
+               else
+               {
+                       return MAX_COST;
+               }
+       }
+       else
+       {
+               return 0;
+       }
+}
+
+static float costAngle(float original_angle, float vec_first[3], float vec_second[3])
+{
+       if (G.scene->toolsettings->skgen_retarget_angle_weight > 0)
+       {
+               float current_angle;
+               
+               if (!VecIsNull(vec_first) && !VecIsNull(vec_second))
+               {
+                       current_angle = saacos(Inpf(vec_first, vec_second));
+
+                       return G.scene->toolsettings->skgen_retarget_angle_weight * fabs(current_angle - original_angle);
+               }
+               else
+               {
+                       return G.scene->toolsettings->skgen_retarget_angle_weight * M_PI;
+               }
+       }
+       else
+       {
+               return 0;
+       }
+}
+
+static float costLength(float original_length, float current_length)
+{
+       if (current_length == 0)
+       {
+               return MAX_COST;
+       }
+       else
+       {
+               float length_ratio = fabs((current_length - original_length) / original_length);
+               return G.scene->toolsettings->skgen_retarget_length_weight * length_ratio * length_ratio;
+       }
+}
+
+static float calcCostLengthDistance(ReebArcIterator *iter, float **vec_cache, RigEdge *edge, float *vec1, float *vec2, int i1, int i2)
+{
+       float vec[3];
+       float length;
+
+       VecSubf(vec, vec2, vec1);
+       length = Normalize(vec);
+
+       return costLength(edge->length, length) + costDistance(iter, vec1, vec2, i1, i2);
+}
+
+static float calcCostAngleLengthDistance(ReebArcIterator *iter, float **vec_cache, RigEdge *edge, float *vec0, float *vec1, float *vec2, int i1, int i2)
+{
+       float vec_second[3], vec_first[3];
+       float length2;
+       float new_cost = 0;
+
+       VecSubf(vec_second, vec2, vec1);
+       length2 = Normalize(vec_second);
+
+
+       /* Angle cost */        
+       if (edge->prev)
+       {
+               VecSubf(vec_first, vec1, vec0); 
+               Normalize(vec_first);
+               
+               new_cost += costAngle(edge->prev->angle, vec_first, vec_second);
+       }
+
+       /* Length cost */
+       new_cost += costLength(edge->length, length2);
+
+       /* Distance cost */
+       new_cost += costDistance(iter, vec1, vec2, i1, i2);
+
+       return new_cost;
+}
+
+static float calcCost(ReebArcIterator *iter, RigEdge *e1, RigEdge *e2, float *vec0, float *vec1, float *vec2, int i0, int i1, int i2)
+{
+       float vec_second[3], vec_first[3];
+       float length1, length2;
+       float new_cost = 0;
+
+       VecSubf(vec_second, vec2, vec1);
+       length2 = Normalize(vec_second);
+
+       VecSubf(vec_first, vec1, vec0); 
+       length1 = Normalize(vec_first);
+
+       /* Angle cost */        
+       new_cost += costAngle(e1->angle, vec_first, vec_second);
+
+       /* Length cost */
+       new_cost += costLength(e1->length, length1);
+       new_cost += costLength(e2->length, length2);
+
+       /* Distance cost */
+       new_cost += costDistance(iter, vec0, vec1, i0, i1);
+       new_cost += costDistance(iter, vec1, vec2, i1, i2);
+
+       return new_cost;
+}
+
+static void calcGradient(RigEdge *e1, RigEdge *e2, ReebArcIterator *iter, int index, int nb_joints, float *cost_cube, int *positions, float **vec_cache)
+{
+       EmbedBucket *bucket = NULL;
+       float *vec0, *vec1, *vec2;
+       float current_cost;
+       int i0, i1, i2;
+       int next_position;
+
+       vec0 = vec_cache[index];
+       vec1 = vec_cache[index + 1];
+       vec2 = vec_cache[index + 2];
+       
+       if (index == 0)
+       {
+               i0 = 0;
+       }
+       else
+       {
+               i0 = positions[index - 1];
+       }
+       
+       i1 = positions[index];
+       
+       if (index +1 == nb_joints)
+       {
+               i2 = iter->length;
+       }
+       else
+       {
+               i2 = positions[index + 1];
+       }
+
+
+       current_cost = calcCost(iter, e1, e2, vec0, vec1, vec2, i0, i1, i2);
+       cost_cube[index * 3 + 1] = current_cost;
+       
+       next_position = positions[index] + 1;
+       
+       if (index + 1 < nb_joints && next_position == positions[index + 1])
+       {
+               cost_cube[index * 3 + 2] = MAX_COST;
+       }
+       else if (next_position > iter->length) /* positions are indexed at 1, so length is last */
+       {
+               cost_cube[index * 3 + 2] = MAX_COST;
+       }
+       else
+       {
+               bucket = peekBucket(iter, next_position);
+               
+               if (bucket == NULL)
+               {
+                       cost_cube[index * 3 + 2] = MAX_COST;
+               }
+               else
+               {
+                       vec1 = bucket->p;
+                       
+                       cost_cube[index * 3 + 2] = calcCost(iter, e1, e2, vec0, vec1, vec2, i0, next_position, i2) - current_cost;
+               }
+       }
+
+       next_position = positions[index] - 1;
+       
+       if (index - 1 > -1 && next_position == positions[index - 1])
+       {
+               cost_cube[index * 3] = MAX_COST;
+       }
+       else if (next_position < 1) /* positions are indexed at 1, so 1 is first */
+       {
+               cost_cube[index * 3] = MAX_COST;
+       }
+       else
+       {
+               bucket = peekBucket(iter, next_position);
+               
+               if (bucket == NULL)
+               {
+                       cost_cube[index * 3] = MAX_COST;
+               }
+               else
+               {
+                       vec1 = bucket->p;
+                       
+                       cost_cube[index * 3] = calcCost(iter, e1, e2, vec0, vec1, vec2, i0, next_position, i2) - current_cost;
+               }
+       }
+}
+
+static float probability(float delta_cost, float temperature)
+{
+       if (delta_cost < 0)
+       {
+               return 1;
+       }
+       else
+       {
+               return (float)exp(delta_cost / temperature);
+       }
+}
+
+static int neighbour(int nb_joints, float *cost_cube, int *moving_joint, int *moving_direction)
+{
+       int total = 0;
+       int chosen = 0;
+       int i;
+       
+       for (i = 0; i < nb_joints; i++)
+       {
+               if (cost_cube[i * 3] < MAX_COST)
+               {
+                       total++;
+               }
+               
+               if (cost_cube[i * 3 + 2] < MAX_COST)
+               {
+                       total++;
+               }
+       }
+       
+       if (total == 0)
+       {
+               return 0;
+       }
+       
+       chosen = (int)(BLI_drand() * total);
+       
+       for (i = 0; i < nb_joints; i++)
+       {
+               if (cost_cube[i * 3] < MAX_COST)
+               {
+                       if (chosen == 0)
+                       {
+                               *moving_joint = i;
+                               *moving_direction = -1;
+                               break;
+                       }
+                       chosen--;
+               }
+               
+               if (cost_cube[i * 3 + 2] < MAX_COST)
+               {
+                       if (chosen == 0)
+                       {
+                               *moving_joint = i;
+                               *moving_direction = 1;
+                               break;
+                       }
+                       chosen--;
+               }
+       }
+       
+       return 1;
+}
+
+static int indexMemoNode(int nb_positions, int previous, int current, int joints_left)
+{
+       return joints_left * nb_positions * nb_positions + current * nb_positions + previous;
+}
+
+static void copyMemoPositions(int *positions, MemoNode *table, int nb_positions, int joints_left)
+{
+       int previous = 0, current = 0;
+       int i = 0;
+       
+       for (i = 0; joints_left > 0; joints_left--, i++)
+       {
+               MemoNode *node;
+               node = table + indexMemoNode(nb_positions, previous, current, joints_left);
+               
+               positions[i] = node->next;
+               
+               previous = current;
+               current = node->next;
+       }
+}
+
+static MemoNode * solveJoints(MemoNode *table, ReebArcIterator *iter, float **vec_cache, int nb_joints, int nb_positions, int previous, int current, RigEdge *edge, int joints_left)
+{
+       MemoNode *node;
+       int index = indexMemoNode(nb_positions, previous, current, joints_left);
+       
+       node = table + index;
+       
+       if (node->weight != 0)
+       {
+               return node;
+       }
+       else if (joints_left == 0)
+       {
+               float *vec1 = vec_cache[current];
+               float *vec2 = vec_cache[nb_positions + 1];
+
+               node->weight = calcCostLengthDistance(iter, vec_cache, edge, vec1, vec2, current, iter->length);
+
+               return node;
+       }
+       else
+       {
+               MemoNode *min_node = NULL;
+               float *vec0 = vec_cache[previous];
+               float *vec1 = vec_cache[current];
+               float min_weight;
+               int min_next;
+               int next;
+               
+               for (next = current + 1; next <= nb_positions - (joints_left - 1); next++)
+               {
+                       MemoNode *next_node;
+                       float *vec2 = vec_cache[next];
+                       float weight = 0;
+                       
+                       /* ADD WEIGHT OF PREVIOUS - CURRENT - NEXT triple */
+                       weight = calcCostAngleLengthDistance(iter, vec_cache, edge, vec0, vec1, vec2, current, next);
+                       
+                       if (weight >= MAX_COST)
+                       {
+                               continue;
+                       }
+                       
+                       /* add node weight */
+                       next_node = solveJoints(table, iter, vec_cache, nb_joints, nb_positions, current, next, edge->next, joints_left - 1);
+                       weight += next_node->weight;
+                       
+                       if (min_node == NULL || weight < min_weight)
+                       {
+                               min_weight = weight;
+                               min_node = next_node;
+                               min_next = next;
+                       }
+               }
+               
+               if (min_node)
+               {
+                       node->weight = min_weight;
+                       node->next = min_next;
+                       return node;
+               }
+               else
+               {
+                       node->weight = MAX_COST;
+                       return node;
+               }
+       }
+       
+}
+
+static int testFlipArc(RigArc *iarc, RigNode *inode_start)
+{
+       ReebArc *earc = iarc->link_mesh;
+       ReebNode *enode_start = BIF_NodeFromIndex(earc, inode_start->link_mesh);
+       
+       /* no flip needed if both nodes are the same */
+       if ((enode_start == earc->head && inode_start == iarc->head) || (enode_start == earc->tail && inode_start == iarc->tail))
+       {
+               return 0;
+       }
+       else
+       {
+               return 1;
+       }
+}
+
+static void retargetArctoArcAggresive(RigGraph *rigg, RigArc *iarc, RigNode *inode_start)
+{
+       ReebArcIterator iter;
+       RigEdge *edge;
+       EmbedBucket *bucket = NULL;
+       ReebNode *node_start, *node_end;
+       ReebArc *earc = iarc->link_mesh;
+       float min_cost = FLT_MAX;
+       float *vec0, *vec1, *vec2;
+       float **vec_cache;
+       float *cost_cache;
+       int *best_positions;
+       int *positions;
+       int nb_edges = BLI_countlist(&iarc->edges);
+       int nb_joints = nb_edges - 1;
+       RetargetMethod method = G.scene->toolsettings->skgen_optimisation_method;
+       int i;
+       
+       if (nb_joints > earc->bcount)
+       {
+               printf("NOT ENOUGH BUCKETS!\n");
+               return;
+       }
+
+       positions = MEM_callocN(sizeof(int) * nb_joints, "Aggresive positions");
+       best_positions = MEM_callocN(sizeof(int) * nb_joints, "Best Aggresive positions");
+       cost_cache = MEM_callocN(sizeof(float) * nb_edges, "Cost cache");
+       vec_cache = MEM_callocN(sizeof(float*) * (nb_edges + 1), "Vec cache");
+       
+       if (testFlipArc(iarc, inode_start))
+       {
+               node_start = earc->tail;
+               node_end = earc->head;
+       }
+       else
+       {
+               node_start = earc->head;
+               node_end = earc->tail;
+       }
+       
+       /* init with first values */
+       for (i = 0; i < nb_joints; i++)
+       {
+               positions[i] = i + 1;
+               //positions[i] = (earc->bcount / nb_edges) * (i + 1);
+       }
+       
+       /* init cost cache */
+       for (i = 0; i < nb_edges; i++)
+       {
+               cost_cache[i] = 0;
+       }
+       
+       vec_cache[0] = node_start->p;
+       vec_cache[nb_edges] = node_end->p;
+
+       if (method == METHOD_MEMOIZE)
+       {
+               int nb_positions = earc->bcount;
+               int nb_memo_nodes = nb_positions * nb_positions * (nb_joints + 1);
+               MemoNode *table = MEM_callocN(nb_memo_nodes * sizeof(MemoNode), "memoization table");
+               MemoNode *result;
+               float **positions_cache = MEM_callocN(sizeof(float*) * (nb_positions + 2), "positions cache");
+               int i;
+               
+               positions_cache[0] = node_start->p;
+               positions_cache[nb_positions + 1] = node_end->p;
+               
+               initArcIterator(&iter, earc, node_start);
+
+               for (i = 1; i <= nb_positions; i++)
+               {
+                       EmbedBucket *bucket = peekBucket(&iter, i);
+                       positions_cache[i] = bucket->p;
+               }
+
+               result = solveJoints(table, &iter, positions_cache, nb_joints, earc->bcount, 0, 0, iarc->edges.first, nb_joints);
+               
+               min_cost = result->weight;
+               copyMemoPositions(best_positions, table, earc->bcount, nb_joints);
+               
+               MEM_freeN(table);
+               MEM_freeN(positions_cache);
+       }
+       /* BRUTE FORCE */
+       else if (method == METHOD_BRUTE_FORCE)
+       {
+               int last_index = 0;
+               int first_pass = 1;
+               int must_move = nb_joints - 1;
+               
+               while(1)
+               {
+                       float cost = 0;
+                       int need_calc = 0;
+                       
+                       /* increment to next possible solution */
+                       
+                       i = nb_joints - 1;
+       
+                       if (first_pass)
+                       {
+                               need_calc = 0;
+                               first_pass = 0;
+                       }
+                       else
+                       {
+                               /* increment positions, starting from the last one
+                                * until a valid increment is found
+                                * */
+                               for (i = must_move; i >= 0; i--)
+                               {
+                                       int remaining_joints = nb_joints - (i + 1); 
+                                       
+                                       positions[i] += 1;
+                                       need_calc = i;
+                                       
+                                       if (positions[i] + remaining_joints <= earc->bcount)
+                                       {
+                                               break;
+                                       }
+                               }
+                       }
+       
+                       if (i == -1)
+                       {
+                               break;
+                       }
+                       
+                       /* reset joints following the last increment*/
+                       for (i = i + 1; i < nb_joints; i++)
+                       {
+                               positions[i] = positions[i - 1] + 1;
+                       }
+               
+                       /* calculating cost */
+                       initArcIterator(&iter, earc, node_start);
+                       
+                       vec0 = NULL;
+                       vec1 = node_start->p;
+                       vec2 = NULL;
+                       
+                       for (edge = iarc->edges.first, i = 0, last_index = 0;
+                                edge;
+                                edge = edge->next, i += 1)
+                       {
+       
+                               if (i >= need_calc)
+                               { 
+                                       float vec_first[3], vec_second[3];
+                                       float length1, length2;
+                                       float new_cost = 0;
+                                       int i1, i2;
+                                       
+                                       if (i < nb_joints)
+                                       {
+                                               i2 = positions[i];
+                                               bucket = peekBucket(&iter, positions[i]);
+                                               vec2 = bucket->p;
+                                               vec_cache[i + 1] = vec2; /* update cache for updated position */
+                                       }
+                                       else
+                                       {
+                                               i2 = iter.length;
+                                               vec2 = node_end->p;
+                                       }
+                                       
+                                       if (i > 0)
+                                       {
+                                               i1 = positions[i - 1];
+                                       }
+                                       else
+                                       {
+                                               i1 = 1;
+                                       }
+                                       
+                                       vec1 = vec_cache[i];
+                                       
+       
+                                       VecSubf(vec_second, vec2, vec1);
+                                       length2 = Normalize(vec_second);
+               
+                                       /* check angle */
+                                       if (i != 0 && G.scene->toolsettings->skgen_retarget_angle_weight > 0)
+                                       {
+                                               RigEdge *previous = edge->prev;
+                                               
+                                               vec0 = vec_cache[i - 1];
+                                               VecSubf(vec_first, vec1, vec0); 
+                                               length1 = Normalize(vec_first);
+                                               
+                                               /* Angle cost */        
+                                               new_cost += costAngle(previous->angle, vec_first, vec_second);
+                                       }
+               
+                                       /* Length Cost */
+                                       new_cost += costLength(edge->length, length2);
+                                       
+                                       /* Distance Cost */
+                                       new_cost += costDistance(&iter, vec1, vec2, i1, i2);
+                                       
+                                       cost_cache[i] = new_cost;
+                               }
+                               
+                               cost += cost_cache[i];
+                               
+                               if (cost > min_cost)
+                               {
+                                       must_move = i;
+                                       break;
+                               }
+                       }
+                       
+                       if (must_move != i || must_move > nb_joints - 1)
+                       {
+                               must_move = nb_joints - 1;
+                       }
+       
+                       /* cost optimizing */
+                       if (cost < min_cost)
+                       {
+                               min_cost = cost;
+                               memcpy(best_positions, positions, sizeof(int) * nb_joints);
+                       }
+               }
+       }
+       /* SIMULATED ANNEALING */
+       else if (method == METHOD_ANNEALING)
+       {
+               RigEdge *previous;
+               float *cost_cube;
+               float cost;
+               int k;
+               int kmax;
+
+               kmax = 100000;
+               
+               BLI_srand(nb_joints);
+               
+               /* [joint: index][position: -1, 0, +1] */
+               cost_cube = MEM_callocN(sizeof(float) * 3 * nb_joints, "Cost Cube");
+               
+               initArcIterator(&iter, earc, node_start);
+
+               /* init vec_cache */
+               for (i = 0; i < nb_joints; i++)
+               {
+                       bucket = peekBucket(&iter, positions[i]);
+                       vec_cache[i + 1] = bucket->p;
+               }
+               
+               cost = 0;
+
+               /* init cost cube */
+               for (previous = iarc->edges.first, edge = previous->next, i = 0;
+                        edge;
+                        previous = edge, edge = edge->next, i += 1)
+               {
+                       calcGradient(previous, edge, &iter, i, nb_joints, cost_cube, positions, vec_cache);
+                       
+                       cost += cost_cube[3 * i + 1];
+               }
+               
+#ifndef USE_THREADS
+               printf("initial cost: %f\n", cost);
+               printf("kmax: %i\n", kmax);
+#endif
+               
+               for (k = 0; k < kmax; k++)
+               {
+                       int status;
+                       int moving_joint = -1;
+                       int move_direction = -1;
+                       float delta_cost;
+                       float temperature;
+                       
+                       status = neighbour(nb_joints, cost_cube, &moving_joint, &move_direction);
+                       
+                       if (status == 0)
+                       {
+                               /* if current state is still a minimum, copy it */
+                               if (cost < min_cost)
+                               {
+                                       min_cost = cost;
+                                       memcpy(best_positions, positions, sizeof(int) * nb_joints);
+                               }
+                               break;
+                       }
+                       
+                       delta_cost = cost_cube[moving_joint * 3 + (1 + move_direction)];
+
+                       temperature = 1 - (float)k / (float)kmax;
+                       if (probability(delta_cost, temperature) > BLI_frand())
+                       {
+                               /* update position */                   
+                               positions[moving_joint] += move_direction;
+                               
+                               /* update vector cache */
+                               bucket = peekBucket(&iter, positions[moving_joint]);
+                               vec_cache[moving_joint + 1] = bucket->p;
+                               
+                               cost += delta_cost;
+       
+                               /* cost optimizing */
+                               if (cost < min_cost)
+                               {
+                                       min_cost = cost;
+                                       memcpy(best_positions, positions, sizeof(int) * nb_joints);
+                               }
+
+                               /* update cost cube */                  
+                               for (previous = iarc->edges.first, edge = previous->next, i = 0;
+                                        edge;
+                                        previous = edge, edge = edge->next, i += 1)
+                               {
+                                       if (i == moving_joint - 1 ||
+                                               i == moving_joint ||
+                                               i == moving_joint + 1)
+                                       {
+                                               calcGradient(previous, edge, &iter, i, nb_joints, cost_cube, positions, vec_cache);
+                                       }
+                               }
+                       }
+               }
+
+               //min_cost = cost;
+               //memcpy(best_positions, positions, sizeof(int) * nb_joints);
+               
+//             printf("k = %i\n", k);
+               
+               
+               MEM_freeN(cost_cube);
+       }       
+
+
+       vec0 = node_start->p;
+       initArcIterator(&iter, earc, node_start);
+       
+#ifndef USE_THREADS
+       printPositions(best_positions, nb_joints);
+       printMovesNeeded(best_positions, nb_joints);
+       printf("min_cost %f\n", min_cost);
+       printf("buckets: %i\n", earc->bcount);
+#endif
+
+       /* set joints to best position */
+       for (edge = iarc->edges.first, i = 0;
+                edge;
+                edge = edge->next, i++)
+       {
+               if (i < nb_joints)
+               {
+                       bucket = peekBucket(&iter, best_positions[i]);
+                       vec1 = bucket->p;
+               }
+               else
+               {
+                       vec1 = node_end->p;
+               }
+               
+               if (edge->bone)
+               {
+                       repositionBone(rigg, edge, vec0, vec1);
+               }
+               
+               vec0 = vec1;
+       }
+       
+       MEM_freeN(positions);
+       MEM_freeN(best_positions);
+       MEM_freeN(cost_cache);
+       MEM_freeN(vec_cache);
+}
+
+static void retargetArctoArcLength(RigGraph *rigg, RigArc *iarc, RigNode *inode_start)
+{
+       ReebArcIterator iter;
+       ReebArc *earc = iarc->link_mesh;
+       ReebNode *node_start, *node_end;
+       RigEdge *edge;
+       EmbedBucket *bucket = NULL;
+       float embedding_length = 0;
+       float *vec0 = NULL;
+       float *vec1 = NULL;
+       float *previous_vec = NULL;
+
+       
+       if (testFlipArc(iarc, inode_start))
+       {
+               node_start = (ReebNode*)earc->tail;
+               node_end = (ReebNode*)earc->head;
+       }
+       else
+       {
+               node_start = (ReebNode*)earc->head;
+               node_end = (ReebNode*)earc->tail;
+       }
+       
+       initArcIterator(&iter, earc, node_start);
+
+       bucket = nextBucket(&iter);
+       
+       vec0 = node_start->p;
+       
+       while (bucket != NULL)
+       {
+               vec1 = bucket->p;
+               
+               embedding_length += VecLenf(vec0, vec1);
+               
+               vec0 = vec1;
+               bucket = nextBucket(&iter);
+       }
+       
+       embedding_length += VecLenf(node_end->p, vec1);
+       
+       /* fit bones */
+       initArcIterator(&iter, earc, node_start);
+
+       bucket = nextBucket(&iter);
+
+       vec0 = node_start->p;
+       previous_vec = vec0;
+       vec1 = bucket->p;
+       
+       for (edge = iarc->edges.first; edge; edge = edge->next)
+       {
+               float new_bone_length = edge->length / iarc->length * embedding_length;
+
+               float length = 0;
+
+               while (bucket && new_bone_length > length)
+               {
+                       length += VecLenf(previous_vec, vec1);
+                       bucket = nextBucket(&iter);
+                       previous_vec = vec1;
+                       vec1 = bucket->p;
+               }
+               
+               if (bucket == NULL)
+               {
+                       vec1 = node_end->p;
+               }
+
+               /* no need to move virtual edges (space between unconnected bones) */           
+               if (edge->bone)
+               {
+                       repositionBone(rigg, edge, vec0, vec1);
+               }
+               
+               vec0 = vec1;
+               previous_vec = vec1;
+       }
+}
+
+static void retargetArctoArc(RigGraph *rigg, RigArc *iarc, RigNode *inode_start)
+{
+#ifdef USE_THREADS
+       RetargetParam *p = MEM_callocN(sizeof(RetargetParam), "RetargetParam");
+       
+       p->rigg = rigg;
+       p->iarc = iarc;
+       p->inode_start = inode_start;
+       
+       BLI_insert_work(rigg->worker, p);
+#else
+       RetargetParam p;
+
+       p.rigg = rigg;
+       p.iarc = iarc;
+       p.inode_start = inode_start;
+       
+       exec_retargetArctoArc(&p);
+#endif
+}
+
+void *exec_retargetArctoArc(void *param)
+{
+       RetargetParam *p = (RetargetParam*)param;
+       RigGraph *rigg = p->rigg;
+       RigArc *iarc = p->iarc; 
+       RigNode *inode_start = p->inode_start;
+       ReebArc *earc = iarc->link_mesh;
+       
+       if (BLI_countlist(&iarc->edges) == 1)
+       {
+               RigEdge *edge = iarc->edges.first;
+
+               if (testFlipArc(iarc, inode_start))
+               {
+                       repositionBone(rigg, edge, earc->tail->p, earc->head->p);
+               }
+               else
+               {
+                       repositionBone(rigg, edge, earc->head->p, earc->tail->p);
+               }
+       }
+       else
+       {
+               RetargetMode mode = detectArcRetargetMode(iarc);
+               
+               if (mode == RETARGET_AGGRESSIVE)
+               {
+                       retargetArctoArcAggresive(rigg, iarc, inode_start);
+               }
+               else
+               {               
+                       retargetArctoArcLength(rigg, iarc, inode_start);
+               }
+       }
+
+#ifdef USE_THREADS
+       MEM_freeN(p);
+#endif
+       
+       return NULL;
+}
+
+static void matchMultiResolutionNode(RigGraph *rigg, RigNode *inode, ReebNode *top_node)
+{
+       ReebNode *enode = top_node;
+       ReebGraph *reebg = BIF_graphForMultiNode(rigg->link_mesh, enode);
+       int ishape, eshape;
+       
+       ishape = BLI_subtreeShape((BGraph*)rigg, (BNode*)inode, NULL, 0) % SHAPE_LEVELS;
+       eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, NULL, 0) % SHAPE_LEVELS;
+       
+       inode->link_mesh = enode;
+
+       while (ishape == eshape && enode->link_down)
+       {
+               inode->link_mesh = enode;
+
+               enode = enode->link_down;
+               reebg = BIF_graphForMultiNode(rigg->link_mesh, enode); /* replace with call to link_down once that exists */
+               eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, NULL, 0) % SHAPE_LEVELS;
+       } 
+}
+
+static void markMultiResolutionChildArc(ReebNode *end_enode, ReebNode *enode)
+{
+       int i;
+       
+       for(i = 0; i < enode->degree; i++)
+       {
+               ReebArc *earc = (ReebArc*)enode->arcs[i];
+               
+               if (earc->flag == ARC_FREE)
+               {
+                       earc->flag = ARC_TAKEN;
+                       
+                       if (earc->tail->degree > 1 && earc->tail != end_enode)
+                       {
+                               markMultiResolutionChildArc(end_enode, earc->tail);
+                       }
+                       break;
+               }
+       }
+}
+
+static void markMultiResolutionArc(ReebArc *start_earc)
+{
+       if (start_earc->link_up)
+       {
+               ReebArc *earc;
+               for (earc = start_earc->link_up ; earc; earc = earc->link_up)
+               {
+                       earc->flag = ARC_TAKEN;
+                       
+                       if (earc->tail->index != start_earc->tail->index)
+                       {
+                               markMultiResolutionChildArc(earc->tail, earc->tail);
+                       }
+               }
+       }
+}
+
+static void matchMultiResolutionArc(RigGraph *rigg, RigNode *start_node, RigArc *next_iarc, ReebArc *next_earc)
+{
+       ReebNode *enode = next_earc->head;
+       ReebGraph *reebg = BIF_graphForMultiNode(rigg->link_mesh, enode);
+       int ishape, eshape;
+
+       ishape = BLI_subtreeShape((BGraph*)rigg, (BNode*)start_node, (BArc*)next_iarc, 1) % SHAPE_LEVELS;
+       eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, (BArc*)next_earc, 1) % SHAPE_LEVELS;
+       
+       while (ishape != eshape && next_earc->link_up)
+       {
+               next_earc->flag = ARC_TAKEN; // mark previous as taken, to prevent backtrack on lower levels
+               
+               next_earc = next_earc->link_up;
+               reebg = reebg->link_up;
+               enode = next_earc->head;
+               eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, (BArc*)next_earc, 1) % SHAPE_LEVELS;
+       } 
+
+       next_earc->flag = ARC_USED;
+       next_iarc->link_mesh = next_earc;
+       
+       /* mark all higher levels as taken too */
+       markMultiResolutionArc(next_earc);
+//     while (next_earc->link_up)
+//     {
+//             next_earc = next_earc->link_up;
+//             next_earc->flag = ARC_TAKEN;
+//     }
+}
+
+static void matchMultiResolutionStartingNode(RigGraph *rigg, ReebGraph *reebg, RigNode *inode)
+{
+       ReebNode *enode;
+       int ishape, eshape;
+       
+       enode = reebg->nodes.first;
+       
+       ishape = BLI_subtreeShape((BGraph*)rigg, (BNode*)inode, NULL, 0) % SHAPE_LEVELS;
+       eshape = BLI_subtreeShape((BGraph*)rigg->link_mesh, (BNode*)enode, NULL, 0) % SHAPE_LEVELS;
+       
+       while (ishape != eshape && reebg->link_up)
+       {
+               reebg = reebg->link_up;
+               
+               enode = reebg->nodes.first;
+               
+               eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, NULL, 0) % SHAPE_LEVELS;
+       } 
+
+       inode->link_mesh = enode;
+}
+
+static void findCorrespondingArc(RigGraph *rigg, RigArc *start_arc, RigNode *start_node, RigArc *next_iarc, int root)
+{
+       ReebNode *enode = start_node->link_mesh;
+       ReebArc *next_earc;
+       int symmetry_level = next_iarc->symmetry_level;
+       int symmetry_group = next_iarc->symmetry_group;
+       int symmetry_flag = next_iarc->symmetry_flag;
+       int i;
+       
+       next_iarc->link_mesh = NULL;
+               
+//     if (root)
+//     {
+//             printf("-----------------------\n");
+//             printf("MATCHING LIMB\n");
+//             RIG_printArcBones(next_iarc);
+//     }
+       
+       for(i = 0; i < enode->degree; i++)
+       {
+               next_earc = (ReebArc*)enode->arcs[i];
+               
+//             if (next_earc->flag == ARC_FREE)
+//             {
+//                     printf("candidate (level %i ?= %i) (flag %i ?= %i) (group %i ?= %i)\n",
+//                     symmetry_level, next_earc->symmetry_level,
+//                     symmetry_flag, next_earc->symmetry_flag, 
+//                     symmetry_group, next_earc->symmetry_flag);
+//             }
+               
+               if (next_earc->flag == ARC_FREE &&
+                       next_earc->symmetry_flag == symmetry_flag &&
+                       next_earc->symmetry_group == symmetry_group &&
+                       next_earc->symmetry_level == symmetry_level)
+               {
+//                     printf("CORRESPONDING ARC FOUND\n");
+//                     printf("flag %i -- level %i -- flag %i -- group %i\n", next_earc->flag, next_earc->symmetry_level, next_earc->symmetry_flag, next_earc->symmetry_group);
+                       
+                       matchMultiResolutionArc(rigg, start_node, next_iarc, next_earc);
+                       break;
+               }
+       }
+       
+       /* not found, try at higher nodes (lower node might have filtered internal arcs, messing shape of tree */
+       if (next_iarc->link_mesh == NULL)
+       {
+//             printf("NO CORRESPONDING ARC FOUND - GOING TO HIGHER LEVELS\n");
+               
+               if (enode->link_up)
+               {
+                       start_node->link_mesh = enode->link_up;
+                       findCorrespondingArc(rigg, start_arc, start_node, next_iarc, 0);
+               }
+       }
+
+       /* still not found, print debug info */
+       if (root && next_iarc->link_mesh == NULL)
+       {
+               start_node->link_mesh = enode; /* linking back with root node */
+               
+//             printf("NO CORRESPONDING ARC FOUND\n");
+//             RIG_printArcBones(next_iarc);
+//             
+//             printf("ON NODE %i, multilevel %i\n", enode->index, enode->multi_level);
+//             
+//             printf("LOOKING FOR\n");
+//             printf("flag %i -- level %i -- flag %i -- group %i\n", ARC_FREE, symmetry_level, symmetry_flag, symmetry_group);
+//             
+//             printf("CANDIDATES\n");
+//             for(i = 0; i < enode->degree; i++)
+//             {
+//                     next_earc = (ReebArc*)enode->arcs[i];
+//                     printf("flag %i -- level %i -- flag %i -- group %i\n", next_earc->flag, next_earc->symmetry_level, next_earc->symmetry_flag, next_earc->symmetry_group);
+//             }
+               
+               /* Emergency matching */
+               for(i = 0; i < enode->degree; i++)
+               {
+                       next_earc = (ReebArc*)enode->arcs[i];
+                       
+                       if (next_earc->flag == ARC_FREE && next_earc->symmetry_level == symmetry_level)
+                       {
+//                             printf("USING: \n");
+//                             printf("flag %i -- level %i -- flag %i -- group %i\n", next_earc->flag, next_earc->symmetry_level, next_earc->symmetry_flag, next_earc->symmetry_group);
+                               matchMultiResolutionArc(rigg, start_node, next_iarc, next_earc);
+                               break;
+                       }
+               }
+       }
+
+}
+
+static void retargetSubgraph(RigGraph *rigg, RigArc *start_arc, RigNode *start_node)
+{
+       RigNode *inode = start_node;
+       int i;
+
+       /* no start arc on first node */
+       if (start_arc)
+       {               
+               ReebNode *enode = start_node->link_mesh;
+               ReebArc *earc = start_arc->link_mesh;
+               
+               retargetArctoArc(rigg, start_arc, start_node);
+               
+               enode = BIF_otherNodeFromIndex(earc, enode);
+               inode = (RigNode*)BLI_otherNode((BArc*)start_arc, (BNode*)inode);
+       
+               /* match with lowest node with correct shape */
+               matchMultiResolutionNode(rigg, inode, enode);
+       }
+       
+       for(i = 0; i < inode->degree; i++)
+       {
+               RigArc *next_iarc = (RigArc*)inode->arcs[i];
+               
+               /* no back tracking */
+               if (next_iarc != start_arc)
+               {
+                       findCorrespondingArc(rigg, start_arc, inode, next_iarc, 1);
+                       if (next_iarc->link_mesh)
+                       {
+                               retargetSubgraph(rigg, next_iarc, inode);
+                       }
+               }
+       }
+}
+
+static void adjustGraphs(RigGraph *rigg)
+{
+       RigArc *arc;
+       
+       for (arc = rigg->arcs.first; arc; arc = arc->next)
+       {
+               if (arc->link_mesh)
+               {
+                       retargetArctoArc(rigg, arc, arc->head);
+               }
+       }
+
+#ifdef USE_THREADS
+       BLI_end_worker(rigg->worker);
+#endif
+
+       /* Turn the list into an armature */
+       editbones_to_armature(&rigg->editbones, rigg->ob);
+       
+       BIF_undo_push("Retarget Skeleton");
+}
+
+static void retargetGraphs(RigGraph *rigg)
+{
+       ReebGraph *reebg = rigg->link_mesh;
+       RigNode *inode;
+       
+       /* flag all ReebArcs as free */
+       BIF_flagMultiArcs(reebg, ARC_FREE);
+       
+       /* return to first level */
+       reebg = rigg->link_mesh;
+       
+       inode = rigg->head;
+       
+       matchMultiResolutionStartingNode(rigg, reebg, inode);
+
+       retargetSubgraph(rigg, NULL, inode);
+       
+       //generateMissingArcs(rigg);
+       
+#ifdef USE_THREADS
+       BLI_end_worker(rigg->worker);
+#endif
+
+       /* Turn the list into an armature */
+       editbones_to_armature(&rigg->editbones, rigg->ob);
+}
+
+
+void BIF_retargetArmature()
+{
+       Object *ob;
+       Base *base;
+       ReebGraph *reebg;
+       double start_time, end_time;
+       double gstart_time, gend_time;
+       double reeb_time, rig_time, retarget_time, total_time;
+       
+       gstart_time = start_time = PIL_check_seconds_timer();
+       
+       reebg = BIF_ReebGraphMultiFromEditMesh();
+       
+       end_time = PIL_check_seconds_timer();
+       reeb_time = end_time - start_time;
+       
+       printf("Reeb Graph created\n");
+
+       base= FIRSTBASE;
+       for (base = FIRSTBASE; base; base = base->next)
+       {
+               if TESTBASELIB(base) {
+                       ob = base->object;
+
+                       if (ob->type==OB_ARMATURE)
+                       {
+                               RigGraph *rigg;
+                               bArmature *arm;
+                               
+                               arm = ob->data;
+                       
+                               /* Put the armature into editmode */
+                               
+                       
+                               start_time = PIL_check_seconds_timer();
+       
+                               rigg = armatureToGraph(ob, arm);
+                               
+                               end_time = PIL_check_seconds_timer();
+                               rig_time = end_time - start_time;
+
+                               printf("Armature graph created\n");
+               
+                               //RIG_printGraph(rigg);
+                               
+                               rigg->link_mesh = reebg;
+                               
+                               printf("retargetting %s\n", ob->id.name);
+                               
+                               start_time = PIL_check_seconds_timer();
+
+                               retargetGraphs(rigg);
+                               
+                               end_time = PIL_check_seconds_timer();
+                               retarget_time = end_time - start_time;
+
+                               BIF_freeRetarget();
+                               
+                               GLOBAL_RIGG = rigg;
+                               
+                               break; /* only one armature at a time */
+                       }
+               }
+       }
+       
+       gend_time = PIL_check_seconds_timer();
+
+       total_time = gend_time - gstart_time;
+
+       printf("-----------\n");
+       printf("runtime: \t%.3f\n", total_time);
+       printf("reeb: \t\t%.3f (%.1f%%)\n", reeb_time, reeb_time / total_time * 100);
+       printf("rig: \t\t%.3f (%.1f%%)\n", rig_time, rig_time / total_time * 100);
+       printf("retarget: \t%.3f (%.1f%%)\n", retarget_time, retarget_time / total_time * 100);
+       printf("-----------\n");
+       
+       BIF_undo_push("Retarget Skeleton");
+       
+       allqueue(REDRAWVIEW3D, 0);
+}
+
+void BIF_adjustRetarget()
+{
+       if (GLOBAL_RIGG)
+       {
+               adjustGraphs(GLOBAL_RIGG);
+       }
+}
+
+void BIF_freeRetarget()
+{
+       if (GLOBAL_RIGG)
+       {
+               RIG_freeRigGraph((BGraph*)GLOBAL_RIGG);
+               GLOBAL_RIGG = NULL;
+       }
+}
index 3d60e9a8eeaf90f32410b770cb4f387518b04b0c..45267f506226acf58e2c61923b3acccd4bdb59f2 100644 (file)
 #include "butspace.h" // own module
 #include "multires.h"
 
+#include "reeb.h"
+
 static float editbutweight= 1.0;
 float editbutvweight= 1;
 static int actmcol= 0, acttface= 0, acttface_rnd = 0, actmcol_rnd = 0;
@@ -5052,6 +5054,9 @@ void do_meshbuts(unsigned short event)
        case B_GEN_SKELETON:
                generateSkeleton();
                break;
+       case B_RETARGET_SKELETON:
+               BIF_retargetArmature();
+               break;
        }
 
        /* WATCH IT: previous events only in editmode! */
@@ -5150,6 +5155,100 @@ static void skgen_reorder(void *option, void *arg2)
        }
 }
 
+static void skgen_graphgen(void *arg1, void *arg2)
+{
+       BIF_GlobalReebGraphFromEditMesh();
+       allqueue(REDRAWVIEW3D, 0);
+}
+
+static void skgen_graphfree(void *arg1, void *arg2)
+{
+       BIF_GlobalReebFree();
+       allqueue(REDRAWVIEW3D, 0);
+}
+
+static void skgen_rigadjust(void *arg1, void *arg2)
+{
+       BIF_adjustRetarget();
+}
+
+static void skgen_rigfree(void *arg1, void *arg2)
+{
+       BIF_freeRetarget();
+}
+
+static void skgen_graph_block(uiBlock *block)
+{
+       uiBlockBeginAlign(block);
+       uiDefButS(block, NUM, B_DIFF, "Resolution:",                                                    1025,150,225,19, &G.scene->toolsettings->skgen_resolution,10.0,1000.0, 0, 0,            "Specifies the resolution of the graph's embedding");
+       uiDefButBitS(block, TOG, SKGEN_HARMONIC, B_DIFF,                "H",                    1250,150, 25,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Apply harmonic smoothing to the weighting");
+       uiDefButBitS(block, TOG, SKGEN_FILTER_INTERNAL, B_DIFF, "Filter In",    1025,130, 83,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Filter internal small arcs from graph");
+       uiDefButF(block, NUM, B_DIFF,                                                   "",                             1111,130,164,19, &G.scene->toolsettings->skgen_threshold_internal,0.0, 10.0, 10, 0,     "Specify the threshold ratio for filtering internal arcs");
+       uiDefButBitS(block, TOG, SKGEN_FILTER_EXTERNAL, B_DIFF, "Filter Ex",    1025,110, 53,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Filter external small arcs from graph");
+       uiDefButBitS(block, TOG, SKGEN_FILTER_SMART,    B_DIFF, "Sm",                   1078,110, 30,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Smart Filtering");
+       uiDefButF(block, NUM, B_DIFF,                                                   "",                             1111,110,164,19, &G.scene->toolsettings->skgen_threshold_external,0.0, 10.0, 10, 0,     "Specify the threshold ratio for filtering external arcs");
+       
+       uiDefButBitS(block, TOG, SKGEN_SYMMETRY, B_DIFF,                "Symmetry",             1025, 90,125,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Restore symmetries based on topology");
+       uiDefButF(block, NUM, B_DIFF,                                                   "T:",                   1150, 90,125,19, &G.scene->toolsettings->skgen_symmetry_limit,0.0, 1.0, 10, 0,  "Specify the threshold distance for considering potential symmetric arcs");
+       uiDefButC(block, NUM, B_DIFF,                                                   "P:",                   1025, 70, 62,19, &G.scene->toolsettings->skgen_postpro_passes, 0, 10, 10, 0,            "Specify the number of processing passes on the embeddings");
+       uiDefButC(block, ROW, B_DIFF,                                                   "Smooth",               1087, 70, 63,19, &G.scene->toolsettings->skgen_postpro, 5.0, (float)SKGEN_SMOOTH, 0, 0, "Smooth embeddings");
+       uiDefButC(block, ROW, B_DIFF,                                                   "Average",              1150, 70, 62,19, &G.scene->toolsettings->skgen_postpro, 5.0, (float)SKGEN_AVERAGE, 0, 0, "Average embeddings");
+       uiDefButC(block, ROW, B_DIFF,                                                   "Sharpen",              1212, 70, 63,19, &G.scene->toolsettings->skgen_postpro, 5.0, (float)SKGEN_SHARPEN, 0, 0, "Sharpen embeddings");
+
+       uiBlockEndAlign(block);
+}
+
+static void editing_panel_mesh_skgen_display(Object *ob, Mesh *me)
+{
+       uiBlock *block;
+       uiBut *but;
+
+       block= uiNewBlock(&curarea->uiblocks, "editing_panel_mesh_skgen_display", UI_EMBOSS, UI_HELV, curarea->win);
+       uiNewPanelTabbed("Mesh Tools More", "Skgen");
+       if(uiNewPanel(curarea, block, "Graph", "Editing", 960, 0, 318, 204)==0) return;
+       
+       but = uiDefBut(block, BUT, B_DIFF, "Generate",                          1025,170,125,19, 0, 0, 0, 0, 0, "Generate Graph from Mesh");
+       uiButSetFunc(but, skgen_graphgen, NULL, NULL);
+       but = uiDefBut(block, BUT, B_DIFF, "Free",                                      1150,170,125,19, 0, 0, 0, 0, 0, "Free Graph from Mesh");
+       uiButSetFunc(but, skgen_graphfree, NULL, NULL);
+       
+       skgen_graph_block(block);
+
+       uiBlockBeginAlign(block);
+       uiDefButBitS(block, TOG, SKGEN_DISP_LENGTH, REDRAWVIEW3D,       "Length",                       1025, 40, 50,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,             "Show Length");
+       uiDefButBitS(block, TOG, SKGEN_DISP_WEIGHT, REDRAWVIEW3D,       "Weight",                       1075, 40, 50,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,             "Show Weight");
+       uiDefButBitS(block, TOG, SKGEN_DISP_EMBED, REDRAWVIEW3D,        "Embed",                        1125, 40, 50,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,             "Show Arc Embedings");
+       uiDefButBitS(block, TOG, SKGEN_DISP_INDEX, REDRAWVIEW3D,        "Index",                        1175, 40, 50,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,             "Show Arc and Node indexes");
+       uiDefButBitS(block, TOG, SKGEN_DISP_ORIG, REDRAWVIEW3D,         "Original",                     1225, 40, 50,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,             "Show Original Graph");
+
+       uiBlockEndAlign(block);
+
+       uiDefButC(block, NUM, REDRAWVIEW3D,                                             "Level:",                       1025, 20, 125,19, &G.scene->toolsettings->skgen_multi_level, 0, REEB_MAX_MULTI_LEVEL, 1, 0,"Specify the level to draw");
+}
+
+static void editing_panel_mesh_skgen_retarget(Object *ob, Mesh *me)
+{
+       uiBlock *block;
+       uiBut *but;
+
+       block= uiNewBlock(&curarea->uiblocks, "editing_panel_mesh_skgen_retarget", UI_EMBOSS, UI_HELV, curarea->win);
+       uiNewPanelTabbed("Mesh Tools More", "Skgen");
+       if(uiNewPanel(curarea, block, "Retarget", "Editing", 960, 0, 318, 204)==0) return;
+       
+       uiDefBut(block, BUT, B_RETARGET_SKELETON, "Retarget Skeleton",  1025,170,100,19, 0, 0, 0, 0, 0, "Retarget Selected Armature to this Mesh");
+       but = uiDefBut(block, BUT, B_DIFF, "Adjust",                                    1125,170,100,19, 0, 0, 0, 0, 0, "Adjust Retarget using new weights");
+       uiButSetFunc(but, skgen_rigadjust, NULL, NULL);
+       but = uiDefBut(block, BUT, B_DIFF, "Free",                                              1225,170,50,19, 0, 0, 0, 0, 0, "Free Retarget structure");
+       uiButSetFunc(but, skgen_rigfree, NULL, NULL);
+
+       skgen_graph_block(block);
+
+       uiDefButF(block, NUM, B_DIFF,                                                   "Ang:",                 1025, 40, 83,19, &G.scene->toolsettings->skgen_retarget_angle_weight, 0, 10, 1, 0,              "Angle Weight");
+       uiDefButF(block, NUM, B_DIFF,                                                   "Len:",                 1108, 40, 83,19, &G.scene->toolsettings->skgen_retarget_length_weight, 0, 10, 1, 0,             "Length Weight");
+       uiDefButF(block, NUM, B_DIFF,                                                   "Dist:",                1191, 40, 84,19, &G.scene->toolsettings->skgen_retarget_distance_weight, 0, 10, 1, 0,           "Distance Weight");
+       uiDefButC(block, NUM, B_DIFF,                                                   "Method:",              1025, 20, 125,19, &G.scene->toolsettings->skgen_optimisation_method, 0, 2, 1, 0,"Optimisation Method (0: brute, 1: memoize, 2: annealing max fixed");
+}
+
 static void editing_panel_mesh_skgen(Object *ob, Mesh *me)
 {
        uiBlock *block;
@@ -5157,20 +5256,17 @@ static void editing_panel_mesh_skgen(Object *ob, Mesh *me)
        int i;
 
        block= uiNewBlock(&curarea->uiblocks, "editing_panel_mesh_skgen", UI_EMBOSS, UI_HELV, curarea->win);
-       if(uiNewPanel(curarea, block, "Skeleton Generator", "Editing", 960, 0, 318, 204)==0) return;
+       uiNewPanelTabbed("Mesh Tools More", "Skgen");
+       if(uiNewPanel(curarea, block, "Generator", "Editing", 960, 0, 318, 204)==0) return;
        
-       uiDefBut(block, BUT, B_GEN_SKELETON, "Generate Skeleton",                       1025,170,250,19, 0, 0, 0, 0, 0, "Generate Skeleton from Mesh");
+       uiDefBut(block, BUT, B_GEN_SKELETON, "Generate",                        1025,170,250,19, 0, 0, 0, 0, 0, "Generate Skeleton from Mesh");
 
-       uiBlockBeginAlign(block);
-       uiDefButS(block, NUM, B_DIFF, "Resolution:",                                                    1025,150,250,19, &G.scene->toolsettings->skgen_resolution,10.0,1000.0, 0, 0,            "Specifies the resolution of the graph's embedding");
-       uiDefButBitS(block, TOG, SKGEN_FILTER_INTERNAL, B_DIFF, "Filter In",    1025,130, 83,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Filter internal small arcs from graph");
-       uiDefButF(block, NUM, B_DIFF,                                                   "T:",                   1111,130,164,19, &G.scene->toolsettings->skgen_threshold_internal,0.0, 1.0, 10, 0,      "Specify the threshold ratio for filtering internal arcs");
-       uiDefButBitS(block, TOG, SKGEN_FILTER_EXTERNAL, B_DIFF, "Filter Ex",    1025,110, 83,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Filter external small arcs from graph");
-       uiDefButF(block, NUM, B_DIFF,                                                   "T:",                   1111,110,164,19, &G.scene->toolsettings->skgen_threshold_external,0.0, 1.0, 10, 0,      "Specify the threshold ratio for filtering external arcs");
+       skgen_graph_block(block);
 
+       uiBlockBeginAlign(block);
        for(i = 0; i < SKGEN_SUB_TOTAL; i++)
        {
-               int y = 90 - 20 * i;
+               int y = 50 - 20 * i;
                
                but = uiDefIconBut(block, BUT, B_MODIFIER_RECALC, VICON_MOVE_DOWN,              1025, y, 16, 19, NULL, 0.0, 0.0, 0.0, 0.0, "Change the order the subdivisions algorithm are applied");
                uiButSetFunc(but, skgen_reorder, SET_INT_IN_POINTER(i), NULL);
@@ -5187,18 +5283,14 @@ static void editing_panel_mesh_skgen(Object *ob, Mesh *me)
                                uiDefButF(block, NUM, B_DIFF,                                                   "T:",                   1111, y,164,19, &G.scene->toolsettings->skgen_angle_limit,0.0, 90.0, 10, 0,                     "Specify the threshold angle in degrees for subdivision");
                                break;
                        case SKGEN_SUB_CORRELATION:
-                               uiDefButBitS(block, TOG, SKGEN_CUT_CORRELATION, B_DIFF, "Correlation",  1041, y, 67,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                      "Subdivide arcs based on correlation");
-                               uiDefButF(block, NUM, B_DIFF,                                                   "T:",                   1111, y,164,19, &G.scene->toolsettings->skgen_correlation_limit,0.0, 1.0, 0.01, 0,      "Specify the threshold correlation for subdivision");
+                               uiDefButBitS(block, TOG, SKGEN_CUT_CORRELATION, B_DIFF, "Adaptative",   1041, y, 67,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                      "Subdivide arcs adaptatively");
+                               uiDefButF(block, NUM, B_DIFF,                                                   "T:",                   1111, y,114,19, &G.scene->toolsettings->skgen_correlation_limit,0.0, 1.0, 0.01, 0,      "Specify the adaptive threshold for subdivision");
+                               uiDefButBitS(block, TOG, SKGEN_STICK_TO_EMBEDDING, B_DIFF,              "E",                    1225, y, 25,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                      "Stick endpoint to embedding");
+                               uiDefButBitS(block, TOG, SKGEN_ADAPTIVE_DISTANCE, B_DIFF,               "D",                    1250, y, 25,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                      "Adaptive distance (on) or variance(off)");
                                break;
                }
        }
 
-       uiDefButBitS(block, TOG, SKGEN_SYMMETRY, B_DIFF,                "Symmetry",             1025, 30,125,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Restore symmetries based on topology");
-       uiDefButF(block, NUM, B_DIFF,                                                   "T:",                   1150, 30,125,19, &G.scene->toolsettings->skgen_symmetry_limit,0.0, 1.0, 10, 0,  "Specify the threshold distance for considering potential symmetric arcs");
-       uiDefButC(block, NUM, B_DIFF,                                                   "P:",                   1025, 10, 62,19, &G.scene->toolsettings->skgen_postpro_passes, 0, 10, 10, 0,            "Specify the number of processing passes on the embeddings");
-       uiDefButC(block, ROW, B_DIFF,                                                   "Smooth",               1087, 10, 63,19, &G.scene->toolsettings->skgen_postpro, 5.0, (float)SKGEN_SMOOTH, 0, 0, "Smooth embeddings");
-       uiDefButC(block, ROW, B_DIFF,                                                   "Average",              1150, 10, 62,19, &G.scene->toolsettings->skgen_postpro, 5.0, (float)SKGEN_AVERAGE, 0, 0, "Average embeddings");
-       uiDefButC(block, ROW, B_DIFF,                                                   "Sharpen",              1212, 10, 63,19, &G.scene->toolsettings->skgen_postpro, 5.0, (float)SKGEN_SHARPEN, 0, 0, "Sharpen embeddings");
        uiBlockEndAlign(block);
 }
 
@@ -6623,8 +6715,11 @@ void editing_panels()
                        editing_panel_mesh_tools1(ob, ob->data);
                        uiNewPanelTabbed("Mesh Tools 1", "Editing");
                        
-                       if (G.rt == 42) /* hidden for now, no time for docs */
-                               editing_panel_mesh_skgen(ob, ob->data);
+                       #ifdef WITH_BF_REEB
+                       editing_panel_mesh_skgen(ob, ob->data);
+                       editing_panel_mesh_skgen_retarget(ob, ob->data);
+                       editing_panel_mesh_skgen_display(ob, ob->data);
+                       #endif
                        
                        editing_panel_mesh_uvautocalculation();
                        if (EM_texFaceCheck())
index 2e6f6c18073a1f871460c92a4c9865da2e405521..de3e464060d00b8e955d49b1c9aa8a732ba6eede 100644 (file)
 
 #include "RE_pipeline.h"       // make_stars
 
+#include "reeb.h"
+
 #include "GPU_draw.h"
 #include "GPU_material.h"
 
@@ -3240,6 +3242,8 @@ void drawview3dspace(ScrArea *sa, void *spacedata)
                        BIF_drawPropCircle(); // only editmode and particles have proportional edit
                BIF_drawSnap();
        }
+       
+       REEB_draw();
 
        if(G.scene->radio) RAD_drawall(v3d->drawtype>=OB_SOLID);
        
index 0b8c1339daed3614b67b9c8f6e31b1bbe8723ec0..5ddf522e4a86aa86e043c2857f0a736ca9ac3b26 100644 (file)
@@ -4514,542 +4514,7 @@ void transform_armature_mirror_update(void)
 /*************************************** SKELETON GENERATOR ******************************************/
 /*****************************************************************************************************/
 
-/**************************************** SYMMETRY HANDLING ******************************************/
 
-void markdownSymmetryArc(ReebArc *arc, ReebNode *node, int level);
-
-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])
-{
-       RadialArc *ring = NULL;
-       RadialArc *unit;
-       float limit = G.scene->toolsettings->skgen_symmetry_limit;
-       int symmetric = 1;
-       int count = 0;
-       int i;
-
-       /* 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->flags == -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->flags == -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 */
-       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;
-               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 = OTHER_NODE(ring[i].arc, node);
-               node2 = OTHER_NODE(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)
-       {
-               /* 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);
-                               }
-               
-               
-                               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);
-}
-
-void reestablishAxialSymmetry(ReebNode *node, int depth, float axis[3])
-{
-       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;
-       
-       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->flags == -depth)
-               {
-                       if (arc1 == NULL)
-                       {
-                               arc1 = connectedArc;
-                               node1 = OTHER_NODE(arc1, node);
-                       }
-                       else
-                       {
-                               arc2 = connectedArc;
-                               node2 = OTHER_NODE(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(p, node1->p, node->p);
-       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)
-       {
-       
-               /* 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)
-               {
-                       ReebArcIterator iter1, iter2;
-                       EmbedBucket *bucket1 = NULL, *bucket2 = NULL;
-                       
-                       initArcIterator(&iter1, arc1, node);
-                       initArcIterator(&iter2, arc2, 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))
-                       {
-                               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);
-                       }
-               }
-       }
-}
-
-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 */
-       if (G.scene->toolsettings->skgen_options & SKGEN_SYMMETRY)
-       {
-               /* 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];
-                       
-                       /* depth is store as a negative in flag. symmetry level is positive */
-                       if (connectedArc->flags == -depth)
-                       {
-                               count++;
-                       }
-                       /* If arc is on the axis */
-                       else if (connectedArc->flags == 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);
-               }
-               else
-               {
-                       reestablishRadialSymmetry(node, depth, axis);
-               }
-       }
-
-       /* markdown secondary symetries */      
-       for (i = 0; node->arcs[i] != NULL; i++)
-       {
-               ReebArc *connectedArc = node->arcs[i];
-               
-               if (connectedArc->flags == -depth)
-               {
-                       /* markdown symmetry for branches corresponding to the depth */
-                       markdownSymmetryArc(connectedArc, node, level + 1);
-               }
-       }
-}
-
-void markdownSymmetryArc(ReebArc *arc, ReebNode *node, int level)
-{
-       int i;
-       arc->flags = level;
-       
-       node = OTHER_NODE(arc, node);
-       
-       for (i = 0; node->arcs[i] != NULL; i++)
-       {
-               ReebArc *connectedArc = node->arcs[i];
-               
-               if (connectedArc != arc)
-               {
-                       ReebNode *connectedNode = OTHER_NODE(connectedArc, node);
-                       
-                       /* symmetry level is positive value, negative values is subtree depth */
-                       connectedArc->flags = -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->flags < 0)
-               {
-                       int j;
-                       
-                       /* true by default */
-                       issymmetryAxis = 1;
-                       
-                       for (j = 0; node->arcs[j] != NULL && issymmetryAxis == 1; j++)
-                       {
-                               ReebArc *otherArc = node->arcs[j];
-                               
-                               /* different arc, same depth */
-                               if (otherArc != connectedArc && otherArc->flags == connectedArc->flags)
-                               {
-                                       /* 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(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->flags < 0)
-               {
-                       /* subtree depth is store as a negative value in the flag */
-                       markdownSecondarySymmetry(node, -connectedArc->flags, 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->flags = 0;
-       }
-       
-       /* mark down all nodes as not on the symmetry axis */
-       for (node = rg->nodes.first; node; node = node->next)
-       {
-               node->flags = 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->flags < 0)
-                       {
-                               arc->flags = 0;
-                       }
-                       else
-                       {
-                               /* mark down nodes with the lowest level symmetry axis */
-                               if (arc->v1->flags == 0 || arc->v1->flags > arc->flags)
-                               {
-                                       arc->v1->flags = arc->flags;
-                               }
-                               if (arc->v2->flags == 0 || arc->v2->flags > arc->flags)
-                               {
-                                       arc->v2->flags = arc->flags;
-                               }
-                       }
-               }
-       }
-}
 
 /**************************************** SUBDIVISION ALGOS ******************************************/
 
@@ -5114,7 +4579,7 @@ EditBone * subdivideByAngle(ReebArc *arc, ReebNode *head, ReebNode *tail)
        return lastBone;
 }
 
-float calcCorrelation(ReebArc *arc, int start, int end, float v0[3], float n[3])
+float calcVariance(ReebArc *arc, int start, int end, float v0[3], float n[3])
 {
        int len = 2 + abs(end - start);
        
@@ -5162,19 +4627,47 @@ float calcCorrelation(ReebArc *arc, int start, int end, float v0[3], float n[3])
                /* adding start(0) and end(1) values to s_t */
                s_t += (avg_t * avg_t) + (1 - avg_t) * (1 - avg_t);
                
-               return 1.0f - s_xyz / s_t; 
+               return s_xyz / s_t; 
        }
        else
        {
-               return 1.0f;
+               return 0;
+       }
+}
+
+float calcDistance(ReebArc *arc, int start, int end, float head[3], float tail[3])
+{
+       ReebArcIterator iter;
+       EmbedBucket *bucket = NULL;
+       float max_dist = 0;
+       
+       /* calculate maximum distance */
+       for (initArcIterator2(&iter, arc, start, end), bucket = nextBucket(&iter);
+               bucket;
+               bucket = nextBucket(&iter))
+       {
+               float v1[3], v2[3], c[3];
+               float dist;
+               
+               VecSubf(v1, head, tail);
+               VecSubf(v2, bucket->p, tail);
+
+               Crossf(c, v1, v2);
+               
+               dist = Inpf(c, c) / Inpf(v1, v1);
+               
+               max_dist = dist > max_dist ? dist : max_dist;
        }
+       
+       
+       return max_dist; 
 }
 
 EditBone * subdivideByCorrelation(ReebArc *arc, ReebNode *head, ReebNode *tail)
 {
        ReebArcIterator iter;
        float n[3];
-       float CORRELATION_THRESHOLD = G.scene->toolsettings->skgen_correlation_limit;
+       float ADAPTIVE_THRESHOLD = G.scene->toolsettings->skgen_correlation_limit;
        EditBone *lastBone = NULL;
        
        /* init iterator to get start and end from head */
@@ -5183,15 +4676,17 @@ EditBone * subdivideByCorrelation(ReebArc *arc, ReebNode *head, ReebNode *tail)
        /* Calculate overall */
        VecSubf(n, arc->buckets[iter.end].p, head->p);
        
-       if (G.scene->toolsettings->skgen_options & SKGEN_CUT_CORRELATION && 
-               calcCorrelation(arc, iter.start, iter.end, head->p, n) < CORRELATION_THRESHOLD)
+       if (G.scene->toolsettings->skgen_options & SKGEN_CUT_CORRELATION)
        {
                EmbedBucket *bucket = NULL;
                EmbedBucket *previous = NULL;
                EditBone *child = NULL;
                EditBone *parent = NULL;
+               float normal[3] = {0, 0, 0};
+               float avg_normal[3];
+               int total = 0;
                int boneStart = iter.start;
-
+               
                parent = add_editbone("Bone");
                parent->flag = BONE_SELECTED|BONE_TIPSEL|BONE_ROOTSEL;
                VECCOPY(parent->head, head->p);
@@ -5200,12 +4695,46 @@ EditBone * subdivideByCorrelation(ReebArc *arc, ReebNode *head, ReebNode *tail)
                        bucket;
                        previous = bucket, bucket = nextBucket(&iter))
                {
-                       /* Calculate normal */
-                       VecSubf(n, bucket->p, parent->head);
+                       float btail[3];
+                       float value = 0;
 
-                       if (calcCorrelation(arc, boneStart, iter.index, parent->head, n) < CORRELATION_THRESHOLD)
+                       if (G.scene->toolsettings->skgen_options & SKGEN_STICK_TO_EMBEDDING)
                        {
-                               VECCOPY(parent->tail, previous->p);
+                               VECCOPY(btail, bucket->p);
+                       }
+                       else
+                       {
+                               float length;
+                               
+                               /* Calculate normal */
+                               VecSubf(n, bucket->p, parent->head);
+                               length = Normalize(n);
+                               
+                               total += 1;
+                               VecAddf(normal, normal, n);
+                               VECCOPY(avg_normal, normal);
+                               VecMulf(avg_normal, 1.0f / total);
+                                
+                               VECCOPY(btail, avg_normal);
+                               VecMulf(btail, length);
+                               VecAddf(btail, btail, parent->head);
+                       }
+
+                       if (G.scene->toolsettings->skgen_options & SKGEN_ADAPTIVE_DISTANCE)
+                       {
+                               value = calcDistance(arc, boneStart, iter.index, parent->head, btail);
+                       }
+                       else
+                       {
+                               float n[3];
+                               
+                               VecSubf(n, btail, parent->head);
+                               value = calcVariance(arc, boneStart, iter.index, parent->head, n);
+                       }
+
+                       if (value > ADAPTIVE_THRESHOLD)
+                       {
+                               VECCOPY(parent->tail, btail);
 
                                child = add_editbone("Bone");
                                VECCOPY(child->head, parent->tail);
@@ -5214,6 +4743,9 @@ EditBone * subdivideByCorrelation(ReebArc *arc, ReebNode *head, ReebNode *tail)
                                
                                parent = child; // new child is next parent
                                boneStart = iter.index; // start from end
+                               
+                               normal[0] = normal[1] = normal[2] = 0;
+                               total = 0;
                        }
                }
 
@@ -5231,7 +4763,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)
        {
@@ -5241,8 +4773,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
        {
@@ -5374,8 +4906,6 @@ void generateSkeletonFromReebGraph(ReebGraph *rg)
        {
                exit_editmode(EM_FREEDATA|EM_FREEUNDO|EM_WAITCURSOR); // freedata, and undo
        }
-
-       setcursor_space(SPACE_VIEW3D, CURSOR_WAIT);
        
        dst = add_object(OB_ARMATURE);
        base_init_from_view3d(BASACT, G.vd);
@@ -5392,7 +4922,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) 
        {
@@ -5402,43 +4932,43 @@ void generateSkeletonFromReebGraph(ReebGraph *rg)
 
                /* Find out the direction of the arc through simple heuristics (in order of priority) :
                 * 
-                * 1- Arcs on primary symmetry axis (flags == 1) point up (head: high weight -> tail: low weight)
+                * 1- Arcs on primary symmetry axis (symmetry == 1) point up (head: high weight -> tail: low weight)
                 * 2- Arcs starting on a primary axis point away from it (head: node on primary axis)
                 * 3- Arcs point down (head: low weight -> tail: high weight)
                 *
-                * Finally, the arc direction is stored in its flags: 1 (low -> high), -1 (high -> low)
+                * Finally, the arc direction is stored in its flag: 1 (low -> high), -1 (high -> low)
                 */
 
                /* if arc is a symmetry axis, internal bones go up the tree */          
-               if (arc->flags == 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->flags = -1; /* mark arc direction */
+                       arc->flag = -1; /* mark arc direction */
                }
                /* Bones point AWAY from the symmetry axis */
-               else if (arc->v1->flags == 1)
+               else if (arc->head->symmetry_level == 1)
                {
-                       head = arc->v1;
-                       tail = arc->v2;
+                       head = arc->head;
+                       tail = arc->tail;
                        
-                       arc->flags = 1; /* mark arc direction */
+                       arc->flag = 1; /* mark arc direction */
                }
-               else if (arc->v2->flags == 1)
+               else if (arc->tail->symmetry_level == 1)
                {
-                       head = arc->v2;
-                       tail = arc->v1;
+                       head = arc->tail;
+                       tail = arc->head;
                        
-                       arc->flags = -1; /* mark arc direction */
+                       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->flags = 1; /* mark arc direction */
+                       arc->flag = 1; /* mark arc direction */
                }
                
                /* Loop over subdivision methods */     
@@ -5480,12 +5010,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->flags == -1) || (arc->v2 == node && arc->flags == 1))
+                       if ((arc->head == node && arc->flag == -1) || (arc->tail == node && arc->flag == 1))
                        {
                                if (incomingArc == NULL)
                                {
@@ -5506,12 +5036,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->flags == 1) || (arc->v2 == node && arc->flags == -1))
+                               if ((arc->head == node && arc->flag == 1) || (arc->tail == node && arc->flag == -1))
                                {
                                        EditBone *childBone = BLI_ghash_lookup(arcBoneMap, arc);
 
@@ -5529,89 +5059,21 @@ void generateSkeletonFromReebGraph(ReebGraph *rg)
        }
        
        BLI_ghash_free(arcBoneMap, NULL, NULL);
-
-       setcursor_space(SPACE_VIEW3D, CURSOR_EDIT);
        
        BIF_undo_push("Generate Skeleton");
 }
 
 void generateSkeleton(void)
 {
-       EditMesh *em = G.editMesh;
-       ReebGraph *rg = NULL;
-       int i;
+       ReebGraph *reebg;
        
-       if (em == NULL)
-               return;
-
        setcursor_space(SPACE_VIEW3D, CURSOR_WAIT);
-
-       if (weightFromDistance(em) == 0)
-       {
-               error("No selected vertex\n");
-               return;
-       }
-               
-       renormalizeWeight(em, 1.0f);
-       
-       weightToHarmonic(em);
-       
-#ifdef DEBUG_REEB
-       weightToVCol(em);
-#endif
-       
-       rg = generateReebGraph(em, G.scene->toolsettings->skgen_resolution);
-
-       verifyBuckets(rg);
        
-       /* Remove arcs without embedding */
-       filterNullReebGraph(rg);
+       reebg = BIF_ReebGraphFromEditMesh();
 
-       verifyBuckets(rg);
+       generateSkeletonFromReebGraph(reebg);
 
+       REEB_freeGraph(reebg);
 
-       i = 1;
-       /* filter until there's nothing more to do */
-       while (i == 1)
-       {
-               i = 0; /* no work done yet */
-               
-               if (G.scene->toolsettings->skgen_options & SKGEN_FILTER_EXTERNAL)
-               {
-                       i |= filterExternalReebGraph(rg, G.scene->toolsettings->skgen_threshold_external * G.scene->toolsettings->skgen_resolution);
-               }
-       
-               verifyBuckets(rg);
-       
-               if (G.scene->toolsettings->skgen_options & SKGEN_FILTER_INTERNAL)
-               {
-                       i |= filterInternalReebGraph(rg, G.scene->toolsettings->skgen_threshold_internal * G.scene->toolsettings->skgen_resolution);
-               }
-       }
-
-       verifyBuckets(rg);
-
-       repositionNodes(rg);
-       
-       verifyBuckets(rg);
-
-       /* Filtering might have created degree 2 nodes, so remove them */
-       removeNormalNodes(rg);
-       
-       verifyBuckets(rg);
-
-       for(i = 0; i <  G.scene->toolsettings->skgen_postpro_passes; i++)
-       {
-               postprocessGraph(rg, G.scene->toolsettings->skgen_postpro);
-       }
-
-       buildAdjacencyList(rg);
-       
-       sortNodes(rg);
-       
-       sortArcs(rg);
-       
-       generateSkeletonFromReebGraph(rg);
-
-       freeGraph(rg);
+       setcursor_space(SPACE_VIEW3D, CURSOR_EDIT);
 }
index 85fb5815c3e0eeaf2005ab779fc6371657d4b3dd..54befb85a9b721fef4a631aa53428e451d232584 100644 (file)
 #include <stdio.h>
 #include <stdlib.h> // for qsort
 
+#include "PIL_time.h"
+
 #include "DNA_listBase.h"
 #include "DNA_scene_types.h"
 #include "DNA_space_types.h"
 #include "DNA_meshdata_types.h"
+#include "DNA_armature_types.h"
 
 #include "MEM_guardedalloc.h"
 
 #include "BLI_arithb.h"
 #include "BLI_editVert.h"
 #include "BLI_edgehash.h"
+#include "BLI_ghash.h"
+#include "BLI_heap.h"
 
 #include "BDR_editobject.h"
 
+#include "BMF_Api.h"
+
 #include "BIF_editmesh.h"
 #include "BIF_editarmature.h"
 #include "BIF_interface.h"
 #include "BIF_toolbox.h"
 #include "BIF_graphics.h"
+#include "BIF_gl.h"
+#include "BIF_resources.h"
 
 #include "BKE_global.h"
 #include "BKE_utildefines.h"
 
 #include "reeb.h"
 
+/* REPLACE WITH NEW ONE IN UTILDEFINES ONCE PATCH IS APPLIED */
+#define FTOCHAR(val) (val<=0.0f)? 0 : ((val>(1.0f-0.5f/255.0f))? 255 : (char)((255.0f*val)+0.5f))
+
+ReebGraph *GLOBAL_RG = NULL;
+ReebGraph *FILTERED_RG = NULL;
+
 /*
  * Skeleton generation algorithm based on: 
  * "Harmonic Skeleton for Realistic Character Animation"
  * SIGGRAPH 2007
  * 
  * */
+#define DEBUG_REEB
+#define DEBUG_REEB_NODE
+
+typedef struct EdgeIndex
+{
+       EditEdge **edges;
+       int              *offset;
+} EdgeIndex;
+
+typedef enum {
+       MERGE_LOWER,
+       MERGE_HIGHER,
+       MERGE_APPEND
+} MergeDirection;
 
 int mergeArcs(ReebGraph *rg, ReebArc *a0, ReebArc *a1);
+void mergeArcEdges(ReebGraph *rg, ReebArc *aDst, ReebArc *aSrc, MergeDirection direction);
 int mergeConnectedArcs(ReebGraph *rg, ReebArc *a0, ReebArc *a1);
-EditEdge * NextEdgeForVert(EditMesh *em, EditVert *v);
+EditEdge * NextEdgeForVert(EdgeIndex *indexed_edges, EditVert *eve);
+void mergeArcFaces(ReebGraph *rg, ReebArc *aDst, ReebArc *aSrc);
+void addFacetoArc(ReebArc *arc, EditFace *efa);
 
-/***************************************** BUCKET UTILS **********************************************/
+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);
 
-void addVertToBucket(EmbedBucket *b, float co[3])
-{
-       b->nv++;
-       VecLerpf(b->p, b->p, co, 1.0f / b->nv);
-}
+void flipArcBuckets(ReebArc *arc);
 
-void removeVertFromBucket(EmbedBucket *b, float co[3])
+
+/***************************************** UTILS **********************************************/
+
+void REEB_freeArc(BArc *barc)
 {
-       VecMulf(b->p, (float)b->nv);
-       VecSubf(b->p, b->p, co);
-       b->nv--;
-       VecMulf(b->p, 1.0f / (float)b->nv);
+       ReebArc *arc = (ReebArc*)barc;
+       BLI_freelistN(&arc->edges);
+       
+       if (arc->buckets)
+               MEM_freeN(arc->buckets);
+               
+       if (arc->faces)
+               BLI_ghash_free(arc->faces, NULL, NULL);
+       
+       MEM_freeN(arc);
 }
 
-void mergeBuckets(EmbedBucket *bDst, EmbedBucket *bSrc)
+void REEB_freeGraph(ReebGraph *rg)
 {
-       if (bDst->nv > 0 && bSrc->nv > 0)
+       ReebArc *arc;
+       ReebNode *node;
+       
+       // free nodes
+       for( node = rg->nodes.first; node; node = node->next )
        {
-               bDst->nv += bSrc->nv;
-               VecLerpf(bDst->p, bDst->p, bSrc->p, (float)bSrc->nv / (float)(bDst->nv));
+               BLI_freeNode((BGraph*)rg, (BNode*)node);
        }
-       else if (bSrc->nv > 0)
+       BLI_freelistN(&rg->nodes);
+       
+       // free arcs
+       arc = rg->arcs.first;
+       while( arc )
        {
-               bDst->nv = bSrc->nv;
-               VECCOPY(bDst->p, bSrc->p);
+               ReebArc *next = arc->next;
+               REEB_freeArc((BArc*)arc);
+               arc = next;
+       }
+       
+       // free edge map
+       BLI_edgehash_free(rg->emap, NULL);
+       
+       /* free linked graph */
+       if (rg->link_up)
+       {
+               REEB_freeGraph(rg->link_up);
        }
+       
+       MEM_freeN(rg);
 }
 
-void mergeArcBuckets(ReebArc *aDst, ReebArc *aSrc, float start, float end)
+ReebGraph * newReebGraph()
 {
-       if (aDst->bcount > 0 && aSrc->bcount > 0)
-       {
-               int indexDst = 0, indexSrc = 0;
-               
-               start = MAX3(start, aDst->buckets[0].val, aSrc->buckets[0].val);
-               
-               while(indexDst < aDst->bcount && aDst->buckets[indexDst].val < start)
-               {
-                       indexDst++;
-               }
+       ReebGraph *rg;
+       rg = MEM_callocN(sizeof(ReebGraph), "reeb graph");
+       
+       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;
+}
 
-               while(indexSrc < aSrc->bcount && aSrc->buckets[indexSrc].val < start)
-               {
-                       indexSrc++;
-               }
-               
-               for( ;  indexDst < aDst->bcount &&
-                               indexSrc < aSrc->bcount &&
-                               aDst->buckets[indexDst].val <= end &&
-                               aSrc->buckets[indexSrc].val <= end
-                               
-                        ;      indexDst++, indexSrc++)
-               {
-                       mergeBuckets(aDst->buckets + indexDst, aSrc->buckets + indexSrc);
-               }
+void BIF_flagMultiArcs(ReebGraph *rg, int flag)
+{
+       for ( ; rg; rg = rg->link_up)
+       {
+               BLI_flagArcs((BGraph*)rg, flag);
        }
 }
 
-void allocArcBuckets(ReebArc *arc)
+ReebNode * addNode(ReebGraph *rg, EditVert *eve, float weight)
 {
-       int i;
-       float start = ceil(arc->v1->weight);
-       arc->bcount = (int)(floor(arc->v2->weight) - start) + 1;
+       ReebNode *node = NULL;
        
-       if (arc->bcount > 0)
+       node = MEM_callocN(sizeof(ReebNode), "reeb node");
+       
+       node->flag = 0; // clear flag on init
+       node->symmetry_level = 0;
+       node->arcs = NULL;
+       node->degree = 0;
+       node->weight = weight;
+       node->index = rg->totnodes;
+       VECCOPY(node->p, eve->co);      
+       
+       BLI_addtail(&rg->nodes, node);
+       rg->totnodes++;
+       
+       return node;
+}
+
+ReebNode * copyNode(ReebGraph *rg, ReebNode *node)
+{
+       ReebNode *cp_node = NULL;
+       
+       cp_node = MEM_callocN(sizeof(ReebNode), "reeb node copy");
+       
+       memcpy(cp_node, node, sizeof(ReebNode));
+       
+       cp_node->prev = NULL;
+       cp_node->next = NULL;
+       cp_node->arcs = NULL;
+       
+       cp_node->link_up = NULL;
+       cp_node->link_down = NULL;
+       
+       BLI_addtail(&rg->nodes, cp_node);
+       rg->totnodes++;
+       
+       return cp_node; 
+}
+
+void relinkNodes(ReebGraph *low_rg, ReebGraph *high_rg)
+{
+       ReebNode *low_node, *high_node;
+       
+       if (low_rg == NULL || high_rg == NULL)
        {
-               arc->buckets = MEM_callocN(sizeof(EmbedBucket) * arc->bcount, "embed bucket");
-               
-               for(i = 0; i < arc->bcount; i++)
+               return;
+       }
+       
+       for (low_node = low_rg->nodes.first; low_node; low_node = low_node->next)
+       {
+               for (high_node = high_rg->nodes.first; high_node; high_node = high_node->next)
                {
-                       arc->buckets[i].val = start + i;
+                       if (low_node->index == high_node->index)
+                       {
+                               high_node->link_down = low_node;
+                               low_node->link_up = high_node;
+                               break;
+                       }
                }
        }
-       else
+}
+
+ReebNode *BIF_otherNodeFromIndex(ReebArc *arc, ReebNode *node)
+{
+       return (arc->head->index == node->index) ? arc->tail : arc->head;
+}
+
+ReebNode *BIF_NodeFromIndex(ReebArc *arc, ReebNode *node)
+{
+       return (arc->head->index == node->index) ? arc->head : arc->tail;
+}
+
+ReebNode *BIF_lowestLevelNode(ReebNode *node)
+{
+       while (node->link_down)
        {
-               arc->buckets = NULL;
+               node = node->link_down;
        }
        
+       return node;
 }
 
-void resizeArcBuckets(ReebArc *arc)
+ReebArc * copyArc(ReebGraph *rg, ReebArc *arc)
 {
-       EmbedBucket *oldBuckets = arc->buckets;
-       int oldBCount = arc->bcount;
+       ReebArc *cp_arc;
+       ReebNode *node;
        
-       allocArcBuckets(arc);
+       cp_arc = MEM_callocN(sizeof(ReebArc), "reeb arc copy");
+
+       memcpy(cp_arc, arc, sizeof(ReebArc));
        
-       if (oldBCount != 0 && arc->bcount != 0)
+       cp_arc->link_up = arc;
+       
+       cp_arc->head = NULL;
+       cp_arc->tail = NULL;
+
+       cp_arc->prev = NULL;
+       cp_arc->next = NULL;
+
+       cp_arc->edges.first = NULL;
+       cp_arc->edges.last = NULL;
+
+       /* copy buckets */      
+       cp_arc->buckets = MEM_callocN(sizeof(EmbedBucket) * cp_arc->bcount, "embed bucket");
+       memcpy(cp_arc->buckets, arc->buckets, sizeof(EmbedBucket) * cp_arc->bcount);
+       
+       /* copy faces map */
+       cp_arc->faces = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
+       mergeArcFaces(rg, cp_arc, arc);
+       
+       /* find corresponding head and tail */
+       for (node = rg->nodes.first; node && (cp_arc->head == NULL || cp_arc->tail == NULL); node = node->next)
        {
-               int oldStart = (int)oldBuckets[0].val;
-               int oldEnd = (int)oldBuckets[oldBCount - 1].val;
-               int newStart = (int)arc->buckets[0].val;
-               int newEnd = (int)arc->buckets[arc->bcount - 1].val;
-               int oldOffset = 0;
-               int newOffset = 0;
-               int len;
-               
-               if (oldStart < newStart)
+               if (node->index == arc->head->index)
                {
-                       oldOffset = newStart - oldStart;
+                       cp_arc->head = node;
                }
-               else
+               else if (node->index == arc->tail->index)
                {
-                       newOffset = oldStart - newStart;
+                       cp_arc->tail = node;
                }
-               
-               len = MIN2(oldEnd - (oldStart + oldOffset) + 1, newEnd - (newStart - newOffset) + 1);
-               
-               memcpy(arc->buckets + newOffset, oldBuckets + oldOffset, len * sizeof(EmbedBucket)); 
        }
+       
+       BLI_addtail(&rg->arcs, cp_arc);
+       
+       return cp_arc;
+}
 
-       if (oldBuckets != NULL)
+ReebGraph * copyReebGraph(ReebGraph *rg, int level)
+{
+       ReebNode *node;
+       ReebArc *arc;
+       ReebGraph *cp_rg = newReebGraph();
+       
+       cp_rg->resolution = rg->resolution;
+       cp_rg->length = rg->length;
+       cp_rg->link_up = rg;
+       cp_rg->multi_level = level;
+
+       /* Copy nodes */        
+       for (node = rg->nodes.first; node; node = node->next)
        {
-               MEM_freeN(oldBuckets);
+               ReebNode *cp_node = copyNode(cp_rg, node);
+               cp_node->multi_level = level;
+       }
+       
+       /* Copy arcs */
+       for (arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               copyArc(cp_rg, arc);
        }
+       
+       BLI_buildAdjacencyList((BGraph*)cp_rg);
+       
+       return cp_rg;
+}
+
+ReebGraph *BIF_graphForMultiNode(ReebGraph *rg, ReebNode *node)
+{
+       ReebGraph *multi_rg = rg;
+       
+       while(multi_rg && multi_rg->multi_level != node->multi_level)
+       {
+               multi_rg = multi_rg->link_up;
+       }
+       
+       return multi_rg;
 }
-/***************************************** UTILS **********************************************/
 
 ReebEdge * copyEdge(ReebEdge *edge)
 {
@@ -213,7 +377,9 @@ 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;
+       ReebNode *tail = (ReebNode*)arc->tail;
+       printf("arc: (%i) %f -> (%i) %f\n", head->index, head->weight, tail->index, tail->weight);
        
        for(edge = arc->edges.first; edge ; edge = edge->next)
        {
@@ -221,51 +387,46 @@ void printArc(ReebArc *arc)
        }
 }
 
-void freeArc(ReebArc *arc)
+void flipArc(ReebArc *arc)
 {
-       BLI_freelistN(&arc->edges);
+       ReebNode *tmp;
+       tmp = arc->head;
+       arc->head = arc->tail;
+       arc->tail = tmp;
        
-       if (arc->buckets)
-               MEM_freeN(arc->buckets);
-       
-       MEM_freeN(arc);
+       flipArcBuckets(arc);
 }
 
-void freeGraph(ReebGraph *rg)
+#ifdef DEBUG_REEB_NODE
+void NodeDegreeDecrement(ReebGraph *rg, ReebNode *node)
 {
-       ReebArc *arc;
-       ReebNode *node;
-       
-       // free nodes
-       for( node = rg->nodes.first; node; node = node->next )
-       {
-               // Free adjacency lists
-               if (node->arcs != NULL)
-               {
-                       MEM_freeN(node->arcs);
-               }
-       }
-       BLI_freelistN(&rg->nodes);
-       
-       // free arcs
-       arc = rg->arcs.first;
-       while( arc )
-       {
-               ReebArc *next = arc->next;
-               freeArc(arc);
-               arc = next;
-       }
-       
-       // free edge map
-       BLI_edgehash_free(rg->emap, NULL);
-       
-       MEM_freeN(rg);
+       node->degree--;
+
+//     if (node->degree == 0)
+//     {
+//             printf("would remove node %i\n", node->index);
+//     }
 }
 
+void NodeDegreeIncrement(ReebGraph *rg, ReebNode *node)
+{
+//     if (node->degree == 0)
+//     {
+//             printf("first connect node %i\n", node->index);
+//     }
+
+       node->degree++;
+}
+
+#else
+#define NodeDegreeDecrement(rg, node) {node->degree--;}
+#define NodeDegreeIncrement(rg, node) {node->degree++;}
+#endif
+
 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)
@@ -275,23 +436,24 @@ 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);
                }
        }
 }
 
 void verifyNodeDegree(ReebGraph *rg)
 {
+#ifdef DEBUG_REEB
        ReebNode *node = NULL;
        ReebArc *arc = NULL;
 
@@ -300,7 +462,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++;
                        }
@@ -309,1615 +471,3261 @@ void verifyNodeDegree(ReebGraph *rg)
                {
                        printf("degree error in node %i: expected %i got %i\n", node->index, count, node->degree);
                }
+               if (node->degree == 0)
+               {
+                       printf("zero degree node %i with weight %f\n", node->index, node->weight);
+               }
        }
+#endif
 }
 
-void verifyBuckets(ReebGraph *rg)
+void verifyBucketsArc(ReebGraph *rg, ReebArc *arc)
 {
-#ifdef DEBUG_REEB
-       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)
        {
-               if (arc->bcount > 0)
+               int i;
+               for(i = 0; i < arc->bcount; i++)
                {
-                       int i;
-                       for(i = 0; i < arc->bcount; i++)
-                       {
-                               if (arc->buckets[i].nv == 0)
-                               {
-                                       printArc(arc);
-                                       printf("count error in bucket %i/%i\n", i+1, arc->bcount);
-                               }
-                       }
-                       
-                       if (ceil(arc->v1->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));
-                       }
-                       if (floor(arc->v2->weight) < arc->buckets[arc->bcount - 1].val)
+                       if (arc->buckets[i].nv == 0)
                        {
                                printArc(arc);
-                               printf("alloc error in last bucket: %f should be %f \n", arc->buckets[arc->bcount - 1].val, floor(arc->v2->weight));
+                               printf("count error in bucket %i/%i\n", i+1, arc->bcount);
                        }
                }
+               
+               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(head->weight));
+               }
+               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(tail->weight));
+               }
        }
-#endif
-}
-
-/************************************** ADJACENCY LIST *************************************************/
-
-void addArcToNodeAdjacencyList(ReebNode *node, ReebArc *arc)
-{
-       ReebArc **arclist;
-
-       for(arclist = node->arcs; *arclist; arclist++)
-       {       }
-       
-       *arclist = arc;
 }
 
-void buildAdjacencyList(ReebGraph *rg)
+void verifyBuckets(ReebGraph *rg)
 {
-       ReebNode *node = NULL;
+#ifdef DEBUG_REEB
        ReebArc *arc = NULL;
-
-       for(node = rg->nodes.first; node; node = node->next)
+       for(arc = rg->arcs.first; arc; arc = arc->next)
        {
-               if (node->arcs != NULL)
-               {
-                       MEM_freeN(node->arcs);
-               }
-               
-               node->arcs = MEM_callocN((node->degree + 1) * sizeof(ReebArc*), "adjacency list");
+               verifyBucketsArc(rg, arc);
        }
+#endif
+}
 
-       for(arc = rg->arcs.first; arc; arc= arc->next)
+void verifyFaces(ReebGraph *rg)
+{
+#ifdef DEBUG_REEB
+       int total = 0;
+       ReebArc *arc = NULL;
+       for(arc = rg->arcs.first; arc; arc = arc->next)
        {
-               addArcToNodeAdjacencyList(arc->v1, arc);
-               addArcToNodeAdjacencyList(arc->v2, arc);
+               total += BLI_ghash_size(arc->faces);
        }
+       
+#endif
 }
 
-int hasAdjacencyList(ReebGraph *rg)
+void verifyArcs(ReebGraph *rg)
 {
-       ReebNode *node;
+       ReebArc *arc;
        
-       for(node = rg->nodes.first; node; node = node->next)
+       for (arc = rg->arcs.first; arc; arc = arc->next)
        {
-               if (node->arcs == NULL)
+               if (arc->head->weight > arc->tail->weight)
                {
-                       return 0;
+                       printf("FLIPPED ARC!\n");
                }
        }
-       
-       return 1;
 }
 
-int countConnectedArcs(ReebGraph *rg, ReebNode *node)
+void verifyMultiResolutionLinks(ReebGraph *rg, int level)
 {
-       int count = 0;
-       
-       /* use adjacency list if present */
-       if (node->arcs)
-       {
-               ReebArc **arcs;
+#ifdef DEBUG_REEB
+       ReebGraph *lower_rg = rg->link_up;
        
-               for(arcs = node->arcs; *arcs; arcs++)
-               {
-                       count++;
-               }
-       }
-       else
+       if (lower_rg)
        {
                ReebArc *arc;
-               for(arc = rg->arcs.first; arc; arc = arc->next)
+               
+               for (arc = rg->arcs.first; arc; arc = arc->next)
                {
-                       if (arc->v1 == node || arc->v2 == node)
+                       if (BLI_findindex(&lower_rg->arcs, arc->link_up) == -1)
                        {
-                               count++;
+                               printf("missing arc %p for level %i\n", arc->link_up, level);
+                               printf("Source arc was ---\n");
+                               printArc(arc);
+
+                               arc->link_up = NULL;
                        }
                }
+               
+               
+               verifyMultiResolutionLinks(lower_rg, level + 1);
        }
-       
-       return count;
+#endif
 }
+/***************************************** BUCKET UTILS **********************************************/
 
-/****************************************** SMOOTHING **************************************************/
+void addVertToBucket(EmbedBucket *b, float co[3])
+{
+       b->nv++;
+       VecLerpf(b->p, b->p, co, 1.0f / b->nv);
+}
 
-void postprocessGraph(ReebGraph *rg, char mode)
+void removeVertFromBucket(EmbedBucket *b, float co[3])
 {
-       ReebArc *arc;
-       float fac1 = 0, fac2 = 1, fac3 = 0;
+       VecMulf(b->p, (float)b->nv);
+       VecSubf(b->p, b->p, co);
+       b->nv--;
+       VecMulf(b->p, 1.0f / (float)b->nv);
+}
 
-       switch(mode)
+void mergeBuckets(EmbedBucket *bDst, EmbedBucket *bSrc)
+{
+       if (bDst->nv > 0 && bSrc->nv > 0)
        {
-       case SKGEN_AVERAGE:
-               fac1 = fac2 = fac3 = 1.0f / 3.0f;
-               break;
-       case SKGEN_SMOOTH:
-               fac1 = fac3 = 0.25f;
-               fac2 = 0.5f;
-               break;
-       case SKGEN_SHARPEN:
-               fac1 = fac2 = -0.25f;
-               fac2 = 1.5f;
-               break;
-       default:
-               error("Unknown post processing mode");
-               return;
+               bDst->nv += bSrc->nv;
+               VecLerpf(bDst->p, bDst->p, bSrc->p, (float)bSrc->nv / (float)(bDst->nv));
        }
-       
-       for(arc = rg->arcs.first; arc; arc = arc->next)
+       else if (bSrc->nv > 0)
        {
-               EmbedBucket *buckets = arc->buckets;
-               int bcount = arc->bcount;
-               int index;
+               bDst->nv = bSrc->nv;
+               VECCOPY(bDst->p, bSrc->p);
+       }
+}
 
-               for(index = 1; index < bcount - 1; index++)
+void mergeArcBuckets(ReebArc *aDst, ReebArc *aSrc, float start, float end)
+{
+       if (aDst->bcount > 0 && aSrc->bcount > 0)
+       {
+               int indexDst = 0, indexSrc = 0;
+               
+               start = MAX3(start, aDst->buckets[0].val, aSrc->buckets[0].val);
+               
+               while(indexDst < aDst->bcount && aDst->buckets[indexDst].val < start)
                {
-                       VecLerpf(buckets[index].p, buckets[index].p, buckets[index - 1].p, fac1 / (fac1 + fac2));
-                       VecLerpf(buckets[index].p, buckets[index].p, buckets[index + 1].p, fac3 / (fac1 + fac2 + fac3));
+                       indexDst++;
+               }
+
+               while(indexSrc < aSrc->bcount && aSrc->buckets[indexSrc].val < start)
+               {
+                       indexSrc++;
+               }
+               
+               for( ;  indexDst < aDst->bcount &&
+                               indexSrc < aSrc->bcount &&
+                               aDst->buckets[indexDst].val <= end &&
+                               aSrc->buckets[indexSrc].val <= end
+                               
+                        ;      indexDst++, indexSrc++)
+               {
+                       mergeBuckets(aDst->buckets + indexDst, aSrc->buckets + indexSrc);
                }
        }
 }
 
-/********************************************SORTING****************************************************/
-
-int compareNodesWeight(void *vnode1, void *vnode2)
+void flipArcBuckets(ReebArc *arc)
 {
-       ReebNode *node1 = (ReebNode*)vnode1;
-       ReebNode *node2 = (ReebNode*)vnode2;
+       int i, j;
        
-       if (node1->weight < node2->weight)
-       {
-               return -1;
-       }
-       if (node1->weight > node2->weight)
-       {
-               return 1;
-       }
-       else
+       for (i = 0, j = arc->bcount - 1; i < j; i++, j--)
        {
-               return 0;
+               EmbedBucket tmp;
+               
+               tmp = arc->buckets[i];
+               arc->buckets[i] = arc->buckets[j];
+               arc->buckets[j] = tmp;
        }
 }
 
-void sortNodes(ReebGraph *rg)
+int countArcBuckets(ReebArc *arc)
 {
-       BLI_sortlist(&rg->nodes, compareNodesWeight);
+       return (int)(floor(arc->tail->weight) - ceil(arc->head->weight)) + 1;
 }
 
-int compareArcsWeight(void *varc1, void *varc2)
+void allocArcBuckets(ReebArc *arc)
 {
-       ReebArc *arc1 = (ReebArc*)varc1;
-       ReebArc *arc2 = (ReebArc*)varc2;
+       int i;
+       float start = ceil(arc->head->weight);
+       arc->bcount = countArcBuckets(arc);
        
-       if (arc1->v1->weight < arc2->v1->weight)
-       {
-               return -1;
-       }
-       if (arc1->v1->weight > arc2->v1->weight)
+       if (arc->bcount > 0)
        {
-               return 1;
+               arc->buckets = MEM_callocN(sizeof(EmbedBucket) * arc->bcount, "embed bucket");
+               
+               for(i = 0; i < arc->bcount; i++)
+               {
+                       arc->buckets[i].val = start + i;
+               }
        }
        else
        {
-               return 0;
+               arc->buckets = NULL;
        }
+       
 }
 
-void sortArcs(ReebGraph *rg)
-{
-       BLI_sortlist(&rg->arcs, compareArcsWeight);
-}
-
-/****************************************** FILTERING **************************************************/
-
-int compareArcs(void *varc1, void *varc2)
+void resizeArcBuckets(ReebArc *arc)
 {
-       ReebArc *arc1 = (ReebArc*)varc1;
-       ReebArc *arc2 = (ReebArc*)varc2;
-       float len1 = arc1->v2->weight - arc1->v1->weight;
-       float len2 = arc2->v2->weight - arc2->v1->weight;
+       EmbedBucket *oldBuckets = arc->buckets;
+       int oldBCount = arc->bcount;
        
-       if (len1 < len2)
+       if (countArcBuckets(arc) == oldBCount)
        {
-               return -1;
+               return;
        }
-       if (len1 > len2)
+       
+       allocArcBuckets(arc);
+       
+       if (oldBCount != 0 && arc->bcount != 0)
        {
-               return 1;
+               int oldStart = (int)oldBuckets[0].val;
+               int oldEnd = (int)oldBuckets[oldBCount - 1].val;
+               int newStart = (int)arc->buckets[0].val;
+               int newEnd = (int)arc->buckets[arc->bcount - 1].val;
+               int oldOffset = 0;
+               int newOffset = 0;
+               int len;
+               
+               if (oldStart < newStart)
+               {
+                       oldOffset = newStart - oldStart;
+               }
+               else
+               {
+                       newOffset = oldStart - newStart;
+               }
+               
+               len = MIN2(oldEnd - (oldStart + oldOffset) + 1, newEnd - (newStart - newOffset) + 1);
+               
+               memcpy(arc->buckets + newOffset, oldBuckets + oldOffset, len * sizeof(EmbedBucket)); 
        }
-       else
+
+       if (oldBuckets != NULL)
        {
-               return 0;
+               MEM_freeN(oldBuckets);
        }
 }
 
-void filterArc(ReebGraph *rg, ReebNode *newNode, ReebNode *removedNode, ReebArc * srcArc, int merging)
+void reweightBuckets(ReebArc *arc)
 {
-       ReebArc *arc = NULL, *nextArc = NULL;
-
-       /* first pass, merge buckets for arcs that spawned the two nodes into the source arc*/
-       for(arc = rg->arcs.first; arc; arc = arc->next)
+       int i;
+       float start = ceil((arc->head)->weight);
+       
+       if (arc->bcount > 0)
        {
-               if (arc->v1 == srcArc->v1 && arc->v2 == srcArc->v2 && arc != srcArc)
+               for(i = 0; i < arc->bcount; i++)
                {
-                       mergeArcBuckets(srcArc, arc, srcArc->v1->weight, srcArc->v2->weight);
+                       arc->buckets[i].val = start + i;
                }
        }
+}
 
-       /* second pass, replace removedNode by newNode, remove arcs that are collapsed in a loop */
-       arc = rg->arcs.first;
-       while(arc)
+static void interpolateBuckets(ReebArc *arc, float *start_p, float *end_p, int start_index, int end_index)
+{
+       int total;
+       int j;
+       
+       total = end_index - start_index + 2;
+       
+       for (j = start_index; j <= end_index; j++)
        {
-               nextArc = arc->next;
+               EmbedBucket *empty = arc->buckets + j;
+               empty->nv = 1;
+               VecLerpf(empty->p, start_p, end_p, (float)(j - start_index + 1) / total);
+       }
+}
+
+void fillArcEmptyBuckets(ReebArc *arc)
+{
+       float *start_p, *end_p;
+       int start_index, end_index;
+       int missing = 0;
+       int i;
+       
+       start_p = arc->head->p;
+       
+       for(i = 0; i < arc->bcount; i++)
+       {
+               EmbedBucket *bucket = arc->buckets + i;
                
-               if (arc->v1 == removedNode || arc->v2 == removedNode)
+               if (missing)
                {
-                       if (arc->v1 == removedNode)
+                       if (bucket->nv > 0)
                        {
-                               arc->v1 = newNode;
-                       }
-                       else
-                       {
-                               arc->v2 = newNode;
+                               missing = 0;
+                               
+                               end_p = bucket->p;
+                               end_index = i - 1;
+                               
+                               interpolateBuckets(arc, start_p, end_p, start_index, end_index);
                        }
-
-                       // Remove looped arcs                   
-                       if (arc->v1 == arc->v2)
+               }
+               else
+               {
+                       if (bucket->nv == 0)
                        {
-                               // v1 or v2 was already newNode, since we're removing an arc, decrement degree
-                               newNode->degree--;
+                               missing = 1;
                                
-                               // If it's safeArc, it'll be removed later, so keep it for now
-                               if (arc != srcArc)
+                               if (i > 0)
                                {
-                                       BLI_remlink(&rg->arcs, arc);
-                                       freeArc(arc);
-                               }
-                       }
-                       // Remove flipped arcs
-                       else if (arc->v1->weight > arc->v2->weight)
-                       {
-                               // Decrement degree from the other node
-                               OTHER_NODE(arc, newNode)->degree--;
-                               
-                               BLI_remlink(&rg->arcs, arc);
-                               freeArc(arc);
-                       }
-                       else
-                       {
-                               newNode->degree++; // incrementing degree since we're adding an arc
-
-                               if (merging)
-                               {
-                                       // resize bucket list
-                                       resizeArcBuckets(arc);
-                                       mergeArcBuckets(arc, srcArc, arc->v1->weight, arc->v2->weight);
+                                       start_p = arc->buckets[i - 1].p;
                                }
+                               start_index = i;
                        }
                }
+       }
+       
+       if (missing)
+       {
+               end_p = arc->tail->p;
+               end_index = arc->bcount - 1;
                
-               arc = nextArc;
+               interpolateBuckets(arc, start_p, end_p, start_index, end_index);
        }
 }
 
-void filterNullReebGraph(ReebGraph *rg)
+static void ExtendArcBuckets(ReebArc *arc)
 {
-       ReebArc *arc = NULL, *nextArc = NULL;
+       ReebArcIterator iter;
+       EmbedBucket *previous, *bucket, *last_bucket, *first_bucket;
+       float average_length = 0, length;
+       int padding_head = 0, padding_tail = 0;
        
-       arc = rg->arcs.first;
-       while(arc)
+       if (arc->bcount == 0)
        {
-               nextArc = arc->next;
-               // Only collapse arcs too short to have any embed bucket
-               if (arc->bcount == 0)
-               {
-                       ReebNode *newNode = arc->v1;
-                       ReebNode *removedNode = arc->v2;
-                       float blend;
-                       
-                       blend = (float)newNode->degree / (float)(newNode->degree + removedNode->degree); // blending factors
-                       
-                       //newNode->weight = FloatLerpf(newNode->weight, removedNode->weight, blend);
-                       VecLerpf(newNode->p, newNode->p, removedNode->p, blend);