merge more etch-a-ton code. nothing works, but it compiles. Will try to get it workin...
authorMartin Poirier <theeth@yahoo.com>
Fri, 20 Mar 2009 18:00:51 +0000 (18:00 +0000)
committerMartin Poirier <theeth@yahoo.com>
Fri, 20 Mar 2009 18:00:51 +0000 (18:00 +0000)
16 files changed:
source/blender/editors/armature/BIF_generate.h [new file with mode: 0644]
source/blender/editors/armature/BIF_retarget.h [new file with mode: 0644]
source/blender/editors/armature/armature_intern.h
source/blender/editors/armature/editarmature.c
source/blender/editors/armature/editarmature_generate.c [new file with mode: 0644]
source/blender/editors/armature/editarmature_retarget.c [new file with mode: 0644]
source/blender/editors/armature/editarmature_sketch.c [new file with mode: 0644]
source/blender/editors/armature/reeb.c [new file with mode: 0644]
source/blender/editors/armature/reeb.h
source/blender/editors/include/BIF_transform.h
source/blender/editors/include/ED_armature.h
source/blender/editors/space_view3d/view3d_buttons.c
source/blender/editors/space_view3d/view3d_draw.c
source/blender/editors/space_view3d/view3d_view.c
source/blender/editors/transform/transform_snap.c
source/blender/windowmanager/intern/wm_init_exit.c

diff --git a/source/blender/editors/armature/BIF_generate.h b/source/blender/editors/armature/BIF_generate.h
new file mode 100644 (file)
index 0000000..8d561d2
--- /dev/null
@@ -0,0 +1,45 @@
+/**
+ * $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.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#ifndef BIF_GENERATE_H
+#define BIF_GENERATE_H
+
+struct bContext;
+struct EditBone;
+struct BArcIterator;
+struct bArmature;
+struct ListBase;
+
+typedef int(NextSubdivisionFunc)(struct bContext*, struct BArcIterator*, int, int, float[3], float[3]);
+float calcArcCorrelation(struct BArcIterator *iter, int start, int end, float v0[3], float n[3]);
+
+int nextFixedSubdivision(struct bContext *C, struct BArcIterator *iter, int start, int end, float head[3], float p[3]);
+int nextLengthSubdivision(struct bContext *C, struct BArcIterator *iter, int start, int end, float head[3], float p[3]);
+int nextAdaptativeSubdivision(struct bContext *C, struct BArcIterator *iter, int start, int end, float head[3], float p[3]);
+
+struct EditBone * subdivideArcBy(struct bContext *C, struct bArmature *arm, ListBase *editbones, struct BArcIterator *iter, float invmat[][4], float tmat[][3], NextSubdivisionFunc next_subdividion);
+
+void setBoneRollFromNormal(struct EditBone *bone, float *no, float invmat[][4], float tmat[][3]);
+
+#endif /* BIF_GENERATE_H */
diff --git a/source/blender/editors/armature/BIF_retarget.h b/source/blender/editors/armature/BIF_retarget.h
new file mode 100644 (file)
index 0000000..049ddf5
--- /dev/null
@@ -0,0 +1,160 @@
+/**
+ * $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.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef BIF_RETARGET_H
+#define BIF_RETARGET_H
+
+#include "DNA_listBase.h"
+
+#include "BLI_graph.h"
+#include "BLI_ghash.h"
+#include "BLI_threads.h"
+
+#include "reeb.h"
+
+struct Object;
+struct bArmature;
+struct bContext;
+
+struct EditBone;
+
+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;
+       /*********************************/
+       
+       int                     flag;
+
+       ListBase        controls;
+       ListBase*       editbones;
+       
+       struct RigNode *head;
+       ReebGraph *link_mesh;
+       
+       
+       struct ThreadedWorker *worker;
+       
+       GHash *bones_map;       /* map of editbones by name */
+       GHash *controls_map;    /* map of rigcontrols by bone pointer */
+       
+       struct 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; /* angle to next edge */
+       float up_angle; /* angle between up_axis and the joint normal (defined as Previous edge CrossProduct Current edge */
+       struct EditBone *bone;
+       float up_axis[3];
+} RigEdge;
+
+/* Graph flags */
+#define        RIG_FREE_BONELIST               1
+
+/* Control flags */
+#define RIG_CTRL_HEAD_DONE             1
+#define RIG_CTRL_TAIL_DONE             2
+#define RIG_CTRL_PARENT_DEFORM 4
+#define RIG_CTRL_FIT_ROOT              8
+#define RIG_CTRL_FIT_BONE              16
+
+#define RIG_CTRL_DONE  (RIG_CTRL_HEAD_DONE|RIG_CTRL_TAIL_DONE)
+
+/* Control tail flags */
+typedef enum {
+       TL_NONE = 0,
+       TL_TAIL,
+       TL_HEAD
+} LinkTailMode;
+
+typedef struct RigControl {
+       struct RigControl *next, *prev;
+       float head[3], tail[3];
+       struct EditBone *bone;
+       struct EditBone *link;
+       struct EditBone *link_tail;
+       float   up_axis[3];
+       float   offset[3];
+       float   qrot[4]; /* for dual linked bones, store the rotation of the linked bone for the finalization */
+       int             flag;
+       LinkTailMode tail_mode;
+} RigControl;
+
+void BIF_retargetArc(struct bContext *C, ReebArc *earc, RigGraph *template_rigg);
+RigGraph *RIG_graphFromArmature(struct bContext *C, struct Object *ob, struct bArmature *arm);
+int RIG_nbJoints(RigGraph *rg);
+char *RIG_nameBone(RigGraph *rg, int arc_index, int bone_index);
+void RIG_freeRigGraph(BGraph *rg);
+
+#endif /* BIF_RETARGET_H */
index 06b6efab94b3bb3dbfd23df069902c3b5f653912..ee3b80cd8f48345d4bdd0937900d3a77636d629b 100644 (file)
@@ -64,6 +64,9 @@ void POSE_OT_select_connected(struct wmOperatorType *ot);
 /* editarmature.c */
 struct bArmature;
 struct EditBone;
+struct ListBase;
+
+void make_boneList(struct ListBase *edbo, struct ListBase *bones, struct EditBone *parent);
 
 struct EditBone *addEditBone(struct bArmature *arm, char *name);
 
index 2aed96b61c577c62ab42db1cdc342979f40a5662..3ac6f1838c1ae5b6890bda8bcbfb5b9a3aab1208 100644 (file)
@@ -75,7 +75,7 @@
 
 #include "BIF_gl.h"
 #include "BIF_transform.h"
-// XXX etch-a-ton #include "BIF_generate.h"
+#include "BIF_generate.h"
 
 #include "RNA_access.h"
 #include "RNA_define.h"
@@ -1762,6 +1762,8 @@ void mouse_armature(bContext *C, short mval[2], int extend)
 
        view3d_set_viewcontext(C, &vc);
        
+       BIF_sk_selectStroke(C, mval, extend);
+       
        nearBone= get_nearest_editbonepoint(&vc, mval, arm->edbo, 1, &selmask);
        if (nearBone) {
 
@@ -1856,7 +1858,7 @@ void ED_armature_to_edit(Object *ob)
        arm->edbo= MEM_callocN(sizeof(ListBase), "edbo armature");
        make_boneList(arm->edbo, &arm->bonebase,NULL);
 
-       // XXX etch-a-ton BIF_freeTemplates(); /* force template update when entering editmode */
+//     BIF_freeTemplates(); /* force template update when entering editmode */
 }
 
 
diff --git a/source/blender/editors/armature/editarmature_generate.c b/source/blender/editors/armature/editarmature_generate.c
new file mode 100644 (file)
index 0000000..938a6a0
--- /dev/null
@@ -0,0 +1,331 @@
+/**
+ * $Id: editarmature_generate.c  $
+ *
+ * ***** 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.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ * editarmature.c: Interface for creating and posing armature objects
+ */
+
+#include <string.h>
+#include <math.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_listBase.h"
+#include "DNA_scene_types.h"
+#include "DNA_armature_types.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_arithb.h"
+#include "BLI_graph.h"
+#include "BKE_utildefines.h"
+#include "BKE_global.h"
+#include "BKE_context.h"
+
+#include "ED_armature.h"
+#include "BIF_generate.h"
+
+void setBoneRollFromNormal(EditBone *bone, float *no, float invmat[][4], float tmat[][3])
+{
+       if (no != NULL && !VecIsNull(no))
+       {
+               float tangent[3], cotangent[3], normal[3];
+
+               VECCOPY(normal, no);    
+               Mat3MulVecfl(tmat, normal);
+
+               VecSubf(tangent, bone->tail, bone->head);
+               Crossf(cotangent, tangent, normal);
+               Crossf(normal, cotangent, tangent);
+               
+               Normalize(normal);
+               
+               bone->roll = ED_rollBoneToVector(bone, normal);
+       }
+}
+
+float calcArcCorrelation(BArcIterator *iter, int start, int end, float v0[3], float n[3])
+{
+       int len = 2 + abs(end - start);
+       
+       if (len > 2)
+       {
+               float avg_t = 0.0f;
+               float s_t = 0.0f;
+               float s_xyz = 0.0f;
+               int i;
+               
+               /* First pass, calculate average */
+               for (i = start; i <= end; i++)
+               {
+                       float v[3];
+                       
+                       IT_peek(iter, i);
+                       VecSubf(v, iter->p, v0);
+                       avg_t += Inpf(v, n);
+               }
+               
+               avg_t /= Inpf(n, n);
+               avg_t += 1.0f; /* adding start (0) and end (1) values */
+               avg_t /= len;
+               
+               /* Second pass, calculate s_xyz and s_t */
+               for (i = start; i <= end; i++)
+               {
+                       float v[3], d[3];
+                       float dt;
+                       
+                       IT_peek(iter, i);
+                       VecSubf(v, iter->p, v0);
+                       Projf(d, v, n);
+                       VecSubf(v, v, d);
+                       
+                       dt = VecLength(d) - avg_t;
+                       
+                       s_t += dt * dt;
+                       s_xyz += Inpf(v, v);
+               }
+               
+               /* 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; 
+       }
+       else
+       {
+               return 1.0f;
+       }
+}
+
+int nextFixedSubdivision(bContext *C, BArcIterator *iter, int start, int end, float head[3], float p[3])
+{
+       static float stroke_length = 0;
+       static float current_length;
+       static char n;
+       Scene *scene = CTX_data_scene(C);
+       float *v1, *v2;
+       float length_threshold;
+       int i;
+       
+       if (stroke_length == 0)
+       {
+               current_length = 0;
+
+               IT_peek(iter, start);
+               v1 = iter->p;
+               
+               for (i = start + 1; i <= end; i++)
+               {
+                       IT_peek(iter, i);
+                       v2 = iter->p;
+
+                       stroke_length += VecLenf(v1, v2);
+                       
+                       v1 = v2;
+               }
+               
+               n = 0;
+               current_length = 0;
+       }
+       
+       n++;
+       
+       length_threshold = n * stroke_length / scene->toolsettings->skgen_subdivision_number;
+       
+       IT_peek(iter, start);
+       v1 = iter->p;
+
+       /* < and not <= because we don't care about end, it is P_EXACT anyway */
+       for (i = start + 1; i < end; i++)
+       {
+               IT_peek(iter, i);
+               v2 = iter->p;
+
+               current_length += VecLenf(v1, v2);
+
+               if (current_length >= length_threshold)
+               {
+                       VECCOPY(p, v2);
+                       return i;
+               }
+               
+               v1 = v2;
+       }
+       
+       stroke_length = 0;
+       
+       return -1;
+}
+int nextAdaptativeSubdivision(bContext *C, BArcIterator *iter, int start, int end, float head[3], float p[3])
+{
+       Scene *scene = CTX_data_scene(C);
+       float correlation_threshold = scene->toolsettings->skgen_correlation_limit;
+       float *start_p;
+       float n[3];
+       int i;
+       
+       IT_peek(iter, start);
+       start_p = iter->p;
+
+       for (i = start + 2; i <= end; i++)
+       {
+               /* Calculate normal */
+               IT_peek(iter, i);
+               VecSubf(n, iter->p, head);
+
+               if (calcArcCorrelation(iter, start, i, start_p, n) < correlation_threshold)
+               {
+                       IT_peek(iter, i - 1);
+                       VECCOPY(p, iter->p);
+                       return i - 1;
+               }
+       }
+       
+       return -1;
+}
+
+int nextLengthSubdivision(bContext *C, BArcIterator *iter, int start, int end, float head[3], float p[3])
+{
+       Scene *scene = CTX_data_scene(C);
+       float lengthLimit = scene->toolsettings->skgen_length_limit;
+       int same = 1;
+       int i;
+       
+       i = start + 1;
+       while (i <= end)
+       {
+               float *vec0;
+               float *vec1;
+               
+               IT_peek(iter, i - 1);
+               vec0 = iter->p;
+
+               IT_peek(iter, i);
+               vec1 = iter->p;
+               
+               /* If lengthLimit hits the current segment */
+               if (VecLenf(vec1, head) > lengthLimit)
+               {
+                       if (same == 0)
+                       {
+                               float dv[3], off[3];
+                               float a, b, c, f;
+                               
+                               /* Solve quadratic distance equation */
+                               VecSubf(dv, vec1, vec0);
+                               a = Inpf(dv, dv);
+                               
+                               VecSubf(off, vec0, head);
+                               b = 2 * Inpf(dv, off);
+                               
+                               c = Inpf(off, off) - (lengthLimit * lengthLimit);
+                               
+                               f = (-b + (float)sqrt(b * b - 4 * a * c)) / (2 * a);
+                               
+                               //printf("a %f, b %f, c %f, f %f\n", a, b, c, f);
+                               
+                               if (isnan(f) == 0 && f < 1.0f)
+                               {
+                                       VECCOPY(p, dv);
+                                       VecMulf(p, f);
+                                       VecAddf(p, p, vec0);
+                               }
+                               else
+                               {
+                                       VECCOPY(p, vec1);
+                               }
+                       }
+                       else
+                       {
+                               float dv[3];
+                               
+                               VecSubf(dv, vec1, vec0);
+                               Normalize(dv);
+                                
+                               VECCOPY(p, dv);
+                               VecMulf(p, lengthLimit);
+                               VecAddf(p, p, head);
+                       }
+                       
+                       return i - 1; /* restart at lower bound */
+               }
+               else
+               {
+                       i++;
+                       same = 0; // Reset same
+               }
+       }
+       
+       return -1;
+}
+
+EditBone * subdivideArcBy(bContext *C, bArmature *arm, ListBase *editbones, BArcIterator *iter, float invmat[][4], float tmat[][3], NextSubdivisionFunc next_subdividion)
+{
+       EditBone *lastBone = NULL;
+       EditBone *child = NULL;
+       EditBone *parent = NULL;
+       int bone_start = 0;
+       int end = iter->length;
+       int index;
+       
+       IT_head(iter);
+       
+       parent = addEditBone(arm, "Bone");
+       VECCOPY(parent->head, iter->p);
+       
+       index = next_subdividion(C, iter, bone_start, end, parent->head, parent->tail);
+       while (index != -1)
+       {
+               IT_peek(iter, index);
+
+               child = addEditBone(arm, "Bone");
+               VECCOPY(child->head, parent->tail);
+               child->parent = parent;
+               child->flag |= BONE_CONNECTED;
+               
+               /* going to next bone, fix parent */
+               Mat4MulVecfl(invmat, parent->tail);
+               Mat4MulVecfl(invmat, parent->head);
+               setBoneRollFromNormal(parent, iter->no, invmat, tmat);
+
+               parent = child; // new child is next parent
+               bone_start = index; // start next bone from current index
+
+               index = next_subdividion(C, iter, bone_start, end, parent->head, parent->tail);
+       }
+       
+       iter->tail(iter);
+
+       VECCOPY(parent->tail, iter->p);
+
+       /* fix last bone */
+       Mat4MulVecfl(invmat, parent->tail);
+       Mat4MulVecfl(invmat, parent->head);
+       setBoneRollFromNormal(parent, iter->no, invmat, tmat);
+       lastBone = parent;
+       
+       return lastBone;
+}
diff --git a/source/blender/editors/armature/editarmature_retarget.c b/source/blender/editors/armature/editarmature_retarget.c
new file mode 100644 (file)
index 0000000..37ffb9f
--- /dev/null
@@ -0,0 +1,2961 @@
+/**
+ * $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> 
+#include <float.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 "BKE_context.h"
+
+#include "ED_armature.h"
+#include "BIF_retarget.h"
+//#include "BIF_space.h"
+//#include "BIF_toolbox.h"
+
+#include "PIL_time.h"
+
+//#include "mydevice.h"
+#include "reeb.h" // FIX ME
+//#include "blendef.h"
+
+#include "armature_intern.h"
+
+/************ RIG RETARGET DATA STRUCTURES ***************/
+
+typedef struct MemoNode {
+       float   weight;
+       int     next;
+} MemoNode;
+
+typedef struct RetargetParam {
+       RigGraph        *rigg;
+       RigArc          *iarc;
+       RigNode         *inode_start;
+       bContext        *context;
+} RetargetParam;
+
+typedef enum 
+{
+       RETARGET_LENGTH,
+       RETARGET_AGGRESSIVE
+} RetargetMode; 
+
+typedef enum
+{
+       METHOD_BRUTE_FORCE = 0,
+       METHOD_MEMOIZE = 1
+} 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_calculateEdgeAngles(RigEdge *edge_first, RigEdge *edge_second);
+float rollBoneByQuat(EditBone *bone, float old_up_axis[3], float qrot[4]);
+
+/* 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 rollBoneByQuatAligned(EditBone *bone, float old_up_axis[3], float qrot[4], float qroll[4], float aligned_axis[3])
+{
+       float nor[3], new_up_axis[3], x_axis[3], z_axis[3];
+       
+       VECCOPY(new_up_axis, old_up_axis);
+       QuatMulVecf(qrot, new_up_axis);
+       
+       VecSubf(nor, bone->tail, bone->head);
+       
+       Crossf(x_axis, nor, aligned_axis);
+       Crossf(z_axis, x_axis, nor);
+       
+       Normalize(new_up_axis);
+       Normalize(x_axis);
+       Normalize(z_axis);
+       
+       if (Inpf(new_up_axis, x_axis) < 0)
+       {
+               VecMulf(x_axis, -1);
+       }
+       
+       if (Inpf(new_up_axis, z_axis) < 0)
+       {
+               VecMulf(z_axis, -1);
+       }
+       
+       if (NormalizedVecAngle2(x_axis, new_up_axis) < NormalizedVecAngle2(z_axis, new_up_axis))
+       {
+               RotationBetweenVectorsToQuat(qroll, new_up_axis, x_axis); /* set roll rotation quat */
+               return ED_rollBoneToVector(bone, x_axis);
+       }
+       else
+       {
+               RotationBetweenVectorsToQuat(qroll, new_up_axis, z_axis); /* set roll rotation quat */
+               return ED_rollBoneToVector(bone, z_axis);
+       }
+}
+
+float rollBoneByQuatJoint(RigEdge *edge, RigEdge *previous, float qrot[4], float qroll[4])
+{
+       if (previous == NULL)
+       {
+               QuatOne(qroll);
+               return rollBoneByQuat(edge->bone, edge->up_axis, qrot);
+       }
+       else
+       {
+               float new_up_axis[3];
+               float vec_first[3], vec_second[3], normal[3];
+               
+               if (previous->bone)
+               {
+                       VecSubf(vec_first, previous->bone->tail, previous->bone->head);
+               } 
+               else if (previous->prev->bone)
+               {
+                       VecSubf(vec_first, edge->bone->head, previous->prev->bone->tail);
+               }
+               else
+               {
+                       /* SHOULDN'T BE HERE */
+                       QuatOne(qroll);
+                       return rollBoneByQuat(edge->bone, edge->up_axis, qrot);
+               }
+               
+               VecSubf(vec_second, edge->bone->tail, edge->bone->head);
+       
+               Normalize(vec_first);
+               Normalize(vec_second);
+               
+               Crossf(normal, vec_first, vec_second);
+               Normalize(normal);
+               
+               AxisAngleToQuat(qroll, vec_second, edge->up_angle);
+               
+               QuatMulVecf(qroll, normal);
+                       
+               VECCOPY(new_up_axis, edge->up_axis);
+               QuatMulVecf(qrot, new_up_axis);
+               
+               Normalize(new_up_axis);
+               
+               /* real qroll between normal and up_axis */
+               RotationBetweenVectorsToQuat(qroll, new_up_axis, normal);
+
+               return ED_rollBoneToVector(edge->bone, normal);
+       }
+}
+
+float rollBoneByQuat(EditBone *bone, float old_up_axis[3], float qrot[4])
+{
+       float new_up_axis[3];
+       
+       VECCOPY(new_up_axis, old_up_axis);
+       QuatMulVecf(qrot, new_up_axis);
+       
+       Normalize(new_up_axis);
+       
+       return ED_rollBoneToVector(bone, new_up_axis);
+}
+
+/************************************ DESTRUCTORS ******************************************************/
+
+void RIG_freeRigArc(BArc *arc)
+{
+       BLI_freelistN(&((RigArc*)arc)->edges);
+}
+
+void RIG_freeRigGraph(BGraph *rg)
+{
+       RigGraph *rigg = (RigGraph*)rg;
+       BNode *node;
+       BArc *arc;
+       
+#ifdef USE_THREADS
+       BLI_destroy_worker(rigg->worker);
+#endif
+       
+       if (rigg->link_mesh)
+       {
+               REEB_freeGraph(rigg->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(&rigg->controls);
+
+       BLI_ghash_free(rigg->bones_map, NULL, NULL);
+       BLI_ghash_free(rigg->controls_map, NULL, NULL);
+       
+       if (rigg->flag & RIG_FREE_BONELIST)
+       {
+               BLI_freelistN(rigg->editbones);
+               MEM_freeN(rigg->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_calculateEdgeAngles(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);
+}
+/************************************** CLONING TEMPLATES **********************************************/
+
+static void renameTemplateBone(char *name, char *template_name, ListBase *editbones, char *side_string, char *num_string)
+{
+       int i, j;
+       
+       for (i = 0, j = 0; template_name[i] != '\0' && i < 31 && j < 31; i++)
+       {
+               if (template_name[i] == '&')
+               {
+                       if (template_name[i+1] == 'S' || template_name[i+1] == 's')
+                       {
+                               j += sprintf(name + j, side_string);
+                               i++;
+                       }
+                       else if (template_name[i+1] == 'N' || template_name[i+1] == 'n')
+                       {
+                               j += sprintf(name + j, num_string);
+                               i++;
+                       }
+                       else
+                       {
+                               name[j] = template_name[i];
+                               j++;
+                       }
+               }
+               else
+               {
+                       name[j] = template_name[i];
+                       j++;
+               }
+       }
+       
+       name[j] = '\0';
+       
+       unique_editbone_name(editbones, name, NULL);
+}
+
+static RigControl *cloneControl(RigGraph *rg, RigGraph *src_rg, RigControl *src_ctrl, GHash *ptr_hash, char *side_string, char *num_string)
+{
+       RigControl *ctrl;
+       char name[32];
+       
+       ctrl = newRigControl(rg);
+       
+       VECCOPY(ctrl->head, src_ctrl->head);
+       VECCOPY(ctrl->tail, src_ctrl->tail);
+       VECCOPY(ctrl->up_axis, src_ctrl->up_axis);
+       VECCOPY(ctrl->offset, src_ctrl->offset);
+       
+       ctrl->tail_mode = src_ctrl->tail_mode;
+       ctrl->flag = src_ctrl->flag;
+
+       renameTemplateBone(name, src_ctrl->bone->name, rg->editbones, side_string, num_string);
+       ctrl->bone = duplicateEditBoneObjects(src_ctrl->bone, name, rg->editbones, src_rg->ob, rg->ob);
+       ctrl->bone->flag &= ~(BONE_TIPSEL|BONE_SELECTED|BONE_ROOTSEL|BONE_ACTIVE);
+       BLI_ghash_insert(ptr_hash, src_ctrl->bone, ctrl->bone);
+       
+       ctrl->link = src_ctrl->link;
+       ctrl->link_tail = src_ctrl->link_tail;
+       
+       return ctrl;
+}
+
+static RigArc *cloneArc(RigGraph *rg, RigGraph *src_rg, RigArc *src_arc, GHash *ptr_hash, char *side_string, char *num_string)
+{
+       RigEdge *src_edge;
+       RigArc  *arc;
+       
+       arc = newRigArc(rg);
+       
+       arc->head = BLI_ghash_lookup(ptr_hash, src_arc->head);
+       arc->tail = BLI_ghash_lookup(ptr_hash, src_arc->tail);
+       
+       arc->head->degree++;
+       arc->tail->degree++;
+       
+       arc->length = src_arc->length;
+
+       arc->count = src_arc->count;
+       
+       for (src_edge = src_arc->edges.first; src_edge; src_edge = src_edge->next)
+       {
+               RigEdge *edge;
+       
+               edge = MEM_callocN(sizeof(RigEdge), "rig edge");
+
+               VECCOPY(edge->head, src_edge->head);
+               VECCOPY(edge->tail, src_edge->tail);
+               VECCOPY(edge->up_axis, src_edge->up_axis);
+               
+               edge->length = src_edge->length;
+               edge->angle = src_edge->angle;
+               edge->up_angle = src_edge->up_angle;
+               
+               if (src_edge->bone != NULL)
+               {
+                       char name[32];
+                       renameTemplateBone(name, src_edge->bone->name, rg->editbones, side_string, num_string);
+                       edge->bone = duplicateEditBoneObjects(src_edge->bone, name, rg->editbones, src_rg->ob, rg->ob);
+                       edge->bone->flag &= ~(BONE_TIPSEL|BONE_SELECTED|BONE_ROOTSEL|BONE_ACTIVE);
+                       BLI_ghash_insert(ptr_hash, src_edge->bone, edge->bone);
+               }
+
+               BLI_addtail(&arc->edges, edge);
+       }
+       
+       return arc;
+}
+
+static RigGraph *cloneRigGraph(RigGraph *src, ListBase *editbones, Object *ob, char *side_string, char *num_string)
+{
+       GHash   *ptr_hash;      
+       RigNode *node;
+       RigArc  *arc;
+       RigControl *ctrl;
+       RigGraph *rg;
+       
+       ptr_hash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
+
+       rg = newRigGraph();
+       
+       rg->ob = ob;
+       rg->editbones = editbones;
+       
+       preEditBoneDuplicate(rg->editbones); /* prime bones for duplication */
+       preEditBoneDuplicate(src->editbones); /* prime bones for duplication */
+       
+       /* Clone nodes */
+       for (node = src->nodes.first; node; node = node->next)
+       {
+               RigNode *cloned_node = newRigNode(rg, node->p);
+               BLI_ghash_insert(ptr_hash, node, cloned_node);
+       }
+       
+       rg->head = BLI_ghash_lookup(ptr_hash, src->head);
+       
+       /* Clone arcs */
+       for (arc = src->arcs.first; arc; arc = arc->next)
+       {
+               cloneArc(rg, src, arc, ptr_hash, side_string, num_string);
+       }
+       
+       /* Clone controls */
+       for (ctrl = src->controls.first; ctrl; ctrl = ctrl->next)
+       {
+               cloneControl(rg, src, ctrl, ptr_hash, side_string, num_string);
+       }
+       
+       /* Relink bones properly */
+       for (arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               RigEdge *edge;
+               
+               for (edge = arc->edges.first; edge; edge = edge->next)
+               {
+                       if (edge->bone != NULL)
+                       {
+                               EditBone *bone;
+                               
+                               updateDuplicateSubtargetObjects(edge->bone, src->editbones, src->ob, rg->ob);
+
+                               if (edge->bone->parent)
+                               {                               
+                                       bone = BLI_ghash_lookup(ptr_hash, edge->bone->parent);
+               
+                                       if (bone != NULL)
+                                       {
+                                               edge->bone->parent = bone;
+                                       }
+                                       else
+                                       {
+                                               /* disconnect since parent isn't cloned
+                                                * this will only happen when cloning from selected bones 
+                                                * */
+                                               edge->bone->flag &= ~BONE_CONNECTED;
+                                       }
+                               }
+                       }
+               }
+       }
+       
+       for (ctrl = rg->controls.first; ctrl; ctrl = ctrl->next)
+       {
+               EditBone *bone;
+               
+               updateDuplicateSubtargetObjects(ctrl->bone, src->editbones, src->ob, rg->ob);
+
+               if (ctrl->bone->parent)
+               {
+                       bone = BLI_ghash_lookup(ptr_hash, ctrl->bone->parent);
+                       
+                       if (bone != NULL)
+                       {
+                               ctrl->bone->parent = bone;
+                       }
+                       else
+                       {
+                               /* disconnect since parent isn't cloned
+                                * this will only happen when cloning from selected bones 
+                                * */
+                               ctrl->bone->flag &= ~BONE_CONNECTED;
+                       }
+               }
+
+               ctrl->link = BLI_ghash_lookup(ptr_hash, ctrl->link);
+               ctrl->link_tail = BLI_ghash_lookup(ptr_hash, ctrl->link_tail);
+       }
+       
+       BLI_ghash_free(ptr_hash, NULL, NULL);
+       
+       return rg;
+}
+
+
+/*******************************************************************************************************/
+
+static void RIG_calculateEdgeAngles(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 = NormalizedVecAngle2(vec_first, vec_second);
+       
+       if (edge_second->bone != NULL)
+       {
+               float normal[3];
+
+               Crossf(normal, vec_first, vec_second);
+               Normalize(normal);
+
+               edge_second->up_angle = NormalizedVecAngle2(normal, edge_second->up_axis);
+       }
+}
+
+/************************************ 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);
+       ctrl->tail_mode = TL_NONE;
+       
+       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)
+                               {
+                                       int target_index;
+                                       
+                                       cti->get_constraint_targets(con, &targets);
+                                       
+                                       for (target_index = 0, ct= targets.first; ct; target_index++, 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);
+                                                       
+                                                       /* Making sure bone is in this armature */
+                                                       if (link != NULL)
+                                                       {
+                                                               /* for pole targets, link to parent bone instead, if possible */
+                                                               if (con->type == CONSTRAINT_TYPE_KINEMATIC && target_index == 1)
+                                                               {
+                                                                       if (link->parent && BLI_ghash_haskey(rg->bones_map, link->parent->name))
+                                                                       {
+                                                                               link = link->parent;
+                                                                       }
+                                                               }
+                                                               
+                                                               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;
+               
+               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)
+                                                                       {
+                                                                               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)
+                                       {
+                                               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)
+                                                       {
+                                                               RIG_parentControl(ctrl, ctrl_child->bone);
+                                                               change = 1;
+                                                               break;
+                                                       }
+                                               }
+                                       }
+                               }
+                       }
+               }
+       }
+       
+       /* third pass, link control tails */
+       for (ctrl = rg->controls.first; ctrl; ctrl = ctrl->next)
+       {
+               /* fit bone already means full match, so skip those */
+               if ((ctrl->flag & RIG_CTRL_FIT_BONE) == 0)
+               {
+                       GHashIterator ghi;
+                       
+                       /* look on deform bones first */
+                       BLI_ghashIterator_init(&ghi, rg->bones_map);
+                       
+                       for( ; !BLI_ghashIterator_isDone(&ghi); BLI_ghashIterator_step(&ghi))
+                       {
+                               EditBone *bone = (EditBone*)BLI_ghashIterator_getValue(&ghi);
+                               
+                               /* don't link with parent */
+                               if (bone->parent != ctrl->bone)
+                               {
+                                       if (VecLenf(ctrl->bone->tail, bone->head) < 0.01)
+                                       {
+                                               ctrl->tail_mode = TL_HEAD;
+                                               ctrl->link_tail = bone;
+                                               break;
+                                       }
+                                       else if (VecLenf(ctrl->bone->tail, bone->tail) < 0.01)
+                                       {
+                                               ctrl->tail_mode = TL_TAIL;
+                                               ctrl->link_tail = bone;
+                                               break;
+                                       }
+                               }
+                       }
+                       
+                       /* if we haven't found one yet, look in control bones */
+                       if (ctrl->tail_mode == TL_NONE)
+                       {
+                       }
+               }
+       }
+       
+}
+
+/*******************************************************************************************************/
+
+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, int selected)
+{
+       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 (selected == 0 || (bone->flag & BONE_SELECTED))
+               { 
+                       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, selected);
+                       }
+                       
+                       /* 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");
+       }       
+}
+
+/*******************************************************************************************************/
+
+RigGraph *RIG_graphFromArmature(bContext *C, Object *ob, bArmature *arm)
+{
+       Object *obedit = CTX_data_edit_object(C);
+       Scene *scene = CTX_data_scene(C);
+       EditBone *ebone;
+       RigGraph *rg;
+       
+       rg = newRigGraph();
+       
+       if (obedit == ob)
+       {
+               bArmature *arm = obedit->data;
+               rg->editbones = arm->edbo;
+       }
+       else
+       {
+               rg->editbones = MEM_callocN(sizeof(ListBase), "EditBones");
+               make_boneList(rg->editbones, &arm->bonebase, NULL);
+               rg->flag |= RIG_FREE_BONELIST;
+       }
+       
+       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, 0);
+               }
+       }
+       
+       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, 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;
+}
+
+RigGraph *armatureSelectedToGraph(bContext *C, Object *ob, bArmature *arm)
+{
+       Object *obedit = CTX_data_edit_object(C);
+       Scene *scene = CTX_data_scene(C);
+       EditBone *ebone;
+       RigGraph *rg;
+       
+       rg = newRigGraph();
+       
+       if (obedit == ob)
+       {
+               rg->editbones = arm->edbo;
+       }
+       else
+       {
+               rg->editbones = MEM_callocN(sizeof(ListBase), "EditBones");
+               make_boneList(rg->editbones, &arm->bonebase, NULL);
+               rg->flag |= RIG_FREE_BONELIST;
+       }
+
+       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, 1);
+               }
+       }
+       
+       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, 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, NULL);
+       
+       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;
+}
+
+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);
+
+static void repositionTailControl(RigGraph *rigg, RigControl *ctrl);
+
+static void finalizeControl(RigGraph *rigg, RigControl *ctrl, float resize)
+{
+       if ((ctrl->flag & RIG_CTRL_DONE) == RIG_CTRL_DONE)
+       {
+               RigControl *ctrl_child;
+
+#if 0          
+               printf("CTRL: %s LINK: %s", ctrl->bone->name, ctrl->link->name);
+               
+               if (ctrl->link_tail)
+               {
+                       printf(" TAIL: %s", ctrl->link_tail->name);
+               }
+               
+               printf("\n");
+#endif
+               
+               /* if there was a tail link: apply link, recalc resize factor and qrot */
+               if (ctrl->tail_mode != TL_NONE)
+               {
+                       float *tail_vec = NULL;
+                       float v1[3], v2[3], qtail[4];
+                       
+                       if (ctrl->tail_mode == TL_TAIL)
+                       {
+                               tail_vec = ctrl->link_tail->tail;
+                       }
+                       else if (ctrl->tail_mode == TL_HEAD)
+                       {
+                               tail_vec = ctrl->link_tail->head;
+                       }
+                       
+                       VecSubf(v1, ctrl->bone->tail, ctrl->bone->head);
+                       VecSubf(v2, tail_vec, ctrl->bone->head);
+                       
+                       VECCOPY(ctrl->bone->tail, tail_vec);
+                       
+                       RotationBetweenVectorsToQuat(qtail, v1, v2);
+                       QuatMul(ctrl->qrot, qtail, ctrl->qrot);
+                       
+                       resize = VecLength(v2) / VecLenf(ctrl->head, ctrl->tail);
+               }
+               
+               ctrl->bone->roll = rollBoneByQuat(ctrl->bone, ctrl->up_axis, ctrl->qrot);
+       
+               /* 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, ctrl->qrot, resize);
+                       }
+                       if (ctrl_child->link_tail == ctrl->bone)
+                       {
+                               repositionTailControl(rigg, ctrl_child);
+                       }
+               }
+       }       
+}
+
+static void repositionTailControl(RigGraph *rigg, RigControl *ctrl)
+{
+       ctrl->flag |= RIG_CTRL_TAIL_DONE;
+
+       finalizeControl(rigg, ctrl, 1); /* resize will be recalculated anyway so we don't need it */
+}
+
+static void repositionControl(RigGraph *rigg, RigControl *ctrl, float head[3], float tail[3], float qrot[4], float resize)
+{
+       float parent_offset[3], tail_offset[3];
+       
+       VECCOPY(parent_offset, ctrl->offset);
+       VecMulf(parent_offset, resize);
+       QuatMulVecf(qrot, parent_offset);
+       
+       VecAddf(ctrl->bone->head, head, parent_offset); 
+
+       ctrl->flag |= RIG_CTRL_HEAD_DONE;
+
+       QUATCOPY(ctrl->qrot, qrot); 
+
+       if (ctrl->tail_mode == TL_NONE)
+       {
+               VecSubf(tail_offset, ctrl->tail, ctrl->head);
+               VecMulf(tail_offset, resize);
+               QuatMulVecf(qrot, tail_offset);
+
+               VecAddf(ctrl->bone->tail, ctrl->bone->head, tail_offset);
+               
+               ctrl->flag |= RIG_CTRL_TAIL_DONE;
+       }
+
+       finalizeControl(rigg, ctrl, resize);
+}
+
+static void repositionBone(bContext *C, RigGraph *rigg, RigEdge *edge, float vec0[3], float vec1[3], float up_axis[3])
+{
+       Scene *scene = CTX_data_scene(C);
+       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);
+       
+       VECCOPY(bone->head, vec0);
+       VECCOPY(bone->tail, vec1);
+       
+       if (!VecIsNull(up_axis))
+       {
+               float qroll[4];
+
+               if (scene->toolsettings->skgen_retarget_roll == SK_RETARGET_ROLL_VIEW)
+               {
+                       bone->roll = rollBoneByQuatAligned(bone, edge->up_axis, qrot, qroll, up_axis);
+               }
+               else if (scene->toolsettings->skgen_retarget_roll == SK_RETARGET_ROLL_JOINT)
+               {
+                       bone->roll = rollBoneByQuatJoint(edge, edge->next, qrot, qroll);
+               }
+               else
+               {
+                       QuatOne(qroll);
+               }
+               
+               QuatMul(qrot, qroll, qrot);
+       }
+       else
+       {
+               bone->roll = rollBoneByQuat(bone, edge->up_axis, qrot);
+       }
+
+       for (ctrl = rigg->controls.first; ctrl; ctrl = ctrl->next)
+       {
+               if (ctrl->link == bone)
+               {
+                       repositionControl(rigg, ctrl, vec0, vec1, qrot, resize);
+               }
+               if (ctrl->link_tail == bone)
+               {
+                       repositionTailControl(rigg, ctrl);
+               }
+       }
+}
+
+static RetargetMode detectArcRetargetMode(RigArc *arc);
+static void retargetArctoArcLength(bContext *C, 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 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 FLT_MAX /* FIX ME */
+
+static float costDistance(BArcIterator *iter, float *vec0, float *vec1, int i0, int i1, float distance_weight)
+{
+       EmbedBucket *bucket = NULL;
+       float max_dist = 0;
+       float v1[3], v2[3], c[3];
+       float v1_inpf;
+
+       if (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 = IT_peek(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 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], float angle_weight)
+{
+       if (angle_weight > 0)
+       {
+               float current_angle;
+               
+               if (!VecIsNull(vec_first) && !VecIsNull(vec_second))
+               {
+                       current_angle = saacos(Inpf(vec_first, vec_second));
+
+                       return angle_weight * fabs(current_angle - original_angle);
+               }
+               else
+               {
+                       return angle_weight * M_PI;
+               }
+       }
+       else
+       {
+               return 0;
+       }
+}
+
+static float costLength(float original_length, float current_length, float length_weight)
+{
+       if (current_length == 0)
+       {
+               return MAX_COST;
+       }
+       else
+       {
+               float length_ratio = fabs((current_length - original_length) / original_length);
+               return length_weight * length_ratio * length_ratio;
+       }
+}
+
+#if 0
+static float calcCostLengthDistance(BArcIterator *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);
+}
+#endif
+
+static float calcCostAngleLengthDistance(BArcIterator *iter, float **vec_cache, RigEdge *edge, float *vec0, float *vec1, float *vec2, int i1, int i2, float angle_weight, float length_weight, float distance_weight)
+{
+       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, angle_weight);
+       }
+
+       /* Length cost */
+       new_cost += costLength(edge->length, length2, length_weight);
+
+       /* Distance cost */
+       new_cost += costDistance(iter, vec1, vec2, i1, i2, distance_weight);
+
+       return new_cost;
+}
+
+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, BArcIterator *iter, float **vec_cache, int nb_joints, int nb_positions, int previous, int current, RigEdge *edge, int joints_left, float angle_weight, float length_weight, float distance_weight)
+{
+       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 *vec0 = vec_cache[previous];
+               float *vec1 = vec_cache[current];
+               float *vec2 = vec_cache[nb_positions + 1];
+
+               node->weight = calcCostAngleLengthDistance(iter, vec_cache, edge, vec0, vec1, vec2, current, iter->length, angle_weight, length_weight, distance_weight);
+
+               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, angle_weight, length_weight, distance_weight);
+                       
+                       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, angle_weight, length_weight, distance_weight);
+                       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(bContext *C, RigGraph *rigg, RigArc *iarc, RigNode *inode_start)
+{
+       ReebArcIterator arc_iter;
+       BArcIterator *iter = (BArcIterator*)&arc_iter;
+       RigEdge *edge;
+       EmbedBucket *bucket = NULL;
+       ReebNode *node_start, *node_end;
+       ReebArc *earc = iarc->link_mesh;
+       float angle_weight = 1.0; // GET FROM CONTEXT
+       float length_weight = 1.0;
+       float distance_weight = 1.0;
+       float min_cost = FLT_MAX;
+       float *vec0, *vec1;
+       int *best_positions;
+       int nb_edges = BLI_countlist(&iarc->edges);
+       int nb_joints = nb_edges - 1;
+       RetargetMethod method = METHOD_MEMOIZE;
+       int i;
+       
+       if (nb_joints > earc->bcount)
+       {
+               printf("NOT ENOUGH BUCKETS!\n");
+               return;
+       }
+
+       best_positions = MEM_callocN(sizeof(int) * nb_joints, "Best positions");
+       
+       if (testFlipArc(iarc, inode_start))
+       {
+               node_start = earc->tail;
+               node_end = earc->head;
+       }
+       else
+       {
+               node_start = earc->head;
+               node_end = earc->tail;
+       }
+
+       /* equal number of joints and potential position, just fill them in */
+       if (nb_joints == earc->bcount)
+       {
+               int i;
+               
+               /* init with first values */
+               for (i = 0; i < nb_joints; i++)
+               {
+                       best_positions[i] = i + 1;
+               }
+       }
+       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 = IT_peek(iter, i);
+                       positions_cache[i] = bucket->p;
+               }
+
+               result = solveJoints(table, iter, positions_cache, nb_joints, earc->bcount, 0, 0, iarc->edges.first, nb_joints, angle_weight, length_weight, distance_weight);
+               
+               min_cost = result->weight;
+               copyMemoPositions(best_positions, table, earc->bcount, nb_joints);
+               
+               MEM_freeN(table);
+               MEM_freeN(positions_cache);
+       }
+
+       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++)
+       {
+               float *no = NULL;
+               if (i < nb_joints)
+               {
+                       bucket = IT_peek(iter, best_positions[i]);
+                       vec1 = bucket->p;
+                       no = bucket->no;
+               }
+               else
+               {
+                       vec1 = node_end->p;
+                       no = node_end->no;
+               }
+               
+               if (edge->bone)
+               {
+                       repositionBone(C, rigg, edge, vec0, vec1, no);
+               }
+               
+               vec0 = vec1;
+       }
+
+       MEM_freeN(best_positions);
+}
+
+static void retargetArctoArcLength(bContext *C, RigGraph *rigg, RigArc *iarc, RigNode *inode_start)
+{
+       ReebArcIterator arc_iter;
+       BArcIterator *iter = (BArcIterator*)&arc_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 = IT_next(iter);
+       
+       vec0 = node_start->p;
+       
+       while (bucket != NULL)
+       {
+               vec1 = bucket->p;
+               
+               embedding_length += VecLenf(vec0, vec1);
+               
+               vec0 = vec1;
+               bucket = IT_next(iter);
+       }
+       
+       embedding_length += VecLenf(node_end->p, vec1);
+       
+       /* fit bones */
+       initArcIterator(iter, earc, node_start);
+
+       bucket = IT_next(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 *no = NULL;
+               float length = 0;
+
+               while (bucket && new_bone_length > length)
+               {
+                       length += VecLenf(previous_vec, vec1);
+                       bucket = IT_next(iter);
+                       previous_vec = vec1;
+                       vec1 = bucket->p;
+                       no = bucket->no;
+               }
+               
+               if (bucket == NULL)
+               {
+                       vec1 = node_end->p;
+                       no = node_end->no;
+               }
+
+               /* no need to move virtual edges (space between unconnected bones) */           
+               if (edge->bone)
+               {
+                       repositionBone(C, rigg, edge, vec0, vec1, no);
+               }
+               
+               vec0 = vec1;
+               previous_vec = vec1;
+       }
+}
+
+static void retargetArctoArc(bContext *C, 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;
+       p->context = C;
+       
+       BLI_insert_work(rigg->worker, p);
+#else
+       RetargetParam p;
+
+       p.rigg = rigg;
+       p.iarc = iarc;
+       p.inode_start = inode_start;
+       p.context = C;
+       
+       exec_retargetArctoArc(&p);
+#endif
+}
+
+void *exec_retargetArctoArc(void *param)
+{
+       RetargetParam *p = (RetargetParam*)param;
+       RigGraph *rigg = p->rigg;
+       RigArc *iarc = p->iarc;
+       bContext *C = p->context;       
+       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(C, rigg, edge, earc->tail->p, earc->head->p, earc->head->no);
+               }
+               else
+               {
+                       repositionBone(C, rigg, edge, earc->head->p, earc->tail->p, earc->tail->no);
+               }
+       }
+       else
+       {
+               RetargetMode mode = detectArcRetargetMode(iarc);
+               
+               if (mode == RETARGET_AGGRESSIVE)
+               {
+                       retargetArctoArcAggresive(C, rigg, iarc, inode_start);
+               }
+               else
+               {               
+                       retargetArctoArcLength(C, 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(bContext *C, 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(C, 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(C, rigg, next_iarc, inode);
+                       }
+               }
+       }
+}
+
+static void finishRetarget(RigGraph *rigg)
+{
+#ifdef USE_THREADS
+       BLI_end_worker(rigg->worker);
+#endif
+}
+
+static void adjustGraphs(bContext *C, RigGraph *rigg)
+{
+       Scene *scene = CTX_data_scene(C);
+       bArmature *arm= rigg->ob->data;
+       RigArc *arc;
+       
+       for (arc = rigg->arcs.first; arc; arc = arc->next)
+       {
+               if (arc->link_mesh)
+               {
+                       retargetArctoArc(C, rigg, arc, arc->head);
+               }
+       }
+
+       finishRetarget(rigg);
+
+       /* Turn the list into an armature */
+       arm->edbo = rigg->editbones;
+       ED_armature_from_edit(scene, rigg->ob);
+       
+       ED_undo_push("Retarget Skeleton");
+}
+
+static void retargetGraphs(bContext *C, RigGraph *rigg)
+{
+       Scene *scene = CTX_data_scene(C);
+       bArmature *arm= rigg->ob->data;
+       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(C, rigg, NULL, inode);
+       
+       //generateMissingArcs(rigg);
+       
+       finishRetarget(rigg);
+
+       /* Turn the list into an armature */
+       arm->edbo = rigg->editbones;
+       ED_armature_from_edit(scene, rigg->ob);
+}
+
+char *RIG_nameBone(RigGraph *rg, int arc_index, int bone_index)
+{
+       RigArc *arc = BLI_findlink(&rg->arcs, arc_index);
+       RigEdge *iedge;
+
+       if (arc == NULL)
+       {
+               return "None";
+       }
+       
+       if (bone_index == BLI_countlist(&arc->edges))
+       {
+               return "Last joint";
+       }
+
+       iedge = BLI_findlink(&arc->edges, bone_index);
+       
+       if (iedge == NULL)
+       {
+               return "Done";
+       }
+       
+       if (iedge->bone == NULL)
+       {
+               return "Bone offset";
+       }
+       
+       return iedge->bone->name;
+}
+
+int RIG_nbJoints(RigGraph *rg)
+{
+       RigArc *arc;
+       int total = 0;
+       
+       total += BLI_countlist(&rg->nodes);
+       
+       for (arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               total += BLI_countlist(&arc->edges) - 1; /* -1 because end nodes are already counted */
+       }
+       
+       return total;
+}
+
+void BIF_retargetArmature(bContext *C)
+{
+       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(C);
+       
+       end_time = PIL_check_seconds_timer();
+       reeb_time = end_time - start_time;
+       
+       printf("Reeb Graph created\n");
+
+       CTX_DATA_BEGIN(C, Base*, base, selected_editable_bases) {
+               Object *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 = RIG_graphFromArmature(C, 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(C, 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 */
+               }
+       }
+       CTX_DATA_END;
+
+       
+       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");
+       
+       ED_undo_push("Retarget Skeleton");
+
+       // XXX  
+//     allqueue(REDRAWVIEW3D, 0);
+}
+
+void BIF_retargetArc(bContext *C, ReebArc *earc, RigGraph *template_rigg)
+{
+       Object *obedit = CTX_data_edit_object(C);
+       Scene *scene = CTX_data_scene(C);
+       bArmature *armedit = obedit->data;
+       Object *ob;
+       RigGraph *rigg;
+       RigArc *iarc;
+       bArmature *arm;
+       char *side_string = scene->toolsettings->skgen_side_string;
+       char *num_string = scene->toolsettings->skgen_num_string;
+       int free_template = 0;
+       
+       if (template_rigg)
+       {
+               ob = template_rigg->ob;         
+               arm = ob->data;
+       }
+       else
+       {
+               free_template = 1;
+               ob = obedit;    
+               arm = ob->data;
+               template_rigg = armatureSelectedToGraph(C, ob, arm);
+       }
+       
+       if (template_rigg->arcs.first == NULL)
+       {
+//             XXX
+//             error("No Template and no deforming bones selected");
+               return;
+       }
+       
+       rigg = cloneRigGraph(template_rigg, armedit->edbo, obedit, side_string, num_string);
+       
+       iarc = rigg->arcs.first;
+       
+       iarc->link_mesh = earc;
+       iarc->head->link_mesh = earc->head;
+       iarc->tail->link_mesh = earc->tail;
+       
+       retargetArctoArc(C, rigg, iarc, iarc->head);
+       
+       finishRetarget(rigg);
+       
+       /* free template if it comes from the edit armature */
+       if (free_template)
+       {
+               RIG_freeRigGraph((BGraph*)template_rigg);
+       }
+       RIG_freeRigGraph((BGraph*)rigg);
+       
+//     XXX
+//     allqueue(REDRAWVIEW3D, 0);
+}
+
+void BIF_adjustRetarget(bContext *C)
+{
+       if (GLOBAL_RIGG)
+       {
+               adjustGraphs(C, GLOBAL_RIGG);
+       }
+}
+
+void BIF_freeRetarget()
+{
+       if (GLOBAL_RIGG)
+       {
+               RIG_freeRigGraph((BGraph*)GLOBAL_RIGG);
+               GLOBAL_RIGG = NULL;
+       }
+}
diff --git a/source/blender/editors/armature/editarmature_sketch.c b/source/blender/editors/armature/editarmature_sketch.c
new file mode 100644 (file)
index 0000000..4ac599a
--- /dev/null
@@ -0,0 +1,3141 @@
+/**
+ * $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.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#include <string.h>
+#include <math.h>
+#include <float.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_listBase.h"
+#include "DNA_scene_types.h"
+#include "DNA_screen_types.h"
+#include "DNA_view3d_types.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_object_types.h"
+#include "DNA_armature_types.h"
+#include "DNA_userdef_types.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_arithb.h"
+#include "BLI_graph.h"
+#include "BLI_ghash.h"
+
+#include "BKE_utildefines.h"
+#include "BKE_global.h"
+#include "BKE_DerivedMesh.h"
+#include "BKE_object.h"
+#include "BKE_anim.h"
+#include "BKE_context.h"
+
+#include "ED_view3d.h"
+
+#include "BIF_gl.h"
+#include "UI_resources.h"
+//#include "BIF_screen.h"
+//#include "BIF_space.h"
+//#include "BIF_mywindow.h"
+#include "ED_armature.h"
+#include "armature_intern.h"
+//#include "BIF_sketch.h"
+#include "BIF_retarget.h"
+#include "BIF_generate.h"
+//#include "BIF_interface.h"
+
+#include "BIF_transform.h"
+
+#include "WM_types.h"
+
+//#include "blendef.h"
+//#include "mydevice.h"
+#include "reeb.h"
+
+typedef enum SK_PType
+{
+       PT_CONTINUOUS,
+       PT_EXACT,
+} SK_PType;
+
+typedef enum SK_PMode
+{
+       PT_SNAP,
+       PT_PROJECT,
+} SK_PMode;
+
+typedef struct SK_Point
+{
+       float p[3];
+       float no[3];
+       SK_PType type;
+       SK_PMode mode;
+} SK_Point;
+
+typedef struct SK_Stroke
+{
+       struct SK_Stroke *next, *prev;
+
+       SK_Point *points;
+       int nb_points;
+       int buf_size;
+       int selected;
+} SK_Stroke;
+
+#define SK_OVERDRAW_LIMIT      5
+
+typedef struct SK_Overdraw
+{
+       SK_Stroke *target;
+       int     start, end;
+       int count;
+} SK_Overdraw;
+
+#define SK_Stroke_BUFFER_INIT_SIZE 20
+
+typedef struct SK_DrawData
+{
+       short mval[2];
+       short previous_mval[2];
+       SK_PType type;
+} SK_DrawData;
+
+typedef struct SK_Intersection
+{
+       struct SK_Intersection *next, *prev;
+       SK_Stroke *stroke;
+       int                     before;
+       int                     after;
+       int                     gesture_index;
+       float           p[3];
+       float           lambda; /* used for sorting intersection points */
+} SK_Intersection;
+
+typedef struct SK_Sketch
+{
+       ListBase        strokes;
+       SK_Stroke       *active_stroke;
+       SK_Stroke       *gesture;
+       SK_Point        next_point;
+       SK_Overdraw over;
+} SK_Sketch;
+
+typedef struct SK_StrokeIterator {
+       HeadFct         head;
+       TailFct         tail;
+       PeekFct         peek;
+       NextFct         next;
+       NextNFct        nextN;
+       PreviousFct     previous;
+       StoppedFct      stopped;
+       
+       float *p, *no;
+       
+       int length;
+       int index;
+       /*********************************/
+       SK_Stroke *stroke;
+       int start;
+       int end;
+       int stride;
+} SK_StrokeIterator;
+
+typedef struct SK_Gesture {
+       SK_Stroke       *stk;
+       SK_Stroke       *segments;
+
+       ListBase        intersections;
+       ListBase        self_intersections;
+
+       int                     nb_self_intersections;
+       int                     nb_intersections;
+       int                     nb_segments;
+} SK_Gesture;
+
+typedef int  (*GestureDetectFct)(bContext*, SK_Gesture*, SK_Sketch *);
+typedef void (*GestureApplyFct)(bContext*, SK_Gesture*, SK_Sketch *);
+
+typedef struct SK_GestureAction {
+       char name[64];
+       GestureDetectFct        detect;
+       GestureApplyFct         apply;
+} SK_GestureAction;
+
+SK_Sketch *GLOBAL_sketch = NULL;
+SK_Point boneSnap;
+int    LAST_SNAP_POINT_VALID = 0;
+float  LAST_SNAP_POINT[3];
+
+/******************** PROTOTYPES ******************************/
+
+void initStrokeIterator(BArcIterator *iter, SK_Stroke *stk, int start, int end);
+
+void sk_deleteSelectedStrokes(SK_Sketch *sketch);
+
+void sk_freeStroke(SK_Stroke *stk);
+void sk_freeSketch(SK_Sketch *sketch);
+
+SK_Point *sk_lastStrokePoint(SK_Stroke *stk);
+
+int sk_detectCutGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch);
+void sk_applyCutGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch);
+int sk_detectTrimGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch);
+void sk_applyTrimGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch);
+int sk_detectCommandGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch);
+void sk_applyCommandGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch);
+int sk_detectDeleteGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch);
+void sk_applyDeleteGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch);
+int sk_detectMergeGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch);
+void sk_applyMergeGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch);
+int sk_detectReverseGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch);
+void sk_applyReverseGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch);
+int sk_detectConvertGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch);
+void sk_applyConvertGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch);
+
+
+void sk_resetOverdraw(SK_Sketch *sketch);
+int sk_hasOverdraw(SK_Sketch *sketch, SK_Stroke *stk);
+
+/******************** GESTURE ACTIONS ******************************/
+
+SK_GestureAction GESTURE_ACTIONS[] =
+       {
+               {"Cut", sk_detectCutGesture, sk_applyCutGesture},
+               {"Trim", sk_detectTrimGesture, sk_applyTrimGesture},
+               {"Command", sk_detectCommandGesture, sk_applyCommandGesture},
+               {"Delete", sk_detectDeleteGesture, sk_applyDeleteGesture},
+               {"Merge", sk_detectMergeGesture, sk_applyMergeGesture},
+               {"Reverse", sk_detectReverseGesture, sk_applyReverseGesture},
+               {"Convert", sk_detectConvertGesture, sk_applyConvertGesture},
+               {"", NULL, NULL}
+       };
+
+/******************** TEMPLATES UTILS *************************/
+
+char  *TEMPLATES_MENU = NULL;
+int    TEMPLATES_CURRENT = 0;
+GHash *TEMPLATES_HASH = NULL;
+RigGraph *TEMPLATE_RIGG = NULL;
+
+void BIF_makeListTemplates(bContext *C)
+{
+       Object *obedit = CTX_data_edit_object(C);
+       Scene *scene = CTX_data_scene(C);
+       Base *base;
+       int index = 0;
+
+       if (TEMPLATES_HASH != NULL)
+       {
+               BLI_ghash_free(TEMPLATES_HASH, NULL, NULL);
+       }
+       
+       TEMPLATES_HASH = BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
+       TEMPLATES_CURRENT = 0;
+
+       for ( base = FIRSTBASE; base; base = base->next )
+       {
+               Object *ob = base->object;
+               
+               if (ob != obedit && ob->type == OB_ARMATURE)
+               {
+                       index++;
+                       BLI_ghash_insert(TEMPLATES_HASH, SET_INT_IN_POINTER(index), ob);
+                       
+                       if (ob == scene->toolsettings->skgen_template)
+                       {
+                               TEMPLATES_CURRENT = index;
+                       }
+               }
+       }
+}
+
+char *BIF_listTemplates(bContext *C)
+{
+       GHashIterator ghi;
+       char menu_header[] = "Template%t|None%x0|";
+       char *p;
+       
+       if (TEMPLATES_MENU != NULL)
+       {
+               MEM_freeN(TEMPLATES_MENU);
+       }
+       
+       TEMPLATES_MENU = MEM_callocN(sizeof(char) * (BLI_ghash_size(TEMPLATES_HASH) * 32 + 30), "skeleton template menu");
+       
+       p = TEMPLATES_MENU;
+       
+       p += sprintf(TEMPLATES_MENU, "%s", menu_header);
+       
+       BLI_ghashIterator_init(&ghi, TEMPLATES_HASH);
+       
+       while (!BLI_ghashIterator_isDone(&ghi))
+       {
+               Object *ob = BLI_ghashIterator_getValue(&ghi);
+               int key = (int)BLI_ghashIterator_getKey(&ghi);
+               
+               p += sprintf(p, "|%s%%x%i", ob->id.name+2, key);
+               
+               BLI_ghashIterator_step(&ghi);
+       }
+       
+       return TEMPLATES_MENU;
+}
+
+int   BIF_currentTemplate(bContext *C)
+{
+       Scene *scene = CTX_data_scene(C);
+       if (TEMPLATES_CURRENT == 0 && scene->toolsettings->skgen_template != NULL)
+       {
+               GHashIterator ghi;
+               BLI_ghashIterator_init(&ghi, TEMPLATES_HASH);
+               
+               while (!BLI_ghashIterator_isDone(&ghi))
+               {
+                       Object *ob = BLI_ghashIterator_getValue(&ghi);
+                       int key = (int)BLI_ghashIterator_getKey(&ghi);
+                       
+                       if (ob == scene->toolsettings->skgen_template)
+                       {
+                               TEMPLATES_CURRENT = key;
+                               break;
+                       }
+                       
+                       BLI_ghashIterator_step(&ghi);
+               }
+       }
+       
+       return TEMPLATES_CURRENT;
+}
+
+RigGraph* sk_makeTemplateGraph(bContext *C, Object *ob)
+{
+       Object *obedit = CTX_data_edit_object(C);
+       if (ob == obedit)
+       {
+               return NULL;
+       }
+       
+       if (ob != NULL)
+       {
+               if (TEMPLATE_RIGG && TEMPLATE_RIGG->ob != ob)
+               {
+                       RIG_freeRigGraph((BGraph*)TEMPLATE_RIGG);
+                       TEMPLATE_RIGG = NULL;
+               }
+               
+               if (TEMPLATE_RIGG == NULL)
+               {
+                       bArmature *arm;
+
+                       arm = ob->data;
+                       
+                       TEMPLATE_RIGG = RIG_graphFromArmature(C, ob, arm);
+               }
+       }
+       
+       return TEMPLATE_RIGG;
+}
+
+int BIF_nbJointsTemplate(bContext *C)
+{
+       Scene *scene = CTX_data_scene(C);
+       RigGraph *rg = sk_makeTemplateGraph(C, scene->toolsettings->skgen_template);
+       
+       if (rg)
+       {
+               return RIG_nbJoints(rg);
+       }
+       else
+       {
+               return -1; 
+       }
+}
+
+char * BIF_nameBoneTemplate(bContext *C)
+{
+       Scene *scene = CTX_data_scene(C);
+       SK_Sketch *stk = GLOBAL_sketch;
+       RigGraph *rg;
+       int index = 0;
+
+       if (stk && stk->active_stroke != NULL)
+       {
+               index = stk->active_stroke->nb_points;
+       }
+       
+       rg = sk_makeTemplateGraph(C, scene->toolsettings->skgen_template);
+       
+       if (rg == NULL)
+       {
+               return "";
+       }
+
+       return RIG_nameBone(rg, 0, index);
+}
+
+void  BIF_freeTemplates(bContext *C)
+{
+       if (TEMPLATES_MENU != NULL)
+       {
+               MEM_freeN(TEMPLATES_MENU);
+               TEMPLATES_MENU = NULL;
+       }
+       
+       if (TEMPLATES_HASH != NULL)
+       {
+               BLI_ghash_free(TEMPLATES_HASH, NULL, NULL);
+               TEMPLATES_HASH = NULL;
+       }
+       
+       if (TEMPLATE_RIGG != NULL)
+       {
+               RIG_freeRigGraph((BGraph*)TEMPLATE_RIGG);
+               TEMPLATE_RIGG = NULL;
+       }
+}
+
+void  BIF_setTemplate(bContext *C, int index)
+{
+       Scene *scene = CTX_data_scene(C);
+       if (index > 0)
+       {
+               scene->toolsettings->skgen_template = BLI_ghash_lookup(TEMPLATES_HASH, SET_INT_IN_POINTER(index));
+       }
+       else
+       {
+               scene->toolsettings->skgen_template = NULL;
+               
+               if (TEMPLATE_RIGG != NULL)
+               {
+                       RIG_freeRigGraph((BGraph*)TEMPLATE_RIGG);
+               }
+               TEMPLATE_RIGG = NULL;
+       }
+}      
+
+/*********************** CONVERSION ***************************/
+
+void sk_autoname(bContext *C, ReebArc *arc)
+{
+       Scene *scene = CTX_data_scene(C);
+       if (scene->toolsettings->skgen_retarget_options & SK_RETARGET_AUTONAME)
+       {
+               if (arc == NULL)
+               {
+                       char *num = scene->toolsettings->skgen_num_string;
+                       int i = atoi(num);
+                       i++;
+                       BLI_snprintf(num, 8, "%i", i);
+               }
+               else
+               {
+                       char *side = scene->toolsettings->skgen_side_string;
+                       int valid = 0;
+                       int caps = 0;
+                       
+                       if (BLI_streq(side, ""))
+                       {
+                               valid = 1;
+                       }
+                       else if (BLI_streq(side, "R") || BLI_streq(side, "L"))
+                       {
+                               valid = 1;
+                               caps = 1;
+                       }
+                       else if (BLI_streq(side, "r") || BLI_streq(side, "l"))
+                       {
+                               valid = 1;
+                               caps = 0;
+                       }
+                       
+                       if (valid)
+                       {
+                               if (arc->head->p[0] < 0)
+                               {
+                                       BLI_snprintf(side, 8, caps?"R":"r");
+                               }
+                               else
+                               {
+                                       BLI_snprintf(side, 8, caps?"L":"l");
+                               }
+                       }
+               }
+       }
+}
+
+ReebNode *sk_pointToNode(SK_Point *pt, float imat[][4], float tmat[][3])
+{
+       ReebNode *node;
+       
+       node = MEM_callocN(sizeof(ReebNode), "reeb node");
+       VECCOPY(node->p, pt->p);
+       Mat4MulVecfl(imat, node->p);
+       
+       VECCOPY(node->no, pt->no);
+       Mat3MulVecfl(tmat, node->no);
+       
+       return node;
+}
+
+ReebArc *sk_strokeToArc(SK_Stroke *stk, float imat[][4], float tmat[][3])
+{
+       ReebArc *arc;
+       int i;
+       
+       arc = MEM_callocN(sizeof(ReebArc), "reeb arc");
+       arc->head = sk_pointToNode(stk->points, imat, tmat);
+       arc->tail = sk_pointToNode(sk_lastStrokePoint(stk), imat, tmat);
+       
+       arc->bcount = stk->nb_points - 2; /* first and last are nodes, don't count */
+       arc->buckets = MEM_callocN(sizeof(EmbedBucket) * arc->bcount, "Buckets");
+       
+       for (i = 0; i < arc->bcount; i++)
+       {
+               VECCOPY(arc->buckets[i].p, stk->points[i + 1].p);
+               Mat4MulVecfl(imat, arc->buckets[i].p);
+
+               VECCOPY(arc->buckets[i].no, stk->points[i + 1].no);
+               Mat3MulVecfl(tmat, arc->buckets[i].no);
+       }
+       
+       return arc;
+}
+
+void sk_retargetStroke(bContext *C, SK_Stroke *stk)
+{
+       Scene *scene = CTX_data_scene(C);
+       Object *obedit = CTX_data_edit_object(C);
+       float imat[4][4];
+       float tmat[3][3];
+       ReebArc *arc;
+       RigGraph *rg;
+       
+       Mat4Invert(imat, obedit->obmat);
+       
+       Mat3CpyMat4(tmat, obedit->obmat);
+       Mat3Transp(tmat);
+
+       arc = sk_strokeToArc(stk, imat, tmat);
+       
+       sk_autoname(C, arc);
+       
+       rg = sk_makeTemplateGraph(C, scene->toolsettings->skgen_template);
+
+       BIF_retargetArc(C, arc, rg);
+       
+       sk_autoname(C, NULL);
+       
+       MEM_freeN(arc->head);
+       MEM_freeN(arc->tail);
+       REEB_freeArc((BArc*)arc);
+}
+
+/**************************************************************/
+
+void sk_freeSketch(SK_Sketch *sketch)
+{
+       SK_Stroke *stk, *next;
+       
+       for (stk = sketch->strokes.first; stk; stk = next)
+       {
+               next = stk->next;
+               
+               sk_freeStroke(stk);
+       }
+       
+       MEM_freeN(sketch);
+}
+
+SK_Sketch* sk_createSketch()
+{
+       SK_Sketch *sketch;
+       
+       sketch = MEM_callocN(sizeof(SK_Sketch), "SK_Sketch");
+       
+       sketch->active_stroke = NULL;
+       sketch->gesture = NULL;
+
+       sketch->strokes.first = NULL;
+       sketch->strokes.last = NULL;
+       
+       return sketch;
+}
+
+void sk_initPoint(bContext *C, SK_Point *pt)
+{
+       ARegion *ar = CTX_wm_region(C);
+       RegionView3D *rv3d = ar->regiondata;
+
+       VECCOPY(pt->no, rv3d->viewinv[2]);
+       Normalize(pt->no);
+       /* more init code here */
+}
+
+void sk_copyPoint(SK_Point *dst, SK_Point *src)
+{
+       memcpy(dst, src, sizeof(SK_Point));
+}
+
+void sk_allocStrokeBuffer(SK_Stroke *stk)
+{
+       stk->points = MEM_callocN(sizeof(SK_Point) * stk->buf_size, "SK_Point buffer");
+}
+
+void sk_freeStroke(SK_Stroke *stk)
+{
+       MEM_freeN(stk->points);
+       MEM_freeN(stk);
+}
+
+SK_Stroke* sk_createStroke()
+{
+       SK_Stroke *stk;
+       
+       stk = MEM_callocN(sizeof(SK_Stroke), "SK_Stroke");
+       
+       stk->selected = 0;
+       stk->nb_points = 0;
+       stk->buf_size = SK_Stroke_BUFFER_INIT_SIZE;
+       
+       sk_allocStrokeBuffer(stk);
+       
+       return stk;
+}
+
+void sk_shrinkStrokeBuffer(SK_Stroke *stk)
+{
+       if (stk->nb_points < stk->buf_size)
+       {
+               SK_Point *old_points = stk->points;
+               
+               stk->buf_size = stk->nb_points;
+
+               sk_allocStrokeBuffer(stk);              
+               
+               memcpy(stk->points, old_points, sizeof(SK_Point) * stk->nb_points);
+               
+               MEM_freeN(old_points);
+       }
+}
+
+void sk_growStrokeBuffer(SK_Stroke *stk)
+{
+       if (stk->nb_points == stk->buf_size)
+       {
+               SK_Point *old_points = stk->points;
+               
+               stk->buf_size *= 2;
+               
+               sk_allocStrokeBuffer(stk);
+               
+               memcpy(stk->points, old_points, sizeof(SK_Point) * stk->nb_points);
+               
+               MEM_freeN(old_points);
+       }
+}
+
+void sk_growStrokeBufferN(SK_Stroke *stk, int n)
+{
+       if (stk->nb_points + n > stk->buf_size)
+       {
+               SK_Point *old_points = stk->points;
+               
+               while (stk->nb_points + n > stk->buf_size)
+               {
+                       stk->buf_size *= 2;
+               }
+               
+               sk_allocStrokeBuffer(stk);
+               
+               memcpy(stk->points, old_points, sizeof(SK_Point) * stk->nb_points);
+               
+               MEM_freeN(old_points);
+       }
+}
+
+
+void sk_replaceStrokePoint(SK_Stroke *stk, SK_Point *pt, int n)
+{
+       memcpy(stk->points + n, pt, sizeof(SK_Point));
+}
+
+void sk_insertStrokePoint(SK_Stroke *stk, SK_Point *pt, int n)
+{
+       int size = stk->nb_points - n;
+       
+       sk_growStrokeBuffer(stk);
+       
+       memmove(stk->points + n + 1, stk->points + n, size * sizeof(SK_Point));
+       
+       memcpy(stk->points + n, pt, sizeof(SK_Point));
+       
+       stk->nb_points++;
+}
+
+void sk_appendStrokePoint(SK_Stroke *stk, SK_Point *pt)
+{
+       sk_growStrokeBuffer(stk);
+       
+       memcpy(stk->points + stk->nb_points, pt, sizeof(SK_Point));
+       
+       stk->nb_points++;
+}
+
+void sk_insertStrokePoints(SK_Stroke *stk, SK_Point *pts, int len, int start, int end)
+{
+       int size = end - start + 1;
+       
+       sk_growStrokeBufferN(stk, len - size);
+       
+       if (len != size)
+       {
+               int tail_size = stk->nb_points - end + 1;
+               
+               memmove(stk->points + start + len, stk->points + end + 1, tail_size * sizeof(SK_Point));
+       }
+       
+       memcpy(stk->points + start, pts, len * sizeof(SK_Point));
+       
+       stk->nb_points += len - size;
+}
+
+void sk_trimStroke(SK_Stroke *stk, int start, int end)
+{
+       int size = end - start + 1;
+       
+       if (start > 0)
+       {
+               memmove(stk->points, stk->points + start, size * sizeof(SK_Point));
+       }
+       
+       stk->nb_points = size;
+}
+
+void sk_straightenStroke(SK_Stroke *stk, int start, int end, float p_start[3], float p_end[3])
+{
+       SK_Point pt1, pt2;
+       SK_Point *prev, *next;
+       float delta_p[3];
+       int i, total;
+       
+       total = end - start;
+
+       VecSubf(delta_p, p_end, p_start);
+       
+       prev = stk->points + start;
+       next = stk->points + end;
+       
+       VECCOPY(pt1.p, p_start);
+       VECCOPY(pt1.no, prev->no);
+       pt1.mode = prev->mode;
+       pt1.type = prev->type;
+       
+       VECCOPY(pt2.p, p_end);
+       VECCOPY(pt2.no, next->no);
+       pt2.mode = next->mode;
+       pt2.type = next->type;
+       
+       sk_insertStrokePoint(stk, &pt1, start + 1); /* insert after start */
+       sk_insertStrokePoint(stk, &pt2, end + 1); /* insert before end (since end was pushed back already) */
+       
+       for (i = 1; i < total; i++)
+       {
+               float delta = (float)i / (float)total;
+               float *p = stk->points[start + 1 + i].p;
+
+               VECCOPY(p, delta_p);
+               VecMulf(p, delta);
+               VecAddf(p, p, p_start);
+       } 
+}
+
+void sk_polygonizeStroke(SK_Stroke *stk, int start, int end)
+{
+       int offset;
+       int i;
+       
+       /* find first exact points outside of range */
+       for (;start > 0; start--)
+       {
+               if (stk->points[start].type == PT_EXACT)
+               {
+                       break;
+               }
+       }
+       
+       for (;end < stk->nb_points - 1; end++)
+       {
+               if (stk->points[end].type == PT_EXACT)
+               {
+                       break;
+               }
+       }
+       
+       offset = start + 1;
+       
+       for (i = start + 1; i < end; i++)
+       {
+               if (stk->points[i].type == PT_EXACT)
+               {
+                       if (offset != i)
+                       {
+                               memcpy(stk->points + offset, stk->points + i, sizeof(SK_Point));
+                       }
+
+                       offset++;
+               }
+       }
+       
+       /* some points were removes, move end of array */
+       if (offset < end)
+       {
+               int size = stk->nb_points - end;
+               memmove(stk->points + offset, stk->points + end, size * sizeof(SK_Point));
+               stk->nb_points = offset + size;
+       }
+}
+
+void sk_flattenStroke(SK_Stroke *stk, int start, int end)
+{
+       float normal[3], distance[3];
+       float limit;
+       int i, total;
+       
+       total = end - start + 1;
+       
+       VECCOPY(normal, stk->points[start].no);
+       
+       VecSubf(distance, stk->points[end].p, stk->points[start].p);
+       Projf(normal, distance, normal);
+       limit = Normalize(normal);
+       
+       for (i = 1; i < total - 1; i++)
+       {
+               float d = limit * i / total;
+               float offset[3];
+               float *p = stk->points[start + i].p;
+
+               VecSubf(distance, p, stk->points[start].p);
+               Projf(distance, distance, normal);
+               
+               VECCOPY(offset, normal);
+               VecMulf(offset, d);
+               
+               VecSubf(p, p, distance);
+               VecAddf(p, p, offset);
+       } 
+}
+
+void sk_removeStroke(SK_Sketch *sketch, SK_Stroke *stk)
+{
+       if (sketch->active_stroke == stk)
+       {
+               sketch->active_stroke = NULL;
+       }
+       
+       BLI_remlink(&sketch->strokes, stk);
+       sk_freeStroke(stk);
+}
+
+void sk_reverseStroke(SK_Stroke *stk)
+{
+       SK_Point *old_points = stk->points;
+       int i = 0;
+       
+       sk_allocStrokeBuffer(stk);
+       
+       for (i = 0; i < stk->nb_points; i++)
+       {
+               sk_copyPoint(stk->points + i, old_points + stk->nb_points - 1 - i);
+       }
+       
+       MEM_freeN(old_points);
+}
+
+
+void sk_cancelStroke(SK_Sketch *sketch)
+{
+       if (sketch->active_stroke != NULL)
+       {
+               sk_resetOverdraw(sketch);
+               sk_removeStroke(sketch, sketch->active_stroke);
+       }
+}
+
+/* Apply reverse Chaikin filter to simplify the polyline
+ * */
+void sk_filterStroke(SK_Stroke *stk, int start, int end)
+{
+       SK_Point *old_points = stk->points;
+       int nb_points = stk->nb_points;
+       int i, j;
+       
+       return;
+       
+       if (start == -1)
+       {
+               start = 0;
+               end = stk->nb_points - 1;
+       }
+
+       sk_allocStrokeBuffer(stk);
+       stk->nb_points = 0;
+       
+       /* adding points before range */
+       for (i = 0; i < start; i++)
+       {
+               sk_appendStrokePoint(stk, old_points + i);
+       }
+       
+       for (i = start, j = start; i <= end; i++)
+       {
+               if (i - j == 3)
+               {
+                       SK_Point pt;
+                       float vec[3];
+                       
+                       sk_copyPoint(&pt, &old_points[j+1]);
+
+                       pt.p[0] = 0;
+                       pt.p[1] = 0;
+                       pt.p[2] = 0;
+                       
+                       VECCOPY(vec, old_points[j].p);
+                       VecMulf(vec, -0.25);
+                       VecAddf(pt.p, pt.p, vec);
+                       
+                       VECCOPY(vec, old_points[j+1].p);
+                       VecMulf(vec,  0.75);
+                       VecAddf(pt.p, pt.p, vec);
+
+                       VECCOPY(vec, old_points[j+2].p);
+                       VecMulf(vec,  0.75);
+                       VecAddf(pt.p, pt.p, vec);
+
+                       VECCOPY(vec, old_points[j+3].p);
+                       VecMulf(vec, -0.25);
+                       VecAddf(pt.p, pt.p, vec);
+                       
+                       sk_appendStrokePoint(stk, &pt);
+
+                       j += 2;
+               }
+               
+               /* this might be uneeded when filtering last continuous stroke */
+               if (old_points[i].type == PT_EXACT)
+               {
+                       sk_appendStrokePoint(stk, old_points + i);
+                       j = i;
+               }
+       } 
+       
+       /* adding points after range */
+       for (i = end + 1; i < nb_points; i++)
+       {
+               sk_appendStrokePoint(stk, old_points + i);
+       }
+
+       MEM_freeN(old_points);
+
+       sk_shrinkStrokeBuffer(stk);
+}
+
+void sk_filterLastContinuousStroke(SK_Stroke *stk)
+{
+       int start, end;
+       
+       end = stk->nb_points -1;
+       
+       for (start = end - 1; start > 0 && stk->points[start].type == PT_CONTINUOUS; start--)
+       {
+               /* nothing to do here*/
+       }
+       
+       if (end - start > 1)
+       {
+               sk_filterStroke(stk, start, end);
+       }
+}
+
+SK_Point *sk_lastStrokePoint(SK_Stroke *stk)
+{
+       SK_Point *pt = NULL;
+       
+       if (stk->nb_points > 0)
+       {
+               pt = stk->points + (stk->nb_points - 1);
+       }
+       
+       return pt;
+}
+
+void sk_drawStroke(SK_Stroke *stk, int id, float color[3], int start, int end)
+{
+       float rgb[3];
+       int i;
+       
+       if (id != -1)
+       {
+               glLoadName(id);
+               
+               glBegin(GL_LINE_STRIP);
+               
+               for (i = 0; i < stk->nb_points; i++)
+               {
+                       glVertex3fv(stk->points[i].p);
+               }
+               
+               glEnd();
+               
+       }
+       else
+       {
+               float d_rgb[3] = {1, 1, 1};
+               
+               VECCOPY(rgb, color);
+               VecSubf(d_rgb, d_rgb, rgb);
+               VecMulf(d_rgb, 1.0f / (float)stk->nb_points);
+               
+               glBegin(GL_LINE_STRIP);
+
+               for (i = 0; i < stk->nb_points; i++)
+               {
+                       if (i >= start && i <= end)
+                       {
+                               glColor3f(0.3, 0.3, 0.3);
+                       }
+                       else
+                       {
+                               glColor3fv(rgb);
+                       }
+                       glVertex3fv(stk->points[i].p);
+                       VecAddf(rgb, rgb, d_rgb);
+               }
+               
+               glEnd();
+       
+               glColor3f(0, 0, 0);
+               glBegin(GL_POINTS);
+       
+               for (i = 0; i < stk->nb_points; i++)
+               {
+                       if (stk->points[i].type == PT_EXACT)
+                       {
+                               glVertex3fv(stk->points[i].p);
+                       }
+               }
+               
+               glEnd();
+       }
+
+//     glColor3f(1, 1, 1);
+//     glBegin(GL_POINTS);
+//
+//     for (i = 0; i < stk->nb_points; i++)
+//     {
+//             if (stk->points[i].type == PT_CONTINUOUS)
+//             {
+//                     glVertex3fv(stk->points[i].p);
+//             }
+//     }
+//
+//     glEnd();
+}
+
+void drawSubdividedStrokeBy(bContext *C, BArcIterator *iter, NextSubdivisionFunc next_subdividion)
+{
+       float head[3], tail[3];
+       int bone_start = 0;
+       int end = iter->length;
+       int index;
+
+       iter->head(iter);
+       VECCOPY(head, iter->p);
+       
+       glColor3f(0, 1, 0);
+       glPointSize(UI_GetThemeValuef(TH_VERTEX_SIZE) * 2);
+       glBegin(GL_POINTS);
+       
+       index = next_subdividion(C, iter, bone_start, end, head, tail);
+       while (index != -1)
+       {
+               glVertex3fv(tail);
+               
+               VECCOPY(head, tail);
+               bone_start = index; // start next bone from current index
+
+               index = next_subdividion(C, iter, bone_start, end, head, tail);
+       }
+       
+       glEnd();
+       glPointSize(UI_GetThemeValuef(TH_VERTEX_SIZE));
+}
+
+void sk_drawStrokeSubdivision(bContext *C, SK_Stroke *stk)
+{
+       Scene *scene = CTX_data_scene(C);
+       int head_index = -1;
+       int i;
+       
+       if (scene->toolsettings->bone_sketching_convert == SK_CONVERT_RETARGET)
+       {
+               return;
+       }
+
+       
+       for (i = 0; i < stk->nb_points; i++)
+       {
+               SK_Point *pt = stk->points + i;
+               
+               if (pt->type == PT_EXACT || i == stk->nb_points - 1) /* stop on exact or on last point */
+               {
+                       if (head_index == -1)
+                       {
+                               head_index = i;
+                       }
+                       else
+                       {
+                               if (i - head_index > 1)
+                               {
+                                       SK_StrokeIterator sk_iter;
+                                       BArcIterator *iter = (BArcIterator*)&sk_iter;
+                                       
+                                       initStrokeIterator(iter, stk, head_index, i);
+
+                                       if (scene->toolsettings->bone_sketching_convert == SK_CONVERT_CUT_ADAPTATIVE)
+                                       {
+                                               drawSubdividedStrokeBy(C, iter, nextAdaptativeSubdivision);
+                                       }
+                                       else if (scene->toolsettings->bone_sketching_convert == SK_CONVERT_CUT_LENGTH)
+                                       {
+                                               drawSubdividedStrokeBy(C, iter, nextLengthSubdivision);
+                                       }
+                                       else if (scene->toolsettings->bone_sketching_convert == SK_CONVERT_CUT_FIXED)
+                                       {
+                                               drawSubdividedStrokeBy(C, iter, nextFixedSubdivision);
+                                       }
+                                       
+                               }
+
+                               head_index = i;
+                       }
+               }
+       }       
+}
+
+SK_Point *sk_snapPointStroke(bContext *C, SK_Stroke *stk, short mval[2], int *dist, int *index, int all_pts)
+{
+       ARegion *ar = CTX_wm_region(C);
+       SK_Point *pt = NULL;
+       int i;
+       
+       for (i = 0; i < stk->nb_points; i++)
+       {
+               if (all_pts || stk->points[i].type == PT_EXACT)
+               {
+                       short pval[2];
+                       int pdist;
+                       
+                       project_short_noclip(ar, stk->points[i].p, pval);
+                       
+                       pdist = ABS(pval[0] - mval[0]) + ABS(pval[1] - mval[1]);
+                       
+                       if (pdist < *dist)
+                       {
+                               *dist = pdist;
+                               pt = stk->points + i;
+                               
+                               if (index != NULL)
+                               {
+                                       *index = i;
+                               }
+                       }
+               }
+       }
+       
+       return pt;
+}
+
+SK_Point *sk_snapPointArmature(bContext *C, Object *ob, ListBase *ebones, short mval[2], int *dist)
+{
+       ARegion *ar = CTX_wm_region(C);
+       SK_Point *pt = NULL;
+       EditBone *bone;
+       
+       for (bone = ebones->first; bone; bone = bone->next)
+       {
+               float vec[3];
+               short pval[2];
+               int pdist;
+               
+               if ((bone->flag & BONE_CONNECTED) == 0)
+               {
+                       VECCOPY(vec, bone->head);
+                       Mat4MulVecfl(ob->obmat, vec);
+                       project_short_noclip(ar, vec, pval);
+                       
+                       pdist = ABS(pval[0] - mval[0]) + ABS(pval[1] - mval[1]);
+                       
+                       if (pdist < *dist)
+                       {
+                               *dist = pdist;
+                               pt = &boneSnap;
+                               VECCOPY(pt->p, vec);
+                               pt->type = PT_EXACT;
+                       }
+               }
+               
+               
+               VECCOPY(vec, bone->tail);
+               Mat4MulVecfl(ob->obmat, vec);
+               project_short_noclip(ar, vec, pval);
+               
+               pdist = ABS(pval[0] - mval[0]) + ABS(pval[1] - mval[1]);
+               
+               if (pdist < *dist)
+               {
+                       *dist = pdist;
+                       pt = &boneSnap;
+                       VECCOPY(pt->p, vec);
+                       pt->type = PT_EXACT;
+               }
+       }
+       
+       return pt;
+}
+
+void sk_resetOverdraw(SK_Sketch *sketch)
+{
+       sketch->over.target = NULL;
+       sketch->over.start = -1;
+       sketch->over.end = -1;
+       sketch->over.count = 0;
+}
+
+int sk_hasOverdraw(SK_Sketch *sketch, SK_Stroke *stk)
+{
+       return  sketch->over.target &&
+                       sketch->over.count >= SK_OVERDRAW_LIMIT &&
+                       (sketch->over.target == stk || stk == NULL) &&
+                       (sketch->over.start != -1 || sketch->over.end != -1);
+}
+
+void sk_updateOverdraw(bContext *C, SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData *dd)
+{
+       if (sketch->over.target == NULL)
+       {
+               SK_Stroke *target;
+               int closest_index = -1;
+               int dist = SNAP_MIN_DISTANCE * 2;
+               
+               /* If snapping, don't start overdraw */
+               if (sk_lastStrokePoint(stk)->mode == PT_SNAP)
+               {
+                       return;
+               }
+               
+               for (target = sketch->strokes.first; target; target = target->next)
+               {
+                       if (target != stk)
+                       {
+                               int index;
+                               
+                               SK_Point *spt = sk_snapPointStroke(C, target, dd->mval, &dist, &index, 1);
+                               
+                               if (spt != NULL)
+                               {
+                                       sketch->over.target = target;
+                                       closest_index = index;
+                               }
+                       }
+               }
+               
+               if (sketch->over.target != NULL)
+               {
+                       if (closest_index > -1)
+                       {
+                               if (sk_lastStrokePoint(stk)->type == PT_EXACT)
+                               {
+                                       sketch->over.count = SK_OVERDRAW_LIMIT;
+                               }
+                               else
+                               {
+                                       sketch->over.count++;
+                               }
+                       }
+
+                       if (stk->nb_points == 1)
+                       {
+                               sketch->over.start = closest_index;
+                       }
+                       else
+                       {
+                               sketch->over.end = closest_index;
+                       }
+               }
+       }
+       else if (sketch->over.target != NULL)
+       {
+               SK_Point *closest_pt = NULL;
+               int dist = SNAP_MIN_DISTANCE * 2;
+               int index;
+
+               closest_pt = sk_snapPointStroke(C, sketch->over.target, dd->mval, &dist, &index, 1);
+               
+               if (closest_pt != NULL)
+               {
+                       if (sk_lastStrokePoint(stk)->type == PT_EXACT)
+                       {
+                               sketch->over.count = SK_OVERDRAW_LIMIT;
+                       }
+                       else
+                       {
+                               sketch->over.count++;
+                       }
+                       
+                       sketch->over.end = index;
+               }
+               else
+               {
+                       sketch->over.end = -1;
+               }
+       }
+}
+
+/* return 1 on reverse needed */
+int sk_adjustIndexes(SK_Sketch *sketch, int *start, int *end)
+{
+       int retval = 0;
+
+       *start = sketch->over.start;
+       *end = sketch->over.end;
+       
+       if (*start == -1)
+       {
+               *start = 0;
+       }
+       
+       if (*end == -1)
+       {
+               *end = sketch->over.target->nb_points - 1;
+       }
+       
+       if (*end < *start)
+       {
+               int tmp = *start;
+               *start = *end;
+               *end = tmp;
+               retval = 1;
+       }
+       
+       return retval;
+}
+
+void sk_endOverdraw(SK_Sketch *sketch)
+{
+       SK_Stroke *stk = sketch->active_stroke;
+       
+       if (sk_hasOverdraw(sketch, NULL))
+       {
+               int start;
+               int end;
+               
+               if (sk_adjustIndexes(sketch, &start, &end))
+               {
+                       sk_reverseStroke(stk);
+               }
+               
+               if (stk->nb_points > 1)
+               {
+                       stk->points->type = sketch->over.target->points[start].type;
+                       sk_lastStrokePoint(stk)->type = sketch->over.target->points[end].type;
+               }
+               
+               sk_insertStrokePoints(sketch->over.target, stk->points, stk->nb_points, start, end);
+               
+               sk_removeStroke(sketch, stk);
+               
+               sk_resetOverdraw(sketch);
+       }
+}
+
+
+void sk_startStroke(SK_Sketch *sketch)
+{
+       SK_Stroke *stk = sk_createStroke();
+       
+       BLI_addtail(&sketch->strokes, stk);
+       sketch->active_stroke = stk;
+
+       sk_resetOverdraw(sketch);       
+}
+
+void sk_endStroke(bContext *C, SK_Sketch *sketch)
+{
+       Scene *scene = CTX_data_scene(C);
+       sk_shrinkStrokeBuffer(sketch->active_stroke);
+
+       if (scene->toolsettings->bone_sketching & BONE_SKETCHING_ADJUST)
+       {
+               sk_endOverdraw(sketch);
+       }
+
+       sketch->active_stroke = NULL;
+}
+
+void sk_updateDrawData(SK_DrawData *dd)
+{
+       dd->type = PT_CONTINUOUS;
+       
+       dd->previous_mval[0] = dd->mval[0];
+       dd->previous_mval[1] = dd->mval[1];
+}
+
+float sk_distanceDepth(bContext *C, float p1[3], float p2[3])
+{
+       ARegion *ar = CTX_wm_region(C);
+       RegionView3D *rv3d = ar->regiondata;
+       float vec[3];
+       float distance;
+       
+       VecSubf(vec, p1, p2);
+       
+       Projf(vec, vec, rv3d->viewinv[2]);
+       
+       distance = VecLength(vec);
+       
+       if (Inpf(rv3d->viewinv[2], vec) > 0)
+       {
+               distance *= -1;
+       }
+       
+       return distance; 
+}
+
+void sk_interpolateDepth(bContext *C, SK_Stroke *stk, int start, int end, float length, float distance)
+{
+       ARegion *ar = CTX_wm_region(C);
+       ScrArea *sa = CTX_wm_area(C);
+       View3D *v3d = sa->spacedata.first;
+
+       float progress = 0;
+       int i;
+       
+       progress = VecLenf(stk->points[start].p, stk->points[start - 1].p);
+       
+       for (i = start; i <= end; i++)
+       {
+               float ray_start[3], ray_normal[3];
+               float delta = VecLenf(stk->points[i].p, stk->points[i + 1].p);
+               short pval[2];
+               
+               project_short_noclip(ar, stk->points[i].p, pval);
+               viewray(ar, v3d, pval, ray_start, ray_normal);
+               
+               VecMulf(ray_normal, distance * progress / length);
+               VecAddf(stk->points[i].p, stk->points[i].p, ray_normal);
+
+               progress += delta ;
+       }
+}
+
+void sk_projectDrawPoint(bContext *C, float vec[3], SK_Stroke *stk, SK_DrawData *dd)
+{
+       ARegion *ar = CTX_wm_region(C);
+       /* copied from grease pencil, need fixing */    
+       SK_Point *last = sk_lastStrokePoint(stk);
+       short cval[2];
+       float fp[3] = {0, 0, 0};
+       float dvec[3];
+       
+       if (last != NULL)
+       {
+               VECCOPY(fp, last->p);
+       }
+       
+       initgrabz(ar->regiondata, fp[0], fp[1], fp[2]);
+       
+       /* method taken from editview.c - mouse_cursor() */
+       project_short_noclip(ar, fp, cval);
+       window_to_3d(ar, dvec, cval[0] - dd->mval[0], cval[1] - dd->mval[1]);
+       VecSubf(vec, fp, dvec);
+}
+
+int sk_getStrokeDrawPoint(bContext *C, SK_Point *pt, SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData *dd)
+{
+       pt->type = dd->type;
+       pt->mode = PT_PROJECT;
+       sk_projectDrawPoint(C, pt->p, stk, dd);
+       
+       return 1;
+}
+
+int sk_addStrokeDrawPoint(bContext *C, SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData *dd)
+{
+       SK_Point pt;
+       
+       sk_initPoint(C, &pt);
+       
+       sk_getStrokeDrawPoint(C, &pt, sketch, stk, dd);
+
+       sk_appendStrokePoint(stk, &pt);
+       
+       return 1;
+}
+
+int sk_getStrokeSnapPoint(bContext *C, SK_Point *pt, SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData *dd)
+{
+       Scene *scene = CTX_data_scene(C);
+       int point_added = 0;
+
+       if (scene->snap_mode == SCE_SNAP_MODE_VOLUME)
+       {
+               ListBase depth_peels;
+               DepthPeel *p1, *p2;
+               float *last_p = NULL;
+               float dist = FLT_MAX;
+               float p[3];
+               
+               depth_peels.first = depth_peels.last = NULL;
+               
+               peelObjectsContext(C, &depth_peels, dd->mval);
+               
+               if (stk->nb_points > 0 && stk->points[stk->nb_points - 1].type == PT_CONTINUOUS)
+               {
+                       last_p = stk->points[stk->nb_points - 1].p;
+               }
+               else if (LAST_SNAP_POINT_VALID)
+               {
+                       last_p = LAST_SNAP_POINT;
+               }
+               
+               
+               for (p1 = depth_peels.first; p1; p1 = p1->next)
+               {
+                       if (p1->flag == 0)
+                       {
+                               float vec[3];
+                               float new_dist;
+                               
+                               p2 = NULL;
+                               p1->flag = 1;
+       
+                               /* if peeling objects, take the first and last from each object */                      
+                               if (scene->snap_flag & SCE_SNAP_PEEL_OBJECT)
+                               {
+                                       DepthPeel *peel;
+                                       for (peel = p1->next; peel; peel = peel->next)
+                                       {
+                                               if (peel->ob == p1->ob)
+                                               {
+                                                       peel->flag = 1;
+                                                       p2 = peel;
+                                               }
+                                       }
+                               }
+                               /* otherwise, pair first with second and so on */
+                               else
+                               {
+                                       for (p2 = p1->next; p2 && p2->ob != p1->ob; p2 = p2->next)
+                                       {
+                                               /* nothing to do here */
+                                       }
+                               }
+                               
+                               if (p2)
+                               {
+                                       p2->flag = 1;
+                                       
+                                       VecAddf(vec, p1->p, p2->p);
+                                       VecMulf(vec, 0.5f);
+                               }
+                               else
+                               {
+                                       VECCOPY(vec, p1->p);
+                               }
+                               
+                               if (last_p == NULL)
+                               {
+                                       VECCOPY(p, vec);
+                                       dist = 0;
+                                       break;
+                               }
+                               
+                               new_dist = VecLenf(last_p, vec);
+                               
+                               if (new_dist < dist)
+                               {
+                                       VECCOPY(p, vec);
+                                       dist = new_dist;
+                               }
+                       }
+               }
+               
+               if (dist != FLT_MAX)
+               {
+                       pt->type = dd->type;
+                       pt->mode = PT_SNAP;
+                       VECCOPY(pt->p, p);
+                       
+                       point_added = 1;
+               }
+               
+               BLI_freelistN(&depth_peels);
+       }
+       else
+       {
+               SK_Stroke *snap_stk;
+               float vec[3];
+               float no[3];
+               int found = 0;
+               int dist = SNAP_MIN_DISTANCE; // Use a user defined value here
+
+               /* snap to strokes */
+               // if (scene->snap_mode == SCE_SNAP_MODE_VERTEX) /* snap all the time to strokes */
+               for (snap_stk = sketch->strokes.first; snap_stk; snap_stk = snap_stk->next)
+               {
+                       SK_Point *spt = NULL;
+                       if (snap_stk == stk)
+                       {
+                               spt = sk_snapPointStroke(C, snap_stk, dd->mval, &dist, NULL, 0);
+                       }
+                       else
+                       {
+                               spt = sk_snapPointStroke(C, snap_stk, dd->mval, &dist, NULL, 1);
+                       }
+                               
+                       if (spt != NULL)
+                       {
+                               VECCOPY(pt->p, spt->p);
+                               point_added = 1;
+                       }
+               }
+
+               /* try to snap to closer object */
+               found = snapObjectsContext(C, dd->mval, &dist, vec, no, SNAP_NOT_SELECTED);
+               if (found == 1)
+               {
+                       pt->type = dd->type;
+                       pt->mode = PT_SNAP;
+                       VECCOPY(pt->p, vec);
+                       
+                       point_added = 1;
+               }
+       }
+       
+       return point_added;
+}
+
+int sk_addStrokeSnapPoint(bContext *C, SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData *dd)
+{
+       int point_added;
+       SK_Point pt;
+       
+       sk_initPoint(C, &pt);
+
+       point_added = sk_getStrokeSnapPoint(C, &pt, sketch, stk, dd);
+       
+       if (point_added)
+       {
+               float final_p[3];
+               float length, distance;
+               int total;
+               int i;
+               
+               VECCOPY(final_p, pt.p);
+               
+               sk_projectDrawPoint(C, pt.p, stk, dd);
+               sk_appendStrokePoint(stk, &pt);
+               
+               /* update all previous point to give smooth Z progresion */
+               total = 0;
+               length = 0;
+               for (i = stk->nb_points - 2; i > 0; i--)
+               {
+                       length += VecLenf(stk->points[i].p, stk->points[i + 1].p);
+                       total++;
+                       if (stk->points[i].mode == PT_SNAP || stk->points[i].type == PT_EXACT)
+                       {
+                               break;
+                       }
+               }
+               
+               if (total > 1)
+               {
+                       distance = sk_distanceDepth(C, final_p, stk->points[i].p);
+                       
+                       sk_interpolateDepth(C, stk, i + 1, stk->nb_points - 2, length, distance);
+               }
+               
+               VECCOPY(stk->points[stk->nb_points - 1].p, final_p);
+               
+               point_added = 1;
+       }
+       
+       return point_added;
+}
+
+void sk_addStrokePoint(bContext *C, SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData *dd, short qual)
+{
+       Scene *scene = CTX_data_scene(C);
+       int point_added = 0;
+       
+       if (qual & KM_CTRL)
+       {
+               point_added = sk_addStrokeSnapPoint(C, sketch, stk, dd);
+       }
+       
+       if (point_added == 0)
+       {
+               point_added = sk_addStrokeDrawPoint(C, sketch, stk, dd);
+       }
+       
+       if (scene->toolsettings->bone_sketching & BONE_SKETCHING_ADJUST)
+       {
+               sk_updateOverdraw(C, sketch, stk, dd);
+       }
+}
+
+void sk_getStrokePoint(bContext *C, SK_Point *pt, SK_Sketch *sketch, SK_Stroke *stk, SK_DrawData *dd, short qual)
+{
+       int point_added = 0;
+       
+       if (qual & KM_CTRL)
+       {
+               point_added = sk_getStrokeSnapPoint(C, pt, sketch, stk, dd);
+               LAST_SNAP_POINT_VALID = 1;
+               VECCOPY(LAST_SNAP_POINT, pt->p);
+       }
+       else
+       {
+               LAST_SNAP_POINT_VALID = 0;
+       }
+       
+       if (point_added == 0)
+       {
+               point_added = sk_getStrokeDrawPoint(C, pt, sketch, stk, dd);
+       }       
+}
+
+void sk_endContinuousStroke(SK_Stroke *stk)
+{
+       stk->points[stk->nb_points - 1].type = PT_EXACT;
+}
+
+void sk_updateNextPoint(SK_Sketch *sketch)
+{
+       if (sketch->active_stroke)
+       {
+               SK_Stroke *stk = sketch->active_stroke;
+               memcpy(&sketch->next_point, stk->points[stk->nb_points - 1].p, sizeof(SK_Point));
+       }
+}
+
+int sk_stroke_filtermval(SK_DrawData *dd)
+{
+       int retval = 0;
+       if (ABS(dd->mval[0] - dd->previous_mval[0]) + ABS(dd->mval[1] - dd->previous_mval[1]) > U.gp_manhattendist)
+       {
+               retval = 1;
+       }
+       
+       return retval;
+}
+
+void sk_initDrawData(SK_DrawData *dd)
+{
+//     XXX
+//     getmouseco_areawin(dd->mval);
+       dd->previous_mval[0] = -1;
+       dd->previous_mval[1] = -1;
+       dd->type = PT_EXACT;
+}
+/********************************************/
+
+static void* headPoint(void *arg);
+static void* tailPoint(void *arg);
+static void* nextPoint(void *arg);
+static void* nextNPoint(void *arg, int n);
+static void* peekPoint(void *arg, int n);
+static void* previousPoint(void *arg);
+static int   iteratorStopped(void *arg);
+
+static void initIteratorFct(SK_StrokeIterator *iter)
+{
+       iter->head = headPoint;
+       iter->tail = tailPoint;
+       iter->peek = peekPoint;
+       iter->next = nextPoint;
+       iter->nextN = nextNPoint;
+       iter->previous = previousPoint;
+       iter->stopped = iteratorStopped;        
+}
+
+static SK_Point* setIteratorValues(SK_StrokeIterator *iter, int index)
+{
+       SK_Point *pt = NULL;
+       
+       if (index >= 0 && index < iter->length)
+       {
+               pt = &(iter->stroke->points[iter->start + (iter->stride * index)]);
+               iter->p = pt->p;
+               iter->no = pt->no;
+       }
+       else
+       {
+               iter->p = NULL;
+               iter->no = NULL;
+       }
+       
+       return pt;
+}
+
+void initStrokeIterator(BArcIterator *arg, SK_Stroke *stk, int start, int end)
+{
+       SK_StrokeIterator *iter = (SK_StrokeIterator*)arg;
+
+       initIteratorFct(iter);
+       iter->stroke = stk;
+       
+       if (start < end)
+       {
+               iter->start = start + 1;
+               iter->end = end - 1;
+               iter->stride = 1;
+       }
+       else
+       {
+               iter->start = start - 1;
+               iter->end = end + 1;
+               iter->stride = -1;
+       }
+       
+       iter->length = iter->stride * (iter->end - iter->start + 1);
+       
+       iter->index = -1;
+}
+
+
+static void* headPoint(void *arg)
+{
+       SK_StrokeIterator *iter = (SK_StrokeIterator*)arg;
+       SK_Point *result = NULL;
+       
+       result = &(iter->stroke->points[iter->start - iter->stride]);
+       iter->p = result->p;
+       iter->no = result->no;
+       
+       return result;
+}
+
+static void* tailPoint(void *arg)
+{
+       SK_StrokeIterator *iter = (SK_StrokeIterator*)arg;
+       SK_Point *result = NULL;
+       
+       result = &(iter->stroke->points[iter->end + iter->stride]);
+       iter->p = result->p;
+       iter->no = result->no;
+       
+       return result;
+}
+
+static void* nextPoint(void *arg)
+{
+       SK_StrokeIterator *iter = (SK_StrokeIterator*)arg;
+       SK_Point *result = NULL;
+       
+       iter->index++;
+       if (iter->index < iter->length)
+       {
+               result = setIteratorValues(iter, iter->index);
+       }
+
+       return result;
+}
+
+static void* nextNPoint(void *arg, int n)
+{
+       SK_StrokeIterator *iter = (SK_StrokeIterator*)arg;
+       SK_Point *result = NULL;
+               
+       iter->index += n;
+
+       /* check if passed end */
+       if (iter->index < iter->length)
+       {
+               result = setIteratorValues(iter, iter->index);
+       }
+
+       return result;
+}
+
+static void* peekPoint(void *arg, int n)
+{
+       SK_StrokeIterator *iter = (SK_StrokeIterator*)arg;
+       SK_Point *result = NULL;
+       int index = iter->index + n;
+
+       /* check if passed end */
+       if (index < iter->length)
+       {
+               result = setIteratorValues(iter, index);
+       }
+
+       return result;
+}
+
+static void* previousPoint(void *arg)
+{
+       SK_StrokeIterator *iter = (SK_StrokeIterator*)arg;
+       SK_Point *result = NULL;
+       
+       if (iter->index > 0)
+       {
+               iter->index--;
+               result = setIteratorValues(iter, iter->index);
+       }
+
+       return result;
+}
+
+static int iteratorStopped(void *arg)
+{
+       SK_StrokeIterator *iter = (SK_StrokeIterator*)arg;
+
+       if (iter->index >= iter->length)
+       {
+               return 1;
+       }
+       else
+       {
+               return 0;
+       }
+}
+
+void sk_convertStroke(bContext *C, SK_Stroke *stk)
+{
+       Object *obedit = CTX_data_edit_object(C);
+       Scene *scene = CTX_data_scene(C);
+       bArmature *arm = obedit->data;
+       SK_Point *head;
+       EditBone *parent = NULL;
+       float invmat[4][4]; /* move in caller function */
+       float tmat[3][3];
+       int head_index = 0;
+       int i;
+       
+       head = NULL;
+       
+       Mat4Invert(invmat, obedit->obmat);
+       
+       Mat3CpyMat4(tmat, obedit->obmat);
+       Mat3Transp(tmat);
+       
+       for (i = 0; i < stk->nb_points; i++)
+       {
+               SK_Point *pt = stk->points + i;
+               
+               if (pt->type == PT_EXACT)
+               {
+                       if (head == NULL)
+                       {
+                               head_index = i;
+                               head = pt;
+                       }
+                       else
+                       {
+                               EditBone *bone = NULL;
+                               EditBone *new_parent;
+                               
+                               if (i - head_index > 1)
+                               {
+                                       SK_StrokeIterator sk_iter;
+                                       BArcIterator *iter = (BArcIterator*)&sk_iter;
+
+                                       initStrokeIterator(iter, stk, head_index, i);
+                                       
+                                       if (scene->toolsettings->bone_sketching_convert == SK_CONVERT_CUT_ADAPTATIVE)
+                                       {
+                                               bone = subdivideArcBy(C, arm, arm->edbo, iter, invmat, tmat, nextAdaptativeSubdivision);
+                                       }
+                                       else if (scene->toolsettings->bone_sketching_convert == SK_CONVERT_CUT_LENGTH)
+                                       {
+                                               bone = subdivideArcBy(C, arm, arm->edbo, iter, invmat, tmat, nextLengthSubdivision);
+                                       }
+                                       else if (scene->toolsettings->bone_sketching_convert == SK_CONVERT_CUT_FIXED)
+                                       {
+                                               bone = subdivideArcBy(C, arm, arm->edbo, iter, invmat, tmat, nextFixedSubdivision);
+                                       }
+                               }
+                               
+                               if (bone == NULL)
+                               {
+                                       bone = addEditBone(arm, "Bone");
+                                       
+                                       VECCOPY(bone->head, head->p);
+                                       VECCOPY(bone->tail, pt->p);
+
+                                       Mat4MulVecfl(invmat, bone->head);
+                                       Mat4MulVecfl(invmat, bone->tail);
+                                       setBoneRollFromNormal(bone, pt->no, invmat, tmat);
+                               }
+                               
+                               new_parent = bone;
+                               bone->flag |= BONE_SELECTED|BONE_TIPSEL|BONE_ROOTSEL;
+                               
+                               /* move to end of chain */
+                               while (bone->parent != NULL)
+                               {
+                                       bone = bone->parent;
+                                       bone->flag |= BONE_SELECTED|BONE_TIPSEL|BONE_ROOTSEL;
+                               }
+
+                               if (parent != NULL)
+                               {
+                                       bone->parent = parent;
+                                       bone->flag |= BONE_CONNECTED;                                   
+                               }
+                               
+                               parent = new_parent;
+                               head_index = i;
+                               head = pt;
+                       }
+               }
+       }
+}
+
+void sk_convert(bContext *C, SK_Sketch *sketch)
+{
+       Scene *scene = CTX_data_scene(C);
+       SK_Stroke *stk;
+       
+       for (stk = sketch->strokes.first; stk; stk = stk->next)
+       {
+               if (stk->selected == 1)
+               {
+                       if (scene->toolsettings->bone_sketching_convert == SK_CONVERT_RETARGET)
+                       {
+                               sk_retargetStroke(C, stk);
+                       }
+                       else
+                       {
+                               sk_convertStroke(C, stk);
+                       }
+//                     XXX
+//                     allqueue(REDRAWBUTSEDIT, 0);
+               }
+       }
+}
+/******************* GESTURE *************************/
+
+
+/* returns the number of self intersections */
+int sk_getSelfIntersections(bContext *C, ListBase *list, SK_Stroke *gesture)
+{
+       ARegion *ar = CTX_wm_region(C);
+       int added = 0;
+       int s_i;
+
+       for (s_i = 0; s_i < gesture->nb_points - 1; s_i++)
+       {
+               float s_p1[3] = {0, 0, 0};
+               float s_p2[3] = {0, 0, 0};
+               int g_i;
+               
+               project_float(ar, gesture->points[s_i].p, s_p1);
+               project_float(ar, gesture->points[s_i + 1].p, s_p2);
+
+               /* start checking from second next, because two consecutive cannot intersect */
+               for (g_i = s_i + 2; g_i < gesture->nb_points - 1; g_i++)
+               {
+                       float g_p1[3] = {0, 0, 0};
+                       float g_p2[3] = {0, 0, 0};
+                       float vi[3];
+                       float lambda;
+                       
+                       project_float(ar, gesture->points[g_i].p, g_p1);
+                       project_float(ar, gesture->points[g_i + 1].p, g_p2);
+                       
+                       if (LineIntersectLineStrict(s_p1, s_p2, g_p1, g_p2, vi, &lambda))
+                       {
+                               SK_Intersection *isect = MEM_callocN(sizeof(SK_Intersection), "Intersection");
+                               
+                               isect->gesture_index = g_i;
+                               isect->before = s_i;
+                               isect->after = s_i + 1;
+                               isect->stroke = gesture;
+                               
+                               VecSubf(isect->p, gesture->points[s_i + 1].p, gesture->points[s_i].p);
+                               VecMulf(isect->p, lambda);
+                               VecAddf(isect->p, isect->p, gesture->points[s_i].p);
+                               
+                               BLI_addtail(list, isect);
+
+                               added++;
+                       }
+               }
+       }
+       
+       return added;
+}
+
+int cmpIntersections(void *i1, void *i2)
+{
+       SK_Intersection *isect1 = i1, *isect2 = i2;
+       
+       if (isect1->stroke == isect2->stroke)
+       {
+               if (isect1->before < isect2->before)
+               {
+                       return -1;
+               }
+               else if (isect1->before > isect2->before)
+               {
+                       return 1;
+               }
+               else
+               {
+                       if (isect1->lambda < isect2->lambda)
+                       {
+                               return -1;
+                       }
+                       else if (isect1->lambda > isect2->lambda)
+                       {
+                               return 1;
+                       }
+               }
+       }
+       
+       return 0;
+}
+
+
+/* returns the maximum number of intersections per stroke */
+int sk_getIntersections(bContext *C, ListBase *list, SK_Sketch *sketch, SK_Stroke *gesture)
+{
+       ARegion *ar = CTX_wm_region(C);
+       ScrArea *sa = CTX_wm_area(C);
+       View3D *v3d = sa->spacedata.first;
+       SK_Stroke *stk;
+       int added = 0;
+
+       for (stk = sketch->strokes.first; stk; stk = stk->next)
+       {
+               int s_added = 0;
+               int s_i;
+               
+               for (s_i = 0; s_i < stk->nb_points - 1; s_i++)
+               {
+                       float s_p1[3] = {0, 0, 0};
+                       float s_p2[3] = {0, 0, 0};
+                       int g_i;
+                       
+                       project_float(ar, stk->points[s_i].p, s_p1);
+                       project_float(ar, stk->points[s_i + 1].p, s_p2);
+
+                       for (g_i = 0; g_i < gesture->nb_points - 1; g_i++)
+                       {
+                               float g_p1[3] = {0, 0, 0};
+                               float g_p2[3] = {0, 0, 0};
+                               float vi[3];
+                               float lambda;
+                               
+                               project_float(ar, gesture->points[g_i].p, g_p1);
+                               project_float(ar, gesture->points[g_i + 1].p, g_p2);
+                               
+                               if (LineIntersectLineStrict(s_p1, s_p2, g_p1, g_p2, vi, &lambda))
+                               {
+                                       SK_Intersection *isect = MEM_callocN(sizeof(SK_Intersection), "Intersection");
+                                       float ray_start[3], ray_end[3];
+                                       short mval[2];
+                                       
+                                       isect->gesture_index = g_i;
+                                       isect->before = s_i;
+                                       isect->after = s_i + 1;
+                                       isect->stroke = stk;
+                                       isect->lambda = lambda;
+                                       
+                                       mval[0] = (short)(vi[0]);
+                                       mval[1] = (short)(vi[1]);
+                                       viewline(ar, v3d, mval, ray_start, ray_end);
+                                       
+                                       LineIntersectLine(      stk->points[s_i].p,
+                                                                               stk->points[s_i + 1].p,
+                                                                               ray_start,
+                                                                               ray_end,
+                                                                               isect->p,
+                                                                               vi);
+                                       
+                                       BLI_addtail(list, isect);
+
+                                       s_added++;
+                               }
+                       }
+               }
+               
+               added = MAX2(s_added, added);
+       }
+       
+       BLI_sortlist(list, cmpIntersections);
+       
+       return added;
+}
+
+int sk_getSegments(SK_Stroke *segments, SK_Stroke *gesture)
+{
+       SK_StrokeIterator sk_iter;
+       BArcIterator *iter = (BArcIterator*)&sk_iter;
+       
+       float CORRELATION_THRESHOLD = 0.99f;
+       float *vec;
+       int i, j;
+       
+       sk_appendStrokePoint(segments, &gesture->points[0]);
+       vec = segments->points[segments->nb_points - 1].p;
+
+       initStrokeIterator(iter, gesture, 0, gesture->nb_points - 1);
+
+       for (i = 1, j = 0; i < gesture->nb_points; i++)
+       { 
+               float n[3];
+               
+               /* Calculate normal */
+               VecSubf(n, gesture->points[i].p, vec);
+               
+               if (calcArcCorrelation(iter, j, i, vec, n) < CORRELATION_THRESHOLD)
+               {
+                       j = i - 1;
+                       sk_appendStrokePoint(segments, &gesture->points[j]);
+                       vec = segments->points[segments->nb_points - 1].p;
+                       segments->points[segments->nb_points - 1].type = PT_EXACT;
+               }
+       }
+
+       sk_appendStrokePoint(segments, &gesture->points[gesture->nb_points - 1]);
+       
+       return segments->nb_points - 1;
+}
+
+int sk_detectCutGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       if (gest->nb_segments == 1 && gest->nb_intersections == 1)
+       {
+               return 1;
+       }
+
+       return 0;
+}
+
+void sk_applyCutGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       SK_Intersection *isect;
+       
+       for (isect = gest->intersections.first; isect; isect = isect->next)
+       {
+               SK_Point pt;
+               
+               pt.type = PT_EXACT;
+               pt.mode = PT_PROJECT; /* take mode from neighbouring points */
+               VECCOPY(pt.p, isect->p);
+               
+               sk_insertStrokePoint(isect->stroke, &pt, isect->after);
+       }
+}
+
+int sk_detectTrimGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       if (gest->nb_segments == 2 && gest->nb_intersections == 1 && gest->nb_self_intersections == 0)
+       {
+               float s1[3], s2[3];
+               float angle;
+               
+               VecSubf(s1, gest->segments->points[1].p, gest->segments->points[0].p);
+               VecSubf(s2, gest->segments->points[2].p, gest->segments->points[1].p);
+               
+               angle = VecAngle2(s1, s2);
+       
+               if (angle > 60 && angle < 120)
+               {
+                       return 1;
+               }
+       }
+
+       return 0;
+}
+
+void sk_applyTrimGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       SK_Intersection *isect;
+       float trim_dir[3];
+       
+       VecSubf(trim_dir, gest->segments->points[2].p, gest->segments->points[1].p);
+       
+       for (isect = gest->intersections.first; isect; isect = isect->next)
+       {
+               SK_Point pt;
+               float stroke_dir[3];
+               
+               pt.type = PT_EXACT;
+               pt.mode = PT_PROJECT; /* take mode from neighbouring points */
+               VECCOPY(pt.p, isect->p);
+               
+               VecSubf(stroke_dir, isect->stroke->points[isect->after].p, isect->stroke->points[isect->before].p);
+               
+               /* same direction, trim end */
+               if (Inpf(stroke_dir, trim_dir) > 0)
+               {
+                       sk_replaceStrokePoint(isect->stroke, &pt, isect->after);
+                       sk_trimStroke(isect->stroke, 0, isect->after);
+               }
+               /* else, trim start */
+               else
+               {
+                       sk_replaceStrokePoint(isect->stroke, &pt, isect->before);
+                       sk_trimStroke(isect->stroke, isect->before, isect->stroke->nb_points - 1);
+               }
+       
+       }
+}
+
+int sk_detectCommandGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       if (gest->nb_segments > 2 && gest->nb_intersections == 2 && gest->nb_self_intersections == 1)
+       {
+               SK_Intersection *isect, *self_isect;
+               
+               /* get the the last intersection of the first pair */
+               for( isect = gest->intersections.first; isect; isect = isect->next )
+               {
+                       if (isect->stroke == isect->next->stroke)
+                       {
+                               isect = isect->next;
+                               break;
+                       }
+               }
+               
+               self_isect = gest->self_intersections.first;
+               
+               if (isect && isect->gesture_index < self_isect->gesture_index)
+               {
+                       return 1;
+               }
+       }
+       
+       return 0;
+}
+
+void sk_applyCommandGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       SK_Intersection *isect;
+       int command = 1;
+       
+//     XXX
+//     command = pupmenu("Action %t|Flatten %x1|Straighten %x2|Polygonize %x3");
+       if(command < 1) return;
+
+       for (isect = gest->intersections.first; isect; isect = isect->next)
+       {
+               SK_Intersection *i2;
+               
+               i2 = isect->next;
+               
+               if (i2 && i2->stroke == isect->stroke)
+               {
+                       switch (command)
+                       {
+                               case 1:
+                                       sk_flattenStroke(isect->stroke, isect->before, i2->after);
+                                       break;
+                               case 2:
+                                       sk_straightenStroke(isect->stroke, isect->before, i2->after, isect->p, i2->p);
+                                       break;
+                               case 3:
+                                       sk_polygonizeStroke(isect->stroke, isect->before, i2->after);
+                                       break;
+                       }
+
+                       isect = i2;
+               }
+       }
+}
+
+int sk_detectDeleteGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       if (gest->nb_segments == 2 && gest->nb_intersections == 2)
+       {
+               float s1[3], s2[3];
+               float angle;
+               
+               VecSubf(s1, gest->segments->points[1].p, gest->segments->points[0].p);
+               VecSubf(s2, gest->segments->points[2].p, gest->segments->points[1].p);
+               
+               angle = VecAngle2(s1, s2);
+               
+               if (angle > 120)
+               {
+                       return 1;
+               }
+       }
+       
+       return 0;
+}
+
+void sk_applyDeleteGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       SK_Intersection *isect;
+       
+       for (isect = gest->intersections.first; isect; isect = isect->next)
+       {
+               /* only delete strokes that are crossed twice */
+               if (isect->next && isect->next->stroke == isect->stroke)
+               {
+                       isect = isect->next;
+                       
+                       sk_removeStroke(sketch, isect->stroke);
+               }
+       }
+}
+
+int sk_detectMergeGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       ARegion *ar = CTX_wm_region(C);
+       if (gest->nb_segments > 2 && gest->nb_intersections == 2)
+       {
+               short start_val[2], end_val[2];
+               short dist;
+               
+               project_short_noclip(ar, gest->stk->points[0].p, start_val);
+               project_short_noclip(ar, sk_lastStrokePoint(gest->stk)->p, end_val);
+               
+               dist = MAX2(ABS(start_val[0] - end_val[0]), ABS(start_val[1] - end_val[1]));
+               
+               /* if gesture is a circle */
+               if ( dist <= 20 )
+               {
+                       SK_Intersection *isect;
+                       
+                       /* check if it circled around an exact point */
+                       for (isect = gest->intersections.first; isect; isect = isect->next)
+                       {
+                               /* only delete strokes that are crossed twice */
+                               if (isect->next && isect->next->stroke == isect->stroke)
+                               {
+                                       int start_index, end_index;
+                                       int i;
+                                       
+                                       start_index = MIN2(isect->after, isect->next->after);
+                                       end_index = MAX2(isect->before, isect->next->before);
+       
+                                       for (i = start_index; i <= end_index; i++)
+                                       {
+                                               if (isect->stroke->points[i].type == PT_EXACT)
+                                               {
+                                                       return 1; /* at least one exact point found, stop detect here */
+                                               }
+                                       }
+       
+                                       /* skip next */                         
+                                       isect = isect->next;
+                               }
+                       }
+               }
+       }
+                               
+       return 0;
+}
+
+void sk_applyMergeGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       SK_Intersection *isect;
+       
+       /* check if it circled around an exact point */
+       for (isect = gest->intersections.first; isect; isect = isect->next)
+       {
+               /* only merge strokes that are crossed twice */
+               if (isect->next && isect->next->stroke == isect->stroke)
+               {
+                       int start_index, end_index;
+                       int i;
+                       
+                       start_index = MIN2(isect->after, isect->next->after);
+                       end_index = MAX2(isect->before, isect->next->before);
+
+                       for (i = start_index; i <= end_index; i++)
+                       {
+                               /* if exact, switch to continuous */
+                               if (isect->stroke->points[i].type == PT_EXACT)
+                               {
+                                       isect->stroke->points[i].type = PT_CONTINUOUS;
+                               }
+                       }
+
+                       /* skip next */                         
+                       isect = isect->next;
+               }
+       }
+}
+
+int sk_detectReverseGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       if (gest->nb_segments > 2 && gest->nb_intersections == 2 && gest->nb_self_intersections == 0)
+       {
+               SK_Intersection *isect;
+               
+               /* check if it circled around an exact point */
+               for (isect = gest->intersections.first; isect; isect = isect->next)
+               {
+                       /* only delete strokes that are crossed twice */
+                       if (isect->next && isect->next->stroke == isect->stroke)
+                       {
+                               float start_v[3], end_v[3];
+                               float angle;
+                               
+                               if (isect->gesture_index < isect->next->gesture_index)
+                               {
+                                       VecSubf(start_v, isect->p, gest->stk->points[0].p);
+                                       VecSubf(end_v, sk_lastStrokePoint(gest->stk)->p, isect->next->p);
+                               }
+                               else
+                               {
+                                       VecSubf(start_v, isect->next->p, gest->stk->points[0].p);
+                                       VecSubf(end_v, sk_lastStrokePoint(gest->stk)->p, isect->p);
+                               }
+                               
+                               angle = VecAngle2(start_v, end_v);
+                               
+                               if (angle > 120)
+                               {
+                                       return 1;
+                               }
+       
+                               /* skip next */                         
+                               isect = isect->next;
+                       }
+               }
+       }
+               
+       return 0;
+}
+
+void sk_applyReverseGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       SK_Intersection *isect;
+       
+       for (isect = gest->intersections.first; isect; isect = isect->next)
+       {
+               /* only reverse strokes that are crossed twice */
+               if (isect->next && isect->next->stroke == isect->stroke)
+               {
+                       sk_reverseStroke(isect->stroke);
+
+                       /* skip next */                         
+                       isect = isect->next;
+               }
+       }
+}
+
+int sk_detectConvertGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       if (gest->nb_segments == 3 && gest->nb_self_intersections == 1)
+       {
+               return 1;
+       }
+       return 0;
+}
+
+void sk_applyConvertGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       sk_convert(C, sketch);
+}
+
+static void sk_initGesture(bContext *C, SK_Gesture *gest, SK_Sketch *sketch)
+{
+       gest->intersections.first = gest->intersections.last = NULL;
+       gest->self_intersections.first = gest->self_intersections.last = NULL;
+       
+       gest->segments = sk_createStroke();
+       gest->stk = sketch->gesture;
+
+       gest->nb_self_intersections = sk_getSelfIntersections(C, &gest->self_intersections, gest->stk);
+       gest->nb_intersections = sk_getIntersections(C, &gest->intersections, sketch, gest->stk);
+       gest->nb_segments = sk_getSegments(gest->segments, gest->stk);
+}
+
+static void sk_freeGesture(SK_Gesture *gest)
+{
+       sk_freeStroke(gest->segments);
+       BLI_freelistN(&gest->intersections);
+       BLI_freelistN(&gest->self_intersections);
+}
+
+void sk_applyGesture(bContext *C, SK_Sketch *sketch)
+{
+       SK_Gesture gest;
+       SK_GestureAction *act;
+       
+       sk_initGesture(C, &gest, sketch);
+       
+       /* detect and apply */
+       for (act = GESTURE_ACTIONS; act->apply != NULL; act++)
+       {
+               if (act->detect(C, &gest, sketch))
+               {
+                       act->apply(C, &gest, sketch);
+                       break;
+               }
+       }
+       
+       sk_freeGesture(&gest);
+}
+
+/********************************************/
+
+void sk_deleteSelectedStrokes(SK_Sketch *sketch)
+{
+       SK_Stroke *stk, *next;
+       
+       for (stk = sketch->strokes.first; stk; stk = next)
+       {
+               next = stk->next;
+               
+               if (stk->selected == 1)
+               {
+                       sk_removeStroke(sketch, stk);
+               }
+       }
+}
+
+void sk_selectAllSketch(SK_Sketch *sketch, int mode)
+{
+       SK_Stroke *stk = NULL;
+       
+       if (mode == -1)
+       {
+               for (stk = sketch->strokes.first; stk; stk = stk->next)
+               {
+                       stk->selected = 0;
+               }
+       }
+       else if (mode == 0)
+       {
+               for (stk = sketch->strokes.first; stk; stk = stk->next)
+               {
+                       stk->selected = 1;
+               }
+       }
+       else if (mode == 1)
+       {
+               int selected = 1;
+               
+               for (stk = sketch->strokes.first; stk; stk = stk->next)
+               {
+                       selected &= stk->selected;
+               }
+               
+               selected ^= 1;
+
+               for (stk = sketch->strokes.first; stk; stk = stk->next)
+               {
+                       stk->selected = selected;
+               }
+       }
+}
+
+void sk_selectStroke(SK_Sketch *sketch, short mval[2], int extend)
+{
+       unsigned int buffer[MAXPICKBUF];
+       short hits;
+
+//XXX
+#if 0
+       persp(PERSP_VIEW);
+
+       hits = view3d_opengl_select(buffer, MAXPICKBUF, mval[0]-5, mval[1]-5, mval[0]+5, mval[1]+5);
+       if(hits==0)
+               hits = view3d_opengl_select(buffer, MAXPICKBUF, mval[0]-12, mval[1]-12, mval[0]+12, mval[1]+12);
+               
+       if (hits>0)
+       {
+               int besthitresult = -1;
+                       
+               if(hits == 1) {
+                       besthitresult = buffer[3];
+               }
+               else {
+                       besthitresult = buffer[3];
+                       /* loop and get best hit */
+               }
+               
+               if (besthitresult > 0)
+               {
+                       SK_Stroke *selected_stk = BLI_findlink(&sketch->strokes, besthitresult - 1);
+                       
+                       if (extend == 0)
+                       {
+                               sk_selectAllSketch(sketch, -1);
+                               
+                               selected_stk->selected = 1;
+                       }
+                       else
+                       {
+                               selected_stk->selected ^= 1;
+                       }
+                       
+                       
+               }
+       }
+#endif
+}
+
+void sk_queueRedrawSketch(SK_Sketch *sketch)
+{
+       if (sketch->active_stroke != NULL)
+       {
+               SK_Point *last = sk_lastStrokePoint(sketch->active_stroke);
+               
+               if (last != NULL)
+               {
+//                     XXX
+//                     allqueue(REDRAWVIEW3D, 0);
+               }
+       }
+}
+
+void sk_drawSketch(bContext *C, SK_Sketch *sketch, int with_names)
+{
+       Scene *scene = CTX_data_scene(C);
+       SK_Stroke *stk;
+       short qual = 0;
+       
+       glDisable(GL_DEPTH_TEST);
+
+       glLineWidth(UI_GetThemeValuef(TH_VERTEX_SIZE));
+       glPointSize(UI_GetThemeValuef(TH_VERTEX_SIZE));
+       
+       if (with_names)
+       {
+               int id;
+               for (id = 1, stk = sketch->strokes.first; stk; id++, stk = stk->next)
+               {
+                       sk_drawStroke(stk, id, NULL, -1, -1);
+               }
+               
+               glLoadName(-1);
+       }
+       else
+       {
+               float selected_rgb[3] = {1, 0, 0};
+               float unselected_rgb[3] = {1, 0.5, 0};
+               
+               for (stk = sketch->strokes.first; stk; stk = stk->next)
+               {
+                       int start = -1;
+                       int end = -1;
+                       
+                       if (sk_hasOverdraw(sketch, stk))
+                       {
+                               sk_adjustIndexes(sketch, &start, &end);
+                       }
+                       
+                       sk_drawStroke(stk, -1, (stk->selected==1?selected_rgb:unselected_rgb), start, end);
+               
+                       if (stk->selected == 1)
+                       {
+                               sk_drawStrokeSubdivision(C, stk);
+                       }
+               }
+       
+               /* only draw gesture in active area */
+               if (sketch->gesture != NULL /*&& area_is_active_area(G.vd->area)*/)
+               {
+                       float gesture_rgb[3] = {0, 0.5, 1};
+                       sk_drawStroke(sketch->gesture, -1, gesture_rgb, -1, -1);
+               }
+               
+               if (sketch->active_stroke != NULL)
+               {
+                       SK_Point *last = sk_lastStrokePoint(sketch->active_stroke);
+                       
+                       if (scene->toolsettings->bone_sketching & BONE_SKETCHING_QUICK)
+                       {
+                               sk_drawStrokeSubdivision(C, sketch->active_stroke);
+                       }
+                       
+                       if (last != NULL)
+                       {
+                               /* update point if in active area */
+                               if (1 /*area_is_active_area(G.vd->area)*/)
+                               {
+                                       SK_DrawData dd;
+                                       
+                                       sk_initDrawData(&dd);
+                                       sk_getStrokePoint(C, &sketch->next_point, sketch, sketch->active_stroke, &dd, qual);
+                               }
+                               
+                               glEnable(GL_LINE_STIPPLE);
+                               glColor3fv(selected_rgb);
+                               glBegin(GL_LINE_STRIP);
+                               
+                                       glVertex3fv(last->p);
+                                       glVertex3fv(sketch->next_point.p);
+                               
+                               glEnd();
+                               
+                               glDisable(GL_LINE_STIPPLE);
+       
+                               switch (sketch->next_point.mode)
+                               {
+                                       case PT_SNAP:
+                                               glColor3f(0, 1, 0);
+                                               break;
+                                       case PT_PROJECT:
+                                               glColor3f(0, 0, 0);
+                                               break;
+                               }
+                               
+                               glBegin(GL_POINTS);
+                               
+                                       glVertex3fv(sketch->next_point.p);
+                               
+                               glEnd();
+                       }
+               }
+       }
+       
+       glLineWidth(1.0);
+       glPointSize(1.0);
+
+       glEnable(GL_DEPTH_TEST);
+}
+
+int sk_paint(bContext *C, SK_Sketch *sketch, short mbut)
+{
+       Scene *scene = CTX_data_scene(C);
+       int retval = 1;
+       short qual = 0;
+       
+       if (mbut == LEFTMOUSE)
+       {
+               SK_DrawData dd;
+               if (sketch->active_stroke == NULL)
+               {
+                       sk_startStroke(sketch);
+                       sk_selectAllSketch(sketch, -1);
+                       
+                       sketch->active_stroke->selected = 1;
+               }
+
+               sk_initDrawData(&dd);
+               
+               /* paint loop */
+               do {
+                       /* get current user input */
+//                     XXX
+//                     getmouseco_areawin(dd.mval);
+                       
+                       /* only add current point to buffer if mouse moved (otherwise wait until it does) */
+                       if (sk_stroke_filtermval(&dd)) {
+
+                               sk_addStrokePoint(C, sketch, sketch->active_stroke, &dd, qual);
+                               sk_updateDrawData(&dd);
+//                             XXX
+//                             force_draw(0);
+                       }
+                       else
+                       {
+//                             BIF_wait_for_statechange();
+                       }
+                       
+//                     while( qtest() ) {
+//                             short event, val;
+//                             event = extern_qread(&val);
+//                     }
+                       
+                       /* do mouse checking at the end, so don't check twice, and potentially
+                        * miss a short tap 
+                        */
+               } while (0 /*get_mbut() & L_MOUSE*/);
+               
+               sk_endContinuousStroke(sketch->active_stroke);
+               sk_filterLastContinuousStroke(sketch->active_stroke);
+               sk_updateNextPoint(sketch);
+       }
+       else if (mbut == RIGHTMOUSE)
+       {
+               if (sketch->active_stroke != NULL)
+               {
+                       SK_Stroke *stk = sketch->active_stroke;
+                       
+                       sk_endStroke(C, sketch);
+                       
+                       if (scene->toolsettings->bone_sketching & BONE_SKETCHING_QUICK)
+                       {
+                               if (scene->toolsettings->bone_sketching_convert == SK_CONVERT_RETARGET)
+                               {
+                                       sk_retargetStroke(C, stk);
+                               }
+                               else
+                               {
+                                       sk_convertStroke(C, stk);
+                               }
+//                             XXX
+//                             BIF_undo_push("Convert Sketch");
+                               sk_removeStroke(sketch, stk);
+//                             XXX
+//                             allqueue(REDRAWBUTSEDIT, 0);
+                       }
+       
+//                     XXX             
+//                     allqueue(REDRAWVIEW3D, 0);
+               }
+               /* no gestures in quick mode */
+               else if (scene->toolsettings->bone_sketching & BONE_SKETCHING_QUICK)
+               {
+                       retval = 0; /* return zero for default click behavior */
+               }
+               else
+               {
+                       SK_DrawData dd;
+                       sketch->gesture = sk_createStroke();
+       
+                       sk_initDrawData(&dd);
+                       
+                       /* paint loop */
+                       do {
+                               /* get current user input */
+//                             XXX
+//                             getmouseco_areawin(dd.mval);
+                               
+                               /* only add current point to buffer if mouse moved (otherwise wait until it does) */
+                               if (sk_stroke_filtermval(&dd)) {
+
+                                       sk_addStrokeDrawPoint(C, sketch, sketch->gesture, &dd);
+                                       sk_updateDrawData(&dd);
+                                       
+                                       /* draw only if mouse has moved */
+                                       if (sketch->gesture->nb_points > 1)
+                                       {
+//                                             XXX
+//                                             force_draw(0);
+                                       }
+                               }
+                               else
+                               {
+//                                     BIF_wait_for_statechange();
+                               }
+                               
+//                             while( qtest() ) {
+//                                     short event, val;
+//                                     event = extern_qread(&val);
+//                             }
+                               
+                               /* do mouse checking at the end, so don't check twice, and potentially
+                                * miss a short tap 
+                                */
+                       } while (0 /*get_mbut() & R_MOUSE*/);
+                       
+                       sk_endContinuousStroke(sketch->gesture);
+                       sk_filterLastContinuousStroke(sketch->gesture);
+                       sk_filterLastContinuousStroke(sketch->gesture);
+                       sk_filterLastContinuousStroke(sketch->gesture);
+       
+                       if (sketch->gesture->nb_points > 1)             
+                       {
+                               /* apply gesture here */
+                               sk_applyGesture(C, sketch);
+                       }
+       
+                       sk_freeStroke(sketch->gesture);
+                       sketch->gesture = NULL;
+                       
+//                     XXX
+//                     allqueue(REDRAWVIEW3D, 0);
+               }
+       }
+       
+       return retval;
+}
+
+void BDR_drawSketchNames(bContext *C)
+{
+       if (BIF_validSketchMode(C))
+       {
+               if (GLOBAL_sketch != NULL)
+               {
+                       sk_drawSketch(C, GLOBAL_sketch, 1);
+               }
+       }
+}
+
+void BDR_drawSketch(bContext *C)
+{
+       if (BIF_validSketchMode(C))
+       {
+               if (GLOBAL_sketch != NULL)
+               {
+                       sk_drawSketch(C, GLOBAL_sketch, 0);
+               }
+       }
+}
+
+void BIF_endStrokeSketch(bContext *C)
+{
+       if (BIF_validSketchMode(C))
+       {
+               if (GLOBAL_sketch != NULL)
+               {
+                       sk_endStroke(C, GLOBAL_sketch);
+//                     allqueue(REDRAWVIEW3D, 0);
+               }
+       }
+}
+
+void BIF_cancelStrokeSketch(bContext *C)
+{
+       if (BIF_validSketchMode(C))
+       {
+               if (GLOBAL_sketch != NULL)
+               {
+                       sk_cancelStroke(GLOBAL_sketch);
+//                     allqueue(REDRAWVIEW3D, 0);
+               }
+       }
+}
+
+void BIF_deleteSketch(bContext *C)
+{
+       if (BIF_validSketchMode(C))
+       {
+               if (GLOBAL_sketch != NULL)
+               {
+                       sk_deleteSelectedStrokes(GLOBAL_sketch);
+//                     allqueue(REDRAWVIEW3D, 0);
+               }
+       }
+}
+
+void BIF_convertSketch(bContext *C)
+{
+       if (BIF_validSketchMode(C))
+       {
+               if (GLOBAL_sketch != NULL)
+               {
+                       sk_convert(C, GLOBAL_sketch);
+//                     BIF_undo_push("Convert Sketch");
+//                     allqueue(REDRAWVIEW3D, 0);
+//                     allqueue(REDRAWBUTSEDIT, 0);
+               }
+       }
+}
+
+int BIF_paintSketch(bContext *C, short mbut)
+{
+       if (BIF_validSketchMode(C))
+       {
+               if (GLOBAL_sketch == NULL)
+               {
+                       GLOBAL_sketch = sk_createSketch();
+               }
+               
+               return sk_paint(C, GLOBAL_sketch, mbut);
+       }
+       else
+       {
+               return 0;
+       }
+}
+       
+
+void BDR_queueDrawSketch(bContext *C)
+{
+       if (BIF_validSketchMode(C))
+       {
+               if (GLOBAL_sketch != NULL)
+               {
+                       sk_queueRedrawSketch(GLOBAL_sketch);
+               }
+       }
+}
+
+void BIF_selectAllSketch(bContext *C, int mode)
+{
+       if (BIF_validSketchMode(C))
+       {
+               if (GLOBAL_sketch != NULL)
+               {
+                       sk_selectAllSketch(GLOBAL_sketch, mode);
+//                     XXX
+//                     allqueue(REDRAWVIEW3D, 0);
+               }
+       }
+}
+
+int BIF_validSketchMode(bContext *C)
+{
+       Object *obedit = CTX_data_edit_object(C);
+       Scene *scene = CTX_data_scene(C);
+       
+       if (obedit && 
+               obedit->type == OB_ARMATURE && 
+               scene->toolsettings->bone_sketching & BONE_SKETCHING)
+       {
+               return 1;
+       }
+       else
+       {
+               return 0;
+       }
+}
+
+int BIF_fullSketchMode(bContext *C)
+{
+       Object *obedit = CTX_data_edit_object(C);
+       Scene *scene = CTX_data_scene(C);
+       
+       if (obedit && 
+               obedit->type == OB_ARMATURE && 
+               scene->toolsettings->bone_sketching & BONE_SKETCHING && 
+               (scene->toolsettings->bone_sketching & BONE_SKETCHING_QUICK) == 0)
+       {
+               return 1;
+       }
+       else
+       {
+               return 0;
+       }
+}
+
+void BIF_freeSketch(bContext *C)
+{
+       if (GLOBAL_sketch != NULL)
+       {
+               sk_freeSketch(GLOBAL_sketch);
+               GLOBAL_sketch = NULL;
+       }
+}
+
+void BIF_sk_selectStroke(bContext *C, short mval[2], int extend)
+{
+       if (GLOBAL_sketch != NULL)
+       {
+               sk_selectStroke(GLOBAL_sketch, mval, extend);
+       }
+}
diff --git a/source/blender/editors/armature/reeb.c b/source/blender/editors/armature/reeb.c
new file mode 100644 (file)
index 0000000..a38b4de
--- /dev/null
@@ -0,0 +1,3725 @@
+/**
+ * $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. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * 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 *****
+ */
+#include <math.h>
+#include <string.h> // for memcpy
+#include <stdio.h>
+#include <stdlib.h> // for qsort
+#include <float.h>
+
+#include "PIL_time.h"
+
+#include "DNA_listBase.h"
+#include "DNA_scene_types.h"
+#include "DNA_space_types.h"
+#include "DNA_object_types.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_armature_types.h"
+
+#include "BKE_context.h"
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_blenlib.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 "ED_mesh.h"
+#include "ED_armature.h"
+//#include "BIF_interface.h"
+//#include "BIF_toolbox.h"
+//#include "BIF_graphics.h"
+#include "BIF_gl.h"
+#include "UI_resources.h"
+
+#include "BKE_global.h"
+#include "BKE_utildefines.h"
+#include "BKE_customdata.h"
+
+//#include "blendef.h"
+
+#include "ONL_opennl.h"
+
+#include "reeb.h"
+
+
+ReebGraph *GLOBAL_RG = NULL;
+ReebGraph *FILTERED_RG = NULL;
+
+/*
+ * Skeleton generation algorithm based on: 
+ * "Harmonic Skeleton for Realistic Character Animation"
+ * Gregoire Aujay, Franck Hetroy, Francis Lazarus and Christine Depraz
+ * SIGGRAPH 2007
+ * 
+ * Reeb graph generation algorithm based on: 
+ * "Robust On-line Computation of Reeb Graphs: Simplicity and Speed"
+ * Valerio Pascucci, Giorgio Scorzelli, Peer-Timo Bremer and Ajith Mascarenhas
+ * SIGGRAPH 2007
+ * 
+ * */
+#define DEBUG_REEB
+#define DEBUG_REEB_NODE
+
+typedef struct VertexData
+{
+       float w; /* weight */
+       int i; /* index */
+       ReebNode *n;
+} VertexData;
+
+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(EdgeIndex *indexed_edges, int index);
+void mergeArcFaces(ReebGraph *rg, ReebArc *aDst, ReebArc *aSrc);
+void addFacetoArc(ReebArc *arc, EditFace *efa);
+
+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 flipArcBuckets(ReebArc *arc);
+
+
+/***************************************** UTILS **********************************************/
+
+VertexData *allocVertexData(EditMesh *em)
+{
+       VertexData *data;
+       EditVert *eve;
+       int totvert, index;
+       
+       totvert = BLI_countlist(&em->verts);
+       
+       data = MEM_callocN(sizeof(VertexData) * totvert, "VertexData");
+
+       for(index = 0, eve = em->verts.first; eve; index++, eve = eve->next)
+       {
+               data[index].i = index;
+               data[index].w = 0;
+               eve->tmp.p = data + index;
+       }
+               
+       return data;
+}
+
+int indexData(EditVert *eve)
+{
+       return ((VertexData*)eve->tmp.p)->i;
+}
+
+float weightData(EditVert *eve)
+{
+       return ((VertexData*)eve->tmp.p)->w;
+}
+
+void weightSetData(EditVert *eve, float w)
+{
+       ((VertexData*)eve->tmp.p)->w = w;
+}
+
+ReebNode* nodeData(EditVert *eve)
+{
+       return ((VertexData*)eve->tmp.p)->n;
+}
+
+void nodeSetData(EditVert *eve, ReebNode *n)
+{
+       ((VertexData*)eve->tmp.p)->n = n;
+}
+
+void REEB_freeArc(BArc *barc)
+{
+       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 REEB_freeGraph(ReebGraph *rg)
+{
+       ReebArc *arc;
+       ReebNode *node;
+       
+       // free nodes
+       for( node = rg->nodes.first; node; node = node->next )
+       {
+               BLI_freeNode((BGraph*)rg, (BNode*)node);
+       }
+       BLI_freelistN(&rg->nodes);
+       
+       // free arcs
+       arc = rg->arcs.first;
+       while( arc )
+       {
+               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);
+}
+
+ReebGraph * newReebGraph()
+{
+       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;
+}
+
+void BIF_flagMultiArcs(ReebGraph *rg, int flag)
+{
+       for ( ; rg; rg = rg->link_up)
+       {
+               BLI_flagArcs((BGraph*)rg, flag);
+       }
+}
+
+ReebNode * addNode(ReebGraph *rg, EditVert *eve)
+{
+       float weight;
+       ReebNode *node = NULL;
+       
+       weight = weightData(eve);
+       
+       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++;
+       
+       nodeSetData(eve, node);
+       
+       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)
+       {
+               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)
+               {
+                       if (low_node->index == high_node->index)
+                       {
+                               high_node->link_down = low_node;
+                               low_node->link_up = high_node;
+                               break;
+                       }
+               }
+       }
+}
+
+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)
+       {
+               node = node->link_down;
+       }
+       
+       return node;
+}
+
+ReebArc * copyArc(ReebGraph *rg, ReebArc *arc)
+{
+       ReebArc *cp_arc;
+       ReebNode *node;
+       
+       cp_arc = MEM_callocN(sizeof(ReebArc), "reeb arc copy");
+
+       memcpy(cp_arc, arc, sizeof(ReebArc));
+       
+       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)
+       {
+               if (node->index == arc->head->index)
+               {
+                       cp_arc->head = node;
+               }
+               else if (node->index == arc->tail->index)
+               {
+                       cp_arc->tail = node;
+               }
+       }
+       
+       BLI_addtail(&rg->arcs, cp_arc);
+       
+       return cp_arc;
+}
+
+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)
+       {
+               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;
+}
+
+ReebEdge * copyEdge(ReebEdge *edge)
+{
+       ReebEdge *newEdge = NULL;
+       
+       newEdge = MEM_callocN(sizeof(ReebEdge), "reeb edge");
+       memcpy(newEdge, edge, sizeof(ReebEdge));
+       
+       newEdge->next = NULL;
+       newEdge->prev = NULL;
+       
+       return newEdge;
+}
+
+void printArc(ReebArc *arc)
+{
+       ReebEdge *edge;
+       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)
+       {
+               printf("\tedge (%i, %i)\n", edge->v1->index, edge->v2->index);
+       }
+}
+
+void flipArc(ReebArc *arc)
+{
+       ReebNode *tmp;
+       tmp = arc->head;
+       arc->head = arc->tail;
+       arc->tail = tmp;
+       
+       flipArcBuckets(arc);
+}
+
+#ifdef DEBUG_REEB_NODE
+void NodeDegreeDecrement(ReebGraph *rg, ReebNode *node)
+{
+       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)
+{
+       BArc *arc = NULL;
+       BNode *node = NULL;
+       
+       // Reset node positions
+       for(node = rg->nodes.first; node; node = node->next)
+       {
+               node->p[0] = node->p[1] = node->p[2] = 0;
+       }
+       
+       for(arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               if (((ReebArc*)arc)->bcount > 0)
+               {
+                       float p[3];
+                       
+                       VECCOPY(p, ((ReebArc*)arc)->buckets[0].p);
+                       VecMulf(p, 1.0f / arc->head->degree);
+                       VecAddf(arc->head->p, arc->head->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;
+
+       for(node = rg->nodes.first; node; node = node->next)
+       {
+               int count = 0;
+               for(arc = rg->arcs.first; arc; arc = arc->next)
+               {
+                       if (arc->head == node || arc->tail == node)
+                       {
+                               count++;
+                       }
+               }
+               if (count != node->degree)
+               {
+                       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 verifyBucketsArc(ReebGraph *rg, ReebArc *arc)
+{
+       ReebNode *head = (ReebNode*)arc->head;
+       ReebNode *tail = (ReebNode*)arc->tail;
+
+       if (arc->bcount > 0)
+       {
+               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(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));
+               }
+       }
+}
+
+void verifyBuckets(ReebGraph *rg)
+{
+#ifdef DEBUG_REEB
+       ReebArc *arc = NULL;
+       for(arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               verifyBucketsArc(rg, arc);
+       }
+#endif
+}
+
+void verifyFaces(ReebGraph *rg)
+{
+#ifdef DEBUG_REEB
+       int total = 0;
+       ReebArc *arc = NULL;
+       for(arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               total += BLI_ghash_size(arc->faces);
+       }
+       
+#endif
+}
+
+void verifyArcs(ReebGraph *rg)
+{
+       ReebArc *arc;
+       
+       for (arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               if (arc->head->weight > arc->tail->weight)
+               {
+                       printf("FLIPPED ARC!\n");
+               }
+       }
+}
+
+void verifyMultiResolutionLinks(ReebGraph *rg, int level)
+{
+#ifdef DEBUG_REEB
+       ReebGraph *lower_rg = rg->link_up;
+       
+       if (lower_rg)
+       {
+               ReebArc *arc;
+               
+               for (arc = rg->arcs.first; arc; arc = arc->next)
+               {
+                       if (BLI_findindex(&lower_rg->arcs, arc->link_up) == -1)
+                       {
+                               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);
+       }
+#endif
+}
+/***************************************** BUCKET UTILS **********************************************/
+
+void addVertToBucket(EmbedBucket *b, float co[3])
+{
+       b->nv++;
+       VecLerpf(b->p, b->p, co, 1.0f / b->nv);
+}
+
+void removeVertFromBucket(EmbedBucket *b, float co[3])
+{
+       VecMulf(b->p, (float)b->nv);
+       VecSubf(b->p, b->p, co);
+       b->nv--;
+       VecMulf(b->p, 1.0f / (float)b->nv);
+}
+
+void mergeBuckets(EmbedBucket *bDst, EmbedBucket *bSrc)
+{
+       if (bDst->nv > 0 && bSrc->nv > 0)
+       {
+               bDst->nv += bSrc->nv;
+               VecLerpf(bDst->p, bDst->p, bSrc->p, (float)bSrc->nv / (float)(bDst->nv));
+       }
+       else if (bSrc->nv > 0)
+       {
+               bDst->nv = bSrc->nv;
+               VECCOPY(bDst->p, bSrc->p);
+       }
+}
+
+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)
+               {
+                       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);
+               }
+       }
+}
+
+void flipArcBuckets(ReebArc *arc)
+{
+       int i, j;
+       
+       for (i = 0, j = arc->bcount - 1; i < j; i++, j--)
+       {
+               EmbedBucket tmp;
+               
+               tmp = arc->buckets[i];
+               arc->buckets[i] = arc->buckets[j];
+               arc->buckets[j] = tmp;
+       }
+}
+
+int countArcBuckets(ReebArc *arc)
+{
+       return (int)(floor(arc->tail->weight) - ceil(arc->head->weight)) + 1;
+}
+
+void allocArcBuckets(ReebArc *arc)
+{
+       int i;
+       float start = ceil(arc->head->weight);
+       arc->bcount = countArcBuckets(arc);
+       
+       if (arc->bcount > 0)
+       {
+               arc->buckets = MEM_callocN(sizeof(EmbedBucket) * arc->bcount, "embed bucket");
+               
+               for(i = 0; i < arc->bcount; i++)
+               {
+                       arc->buckets[i].val = start + i;
+               }
+       }
+       else
+       {
+               arc->buckets = NULL;
+       }
+       
+}
+
+void resizeArcBuckets(ReebArc *arc)
+{
+       EmbedBucket *oldBuckets = arc->buckets;
+       int oldBCount = arc->bcount;
+       
+       if (countArcBuckets(arc) == oldBCount)
+       {
+               return;
+       }
+       
+       allocArcBuckets(arc);
+       
+       if (oldBCount != 0 && arc->bcount != 0)
+       {
+               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)); 
+       }
+
+       if (oldBuckets != NULL)
+       {
+               MEM_freeN(oldBuckets);
+       }
+}
+
+void reweightBuckets(ReebArc *arc)
+{
+       int i;
+       float start = ceil((arc->head)->weight);
+       
+       if (arc->bcount > 0)
+       {
+               for(i = 0; i < arc->bcount; i++)
+               {
+                       arc->buckets[i].val = start + i;
+               }
+       }
+}
+
+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++)
+       {
+               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 = 0, end_index = 0;
+       int missing = 0;
+       int i;
+       
+       start_p = arc->head->p;
+       
+       for(i = 0; i < arc->bcount; i++)
+       {
+               EmbedBucket *bucket = arc->buckets + i;
+               
+               if (missing)
+               {
+                       if (bucket->nv > 0)
+                       {
+                               missing = 0;
+                               
+                               end_p = bucket->p;
+                               end_index = i - 1;
+                               
+                               interpolateBuckets(arc, start_p, end_p, start_index, end_index);
+                       }
+               }
+               else
+               {
+                       if (bucket->nv == 0)
+                       {
+                               missing = 1;
+                               
+                               if (i > 0)
+                               {
+                                       start_p = arc->buckets[i - 1].p;
+                               }
+                               start_index = i;
+                       }
+               }
+       }
+       
+       if (missing)
+       {
+               end_p = arc->tail->p;
+               end_index = arc->bcount - 1;
+               
+               interpolateBuckets(arc, start_p, end_p, start_index, end_index);
+       }
+}
+
+static void ExtendArcBuckets(ReebArc *arc)
+{
+       ReebArcIterator arc_iter;
+       BArcIterator *iter = (BArcIterator*)&arc_iter;
+       EmbedBucket *last_bucket, *first_bucket;
+       float *previous = NULL;
+       float average_length = 0, length;
+       int padding_head = 0, padding_tail = 0;
+       
+       if (arc->bcount == 0)
+       {
+               return; /* failsafe, shouldn't happen */
+       }
+       
+       initArcIterator(iter, arc, arc->head);
+       IT_next(iter);
+       previous = iter->p;
+       
+       for (   IT_next(iter);
+                       IT_stopped(iter) == 0;
+                       previous = iter->p, IT_next(iter)
+               )
+       {
+               average_length += VecLenf(previous, iter->p);
+       }
+       average_length /= (arc->bcount - 1);
+       
+       first_bucket = arc->buckets;
+       last_bucket = arc->buckets + (arc->bcount - 1);
+       
+       length = VecLenf(first_bucket->p, arc->head->p);
+       if (length > 2 * average_length)
+       {
+               padding_head = (int)floor(length / average_length);
+       }
+
+       length = VecLenf(last_bucket->p, arc->tail->p);
+       if (length > 2 * average_length)
+       {
+               padding_tail = (int)floor(length / average_length);
+       }
+       
+       if (padding_head + padding_tail > 0)
+       {
+               EmbedBucket *old_buckets = arc->buckets;
+               
+               arc->buckets = MEM_callocN(sizeof(EmbedBucket) * (padding_head + arc->bcount + padding_tail), "embed bucket");
+               memcpy(arc->buckets + padding_head, old_buckets, arc->bcount * sizeof(EmbedBucket));
+               
+               arc->bcount = padding_head + arc->bcount + padding_tail;
+               
+               MEM_freeN(old_buckets);
+       }
+       
+       if (padding_head > 0)
+       {
+               interpolateBuckets(arc, arc->head->p, first_bucket->p, 0, padding_head);
+       }
+       
+       if (padding_tail > 0)
+       {
+               interpolateBuckets(arc, last_bucket->p, arc->tail->p, arc->bcount - padding_tail, arc->bcount - 1);
+       }
+}
+
+/* CALL THIS ONLY AFTER FILTERING, SINCE IT MESSES UP WEIGHT DISTRIBUTION */
+void extendGraphBuckets(ReebGraph *rg)
+{
+       ReebArc *arc;
+       
+       for (arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               ExtendArcBuckets(arc);
+       }
+}
+
+/**************************************** LENGTH CALCULATIONS ****************************************/
+
+void calculateArcLength(ReebArc *arc)
+{
+       ReebArcIterator arc_iter;
+       BArcIterator *iter = (BArcIterator*)&arc_iter;
+       float *vec0, *vec1;
+
+       arc->length = 0;
+       
+       initArcIterator(iter, arc, arc->head);
+
+       vec0 = arc->head->p;
+       vec1 = arc->head->p; /* in case there's no embedding */
+
+       while (IT_next(iter))   
+       {
+               vec1 = iter->p;
+               
+               arc->length += VecLenf(vec0, vec1);
+               
+               vec0 = vec1;
+       }
+       
+       arc->length += VecLenf(arc->tail->p, vec1);     
+}
+
+void calculateGraphLength(ReebGraph *rg)
+{
+       ReebArc *arc;
+       
+       for (arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               calculateArcLength(arc);
+       }
+}
+
+/**************************************** SYMMETRY HANDLING ******************************************/
+
+void REEB_RadialSymmetry(BNode* root_node, RadialArc* ring, int count)
+{
+       ReebNode *node = (ReebNode*)root_node;
+       float axis[3];
+       int i;
+       
+       VECCOPY(axis, root_node->symmetry_axis);
+       
+       /* first pass, merge incrementally */
+       for (i = 0; i < count - 1; i++)
+       {
+               ReebNode *node1, *node2;
+               ReebArc *arc1, *arc2;
+               float tangent[3];
+               float normal[3];
+               int j = i + 1;
+
+               VecAddf(tangent, ring[i].n, ring[j].n);
+               Crossf(normal, tangent, axis);
+               
+               node1 = (ReebNode*)BLI_otherNode(ring[i].arc, root_node);
+               node2 = (ReebNode*)BLI_otherNode(ring[j].arc, root_node);
+               
+               arc1 = (ReebArc*)ring[i].arc;
+               arc2 = (ReebArc*)ring[j].arc;
+
+               /* mirror first node and mix with the second */
+               BLI_mirrorAlongAxis(node1->p, root_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 (arc1->bcount > 0 && arc2->bcount > 0)
+               {
+                       ReebArcIterator arc_iter1, arc_iter2;
+                       BArcIterator *iter1 = (BArcIterator*)&arc_iter1;
+                       BArcIterator *iter2 = (BArcIterator*)&arc_iter2;
+                       EmbedBucket *bucket1 = NULL, *bucket2 = NULL;
+                       
+                       initArcIterator(iter1, arc1, (ReebNode*)root_node);
+                       initArcIterator(iter2, arc2, (ReebNode*)root_node);
+                       
+                       bucket1 = IT_next(iter1);
+                       bucket2 = IT_next(iter2);
+               
+                       /* Make sure they both start at the same value */       
+                       while(bucket1 && bucket2 && bucket1->val < bucket2->val)
+                       {
+                               bucket1 = IT_next(iter1);
+                       }
+                       
+                       while(bucket1 && bucket2 && bucket2->val < bucket1->val)
+                       {
+               &n