merge 16951:17122
authorMartin Poirier <theeth@yahoo.com>
Mon, 20 Oct 2008 00:48:10 +0000 (00:48 +0000)
committerMartin Poirier <theeth@yahoo.com>
Mon, 20 Oct 2008 00:48:10 +0000 (00:48 +0000)
30 files changed:
intern/bmfont/intern/BDF2BMF.py [deleted file]
release/scripts/reeb.py [new file with mode: 0644]
source/blender/blenkernel/intern/bvhutils.c
source/blender/blenkernel/intern/scene.c
source/blender/blenlib/BLI_arithb.h
source/blender/blenlib/BLI_ghash.h
source/blender/blenlib/BLI_graph.h [new file with mode: 0644]
source/blender/blenlib/BLI_threads.h
source/blender/blenlib/intern/BLI_ghash.c
source/blender/blenlib/intern/arithb.c
source/blender/blenlib/intern/graph.c [new file with mode: 0644]
source/blender/blenlib/intern/threads.c
source/blender/blenloader/intern/readfile.c
source/blender/include/BIF_editarmature.h
source/blender/include/butspace.h
source/blender/include/reeb.h
source/blender/makesdna/DNA_scene_types.h
source/blender/src/autoarmature.c [new file with mode: 0644]
source/blender/src/buttons_editing.c
source/blender/src/drawview.c
source/blender/src/editarmature.c
source/blender/src/reeb.c
source/blender/src/usiblender.c
source/gameengine/Converter/BL_ShapeActionActuator.h
source/gameengine/Converter/BL_ShapeDeformer.cpp
source/gameengine/Converter/BL_ShapeDeformer.h
source/gameengine/GameLogic/SCA_ActuatorEventManager.cpp
source/gameengine/GameLogic/SCA_ActuatorEventManager.h
source/gameengine/GameLogic/SCA_ActuatorSensor.cpp
source/gameengine/GameLogic/SCA_ActuatorSensor.h

diff --git a/intern/bmfont/intern/BDF2BMF.py b/intern/bmfont/intern/BDF2BMF.py
deleted file mode 100644 (file)
index 15b9e5b..0000000
+++ /dev/null
@@ -1,177 +0,0 @@
-#!/usr/bin/python
-
-# ***** 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 LICENCE BLOCK *****
-# --------------------------------------------------------------------------
-
-HELP_TXT = \
-'''
-Convert BDF pixmap fonts into C++ files Blender can read.
-Use to replace bitmap fonts or add new ones.
-
-Usage
-       python bdf2bmf.py -name=SomeName myfile.bdf
-
-Blender currently supports fonts with a maximum width of 8 pixels.
-'''
-
-# -------- Simple BDF parser
-import sys
-def parse_bdf(f, MAX_CHARS=256):
-       lines = [l.strip().upper().split() for l in f.readlines()]
-
-       is_bitmap = False
-       dummy = {'BITMAP':[]}
-       char_data = [dummy.copy() for i in xrange(MAX_CHARS)]
-       context_bitmap = []
-
-       for l in lines:
-               if l[0]=='ENCODING':            enc = int(l[1])
-               elif l[0]=='BBX':                       bbx = [int(c) for c in l[1:]]
-               elif l[0]=='DWIDTH':            dwidth = int(l[1])
-               elif l[0]=='BITMAP':            is_bitmap = True
-               elif l[0]=='ENDCHAR':
-                       if enc < MAX_CHARS:
-                               char_data[enc]['BBX'] = bbx
-                               char_data[enc]['DWIDTH'] = dwidth
-                               char_data[enc]['BITMAP'] = context_bitmap
-                               
-                       context_bitmap = []
-                       enc = bbx = None
-                       is_bitmap = False
-               else:
-                       # None of the above, Ok, were reading a bitmap
-                       if is_bitmap and enc < MAX_CHARS:
-                               context_bitmap.append( int(l[0], 16) )
-       
-       return char_data
-# -------- end simple BDF parser
-
-def bdf2cpp_name(path):
-       return path.split('.')[0] + '.cpp'
-
-def convert_to_blender(bdf_dict, font_name, origfilename, MAX_CHARS=256):
-       
-       # first get a global width/height, also set the offsets
-       xmin = ymin =  10000000
-       xmax = ymax = -10000000
-       
-       bitmap_offsets = [-1] * MAX_CHARS
-       bitmap_tot = 0
-       for i, c in enumerate(bdf_dict):
-               if c.has_key('BBX'):
-                       bbx = c['BBX']
-                       xmax = max(bbx[0], xmax)
-                       ymax = max(bbx[1], ymax)
-                       xmin = min(bbx[2], xmin)
-                       ymin = min(bbx[3], ymin)
-                       
-                       bitmap_offsets[i] = bitmap_tot
-                       bitmap_tot += len(c['BITMAP'])
-               
-               c['BITMAP'].reverse()
-       
-       # Now we can write. Ok if we have no .'s in the path.
-       f = open(bdf2cpp_name(origfilename), 'w')
-       
-       f.write('''
-#ifdef HAVE_CONFIG_H
-#include <config.h>
-#endif
-
-#include "BMF_FontData.h"
-
-#include "BMF_Settings.h"
-''')
-       
-       f.write('#if BMF_INCLUDE_%s\n\n' % font_name.upper())
-       f.write('static unsigned char bitmap_data[]= {')
-       newline = 8
-       
-       for i, c in enumerate(bdf_dict):
-       
-               for cdata in c['BITMAP']:
-                       # Just formatting
-                       newline+=1
-                       if newline >= 8:
-                               newline = 0
-                               f.write('\n\t')
-                       # End formatting
-                       
-                       f.write('0x%.2hx,' % cdata) # 0x80 <- format
-                       
-       f.write("\n};\n")
-       
-       f.write("BMF_FontData BMF_font_%s = {\n" % font_name)
-       f.write('\t%d, %d,\n' % (xmin, ymin))
-       f.write('\t%d, %d,\n' % (xmax, ymax))
-       
-       f.write('\t{\n')
-       
-
-       for i, c in enumerate(bdf_dict):
-               if bitmap_offsets[i] == -1 or c.has_key('BBX') == False:
-                       f.write('\t\t{0,0,0,0,0, -1},\n')
-               else:
-                       bbx = c['BBX']
-                       f.write('\t\t{%d,%d,%d,%d,%d, %d},\n' % (bbx[0], bbx[1], -bbx[2], -bbx[3], c['DWIDTH'], bitmap_offsets[i]))
-       
-       f.write('''
-       },
-       bitmap_data
-};
-
-#endif
-''')
-
-def main():
-       # replace "[-name=foo]" with  "[-name] [foo]"
-       args = []
-       for arg in sys.argv:
-               for a in arg.replace('=', ' ').split():
-                       args.append(a)
-       
-       name = 'untitled'
-       done_anything = False
-       for i, arg in enumerate(args):
-               if arg == '-name':
-                       if i==len(args)-1:
-                               print 'no arg given for -name, aborting'
-                               return
-                       else:
-                               name = args[i+1]
-               
-               elif arg.lower().endswith('.bdf'):
-                       try:
-                               f = open(arg)
-                               print '...Writing to:', bdf2cpp_name(arg)
-                       except:
-                               print 'could not open "%s", aborting' % arg
-                       
-                       
-                       bdf_dict = parse_bdf(f)
-                       convert_to_blender(bdf_dict, name, arg)
-                       done_anything = True
-       
-       if not done_anything:
-               print HELP_TXT
-               print '...nothing to do'
-
-if __name__ == '__main__':
-       main()
-       
diff --git a/release/scripts/reeb.py b/release/scripts/reeb.py
new file mode 100644 (file)
index 0000000..63ab120
--- /dev/null
@@ -0,0 +1,110 @@
+#!BPY
+"""
+Name: 'Reeb graph import'
+Blender: 245
+Group: 'Import'
+Tooltip: 'Imports a reeb graph saved after skeleton generation'
+"""
+import Blender
+
+def name(count):
+       if count == -1:
+               return ""
+       else:
+               return "%05" % count
+
+def importGraph(count):
+       bNode = Blender.Draw.Create(1)
+       bSize = Blender.Draw.Create(0.01)
+
+       Block = []
+       
+       Block.append(("Size: ", bSize, 0.01, 10.0, "Size of the nodes"))
+       Block.append(("Nodes", bNode, "Import nodes as tetras"))
+       
+       retval = Blender.Draw.PupBlock("Reeb Graph Import", Block)
+       
+       if not retval:
+               return
+
+
+       me = Blender.Mesh.New("graph%s" % name(count))
+       scn = Blender.Scene.GetCurrent()
+       
+       f = open("test%s.txt" % name(count), "r")
+       
+       verts = []
+       edges = []
+       faces = []
+       
+       i = 0
+       first = False
+       
+       SIZE = float(bSize.val)
+       WITH_NODE = bool(bNode.val)
+       
+       def addNode(v, s, verts, faces):
+               if WITH_NODE:
+                       v1 = [v[0], v[1], v[2] + s]
+                       i1 = len(verts)
+                       verts.append(v1)
+                       v2 = [v[0], v[1] + 0.959 * s, v[2] - 0.283 * s]
+                       i2 = len(verts)
+                       verts.append(v2)
+                       v3 = [v[0] - 0.830 * s, v[1] - 0.479 * s, v[2] - 0.283 * s]
+                       i3 = len(verts)
+                       verts.append(v3)
+                       v4 = [v[0] + 0.830 * s, v[1] - 0.479 * s, v[2] - 0.283 * s]
+                       i4 = len(verts)
+                       verts.append(v4)
+                       
+                       faces.append([i1,i2,i3])
+                       faces.append([i1,i3,i4])
+                       faces.append([i2,i3,i4])
+                       faces.append([i1,i2,i4])
+                       
+                       return 4
+               else:
+                       return 0
+               
+       for line in f:
+               data = line.strip().split(" ")
+               if data[0] == "v1":
+                       v = [float(x) for x in data[-3:]]
+                       i += addNode(v, SIZE, verts, faces)
+                       verts.append(v)
+                       i += 1
+               elif data[0] == "v2":
+                       pass
+                       v = [float(x) for x in data[-3:]]
+                       verts.append(v)
+                       edges.append((i-1, i))
+                       i += 1
+                       i += addNode(v, SIZE, verts, faces)
+               elif data[0] == "b":
+                       verts.append([float(x) for x in data[-3:]])
+                       edges.append((i-1, i))
+                       i += 1
+#              elif data[0] == "angle":
+#                      obj = scn.objects.new('Empty')
+#                      obj.loc = (float(data[1]), float(data[2]), float(data[3]))
+#                      obj.properties["angle"] = data[4]
+#                      del obj
+                        
+                        
+       me.verts.extend(verts)
+       me.edges.extend(edges)
+       me.faces.extend(faces)
+       
+       
+       ob = scn.objects.new(me, "graph%s" % name(count))
+       del ob
+       del scn
+       
+
+#for i in range(16):
+#      importGraph(i)
+
+if __name__=='__main__':
+       importGraph(-1)
index ae449843d2a7f668660e46a2e1ee07c48cf59099..5b68a637ea2645b13511feb5b55a4cf52e807f12 100644 (file)
 
 /* Math stuff for ray casting on mesh faces and for nearest surface */
 
+static float nearest_point_in_tri_surface(const float *point, const float *v0, const float *v1, const float *v2, float *nearest);
+
+#define ISECT_EPSILON 1e-6
 static float ray_tri_intersection(const BVHTreeRay *ray, const float m_dist, const float *v0, const float *v1, const float *v2)
 {
        float dist;
 
-       if(RayIntersectsTriangle((float*)ray->origin, (float*)ray->direction, (float*)v0, (float*)v1, (float*)v2, &dist, NULL))
+       if(RayIntersectsTriangle(ray->origin, ray->direction, v0, v1, v2, &dist, NULL))
                return dist;
 
        return FLT_MAX;
@@ -68,7 +71,7 @@ static float sphereray_tri_intersection(const BVHTreeRay *ray, float radius, con
        CalcNormFloat((float*)v0, (float*)v1, (float*)v2, plane_normal);
 
        VECADDFAC( p1, ray->origin, ray->direction, m_dist);
-       if(SweepingSphereIntersectsTriangleUV((float*)ray->origin, p1, radius, (float*)v0, (float*)v1, (float*)v2, &idist, hit_point))
+       if(SweepingSphereIntersectsTriangleUV(ray->origin, p1, radius, v0, v1, v2, &idist, &hit_point))
        {
                return idist * m_dist;
        }
@@ -76,324 +79,170 @@ static float sphereray_tri_intersection(const BVHTreeRay *ray, float radius, con
        return FLT_MAX;
 }
 
-
 /*
- * Function adapted from David Eberly's distance tools (LGPL)
- * http://www.geometrictools.com/LibFoundation/Distance/Distance.html
+ * This calculates the distance from point to the plane
+ * Distance is negative if point is on the back side of plane
  */
-static float nearest_point_in_tri_surface(const float *v0,const float *v1,const float *v2,const float *p, int *v, int *e, float *nearest )
+static float point_plane_distance(const float *point, const float *plane_point, const float *plane_normal)
 {
-       float diff[3];
-       float e0[3];
-       float e1[3];
-       float A00;
-       float A01;
-       float A11;
-       float B0;
-       float B1;
-       float C;
-       float Det;
-       float S;
-       float T;
-       float sqrDist;
-       int lv = -1, le = -1;
-       
-       VECSUB(diff, v0, p);
-       VECSUB(e0, v1, v0);
-       VECSUB(e1, v2, v0);
-       
-       A00 = INPR ( e0, e0 );
-       A01 = INPR( e0, e1 );
-       A11 = INPR ( e1, e1 );
-       B0 = INPR( diff, e0 );
-       B1 = INPR( diff, e1 );
-       C = INPR( diff, diff );
-       Det = fabs( A00 * A11 - A01 * A01 );
-       S = A01 * B1 - A11 * B0;
-       T = A01 * B0 - A00 * B1;
-
-       if ( S + T <= Det )
+       float pp[3];
+       VECSUB(pp, point, plane_point);
+       return INPR(pp, plane_normal);
+}
+static float choose_nearest(const float v0[2], const float v1[2], const float point[2], float closest[2])
+{
+       float d[2][2], sdist[2];
+       VECSUB2D(d[0], v0, point);
+       VECSUB2D(d[1], v1, point);
+
+       sdist[0] = d[0][0]*d[0][0] + d[0][1]*d[0][1];
+       sdist[1] = d[1][0]*d[1][0] + d[1][1]*d[1][1];
+
+       if(sdist[0] < sdist[1])
        {
-               if ( S < 0.0f )
-               {
-                       if ( T < 0.0f )  // Region 4
-                       {
-                               if ( B0 < 0.0f )
-                               {
-                                       T = 0.0f;
-                                       if ( -B0 >= A00 )
-                                       {
-                                               S = (float)1.0;
-                                               sqrDist = A00 + 2.0f * B0 + C;
-                                               lv = 1;
-                                       }
-                                       else
-                                       {
-                                               if(fabs(A00) > FLT_EPSILON)
-                                                       S = -B0/A00;
-                                               else
-                                                       S = 0.0f;
-                                               sqrDist = B0 * S + C;
-                                               le = 0;
-                                       }
-                               }
-                               else
-                               {
-                                       S = 0.0f;
-                                       if ( B1 >= 0.0f )
-                                       {
-                                               T = 0.0f;
-                                               sqrDist = C;
-                                               lv = 0;
-                                       }
-                                       else if ( -B1 >= A11 )
-                                       {
-                                               T = 1.0f;
-                                               sqrDist = A11 + 2.0f * B1 + C;
-                                               lv = 2;
-                                       }
-                                       else
-                                       {
-                                               if(fabs(A11) > FLT_EPSILON)
-                                                       T = -B1 / A11;
-                                               else
-                                                       T = 0.0f;
-                                               sqrDist = B1 * T + C;
-                                               le = 1;
-                                       }
-                               }
-                       }
-                       else  // Region 3
-                       {
-                               S = 0.0f;
-                               if ( B1 >= 0.0f )
-                               {
-                                       T = 0.0f;
-                                       sqrDist = C;
-                                       lv = 0;
-                               }
-                               else if ( -B1 >= A11 )
-                               {
-                                       T = 1.0f;
-                                       sqrDist = A11 + 2.0f * B1 + C;
-                                       lv = 2;
-                               }
-                               else
-                               {
-                                       if(fabs(A11) > FLT_EPSILON)
-                                               T = -B1 / A11;
-                                       else
-                                               T = 0.0;
-                                       sqrDist = B1 * T + C;
-                                       le = 1;
-                               }
-                       }
-               }
-               else if ( T < 0.0f )  // Region 5
-               {
-                       T = 0.0f;
-                       if ( B0 >= 0.0f )
-                       {
-                               S = 0.0f;
-                               sqrDist = C;
-                               lv = 0;
-                       }
-                       else if ( -B0 >= A00 )
-                       {
-                               S = 1.0f;
-                               sqrDist = A00 + 2.0f * B0 + C;
-                               lv = 1;
-                       }
-                       else
-                       {
-                               if(fabs(A00) > FLT_EPSILON)
-                                       S = -B0 / A00;
-                               else
-                                       S = 0.0f;
-                               sqrDist = B0 * S + C;
-                               le = 0;
-                       }
-               }
-               else  // Region 0
-               {
-            // Minimum at interior lv
-                       float invDet;
-                       if(fabs(Det) > FLT_EPSILON)
-                               invDet = 1.0f / Det;
-                       else
-                               invDet = 0.0f;
-                       S *= invDet;
-                       T *= invDet;
-                       sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0) +
-                                       T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
-               }
+               if(closest)
+                       VECCOPY2D(closest, v0);
+               return sdist[0];
        }
        else
        {
-               float tmp0, tmp1, numer, denom;
+               if(closest)
+                       VECCOPY2D(closest, v1);
+               return sdist[1];
+       }
+}
+/*
+ * calculates the closest point between point-tri (2D)
+ * returns that tri must be right-handed
+ * Returns square distance
+ */
+static float closest_point_in_tri2D(const float point[2], /*const*/ float tri[3][2], float closest[2])
+{
+       float edge_di[2];
+       float v_point[2];
+       float proj[2];                                  //point projected over edge-dir, edge-normal (witouth normalized edge)
+       const float *v0 = tri[2], *v1;
+       float edge_slen, d;                             //edge squared length
+       int i;
+       const float *nearest_vertex = NULL;
 
-               if ( S < 0.0f )  // Region 2
-               {
-                       tmp0 = A01 + B0;
-                       tmp1 = A11 + B1;
-                       if ( tmp1 > tmp0 )
-                       {
-                               numer = tmp1 - tmp0;
-                               denom = A00 - 2.0f * A01 + A11;
-                               if ( numer >= denom )
-                               {
-                                       S = 1.0f;
-                                       T = 0.0f;
-                                       sqrDist = A00 + 2.0f * B0 + C;
-                                       lv = 1;
-                               }
-                               else
-                               {
-                                       if(fabs(denom) > FLT_EPSILON)
-                                               S = numer / denom;
-                                       else
-                                               S = 0.0f;
-                                       T = 1.0f - S;
-                                       sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) +
-                                                       T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
-                                       le = 2;
-                               }
-                       }
-                       else
-                       {
-                               S = 0.0f;
-                               if ( tmp1 <= 0.0f )
-                               {
-                                       T = 1.0f;
-                                       sqrDist = A11 + 2.0f * B1 + C;
-                                       lv = 2;
-                               }
-                               else if ( B1 >= 0.0f )
-                               {
-                                       T = 0.0f;
-                                       sqrDist = C;
-                                       lv = 0;
-                               }
-                               else
-                               {
-                                       if(fabs(A11) > FLT_EPSILON)
-                                               T = -B1 / A11;
-                                       else
-                                               T = 0.0f;
-                                       sqrDist = B1 * T + C;
-                                       le = 1;
-                               }
-                       }
-               }
-               else if ( T < 0.0f )  // Region 6
+
+       //for each edge
+       for(i=0, v0=tri[2], v1=tri[0]; i < 3; v0=tri[i++], v1=tri[i])
+       {
+               VECSUB2D(edge_di,    v1, v0);
+               VECSUB2D(v_point, point, v0);
+
+               proj[1] =  v_point[0]*edge_di[1] - v_point[1]*edge_di[0];       //dot product with edge normal
+
+               //point inside this edge
+               if(proj[1] < 0)
+                       continue;
+
+               proj[0] = v_point[0]*edge_di[0] + v_point[1]*edge_di[1];
+
+               //closest to this edge is v0
+               if(proj[0] < 0)
                {
-                       tmp0 = A01 + B1;
-                       tmp1 = A00 + B0;
-                       if ( tmp1 > tmp0 )
-                       {
-                               numer = tmp1 - tmp0;
-                               denom = A00 - 2.0f * A01 + A11;
-                               if ( numer >= denom )
-                               {
-                                       T = 1.0f;
-                                       S = 0.0f;
-                                       sqrDist = A11 + 2.0f * B1 + C;
-                                       lv = 2;
-                               }
-                               else
-                               {
-                                       if(fabs(denom) > FLT_EPSILON)
-                                               T = numer / denom;
-                                       else
-                                               T = 0.0f;
-                                       S = 1.0f - T;
-                                       sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) +
-                                                       T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
-                                       le = 2;
-                               }
-                       }
+                       if(nearest_vertex == NULL || nearest_vertex == v0)
+                               nearest_vertex = v0;
                        else
                        {
-                               T = 0.0f;
-                               if ( tmp1 <= 0.0f )
-                               {
-                                       S = 1.0f;
-                                       sqrDist = A00 + 2.0f * B0 + C;
-                                       lv = 1;
-                               }
-                               else if ( B0 >= 0.0f )
-                               {
-                                       S = 0.0f;
-                                       sqrDist = C;
-                                       lv = 0;
-                               }
-                               else
-                               {
-                                       if(fabs(A00) > FLT_EPSILON)
-                                               S = -B0 / A00;
-                                       else
-                                               S = 0.0f;
-                                       sqrDist = B0 * S + C;
-                                       le = 0;
-                               }
+                               //choose nearest
+                               return choose_nearest(nearest_vertex, v0, point, closest);
                        }
+                       i++;    //We can skip next edge
+                       continue;
                }
-               else  // Region 1
+
+               edge_slen = edge_di[0]*edge_di[0] + edge_di[1]*edge_di[1];      //squared edge len
+               //closest to this edge is v1
+               if(proj[0] > edge_slen)
                {
-                       numer = A11 + B1 - A01 - B0;
-                       if ( numer <= 0.0f )
-                       {
-                               S = 0.0f;
-                               T = 1.0f;
-                               sqrDist = A11 + 2.0f * B1 + C;
-                               lv = 2;
-                       }
+                       if(nearest_vertex == NULL || nearest_vertex == v1)
+                               nearest_vertex = v1;
                        else
                        {
-                               denom = A00 - 2.0f * A01 + A11;
-                               if ( numer >= denom )
-                               {
-                                       S = 1.0f;
-                                       T = 0.0f;
-                                       sqrDist = A00 + 2.0f * B0 + C;
-                                       lv = 1;
-                               }
-                               else
-                               {
-                                       if(fabs(denom) > FLT_EPSILON)
-                                               S = numer / denom;
-                                       else
-                                               S = 0.0f;
-                                       T = 1.0f - S;
-                                       sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) +
-                                                       T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
-                                       le = 2;
-                               }
+                               return choose_nearest(nearest_vertex, v1, point, closest);
                        }
+                       continue;
                }
+
+               //nearest is on this edge
+               d= proj[1] / edge_slen;
+               closest[0] = point[0] - edge_di[1] * d;
+               closest[1] = point[1] + edge_di[0] * d;
+
+               return proj[1]*proj[1]/edge_slen;
        }
 
-       // Account for numerical round-off error
-       if ( sqrDist < FLT_EPSILON )
-               sqrDist = 0.0f;
-       
+       if(nearest_vertex)
+       {
+               VECSUB2D(v_point, nearest_vertex, point);
+               VECCOPY2D(closest, nearest_vertex);
+               return v_point[0]*v_point[0] + v_point[1]*v_point[1];
+       }
+       else
+       {
+               VECCOPY(closest, point);        //point is already inside
+               return 0.0f;
+       }
+}
+
+/*
+ * Returns the square of the minimum distance between the point and a triangle surface
+ * If nearest is not NULL the nearest surface point is written on it
+ */
+static float nearest_point_in_tri_surface(const float *point, const float *v0, const float *v1, const float *v2, float *nearest)
+{
+       //Lets solve the 2D problem (closest point-tri)
+       float normal_dist, plane_sdist, plane_offset;
+       float du[3], dv[3], dw[3];      //orthogonal axis (du=(v0->v1), dw=plane normal)
+
+       float p_2d[2], tri_2d[3][2], nearest_2d[2];
+
+       CalcNormFloat((float*)v0, (float*)v1, (float*)v2, dw);
+
+       //point-plane distance and calculate axis
+       normal_dist = point_plane_distance(point, v0, dw);
+
+       // OPTIMIZATION
+       //      if we are only interested in nearest distance if its closer than some distance already found
+       //  we can:
+       //              if(normal_dist*normal_dist >= best_dist_so_far) return FLOAT_MAX;
+       //
+
+       VECSUB(du, v1, v0);
+       Normalize(du);
+       Crossf(dv, dw, du);
+       plane_offset = INPR(v0, dw);
+
+       //project stuff to 2d
+       tri_2d[0][0] = INPR(du, v0);
+       tri_2d[0][1] = INPR(dv, v0);
+
+       tri_2d[1][0] = INPR(du, v1);
+       tri_2d[1][1] = INPR(dv, v1);
+
+       tri_2d[2][0] = INPR(du, v2);
+       tri_2d[2][1] = INPR(dv, v2);
+
+       p_2d[0] = INPR(du, point);
+       p_2d[1] = INPR(dv, point);
+
+       //we always have a right-handed tri
+       //this should always happen because of the way normal is calculated
+       plane_sdist = closest_point_in_tri2D(p_2d, tri_2d, nearest_2d);
+
+       //project back to 3d
+       if(nearest)
        {
-               float w[3], x[3], y[3], z[3];
-               VECCOPY(w, v0);
-               VECCOPY(x, e0);
-               VecMulf(x, S);
-               VECCOPY(y, e1);
-               VecMulf(y, T);
-               VECADD(z, w, x);
-               VECADD(z, z, y);
-               //VECSUB(d, p, z);
-               VECCOPY(nearest, z);
-               // d = p - ( v0 + S * e0 + T * e1 );
+               nearest[0] = du[0]*nearest_2d[0] + dv[0] * nearest_2d[1] + dw[0] * plane_offset;
+               nearest[1] = du[1]*nearest_2d[0] + dv[1] * nearest_2d[1] + dw[1] * plane_offset;
+               nearest[2] = du[2]*nearest_2d[0] + dv[2] * nearest_2d[1] + dw[2] * plane_offset;
        }
-       *v = lv;
-       *e = le;
 
-       return sqrDist;
+       return plane_sdist + normal_dist*normal_dist;
 }
 
 
@@ -419,17 +268,17 @@ static void mesh_faces_nearest_point(void *userdata, int index, const float *co,
        do
        {       
                float nearest_tmp[3], dist;
-               int vertex, edge;
-               
-               dist = nearest_point_in_tri_surface(t0, t1, t2, co, &vertex, &edge, nearest_tmp);
+
+               dist = nearest_point_in_tri_surface(co,t0, t1, t2, nearest_tmp);
                if(dist < nearest->dist)
                {
                        nearest->index = index;
                        nearest->dist = dist;
                        VECCOPY(nearest->co, nearest_tmp);
-                       CalcNormFloat(t0, t1, t2, nearest->no);
+                       CalcNormFloat((float*)t0, (float*)t1, (float*)t2, nearest->no); //TODO.. (interpolate normals from the vertexs coordinates?
                }
 
+
                t1 = t2;
                t2 = t3;
                t3 = NULL;
@@ -547,7 +396,7 @@ void bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *mesh, float eps
                        VECCOPY(co[2], vert[ face[i].v3 ].co);
                        if(face[i].v4)
                                VECCOPY(co[3], vert[ face[i].v4 ].co);
-                       
+
                        BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
                }
                BLI_bvhtree_balance(tree);
index dea36a69643c4cafd8d45277434554304d7f2ebc..7d864c83d2cd904673624411db132833322a7ab5 100644 (file)
@@ -253,6 +253,21 @@ Scene *add_scene(char *name)
        sce->toolsettings->select_thresh= 0.01f;
        sce->toolsettings->jointrilimit = 0.8f;
 
+       sce->toolsettings->skgen_resolution = 100;
+       sce->toolsettings->skgen_threshold_internal     = 0.01f;
+       sce->toolsettings->skgen_threshold_external     = 0.01f;
+       sce->toolsettings->skgen_angle_limit                    = 45.0f;
+       sce->toolsettings->skgen_length_ratio                   = 1.3f;
+       sce->toolsettings->skgen_length_limit                   = 1.5f;
+       sce->toolsettings->skgen_correlation_limit              = 0.98f;
+       sce->toolsettings->skgen_symmetry_limit                 = 0.1f;
+       sce->toolsettings->skgen_postpro = SKGEN_SMOOTH;
+       sce->toolsettings->skgen_postpro_passes = 1;
+       sce->toolsettings->skgen_options = SKGEN_FILTER_INTERNAL|SKGEN_FILTER_EXTERNAL|SKGEN_FILTER_SMART|SKGEN_HARMONIC|SKGEN_SUB_CORRELATION|SKGEN_STICK_TO_EMBEDDING;
+       sce->toolsettings->skgen_subdivisions[0] = SKGEN_SUB_CORRELATION;
+       sce->toolsettings->skgen_subdivisions[1] = SKGEN_SUB_LENGTH;
+       sce->toolsettings->skgen_subdivisions[2] = SKGEN_SUB_ANGLE;
+
        pset= &sce->toolsettings->particle;
        pset->flag= PE_KEEP_LENGTHS|PE_LOCK_FIRST|PE_DEFLECT_EMITTER;
        pset->emitterdist= 0.25f;
index e2e71a2fb1a7e67cde095a0f5886eee2e2f78bd9..e4b983d9ba307f2bf78132d204e388b45762855b 100644 (file)
@@ -245,6 +245,7 @@ void VecMulf(float *v1, float f);
 int VecLenCompare(float *v1, float *v2, float limit);
 int VecCompare(float *v1, float *v2, float limit);
 int VecEqual(float *v1, float *v2);
+int VecIsNull(float *v);
 
 void printvecf(char *str,float v[3]);
 void printvec4f(char *str, float v[4]);
@@ -265,6 +266,7 @@ void Vec2Copyf(float *v1, float *v2);
 void Vec2Lerpf(float *target, float *a, float *b, float t);
 
 void AxisAngleToQuat(float *q, float *axis, float angle);
+void RotationBetweenVectorsToQuat(float *q, float v1[3], float v2[3]);
 void vectoquat(float *vec, short axis, short upflag, float *q);
 
 float VecAngle2(float *v1, float *v2);
index aec77f5f3859ddcd684cc31c3af321cc18b5e25a..c77e82f0a2bbcb3ea6fc8830bcadf660cbd3dde1 100644 (file)
 
 struct GHash;
 typedef struct GHash GHash;
-typedef struct GHashIterator GHashIterator;
+
+typedef struct GHashIterator {
+       GHash *gh;
+       int curBucket;
+       struct Entry *curEntry;
+} GHashIterator;
 
 typedef unsigned int   (*GHashHashFP)          (void *key);
 typedef int                            (*GHashCmpFP)           (void *a, void *b);
@@ -62,6 +67,15 @@ int          BLI_ghash_size          (GHash *gh);
         * @return Pointer to a new DynStr.
         */
 GHashIterator* BLI_ghashIterator_new           (GHash *gh);
+       /**
+        * Init an already allocated GHashIterator. The hash table must not
+        * be mutated while the iterator is in use, and the iterator will
+        * step exactly BLI_ghash_size(gh) times before becoming done.
+        * 
+        * @param ghi The GHashIterator to initialize.
+        * @param gh The GHash to iterate over.
+        */
+void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh);
        /**
         * Free a GHashIterator.
         *
diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h
new file mode 100644 (file)
index 0000000..160c2e0
--- /dev/null
@@ -0,0 +1,125 @@
+#ifndef BLI_GRAPH_H_
+#define BLI_GRAPH_H_
+
+#include "DNA_listBase.h"
+
+struct BGraph;
+struct BNode;
+struct BArc;
+
+struct RadialArc;
+
+typedef void (*FreeArc)(struct BArc*);
+typedef void (*FreeNode)(struct BNode*);
+typedef void (*RadialSymmetry)(struct BNode* root_node, struct RadialArc* ring, int total);
+typedef void (*AxialSymmetry)(struct BNode* root_node, struct BNode* node1, struct BNode* node2, struct BArc* arc1, struct BArc* arc2);
+
+/* IF YOU MODIFY THOSE TYPES, YOU NEED TO UPDATE ALL THOSE THAT "INHERIT" FROM THEM
+ * 
+ * RigGraph, ReebGraph
+ * 
+ * */
+
+typedef struct BGraph {
+       ListBase        arcs;
+       ListBase        nodes;
+       
+       float length;
+       
+       /* function pointer to deal with custom fonctionnality */
+       FreeArc                 free_arc;
+       FreeNode                free_node;
+       RadialSymmetry  radial_symmetry;
+       AxialSymmetry   axial_symmetry;
+} BGraph;
+
+typedef struct BNode {
+       void *next, *prev;
+       float p[3];
+       int flag;
+
+       int degree;
+       struct BArc **arcs;
+       
+       int subgraph_index;
+
+       int symmetry_level;
+       int symmetry_flag;
+       float symmetry_axis[3];
+} BNode;
+
+typedef struct BArc {
+       void *next, *prev;
+       struct BNode *head, *tail;
+       int flag;
+
+       float length;
+
+       int symmetry_level;
+       int symmetry_group;
+       int symmetry_flag;
+} BArc;
+
+/* Helper structure for radial symmetry */
+typedef struct RadialArc
+{
+       struct BArc *arc; 
+       float n[3]; /* normalized vector joining the nodes of the arc */
+} RadialArc;
+
+BNode *BLI_otherNode(BArc *arc, BNode *node);
+
+void BLI_freeNode(BGraph *graph, BNode *node);
+void BLI_removeNode(BGraph *graph, BNode *node);
+
+void BLI_removeArc(BGraph *graph, BArc *arc);
+
+void BLI_flagNodes(BGraph *graph, int flag);
+void BLI_flagArcs(BGraph *graph, int flag);
+
+int BLI_hasAdjacencyList(BGraph *rg);
+void BLI_buildAdjacencyList(BGraph *rg);
+void BLI_rebuildAdjacencyList(BGraph* rg);
+void BLI_rebuildAdjacencyListForNode(BGraph* rg, BNode *node);
+void BLI_freeAdjacencyList(BGraph *rg);
+
+int BLI_FlagSubgraphs(BGraph *graph);
+void BLI_ReflagSubgraph(BGraph *graph, int old_subgraph, int new_subgraph);
+
+#define SHAPE_RADIX 10 /* each shape level is encoded this base */
+
+int BLI_subtreeShape(BGraph *graph, BNode *node, BArc *rootArc, int include_root);
+float BLI_subtreeLength(BNode *node);
+void BLI_calcGraphLength(BGraph *graph);
+
+void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced);
+void BLI_replaceNodeInArc(BGraph *graph, BArc *arc, BNode *node_src, BNode *node_replaced);
+void BLI_removeDoubleNodes(BGraph *graph, float limit);
+BNode * BLI_FindNodeByPosition(BGraph *graph, float *p, float limit);
+
+BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v);
+
+int    BLI_isGraphCyclic(BGraph *graph);
+
+/*------------ Symmetry handling ------------*/
+void BLI_markdownSymmetry(BGraph *graph, BNode *root_node, float limit);
+
+void BLI_mirrorAlongAxis(float v[3], float center[3], float axis[3]);
+
+/* BNode symmetry flags */
+#define SYM_TOPOLOGICAL        1
+#define SYM_PHYSICAL   2
+
+/* the following two are exclusive */
+#define SYM_AXIAL              4
+#define SYM_RADIAL             8
+
+/* BArc symmetry flags
+ * 
+ * axial symetry sides */
+#define SYM_SIDE_POSITIVE              1
+#define SYM_SIDE_NEGATIVE              2
+/* Anything higher is the order in radial symmetry */
+#define SYM_SIDE_RADIAL                        3
+
+#endif /*BLI_GRAPH_H_*/
index 39162b8bd91f934b040307b718943fd4c91ab214..5a7e84c42fb0818c92aea4b9e7497459b59824df 100644 (file)
 #define BLENDER_MAX_THREADS            8
 
 struct ListBase;
-
 void   BLI_init_threads        (struct ListBase *threadbase, void *(*do_thread)(void *), int tot);
 int            BLI_available_threads(struct ListBase *threadbase);
 int            BLI_available_thread_index(struct ListBase *threadbase);
 void   BLI_insert_thread       (struct ListBase *threadbase, void *callerdata);
 void   BLI_remove_thread       (struct ListBase *threadbase, void *callerdata);
+void   BLI_remove_thread_index(struct ListBase *threadbase, int index);
+void   BLI_remove_threads(struct ListBase *threadbase);
 void   BLI_end_threads         (struct ListBase *threadbase);
 
 void   BLI_lock_thread         (int type);
 void   BLI_unlock_thread       (int type);
 
 int            BLI_system_thread_count( void ); /* gets the number of threads the system can make use of */
+
+/* ThreadedWorker is a simple tool for dispatching work to a limited number of threads in a transparent
+ * fashion from the caller's perspective
+ * */
+
+struct ThreadedWorker;
+
+/* Create a new worker supporting tot parallel threads.
+ * When new work in inserted and all threads are busy, sleep(sleep_time) before checking again
+ */
+struct ThreadedWorker *BLI_create_worker(void *(*do_thread)(void *), int tot, int sleep_time);
+
+/* join all working threads */
+void BLI_end_worker(struct ThreadedWorker *worker);
+
+/* also ends all working threads */
+void BLI_destroy_worker(struct ThreadedWorker *worker);
+
+/* Spawns a new work thread if possible, sleeps until one is available otherwise
+ * NOTE: inserting work is NOT thread safe, so make sure it is only done from one thread */
+void BLI_insert_work(struct ThreadedWorker *worker, void *param);
+
+
 #endif
 
index e9271ca3bb57ec1978344a88f43cdb5c4440edab..1967b8a88e2376b34c19ceaeb9abe49e8cf1c127 100644 (file)
@@ -200,12 +200,6 @@ void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreef
 
 /***/
 
-struct GHashIterator {
-       GHash *gh;
-       int curBucket;
-       Entry *curEntry;
-};
-
 GHashIterator *BLI_ghashIterator_new(GHash *gh) {
        GHashIterator *ghi= malloc(sizeof(*ghi));
        ghi->gh= gh;
@@ -219,6 +213,17 @@ GHashIterator *BLI_ghashIterator_new(GHash *gh) {
        }
        return ghi;
 }
+void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh) {
+       ghi->gh= gh;
+       ghi->curEntry= NULL;
+       ghi->curBucket= -1;
+       while (!ghi->curEntry) {
+               ghi->curBucket++;
+               if (ghi->curBucket==ghi->gh->nbuckets)
+                       break;
+               ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
+       }
+}
 void BLI_ghashIterator_free(GHashIterator *ghi) {
        free(ghi);
 }
index 79517c4fde4038819f4cfd3e0035415ec5b22bb3..149d3cf1f8f5bc65413d18a6346fae0a008657c0 100644 (file)
@@ -1371,6 +1371,18 @@ void NormalQuat(float *q)
        }
 }
 
+void RotationBetweenVectorsToQuat(float *q, float v1[3], float v2[3])
+{
+       float axis[3];
+       float angle;
+       
+       Crossf(axis, v1, v2);
+       
+       angle = NormalizedVecAngle2(v1, v2);
+       
+       AxisAngleToQuat(q, axis, angle);
+}
+
 void AxisAngleToQuat(float *q, float *axis, float angle)
 {
        float nor[3];
@@ -2219,6 +2231,11 @@ int VecEqual(float *v1, float *v2)
        return ((v1[0]==v2[0]) && (v1[1]==v2[1]) && (v1[2]==v2[2]));
 }
 
+int VecIsNull(float *v)
+{
+       return (v[0] == 0 && v[1] == 0 && v[2] == 0);
+}
+
 void CalcNormShort( short *v1, short *v2, short *v3, float *n) /* is also cross product */
 {
        float n1[3],n2[3];
diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c
new file mode 100644 (file)
index 0000000..8f35b38
--- /dev/null
@@ -0,0 +1,1087 @@
+/**
+ * $Id:
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * Contributor(s): Martin Poirier
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ * graph.c: Common graph interface and methods
+ */
+
+#include <float.h> 
+#include <math.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_graph.h"
+#include "BLI_blenlib.h"
+#include "BLI_arithb.h"
+
+#include "BKE_utildefines.h"
+
+static void testRadialSymmetry(BGraph *graph, BNode* root_node, RadialArc* ring, int total, float axis[3], float limit, int group);
+
+static void handleAxialSymmetry(BGraph *graph, BNode *root_node, int depth, float axis[3], float limit);
+static void testAxialSymmetry(BGraph *graph, BNode* root_node, BNode* node1, BNode* node2, BArc* arc1, BArc* arc2, float axis[3], float limit, int group);
+static void flagAxialSymmetry(BNode *root_node, BNode *end_node, BArc *arc, int group);
+
+void BLI_freeNode(BGraph *graph, BNode *node)
+{
+       if (node->arcs)
+       {
+               MEM_freeN(node->arcs);
+       }
+       
+       if (graph->free_node)
+       {
+               graph->free_node(node);
+       }
+}
+
+void BLI_removeNode(BGraph *graph, BNode *node)
+{
+       BLI_freeNode(graph, node);
+       BLI_freelinkN(&graph->nodes, node);
+}
+
+BNode *BLI_otherNode(BArc *arc, BNode *node)
+{
+       return (arc->head == node) ? arc->tail : arc->head;
+}
+
+void BLI_removeArc(BGraph *graph, BArc *arc)
+{
+       if (graph->free_arc)
+       {
+               graph->free_arc(arc);
+       }
+
+       BLI_freelinkN(&graph->arcs, arc);
+}
+
+void BLI_flagNodes(BGraph *graph, int flag)
+{
+       BNode *node;
+       
+       for(node = graph->nodes.first; node; node = node->next)
+       {
+               node->flag = flag;
+       }
+}
+
+void BLI_flagArcs(BGraph *graph, int flag)
+{
+       BArc *arc;
+       
+       for(arc = graph->arcs.first; arc; arc = arc->next)
+       {
+               arc->flag = flag;
+       }
+}
+
+static void addArcToNodeAdjacencyList(BNode *node, BArc *arc)
+{
+       node->arcs[node->flag] = arc;
+       node->flag++;
+}
+
+void BLI_buildAdjacencyList(BGraph *graph)
+{
+       BNode *node;
+       BArc *arc;
+
+       for(node = graph->nodes.first; node; node = node->next)
+       {
+               if (node->arcs != NULL)
+               {
+                       MEM_freeN(node->arcs);
+               }
+               
+               node->arcs = MEM_callocN((node->degree) * sizeof(BArc*), "adjacency list");
+               
+               /* temporary use to indicate the first index available in the lists */
+               node->flag = 0;
+       }
+
+       for(arc = graph->arcs.first; arc; arc= arc->next)
+       {
+               addArcToNodeAdjacencyList(arc->head, arc);
+               addArcToNodeAdjacencyList(arc->tail, arc);
+       }
+
+       for(node = graph->nodes.first; node; node = node->next)
+       {
+               if (node->degree != node->flag)
+               {
+                       printf("error in node [%p]. Added only %i arcs out of %i\n", node, node->flag, node->degree);
+               }
+       }
+}
+
+void BLI_rebuildAdjacencyListForNode(BGraph* graph, BNode *node)
+{
+       BArc *arc;
+
+       if (node->arcs != NULL)
+       {
+               MEM_freeN(node->arcs);
+       }
+       
+       node->arcs = MEM_callocN((node->degree) * sizeof(BArc*), "adjacency list");
+       
+       /* temporary use to indicate the first index available in the lists */
+       node->flag = 0;
+
+       for(arc = graph->arcs.first; arc; arc= arc->next)
+       {
+               if (arc->head == node)
+               {
+                       addArcToNodeAdjacencyList(arc->head, arc);
+               }
+               else if (arc->tail == node)
+               {
+                       addArcToNodeAdjacencyList(arc->tail, arc);
+               }
+       }
+
+       if (node->degree != node->flag)
+       {
+               printf("error in node [%p]. Added only %i arcs out of %i\n", node, node->flag, node->degree);
+       }
+}
+
+void BLI_freeAdjacencyList(BGraph *graph)
+{
+       BNode *node;
+
+       for(node = graph->nodes.first; node; node = node->next)
+       {
+               if (node->arcs != NULL)
+               {
+                       MEM_freeN(node->arcs);
+                       node->arcs = NULL;
+               }
+       }
+}
+
+int BLI_hasAdjacencyList(BGraph *graph)
+{
+       BNode *node;
+       
+       for(node = graph->nodes.first; node; node = node->next)
+       {
+               if (node->arcs == NULL)
+               {
+                       return 0;
+               }
+       }
+       
+       return 1;
+}
+
+void BLI_replaceNodeInArc(BGraph *graph, BArc *arc, BNode *node_src, BNode *node_replaced)
+{
+       if (arc->head == node_replaced)
+       {
+               arc->head = node_src;
+               node_src->degree++;
+       }
+
+       if (arc->tail == node_replaced)
+       {
+               arc->tail = node_src;
+               node_src->degree++;
+       }
+       
+       if (arc->head == arc->tail)
+       {
+               node_src->degree -= 2;
+               
+               graph->free_arc(arc);
+               BLI_freelinkN(&graph->arcs, arc);
+       }
+
+       if (node_replaced->degree == 0)
+       {
+               BLI_removeNode(graph, node_replaced);
+       }
+}
+
+void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced)
+{
+       BArc *arc, *next_arc;
+       
+       for (arc = graph->arcs.first; arc; arc = next_arc)
+       {
+               next_arc = arc->next;
+               
+               if (arc->head == node_replaced)
+               {
+                       arc->head = node_src;
+                       node_replaced->degree--;
+                       node_src->degree++;
+               }
+
+               if (arc->tail == node_replaced)
+               {
+                       arc->tail = node_src;
+                       node_replaced->degree--;
+                       node_src->degree++;
+               }
+               
+               if (arc->head == arc->tail)
+               {
+                       node_src->degree -= 2;
+                       
+                       graph->free_arc(arc);
+                       BLI_freelinkN(&graph->arcs, arc);
+               }
+       }
+       
+       if (node_replaced->degree == 0)
+       {
+               BLI_removeNode(graph, node_replaced);
+       }
+}
+
+void BLI_removeDoubleNodes(BGraph *graph, float limit)
+{
+       BNode *node_src, *node_replaced;
+       
+       for(node_src = graph->nodes.first; node_src; node_src = node_src->next)
+       {
+               for(node_replaced = graph->nodes.first; node_replaced; node_replaced = node_replaced->next)
+               {
+                       if (node_replaced != node_src && VecLenf(node_replaced->p, node_src->p) <= limit)
+                       {
+                               BLI_replaceNode(graph, node_src, node_replaced);
+                       }
+               }
+       }
+       
+}
+
+BNode * BLI_FindNodeByPosition(BGraph *graph, float *p, float limit)
+{
+       BNode *closest_node = NULL, *node;
+       float min_distance;
+       
+       for(node = graph->nodes.first; node; node = node->next)
+       {
+               float distance = VecLenf(p, node->p); 
+               if (distance <= limit && (closest_node == NULL || distance < min_distance))
+               {
+                       closest_node = node;
+                       min_distance = distance;
+               }
+       }
+       
+       return closest_node;
+}
+/************************************* SUBGRAPH DETECTION **********************************************/
+
+void flagSubgraph(BNode *node, int subgraph)
+{
+       if (node->subgraph_index == 0)
+       {
+               BArc *arc;
+               int i;
+               
+               node->subgraph_index = subgraph;
+               
+               for(i = 0; i < node->degree; i++)
+               {
+                       arc = node->arcs[i];
+                       flagSubgraph(BLI_otherNode(arc, node), subgraph);
+               }
+       }
+} 
+
+int BLI_FlagSubgraphs(BGraph *graph)
+{
+       BNode *node;
+       int subgraph = 0;
+
+       if (BLI_hasAdjacencyList(graph) == 0)
+       {
+               BLI_buildAdjacencyList(graph);
+       }
+       
+       for(node = graph->nodes.first; node; node = node->next)
+       {
+               node->subgraph_index = 0;
+       }
+       
+       for (node = graph->nodes.first; node; node = node->next)
+       {
+               if (node->subgraph_index == 0)
+               {
+                       subgraph++;
+                       flagSubgraph(node, subgraph);
+               }
+       }
+       
+       return subgraph;
+}
+
+void BLI_ReflagSubgraph(BGraph *graph, int old_subgraph, int new_subgraph)
+{
+       BNode *node;
+
+       for (node = graph->nodes.first; node; node = node->next)
+       {
+               if (node->flag == old_subgraph)
+               {
+                       node->flag = new_subgraph;
+               }
+       }
+}
+
+/*************************************** CYCLE DETECTION ***********************************************/
+
+int detectCycle(BNode *node, BArc *src_arc)
+{
+       int value = 0;
+       
+       if (node->flag == 0)
+       {
+               int i;
+
+               /* mark node as visited */
+               node->flag = 1;
+
+               for(i = 0; i < node->degree && value == 0; i++)
+               {
+                       BArc *arc = node->arcs[i];
+                       
+                       /* don't go back on the source arc */
+                       if (arc != src_arc)
+                       {
+                               value = detectCycle(BLI_otherNode(arc, node), arc);
+                       }
+               }
+       }
+       else
+       {
+               value = 1;
+       }
+       
+       return value;
+}
+
+int    BLI_isGraphCyclic(BGraph *graph)
+{
+       BNode *node;
+       int value = 0;
+       
+       /* NEED TO CHECK IF ADJACENCY LIST EXIST */
+       
+       /* Mark all nodes as not visited */
+       BLI_flagNodes(graph, 0);
+
+       /* detectCycles in subgraphs */ 
+       for(node = graph->nodes.first; node && value == 0; node = node->next)
+       {
+               /* only for nodes in subgraphs that haven't been visited yet */
+               if (node->flag == 0)
+               {
+                       value = value || detectCycle(node, NULL);
+               }               
+       }
+       
+       return value;
+}
+
+BArc * BLI_findConnectedArc(BGraph *graph, BArc *arc, BNode *v)
+{
+       BArc *nextArc = arc->next;
+       
+       for(nextArc = graph->arcs.first; nextArc; nextArc = nextArc->next)
+       {
+               if (arc != nextArc && (nextArc->head == v || nextArc->tail == v))
+               {
+                       break;
+               }
+       }
+       
+       return nextArc;
+}
+
+/*********************************** GRAPH AS TREE FUNCTIONS *******************************************/
+
+int subtreeShape(BNode *node, BArc *rootArc, int include_root)
+{
+       int depth = 0;
+       
+       node->flag = 1;
+       
+       if (include_root)
+       {
+               BNode *newNode = BLI_otherNode(rootArc, node);
+               return subtreeShape(newNode, rootArc, 0);
+       }
+       else
+       {
+               /* Base case, no arcs leading away */
+               if (node->arcs == NULL || *(node->arcs) == NULL)
+               {
+                       return 0;
+               }
+               else
+               {
+                       int i;
+       
+                       for(i = 0; i < node->degree; i++)
+                       {
+                               BArc *arc = node->arcs[i];
+                               BNode *newNode = BLI_otherNode(arc, node);
+                               
+                               /* stop immediate and cyclic backtracking */
+                               if (arc != rootArc && newNode->flag == 0)
+                               {
+                                       depth += subtreeShape(newNode, arc, 0);
+                               }
+                       }
+               }
+               
+               return SHAPE_RADIX * depth + 1;
+       }
+}
+
+int BLI_subtreeShape(BGraph *graph, BNode *node, BArc *rootArc, int include_root)
+{
+       BNode *test_node;
+       
+       BLI_flagNodes(graph, 0);
+       return subtreeShape(node, rootArc, include_root);
+}
+
+float BLI_subtreeLength(BNode *node)
+{
+       float length = 0;
+       int i;
+
+       node->flag = 0; /* flag node as visited */
+
+       for(i = 0; i < node->degree; i++)
+       {
+               BArc *arc = node->arcs[i];
+               BNode *other_node = BLI_otherNode(arc, node);
+               
+               if (other_node->flag != 0)
+               {
+                       float subgraph_length = arc->length + BLI_subtreeLength(other_node); 
+                       length = MAX2(length, subgraph_length);
+               }
+       }
+       
+       return length;
+}
+
+void BLI_calcGraphLength(BGraph *graph)
+{
+       float length = 0;
+       int nb_subgraphs;
+       int i;
+       
+       nb_subgraphs = BLI_FlagSubgraphs(graph);
+       
+       for (i = 1; i <= nb_subgraphs; i++)
+       {
+               BNode *node;
+               
+               for (node = graph->nodes.first; node; node = node->next)
+               {
+                       /* start on an external node  of the subgraph */
+                       if (node->subgraph_index == i && node->degree == 1)
+                       {
+                               float subgraph_length = BLI_subtreeLength(node);
+                               length = MAX2(length, subgraph_length);
+                               break;
+                       }
+               }
+       }
+       
+       graph->length = length;
+}
+
+/********************************* SYMMETRY DETECTION **************************************************/
+
+void markdownSymmetryArc(BGraph *graph, BArc *arc, BNode *node, int level, float limit);
+
+void BLI_mirrorAlongAxis(float v[3], float center[3], float axis[3])
+{
+       float dv[3], pv[3];
+       
+       VecSubf(dv, v, center);
+       Projf(pv, dv, axis);
+       VecMulf(pv, -2);
+       VecAddf(v, v, pv);
+}
+
+static void testRadialSymmetry(BGraph *graph, BNode* root_node, RadialArc* ring, int total, float axis[3], float limit, int group)
+{
+       int symmetric = 1;
+       int i;
+       
+       /* sort ring by angle */
+       for (i = 0; i < total - 1; i++)
+       {
+               float minAngle = FLT_MAX;
+               int minIndex = -1;
+               int j;
+
+               for (j = i + 1; j < total; j++)
+               {
+                       float angle = Inpf(ring[i].n, ring[j].n);
+
+                       /* map negative values to 1..2 */
+                       if (angle < 0)
+                       {
+                               angle = 1 - angle;
+                       }
+
+                       if (angle < minAngle)
+                       {
+                               minIndex = j;
+                               minAngle = angle;
+                       }
+               }
+
+               /* swap if needed */
+               if (minIndex != i + 1)
+               {
+                       RadialArc tmp;
+                       tmp = ring[i + 1];
+                       ring[i + 1] = ring[minIndex];
+                       ring[minIndex] = tmp;
+               }
+       }
+
+       for (i = 0; i < total && symmetric; i++)
+       {
+               BNode *node1, *node2;
+               float tangent[3];
+               float normal[3];
+               float p[3];
+               int j = (i + 1) % total; /* next arc in the circular list */
+
+               VecAddf(tangent, ring[i].n, ring[j].n);
+               Crossf(normal, tangent, axis);
+               
+               node1 = BLI_otherNode(ring[i].arc, root_node);
+               node2 = BLI_otherNode(ring[j].arc, root_node);
+
+               VECCOPY(p, node2->p);
+               BLI_mirrorAlongAxis(p, root_node->p, normal);
+               
+               /* check if it's within limit before continuing */
+               if (VecLenf(node1->p, p) > limit)
+               {
+                       symmetric = 0;
+               }
+
+       }
+
+       if (symmetric)
+       {
+               /* mark node as symmetric physically */
+               VECCOPY(root_node->symmetry_axis, axis);
+               root_node->symmetry_flag |= SYM_PHYSICAL;
+               root_node->symmetry_flag |= SYM_RADIAL;
+               
+               /* FLAG SYMMETRY GROUP */
+               for (i = 0; i < total; i++)
+               {
+                       ring[i].arc->symmetry_group = group;
+                       ring[i].arc->symmetry_flag = SYM_SIDE_RADIAL + i;
+               }
+
+               if (graph->radial_symmetry)
+               {
+                       graph->radial_symmetry(root_node, ring, total);
+               }
+       }
+}
+
+static void handleRadialSymmetry(BGraph *graph, BNode *root_node, int depth, float axis[3], float limit)
+{
+       RadialArc *ring = NULL;
+       RadialArc *unit;
+       int total = 0;
+       int group;
+       int first;
+       int i;
+
+       /* mark topological symmetry */
+       root_node->symmetry_flag |= SYM_TOPOLOGICAL;
+
+       /* total the number of arcs in the symmetry ring */
+       for (i = 0; i < root_node->degree; i++)
+       {
+               BArc *connectedArc = root_node->arcs[i];
+               
+               /* depth is store as a negative in flag. symmetry level is positive */
+               if (connectedArc->symmetry_level == -depth)
+               {
+                       total++;
+               }
+       }
+
+       ring = MEM_callocN(sizeof(RadialArc) * total, "radial symmetry ring");
+       unit = ring;
+
+       /* fill in the ring */
+       for (unit = ring, i = 0; i < root_node->degree; i++)
+       {
+               BArc *connectedArc = root_node->arcs[i];
+               
+               /* depth is store as a negative in flag. symmetry level is positive */
+               if (connectedArc->symmetry_level == -depth)
+               {
+                       BNode *otherNode = BLI_otherNode(connectedArc, root_node);
+                       float vec[3];
+
+                       unit->arc = connectedArc;
+
+                       /* project the node to node vector on the symmetry plane */
+                       VecSubf(unit->n, otherNode->p, root_node->p);
+                       Projf(vec, unit->n, axis);
+                       VecSubf(unit->n, unit->n, vec);
+
+                       Normalize(unit->n);
+
+                       unit++;
+               }
+       }
+
+       /* sort ring by arc length
+        * using a rather bogus insertion sort
+        * butrings will never get too big to matter
+        * */
+       for (i = 0; i < total; i++)
+       {
+               int j;
+
+               for (j = i - 1; j >= 0; j--)
+               {
+                       BArc *arc1, *arc2;
+                       
+                       arc1 = ring[j].arc;
+                       arc2 = ring[j + 1].arc;
+                       
+                       if (arc1->length > arc2->length)
+                       {
+                               /* swap with smaller */
+                               RadialArc tmp;
+                               
+                               tmp = ring[j + 1];
+                               ring[j + 1] = ring[j];
+                               ring[j] = tmp;
+                       }
+                       else
+                       {
+                               break;
+                       }
+               }
+       }
+
+       /* Dispatch to specific symmetry tests */
+       first = 0;
+       group = 0;
+       
+       for (i = 1; i < total; i++)
+       {
+               int dispatch = 0;
+               int last = i - 1;
+               
+               if (fabs(ring[first].arc->length - ring[i].arc->length) > limit)
+               {
+                       dispatch = 1;
+               }
+
+               /* if not dispatching already and on last arc
+                * Dispatch using current arc as last
+                * */           
+               if (dispatch == 0 && i == total - 1)
+               {
+                       last = i;
+                       dispatch = 1;
+               } 
+               
+               if (dispatch)
+               {
+                       int sub_total = last - first + 1; 
+
+                       group += 1;
+
+                       if (sub_total == 1)
+                       {
+                               group -= 1; /* not really a group so decrement */
+                               /* NOTHING TO DO */
+                       }
+                       else if (sub_total == 2)
+                       {
+                               BArc *arc1, *arc2;
+                               BNode *node1, *node2;
+                               
+                               arc1 = ring[first].arc;
+                               arc2 = ring[last].arc;
+                               
+                               node1 = BLI_otherNode(arc1, root_node);
+                               node2 = BLI_otherNode(arc2, root_node);
+                               
+                               testAxialSymmetry(graph, root_node, node1, node2, arc1, arc2, axis, limit, group);
+                       }
+                       else if (sub_total != total) /* allocate a new sub ring if needed */
+                       {
+                               RadialArc *sub_ring = MEM_callocN(sizeof(RadialArc) * sub_total, "radial symmetry ring");
+                               int sub_i;
+                               
+                               /* fill in the sub ring */
+                               for (sub_i = 0; sub_i < sub_total; sub_i++)
+                               {
+                                       sub_ring[sub_i] = ring[first + sub_i];
+                               }
+                               
+                               testRadialSymmetry(graph, root_node, sub_ring, sub_total, axis, limit, group);
+                       
+                               MEM_freeN(sub_ring);
+                       }
+                       else if (sub_total == total)
+                       {
+                               testRadialSymmetry(graph, root_node, ring, total, axis, limit, group);
+                       }
+                       
+                       first = i;
+               }
+       }
+
+
+       MEM_freeN(ring);
+}
+
+static void flagAxialSymmetry(BNode *root_node, BNode *end_node, BArc *arc, int group)
+{
+       float vec[3];
+       
+       arc->symmetry_group = group;
+       
+       VecSubf(vec, end_node->p, root_node->p);
+       
+       if (Inpf(vec, root_node->symmetry_axis) < 0)
+       {
+               arc->symmetry_flag |= SYM_SIDE_NEGATIVE;
+       }
+       else
+       {
+               arc->symmetry_flag |= SYM_SIDE_POSITIVE;
+       }
+}
+
+static void testAxialSymmetry(BGraph *graph, BNode* root_node, BNode* node1, BNode* node2, BArc* arc1, BArc* arc2, float axis[3], float limit, int group)
+{
+       float nor[3], vec[3], p[3];
+
+       VecSubf(p, node1->p, root_node->p);
+       Crossf(nor, p, axis);
+
+       VecSubf(p, root_node->p, node2->p);
+       Crossf(vec, p, axis);
+       VecAddf(vec, vec, nor);
+       
+       Crossf(nor, vec, axis);
+       
+       if (abs(nor[0]) > abs(nor[1]) && abs(nor[0]) > abs(nor[2]) && nor[0] < 0)
+       {
+               VecMulf(nor, -1);
+       }
+       else if (abs(nor[1]) > abs(nor[0]) && abs(nor[1]) > abs(nor[2]) && nor[1] < 0)
+       {
+               VecMulf(nor, -1);
+       }
+       else if (abs(nor[2]) > abs(nor[1]) && abs(nor[2]) > abs(nor[0]) && nor[2] < 0)
+       {
+               VecMulf(nor, -1);
+       }
+       
+       /* mirror node2 along axis */
+       VECCOPY(p, node2->p);
+       BLI_mirrorAlongAxis(p, root_node->p, nor);
+       
+       /* check if it's within limit before continuing */
+       if (VecLenf(node1->p, p) <= limit)
+       {
+               /* mark node as symmetric physically */
+               VECCOPY(root_node->symmetry_axis, nor);
+               root_node->symmetry_flag |= SYM_PHYSICAL;
+               root_node->symmetry_flag |= SYM_AXIAL;
+
+               /* flag side on arcs */
+               flagAxialSymmetry(root_node, node1, arc1, group);
+               flagAxialSymmetry(root_node, node2, arc2, group);
+               
+               if (graph->axial_symmetry)
+               {
+                       graph->axial_symmetry(root_node, node1, node2, arc1, arc2);
+               }
+       }
+       else
+       {
+               /* NOT SYMMETRIC */
+       }
+}
+
+static void handleAxialSymmetry(BGraph *graph, BNode *root_node, int depth, float axis[3], float limit)
+{
+       BArc *arc1 = NULL, *arc2 = NULL;
+       BNode *node1 = NULL, *node2 = NULL;
+       int i;
+       
+       /* mark topological symmetry */
+       root_node->symmetry_flag |= SYM_TOPOLOGICAL;
+
+       for (i = 0; i < root_node->degree; i++)
+       {
+               BArc *connectedArc = root_node->arcs[i];
+               
+               /* depth is store as a negative in flag. symmetry level is positive */
+               if (connectedArc->symmetry_level == -depth)
+               {
+                       if (arc1 == NULL)
+                       {
+                               arc1 = connectedArc;
+                               node1 = BLI_otherNode(arc1, root_node);
+                       }
+                       else
+                       {
+                               arc2 = connectedArc;
+                               node2 = BLI_otherNode(arc2, root_node);
+                               break; /* Can stop now, the two arcs have been found */
+                       }
+               }
+       }
+       
+       /* shouldn't happen, but just to be sure */
+       if (node1 == NULL || node2 == NULL)
+       {
+               return;
+       }
+       
+       testAxialSymmetry(graph, root_node, node1, node2, arc1, arc2, axis, limit, 1);
+}
+
+static void markdownSecondarySymmetry(BGraph *graph, BNode *node, int depth, int level, float limit)
+{
+       float axis[3] = {0, 0, 0};
+       int count = 0;
+       int i;
+       
+       /* count the number of branches in this symmetry group
+        * and determinte the axis of symmetry
+        *  */  
+       for (i = 0; i < node->degree; i++)
+       {
+               BArc *connectedArc = node->arcs[i];
+               
+               /* depth is store as a negative in flag. symmetry level is positive */
+               if (connectedArc->symmetry_level == -depth)
+               {
+                       count++;
+               }
+               /* If arc is on the axis */
+               else if (connectedArc->symmetry_level == level)
+               {
+                       VecAddf(axis, axis, connectedArc->head->p);
+                       VecSubf(axis, axis, connectedArc->tail->p);
+               }
+       }
+
+       Normalize(axis);
+
+       /* Split between axial and radial symmetry */
+       if (count == 2)
+       {
+               handleAxialSymmetry(graph, node, depth, axis, limit);
+       }
+       else
+       {
+               handleRadialSymmetry(graph, node, depth, axis, limit);
+       }
+               
+       /* markdown secondary symetries */      
+       for (i = 0; i < node->degree; i++)
+       {
+               BArc *connectedArc = node->arcs[i];
+               
+               if (connectedArc->symmetry_level == -depth)
+               {
+                       /* markdown symmetry for branches corresponding to the depth */
+                       markdownSymmetryArc(graph, connectedArc, node, level + 1, limit);
+               }
+       }
+}
+
+void markdownSymmetryArc(BGraph *graph, BArc *arc, BNode *node, int level, float limit)
+{
+       int i;
+
+       /* if arc is null, we start straight from a node */     
+       if (arc)
+       {
+               arc->symmetry_level = level;
+               
+               node = BLI_otherNode(arc, node);
+       }
+       
+       for (i = 0; i < node->degree; i++)
+       {
+               BArc *connectedArc = node->arcs[i];
+               
+               if (connectedArc != arc)
+               {
+                       BNode *connectedNode = BLI_otherNode(connectedArc, node);
+                       
+                       /* symmetry level is positive value, negative values is subtree depth */
+                       connectedArc->symmetry_level = -BLI_subtreeShape(graph, connectedNode, connectedArc, 0);
+               }
+       }
+
+       arc = NULL;
+
+       for (i = 0; i < node->degree; i++)
+       {
+               int issymmetryAxis = 0;
+               BArc *connectedArc = node->arcs[i];
+               
+               /* only arcs not already marked as symetric */
+               if (connectedArc->symmetry_level < 0)
+               {
+                       int j;
+                       
+                       /* true by default */
+                       issymmetryAxis = 1;
+                       
+                       for (j = 0; j < node->degree; j++)
+                       {
+                               BArc *otherArc = node->arcs[j];
+                               
+                               /* different arc, same depth */
+                               if (otherArc != connectedArc && otherArc->symmetry_level == connectedArc->symmetry_level)
+                               {
+                                       /* not on the symmetry axis */
+                                       issymmetryAxis = 0;
+                                       break;
+                               } 
+                       }
+               }
+               
+               /* arc could be on the symmetry axis */
+               if (issymmetryAxis == 1)
+               {
+                       /* no arc as been marked previously, keep this one */
+                       if (arc == NULL)
+                       {
+                               arc = connectedArc;
+                       }
+                       else if (connectedArc->symmetry_level < arc->symmetry_level)
+                       {
+                               /* go with more complex subtree as symmetry arc */
+                               arc = connectedArc;
+                       }
+               }
+       }
+       
+       /* go down the arc continuing the symmetry axis */
+       if (arc)
+       {
+               markdownSymmetryArc(graph, arc, node, level, limit);
+       }
+
+       
+       /* secondary symmetry */
+       for (i = 0; i < node->degree; i++)
+       {
+               BArc *connectedArc = node->arcs[i];
+               
+               /* only arcs not already marked as symetric and is not the next arc on the symmetry axis */
+               if (connectedArc->symmetry_level < 0)
+               {
+                       /* subtree depth is store as a negative value in the symmetry */
+                       markdownSecondarySymmetry(graph, node, -connectedArc->symmetry_level, level, limit);
+               }
+       }
+}
+
+void BLI_markdownSymmetry(BGraph *graph, BNode *root_node, float limit)
+{
+       BNode *node;
+       BArc *arc;
+       
+       if (BLI_isGraphCyclic(graph))
+       {
+               return;
+       }
+       
+       /* mark down all arcs as non-symetric */
+       BLI_flagArcs(graph, 0);
+       
+       /* mark down all nodes as not on the symmetry axis */
+       BLI_flagNodes(graph, 0);
+
+       node = root_node;
+       
+       /* sanity check REMOVE ME */
+       if (node->degree > 0)
+       {
+               arc = node->arcs[0];
+               
+               if (node->degree == 1)
+               {
+                       markdownSymmetryArc(graph, arc, node, 1, limit);
+               }
+               else
+               {
+                       markdownSymmetryArc(graph, NULL, node, 1, limit);
+               }
+               
+
+
+               /* mark down non-symetric arcs */
+               for (arc = graph->arcs.first; arc; arc = arc->next)
+               {
+                       if (arc->symmetry_level < 0)
+                       {
+                               arc->symmetry_level = 0;
+                       }
+                       else
+                       {
+                               /* mark down nodes with the lowest level symmetry axis */
+                               if (arc->head->symmetry_level == 0 || arc->head->symmetry_level > arc->symmetry_level)
+                               {
+                                       arc->head->symmetry_level = arc->symmetry_level;
+                               }
+                               if (arc->tail->symmetry_level == 0 || arc->tail->symmetry_level > arc->symmetry_level)
+                               {
+                                       arc->tail->symmetry_level = arc->symmetry_level;
+                               }
+                       }
+               }
+       }
+}
+
index 92fad291e83e886446e9631a33cbd4f63369f107..9df8bbc81e3628de740c200463a093e76e8e46f3 100644 (file)
@@ -38,6 +38,8 @@
 #include "BLI_blenlib.h"
 #include "BLI_threads.h"
 
+#include "PIL_time.h"
+
 /* for checking system threads - BLI_system_thread_count */
 #ifdef WIN32
 #include "Windows.h"
@@ -199,6 +201,34 @@ void BLI_remove_thread(ListBase *threadbase, void *callerdata)
        }
 }
 
+void BLI_remove_thread_index(ListBase *threadbase, int index)
+{
+       ThreadSlot *tslot;
+       int counter=0;
+       
+       for(tslot = threadbase->first; tslot; tslot = tslot->next, counter++) {
+               if (counter == index && tslot->avail == 0) {
+                       tslot->callerdata = NULL;
+                       pthread_join(tslot->pthread, NULL);
+                       tslot->avail = 1;
+                       break;
+               }
+       }
+}
+
+void BLI_remove_threads(ListBase *threadbase)
+{
+       ThreadSlot *tslot;
+       
+       for(tslot = threadbase->first; tslot; tslot = tslot->next) {
+               if (tslot->avail == 0) {
+                       tslot->callerdata = NULL;
+                       pthread_join(tslot->pthread, NULL);
+                       tslot->avail = 1;
+               }
+       }
+}
+
 void BLI_end_threads(ListBase *threadbase)
 {
        ThreadSlot *tslot;
@@ -265,4 +295,104 @@ int BLI_system_thread_count( void )
        return t;
 }
 
+/* ************************************************ */
+
+typedef struct ThreadedWorker {
+       ListBase threadbase;
+       void *(*work_fnct)(void *);
+       char     busy[RE_MAX_THREAD];
+       int              total;
+       int              sleep_time;
+} ThreadedWorker;
+
+typedef struct WorkParam {
+       ThreadedWorker *worker;
+       void *param;
+       int       index;
+} WorkParam;
+
+void *exec_work_fnct(void *v_param)
+{
+       WorkParam *p = (WorkParam*)v_param;
+       void *value;
+       
+       value = p->worker->work_fnct(p->param);
+       
+       p->worker->busy[p->index] = 0;
+       MEM_freeN(p);
+       
+       return value;
+}
+
+ThreadedWorker *BLI_create_worker(void *(*do_thread)(void *), int tot, int sleep_time)
+{
+       ThreadedWorker *worker;
+       
+       worker = MEM_callocN(sizeof(ThreadedWorker), "threadedworker");
+       
+       if (tot > RE_MAX_THREAD)
+       {
+               tot = RE_MAX_THREAD;
+       }
+       else if (tot < 1)
+       {
+               tot= 1;
+       }
+       
+       worker->total = tot;
+       worker->work_fnct = do_thread;
+       
+       BLI_init_threads(&worker->threadbase, exec_work_fnct, tot);
+       
+       return worker;
+}
+
+void BLI_end_worker(ThreadedWorker *worker)
+{
+       BLI_remove_threads(&worker->threadbase);
+}
+
+void BLI_destroy_worker(ThreadedWorker *worker)
+{
+       BLI_end_worker(worker);
+       BLI_freelistN(&worker->threadbase);
+       MEM_freeN(worker);
+}
+
+void BLI_insert_work(ThreadedWorker *worker, void *param)
+{
+       WorkParam *p = MEM_callocN(sizeof(WorkParam), "workparam");
+       int index;
+       
+       if (BLI_available_threads(&worker->threadbase) == 0)
+       {
+               index = worker->total;
+               while(index == worker->total)
+               {
+                       PIL_sleep_ms(worker->sleep_time);
+                       
+                       for (index = 0; index < worker->total; index++)
+                       {
+                               if (worker->busy[index] == 0)
+                               {
+                                       BLI_remove_thread_index(&worker->threadbase, index);
+                                       break;
+                               }
+                       }
+               }
+       }
+       else
+       {
+               index = BLI_available_thread_index(&worker->threadbase);
+       }
+       
+       worker->busy[index] = 1;
+       
+       p->param = param;
+       p->index = index;
+       p->worker = worker;
+       
+       BLI_insert_thread(&worker->threadbase, p);
+}
+
 /* eof */
index c2dcc86ae41dbf90716923b6fe386b7c7dd914ab..ec26683444ebed7fd2c7380abb46552301275c85 100644 (file)
@@ -7373,6 +7373,24 @@ static void do_versions(FileData *fd, Library *lib, Main *main)
                        }
                }
        }
+       
+       /* sanity check for skgen
+        * */
+       {
+               Scene *sce;
+               for(sce=main->scene.first; sce; sce = sce->id.next)
+               {
+                       if (sce->toolsettings->skgen_subdivisions[0] == sce->toolsettings->skgen_subdivisions[1] ||
+                               sce->toolsettings->skgen_subdivisions[0] == sce->toolsettings->skgen_subdivisions[2] ||
+                               sce->toolsettings->skgen_subdivisions[1] == sce->toolsettings->skgen_subdivisions[2])
+                       {
+                                       sce->toolsettings->skgen_subdivisions[0] = SKGEN_SUB_CORRELATION;
+                                       sce->toolsettings->skgen_subdivisions[1] = SKGEN_SUB_LENGTH;
+                                       sce->toolsettings->skgen_subdivisions[2] = SKGEN_SUB_ANGLE;
+                       }
+               }
+       }
+       
 
        if ((main->versionfile < 245) || (main->versionfile == 245 && main->subversionfile < 2)) {
                Image *ima;
index d390b96f61f5bccc4dd103ff9ae9db3b274a9480..02d736808188b2826ca2103519b3df37126f8ffe 100644 (file)
@@ -68,6 +68,8 @@ typedef struct EditBone
 
 } EditBone;
 
+void   make_boneList(struct ListBase *list, struct ListBase *bones, EditBone *parent);
+void   editbones_to_armature (struct ListBase *list, struct Object *ob);
 
 void   adduplicate_armature(void);
 void   addvert_armature(void);
@@ -148,6 +150,15 @@ void       align_selected_bones(void);
 
 #define BONESEL_NOSEL  0x80000000      /* Indicates a negative number */
 
+/* from autoarmature */
+void BIF_retargetArmature();
+void BIF_adjustRetarget();
+void BIF_freeRetarget();
+
+struct ReebArc;
+float calcVariance(struct ReebArc *arc, int start, int end, float v0[3], float n[3]);
+float calcDistance(struct ReebArc *arc, int start, int end, float head[3], float tail[3]);
+
 /* useful macros */
 #define EBONE_VISIBLE(arm, ebone) ((arm->layer & ebone->layer) && !(ebone->flag & BONE_HIDDEN_A))
 #define EBONE_EDITABLE(ebone) ((ebone->flag & BONE_SELECTED) && !(ebone->flag & BONE_EDITMODE_LOCKED)) 
index 3de427476b9419b812718465d54c693de8c2776f..8cac5a074ab54916c39505c6f0682c108c5a3c47 100644 (file)
@@ -443,7 +443,8 @@ void curvemap_buttons(struct uiBlock *block, struct CurveMapping *cumap, char la
 #define B_SETMCOL_RND          2083
 #define B_DRAWBWEIGHTS         2084
 
-#define B_GEN_SKELETON         2090
+#define B_GEN_SKELETON         2085
+#define B_RETARGET_SKELETON    2086
 
 /* *********************** */
 #define B_VGROUPBUTS           2100
index c8352aedec54e63710c5fba10cff01ea4e8b0982..1f9a7801b065d03148fc486ee51f18842e5ff0d9 100644 (file)
 
 #include "DNA_listBase.h"
 
+#include "BLI_graph.h"
+
+struct GHash;
 struct EdgeHash;
 struct ReebArc;
 struct ReebEdge;
 struct ReebNode;
 
 typedef struct ReebGraph {
-       ListBase arcs;
-       ListBase nodes;
+       ListBase        arcs;
+       ListBase        nodes;
+       
+       float length;
+       
+       FreeArc                 free_arc;
+       FreeNode                free_node;
+       RadialSymmetry  radial_symmetry;
+       AxialSymmetry   axial_symmetry;
+       /*********************************/
+       
+       int resolution;
        int totnodes;
        struct EdgeHash *emap;
+       int multi_level;
+       struct ReebGraph *link_up; /* for multi resolution filtering, points to higher levels */
 } ReebGraph;
 
 typedef struct EmbedBucket {
@@ -49,13 +64,25 @@ typedef struct EmbedBucket {
 } EmbedBucket;
 
 typedef struct ReebNode {
-       struct ReebNode *next, *prev;
+       void *next, *prev;
+       float p[3];
+       int flag;
+
+       int degree;
        struct ReebArc **arcs;
+
+       int subgraph_index;
+
+       int symmetry_level;
+       int symmetry_flag;
+       float symmetry_axis[3];
+       /*********************************/
+
        int index;
-       int degree;
        float weight;
-       float p[3];
-       int flags;
+       int     multi_level;
+       struct ReebNode *link_down; /* for multi resolution filtering, points to lower levels, if present */
+       struct ReebNode *link_up;
 } ReebNode;
 
 typedef struct ReebEdge {
@@ -63,15 +90,28 @@ typedef struct ReebEdge {
        struct ReebArc  *arc;
        struct ReebNode *v1, *v2;
        struct ReebEdge *nextEdge;
+       int flag;
 } ReebEdge;
 
 typedef struct ReebArc {
-       struct ReebArc *next, *prev;
+       void *next, *prev;
+       struct ReebNode *head, *tail;
+       int flag;
+
+       float length;
+
+       int symmetry_level;
+       int symmetry_group;
+       int symmetry_flag;
+       /*********************************/
+
        ListBase edges;
-       struct ReebNode *v1, *v2;
+       int bcount;
        struct EmbedBucket *buckets;
-       int     bcount;
-       int flags;
+
+       struct GHash *faces;    
+       float angle;
+       struct ReebArc *link_up; /* for multi resolution filtering, points to higher levels */
 } ReebArc;
 
 typedef struct ReebArcIterator {
@@ -79,29 +119,37 @@ typedef struct ReebArcIterator {
        int index;
        int start;
        int end;
-       int stride;
+       int stride; 
+       int length;
 } ReebArcIterator;
 
 struct EditMesh;
+struct EdgeIndex;
 
-int weightToHarmonic(struct EditMesh *em);
-int weightFromDistance(struct EditMesh *em);
+int weightToHarmonic(struct EditMesh *em, struct EdgeIndex *indexed_edges);
+int weightFromDistance(struct EditMesh *em, struct EdgeIndex *indexed_edges);
 int weightFromLoc(struct EditMesh *me, int axis);
-void weightToVCol(struct EditMesh *em);
+void weightToVCol(struct EditMesh *em, int index);
+void arcToVCol(struct ReebGraph *rg, struct EditMesh *em, int index);
+void angleToVCol(struct EditMesh *em, int index);
 void renormalizeWeight(struct EditMesh *em, float newmax);
 
 ReebGraph * generateReebGraph(struct EditMesh *me, int subdivisions);
-void freeGraph(ReebGraph *rg);
-void exportGraph(ReebGraph *rg, int count);
-
-#define OTHER_NODE(arc, node) ((arc->v1 == node) ? arc->v2 : arc->v1)
+ReebGraph * newReebGraph();
 
 void initArcIterator(struct ReebArcIterator *iter, struct ReebArc *arc, struct ReebNode *head);
 void initArcIterator2(struct ReebArcIterator *iter, struct ReebArc *arc, int start, int end);
+void initArcIteratorStart(struct ReebArcIterator *iter, struct ReebArc *arc, struct ReebNode *head, int start);
 struct EmbedBucket * nextBucket(struct ReebArcIterator *iter);
+struct EmbedBucket * nextNBucket(ReebArcIterator *iter, int n);
+struct EmbedBucket * peekBucket(ReebArcIterator *iter, int n);
+struct EmbedBucket * currentBucket(struct ReebArcIterator *iter);
+struct EmbedBucket * previousBucket(struct ReebArcIterator *iter);
+int iteratorStopped(struct ReebArcIterator *iter);
 
 /* Filtering */
 void filterNullReebGraph(ReebGraph *rg);
+int filterSmartReebGraph(ReebGraph *rg, float threshold);
 int filterExternalReebGraph(ReebGraph *rg, float threshold);
 int filterInternalReebGraph(ReebGraph *rg, float threshold);
 
@@ -110,18 +158,33 @@ void repositionNodes(ReebGraph *rg);
 void postprocessGraph(ReebGraph *rg, char mode);
 void removeNormalNodes(ReebGraph *rg);
 
-/* Graph processing */
-void buildAdjacencyList(ReebGraph *rg);
-
 void sortNodes(ReebGraph *rg);
 void sortArcs(ReebGraph *rg);
 
-int subtreeDepth(ReebNode *node, ReebArc *rootArc);
-int countConnectedArcs(ReebGraph *rg, ReebNode *node);
-int hasAdjacencyList(ReebGraph *rg); 
-int    isGraphCyclic(ReebGraph *rg);
-
-/* Sanity check */
+/*------------ Sanity check ------------*/
 void verifyBuckets(ReebGraph *rg);
+void verifyFaces(ReebGraph *rg);
+
+/*********************** PUBLIC *********************************/
+
+#define REEB_MAX_MULTI_LEVEL   10
+
+ReebGraph *BIF_ReebGraphFromEditMesh(void);
+ReebGraph *BIF_ReebGraphMultiFromEditMesh(void);
+void BIF_flagMultiArcs(ReebGraph *rg, int flag);
+
+void BIF_GlobalReebGraphFromEditMesh(void);
+void BIF_GlobalReebFree(void);
+
+ReebNode *BIF_otherNodeFromIndex(ReebArc *arc, ReebNode *node);
+ReebNode *BIF_NodeFromIndex(ReebArc *arc, ReebNode *node);
+ReebNode *BIF_lowestLevelNode(ReebNode *node);
+
+ReebGraph *BIF_graphForMultiNode(ReebGraph *rg, ReebNode *node);
+
+void REEB_freeGraph(ReebGraph *rg);
+void REEB_exportGraph(ReebGraph *rg, int count);
+void REEB_draw();
+
 
 #endif /*REEB_H_*/
index a5eaf222941eee3bf93a4b90a77c6aecf4646287..c1c164f136f4427708581acfaa031be5be1af20a 100644 (file)
@@ -433,14 +433,20 @@ typedef struct ToolSettings {
        float skgen_angle_limit;
        float skgen_correlation_limit;
        float skgen_symmetry_limit;
+       float skgen_retarget_angle_weight;
+       float skgen_retarget_length_weight;
+       float skgen_retarget_distance_weight;
        short skgen_options;
        char  skgen_postpro;
        char  skgen_postpro_passes;
        char  skgen_subdivisions[3];
+       char  skgen_multi_level;
+       char  skgen_optimisation_method;
+       
+       char tpad[6];
        
        /* Alt+RMB option */
        char edge_mode;
-       char pad3[4];
 } ToolSettings;
 
 /* Used by all brushes to store their properties, which can be directly set
@@ -837,12 +843,21 @@ typedef struct Scene {
 #define RETOPO_ELLIPSE 4
 
 /* toolsettings->skgen_options */
-#define SKGEN_FILTER_INTERNAL  1
-#define SKGEN_FILTER_EXTERNAL  2
-#define        SKGEN_SYMMETRY                  4
-#define        SKGEN_CUT_LENGTH                8
-#define        SKGEN_CUT_ANGLE                 16
-#define        SKGEN_CUT_CORRELATION   32
+#define SKGEN_FILTER_INTERNAL  (1 << 0)
+#define SKGEN_FILTER_EXTERNAL  (1 << 1)
+#define        SKGEN_SYMMETRY                  (1 << 2)
+#define        SKGEN_CUT_LENGTH                (1 << 3)
+#define        SKGEN_CUT_ANGLE                 (1 << 4)
+#define        SKGEN_CUT_CORRELATION   (1 << 5)
+#define        SKGEN_HARMONIC                  (1 << 6)
+#define        SKGEN_STICK_TO_EMBEDDING        (1 << 7)
+#define        SKGEN_ADAPTIVE_DISTANCE         (1 << 8)
+#define SKGEN_FILTER_SMART             (1 << 9)
+#define SKGEN_DISP_LENGTH              (1 << 10)
+#define SKGEN_DISP_WEIGHT              (1 << 11)
+#define SKGEN_DISP_ORIG                        (1 << 12)
+#define SKGEN_DISP_EMBED               (1 << 13)
+#define SKGEN_DISP_INDEX               (1 << 14)
 
 #define        SKGEN_SUB_LENGTH                0
 #define        SKGEN_SUB_ANGLE                 1
diff --git a/source/blender/src/autoarmature.c b/source/blender/src/autoarmature.c
new file mode 100644 (file)
index 0000000..b0a7a2a
--- /dev/null
@@ -0,0 +1,2968 @@
+/**
+ * $Id:
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * Contributor(s): Martin Poirier
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ * autoarmature.c: Interface for automagically manipulating armature (retarget, created, ...)
+ */
+
+#include <ctype.h>
+#include <stdlib.h>
+#include <string.h>
+#include <math.h> 
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include "MEM_guardedalloc.h"
+
+#include "PIL_time.h"
+
+#include "DNA_ID.h"
+#include "DNA_action_types.h"
+#include "DNA_armature_types.h"
+#include "DNA_constraint_types.h"
+#include "DNA_mesh_types.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_object_types.h"
+#include "DNA_scene_types.h"
+#include "DNA_view3d_types.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_arithb.h"
+#include "BLI_editVert.h"
+#include "BLI_ghash.h"
+#include "BLI_graph.h"
+#include "BLI_rand.h"
+#include "BLI_threads.h"
+
+#include "BDR_editobject.h"
+
+#include "BKE_global.h"
+#include "BKE_utildefines.h"
+#include "BKE_constraint.h"
+#include "BKE_armature.h"
+
+#include "BIF_editarmature.h"
+#include "BIF_space.h"
+
+#include "PIL_time.h"
+
+#include "mydevice.h"
+#include "reeb.h" // FIX ME
+#include "blendef.h"
+
+/************ RIG RETARGET DATA STRUCTURES ***************/
+
+struct RigJoint;
+struct RigGraph;
+struct RigNode;
+struct RigArc;
+struct RigEdge;
+
+//#define USE_THREADS
+
+typedef struct RigGraph {
+       ListBase        arcs;
+       ListBase        nodes;
+       
+       float length;
+       
+       FreeArc                 free_arc;
+       FreeNode                free_node;
+       RadialSymmetry  radial_symmetry;
+       AxialSymmetry   axial_symmetry;
+       /*********************************/
+
+       struct RigNode *head;
+       ReebGraph *link_mesh;
+       
+       ListBase editbones;
+       
+       ListBase controls;
+       struct ThreadedWorker *worker;
+       
+       GHash *bones_map;       /* map of editbones by name */
+       GHash *controls_map;    /* map of rigcontrols by bone pointer */
+       
+       Object *ob;
+} RigGraph;
+
+typedef struct RigNode {
+       void *next, *prev;
+       float p[3];
+       int flag;
+
+       int degree;
+       struct BArc **arcs;
+
+       int subgraph_index;
+
+       int symmetry_level;
+       int symmetry_flag;
+       float symmetry_axis[3];
+       /*********************************/
+
+       ReebNode *link_mesh;
+} RigNode;
+
+typedef struct RigArc {
+       void *next, *prev;
+       RigNode *head, *tail;
+       int flag;
+
+       float length;
+
+       int symmetry_level;
+       int symmetry_group;
+       int symmetry_flag;
+       /*********************************/
+       
+       ListBase edges;
+       int count;
+       ReebArc *link_mesh;
+} RigArc;
+
+typedef struct RigEdge {
+       struct RigEdge *next, *prev;
+       float head[3], tail[3];
+       float length;
+       float angle;
+       EditBone *bone;
+       float up_axis[3];
+} RigEdge;
+
+/* Control flags */
+#define RIG_CTRL_DONE                  1
+#define RIG_CTRL_PARENT_DEFORM 2
+#define RIG_CTRL_FIT_ROOT              4
+#define RIG_CTRL_FIT_BONE              8
+
+typedef struct RigControl {
+       struct RigControl *next, *prev;
+       float head[3], tail[3];
+       EditBone *bone;
+       EditBone *link;
+       float   up_axis[3];
+       float   offset[3];
+       int             flag;
+} RigControl;
+
+typedef struct MemoNode {
+       float   weight;
+       int     next;
+} MemoNode;
+
+typedef struct RetargetParam {
+       RigGraph        *rigg;
+       RigArc          *iarc;
+       RigNode         *inode_start;
+} RetargetParam;
+
+typedef enum 
+{
+       RETARGET_LENGTH,
+       RETARGET_AGGRESSIVE
+} RetargetMode; 
+
+typedef enum
+{
+       METHOD_BRUTE_FORCE = 0,
+       METHOD_MEMOIZE = 1,
+       METHOD_ANNEALING = 2
+} RetargetMethod;
+
+typedef enum
+{
+       ARC_FREE = 0,
+       ARC_TAKEN = 1,
+       ARC_USED = 2
+} ArcUsageFlags;
+
+
+RigGraph *GLOBAL_RIGG = NULL;
+
+/*******************************************************************************************************/
+
+void *exec_retargetArctoArc(void *param);
+
+static void RIG_calculateEdgeAngle(RigEdge *edge_first, RigEdge *edge_second);
+
+/* two levels */
+#define SHAPE_LEVELS (SHAPE_RADIX * SHAPE_RADIX) 
+
+/*********************************** EDITBONE UTILS ****************************************************/
+
+int countEditBoneChildren(ListBase *list, EditBone *parent)
+{
+       EditBone *ebone;
+       int count = 0;
+       
+       for (ebone = list->first; ebone; ebone = ebone->next)
+       {
+               if (ebone->parent == parent)
+               {
+                       count++;
+               }
+       }
+       
+       return count;
+}
+
+EditBone* nextEditBoneChild(ListBase *list, EditBone *parent, int n)
+{
+       EditBone *ebone;
+       
+       for (ebone = list->first; ebone; ebone = ebone->next)
+       {
+               if (ebone->parent == parent)
+               {
+                       if (n == 0)
+                       {
+                               return ebone;
+                       }
+                       n--;
+               }
+       }
+       
+       return NULL;
+}
+
+void getEditBoneRollUpAxis(EditBone *bone, float roll, float up_axis[3])
+{
+       float mat[3][3], nor[3];
+
+       VecSubf(nor, bone->tail, bone->head);
+       
+       vec_roll_to_mat3(nor, roll, mat);
+       VECCOPY(up_axis, mat[2]);
+}
+
+float getNewBoneRoll(EditBone *bone, float old_up_axis[3], float quat[4])
+{
+       float mat[3][3];
+       float nor[3], up_axis[3], new_up_axis[3], vec[3];
+       float roll;
+       
+       VECCOPY(new_up_axis, old_up_axis);
+       QuatMulVecf(quat, new_up_axis);
+
+       VecSubf(nor, bone->tail, bone->head);
+       
+       vec_roll_to_mat3(nor, 0, mat);
+       VECCOPY(up_axis, mat[2]);
+       
+       roll = NormalizedVecAngle2(new_up_axis, up_axis);
+       
+       Crossf(vec, up_axis, new_up_axis);
+       
+       if (Inpf(vec, nor) < 0)
+       {
+               roll = -roll;
+       }
+       
+       return roll;
+}
+
+/************************************ DESTRUCTORS ******************************************************/
+
+void RIG_freeRigArc(BArc *arc)
+{
+       BLI_freelistN(&((RigArc*)arc)->edges);
+}
+
+void RIG_freeRigGraph(BGraph *rg)
+{
+       BNode *node;
+       BArc *arc;
+       
+#ifdef USE_THREADS
+       BLI_destroy_worker(((RigGraph*)rg)->worker);
+#endif
+       
+       REEB_freeGraph(((RigGraph*)rg)->link_mesh);
+       
+       for (arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               RIG_freeRigArc(arc);
+       }
+       BLI_freelistN(&rg->arcs);
+       
+       for (node = rg->nodes.first; node; node = node->next)
+       {
+               BLI_freeNode(rg, (BNode*)node);
+       }
+       BLI_freelistN(&rg->nodes);
+       
+       BLI_freelistN(&((RigGraph*)rg)->controls);
+
+       BLI_ghash_free(((RigGraph*)rg)->bones_map, NULL, NULL);
+       BLI_ghash_free(((RigGraph*)rg)->controls_map, NULL, NULL);
+       
+       BLI_freelistN(&((RigGraph*)rg)->editbones);
+       
+       MEM_freeN(rg);
+}
+
+/************************************* ALLOCATORS ******************************************************/
+
+static RigGraph *newRigGraph()
+{
+       RigGraph *rg;
+       int totthread;
+       
+       rg = MEM_callocN(sizeof(RigGraph), "rig graph");
+       
+       rg->head = NULL;
+       
+       rg->bones_map = BLI_ghash_new(BLI_ghashutil_strhash, BLI_ghashutil_strcmp);
+       rg->controls_map = BLI_ghash_new(BLI_ghashutil_strhash, BLI_ghashutil_strcmp);
+       
+       rg->free_arc = RIG_freeRigArc;
+       rg->free_node = NULL;
+       
+#ifdef USE_THREADS
+       if(G.scene->r.mode & R_FIXED_THREADS)
+       {
+               totthread = G.scene->r.threads;
+       }
+       else
+       {
+               totthread = BLI_system_thread_count();
+       }
+       
+       rg->worker = BLI_create_worker(exec_retargetArctoArc, totthread, 20); /* fix number of threads */
+#endif
+       
+       return rg;
+}
+
+static RigArc *newRigArc(RigGraph *rg)
+{
+       RigArc *arc;
+       
+       arc = MEM_callocN(sizeof(RigArc), "rig arc");
+       arc->count = 0;
+       BLI_addtail(&rg->arcs, arc);
+       
+       return arc;
+}
+
+static RigControl *newRigControl(RigGraph *rg)
+{
+       RigControl *ctrl;
+       
+       ctrl = MEM_callocN(sizeof(RigControl), "rig control");
+       
+       BLI_addtail(&rg->controls, ctrl);
+       
+       return ctrl;
+}
+
+static RigNode *newRigNodeHead(RigGraph *rg, RigArc *arc, float p[3])
+{
+       RigNode *node;
+       node = MEM_callocN(sizeof(RigNode), "rig node");
+       BLI_addtail(&rg->nodes, node);
+
+       VECCOPY(node->p, p);
+       node->degree = 1;
+       node->arcs = NULL;
+       
+       arc->head = node;
+       
+       return node;
+}
+
+static void addRigNodeHead(RigGraph *rg, RigArc *arc, RigNode *node)
+{
+       node->degree++;
+
+       arc->head = node;
+}
+
+static RigNode *newRigNode(RigGraph *rg, float p[3])
+{
+       RigNode *node;
+       node = MEM_callocN(sizeof(RigNode), "rig node");
+       BLI_addtail(&rg->nodes, node);
+
+       VECCOPY(node->p, p);
+       node->degree = 0;
+       node->arcs = NULL;
+       
+       return node;
+}
+
+static RigNode *newRigNodeTail(RigGraph *rg, RigArc *arc, float p[3])
+{
+       RigNode *node = newRigNode(rg, p);
+       
+       node->degree = 1;
+       arc->tail = node;
+
+       return node;
+}
+
+static void RIG_appendEdgeToArc(RigArc *arc, RigEdge *edge)
+{
+       BLI_addtail(&arc->edges, edge);
+
+       if (edge->prev == NULL)
+       {
+               VECCOPY(edge->head, arc->head->p);
+       }
+       else
+       {
+               RigEdge *last_edge = edge->prev;
+               VECCOPY(edge->head, last_edge->tail);
+               RIG_calculateEdgeAngle(last_edge, edge);
+       }
+       
+       edge->length = VecLenf(edge->head, edge->tail);
+       
+       arc->length += edge->length;
+       
+       arc->count += 1;
+}
+
+static void RIG_addEdgeToArc(RigArc *arc, float tail[3], EditBone *bone)
+{
+       RigEdge *edge;
+
+       edge = MEM_callocN(sizeof(RigEdge), "rig edge");
+
+       VECCOPY(edge->tail, tail);
+       edge->bone = bone;
+       
+       if (bone)
+       {
+               getEditBoneRollUpAxis(bone, bone->roll, edge->up_axis);
+       }
+       
+       RIG_appendEdgeToArc(arc, edge);
+}
+
+/*******************************************************************************************************/
+
+static void RIG_calculateEdgeAngle(RigEdge *edge_first, RigEdge *edge_second)
+{
+       float vec_first[3], vec_second[3];
+       
+       VecSubf(vec_first, edge_first->tail, edge_first->head); 
+       VecSubf(vec_second, edge_second->tail, edge_second->head);
+
+       Normalize(vec_first);
+       Normalize(vec_second);
+       
+       edge_first->angle = saacos(Inpf(vec_first, vec_second));
+}
+
+/************************************ CONTROL BONES ****************************************************/
+
+static void RIG_addControlBone(RigGraph *rg, EditBone *bone)
+{
+       RigControl *ctrl = newRigControl(rg);
+       ctrl->bone = bone;
+       VECCOPY(ctrl->head, bone->head);
+       VECCOPY(ctrl->tail, bone->tail);
+       getEditBoneRollUpAxis(bone, bone->roll, ctrl->up_axis);
+       
+       BLI_ghash_insert(rg->controls_map, bone->name, ctrl);
+}
+
+static int RIG_parentControl(RigControl *ctrl, EditBone *link)
+{
+       if (link)
+       {
+               float offset[3];
+               int flag = 0;
+               
+               VecSubf(offset, ctrl->bone->head, link->head);
+
+               /* if root matches, check for direction too */          
+               if (Inpf(offset, offset) < 0.0001)
+               {
+                       float vbone[3], vparent[3];
+                       
+                       flag |= RIG_CTRL_FIT_ROOT;
+                       
+                       VecSubf(vbone, ctrl->bone->tail, ctrl->bone->head);
+                       VecSubf(vparent, link->tail, link->head);
+                       
+                       /* test for opposite direction */
+                       if (Inpf(vbone, vparent) > 0)
+                       {
+                               float nor[3];
+                               float len;
+                               
+                               Crossf(nor, vbone, vparent);
+                               
+                               len = Inpf(nor, nor);
+                               if (len < 0.0001)
+                               {
+                                       flag |= RIG_CTRL_FIT_BONE;
+                               }
+                       }
+               }
+               
+               /* Bail out if old one is automatically better */
+               if (flag < ctrl->flag)
+               {
+                       return 0;
+               }
+               
+               /* if there's already a link
+                *      overwrite only if new link is higher in the chain */
+               if (ctrl->link && flag == ctrl->flag)
+               {
+                       EditBone *bone = NULL;
+                       
+                       for (bone = ctrl->link; bone; bone = bone->parent)
+                       {
+                               /* if link is in the chain, break and use that one */
+                               if (bone == link)
+                               {
+                                       break;
+                               }
+                       }
+                       
+                       /* not in chain, don't update link */
+                       if (bone == NULL)
+                       {
+                               return 0;
+                       }
+               }
+               
+               
+               ctrl->link = link;
+               ctrl->flag = flag;
+               
+               VECCOPY(ctrl->offset, offset);
+               
+               return 1;
+       }
+       
+       return 0;
+}
+
+static void RIG_reconnectControlBones(RigGraph *rg)
+{
+       RigControl *ctrl;
+       int change = 1;
+       
+       /* first pass, link to deform bones */
+       for (ctrl = rg->controls.first; ctrl; ctrl = ctrl->next)
+       {
+               bPoseChannel *pchan;
+               bConstraint *con;
+               int found = 0;
+               
+               /* DO SOME MAGIC HERE */
+               for (pchan= rg->ob->pose->chanbase.first; pchan; pchan= pchan->next)
+               {
+                       for (con= pchan->constraints.first; con; con= con->next) 
+                       {
+                               bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
+                               ListBase targets = {NULL, NULL};
+                               bConstraintTarget *ct;
+                               
+                               /* constraint targets */
+                               if (cti && cti->get_constraint_targets)
+                               {
+                                       cti->get_constraint_targets(con, &targets);
+                                       
+                                       for (ct= targets.first; ct; ct= ct->next)
+                                       {
+                                               if ((ct->tar == rg->ob) && strcmp(ct->subtarget, ctrl->bone->name) == 0)
+                                               {
+                                                       /* SET bone link to bone corresponding to pchan */
+                                                       EditBone *link = BLI_ghash_lookup(rg->bones_map, pchan->name);
+                                                       
+                                                       found = RIG_parentControl(ctrl, link);
+                                               }
+                                       }
+                                       
+                                       if (cti->flush_constraint_targets)
+                                               cti->flush_constraint_targets(con, &targets, 0);
+                               }
+                       }
+               }
+
+               /* if not found yet, check parent */
+               if (found == 0)
+               {               
+                       if (ctrl->bone->parent)
+                       {
+                               /* make sure parent is a deforming bone
+                                * NULL if not
+                                *  */
+                               EditBone *link = BLI_ghash_lookup(rg->bones_map, ctrl->bone->parent->name);
+                               
+                               found = RIG_parentControl(ctrl, link);
+                       }
+                       
+                       /* check if bone is not superposed on another one */
+                       {
+                               RigArc *arc;
+                               RigArc *best_arc = NULL;
+                               EditBone *link = NULL;
+                               
+                               for (arc = rg->arcs.first; arc; arc = arc->next)
+                               {
+                                       RigEdge *edge;
+                                       for (edge = arc->edges.first; edge; edge = edge->next)
+                                       {
+                                               if (edge->bone)
+                                               {
+                                                       int fit = 0;
+                                                       
+                                                       fit = VecLenf(ctrl->bone->head, edge->bone->head) < 0.0001;
+                                                       fit = fit || VecLenf(ctrl->bone->tail, edge->bone->tail) < 0.0001;
+                                                       
+                                                       if (fit)
+                                                       {
+                                                               /* pick the bone on the arc with the lowest symmetry level
+                                                                * means you connect control to the trunk of the skeleton */
+                                                               if (best_arc == NULL || arc->symmetry_level < best_arc->symmetry_level)
+                                                               {
+                                                                       best_arc = arc;
+                                                                       link = edge->bone;
+                                                               }
+                                                       }
+                                               }
+                                       }
+                               }
+                               
+                               found = RIG_parentControl(ctrl, link);
+                       }
+               }
+               
+               /* if not found yet, check child */             
+               if (found == 0)
+               {
+                       RigArc *arc;
+                       RigArc *best_arc = NULL;
+                       EditBone *link = NULL;
+                       
+                       for (arc = rg->arcs.first; arc; arc = arc->next)
+                       {
+                               RigEdge *edge;
+                               for (edge = arc->edges.first; edge; edge = edge->next)
+                               {
+                                       if (edge->bone && edge->bone->parent == ctrl->bone)
+                                       {
+                                               /* pick the bone on the arc with the lowest symmetry level
+                                                * means you connect control to the trunk of the skeleton */
+                                               if (best_arc == NULL || arc->symmetry_level < best_arc->symmetry_level)
+                                               {
+                                                       best_arc = arc;
+                                                       link = edge->bone;
+                                               }
+                                       }
+                               }
+                       }
+                       
+                       found = RIG_parentControl(ctrl, link);
+               }
+
+       }
+       
+       
+       /* second pass, make chains in control bones */
+       while (change)
+       {
+               change = 0;
+               
+               printf("-------------------------\n");
+               
+               for (ctrl = rg->controls.first; ctrl; ctrl = ctrl->next)
+               {
+                       /* if control is not linked yet */
+                       if (ctrl->link == NULL)
+                       {
+                               bPoseChannel *pchan;
+                               bConstraint *con;
+                               RigControl *ctrl_parent = NULL;
+                               RigControl *ctrl_child;
+                               int found = 0;
+
+                               if (ctrl->bone->parent)
+                               {
+                                       ctrl_parent = BLI_ghash_lookup(rg->controls_map, ctrl->bone->parent->name);
+                               }
+
+                               /* check constraints first */
+                               
+                               /* DO SOME MAGIC HERE */
+                               for (pchan= rg->ob->pose->chanbase.first; pchan; pchan= pchan->next)
+                               {
+                                       for (con= pchan->constraints.first; con; con= con->next) 
+                                       {
+                                               bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
+                                               ListBase targets = {NULL, NULL};
+                                               bConstraintTarget *ct;
+                                               
+                                               /* constraint targets */
+                                               if (cti && cti->get_constraint_targets)
+                                               {
+                                                       cti->get_constraint_targets(con, &targets);
+                                                       
+                                                       for (ct= targets.first; ct; ct= ct->next)
+                                                       {
+                                                               if ((ct->tar == rg->ob) && strcmp(ct->subtarget, ctrl->bone->name) == 0)
+                                                               {
+                                                                       /* SET bone link to ctrl corresponding to pchan */
+                                                                       RigControl *link = BLI_ghash_lookup(rg->controls_map, pchan->name);
+
+                                                                       /* if owner is a control bone, link with it */                                                                  
+                                                                       if (link && link->link)
+                                                                       {
+                                                                               printf("%s -constraint- %s\n", ctrl->bone->name, link->bone->name);
+                                                                               RIG_parentControl(ctrl, link->bone);
+                                                                               found = 1;
+                                                                               break;
+                                                                       }
+                                                               }
+                                                       }
+                                                       
+                                                       if (cti->flush_constraint_targets)
+                                                               cti->flush_constraint_targets(con, &targets, 0);
+                                               }
+                                       }
+                               }                       
+
+                               if (found == 0)
+                               {
+                                       /* check if parent is already linked */
+                                       if (ctrl_parent && ctrl_parent->link)
+                                       {
+                                               printf("%s -parent- %s\n", ctrl->bone->name, ctrl_parent->bone->name);
+                                               RIG_parentControl(ctrl, ctrl_parent->bone);
+                                               change = 1;
+                                       }
+                                       else
+                                       {
+                                               /* check childs */
+                                               for (ctrl_child = rg->controls.first; ctrl_child; ctrl_child = ctrl_child->next)
+                                               {
+                                                       /* if a child is linked, link to that one */
+                                                       if (ctrl_child->link && ctrl_child->bone->parent == ctrl->bone)
+                                                       {
+                                                               printf("%s -child- %s\n", ctrl->bone->name, ctrl_child->bone->name);
+                                                               RIG_parentControl(ctrl, ctrl_child->bone);
+                                                               change = 1;
+                                                               break;
+                                                       }
+                                               }
+                                       }
+                               }
+                       }
+               }
+               
+       }
+}
+
+/*******************************************************************************************************/
+
+static void RIG_joinArcs(RigGraph *rg, RigNode *node, RigArc *joined_arc1, RigArc *joined_arc2)
+{
+       RigEdge *edge, *next_edge;
+       
+       /* ignore cases where joint is at start or end */
+       if (joined_arc1->head == joined_arc2->head || joined_arc1->tail == joined_arc2->tail)
+       {
+               return;
+       }
+       
+       /* swap arcs to make sure arc1 is before arc2 */
+       if (joined_arc1->head == joined_arc2->tail)
+       {
+               RigArc *tmp = joined_arc1;
+               joined_arc1 = joined_arc2;
+               joined_arc2 = tmp;
+       }
+       
+       for (edge = joined_arc2->edges.first; edge; edge = next_edge)
+       {
+               next_edge = edge->next;
+               
+               RIG_appendEdgeToArc(joined_arc1, edge);
+       }
+       
+       joined_arc1->tail = joined_arc2->tail;
+       
+       joined_arc2->edges.first = joined_arc2->edges.last = NULL;
+       
+       BLI_removeArc((BGraph*)rg, (BArc*)joined_arc2);
+       
+       BLI_removeNode((BGraph*)rg, (BNode*)node);
+}
+
+static void RIG_removeNormalNodes(RigGraph *rg)
+{
+       RigNode *node, *next_node;
+       
+       for (node = rg->nodes.first; node; node = next_node)
+       {
+               next_node = node->next;
+               
+               if (node->degree == 2)
+               {
+                       RigArc *arc, *joined_arc1 = NULL, *joined_arc2 = NULL;
+                       
+                       for (arc = rg->arcs.first; arc; arc = arc->next)
+                       {
+                               if (arc->head == node || arc->tail == node)
+                               {
+                                       if (joined_arc1 == NULL)
+                                       {
+                                               joined_arc1 = arc;
+                                       }
+                                       else
+                                       {
+                                               joined_arc2 = arc;
+                                               break;
+                                       }
+                               }
+                       }
+                       
+                       RIG_joinArcs(rg, node, joined_arc1, joined_arc2);
+               }
+       }
+}
+
+static void RIG_removeUneededOffsets(RigGraph *rg)
+{
+       RigArc *arc;
+       
+       for (arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               RigEdge *first_edge, *last_edge;
+               
+               first_edge = arc->edges.first;
+               last_edge = arc->edges.last;
+               
+               if (first_edge->bone == NULL)
+               {
+                       if (first_edge->bone == NULL && VecLenf(first_edge->tail, arc->head->p) <= 0.001)
+                       {
+                               BLI_remlink(&arc->edges, first_edge);
+                               MEM_freeN(first_edge);
+                       }
+                       else if (arc->head->degree == 1)
+                       {
+                               RigNode *new_node = (RigNode*)BLI_FindNodeByPosition((BGraph*)rg, first_edge->tail, 0.001);
+                               
+                               if (new_node)
+                               {
+                                       BLI_remlink(&arc->edges, first_edge);
+                                       MEM_freeN(first_edge);
+                                       BLI_replaceNodeInArc((BGraph*)rg, (BArc*)arc, (BNode*)new_node, (BNode*)arc->head);
+                               }
+                               else
+                               {
+                                       RigEdge *next_edge = first_edge->next;
+       
+                                       if (next_edge)
+                                       {
+                                               BLI_remlink(&arc->edges, first_edge);
+                                               MEM_freeN(first_edge);
+                                               
+                                               VECCOPY(arc->head->p, next_edge->head);
+                                       }
+                               }
+                       }
+                       else
+                       {
+                               /* check if all arc connected start with a null edge */
+                               RigArc *other_arc;
+                               for (other_arc = rg->arcs.first; other_arc; other_arc = other_arc->next)
+                               {
+                                       if (other_arc != arc)
+                                       {
+                                               RigEdge *test_edge;
+                                               if (other_arc->head == arc->head)
+                                               {
+                                                       test_edge = other_arc->edges.first;
+                                                       
+                                                       if (test_edge->bone != NULL)
+                                                       {
+                                                               break;
+                                                       }
+                                               }
+                                               else if (other_arc->tail == arc->head)
+                                               {
+                                                       test_edge = other_arc->edges.last;
+                                                       
+                                                       if (test_edge->bone != NULL)
+                                                       {
+                                                               break;
+                                                       }
+                                               }
+                                       }
+                               }
+                               
+                               if (other_arc == NULL)
+                               {
+                                       RigNode *new_node = (RigNode*)BLI_FindNodeByPosition((BGraph*)rg, first_edge->tail, 0.001);
+                                       
+                                       if (new_node)
+                                       {
+                                               /* remove null edge in other arcs too */
+                                               for (other_arc = rg->arcs.first; other_arc; other_arc = other_arc->next)
+                                               {
+                                                       if (other_arc != arc)
+                                                       {
+                                                               RigEdge *test_edge;
+                                                               if (other_arc->head == arc->head)
+                                                               {
+                                                                       BLI_replaceNodeInArc((BGraph*)rg, (BArc*)other_arc, (BNode*)new_node, (BNode*)other_arc->head);
+                                                                       test_edge = other_arc->edges.first;
+                                                                       BLI_remlink(&other_arc->edges, test_edge);
+                                                                       MEM_freeN(test_edge);
+                                                               }
+                                                               else if (other_arc->tail == arc->head)
+                                                               {
+                                                                       BLI_replaceNodeInArc((BGraph*)rg, (BArc*)other_arc, (BNode*)new_node, (BNode*)other_arc->tail);
+                                                                       test_edge = other_arc->edges.last;
+                                                                       BLI_remlink(&other_arc->edges, test_edge);
+                                                                       MEM_freeN(test_edge);
+                                                               }
+                                                       }
+                                               }
+                                               
+                                               BLI_remlink(&arc->edges, first_edge);
+                                               MEM_freeN(first_edge);
+                                               BLI_replaceNodeInArc((BGraph*)rg, (BArc*)arc, (BNode*)new_node, (BNode*)arc->head);
+                                       }
+                                       else
+                                       {
+                                               RigEdge *next_edge = first_edge->next;
+               
+                                               if (next_edge)
+                                               {
+                                                       BLI_remlink(&arc->edges, first_edge);
+                                                       MEM_freeN(first_edge);
+                                                       
+                                                       VECCOPY(arc->head->p, next_edge->head);
+                                                       
+                                                       /* remove null edge in other arcs too */
+                                                       for (other_arc = rg->arcs.first; other_arc; other_arc = other_arc->next)
+                                                       {
+                                                               if (other_arc != arc)
+                                                               {
+                                                                       RigEdge *test_edge;
+                                                                       if (other_arc->head == arc->head)
+                                                                       {
+                                                                               test_edge = other_arc->edges.first;
+                                                                               BLI_remlink(&other_arc->edges, test_edge);
+                                                                               MEM_freeN(test_edge);
+                                                                       }
+                                                                       else if (other_arc->tail == arc->head)
+                                                                       {
+                                                                               test_edge = other_arc->edges.last;
+                                                                               BLI_remlink(&other_arc->edges, test_edge);
+                                                                               MEM_freeN(test_edge);
+                                                                       }
+                                                               }
+                                                       }
+                                               }
+                                       }
+                               }
+                       }
+               }
+               
+               if (last_edge->bone == NULL)
+               {
+                       if (VecLenf(last_edge->head, arc->tail->p) <= 0.001)
+                       {
+                               BLI_remlink(&arc->edges, last_edge);
+                               MEM_freeN(last_edge);
+                       }
+                       else if (arc->tail->degree == 1)
+                       {
+                               RigNode *new_node = (RigNode*)BLI_FindNodeByPosition((BGraph*)rg, last_edge->head, 0.001);
+                               
+                               if (new_node)
+                               {
+                                       RigEdge *previous_edge = last_edge->prev;
+                                       
+                                       BLI_remlink(&arc->edges, last_edge);
+                                       MEM_freeN(last_edge);
+                                       BLI_replaceNodeInArc((BGraph*)rg, (BArc*)arc, (BNode*)new_node, (BNode*)arc->tail);
+                                       
+                                       /* set previous angle to 0, since there's no following edges */
+                                       if (previous_edge)
+                                       {
+                                               previous_edge->angle = 0;
+                                       }
+                               }
+                               else
+                               {
+                                       RigEdge *previous_edge = last_edge->prev;
+       
+                                       if (previous_edge)
+                                       {
+                                               BLI_remlink(&arc->edges, last_edge);
+                                               MEM_freeN(last_edge);
+                                               
+                                               VECCOPY(arc->tail->p, previous_edge->tail);
+                                               previous_edge->angle = 0;
+                                       }
+                               }
+                       }
+               }
+       }
+}
+
+static void RIG_arcFromBoneChain(RigGraph *rg, ListBase *list, EditBone *root_bone, RigNode *starting_node)
+{
+       EditBone *bone, *last_bone = root_bone;
+       RigArc *arc = NULL;
+       int contain_head = 0;
+       
+       for(bone = root_bone; bone; bone = nextEditBoneChild(list, bone, 0))
+       {
+               int nb_children;
+               
+               if ((bone->flag & BONE_NO_DEFORM) == 0)
+               {
+                       BLI_ghash_insert(rg->bones_map, bone->name, bone);
+               
+                       if (arc == NULL)
+                       {
+                               arc = newRigArc(rg);
+                               
+                               if (starting_node == NULL)
+                               {
+                                       starting_node = newRigNodeHead(rg, arc, root_bone->head);
+                               }
+                               else
+                               {
+                                       addRigNodeHead(rg, arc, starting_node);
+                               }
+                       }
+                       
+                       if (bone->parent && (bone->flag & BONE_CONNECTED) == 0)
+                       {
+                               RIG_addEdgeToArc(arc, bone->head, NULL);
+                       }
+                       
+                       RIG_addEdgeToArc(arc, bone->tail, bone);
+                       
+                       last_bone = bone;
+                       
+                       if (strcmp(bone->name, "head") == 0)
+                       {
+                               contain_head = 1;
+                       }
+               }
+               else if ((bone->flag & BONE_EDITMODE_LOCKED) == 0) /* ignore locked bones */
+               {
+                       RIG_addControlBone(rg, bone);
+               }
+               
+               nb_children = countEditBoneChildren(list, bone);
+               if (nb_children > 1)
+               {
+                       RigNode *end_node = NULL;
+                       int i;
+                       
+                       if (arc != NULL)
+                       {
+                               end_node = newRigNodeTail(rg, arc, bone->tail);
+                       }
+                       else
+                       {
+                               end_node = newRigNode(rg, bone->tail);
+                       }
+
+                       for (i = 0; i < nb_children; i++)
+                       {
+                               root_bone = nextEditBoneChild(list, bone, i);
+                               RIG_arcFromBoneChain(rg, list, root_bone, end_node);
+                       }
+                       
+                       /* arc ends here, break */
+                       break;
+               }
+       }
+       
+       /* If the loop exited without forking */
+       if (arc != NULL && bone == NULL)
+       {
+               newRigNodeTail(rg, arc, last_bone->tail);
+       }
+
+       if (contain_head)
+       {
+               rg->head = arc->tail;
+       }
+}
+
+/*******************************************************************************************************/
+static void RIG_findHead(RigGraph *rg)
+{
+       if (rg->head == NULL)
+       {
+               if (BLI_countlist(&rg->arcs) == 1)
+               {
+                       RigArc *arc = rg->arcs.first;
+                       
+                       rg->head = (RigNode*)arc->head;
+               }
+               else
+               {
+                       RigArc *arc;
+                       
+                       for (arc = rg->arcs.first; arc; arc = arc->next)
+                       {
+                               RigEdge *edge = arc->edges.last;
+                               
+                               if (edge->bone->flag & (BONE_TIPSEL|BONE_SELECTED))
+                               {
+                                       rg->head = arc->tail;
+                                       break;
+                               }
+                       }
+               }
+               
+               if (rg->head == NULL)
+               {
+                       rg->head = rg->nodes.first;
+               }
+       }
+}
+
+/*******************************************************************************************************/
+
+void RIG_printNode(RigNode *node, char name[])
+{
+       printf("%s %p %i <%0.3f, %0.3f, %0.3f>\n", name, node, node->degree, node->p[0], node->p[1], node->p[2]);
+       
+       if (node->symmetry_flag & SYM_TOPOLOGICAL)
+       {
+               if (node->symmetry_flag & SYM_AXIAL)
+                       printf("Symmetry AXIAL\n");
+               else if (node->symmetry_flag & SYM_RADIAL)
+                       printf("Symmetry RADIAL\n");
+                       
+               printvecf("symmetry axis", node->symmetry_axis);
+       }
+}
+
+void RIG_printArcBones(RigArc *arc)
+{
+       RigEdge *edge;
+
+       for (edge = arc->edges.first; edge; edge = edge->next)
+       {
+               if (edge->bone)
+                       printf("%s ", edge->bone->name);
+               else
+                       printf("---- ");
+       }
+       printf("\n");
+}
+
+void RIG_printCtrl(RigControl *ctrl, char *indent)
+{
+       char text[128];
+       
+       printf("%sBone: %s\n", indent, ctrl->bone->name);
+       printf("%sLink: %s\n", indent, ctrl->link ? ctrl->link->name : "!NONE!");
+       
+       sprintf(text, "%soffset", indent);
+       printvecf(text, ctrl->offset);
+       
+       printf("%sFlag: %i\n", indent, ctrl->flag);
+}
+
+void RIG_printLinkedCtrl(RigGraph *rg, EditBone *bone, int tabs)
+{
+       RigControl *ctrl;
+       char indent[64];
+       char *s = indent;
+       int i;
+       
+       for (i = 0; i < tabs; i++)
+       {
+               s[0] = '\t';
+               s++;
+       }
+       s[0] = 0;
+       
+       for (ctrl = rg->controls.first; ctrl; ctrl = ctrl->next)
+       {
+               if (ctrl->link == bone)
+               {
+                       RIG_printCtrl(ctrl, indent);
+                       RIG_printLinkedCtrl(rg, ctrl->bone, tabs + 1);
+               }
+       }
+}
+
+void RIG_printArc(RigGraph *rg, RigArc *arc)
+{
+       RigEdge *edge;
+
+       RIG_printNode((RigNode*)arc->head, "head");
+
+       for (edge = arc->edges.first; edge; edge = edge->next)
+       {
+               printf("\tinner joints %0.3f %0.3f %0.3f\n", edge->tail[0], edge->tail[1], edge->tail[2]);
+               printf("\t\tlength %f\n", edge->length);
+               printf("\t\tangle %f\n", edge->angle * 180 / M_PI);
+               if (edge->bone)
+               {
+                       printf("\t\t%s\n", edge->bone->name);
+                       RIG_printLinkedCtrl(rg, edge->bone, 3);
+               }
+       }       
+       printf("symmetry level: %i flag: %i group %i\n", arc->symmetry_level, arc->symmetry_flag, arc->symmetry_group);
+
+       RIG_printNode((RigNode*)arc->tail, "tail");
+}
+
+void RIG_printGraph(RigGraph *rg)
+{
+       RigArc *arc;
+
+       printf("---- ARCS ----\n");
+       for (arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               RIG_printArc(rg, arc);  
+               printf("\n");
+       }
+
+       if (rg->head)
+       {
+               RIG_printNode(rg->head, "HEAD NODE:");
+       }
+       else
+       {
+               printf("HEAD NODE: NONE\n");
+       }       
+}
+
+/*******************************************************************************************************/
+
+static RigGraph *armatureToGraph(Object *ob, bArmature *arm)
+{
+       EditBone *ebone;
+       RigGraph *rg;
+       
+       rg = newRigGraph();
+       
+       make_boneList(&rg->editbones, &arm->bonebase, NULL);
+       rg->ob = ob;
+
+       /* Do the rotations */
+       for (ebone = rg->editbones.first; ebone; ebone=ebone->next){
+               if (ebone->parent == NULL)
+               {
+                       RIG_arcFromBoneChain(rg, &rg->editbones, ebone, NULL);
+               }
+       }
+       
+       BLI_removeDoubleNodes((BGraph*)rg, 0.001);
+       
+       RIG_removeNormalNodes(rg);
+       
+       RIG_removeUneededOffsets(rg);
+       
+       BLI_buildAdjacencyList((BGraph*)rg);
+       
+       RIG_findHead(rg);
+
+       BLI_markdownSymmetry((BGraph*)rg, (BNode*)rg->head, G.scene->toolsettings->skgen_symmetry_limit);
+       
+       RIG_reconnectControlBones(rg); /* after symmetry, because we use levels to find best match */
+       
+       if (BLI_isGraphCyclic((BGraph*)rg))
+       {
+               printf("armature cyclic\n");
+       }
+       
+       return rg;
+}
+
+/************************************ GENERATING *****************************************************/
+
+static EditBone *add_editbonetolist(char *name, ListBase *list)
+{
+       EditBone *bone= MEM_callocN(sizeof(EditBone), "eBone");
+       
+       BLI_strncpy(bone->name, name, 32);
+       unique_editbone_name(list, bone->name);
+       
+       BLI_addtail(list, bone);
+       
+       bone->flag |= BONE_TIPSEL;
+       bone->weight= 1.0F;
+       bone->dist= 0.25F;
+       bone->xwidth= 0.1;
+       bone->zwidth= 0.1;
+       bone->ease1= 1.0;
+       bone->ease2= 1.0;
+       bone->rad_head= 0.10;
+       bone->rad_tail= 0.05;
+       bone->segments= 1;
+       bone->layer=  1;//arm->layer;
+       
+       return bone;
+}
+
+EditBone * generateBonesForArc(RigGraph *rigg, ReebArc *arc, ReebNode *head, ReebNode *tail)
+{
+       ReebArcIterator iter;
+       float n[3];
+       float ADAPTIVE_THRESHOLD = G.scene->toolsettings->skgen_correlation_limit;
+       EditBone *lastBone = NULL;
+       
+       /* init iterator to get start and end from head */
+       initArcIterator(&iter, arc, head);
+       
+       /* Calculate overall */
+       VecSubf(n, arc->buckets[iter.end].p, head->p);
+       
+       if (1 /* G.scene->toolsettings->skgen_options & SKGEN_CUT_CORRELATION */ )
+       {
+               EmbedBucket *bucket = NULL;
+               EmbedBucket *previous = NULL;
+               EditBone *child = NULL;
+               EditBone *parent = NULL;
+               float normal[3] = {0, 0, 0};
+               float avg_normal[3];
+               int total = 0;
+               int boneStart = iter.start;
+               
+               parent = add_editbonetolist("Bone", &rigg->editbones);
+               parent->flag = BONE_SELECTED|BONE_TIPSEL|BONE_ROOTSEL;
+               VECCOPY(parent->head, head->p);
+               
+               for (previous = nextBucket(&iter), bucket = nextBucket(&iter);
+                       bucket;
+                       previous = bucket, bucket = nextBucket(&iter))
+               {
+                       float btail[3];
+                       float value = 0;
+
+                       if (G.scene->toolsettings->skgen_options & SKGEN_STICK_TO_EMBEDDING)
+                       {
+                               VECCOPY(btail, bucket->p);
+                       }
+                       else
+                       {
+                               float length;
+                               
+                               /* Calculate normal */
+                               VecSubf(n, bucket->p, parent->head);
+                               length = Normalize(n);
+                               
+                               total += 1;
+                               VecAddf(normal, normal, n);
+                               VECCOPY(avg_normal, normal);
+                               VecMulf(avg_normal, 1.0f / total);
+                                
+                               VECCOPY(btail, avg_normal);
+                               VecMulf(btail, length);
+                               VecAddf(btail, btail, parent->head);
+                       }
+
+                       if (G.scene->toolsettings->skgen_options & SKGEN_ADAPTIVE_DISTANCE)
+                       {
+                               value = calcDistance(arc, boneStart, iter.index, parent->head, btail);
+                       }
+                       else
+                       {
+                               float n[3];
+                               
+                               VecSubf(n, btail, parent->head);
+                               value = calcVariance(arc, boneStart, iter.index, parent->head, n);
+                       }
+
+                       if (value > ADAPTIVE_THRESHOLD)
+                       {
+                               VECCOPY(parent->tail, btail);
+
+                               child = add_editbonetolist("Bone", &rigg->editbones);
+                               VECCOPY(child->head, parent->tail);
+                               child->parent = parent;
+                               child->flag |= BONE_CONNECTED|BONE_SELECTED|BONE_TIPSEL|BONE_ROOTSEL;
+                               
+                               parent = child; // new child is next parent
+                               boneStart = iter.index; // start from end
+                               
+                               normal[0] = normal[1] = normal[2] = 0;
+                               total = 0;
+                       }
+               }
+
+               VECCOPY(parent->tail, tail->p);
+               
+               lastBone = parent; /* set last bone in the chain */
+       }
+       
+       return lastBone;
+}
+
+void generateMissingArcsFromNode(RigGraph *rigg, ReebNode *node, int multi_level_limit)
+{
+       while (node->multi_level > multi_level_limit && node->link_up)
+       {
+               node = node->link_up;
+       }
+       
+       while (node->multi_level < multi_level_limit && node->link_down)
+       {
+               node = node->link_down;
+       }
+       
+       if (node->multi_level == multi_level_limit)
+       {
+               int i;
+               
+               for (i = 0; i < node->degree; i++)
+               {
+                       ReebArc *earc = node->arcs[i];
+                       
+                       if (earc->flag == ARC_FREE && earc->head == node)
+                       {
+                               ReebNode *other = BIF_otherNodeFromIndex(earc, node);
+                               
+                               earc->flag = ARC_USED;
+                               
+                               generateBonesForArc(rigg, earc, node, other);
+                               generateMissingArcsFromNode(rigg, other, multi_level_limit);
+                       }
+               }
+       }
+}
+
+void generateMissingArcs(RigGraph *rigg)
+{
+       ReebGraph *reebg = rigg->link_mesh;
+       int multi_level_limit = 5;
+       
+       for (reebg = rigg->link_mesh; reebg; reebg = reebg->link_up)
+       {
+               ReebArc *earc;
+               
+               for (earc = reebg->arcs.first; earc; earc = earc->next)
+               {
+                       if (earc->flag == ARC_USED)
+                       {
+                               generateMissingArcsFromNode(rigg, earc->head, multi_level_limit);
+                               generateMissingArcsFromNode(rigg, earc->tail, multi_level_limit);
+                       }
+               }
+       }
+}
+
+/************************************ RETARGETTING *****************************************************/
+
+static void repositionControl(RigGraph *rigg, RigControl *ctrl, float head[3], float tail[3], float qrot[4], float resize)
+{
+       RigControl *ctrl_child;
+       float parent_offset[3], tail_offset[3];
+       
+       VecSubf(tail_offset, ctrl->tail, ctrl->head);
+       VecMulf(tail_offset, resize);
+       
+       VECCOPY(parent_offset, ctrl->offset);
+       VecMulf(parent_offset, resize);
+       
+       QuatMulVecf(qrot, parent_offset);
+       QuatMulVecf(qrot, tail_offset);
+       
+       VecAddf(ctrl->bone->head, head, parent_offset); 
+       VecAddf(ctrl->bone->tail, ctrl->bone->head, tail_offset);
+       ctrl->bone->roll = getNewBoneRoll(ctrl->bone, ctrl->up_axis, qrot);
+       
+       ctrl->flag |= RIG_CTRL_DONE;
+
+       /* Cascade to connected control bones */
+       for (ctrl_child = rigg->controls.first; ctrl_child; ctrl_child = ctrl_child->next)
+       {
+               if (ctrl_child->link == ctrl->bone)
+               {
+                       repositionControl(rigg, ctrl_child, ctrl->bone->head, ctrl->bone->tail, qrot, resize);
+               }
+       }
+
+}
+
+static void repositionBone(RigGraph *rigg, RigEdge *edge, float vec0[3], float vec1[3])
+{
+       EditBone *bone;
+       RigControl *ctrl;
+       float qrot[4], resize;
+       float v1[3], v2[3];
+       float l1, l2;
+       
+       bone = edge->bone;
+       
+       VecSubf(v1, edge->tail, edge->head);
+       VecSubf(v2, vec1, vec0);
+       
+       l1 = Normalize(v1);
+       l2 = Normalize(v2);
+
+       resize = l2 / l1;
+       
+       RotationBetweenVectorsToQuat(qrot, v1, v2);
+       
+       for (ctrl = rigg->controls.first; ctrl; ctrl = ctrl->next)
+       {
+               if (ctrl->link == bone)
+               {
+                       repositionControl(rigg, ctrl, vec0, vec1, qrot, resize);
+               }
+       }
+       
+       VECCOPY(bone->head, vec0);
+       VECCOPY(bone->tail, vec1);
+       bone->roll = getNewBoneRoll(bone, edge->up_axis, qrot);
+}
+
+static RetargetMode detectArcRetargetMode(RigArc *arc);
+static void retargetArctoArcLength(RigGraph *rigg, RigArc *iarc, RigNode *inode_start);
+
+
+static RetargetMode detectArcRetargetMode(RigArc *iarc)
+{
+       RetargetMode mode = RETARGET_AGGRESSIVE;
+       ReebArc *earc = iarc->link_mesh;
+       RigEdge *edge;
+       int large_angle = 0;
+       float avg_angle = 0;
+       float avg_length = 0;
+       int nb_edges = 0;
+       
+       
+       for (edge = iarc->edges.first; edge; edge = edge->next)
+       {
+               avg_angle += edge->angle;
+               nb_edges++;
+       }
+       
+       avg_angle /= nb_edges - 1; /* -1 because last edge doesn't have an angle */
+
+       avg_length = iarc->length / nb_edges;
+       
+       
+       if (nb_edges > 2)
+       {
+               for (edge = iarc->edges.first; edge; edge = edge->next)
+               {
+                       if (fabs(edge->angle - avg_angle) > M_PI / 6)
+                       {
+                               large_angle = 1;
+                       }
+               }
+       }
+       else if (nb_edges == 2 && avg_angle > 0)
+       {
+               large_angle = 1;
+       }
+               
+       
+       if (large_angle == 0)
+       {
+               mode = RETARGET_LENGTH;
+       }
+       
+       if (earc->bcount <= (iarc->count - 1))
+       {
+               mode = RETARGET_LENGTH;
+       }
+       
+       mode = RETARGET_AGGRESSIVE;
+       
+       return mode;
+}
+
+#ifndef USE_THREADS
+static void printCostCube(float *cost_cube, int nb_joints)
+{
+       int i;
+       
+       for (i = 0; i < nb_joints; i++)
+       {
+               printf("%0.3f ", cost_cube[3 * i]);
+       }
+       printf("\n");
+
+       for (i = 0; i < nb_joints; i++)
+       {
+               printf("%0.3f ", cost_cube[3 * i + 1]);
+       }
+       printf("\n");
+
+       for (i = 0; i < nb_joints; i++)
+       {
+               printf("%0.3f ", cost_cube[3 * i + 2]);
+       }
+       printf("\n");
+}
+
+static void printMovesNeeded(int *positions, int nb_positions)
+{
+       int moves = 0;
+       int i;
+       
+       for (i = 0; i < nb_positions; i++)
+       {
+               moves += positions[i] - (i + 1);
+       }
+       
+       printf("%i moves needed\n", moves);
+}
+
+static void printPositions(int *positions, int nb_positions)
+{
+       int i;
+       
+       for (i = 0; i < nb_positions; i++)
+       {
+               printf("%i ", positions[i]);
+       }
+       printf("\n");
+}
+#endif
+
+#define MAX_COST 100 /* FIX ME */
+
+static float costDistance(ReebArcIterator *iter, float *vec0, float *vec1, int i0, int i1)
+{
+       EmbedBucket *bucket = NULL;
+       float max_dist = 0;
+       float v1[3], v2[3], c[3];
+       float v1_inpf;
+
+       if (G.scene->toolsettings->skgen_retarget_distance_weight > 0)
+       {
+               VecSubf(v1, vec0, vec1);
+               
+               v1_inpf = Inpf(v1, v1);
+               
+               if (v1_inpf > 0)
+               {
+                       int j;
+                       for (j = i0 + 1; j < i1 - 1; j++)
+                       {
+                               float dist;
+                               
+                               bucket = peekBucket(iter, j);
+       
+                               VecSubf(v2, bucket->p, vec1);
+               
+                               Crossf(c, v1, v2);
+                               
+                               dist = Inpf(c, c) / v1_inpf;
+                               
+                               max_dist = dist > max_dist ? dist : max_dist;
+                       }
+                       
+                       return G.scene->toolsettings->skgen_retarget_distance_weight * max_dist;
+               }
+               else
+               {
+                       return MAX_COST;
+               }
+       }
+       else
+       {
+               return 0;
+       }
+}
+
+static float costAngle(float original_angle, float vec_first[3], float vec_second[3])
+{
+       if (G.scene->toolsettings->skgen_retarget_angle_weight > 0)
+       {
+               float current_angle;
+               
+               if (!VecIsNull(vec_first) && !VecIsNull(vec_second))
+               {
+                       current_angle = saacos(Inpf(vec_first, vec_second));
+
+                       return G.scene->toolsettings->skgen_retarget_angle_weight * fabs(current_angle - original_angle);
+               }
+               else
+               {
+                       return G.scene->toolsettings->skgen_retarget_angle_weight * M_PI;
+               }
+       }
+       else
+       {
+               return 0;
+       }
+}
+
+static float costLength(float original_length, float current_length)
+{
+       if (current_length == 0)
+       {
+               return MAX_COST;
+       }
+       else
+       {
+               float length_ratio = fabs((current_length - original_length) / original_length);
+               return G.scene->toolsettings->skgen_retarget_length_weight * length_ratio * length_ratio;
+       }
+}
+
+static float calcCostLengthDistance(ReebArcIterator *iter, float **vec_cache, RigEdge *edge, float *vec1, float *vec2, int i1, int i2)
+{
+       float vec[3];
+       float length;
+
+       VecSubf(vec, vec2, vec1);
+       length = Normalize(vec);
+
+       return costLength(edge->length, length) + costDistance(iter, vec1, vec2, i1, i2);
+}
+
+static float calcCostAngleLengthDistance(ReebArcIterator *iter, float **vec_cache, RigEdge *edge, float *vec0, float *vec1, float *vec2, int i1, int i2)
+{
+       float vec_second[3], vec_first[3];
+       float length2;
+       float new_cost = 0;
+
+       VecSubf(vec_second, vec2, vec1);
+       length2 = Normalize(vec_second);
+
+
+       /* Angle cost */        
+       if (edge->prev)
+       {
+               VecSubf(vec_first, vec1, vec0); 
+               Normalize(vec_first);
+               
+               new_cost += costAngle(edge->prev->angle, vec_first, vec_second);
+       }
+
+       /* Length cost */
+       new_cost += costLength(edge->length, length2);
+
+       /* Distance cost */
+       new_cost += costDistance(iter, vec1, vec2, i1, i2);
+
+       return new_cost;
+}
+
+static float calcCost(ReebArcIterator *iter, RigEdge *e1, RigEdge *e2, float *vec0, float *vec1, float *vec2, int i0, int i1, int i2)
+{
+       float vec_second[3], vec_first[3];
+       float length1, length2;
+       float new_cost = 0;
+
+       VecSubf(vec_second, vec2, vec1);
+       length2 = Normalize(vec_second);
+
+       VecSubf(vec_first, vec1, vec0); 
+       length1 = Normalize(vec_first);
+
+       /* Angle cost */        
+       new_cost += costAngle(e1->angle, vec_first, vec_second);
+
+       /* Length cost */
+       new_cost += costLength(e1->length, length1);
+       new_cost += costLength(e2->length, length2);
+
+       /* Distance cost */
+       new_cost += costDistance(iter, vec0, vec1, i0, i1);
+       new_cost += costDistance(iter, vec1, vec2, i1, i2);
+
+       return new_cost;
+}
+
+static void calcGradient(RigEdge *e1, RigEdge *e2, ReebArcIterator *iter, int index, int nb_joints, float *cost_cube, int *positions, float **vec_cache)
+{
+       EmbedBucket *bucket = NULL;
+       float *vec0, *vec1, *vec2;
+       float current_cost;
+       int i0, i1, i2;
+       int next_position;
+
+       vec0 = vec_cache[index];
+       vec1 = vec_cache[index + 1];
+       vec2 = vec_cache[index + 2];
+       
+       if (index == 0)
+       {
+               i0 = 0;
+       }
+       else
+       {
+               i0 = positions[index - 1];
+       }
+       
+       i1 = positions[index];
+       
+       if (index +1 == nb_joints)
+       {
+               i2 = iter->length;
+       }
+       else
+       {
+               i2 = positions[index + 1];
+       }
+
+
+       current_cost = calcCost(iter, e1, e2, vec0, vec1, vec2, i0, i1, i2);
+       cost_cube[index * 3 + 1] = current_cost;
+       
+       next_position = positions[index] + 1;
+       
+       if (index + 1 < nb_joints && next_position == positions[index + 1])
+       {
+               cost_cube[index * 3 + 2] = MAX_COST;
+       }
+       else if (next_position > iter->length) /* positions are indexed at 1, so length is last */
+       {
+               cost_cube[index * 3 + 2] = MAX_COST;
+       }
+       else
+       {
+               bucket = peekBucket(iter, next_position);
+               
+               if (bucket == NULL)
+               {
+                       cost_cube[index * 3 + 2] = MAX_COST;
+               }
+               else
+               {
+                       vec1 = bucket->p;
+                       
+                       cost_cube[index * 3 + 2] = calcCost(iter, e1, e2, vec0, vec1, vec2, i0, next_position, i2) - current_cost;
+               }
+       }
+
+       next_position = positions[index] - 1;
+       
+       if (index - 1 > -1 && next_position == positions[index - 1])
+       {
+               cost_cube[index * 3] = MAX_COST;
+       }
+       else if (next_position < 1) /* positions are indexed at 1, so 1 is first */
+       {
+               cost_cube[index * 3] = MAX_COST;
+       }
+       else
+       {
+               bucket = peekBucket(iter, next_position);
+               
+               if (bucket == NULL)
+               {
+                       cost_cube[index * 3] = MAX_COST;
+               }
+               else
+               {
+                       vec1 = bucket->p;
+                       
+                       cost_cube[index * 3] = calcCost(iter, e1, e2, vec0, vec1, vec2, i0, next_position, i2) - current_cost;
+               }
+       }
+}
+
+static float probability(float delta_cost, float temperature)
+{
+       if (delta_cost < 0)
+       {
+               return 1;
+       }
+       else
+       {
+               return (float)exp(delta_cost / temperature);
+       }
+}
+
+static int neighbour(int nb_joints, float *cost_cube, int *moving_joint, int *moving_direction)
+{
+       int total = 0;
+       int chosen = 0;
+       int i;
+       
+       for (i = 0; i < nb_joints; i++)
+       {
+               if (cost_cube[i * 3] < MAX_COST)
+               {
+                       total++;
+               }
+               
+               if (cost_cube[i * 3 + 2] < MAX_COST)
+               {
+                       total++;
+               }
+       }
+       
+       if (total == 0)
+       {
+               return 0;
+       }
+       
+       chosen = (int)(BLI_drand() * total);
+       
+       for (i = 0; i < nb_joints; i++)
+       {
+               if (cost_cube[i * 3] < MAX_COST)
+               {
+                       if (chosen == 0)
+                       {
+                               *moving_joint = i;
+                               *moving_direction = -1;
+                               break;
+                       }
+                       chosen--;
+               }
+               
+               if (cost_cube[i * 3 + 2] < MAX_COST)
+               {
+                       if (chosen == 0)
+                       {
+                               *moving_joint = i;
+                               *moving_direction = 1;
+                               break;
+                       }
+                       chosen--;
+               }
+       }
+       
+       return 1;
+}
+
+static int indexMemoNode(int nb_positions, int previous, int current, int joints_left)
+{
+       return joints_left * nb_positions * nb_positions + current * nb_positions + previous;
+}
+
+static void copyMemoPositions(int *positions, MemoNode *table, int nb_positions, int joints_left)
+{
+       int previous = 0, current = 0;
+       int i = 0;
+       
+       for (i = 0; joints_left > 0; joints_left--, i++)
+       {
+               MemoNode *node;
+               node = table + indexMemoNode(nb_positions, previous, current, joints_left);
+               
+               positions[i] = node->next;
+               
+               previous = current;
+               current = node->next;
+       }
+}
+
+static MemoNode * solveJoints(MemoNode *table, ReebArcIterator *iter, float **vec_cache, int nb_joints, int nb_positions, int previous, int current, RigEdge *edge, int joints_left)
+{
+       MemoNode *node;
+       int index = indexMemoNode(nb_positions, previous, current, joints_left);
+       
+       node = table + index;
+       
+       if (node->weight != 0)
+       {
+               return node;
+       }
+       else if (joints_left == 0)
+       {
+               float *vec1 = vec_cache[current];
+               float *vec2 = vec_cache[nb_positions + 1];
+
+               node->weight = calcCostLengthDistance(iter, vec_cache, edge, vec1, vec2, current, iter->length);
+
+               return node;
+       }
+       else
+       {
+               MemoNode *min_node = NULL;
+               float *vec0 = vec_cache[previous];
+               float *vec1 = vec_cache[current];
+               float min_weight;
+               int min_next;
+               int next;
+               
+               for (next = current + 1; next <= nb_positions - (joints_left - 1); next++)
+               {
+                       MemoNode *next_node;
+                       float *vec2 = vec_cache[next];
+                       float weight = 0;
+                       
+                       /* ADD WEIGHT OF PREVIOUS - CURRENT - NEXT triple */
+                       weight = calcCostAngleLengthDistance(iter, vec_cache, edge, vec0, vec1, vec2, current, next);
+                       
+                       if (weight >= MAX_COST)
+                       {
+                               continue;
+                       }
+                       
+                       /* add node weight */
+                       next_node = solveJoints(table, iter, vec_cache, nb_joints, nb_positions, current, next, edge->next, joints_left - 1);
+                       weight += next_node->weight;
+                       
+                       if (min_node == NULL || weight < min_weight)
+                       {
+                               min_weight = weight;
+                               min_node = next_node;
+                               min_next = next;
+                       }
+               }
+               
+               if (min_node)
+               {
+                       node->weight = min_weight;
+                       node->next = min_next;
+                       return node;
+               }
+               else
+               {
+                       node->weight = MAX_COST;
+                       return node;
+               }
+       }
+       
+}
+
+static int testFlipArc(RigArc *iarc, RigNode *inode_start)
+{
+       ReebArc *earc = iarc->link_mesh;
+       ReebNode *enode_start = BIF_NodeFromIndex(earc, inode_start->link_mesh);
+       
+       /* no flip needed if both nodes are the same */
+       if ((enode_start == earc->head && inode_start == iarc->head) || (enode_start == earc->tail && inode_start == iarc->tail))
+       {
+               return 0;
+       }
+       else
+       {
+               return 1;
+       }
+}
+
+static void retargetArctoArcAggresive(RigGraph *rigg, RigArc *iarc, RigNode *inode_start)
+{
+       ReebArcIterator iter;
+       RigEdge *edge;
+       EmbedBucket *bucket = NULL;
+       ReebNode *node_start, *node_end;
+       ReebArc *earc = iarc->link_mesh;
+       float min_cost = FLT_MAX;
+       float *vec0, *vec1, *vec2;
+       float **vec_cache;
+       float *cost_cache;
+       int *best_positions;
+       int *positions;
+       int nb_edges = BLI_countlist(&iarc->edges);
+       int nb_joints = nb_edges - 1;
+       RetargetMethod method = G.scene->toolsettings->skgen_optimisation_method;
+       int i;
+       
+       if (nb_joints > earc->bcount)
+       {
+               printf("NOT ENOUGH BUCKETS!\n");
+               return;
+       }
+
+       positions = MEM_callocN(sizeof(int) * nb_joints, "Aggresive positions");
+       best_positions = MEM_callocN(sizeof(int) * nb_joints, "Best Aggresive positions");
+       cost_cache = MEM_callocN(sizeof(float) * nb_edges, "Cost cache");
+       vec_cache = MEM_callocN(sizeof(float*) * (nb_edges + 1), "Vec cache");
+       
+       if (testFlipArc(iarc, inode_start))
+       {
+               node_start = earc->tail;
+               node_end = earc->head;
+       }
+       else
+       {
+               node_start = earc->head;
+               node_end = earc->tail;
+       }
+       
+       /* init with first values */
+       for (i = 0; i < nb_joints; i++)
+       {
+               positions[i] = i + 1;
+               //positions[i] = (earc->bcount / nb_edges) * (i + 1);
+       }
+       
+       /* init cost cache */
+       for (i = 0; i < nb_edges; i++)
+       {
+               cost_cache[i] = 0;
+       }
+       
+       vec_cache[0] = node_start->p;
+       vec_cache[nb_edges] = node_end->p;
+
+       if (method == METHOD_MEMOIZE)
+       {
+               int nb_positions = earc->bcount;
+               int nb_memo_nodes = nb_positions * nb_positions * (nb_joints + 1);
+               MemoNode *table = MEM_callocN(nb_memo_nodes * sizeof(MemoNode), "memoization table");
+               MemoNode *result;
+               float **positions_cache = MEM_callocN(sizeof(float*) * (nb_positions + 2), "positions cache");
+               int i;
+               
+               positions_cache[0] = node_start->p;
+               positions_cache[nb_positions + 1] = node_end->p;
+               
+               initArcIterator(&iter, earc, node_start);
+
+               for (i = 1; i <= nb_positions; i++)
+               {
+                       EmbedBucket *bucket = peekBucket(&iter, i);
+                       positions_cache[i] = bucket->p;
+               }
+
+               result = solveJoints(table, &iter, positions_cache, nb_joints, earc->bcount, 0, 0, iarc->edges.first, nb_joints);
+               
+               min_cost = result->weight;
+               copyMemoPositions(best_positions, table, earc->bcount, nb_joints);
+               
+               MEM_freeN(table);
+               MEM_freeN(positions_cache);
+       }
+       /* BRUTE FORCE */
+       else if (method == METHOD_BRUTE_FORCE)
+       {
+               int last_index = 0;
+               int first_pass = 1;
+               int must_move = nb_joints - 1;
+               
+               while(1)
+               {
+                       float cost = 0;
+                       int need_calc = 0;
+                       
+                       /* increment to next possible solution */
+                       
+                       i = nb_joints - 1;
+       
+                       if (first_pass)
+                       {
+                               need_calc = 0;
+                               first_pass = 0;
+                       }
+                       else
+                       {
+                               /* increment positions, starting from the last one
+                                * until a valid increment is found
+                                * */
+                               for (i = must_move; i >= 0; i--)
+                               {
+                                       int remaining_joints = nb_joints - (i + 1); 
+                                       
+                                       positions[i] += 1;
+                                       need_calc = i;
+                                       
+                                       if (positions[i] + remaining_joints <= earc->bcount)
+                                       {
+                                               break;
+                                       }
+                               }
+                       }
+       
+                       if (i == -1)
+                       {
+                               break;
+                       }
+                       
+                       /* reset joints following the last increment*/
+                       for (i = i + 1; i < nb_joints; i++)
+                       {
+                               positions[i] = positions[i - 1] + 1;
+                       }
+               
+                       /* calculating cost */
+                       initArcIterator(&iter, earc, node_start);
+                       
+                       vec0 = NULL;
+                       vec1 = node_start->p;
+                       vec2 = NULL;
+                       
+                       for (edge = iarc->edges.first, i = 0, last_index = 0;
+                                edge;
+                                edge = edge->next, i += 1)
+                       {
+       
+                               if (i >= need_calc)
+                               { 
+                                       float vec_first[3], vec_second[3];
+                                       float length1, length2;
+                                       float new_cost = 0;
+                                       int i1, i2;
+                                       
+                                       if (i < nb_joints)
+                                       {
+                                               i2 = positions[i];
+                                               bucket = peekBucket(&iter, positions[i]);
+                                               vec2 = bucket->p;
+                                               vec_cache[i + 1] = vec2; /* update cache for updated position */
+                                       }
+                                       else
+                                       {
+                                               i2 = iter.length;
+                                               vec2 = node_end->p;
+                                       }
+                                       
+                                       if (i > 0)
+                                       {
+                                               i1 = positions[i - 1];
+                                       }
+                                       else
+                                       {
+                                               i1 = 1;
+                                       }
+                                       
+                                       vec1 = vec_cache[i];
+                                       
+       
+                                       VecSubf(vec_second, vec2, vec1);
+                                       length2 = Normalize(vec_second);
+               
+                                       /* check angle */
+                                       if (i != 0 && G.scene->toolsettings->skgen_retarget_angle_weight > 0)
+                                       {
+                                               RigEdge *previous = edge->prev;
+                                               
+                                               vec0 = vec_cache[i - 1];
+                                               VecSubf(vec_first, vec1, vec0); 
+                                               length1 = Normalize(vec_first);
+                                               
+                                               /* Angle cost */        
+                                               new_cost += costAngle(previous->angle, vec_first, vec_second);
+                                       }
+               
+                                       /* Length Cost */
+                                       new_cost += costLength(edge->length, length2);
+                                       
+                                       /* Distance Cost */
+                                       new_cost += costDistance(&iter, vec1, vec2, i1, i2);
+                                       
+                                       cost_cache[i] = new_cost;
+                               }
+                               
+                               cost += cost_cache[i];
+                               
+                               if (cost > min_cost)
+                               {
+                                       must_move = i;
+                                       break;
+                               }
+                       }
+                       
+                       if (must_move != i || must_move > nb_joints - 1)
+                       {
+                               must_move = nb_joints - 1;
+                       }
+       
+                       /* cost optimizing */
+                       if (cost < min_cost)
+                       {
+                               min_cost = cost;
+                               memcpy(best_positions, positions, sizeof(int) * nb_joints);
+                       }
+               }
+       }
+       /* SIMULATED ANNEALING */
+       else if (method == METHOD_ANNEALING)
+       {
+               RigEdge *previous;
+               float *cost_cube;
+               float cost;
+               int k;
+               int kmax;
+
+               kmax = 100000;
+               
+               BLI_srand(nb_joints);
+               
+               /* [joint: index][position: -1, 0, +1] */
+               cost_cube = MEM_callocN(sizeof(float) * 3 * nb_joints, "Cost Cube");
+               
+               initArcIterator(&iter, earc, node_start);
+
+               /* init vec_cache */
+               for (i = 0; i < nb_joints; i++)
+               {
+                       bucket = peekBucket(&iter, positions[i]);
+                       vec_cache[i + 1] = bucket->p;
+               }
+               
+               cost = 0;
+
+               /* init cost cube */
+               for (previous = iarc->edges.first, edge = previous->next, i = 0;
+                        edge;
+                        previous = edge, edge = edge->next, i += 1)
+               {
+                       calcGradient(previous, edge, &iter, i, nb_joints, cost_cube, positions, vec_cache);
+                       
+                       cost += cost_cube[3 * i + 1];
+               }
+               
+#ifndef USE_THREADS
+               printf("initial cost: %f\n", cost);
+               printf("kmax: %i\n", kmax);
+#endif
+               
+               for (k = 0; k < kmax; k++)
+               {
+                       int status;
+                       int moving_joint = -1;
+                       int move_direction = -1;
+                       float delta_cost;
+                       float temperature;
+                       
+                       status = neighbour(nb_joints, cost_cube, &moving_joint, &move_direction);
+                       
+                       if (status == 0)
+                       {
+                               /* if current state is still a minimum, copy it */
+                               if (cost < min_cost)
+                               {
+                                       min_cost = cost;
+                                       memcpy(best_positions, positions, sizeof(int) * nb_joints);
+                               }
+                               break;
+                       }
+                       
+                       delta_cost = cost_cube[moving_joint * 3 + (1 + move_direction)];
+
+                       temperature = 1 - (float)k / (float)kmax;
+                       if (probability(delta_cost, temperature) > BLI_frand())
+                       {
+                               /* update position */                   
+                               positions[moving_joint] += move_direction;
+                               
+                               /* update vector cache */
+                               bucket = peekBucket(&iter, positions[moving_joint]);
+                               vec_cache[moving_joint + 1] = bucket->p;
+                               
+                               cost += delta_cost;
+       
+                               /* cost optimizing */
+                               if (cost < min_cost)
+                               {
+                                       min_cost = cost;
+                                       memcpy(best_positions, positions, sizeof(int) * nb_joints);
+                               }
+
+                               /* update cost cube */                  
+                               for (previous = iarc->edges.first, edge = previous->next, i = 0;
+                                        edge;
+                                        previous = edge, edge = edge->next, i += 1)
+                               {
+                                       if (i == moving_joint - 1 ||
+                                               i == moving_joint ||
+                                               i == moving_joint + 1)
+                                       {
+                                               calcGradient(previous, edge, &iter, i, nb_joints, cost_cube, positions, vec_cache);
+                                       }
+                               }
+                       }
+               }
+
+               //min_cost = cost;
+               //memcpy(best_positions, positions, sizeof(int) * nb_joints);
+               
+//             printf("k = %i\n", k);
+               
+               
+               MEM_freeN(cost_cube);
+       }       
+
+
+       vec0 = node_start->p;
+       initArcIterator(&iter, earc, node_start);
+       
+#ifndef USE_THREADS
+       printPositions(best_positions, nb_joints);
+       printMovesNeeded(best_positions, nb_joints);
+       printf("min_cost %f\n", min_cost);
+       printf("buckets: %i\n", earc->bcount);
+#endif
+
+       /* set joints to best position */
+       for (edge = iarc->edges.first, i = 0;
+                edge;
+                edge = edge->next, i++)
+       {
+               if (i < nb_joints)
+               {
+                       bucket = peekBucket(&iter, best_positions[i]);
+                       vec1 = bucket->p;
+               }
+               else
+               {
+                       vec1 = node_end->p;
+               }
+               
+               if (edge->bone)
+               {
+                       repositionBone(rigg, edge, vec0, vec1);
+               }
+               
+               vec0 = vec1;
+       }
+       
+       MEM_freeN(positions);
+       MEM_freeN(best_positions);
+       MEM_freeN(cost_cache);
+       MEM_freeN(vec_cache);
+}
+
+static void retargetArctoArcLength(RigGraph *rigg, RigArc *iarc, RigNode *inode_start)
+{
+       ReebArcIterator iter;
+       ReebArc *earc = iarc->link_mesh;
+       ReebNode *node_start, *node_end;
+       RigEdge *edge;
+       EmbedBucket *bucket = NULL;
+       float embedding_length = 0;
+       float *vec0 = NULL;
+       float *vec1 = NULL;
+       float *previous_vec = NULL;
+
+       
+       if (testFlipArc(iarc, inode_start))
+       {
+               node_start = (ReebNode*)earc->tail;
+               node_end = (ReebNode*)earc->head;
+       }
+       else
+       {
+               node_start = (ReebNode*)earc->head;
+               node_end = (ReebNode*)earc->tail;
+       }
+       
+       initArcIterator(&iter, earc, node_start);
+
+       bucket = nextBucket(&iter);
+       
+       vec0 = node_start->p;
+       
+       while (bucket != NULL)
+       {
+               vec1 = bucket->p;
+               
+               embedding_length += VecLenf(vec0, vec1);
+               
+               vec0 = vec1;
+               bucket = nextBucket(&iter);
+       }
+       
+       embedding_length += VecLenf(node_end->p, vec1);
+       
+       /* fit bones */
+       initArcIterator(&iter, earc, node_start);
+
+       bucket = nextBucket(&iter);
+
+       vec0 = node_start->p;
+       previous_vec = vec0;
+       vec1 = bucket->p;
+       
+       for (edge = iarc->edges.first; edge; edge = edge->next)
+       {
+               float new_bone_length = edge->length / iarc->length * embedding_length;
+
+               float length = 0;
+
+               while (bucket && new_bone_length > length)
+               {
+                       length += VecLenf(previous_vec, vec1);
+                       bucket = nextBucket(&iter);
+                       previous_vec = vec1;
+                       vec1 = bucket->p;
+               }
+               
+               if (bucket == NULL)
+               {
+                       vec1 = node_end->p;
+               }
+
+               /* no need to move virtual edges (space between unconnected bones) */           
+               if (edge->bone)
+               {
+                       repositionBone(rigg, edge, vec0, vec1);
+               }
+               
+               vec0 = vec1;
+               previous_vec = vec1;
+       }
+}
+
+static void retargetArctoArc(RigGraph *rigg, RigArc *iarc, RigNode *inode_start)
+{
+#ifdef USE_THREADS
+       RetargetParam *p = MEM_callocN(sizeof(RetargetParam), "RetargetParam");
+       
+       p->rigg = rigg;
+       p->iarc = iarc;
+       p->inode_start = inode_start;
+       
+       BLI_insert_work(rigg->worker, p);
+#else
+       RetargetParam p;
+
+       p.rigg = rigg;
+       p.iarc = iarc;
+       p.inode_start = inode_start;
+       
+       exec_retargetArctoArc(&p);
+#endif
+}
+
+void *exec_retargetArctoArc(void *param)
+{
+       RetargetParam *p = (RetargetParam*)param;
+       RigGraph *rigg = p->rigg;
+       RigArc *iarc = p->iarc; 
+       RigNode *inode_start = p->inode_start;
+       ReebArc *earc = iarc->link_mesh;
+       
+       if (BLI_countlist(&iarc->edges) == 1)
+       {
+               RigEdge *edge = iarc->edges.first;
+
+               if (testFlipArc(iarc, inode_start))
+               {
+                       repositionBone(rigg, edge, earc->tail->p, earc->head->p);
+               }
+               else
+               {
+                       repositionBone(rigg, edge, earc->head->p, earc->tail->p);
+               }
+       }
+       else
+       {
+               RetargetMode mode = detectArcRetargetMode(iarc);
+               
+               if (mode == RETARGET_AGGRESSIVE)
+               {
+                       retargetArctoArcAggresive(rigg, iarc, inode_start);
+               }
+               else
+               {               
+                       retargetArctoArcLength(rigg, iarc, inode_start);
+               }
+       }
+
+#ifdef USE_THREADS
+       MEM_freeN(p);
+#endif
+       
+       return NULL;
+}
+
+static void matchMultiResolutionNode(RigGraph *rigg, RigNode *inode, ReebNode *top_node)
+{
+       ReebNode *enode = top_node;
+       ReebGraph *reebg = BIF_graphForMultiNode(rigg->link_mesh, enode);
+       int ishape, eshape;
+       
+       ishape = BLI_subtreeShape((BGraph*)rigg, (BNode*)inode, NULL, 0) % SHAPE_LEVELS;
+       eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, NULL, 0) % SHAPE_LEVELS;
+       
+       inode->link_mesh = enode;
+
+       while (ishape == eshape && enode->link_down)
+       {
+               inode->link_mesh = enode;
+
+               enode = enode->link_down;
+               reebg = BIF_graphForMultiNode(rigg->link_mesh, enode); /* replace with call to link_down once that exists */
+               eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, NULL, 0) % SHAPE_LEVELS;
+       } 
+}
+
+static void markMultiResolutionChildArc(ReebNode *end_enode, ReebNode *enode)
+{
+       int i;
+       
+       for(i = 0; i < enode->degree; i++)
+       {
+               ReebArc *earc = (ReebArc*)enode->arcs[i];
+               
+               if (earc->flag == ARC_FREE)
+               {
+                       earc->flag = ARC_TAKEN;
+                       
+                       if (earc->tail->degree > 1 && earc->tail != end_enode)
+                       {
+                               markMultiResolutionChildArc(end_enode, earc->tail);
+                       }
+                       break;
+               }
+       }
+}
+
+static void markMultiResolutionArc(ReebArc *start_earc)
+{
+       if (start_earc->link_up)
+       {
+               ReebArc *earc;
+               for (earc = start_earc->link_up ; earc; earc = earc->link_up)
+               {
+                       earc->flag = ARC_TAKEN;
+                       
+                       if (earc->tail->index != start_earc->tail->index)
+                       {
+                               markMultiResolutionChildArc(earc->tail, earc->tail);
+                       }
+               }
+       }
+}
+
+static void matchMultiResolutionArc(RigGraph *rigg, RigNode *start_node, RigArc *next_iarc, ReebArc *next_earc)
+{
+       ReebNode *enode = next_earc->head;
+       ReebGraph *reebg = BIF_graphForMultiNode(rigg->link_mesh, enode);
+       int ishape, eshape;
+
+       ishape = BLI_subtreeShape((BGraph*)rigg, (BNode*)start_node, (BArc*)next_iarc, 1) % SHAPE_LEVELS;
+       eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, (BArc*)next_earc, 1) % SHAPE_LEVELS;
+       
+       while (ishape != eshape && next_earc->link_up)
+       {
+               next_earc->flag = ARC_TAKEN; // mark previous as taken, to prevent backtrack on lower levels
+               
+               next_earc = next_earc->link_up;
+               reebg = reebg->link_up;
+               enode = next_earc->head;
+               eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, (BArc*)next_earc, 1) % SHAPE_LEVELS;
+       } 
+
+       next_earc->flag = ARC_USED;
+       next_iarc->link_mesh = next_earc;
+       
+       /* mark all higher levels as taken too */
+       markMultiResolutionArc(next_earc);
+//     while (next_earc->link_up)
+//     {
+//             next_earc = next_earc->link_up;
+//             next_earc->flag = ARC_TAKEN;
+//     }
+}
+
+static void matchMultiResolutionStartingNode(RigGraph *rigg, ReebGraph *reebg, RigNode *inode)
+{
+       ReebNode *enode;
+       int ishape, eshape;
+       
+       enode = reebg->nodes.first;
+       
+       ishape = BLI_subtreeShape((BGraph*)rigg, (BNode*)inode, NULL, 0) % SHAPE_LEVELS;
+       eshape = BLI_subtreeShape((BGraph*)rigg->link_mesh, (BNode*)enode, NULL, 0) % SHAPE_LEVELS;
+       
+       while (ishape != eshape && reebg->link_up)
+       {
+               reebg = reebg->link_up;
+               
+               enode = reebg->nodes.first;
+               
+               eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, NULL, 0) % SHAPE_LEVELS;
+       } 
+
+       inode->link_mesh = enode;
+}
+
+static void findCorrespondingArc(RigGraph *rigg, RigArc *start_arc, RigNode *start_node, RigArc *next_iarc, int root)
+{
+       ReebNode *enode = start_node->link_mesh;
+       ReebArc *next_earc;
+       int symmetry_level = next_iarc->symmetry_level;
+       int symmetry_group = next_iarc->symmetry_group;
+       int symmetry_flag = next_iarc->symmetry_flag;
+       int i;
+       
+       next_iarc->link_mesh = NULL;
+               
+//     if (root)
+//     {
+//             printf("-----------------------\n");
+//             printf("MATCHING LIMB\n");
+//             RIG_printArcBones(next_iarc);
+//     }
+       
+       for(i = 0; i < enode->degree; i++)
+       {
+               next_earc = (ReebArc*)enode->arcs[i];
+               
+//             if (next_earc->flag == ARC_FREE)
+//             {
+//                     printf("candidate (level %i ?= %i) (flag %i ?= %i) (group %i ?= %i)\n",
+//                     symmetry_level, next_earc->symmetry_level,
+//                     symmetry_flag, next_earc->symmetry_flag, 
+//                     symmetry_group, next_earc->symmetry_flag);
+//             }
+               
+               if (next_earc->flag == ARC_FREE &&
+                       next_earc->symmetry_flag == symmetry_flag &&
+                       next_earc->symmetry_group == symmetry_group &&
+                       next_earc->symmetry_level == symmetry_level)
+               {
+//                     printf("CORRESPONDING ARC FOUND\n");
+//                     printf("flag %i -- level %i -- flag %i -- group %i\n", next_earc->flag, next_earc->symmetry_level, next_earc->symmetry_flag, next_earc->symmetry_group);
+                       
+                       matchMultiResolutionArc(rigg, start_node, next_iarc, next_earc);
+                       break;
+               }
+       }
+       
+       /* not found, try at higher nodes (lower node might have filtered internal arcs, messing shape of tree */
+       if (next_iarc->link_mesh == NULL)
+       {
+//             printf("NO CORRESPONDING ARC FOUND - GOING TO HIGHER LEVELS\n");
+               
+               if (enode->link_up)
+               {
+                       start_node->link_mesh = enode->link_up;
+                       findCorrespondingArc(rigg, start_arc, start_node, next_iarc, 0);
+               }
+       }
+
+       /* still not found, print debug info */
+       if (root && next_iarc->link_mesh == NULL)
+       {
+               start_node->link_mesh = enode; /* linking back with root node */
+               
+//             printf("NO CORRESPONDING ARC FOUND\n");
+//             RIG_printArcBones(next_iarc);
+//             
+//             printf("ON NODE %i, multilevel %i\n", enode->index, enode->multi_level);
+//             
+//             printf("LOOKING FOR\n");
+//             printf("flag %i -- level %i -- flag %i -- group %i\n", ARC_FREE, symmetry_level, symmetry_flag, symmetry_group);
+//             
+//             printf("CANDIDATES\n");
+//             for(i = 0; i < enode->degree; i++)
+//             {
+//                     next_earc = (ReebArc*)enode->arcs[i];
+//                     printf("flag %i -- level %i -- flag %i -- group %i\n", next_earc->flag, next_earc->symmetry_level, next_earc->symmetry_flag, next_earc->symmetry_group);
+//             }
+               
+               /* Emergency matching */
+               for(i = 0; i < enode->degree; i++)
+               {
+                       next_earc = (ReebArc*)enode->arcs[i];
+                       
+                       if (next_earc->flag == ARC_FREE && next_earc->symmetry_level == symmetry_level)
+                       {
+//                             printf("USING: \n");
+//                             printf("flag %i -- level %i -- flag %i -- group %i\n", next_earc->flag, next_earc->symmetry_level, next_earc->symmetry_flag, next_earc->symmetry_group);
+                               matchMultiResolutionArc(rigg, start_node, next_iarc, next_earc);
+                               break;
+                       }
+               }
+       }
+
+}
+
+static void retargetSubgraph(RigGraph *rigg, RigArc *start_arc, RigNode *start_node)
+{
+       RigNode *inode = start_node;
+       int i;
+
+       /* no start arc on first node */
+       if (start_arc)
+       {               
+               ReebNode *enode = start_node->link_mesh;
+               ReebArc *earc = start_arc->link_mesh;
+               
+               retargetArctoArc(rigg, start_arc, start_node);
+               
+               enode = BIF_otherNodeFromIndex(earc, enode);
+               inode = (RigNode*)BLI_otherNode((BArc*)start_arc, (BNode*)inode);
+       
+               /* match with lowest node with correct shape */
+               matchMultiResolutionNode(rigg, inode, enode);
+       }
+       
+       for(i = 0; i < inode->degree; i++)
+       {
+               RigArc *next_iarc = (RigArc*)inode->arcs[i];
+               
+               /* no back tracking */
+               if (next_iarc != start_arc)
+               {
+                       findCorrespondingArc(rigg, start_arc, inode, next_iarc, 1);
+                       if (next_iarc->link_mesh)
+                       {
+                               retargetSubgraph(rigg, next_iarc, inode);
+                       }
+               }
+       }
+}
+
+static void adjustGraphs(RigGraph *rigg)
+{
+       RigArc *arc;
+       
+       for (arc = rigg->arcs.first; arc; arc = arc->next)
+       {
+               if (arc->link_mesh)
+               {
+                       retargetArctoArc(rigg, arc, arc->head);
+               }
+       }
+
+#ifdef USE_THREADS
+       BLI_end_worker(rigg->worker);
+#endif
+
+       /* Turn the list into an armature */
+       editbones_to_armature(&rigg->editbones, rigg->ob);
+       
+       BIF_undo_push("Retarget Skeleton");
+}
+
+static void retargetGraphs(RigGraph *rigg)
+{
+       ReebGraph *reebg = rigg->link_mesh;
+       RigNode *inode;
+       
+       /* flag all ReebArcs as free */
+       BIF_flagMultiArcs(reebg, ARC_FREE);
+       
+       /* return to first level */
+       reebg = rigg->link_mesh;
+       
+       inode = rigg->head;
+       
+       matchMultiResolutionStartingNode(rigg, reebg, inode);
+
+       retargetSubgraph(rigg, NULL, inode);
+       
+       //generateMissingArcs(rigg);
+       
+#ifdef USE_THREADS
+       BLI_end_worker(rigg->worker);
+#endif
+
+       /* Turn the list into an armature */
+       editbones_to_armature(&rigg->editbones, rigg->ob);
+}
+
+
+void BIF_retargetArmature()
+{
+       Object *ob;
+       Base *base;
+       ReebGraph *reebg;
+       double start_time, end_time;
+       double gstart_time, gend_time;
+       double reeb_time, rig_time, retarget_time, total_time;
+       
+       gstart_time = start_time = PIL_check_seconds_timer();
+       
+       reebg = BIF_ReebGraphMultiFromEditMesh();
+       
+       end_time = PIL_check_seconds_timer();
+       reeb_time = end_time - start_time;
+       
+       printf("Reeb Graph created\n");
+
+       base= FIRSTBASE;
+       for (base = FIRSTBASE; base; base = base->next)
+       {
+               if TESTBASELIB(base) {
+                       ob = base->object;
+
+                       if (ob->type==OB_ARMATURE)
+                       {
+                               RigGraph *rigg;
+                               bArmature *arm;
+                               
+                               arm = ob->data;
+                       
+                               /* Put the armature into editmode */
+                               
+                       
+                               start_time = PIL_check_seconds_timer();
+       
+                               rigg = armatureToGraph(ob, arm);
+                               
+                               end_time = PIL_check_seconds_timer();
+                               rig_time = end_time - start_time;
+
+                               printf("Armature graph created\n");
+               
+                               //RIG_printGraph(rigg);
+                               
+                               rigg->link_mesh = reebg;
+                               
+                               printf("retargetting %s\n", ob->id.name);
+                               
+                               start_time = PIL_check_seconds_timer();
+
+                               retargetGraphs(rigg);
+                               
+                               end_time = PIL_check_seconds_timer();
+                               retarget_time = end_time - start_time;
+
+                               BIF_freeRetarget();
+                               
+                               GLOBAL_RIGG = rigg;
+                               
+                               break; /* only one armature at a time */
+                       }
+               }
+       }
+       
+       gend_time = PIL_check_seconds_timer();
+
+       total_time = gend_time - gstart_time;
+
+       printf("-----------\n");
+       printf("runtime: \t%.3f\n", total_time);
+       printf("reeb: \t\t%.3f (%.1f%%)\n", reeb_time, reeb_time / total_time * 100);
+       printf("rig: \t\t%.3f (%.1f%%)\n", rig_time, rig_time / total_time * 100);
+       printf("retarget: \t%.3f (%.1f%%)\n", retarget_time, retarget_time / total_time * 100);
+       printf("-----------\n");
+       
+       BIF_undo_push("Retarget Skeleton");
+       
+       allqueue(REDRAWVIEW3D, 0);
+}
+
+void BIF_adjustRetarget()
+{
+       if (GLOBAL_RIGG)
+       {
+               adjustGraphs(GLOBAL_RIGG);
+       }
+}
+
+void BIF_freeRetarget()
+{
+       if (GLOBAL_RIGG)
+       {
+               RIG_freeRigGraph((BGraph*)GLOBAL_RIGG);
+               GLOBAL_RIGG = NULL;
+       }
+}
index 4b3e8b1a05633f4e5cb36d50795682eae07425dc..fd13c88b81635db9310502f51f3f0e7921d45fcc 100644 (file)
 #include "butspace.h" // own module
 #include "multires.h"
 
+#include "reeb.h"
+
 static float editbutweight= 1.0;
 float editbutvweight= 1;
 static int actmcol= 0, acttface= 0, acttface_rnd = 0, actmcol_rnd = 0;
@@ -5047,6 +5049,9 @@ void do_meshbuts(unsigned short event)
        case B_GEN_SKELETON:
                generateSkeleton();
                break;
+       case B_RETARGET_SKELETON:
+               BIF_retargetArmature();
+               break;
        }
 
        /* WATCH IT: previous events only in editmode! */
@@ -5145,6 +5150,100 @@ static void skgen_reorder(void *option, void *arg2)
        }
 }
 
+static void skgen_graphgen(void *arg1, void *arg2)
+{
+       BIF_GlobalReebGraphFromEditMesh();
+       allqueue(REDRAWVIEW3D, 0);
+}
+
+static void skgen_graphfree(void *arg1, void *arg2)
+{
+       BIF_GlobalReebFree();
+       allqueue(REDRAWVIEW3D, 0);
+}
+
+static void skgen_rigadjust(void *arg1, void *arg2)
+{
+       BIF_adjustRetarget();
+}
+
+static void skgen_rigfree(void *arg1, void *arg2)
+{
+       BIF_freeRetarget();
+}
+
+static void skgen_graph_block(uiBlock *block)
+{
+       uiBlockBeginAlign(block);
+       uiDefButS(block, NUM, B_DIFF, "Resolution:",                                                    1025,150,225,19, &G.scene->toolsettings->skgen_resolution,10.0,1000.0, 0, 0,            "Specifies the resolution of the graph's embedding");
+       uiDefButBitS(block, TOG, SKGEN_HARMONIC, B_DIFF,                "H",                    1250,150, 25,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Apply harmonic smoothing to the weighting");
+       uiDefButBitS(block, TOG, SKGEN_FILTER_INTERNAL, B_DIFF, "Filter In",    1025,130, 83,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Filter internal small arcs from graph");
+       uiDefButF(block, NUM, B_DIFF,                                                   "",                             1111,130,164,19, &G.scene->toolsettings->skgen_threshold_internal,0.0, 10.0, 10, 0,     "Specify the threshold ratio for filtering internal arcs");
+       uiDefButBitS(block, TOG, SKGEN_FILTER_EXTERNAL, B_DIFF, "Filter Ex",    1025,110, 53,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Filter external small arcs from graph");
+       uiDefButBitS(block, TOG, SKGEN_FILTER_SMART,    B_DIFF, "Sm",                   1078,110, 30,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Smart Filtering");
+       uiDefButF(block, NUM, B_DIFF,                                                   "",                             1111,110,164,19, &G.scene->toolsettings->skgen_threshold_external,0.0, 10.0, 10, 0,     "Specify the threshold ratio for filtering external arcs");
+       
+       uiDefButBitS(block, TOG, SKGEN_SYMMETRY, B_DIFF,                "Symmetry",             1025, 90,125,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Restore symmetries based on topology");
+       uiDefButF(block, NUM, B_DIFF,                                                   "T:",                   1150, 90,125,19, &G.scene->toolsettings->skgen_symmetry_limit,0.0, 1.0, 10, 0,  "Specify the threshold distance for considering potential symmetric arcs");
+       uiDefButC(block, NUM, B_DIFF,                                                   "P:",                   1025, 70, 62,19, &G.scene->toolsettings->skgen_postpro_passes, 0, 10, 10, 0,            "Specify the number of processing passes on the embeddings");
+       uiDefButC(block, ROW, B_DIFF,                                                   "Smooth",               1087, 70, 63,19, &G.scene->toolsettings->skgen_postpro, 5.0, (float)SKGEN_SMOOTH, 0, 0, "Smooth embeddings");
+       uiDefButC(block, ROW, B_DIFF,                                                   "Average",              1150, 70, 62,19, &G.scene->toolsettings->skgen_postpro, 5.0, (float)SKGEN_AVERAGE, 0, 0, "Average embeddings");
+       uiDefButC(block, ROW, B_DIFF,                                                   "Sharpen",              1212, 70, 63,19, &G.scene->toolsettings->skgen_postpro, 5.0, (float)SKGEN_SHARPEN, 0, 0, "Sharpen embeddings");
+
+       uiBlockEndAlign(block);
+}
+
+static void editing_panel_mesh_skgen_display(Object *ob, Mesh *me)
+{
+       uiBlock *block;
+       uiBut *but;
+
+       block= uiNewBlock(&curarea->uiblocks, "editing_panel_mesh_skgen_display", UI_EMBOSS, UI_HELV, curarea->win);
+       uiNewPanelTabbed("Mesh Tools More", "Skgen");
+       if(uiNewPanel(curarea, block, "Graph", "Editing", 960, 0, 318, 204)==0) return;
+       
+       but = uiDefBut(block, BUT, B_DIFF, "Generate",                          1025,170,125,19, 0, 0, 0, 0, 0, "Generate Graph from Mesh");
+       uiButSetFunc(but, skgen_graphgen, NULL, NULL);
+       but = uiDefBut(block, BUT, B_DIFF, "Free",                                      1150,170,125,19, 0, 0, 0, 0, 0, "Free Graph from Mesh");
+       uiButSetFunc(but, skgen_graphfree, NULL, NULL);
+       
+       skgen_graph_block(block);
+
+       uiBlockBeginAlign(block);
+       uiDefButBitS(block, TOG, SKGEN_DISP_LENGTH, REDRAWVIEW3D,       "Length",                       1025, 40, 50,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,             "Show Length");
+       uiDefButBitS(block, TOG, SKGEN_DISP_WEIGHT, REDRAWVIEW3D,       "Weight",                       1075, 40, 50,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,             "Show Weight");
+       uiDefButBitS(block, TOG, SKGEN_DISP_EMBED, REDRAWVIEW3D,        "Embed",                        1125, 40, 50,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,             "Show Arc Embedings");
+       uiDefButBitS(block, TOG, SKGEN_DISP_INDEX, REDRAWVIEW3D,        "Index",                        1175, 40, 50,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,             "Show Arc and Node indexes");
+       uiDefButBitS(block, TOG, SKGEN_DISP_ORIG, REDRAWVIEW3D,         "Original",                     1225, 40, 50,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,             "Show Original Graph");
+
+       uiBlockEndAlign(block);
+
+       uiDefButC(block, NUM, REDRAWVIEW3D,                                             "Level:",                       1025, 20, 125,19, &G.scene->toolsettings->skgen_multi_level, 0, REEB_MAX_MULTI_LEVEL, 1, 0,"Specify the level to draw");
+}
+
+static void editing_panel_mesh_skgen_retarget(Object *ob, Mesh *me)
+{
+       uiBlock *block;
+       uiBut *but;
+
+       block= uiNewBlock(&curarea->uiblocks, "editing_panel_mesh_skgen_retarget", UI_EMBOSS, UI_HELV, curarea->win);
+       uiNewPanelTabbed("Mesh Tools More", "Skgen");
+       if(uiNewPanel(curarea, block, "Retarget", "Editing", 960, 0, 318, 204)==0) return;
+       
+       uiDefBut(block, BUT, B_RETARGET_SKELETON, "Retarget Skeleton",  1025,170,100,19, 0, 0, 0, 0, 0, "Retarget Selected Armature to this Mesh");
+       but = uiDefBut(block, BUT, B_DIFF, "Adjust",                                    1125,170,100,19, 0, 0, 0, 0, 0, "Adjust Retarget using new weights");
+       uiButSetFunc(but, skgen_rigadjust, NULL, NULL);
+       but = uiDefBut(block, BUT, B_DIFF, "Free",                                              1225,170,50,19, 0, 0, 0, 0, 0, "Free Retarget structure");
+       uiButSetFunc(but, skgen_rigfree, NULL, NULL);
+
+       skgen_graph_block(block);
+
+       uiDefButF(block, NUM, B_DIFF,                                                   "Ang:",                 1025, 40, 83,19, &G.scene->toolsettings->skgen_retarget_angle_weight, 0, 10, 1, 0,              "Angle Weight");
+       uiDefButF(block, NUM, B_DIFF,                                                   "Len:",                 1108, 40, 83,19, &G.scene->toolsettings->skgen_retarget_length_weight, 0, 10, 1, 0,             "Length Weight");
+       uiDefButF(block, NUM, B_DIFF,                                                   "Dist:",                1191, 40, 84,19, &G.scene->toolsettings->skgen_retarget_distance_weight, 0, 10, 1, 0,           "Distance Weight");
+       uiDefButC(block, NUM, B_DIFF,                                                   "Method:",              1025, 20, 125,19, &G.scene->toolsettings->skgen_optimisation_method, 0, 2, 1, 0,"Optimisation Method (0: brute, 1: memoize, 2: annealing max fixed");
+}
+
 static void editing_panel_mesh_skgen(Object *ob, Mesh *me)
 {
        uiBlock *block;
@@ -5152,20 +5251,17 @@ static void editing_panel_mesh_skgen(Object *ob, Mesh *me)
        int i;
 
        block= uiNewBlock(&curarea->uiblocks, "editing_panel_mesh_skgen", UI_EMBOSS, UI_HELV, curarea->win);
-       if(uiNewPanel(curarea, block, "Skeleton Generator", "Editing", 960, 0, 318, 204)==0) return;
+       uiNewPanelTabbed("Mesh Tools More", "Skgen");
+       if(uiNewPanel(curarea, block, "Generator", "Editing", 960, 0, 318, 204)==0) return;
        
-       uiDefBut(block, BUT, B_GEN_SKELETON, "Generate Skeleton",                       1025,170,250,19, 0, 0, 0, 0, 0, "Generate Skeleton from Mesh");
+       uiDefBut(block, BUT, B_GEN_SKELETON, "Generate",                        1025,170,250,19, 0, 0, 0, 0, 0, "Generate Skeleton from Mesh");
 
-       uiBlockBeginAlign(block);
-       uiDefButS(block, NUM, B_DIFF, "Resolution:",                                                    1025,150,250,19, &G.scene->toolsettings->skgen_resolution,10.0,1000.0, 0, 0,            "Specifies the resolution of the graph's embedding");
-       uiDefButBitS(block, TOG, SKGEN_FILTER_INTERNAL, B_DIFF, "Filter In",    1025,130, 83,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Filter internal small arcs from graph");
-       uiDefButF(block, NUM, B_DIFF,                                                   "T:",                   1111,130,164,19, &G.scene->toolsettings->skgen_threshold_internal,0.0, 1.0, 10, 0,      "Specify the threshold ratio for filtering internal arcs");
-       uiDefButBitS(block, TOG, SKGEN_FILTER_EXTERNAL, B_DIFF, "Filter Ex",    1025,110, 83,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Filter external small arcs from graph");
-       uiDefButF(block, NUM, B_DIFF,                                                   "T:",                   1111,110,164,19, &G.scene->toolsettings->skgen_threshold_external,0.0, 1.0, 10, 0,      "Specify the threshold ratio for filtering external arcs");
+       skgen_graph_block(block);
 
+       uiBlockBeginAlign(block);
        for(i = 0; i < SKGEN_SUB_TOTAL; i++)
        {
-               int y = 90 - 20 * i;
+               int y = 50 - 20 * i;
                
                but = uiDefIconBut(block, BUT, B_MODIFIER_RECALC, VICON_MOVE_DOWN,              1025, y, 16, 19, NULL, 0.0, 0.0, 0.0, 0.0, "Change the order the subdivisions algorithm are applied");
                uiButSetFunc(but, skgen_reorder, SET_INT_IN_POINTER(i), NULL);
@@ -5182,18 +5278,14 @@ static void editing_panel_mesh_skgen(Object *ob, Mesh *me)
                                uiDefButF(block, NUM, B_DIFF,                                                   "T:",                   1111, y,164,19, &G.scene->toolsettings->skgen_angle_limit,0.0, 90.0, 10, 0,                     "Specify the threshold angle in degrees for subdivision");
                                break;
                        case SKGEN_SUB_CORRELATION:
-                               uiDefButBitS(block, TOG, SKGEN_CUT_CORRELATION, B_DIFF, "Correlation",  1041, y, 67,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                      "Subdivide arcs based on correlation");
-                               uiDefButF(block, NUM, B_DIFF,                                                   "T:",                   1111, y,164,19, &G.scene->toolsettings->skgen_correlation_limit,0.0, 1.0, 0.01, 0,      "Specify the threshold correlation for subdivision");
+                               uiDefButBitS(block, TOG, SKGEN_CUT_CORRELATION, B_DIFF, "Adaptative",   1041, y, 67,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                      "Subdivide arcs adaptatively");
+                               uiDefButF(block, NUM, B_DIFF,                                                   "T:",                   1111, y,114,19, &G.scene->toolsettings->skgen_correlation_limit,0.0, 1.0, 0.01, 0,      "Specify the adaptive threshold for subdivision");
+                               uiDefButBitS(block, TOG, SKGEN_STICK_TO_EMBEDDING, B_DIFF,              "E",                    1225, y, 25,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                      "Stick endpoint to embedding");
+                               uiDefButBitS(block, TOG, SKGEN_ADAPTIVE_DISTANCE, B_DIFF,               "D",                    1250, y, 25,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                      "Adaptive distance (on) or variance(off)");
                                break;
                }
        }
 
-       uiDefButBitS(block, TOG, SKGEN_SYMMETRY, B_DIFF,                "Symmetry",             1025, 30,125,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,                                     "Restore symmetries based on topology");
-       uiDefButF(block, NUM, B_DIFF,                                                   "T:",                   1150, 30,125,19, &G.scene->toolsettings->skgen_symmetry_limit,0.0, 1.0, 10, 0,  "Specify the threshold distance for considering potential symmetric arcs");
-       uiDefButC(block, NUM, B_DIFF,                                                   "P:",                   1025, 10, 62,19, &G.scene->toolsettings->skgen_postpro_passes, 0, 10, 10, 0,            "Specify the number of processing passes on the embeddings");
-       uiDefButC(block, ROW, B_DIFF,                                                   "Smooth",               1087, 10, 63,19, &G.scene->toolsettings->skgen_postpro, 5.0, (float)SKGEN_SMOOTH, 0, 0, "Smooth embeddings");
-       uiDefButC(block, ROW, B_DIFF,                                                   "Average",              1150, 10, 62,19, &G.scene->toolsettings->skgen_postpro, 5.0, (float)SKGEN_AVERAGE, 0, 0, "Average embeddings");
-       uiDefButC(block, ROW, B_DIFF,                                                   "Sharpen",              1212, 10, 63,19, &G.scene->toolsettings->skgen_postpro, 5.0, (float)SKGEN_SHARPEN, 0, 0, "Sharpen embeddings");
        uiBlockEndAlign(block);
 }
 
@@ -6618,8 +6710,9 @@ void editing_panels()
                        editing_panel_mesh_tools1(ob, ob->data);
                        uiNewPanelTabbed("Mesh Tools 1", "Editing");
                        
-                       if (G.rt == 42) /* hidden for now, no time for docs */
-                               editing_panel_mesh_skgen(ob, ob->data);
+                       editing_panel_mesh_skgen(ob, ob->data);
+                       editing_panel_mesh_skgen_retarget(ob, ob->data);
+                       editing_panel_mesh_skgen_display(ob, ob->data);
                        
                        editing_panel_mesh_uvautocalculation();
                        if (EM_texFaceCheck())
index 8f2623575aa75a4c4d00db3e55bf7c91fa6686af..a169848aa627fff60f1caf45800fde771ca7fda7 100644 (file)
 
 #include "RE_pipeline.h"       // make_stars
 
+#include "reeb.h"
+
 #include "GPU_draw.h"
 #include "GPU_material.h"
 
@@ -3238,6 +3240,8 @@ void drawview3dspace(ScrArea *sa, void *spacedata)
                        BIF_drawPropCircle(); // only editmode and particles have proportional edit
                BIF_drawSnap();
        }
+       
+       REEB_draw();
 
        if(G.scene->radio) RAD_drawall(v3d->drawtype>=OB_SOLID);
        
index d5e5b5a1c4a2ad846cc460a1ab41f3f816810e9e..d94d77952248f2993c32b76f41eb68279f06289a 100644 (file)
@@ -4488,542 +4488,7 @@ void transform_armature_mirror_update(void)
 /*************************************** SKELETON GENERATOR ******************************************/
 /*****************************************************************************************************/
 
-/**************************************** SYMMETRY HANDLING ******************************************/
 
-void markdownSymmetryArc(ReebArc *arc, ReebNode *node, int level);
-
-void mirrorAlongAxis(float v[3], float center[3], float axis[3])
-{
-       float dv[3], pv[3];
-       
-       VecSubf(dv, v, center);
-       Projf(pv, dv, axis);
-       VecMulf(pv, -2);
-       VecAddf(v, v, pv);
-}
-
-/* Helper structure for radial symmetry */
-typedef struct RadialArc
-{
-       ReebArc *arc; 
-       float n[3]; /* normalized vector joining the nodes of the arc */
-} RadialArc;
-
-void reestablishRadialSymmetry(ReebNode *node, int depth, float axis[3])
-{
-       RadialArc *ring = NULL;
-       RadialArc *unit;
-       float limit = G.scene->toolsettings->skgen_symmetry_limit;
-       int symmetric = 1;
-       int count = 0;
-       int i;
-
-       /* count the number of arcs in the symmetry ring */
-       for (i = 0; node->arcs[i] != NULL; i++)
-       {
-               ReebArc *connectedArc = node->arcs[i];
-               
-               /* depth is store as a negative in flag. symmetry level is positive */
-               if (connectedArc->flags == -depth)
-               {
-                       count++;
-               }
-       }
-
-       ring = MEM_callocN(sizeof(RadialArc) * count, "radial symmetry ring");
-       unit = ring;
-
-       /* fill in the ring */
-       for (unit = ring, i = 0; node->arcs[i] != NULL; i++)
-       {
-               ReebArc *connectedArc = node->arcs[i];
-               
-               /* depth is store as a negative in flag. symmetry level is positive */
-               if (connectedArc->flags == -depth)
-               {
-                       ReebNode *otherNode = OTHER_NODE(connectedArc, node);
-                       float vec[3];
-
-                       unit->arc = connectedArc;
-
-                       /* project the node to node vector on the symmetry plane */
-                       VecSubf(unit->n, otherNode->p, node->p);
-                       Projf(vec, unit->n, axis);
-                       VecSubf(unit->n, unit->n, vec);
-
-                       Normalize(unit->n);
-
-                       unit++;
-               }
-       }
-
-       /* sort ring */
-       for (i = 0; i < count - 1; i++)
-       {
-               float minAngle = 3; /* arbitrary high value, higher than 2, at least */
-               int minIndex = -1;
-               int j;
-
-               for (j = i + 1; j < count; j++)
-               {
-                       float angle = Inpf(ring[i].n, ring[j].n);
-
-                       /* map negative values to 1..2 */
-                       if (angle < 0)
-                       {
-                               angle = 1 - angle;
-                       }
-
-                       if (angle < minAngle)
-                       {
-                               minIndex = j;
-                               minAngle = angle;
-                       }
-               }
-
-               /* swap if needed */
-               if (minIndex != i + 1)
-               {
-                       RadialArc tmp;
-                       tmp = ring[i + 1];
-                       ring[i + 1] = ring[minIndex];
-                       ring[minIndex] = tmp;
-               }
-       }
-
-       for (i = 0; i < count && symmetric; i++)
-       {
-               ReebNode *node1, *node2;
-               float tangent[3];
-               float normal[3];
-               float p[3];
-               int j = (i + 1) % count; /* next arc in the circular list */
-
-               VecAddf(tangent, ring[i].n, ring[j].n);
-               Crossf(normal, tangent, axis);
-               
-               node1 = OTHER_NODE(ring[i].arc, node);
-               node2 = OTHER_NODE(ring[j].arc, node);
-
-               VECCOPY(p, node2->p);
-               mirrorAlongAxis(p, node->p, normal);
-               
-               /* check if it's within limit before continuing */
-               if (VecLenf(node1->p, p) > limit)
-               {
-                       symmetric = 0;
-               }
-
-       }
-
-       if (symmetric)
-       {
-               /* first pass, merge incrementally */
-               for (i = 0; i < count - 1; i++)
-               {
-                       ReebNode *node1, *node2;
-                       float tangent[3];
-                       float normal[3];
-                       int j = i + 1;
-       
-                       VecAddf(tangent, ring[i].n, ring[j].n);
-                       Crossf(normal, tangent, axis);
-                       
-                       node1 = OTHER_NODE(ring[i].arc, node);
-                       node2 = OTHER_NODE(ring[j].arc, node);
-       
-                       /* mirror first node and mix with the second */
-                       mirrorAlongAxis(node1->p, node->p, normal);
-                       VecLerpf(node2->p, node2->p, node1->p, 1.0f / (j + 1));
-                       
-                       /* Merge buckets
-                        * there shouldn't be any null arcs here, but just to be safe 
-                        * */
-                       if (ring[i].arc->bcount > 0 && ring[j].arc->bcount > 0)
-                       {
-                               ReebArcIterator iter1, iter2;
-                               EmbedBucket *bucket1 = NULL, *bucket2 = NULL;
-                               
-                               initArcIterator(&iter1, ring[i].arc, node);
-                               initArcIterator(&iter2, ring[j].arc, node);
-                               
-                               bucket1 = nextBucket(&iter1);
-                               bucket2 = nextBucket(&iter2);
-                       
-                               /* Make sure they both start at the same value */       
-                               while(bucket1 && bucket1->val < bucket2->val)
-                               {
-                                       bucket1 = nextBucket(&iter1);
-                               }
-                               
-                               while(bucket2 && bucket2->val < bucket1->val)
-                               {
-                                       bucket2 = nextBucket(&iter2);
-                               }
-               
-               
-                               for ( ;bucket1 && bucket2; bucket1 = nextBucket(&iter1), bucket2 = nextBucket(&iter2))
-                               {
-                                       bucket2->nv += bucket1->nv; /* add counts */
-                                       
-                                       /* mirror on axis */
-                                       mirrorAlongAxis(bucket1->p, node->p, normal);
-                                       /* add bucket2 in bucket1 */
-                                       VecLerpf(bucket2->p, bucket2->p, bucket1->p, (float)bucket1->nv / (float)(bucket2->nv));
-                               }
-                       }
-               }
-               
-               /* second pass, mirror back on previous arcs */
-               for (i = count - 1; i > 0; i--)
-               {
-                       ReebNode *node1, *node2;
-                       float tangent[3];
-                       float normal[3];
-                       int j = i - 1;
-       
-                       VecAddf(tangent, ring[i].n, ring[j].n);
-                       Crossf(normal, tangent, axis);
-                       
-                       node1 = OTHER_NODE(ring[i].arc, node);
-                       node2 = OTHER_NODE(ring[j].arc, node);
-       
-                       /* copy first node than mirror */
-                       VECCOPY(node2->p, node1->p);
-                       mirrorAlongAxis(node2->p, node->p, normal);
-                       
-                       /* Copy buckets
-                        * there shouldn't be any null arcs here, but just to be safe 
-                        * */
-                       if (ring[i].arc->bcount > 0 && ring[j].arc->bcount > 0)
-                       {
-                               ReebArcIterator iter1, iter2;
-                               EmbedBucket *bucket1 = NULL, *bucket2 = NULL;
-                               
-                               initArcIterator(&iter1, ring[i].arc, node);
-                               initArcIterator(&iter2, ring[j].arc, node);
-                               
-                               bucket1 = nextBucket(&iter1);
-                               bucket2 = nextBucket(&iter2);
-                       
-                               /* Make sure they both start at the same value */       
-                               while(bucket1 && bucket1->val < bucket2->val)
-                               {
-                                       bucket1 = nextBucket(&iter1);
-                               }
-                               
-                               while(bucket2 && bucket2->val < bucket1->val)
-                               {
-                                       bucket2 = nextBucket(&iter2);
-                               }
-               
-               
-                               for ( ;bucket1 && bucket2; bucket1 = nextBucket(&iter1), bucket2 = nextBucket(&iter2))
-                               {
-                                       /* copy and mirror back to bucket2 */                   
-                                       bucket2->nv = bucket1->nv;
-                                       VECCOPY(bucket2->p, bucket1->p);
-                                       mirrorAlongAxis(bucket2->p, node->p, normal);
-                               }
-                       }
-               }
-       }
-
-       MEM_freeN(ring);
-}
-
-void reestablishAxialSymmetry(ReebNode *node, int depth, float axis[3])
-{
-       ReebArc *arc1 = NULL;
-       ReebArc *arc2 = NULL;
-       ReebNode *node1 = NULL, *node2 = NULL;
-       float limit = G.scene->toolsettings->skgen_symmetry_limit;
-       float nor[3], vec[3], p[3];
-       int i;
-       
-       for (i = 0; node->arcs[i] != NULL; i++)
-       {
-               ReebArc *connectedArc = node->arcs[i];
-               
-               /* depth is store as a negative in flag. symmetry level is positive */
-               if (connectedArc->flags == -depth)
-               {
-                       if (arc1 == NULL)
-                       {
-                               arc1 = connectedArc;
-                               node1 = OTHER_NODE(arc1, node);
-                       }
-                       else
-                       {
-                               arc2 = connectedArc;
-                               node2 = OTHER_NODE(arc2, node);
-                               break; /* Can stop now, the two arcs have been found */
-                       }
-               }
-       }
-       
-       /* shouldn't happen, but just to be sure */
-       if (node1 == NULL || node2 == NULL)
-       {
-               return;
-       }
-       
-       VecSubf(p, node1->p, node->p);
-       Crossf(vec, p, axis);
-       Crossf(nor, vec, axis);
-       
-       /* mirror node2 along axis */
-       VECCOPY(p, node2->p);
-       mirrorAlongAxis(p, node->p, nor);
-       
-       /* check if it's within limit before continuing */
-       if (VecLenf(node1->p, p) <= limit)
-       {
-       
-               /* average with node1 */
-               VecAddf(node1->p, node1->p, p);
-               VecMulf(node1->p, 0.5f);
-               
-               /* mirror back on node2 */
-               VECCOPY(node2->p, node1->p);
-               mirrorAlongAxis(node2->p, node->p, nor);
-               
-               /* Merge buckets
-                * there shouldn't be any null arcs here, but just to be safe 
-                * */
-               if (arc1->bcount > 0 && arc2->bcount > 0)
-               {
-                       ReebArcIterator iter1, iter2;
-                       EmbedBucket *bucket1 = NULL, *bucket2 = NULL;
-                       
-                       initArcIterator(&iter1, arc1, node);
-                       initArcIterator(&iter2, arc2, node);
-                       
-                       bucket1 = nextBucket(&iter1);
-                       bucket2 = nextBucket(&iter2);
-               
-                       /* Make sure they both start at the same value */       
-                       while(bucket1 && bucket1->val < bucket2->val)
-                       {
-                               bucket1 = nextBucket(&iter1);
-                       }
-                       
-                       while(bucket2 && bucket2->val < bucket1->val)
-                       {
-                               bucket2 = nextBucket(&iter2);
-                       }
-       
-       
-                       for ( ;bucket1 && bucket2; bucket1 = nextBucket(&iter1), bucket2 = nextBucket(&iter2))
-                       {
-                               bucket1->nv += bucket2->nv; /* add counts */
-                               
-                               /* mirror on axis */
-                               mirrorAlongAxis(bucket2->p, node->p, nor);
-                               /* add bucket2 in bucket1 */
-                               VecLerpf(bucket1->p, bucket1->p, bucket2->p, (float)bucket2->nv / (float)(bucket1->nv));
-       
-                               /* copy and mirror back to bucket2 */                   
-                               bucket2->nv = bucket1->nv;
-                               VECCOPY(bucket2->p, bucket1->p);
-                               mirrorAlongAxis(bucket2->p, node->p, nor);
-                       }
-               }
-       }
-}
-
-void markdownSecondarySymmetry(ReebNode *node, int depth, int level)
-{
-       float axis[3] = {0, 0, 0};
-       int count = 0;
-       int i;
-
-       /* Only reestablish spatial symmetry if needed */
-       if (G.scene->toolsettings->skgen_options & SKGEN_SYMMETRY)
-       {
-               /* count the number of branches in this symmetry group
-                * and determinte the axis of symmetry
-                *  */  
-               for (i = 0; node->arcs[i] != NULL; i++)
-               {
-                       ReebArc *connectedArc = node->arcs[i];
-                       
-                       /* depth is store as a negative in flag. symmetry level is positive */
-                       if (connectedArc->flags == -depth)
-                       {
-                               count++;
-                       }
-                       /* If arc is on the axis */
-                       else if (connectedArc->flags == level)
-                       {
-                               VecAddf(axis, axis, connectedArc->v1->p);
-                               VecSubf(axis, axis, connectedArc->v2->p);
-                       }
-               }
-       
-               Normalize(axis);
-       
-               /* Split between axial and radial symmetry */
-               if (count == 2)
-               {
-                       reestablishAxialSymmetry(node, depth, axis);
-               }
-               else
-               {
-                       reestablishRadialSymmetry(node, depth, axis);
-               }
-       }
-
-       /* markdown secondary symetries */      
-       for (i = 0; node->arcs[i] != NULL; i++)
-       {
-               ReebArc *connectedArc = node->arcs[i];
-               
-               if (connectedArc->flags == -depth)
-               {
-                       /* markdown symmetry for branches corresponding to the depth */
-                       markdownSymmetryArc(connectedArc, node, level + 1);
-               }
-       }
-}
-
-void markdownSymmetryArc(ReebArc *arc, ReebNode *node, int level)
-{
-       int i;
-       arc->flags = level;
-       
-       node = OTHER_NODE(arc, node);
-       
-       for (i = 0; node->arcs[i] != NULL; i++)
-       {
-               ReebArc *connectedArc = node->arcs[i];
-               
-               if (connectedArc != arc)
-               {
-                       ReebNode *connectedNode = OTHER_NODE(connectedArc, node);
-                       
-                       /* symmetry level is positive value, negative values is subtree depth */
-                       connectedArc->flags = -subtreeDepth(connectedNode, connectedArc);
-               }
-       }
-
-       arc = NULL;
-
-       for (i = 0; node->arcs[i] != NULL; i++)
-       {
-               int issymmetryAxis = 0;
-               ReebArc *connectedArc = node->arcs[i];
-               
-               /* only arcs not already marked as symetric */
-               if (connectedArc->flags < 0)
-               {
-                       int j;
-                       
-                       /* true by default */
-                       issymmetryAxis = 1;
-                       
-                       for (j = 0; node->arcs[j] != NULL && issymmetryAxis == 1; j++)
-                       {
-                               ReebArc *otherArc = node->arcs[j];
-                               
-                               /* different arc, same depth */
-                               if (otherArc != connectedArc && otherArc->flags == connectedArc->flags)
-                               {
-                                       /* not on the symmetry axis */
-                                       issymmetryAxis = 0;
-                               } 
-                       }
-               }
-               
-               /* arc could be on the symmetry axis */
-               if (issymmetryAxis == 1)
-               {
-                       /* no arc as been marked previously, keep this one */
-                       if (arc == NULL)
-                       {
-                               arc = connectedArc;
-                       }
-                       else
-                       {
-                               /* there can't be more than one symmetry arc */
-                               arc = NULL;
-                               break;
-                       }
-               }
-       }
-       
-       /* go down the arc continuing the symmetry axis */
-       if (arc)
-       {
-               markdownSymmetryArc(arc, node, level);
-       }
-
-       
-       /* secondary symmetry */
-       for (i = 0; node->arcs[i] != NULL; i++)
-       {
-               ReebArc *connectedArc = node->arcs[i];
-               
-               /* only arcs not already marked as symetric and is not the next arc on the symmetry axis */
-               if (connectedArc->flags < 0)
-               {
-                       /* subtree depth is store as a negative value in the flag */
-                       markdownSecondarySymmetry(node, -connectedArc->flags, level);
-               }
-       }
-}
-
-void markdownSymmetry(ReebGraph *rg)
-{
-       ReebNode *node;
-       ReebArc *arc;
-       /* only for Acyclic graphs */
-       int cyclic = isGraphCyclic(rg);
-       
-       /* mark down all arcs as non-symetric */
-       for (arc = rg->arcs.first; arc; arc = arc->next)
-       {
-               arc->flags = 0;
-       }
-       
-       /* mark down all nodes as not on the symmetry axis */
-       for (node = rg->nodes.first; node; node = node->next)
-       {
-               node->flags = 0;
-       }
-
-       /* node list is sorted, so lowest node is always the head (by design) */
-       node = rg->nodes.first;
-       
-       /* only work on acyclic graphs and if only one arc is incident on the first node */
-       if (cyclic == 0 && countConnectedArcs(rg, node) == 1)
-       {
-               arc = node->arcs[0];
-               
-               markdownSymmetryArc(arc, node, 1);
-
-               /* mark down non-symetric arcs */
-               for (arc = rg->arcs.first; arc; arc = arc->next)
-               {
-                       if (arc->flags < 0)
-                       {
-                               arc->flags = 0;
-                       }
-                       else
-                       {
-                               /* mark down nodes with the lowest level symmetry axis */
-                               if (arc->v1->flags == 0 || arc->v1->flags > arc->flags)
-                               {
-                                       arc->v1->flags = arc->flags;
-                               }
-                               if (arc->v2->flags == 0 || arc->v2->flags > arc->flags)
-                               {
-                                       arc->v2->flags = arc->flags;
-                               }
-                       }
-               }
-       }
-}
 
 /**************************************** SUBDIVISION ALGOS ******************************************/
 
@@ -5088,7 +4553,7 @@ EditBone * subdivideByAngle(ReebArc *arc, ReebNode *head, ReebNode *tail)
        return lastBone;
 }
 
-float calcCorrelation(ReebArc *arc, int start, int end, float v0[3], float n[3])
+float calcVariance(ReebArc *arc, int start, int end, float v0[3], float n[3])
 {
        int len = 2 + abs(end - start);
        
@@ -5136,19 +4601,47 @@ float calcCorrelation(ReebArc *arc, int start, int end, float v0[3], float n[3])
                /* adding start(0) and end(1) values to s_t */
                s_t += (avg_t * avg_t) + (1 - avg_t) * (1 - avg_t);
                
-               return 1.0f - s_xyz / s_t; 
+               return s_xyz / s_t; 
        }
        else
        {
-               return 1.0f;
+               return 0;
+       }
+}
+
+float calcDistance(ReebArc *arc, int start, int end, float head[3], float tail[3])
+{
+       ReebArcIterator iter;
+       EmbedBucket *bucket = NULL;
+       float max_dist = 0;
+       
+       /* calculate maximum distance */
+       for (initArcIterator2(&iter, arc, start, end), bucket = nextBucket(&iter);
+               bucket;
+               bucket = nextBucket(&iter))
+       {
+               float v1[3], v2[3], c[3];
+               float dist;
+               
+               VecSubf(v1, head, tail);
+               VecSubf(v2, bucket->p, tail);
+
+               Crossf(c, v1, v2);
+               
+               dist = Inpf(c, c) / Inpf(v1, v1);
+               
+               max_dist = dist > max_dist ? dist : max_dist;
        }
+       
+       
+       return max_dist; 
 }
 
 EditBone * subdivideByCorrelation(ReebArc *arc, ReebNode *head, ReebNode *tail)
 {
        ReebArcIterator iter;
        float n[3];
-       float CORRELATION_THRESHOLD = G.scene->toolsettings->skgen_correlation_limit;
+       float ADAPTIVE_THRESHOLD = G.scene->toolsettings->skgen_correlation_limit;
        EditBone *lastBone = NULL;
        
        /* init iterator to get start and end from head */
@@ -5157,15 +4650,17 @@ EditBone * subdivideByCorrelation(ReebArc *arc, ReebNode *head, ReebNode *tail)
        /* Calculate overall */
        VecSubf(n, arc->buckets[iter.end].p, head->p);
        
-       if (G.scene->toolsettings->skgen_options & SKGEN_CUT_CORRELATION && 
-               calcCorrelation(arc, iter.start, iter.end, head->p, n) < CORRELATION_THRESHOLD)
+       if (G.scene->toolsettings->skgen_options & SKGEN_CUT_CORRELATION)
        {
                EmbedBucket *bucket = NULL;
                EmbedBucket *previous = NULL;
                EditBone *child = NULL;
                EditBone *parent = NULL;
+               float normal[3] = {0, 0, 0};
+               float avg_normal[3];
+               int total = 0;
                int boneStart = iter.start;
-
+               
                parent = add_editbone("Bone");
                parent->flag = BONE_SELECTED|BONE_TIPSEL|BONE_ROOTSEL;
                VECCOPY(parent->head, head->p);
@@ -5174,12 +4669,46 @@ EditBone * subdivideByCorrelation(ReebArc *arc, ReebNode *head, ReebNode *tail)
                        bucket;
                        previous = bucket, bucket = nextBucket(&iter))
                {
-                       /* Calculate normal */
-                       VecSubf(n, bucket->p, parent->head);
+                       float btail[3];
+                       float value = 0;
 
-                       if (calcCorrelation(arc, boneStart, iter.index, parent->head, n) < CORRELATION_THRESHOLD)
+                       if (G.scene->toolsettings->skgen_options & SKGEN_STICK_TO_EMBEDDING)
                        {
-                               VECCOPY(parent->tail, previous->p);
+                               VECCOPY(btail, bucket->p);
+                       }
+                       else
+                       {
+                               float length;
+                               
+                               /* Calculate normal */
+                               VecSubf(n, bucket->p, parent->head);
+                               length = Normalize(n);
+                               
+                               total += 1;
+                               VecAddf(normal, normal, n);
+                               VECCOPY(avg_normal, normal);
+                               VecMulf(avg_normal, 1.0f / total);
+                                
+                               VECCOPY(btail, avg_normal);
+                               VecMulf(btail, length);
+                               VecAddf(btail, btail, parent->head);
+                       }
+
+                       if (G.scene->toolsettings->skgen_options & SKGEN_ADAPTIVE_DISTANCE)
+                       {
+                               value = calcDistance(arc, boneStart, iter.index, parent->head, btail);
+                       }
+                       else
+                       {
+                               float n[3];
+                               
+                               VecSubf(n, btail, parent->head);
+                               value = calcVariance(arc, boneStart, iter.index, parent->head, n);
+                       }
+
+                       if (value > ADAPTIVE_THRESHOLD)
+                       {
+                               VECCOPY(parent->tail, btail);
 
                                child = add_editbone("Bone");
                                VECCOPY(child->head, parent->tail);
@@ -5188,6 +4717,9 @@ EditBone * subdivideByCorrelation(ReebArc *arc, ReebNode *head, ReebNode *tail)
                                
                                parent = child; // new child is next parent
                                boneStart = iter.index; // start from end
+                               
+                               normal[0] = normal[1] = normal[2] = 0;
+                               total = 0;
                        }
                }
 
@@ -5205,7 +4737,7 @@ float arcLengthRatio(ReebArc *arc)
        float embedLength = 0.0f;
        int i;
        
-       arcLength = VecLenf(arc->v1->p, arc->v2->p);
+       arcLength = VecLenf(arc->head->p, arc->tail->p);
        
        if (arc->bcount > 0)
        {
@@ -5215,8 +4747,8 @@ float arcLengthRatio(ReebArc *arc)
                        embedLength += VecLenf(arc->buckets[i - 1].p, arc->buckets[i].p);
                }
                /* Add head and tail -> embedding vectors */
-               embedLength += VecLenf(arc->v1->p, arc->buckets[0].p);
-               embedLength += VecLenf(arc->v2->p, arc->buckets[arc->bcount - 1].p);
+               embedLength += VecLenf(arc->head->p, arc->buckets[0].p);
+               embedLength += VecLenf(arc->tail->p, arc->buckets[arc->bcount - 1].p);
        }
        else
        {
@@ -5348,8 +4880,6 @@ void generateSkeletonFromReebGraph(ReebGraph *rg)
        {
                exit_editmode(EM_FREEDATA|EM_FREEUNDO|EM_WAITCURSOR); // freedata, and undo
        }
-
-       setcursor_space(SPACE_VIEW3D, CURSOR_WAIT);
        
        dst = add_object(OB_ARMATURE);
        base_init_from_view3d(BASACT, G.vd);
@@ -5366,7 +4896,7 @@ void generateSkeletonFromReebGraph(ReebGraph *rg)
 
        arcBoneMap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
        
-       markdownSymmetry(rg);
+       BLI_markdownSymmetry((BGraph*)rg, rg->nodes.first, G.scene->toolsettings->skgen_symmetry_limit);
        
        for (arc = rg->arcs.first; arc; arc = arc->next) 
        {
@@ -5376,43 +4906,43 @@ void generateSkeletonFromReebGraph(ReebGraph *rg)
 
                /* Find out the direction of the arc through simple heuristics (in order of priority) :
                 * 
-                * 1- Arcs on primary symmetry axis (flags == 1) point up (head: high weight -> tail: low weight)
+                * 1- Arcs on primary symmetry axis (symmetry == 1) point up (head: high weight -> tail: low weight)
                 * 2- Arcs starting on a primary axis point away from it (head: node on primary axis)
                 * 3- Arcs point down (head: low weight -> tail: high weight)
                 *
-                * Finally, the arc direction is stored in its flags: 1 (low -> high), -1 (high -> low)
+                * Finally, the arc direction is stored in its flag: 1 (low -> high), -1 (high -> low)
                 */
 
                /* if arc is a symmetry axis, internal bones go up the tree */          
-               if (arc->flags == 1 && arc->v2->degree != 1)
+               if (arc->symmetry_level == 1 && arc->tail->degree != 1)
                {
-                       head = arc->v2;
-                       tail = arc->v1;
+                       head = arc->tail;
+                       tail = arc->head;
                        
-                       arc->flags = -1; /* mark arc direction */
+                       arc->flag = -1; /* mark arc direction */
                }
                /* Bones point AWAY from the symmetry axis */
-               else if (arc->v1->flags == 1)
+               else if (arc->head->symmetry_level == 1)
                {
-                       head = arc->v1;
-                       tail = arc->v2;
+                       head = arc->head;
+                       tail = arc->tail;
                        
-                       arc->flags = 1; /* mark arc direction */
+                       arc->flag = 1; /* mark arc direction */
                }
-               else if (arc->v2->flags == 1)
+               else if (arc->tail->symmetry_level == 1)
                {
-                       head = arc->v2;
-                       tail = arc->v1;
+                       head = arc->tail;
+                       tail = arc->head;
                        
-                       arc->flags = -1; /* mark arc direction */
+                       arc->flag = -1; /* mark arc direction */
                }
                /* otherwise, always go from low weight to high weight */
                else
                {
-                       head = arc->v1;
-                       tail = arc->v2;
+                       head = arc->head;
+                       tail = arc->tail;
                        
-                       arc->flags = 1; /* mark arc direction */
+                       arc->flag = 1; /* mark arc direction */
                }
                
                /* Loop over subdivision methods */     
@@ -5454,12 +4984,12 @@ void generateSkeletonFromReebGraph(ReebGraph *rg)
                ReebArc *incomingArc = NULL;
                int i;
 
-               for (i = 0; node->arcs[i] != NULL; i++)
+               for (i = 0; i < node->degree; i++)
                {
-                       arc = node->arcs[i];
+                       arc = (ReebArc*)node->arcs[i];
 
                        /* if arc is incoming into the node */
-                       if ((arc->v1 == node && arc->flags == -1) || (arc->v2 == node && arc->flags == 1))
+                       if ((arc->head == node && arc->flag == -1) || (arc->tail == node && arc->flag == 1))
                        {
                                if (incomingArc == NULL)
                                {
@@ -5480,12 +5010,12 @@ void generateSkeletonFromReebGraph(ReebGraph *rg)
                        EditBone *parentBone = BLI_ghash_lookup(arcBoneMap, incomingArc);
 
                        /* Look for outgoing arcs and parent their bones */
-                       for (i = 0; node->arcs[i] != NULL; i++)
+                       for (i = 0; i < node->degree; i++)
                        {
                                arc = node->arcs[i];