merging trunk 15964 -> 16116
authorMartin Poirier <theeth@yahoo.com>
Thu, 14 Aug 2008 21:16:48 +0000 (21:16 +0000)
committerMartin Poirier <theeth@yahoo.com>
Thu, 14 Aug 2008 21:16:48 +0000 (21:16 +0000)
30 files changed:
intern/bmfont/intern/BDF2BMF.py [deleted file]
release/scripts/reeb.py [new file with mode: 0644]
source/blender/blenkernel/BKE_bvhutils.h [deleted file]
source/blender/blenkernel/intern/bvhutils.c [deleted file]
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/intern/BLI_ghash.c
source/blender/blenlib/intern/arithb.c
source/blender/blenlib/intern/graph.c [new file with mode: 0644]
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.cpp
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)
diff --git a/source/blender/blenkernel/BKE_bvhutils.h b/source/blender/blenkernel/BKE_bvhutils.h
deleted file mode 100644 (file)
index dd9ea61..0000000
+++ /dev/null
@@ -1,98 +0,0 @@
-/**
- *
- * $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.
- *
- * The Original Code is Copyright (C) 2006 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): AndrĂ© Pinto
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-#ifndef BKE_BVHUTILS_H
-#define BKE_BVHUTILS_H
-
-#include "BLI_kdopbvh.h"
-
-/*
- * This header encapsulates necessary code to buld a BVH
- */
-
-struct DerivedMesh;
-struct MVert;
-struct MFace;
-
-/*
- * struct that kepts basic information about a BVHTree build from a mesh
- */
-typedef struct BVHTreeFromMesh
-{
-       struct BVHTree *tree;
-
-       /* default callbacks to bvh nearest and raycast */
-       BVHTree_NearestPointCallback nearest_callback;
-       BVHTree_RayCastCallback      raycast_callback;
-
-       /* Mesh represented on this BVHTree */
-       struct DerivedMesh *mesh; 
-
-       /* Vertex array, so that callbacks have instante access to data */
-       struct MVert *vert;
-       struct MFace *face;
-
-       /* radius for raycast */
-       float sphere_radius;
-
-} BVHTreeFromMesh;
-
-/*
- * Builds a bvh tree where nodes are the vertexs of the given mesh.
- * Configures BVHTreeFromMesh.
- *
- * The tree is build in mesh space coordinates, this means special care must be made on queries
- * so that the coordinates and rays are first translated on the mesh local coordinates.
- * Reason for this is that later bvh_from_mesh_* might use a cache system and so it becames possible to reuse
- * a BVHTree.
- * 
- * free_bvhtree_from_mesh should be called when the tree is no longer needed.
- */
-void bvhtree_from_mesh_verts(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
-
-/*
- * Builds a bvh tree where nodes are the faces of the given mesh.
- * Configures BVHTreeFromMesh.
- *
- * The tree is build in mesh space coordinates, this means special care must be made on queries
- * so that the coordinates and rays are first translated on the mesh local coordinates.
- * Reason for this is that later bvh_from_mesh_* might use a cache system and so it becames possible to reuse
- * a BVHTree.
- * 
- * free_bvhtree_from_mesh should be called when the tree is no longer needed.
- */
-void bvhtree_from_mesh_faces(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
-
-/*
- * Frees data allocated by a call to bvhtree_from_mesh_*.
- */
-void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data);
-
-#endif
-
diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c
deleted file mode 100644 (file)
index 042e2af..0000000
+++ /dev/null
@@ -1,577 +0,0 @@
-/**
- *
- * $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.
- *
- * The Original Code is Copyright (C) Blender Foundation.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): AndrĂ© Pinto.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-#include <stdio.h>
-#include <string.h>
-#include <math.h>
-
-#include "BKE_bvhutils.h"
-
-#include "DNA_object_types.h"
-#include "DNA_modifier_types.h"
-#include "DNA_meshdata_types.h"
-
-#include "BKE_DerivedMesh.h"
-#include "BKE_utildefines.h"
-#include "BKE_deform.h"
-#include "BKE_cdderivedmesh.h"
-#include "BKE_displist.h"
-#include "BKE_global.h"
-
-#include "BLI_arithb.h"
-
-/* Math stuff for ray casting on mesh faces and for nearest surface */
-
-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))
-               return dist;
-
-       return FLT_MAX;
-}
-
-static float sphereray_tri_intersection(const BVHTreeRay *ray, float radius, const float m_dist, const float *v0, const float *v1, const float *v2)
-{
-       
-       float idist;
-       float p1[3];
-       float plane_normal[3], hit_point[3];
-
-       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))
-       {
-               return idist * m_dist;
-       }
-
-       return FLT_MAX;
-}
-
-
-/*
- * Function adapted from David Eberly's distance tools (LGPL)
- * http://www.geometrictools.com/LibFoundation/Distance/Distance.html
- */
-static float nearest_point_in_tri_surface(const float *v0,const float *v1,const float *v2,const float *p, int *v, int *e, float *d, float *nearest )
-{
-       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 )
-       {
-               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;
-               }
-       }
-       else
-       {
-               float tmp0, tmp1, numer, denom;
-
-               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
-               {
-                       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;
-                               }
-                       }
-                       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;
-                               }
-                       }
-               }
-               else  // Region 1
-               {
-                       numer = A11 + B1 - A01 - B0;
-                       if ( numer <= 0.0f )
-                       {
-                               S = 0.0f;
-                               T = 1.0f;
-                               sqrDist = A11 + 2.0f * B1 + C;
-                               lv = 2;
-                       }
-                       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;
-                               }
-                       }
-               }
-       }
-
-       // Account for numerical round-off error
-       if ( sqrDist < FLT_EPSILON )
-               sqrDist = 0.0f;
-       
-       {
-               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 );
-       }
-       *v = lv;
-       *e = le;
-
-       return sqrDist;
-}
-
-
-/*
- * BVH from meshs callbacks
- */
-
-// Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_faces.
-// userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
-static void mesh_faces_nearest_point(void *userdata, int index, const float *co, BVHTreeNearest *nearest)
-{
-       const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
-       MVert *vert     = data->vert;
-       MFace *face = data->face + index;
-
-       float *t0, *t1, *t2, *t3;
-       t0 = vert[ face->v1 ].co;
-       t1 = vert[ face->v2 ].co;
-       t2 = vert[ face->v3 ].co;
-       t3 = face->v4 ? vert[ face->v4].co : NULL;
-
-       
-       do
-       {       
-               float nearest_tmp[3], col_normal[3], dist;
-               int vertex, edge;
-               
-               dist = nearest_point_in_tri_surface(t0, t1, t2, co, &vertex, &edge, col_normal, nearest_tmp);
-               if(dist < nearest->dist)
-               {
-                       nearest->index = index;
-                       nearest->dist = dist;
-                       VECCOPY(nearest->co, nearest_tmp);
-                       VECCOPY(nearest->no, col_normal);
-               }
-
-               t1 = t2;
-               t2 = t3;
-               t3 = NULL;
-
-       } while(t2);
-}
-
-// Callback to bvh tree raycast. The tree must bust have been built using bvhtree_from_mesh_faces.
-// userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
-static void mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
-{
-       const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
-       MVert *vert     = data->vert;
-       MFace *face = data->face + index;
-
-       float *t0, *t1, *t2, *t3;
-       t0 = vert[ face->v1 ].co;
-       t1 = vert[ face->v2 ].co;
-       t2 = vert[ face->v3 ].co;
-       t3 = face->v4 ? vert[ face->v4].co : NULL;
-
-       
-       do
-       {       
-               float dist;
-               if(data->sphere_radius == 0.0f)
-                       dist = ray_tri_intersection(ray, hit->dist, t0, t1, t2);
-               else
-                       dist = sphereray_tri_intersection(ray, data->sphere_radius, hit->dist, t0, t1, t2);
-
-               if(dist >= 0 && dist < hit->dist)
-               {
-                       hit->index = index;
-                       hit->dist = dist;
-                       VECADDFAC(hit->co, ray->origin, ray->direction, dist);
-
-                       CalcNormFloat(t0, t1, t2, hit->no);
-               }
-
-               t1 = t2;
-               t2 = t3;
-               t3 = NULL;
-
-       } while(t2);
-}
-
-/*
- * BVH builders
- */
-// Builds a bvh tree.. where nodes are the vertexs of the given mesh
-void bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis)
-{
-       int i;
-       int numVerts= mesh->getNumVerts(mesh);
-       MVert *vert     = mesh->getVertDataArray(mesh, CD_MVERT);
-       BVHTree *tree = NULL;
-
-       memset(data, 0, sizeof(*data));
-
-       if(vert == NULL)
-       {
-               printf("bvhtree cant be build: cant get a vertex array");
-               return;
-       }
-
-       tree = BLI_bvhtree_new(numVerts, epsilon, tree_type, axis);
-       if(tree != NULL)
-       {
-               for(i = 0; i < numVerts; i++)
-                       BLI_bvhtree_insert(tree, i, vert[i].co, 1);
-
-               BLI_bvhtree_balance(tree);
-
-               data->tree = tree;
-
-               //a NULL nearest callback works fine
-               //remeber the min distance to point is the same as the min distance to BV of point
-               data->nearest_callback = NULL;
-               data->raycast_callback = NULL;
-
-               data->mesh = mesh;
-               data->vert = mesh->getVertDataArray(mesh, CD_MVERT);
-               data->face = mesh->getFaceDataArray(mesh, CD_MFACE);
-
-               data->sphere_radius = epsilon;
-       }
-}
-
-// Builds a bvh tree.. where nodes are the faces of the given mesh.
-void bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis)
-{
-       int i;
-       int numFaces= mesh->getNumFaces(mesh);
-       MVert *vert     = mesh->getVertDataArray(mesh, CD_MVERT);
-       MFace *face = mesh->getFaceDataArray(mesh, CD_MFACE);
-       BVHTree *tree = NULL;
-
-       memset(data, 0, sizeof(*data));
-
-       if(vert == NULL && face == NULL)
-       {
-               printf("bvhtree cant be build: cant get a vertex/face array");
-               return;
-       }
-
-       /* Create a bvh-tree of the given target */
-       tree = BLI_bvhtree_new(numFaces, epsilon, tree_type, axis);
-       if(tree != NULL)
-       {
-               for(i = 0; i < numFaces; i++)
-               {
-                       float co[4][3];
-                       VECCOPY(co[0], vert[ face[i].v1 ].co);
-                       VECCOPY(co[1], vert[ face[i].v2 ].co);
-                       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);
-
-               data->tree = tree;
-               data->nearest_callback = mesh_faces_nearest_point;
-               data->raycast_callback = mesh_faces_spherecast;
-
-               data->mesh = mesh;
-               data->vert = mesh->getVertDataArray(mesh, CD_MVERT);
-               data->face = mesh->getFaceDataArray(mesh, CD_MFACE);
-
-               data->sphere_radius = epsilon;
-       }
-}
-
-// Frees data allocated by a call to bvhtree_from_mesh_*.
-void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data)
-{
-       if(data->tree)
-       {
-               BLI_bvhtree_free(data->tree);
-               memset( data, 0, sizeof(data) );
-       }
-}
-
-
index 553107dd2648aa782251243f34a72664ebcec1bb..6102ee9a5d760404c2c3c4ed4feb3118e9a65bb4 100644 (file)
@@ -252,6 +252,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 c22b6f79e08f91c86eee4054db39a96808ec6b05..ccb592bba052eea40ae27e8db964acdc4af594f1 100644 (file)
@@ -262,6 +262,7 @@ void Vec2Subf(float *v, float *v1, float *v2);
 void Vec2Copyf(float *v1, float *v2);
 
 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..89f21b9
--- /dev/null
@@ -0,0 +1,118 @@
+#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 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_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(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_removeDoubleNodes(BGraph *graph, 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 */
+
+#endif /*BLI_GRAPH_H_*/
index 227cb8f5e9a5e23c95f2c446f01bbe8020691d12..bae6ad428ea39c0f6cde431c2e161d7b309a4832 100644 (file)
@@ -198,12 +198,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;
@@ -217,6 +211,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 8bd7ad405af82b5e2ef492a69830c83051ad65bc..4cc8e45b1cffe0e2c3c40e3c2b9f466419201e7d 100644 (file)
@@ -1336,6 +1336,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];
diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c
new file mode 100644 (file)
index 0000000..80d770e
--- /dev/null
@@ -0,0 +1,1012 @@
+/**
+ * $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_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 *rg)
+{
+       BNode *node;
+       BArc *arc;
+
+       for(node = rg->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 = rg->arcs.first; arc; arc= arc->next)
+       {
+               addArcToNodeAdjacencyList(arc->head, arc);
+               addArcToNodeAdjacencyList(arc->tail, arc);
+       }
+
+       for(node = rg->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* rg, 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 = rg->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 *rg)
+{
+       BNode *node;
+
+       for(node = rg->nodes.first; node; node = node->next)
+       {
+               if (node->arcs != NULL)
+               {
+                       MEM_freeN(node->arcs);
+                       node->arcs = NULL;
+               }
+       }
+}
+
+int BLI_hasAdjacencyList(BGraph *rg)
+{
+       BNode *node;
+       
+       for(node = rg->nodes.first; node; node = node->next)
+       {
+               if (node->arcs == NULL)
+               {
+                       return 0;
+               }
+       }
+       
+       return 1;
+}
+
+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_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);
+               }
+       }
+}
+
+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);
+                               
+                               BLI_removeNode(graph, node_replaced);
+                       }
+               }
+       }
+       
+}
+/************************************* SUBGRAPH DETECTION **********************************************/
+
+void flagSubgraph(BNode *node, int subgraph)
+{
+       if (node->flag == 0)
+       {
+               BArc *arc;
+               int i;
+               
+               node->flag = 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);
+       }
+       
+       BLI_flagNodes(graph, 0);
+       
+       for (node = graph->nodes.first; node; node = node->next)
+       {
+               if (node->flag == 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 BLI_subtreeShape(BNode *node, BArc *rootArc, int include_root)
+{
+       int depth = 0;
+       
+       if (include_root)
+       {
+               BNode *newNode = BLI_otherNode(rootArc, node);
+               return BLI_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];
+                               
+                               /* only arcs that go down the tree */
+                               if (arc != rootArc)
+                               {
+                                       BNode *newNode = BLI_otherNode(arc, node);
+                                       depth += BLI_subtreeShape(newNode, arc, 0);
+                               }
+                       }
+               }
+               
+               return SHAPE_RADIX * depth + 1;
+       }
+}
+
+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->flag == 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 = 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)
+                       {
+                               /* 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(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 ad19cde3c9ba963ad5700bd4cdb848b396056286..c399ca13437d48bdc99ecbfaedfbeb0e4ffc5842 100644 (file)
@@ -7343,6 +7343,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 07fc8f08b4a0a7be2e51fb366e15be1f4f10dc85..f69ebd133bd80291dae9708f3ac538e62e2415e8 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);
@@ -144,6 +146,9 @@ void        show_all_armature_bones(void);
 
 #define BONESEL_NOSEL  0x80000000      /* Indicates a negative number */
 
+/* from autoarmature */
+void BIF_retargetArmature();
+
 /* 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 8e80f630cf25f2d8f9098fc9c6f2de68c196bed0..6cf010571c479ba61b2d8d06e735084656bbc50c 100644 (file)
@@ -446,7 +446,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..815afed6dfa909a0d3d835466b2767b37a6e1a33 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;
+       struct ReebGraph *link_up; /* for multi resolution filtering, points to higher levels */
 } ReebGraph;
 
 typedef struct EmbedBucket {
@@ -49,13 +63,22 @@ 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 symmetry_level;
+       int symmetry_flag;
+       float symmetry_axis[3];
+       /*********************************/
+
        int index;
-       int degree;
        float weight;
-       float p[3];
-       int flags;
+       struct ReebNode *link_down; /* for multi resolution filtering, points to lower levels, if present */
+       struct ReebNode *link_up;
 } ReebNode;
 
 typedef struct ReebEdge {
@@ -63,15 +86,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 {
@@ -80,6 +116,7 @@ typedef struct ReebArcIterator {
        int start;
        int end;
        int stride;
+       int length;
 } ReebArcIterator;
 
 struct EditMesh;
@@ -87,21 +124,27 @@ struct EditMesh;
 int weightToHarmonic(struct EditMesh *em);
 int weightFromDistance(struct EditMesh *em);
 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 +153,30 @@ 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_lowestLevelNode(ReebNode *node);
+
+void REEB_freeGraph(ReebGraph *rg);
+void REEB_exportGraph(ReebGraph *rg, int count);
+void REEB_draw();
+
 
 #endif /*REEB_H_*/
index 75affbfa7f5133e7854fe540c031cc5e68838ce2..55d5a68662a7b9139b977407e380d8b57af46489 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
@@ -830,12 +836,20 @@ 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_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..e6bd97f
--- /dev/null
@@ -0,0 +1,1822 @@
+/**
+ * $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 "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;
+
+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 controls;
+       ListBase threads;
+       
+       GHash *bones_map;
+       
+       Object *ob;
+} RigGraph;
+
+typedef struct RigNode {
+       void *next, *prev;
+       float p[3];
+       int flag;
+
+       int degree;
+       struct BArc **arcs;
+
+       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;
+} RigEdge;
+
+#define RIG_CTRL_DONE  1
+
+typedef struct RigControl {
+       struct RigControl *next, *prev;
+       EditBone *bone;
+       EditBone *parent;
+       float   offset[3];
+       int             flag;
+} RigControl;
+
+typedef struct RetargetParam {
+       RigGraph        *rigg;
+       RigArc          *iarc;
+} RetargetParam;
+
+typedef enum 
+{
+       RETARGET_LENGTH,
+       RETARGET_AGGRESSIVE
+} RetargetMode; 
+
+typedef enum
+{
+       METHOD_BRUTE_FORCE = 0,
+       METHOD_ANNEALING = 1
+} RetargetMethod;
+
+/*******************************************************************************************************/
+
+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;
+}
+
+
+/************************************ DESTRUCTORS ******************************************************/
+
+void RIG_freeRigArc(BArc *arc)
+{
+       BLI_freelistN(&((RigArc*)arc)->edges);
+}
+
+void RIG_freeRigGraph(BGraph *rg)
+{
+       BNode *node;
+       BArc *arc;
+       
+       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((BGraph*)rg, (BNode*)node);
+       }
+       BLI_freelistN(&rg->nodes);
+       
+       BLI_ghash_free(((RigGraph*)rg)->bones_map, NULL, NULL);
+       
+       MEM_freeN(rg);
+}
+
+/************************************* ALLOCATORS ******************************************************/
+
+static RigGraph *newRigGraph()
+{
+       RigGraph *rg;
+       rg = MEM_callocN(sizeof(RigGraph), "rig graph");
+       
+       rg->head = NULL;
+       
+       rg->bones_map = BLI_ghash_new(BLI_ghashutil_strhash, BLI_ghashutil_strcmp);
+       
+       rg->free_arc = RIG_freeRigArc;
+       rg->free_node = NULL;
+       
+       BLI_init_threads(&rg->threads, exec_retargetArctoArc, 2); /* fix number of threads */
+       
+       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 *newRigNodeTail(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->tail = node;
+
+       return node;
+}
+
+static void RIG_addEdgeToArc(RigArc *arc, float tail[3], EditBone *bone)
+{
+       RigEdge *edge;
+
+       edge = MEM_callocN(sizeof(RigEdge), "rig edge");
+       BLI_addtail(&arc->edges, edge);
+
+
+       VECCOPY(edge->tail, tail);
+       edge->bone = bone;
+       
+       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_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;
+}
+
+static void RIG_parentControl(RigControl *ctrl, EditBone *parent)
+{
+       if (parent)
+       {
+               ctrl->parent = parent;
+               
+               VecSubf(ctrl->offset, ctrl->bone->head, ctrl->parent->tail);
+       }
+}
+
+static void RIG_reconnectControlBones(RigGraph *rg)
+{
+       RigControl *ctrl;
+       
+       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 parent to bone corresponding to pchan */
+                                                       EditBone *parent = BLI_ghash_lookup(rg->bones_map, pchan->name);
+                                                       
+                                                       RIG_parentControl(ctrl, parent);
+                                                       found = 1;
+                                               }
+                                       }
+                                       
+                                       if (cti->flush_constraint_targets)
+                                               cti->flush_constraint_targets(con, &targets, 0);
+                               }
+                       }
+               }
+
+               /* if not found yet, check parent */            
+               if (found == 0)
+               {
+                       RIG_parentControl(ctrl, ctrl->bone->parent);
+               }
+       }
+}
+
+/*******************************************************************************************************/
+
+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;
+               
+               BLI_ghash_insert(rg->bones_map, bone->name, bone);
+               
+               if ((bone->flag & BONE_NO_DEFORM) == 0)
+               {
+                       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
+               {
+                       RIG_addControlBone(rg, bone);
+               }
+               
+               nb_children = countEditBoneChildren(list, bone);
+               if (nb_children > 1)
+               {
+                       RigNode *end_node = newRigNodeTail(rg, arc, bone->tail);
+                       int i;
+                       
+                       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_printArc(RigArc *arc)
+{
+       RigEdge *edge;
+
+       printf("\n");
+
+       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);
+       }       
+       printf("symmetry level: %i\n", arc->symmetry_level);
+
+       RIG_printNode((RigNode*)arc->tail, "tail");
+}
+
+void RIG_printGraph(RigGraph *rg)
+{
+       RigArc *arc;
+
+       for (arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               RIG_printArc(arc);      
+       }
+       
+       if (rg->head)
+       {
+               RIG_printNode(rg->head, "HEAD NODE:");
+       }
+       else
+       {
+               printf("HEAD NODE: NONE\n");
+       }       
+}
+
+/*******************************************************************************************************/
+
+static RigGraph *armatureToGraph(Object *ob, ListBase *list)
+{
+       EditBone *ebone;
+       RigGraph *rg;
+       
+       rg = newRigGraph();
+       
+       rg->ob = ob;
+
+       /* Do the rotations */
+       for (ebone = list->first; ebone; ebone=ebone->next){
+               if (ebone->parent == NULL)
+               {
+                       RIG_arcFromBoneChain(rg, list, ebone, NULL);
+               }
+       }
+       
+       RIG_reconnectControlBones(rg);
+       
+       BLI_removeDoubleNodes((BGraph*)rg, 0.001);
+       
+       BLI_buildAdjacencyList((BGraph*)rg);
+       
+       RIG_findHead(rg);
+       
+       return rg;
+}
+
+/************************************ RETARGETTING *****************************************************/
+
+static void repositionControl(RigGraph *rigg, RigControl *ctrl, float parent[3], float qrot[4], float resize)
+{
+       RigControl *ctrl_child;
+       float parent_offset[3], tail_offset[3];
+       
+       VecSubf(tail_offset, ctrl->bone->tail, ctrl->bone->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, parent, parent_offset); 
+       VecAddf(ctrl->bone->tail, ctrl->bone->head, tail_offset);
+       
+       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->parent == ctrl->bone)
+               {
+                       repositionControl(rigg, ctrl_child, ctrl->bone->tail, qrot, resize);
+               }
+       }
+
+}
+
+static void repositionBone(RigGraph *rigg, EditBone *bone, float vec0[3], float vec1[3])
+{
+       RigControl *ctrl;
+       float qrot[4], resize = 0;
+       
+       QuatOne(qrot);
+       
+       for (ctrl = rigg->controls.first; ctrl; ctrl = ctrl->next)
+       {
+               if (ctrl->parent == bone)
+               {
+                       if (resize == 0)
+                       {
+                               float v1[3], v2[3];
+                               float l1, l2;
+                               
+                               VecSubf(v1, bone->tail, bone->head);
+                               VecSubf(v2, vec1, vec0);
+                               
+                               l1 = Normalize(v1);
+                               l2 = Normalize(v2);
+
+                               resize = l2 / l1;
+                               
+                               RotationBetweenVectorsToQuat(qrot, v1, v2);
+                       }
+                       
+                       repositionControl(rigg, ctrl, vec1, qrot, resize);
+               }
+       }
+       
+       VECCOPY(bone->head, vec0);
+       VECCOPY(bone->tail, vec1);
+}
+
+static RetargetMode detectArcRetargetMode(RigArc *arc);
+static void retargetArctoArcLength(RigGraph *rigg, RigArc *iarc);
+
+
+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;
+}
+
+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");
+}
+
+#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], float length1, float length2)
+{
+       if (G.scene->toolsettings->skgen_retarget_angle_weight > 0)
+       {
+               float current_angle;
+               
+               if (length1 > 0 && length2 > 0)
+               {
+                       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 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, length1, length2);
+
+       /* 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 void retargetArctoArcAggresive(RigGraph *rigg, RigArc *iarc)
+{
+       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;
+       int symmetry_axis = 0;
+       RetargetMethod method = METHOD_ANNEALING; //G.scene->toolsettings->skgen_optimisation_method;
+       int i;
+
+       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");
+       
+       /* symmetry axis */
+       if (earc->symmetry_level == 1 && iarc->symmetry_level == 1)
+       {
+               symmetry_axis = 1;
+               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 (nb_joints < 3)
+       {
+               method = METHOD_BRUTE_FORCE;
+       }
+       
+       if (G.scene->toolsettings->skgen_optimisation_method == 0)
+       {
+               method = METHOD_BRUTE_FORCE;
+       }
+
+       /* BRUTE FORCE */
+       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, length1, length2);
+                                       }
+               
+                                       /* 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;
+
+               switch (G.scene->toolsettings->skgen_optimisation_method)
+               {
+                       case 1:
+                               kmax = 100000;
+                               break;
+                       case 2:
+                               kmax = nb_joints * earc->bcount * 200;
+                               break;
+               }
+               
+               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];
+               }
+               
+               printf("initial cost: %f\n", cost);
+               printf("kmax: %i\n", kmax);
+               
+               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);
+       
+       printPositions(best_positions, nb_joints);
+       printMovesNeeded(best_positions, nb_joints);
+       printf("min_cost %f\n", min_cost);
+       printf("buckets: %i\n", earc->bcount);
+
+       /* set joints to best position */
+       for (edge = iarc->edges.first, i = 0;
+                edge;
+                edge = edge->next, i++)
+       {
+               EditBone *bone = edge->bone;
+               
+               if (i < nb_joints)
+               {
+                       bucket = peekBucket(&iter, best_positions[i]);
+                       vec1 = bucket->p;
+               }
+               else
+               {
+                       vec1 = node_end->p;
+               }
+               
+               if (bone)
+               {
+                       repositionBone(rigg, bone, 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)
+{
+       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;
+       int symmetry_axis = 0;
+
+       
+       /* symmetry axis */
+       if (earc->symmetry_level == 1 && iarc->symmetry_level == 1)
+       {
+               symmetry_axis = 1;
+               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)
+       {
+               EditBone *bone = edge->bone;
+               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 (bone)
+               {
+                       repositionBone(rigg, bone, vec0, vec1);
+               }
+               
+               vec0 = vec1;
+               previous_vec = vec1;
+       }
+}
+
+static void retargetArctoArc(RigGraph *rigg, RigArc *iarc)
+{
+       ReebArc *earc = iarc->link_mesh;
+       
+       if (BLI_countlist(&iarc->edges) == 1)
+       {
+               RigEdge *edge = iarc->edges.first;
+               EditBone *bone = edge->bone;
+               
+               /* symmetry axis */
+               if (earc->symmetry_level == 1 && iarc->symmetry_level == 1)
+               {
+                       repositionBone(rigg, bone, earc->tail->p, earc->head->p);
+               }
+               /* or not */
+               else
+               {
+                       repositionBone(rigg, bone, earc->head->p, earc->tail->p);
+               }
+       }
+       else
+       {
+               RetargetMode mode = detectArcRetargetMode(iarc);
+               
+               if (mode == RETARGET_AGGRESSIVE)
+               {
+                       retargetArctoArcAggresive(rigg, iarc);
+               }
+               else
+               {               
+                       retargetArctoArcLength(rigg, iarc);
+               }
+       }
+}
+
+void *exec_retargetArctoArc(void *param)
+{
+       RetargetParam *p = (RetargetParam*)param;
+       retargetArctoArc(p->rigg, p->iarc);
+       MEM_freeN(param);
+       
+       return NULL;
+}
+
+void thread_retargetArctoArc(RigGraph *rigg, RigArc *iarc)
+{
+}
+
+static void matchMultiResolutionNode(RigNode *inode, ReebNode *top_node)
+{
+       ReebNode *enode;
+       int ishape, eshape;
+       
+       enode = top_node;
+       
+       ishape = BLI_subtreeShape((BNode*)inode, NULL, 0) % SHAPE_LEVELS;
+       eshape = BLI_subtreeShape((BNode*)enode, NULL, 0) % SHAPE_LEVELS;
+       
+       inode->link_mesh = enode;
+
+       while (ishape == eshape && enode->link_down)
+       {
+               inode->link_mesh = enode;
+
+               enode = enode->link_down;
+               eshape = BLI_subtreeShape((BNode*)enode, NULL, 0) % SHAPE_LEVELS;
+       } 
+}
+
+static void matchMultiResolutionArc(RigNode *start_node, RigArc *next_iarc, ReebArc *next_earc)
+{
+       ReebNode *enode = next_earc->head;
+       int ishape, eshape;
+
+       ishape = BLI_subtreeShape((BNode*)start_node, (BArc*)next_iarc, 1) % SHAPE_LEVELS;
+       eshape = BLI_subtreeShape((BNode*)enode, (BArc*)next_earc, 1) % SHAPE_LEVELS;
+       
+       while (ishape != eshape && next_earc->link_up)
+       {
+               next_earc->flag = 1; // mark previous as taken, to prevent backtrack on lower levels
+               
+               next_earc = next_earc->link_up;
+               enode = next_earc->head;
+               eshape = BLI_subtreeShape((BNode*)enode, (BArc*)next_earc, 1) % SHAPE_LEVELS;
+       } 
+
+       next_earc->flag = 1; // mark as taken
+       next_iarc->link_mesh = next_earc;
+       
+       /* mark all higher levels as taken too */
+       while (next_earc->link_up)
+       {
+               next_earc = next_earc->link_up;
+               next_earc->flag = 1; // mark as taken
+       }
+}
+
+static void matchMultiResolutionStartingNode(ReebGraph *reebg, RigNode *inode)
+{
+       ReebNode *enode;
+       int ishape, eshape;
+       
+       enode = reebg->nodes.first;
+       
+       ishape = BLI_subtreeShape((BNode*)inode, NULL, 0) % SHAPE_LEVELS;
+       eshape = BLI_subtreeShape((BNode*)enode, NULL, 0) % SHAPE_LEVELS;
+       
+       while (ishape != eshape && reebg->link_up)
+       {
+               reebg = reebg->link_up;
+               
+               enode = reebg->nodes.first;
+               
+               eshape = BLI_subtreeShape((BNode*)enode, NULL, 0) % SHAPE_LEVELS;
+       } 
+
+       inode->link_mesh = enode;
+}
+
+static void findCorrespondingArc(RigArc *start_arc, RigNode *start_node, RigArc *next_iarc)
+{
+       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;
+               
+       for(i = 0; i < enode->degree; i++)
+       {
+               next_earc = (ReebArc*)enode->arcs[i];
+               if (next_earc->flag == 0 && /* not already taken */
+                       next_earc->symmetry_flag == symmetry_flag &&
+                       next_earc->symmetry_group == symmetry_group &&
+                       next_earc->symmetry_level == symmetry_level)
+               {
+                       printf("-----------------------\n");
+                       printf("CORRESPONDING ARC FOUND\n");
+                       RIG_printArcBones(next_iarc);
+                       printf("flag %i -- symmetry level %i -- symmetry flag %i\n", next_earc->flag, next_earc->symmetry_level, next_earc->symmetry_flag);
+                       
+                       matchMultiResolutionArc(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)
+       {
+               if (enode->link_up)
+               {
+                       start_node->link_mesh = enode->link_up;
+                       findCorrespondingArc(start_arc, start_node, next_iarc);
+               }
+       }
+
+       /* still not found, print debug info */
+       if (next_iarc->link_mesh == NULL)
+       {
+               printf("--------------------------\n");
+               printf("NO CORRESPONDING ARC FOUND\n");
+               RIG_printArcBones(next_iarc);
+               
+               printf("LOOKING FOR\n");
+               printf("flag %i -- symmetry level %i -- symmetry flag %i\n", 0, symmetry_level, symmetry_flag);
+               
+               printf("CANDIDATES\n");
+               for(i = 0; i < enode->degree; i++)
+               {
+                       next_earc = (ReebArc*)enode->arcs[i];
+                       printf("flag %i -- symmetry level %i -- symmetry flag %i\n", next_earc->flag, next_earc->symmetry_level, next_earc->symmetry_flag);
+               }
+       }
+
+}
+
+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);
+               
+               enode = BIF_otherNodeFromIndex(earc, enode);
+               inode = (RigNode*)BLI_otherNode((BArc*)start_arc, (BNode*)inode);
+       
+               /* match with lowest node with correct shape */
+               matchMultiResolutionNode(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(start_arc, inode, next_iarc);
+                       if (next_iarc->link_mesh)
+                       {
+                               retargetSubgraph(rigg, next_iarc, inode);
+                       }
+               }
+       }
+}
+
+static void retargetGraphs(RigGraph *rigg)
+{
+       ReebGraph *reebg = rigg->link_mesh;
+       RigNode *inode;
+       
+       /* flag all ReebArcs as not taken */
+       BIF_flagMultiArcs(reebg, 0);
+       
+       /* return to first level */
+       reebg = rigg->link_mesh;
+       
+       inode = rigg->head;
+       
+       matchMultiResolutionStartingNode(reebg, inode);
+
+       retargetSubgraph(rigg, NULL, inode);
+}
+
+void BIF_retargetArmature()
+{
+       Object *ob;
+       Base *base;
+       ReebGraph *reebg;
+       
+       reebg = BIF_ReebGraphMultiFromEditMesh();
+       
+       
+       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;
+                               ListBase  list;
+                               bArmature *arm;
+                               
+                               arm = ob->data;
+                       
+                               /* Put the armature into editmode */
+                               list.first= list.last = NULL;
+                               make_boneList(&list, &arm->bonebase, NULL);
+                       
+                               rigg = armatureToGraph(ob, &list);
+                               
+                               BLI_markdownSymmetry((BGraph*)rigg, (BNode*)rigg->head, G.scene->toolsettings->skgen_symmetry_limit);
+                               
+                               printf("Armature graph created\n");
+               
+                               RIG_printGraph(rigg);
+                               
+                               rigg->link_mesh = reebg;
+                               
+                               printf("retargetting %s\n", ob->id.name);
+                               
+                               retargetGraphs(rigg);
+                               
+                               /* Turn the list into an armature */
+                               editbones_to_armature(&list, ob);
+                               
+                               BLI_freelistN(&list);
+
+                               RIG_freeRigGraph((BGraph*)rigg);
+                       }
+               }
+       }
+
+       REEB_freeGraph(reebg);
+       
+       BIF_undo_push("Retarget Skeleton");
+       
+       exit_editmode(EM_FREEDATA|EM_FREEUNDO|EM_WAITCURSOR); // freedata, and undo
+
+       allqueue(REDRAWVIEW3D, 0);
+}
index cb6f7e629fa42e9fd9c9bfa9982d151d8d09397c..906405344c47d7f3e2949ddda6111c11791da33d 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;
@@ -4895,6 +4897,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! */
@@ -4993,6 +4998,83 @@ 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_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, 63,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,             "Show Length");
+       uiDefButBitS(block, TOG, SKGEN_DISP_WEIGHT, REDRAWVIEW3D,       "Weight",                       1088, 40, 63,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,             "Show Weight");
+       uiDefButBitS(block, TOG, SKGEN_DISP_EMBED, REDRAWVIEW3D,        "Embed",                        1151, 40, 62,19, &G.scene->toolsettings->skgen_options, 0, 0, 0, 0,             "Show Arc Embedings");
+       uiDefButBitS(block, TOG, SKGEN_DISP_ORIG, REDRAWVIEW3D,         "Original",                     1213, 40, 62,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;
+
+       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,250,19, 0, 0, 0, 0, 0, "Retarget Selected Armature to this Mesh");
+
+       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: annealing max fixed, 2: annealing max linear");
+}
+
 static void editing_panel_mesh_skgen(Object *ob, Mesh *me)
 {
        uiBlock *block;
@@ -5000,20 +5082,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);
@@ -5030,18 +5109,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);
 }
 
@@ -6461,8 +6536,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 2030eb658dec077dec3cf7a64dc6498f16876bb7..65111bccfa9186f44dd2850d58c85cc36dacf440 100644 (file)
 
 #include "RE_pipeline.h"       // make_stars
 
+#include "reeb.h"
+
 #include "multires.h"
 
 /* For MULTISAMPLE_ARB #define.
@@ -3204,6 +3206,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 35986fcff4aa392ea3699a4dbad5946abd0c73b4..92c2db0eb5784e5b2e462a6aa2b856923f91a853 100644 (file)
@@ -4248,542 +4248,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 ******************************************/
 
@@ -4848,7 +4313,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);
        
@@ -4896,19 +4361,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 */
@@ -4917,15 +4410,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);
@@ -4934,12 +4429,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);
@@ -4948,6 +4477,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;
                        }
                }
 
@@ -4965,7 +4497,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)
        {
@@ -4975,8 +4507,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
        {
@@ -5108,8 +4640,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);
@@ -5126,7 +4656,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) 
        {
@@ -5136,43 +4666,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 */     
@@ -5214,12 +4744,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)
                                {
@@ -5240,12 +4770,12 @@ void generateSkeletonFromReebGraph(ReebGraph *rg)
                        EditBone *parentBone = BLI_ghash_lookup(arcBoneMap, incomingArc);
 
                        /* Look for outgoing arcs and parent their bones */
-                       for (i = 0; node->arcs[i] != NULL; i++)
+                       for (i = 0; i < node->degree; i++)
                        {
                                arc = node->arcs[i];
 
                                /* if arc is outgoing from the node */
-                               if ((arc->v1 == node && arc->flags == 1) || (arc->v2 == node && arc->flags == -1))
+                               if ((arc->head == node && arc->flag == 1) || (arc->tail == node && arc->flag == -1))
                                {
                                        EditBone *childBone = BLI_ghash_lookup(arcBoneMap, arc);
 
@@ -5263,89 +4793,21 @@ void generateSkeletonFromReebGraph(ReebGraph *rg)
        }
        
        BLI_ghash_free(arcBoneMap, NULL, NULL);
-
-       setcursor_space(SPACE_VIEW3D, CURSOR_EDIT);
        
        BIF_undo_push("Generate Skeleton");
 }
 
 void generateSkeleton(void)
 {
-       EditMesh *em = G.editMesh;
-       ReebGraph *rg = NULL;
-       int i;
+       ReebGraph *reebg;
        
-       if (em == NULL)
-               return;
-
        setcursor_space(SPACE_VIEW3D, CURSOR_WAIT);
-
-       if (weightFromDistance(em) == 0)
-       {
-               error("No selected vertex\n");
-               return;
-       }
-               
-       renormalizeWeight(em, 1.0f);
-       
-       weightToHarmonic(em);
-       
-#ifdef DEBUG_REEB
-       weightToVCol(em);
-#endif
-       
-       rg = generateReebGraph(em, G.scene->toolsettings->skgen_resolution);
-
-       verifyBuckets(rg);
        
-       /* Remove arcs without embedding */
-       filterNullReebGraph(rg);
+       reebg = BIF_ReebGraphFromEditMesh();
 
-       verifyBuckets(rg);
+       generateSkeletonFromReebGraph(reebg);
 
+       REEB_freeGraph(reebg);
 
-       i = 1;
-       /* filter until there's nothing more to do */
-       while (i == 1)
-       {
-               i = 0; /* no work done yet */
-               
-               if (G.scene->toolsettings->skgen_options & SKGEN_FILTER_EXTERNAL)
-               {
-                       i |= filterExternalReebGraph(rg, G.scene->toolsettings->skgen_threshold_external * G.scene->toolsettings->skgen_resolution);
-               }
-       
-               verifyBuckets(rg);
-       
-               if (G.scene->toolsettings->skgen_options & SKGEN_FILTER_INTERNAL)
-               {
-                       i |= filterInternalReebGraph(rg, G.scene->toolsettings->skgen_threshold_internal * G.scene->toolsettings->skgen_resolution);
-               }
-       }
-
-       verifyBuckets(rg);
-
-       repositionNodes(rg);
-       
-       verifyBuckets(rg);
-
-       /* Filtering might have created degree 2 nodes, so remove them */
-       removeNormalNodes(rg);
-       
-       verifyBuckets(rg);
-
-       for(i = 0; i <  G.scene->toolsettings->skgen_postpro_passes; i++)
-       {
-               postprocessGraph(rg, G.scene->toolsettings->skgen_postpro);
-       }
-
-       buildAdjacencyList(rg);
-       
-       sortNodes(rg);
-       
-       sortArcs(rg);
-       
-       generateSkeletonFromReebGraph(rg);
-
-       freeGraph(rg);
+       setcursor_space(SPACE_VIEW3D, CURSOR_EDIT);
 }
index 85fb5815c3e0eeaf2005ab779fc6371657d4b3dd..9938a8850ccb354b8dad2b2ed9cb20162ed480f0 100644 (file)
@@ -34,6 +34,7 @@
 #include "DNA_scene_types.h"
 #include "DNA_space_types.h"
 #include "DNA_meshdata_types.h"
+#include "DNA_armature_types.h"
 
 #include "MEM_guardedalloc.h"
 
 #include "BLI_arithb.h"
 #include "BLI_editVert.h"
 #include "BLI_edgehash.h"
+#include "BLI_ghash.h"
 
 #include "BDR_editobject.h"
 
+#include "BMF_Api.h"
+
 #include "BIF_editmesh.h"
 #include "BIF_editarmature.h"
 #include "BIF_interface.h"
 #include "BIF_toolbox.h"
 #include "BIF_graphics.h"
+#include "BIF_gl.h"
+#include "BIF_resources.h"
 
 #include "BKE_global.h"
 #include "BKE_utildefines.h"
 
 #include "reeb.h"
 
+/* REPLACE WITH NEW ONE IN UTILDEFINES ONCE PATCH IS APPLIED */
+#define FTOCHAR(val) (val<=0.0f)? 0 : ((val>(1.0f-0.5f/255.0f))? 255 : (char)((255.0f*val)+0.5f))
+
+ReebGraph *GLOBAL_RG = NULL;
+ReebGraph *FILTERED_RG = NULL;
+
 /*
  * Skeleton generation algorithm based on: 
  * "Harmonic Skeleton for Realistic Character Animation"
  * SIGGRAPH 2007
  * 
  * */
+#define DEBUG_REEB
+#define DEBUG_REEB_NODE
+
+typedef enum {
+       MERGE_LOWER,
+       MERGE_HIGHER,
+       MERGE_APPEND
+} MergeDirection;
 
 int mergeArcs(ReebGraph *rg, ReebArc *a0, ReebArc *a1);
+void mergeArcEdges(ReebGraph *rg, ReebArc *aDst, ReebArc *aSrc, MergeDirection direction);
 int mergeConnectedArcs(ReebGraph *rg, ReebArc *a0, ReebArc *a1);
 EditEdge * NextEdgeForVert(EditMesh *em, EditVert *v);
+void mergeArcFaces(ReebGraph *rg, ReebArc *aDst, ReebArc *aSrc);
+void addFacetoArc(ReebArc *arc, EditFace *efa);
 
-/***************************************** BUCKET UTILS **********************************************/
+void REEB_RadialSymmetry(BNode* root_node, RadialArc* ring, int count);
+void REEB_AxialSymmetry(BNode* root_node, BNode* node1, BNode* node2, struct BArc* barc1, BArc* barc2);
 
-void addVertToBucket(EmbedBucket *b, float co[3])
-{
-       b->nv++;
-       VecLerpf(b->p, b->p, co, 1.0f / b->nv);
-}
+void flipArcBuckets(ReebArc *arc);
 
-void removeVertFromBucket(EmbedBucket *b, float co[3])
+
+/***************************************** UTILS **********************************************/
+
+void REEB_freeArc(BArc *barc)
 {
-       VecMulf(b->p, (float)b->nv);
-       VecSubf(b->p, b->p, co);
-       b->nv--;
-       VecMulf(b->p, 1.0f / (float)b->nv);
+       ReebArc *arc = (ReebArc*)barc;
+       BLI_freelistN(&arc->edges);
+       
+       if (arc->buckets)
+               MEM_freeN(arc->buckets);
+               
+       if (arc->faces)
+               BLI_ghash_free(arc->faces, NULL, NULL);
+       
+       MEM_freeN(arc);
 }
 
-void mergeBuckets(EmbedBucket *bDst, EmbedBucket *bSrc)
+void REEB_freeGraph(ReebGraph *rg)
 {
-       if (bDst->nv > 0 && bSrc->nv > 0)
+       ReebArc *arc;
+       ReebNode *node;
+       
+       // free nodes
+       for( node = rg->nodes.first; node; node = node->next )
        {
-               bDst->nv += bSrc->nv;
-               VecLerpf(bDst->p, bDst->p, bSrc->p, (float)bSrc->nv / (float)(bDst->nv));
+               BLI_freeNode((BGraph*)rg, (BNode*)node);
        }
-       else if (bSrc->nv > 0)
+       BLI_freelistN(&rg->nodes);
+       
+       // free arcs
+       arc = rg->arcs.first;
+       while( arc )
        {
-               bDst->nv = bSrc->nv;
-               VECCOPY(bDst->p, bSrc->p);
+               ReebArc *next = arc->next;
+               REEB_freeArc((BArc*)arc);
+               arc = next;
+       }
+       
+       // free edge map
+       BLI_edgehash_free(rg->emap, NULL);
+       
+       /* free linked graph */
+       if (rg->link_up)
+       {
+               REEB_freeGraph(rg->link_up);
        }
+       
+       MEM_freeN(rg);
 }
 
-void mergeArcBuckets(ReebArc *aDst, ReebArc *aSrc, float start, float end)
+ReebGraph * newReebGraph()
 {
-       if (aDst->bcount > 0 && aSrc->bcount > 0)
-       {
-               int indexDst = 0, indexSrc = 0;
-               
-               start = MAX3(start, aDst->buckets[0].val, aSrc->buckets[0].val);
-               
-               while(indexDst < aDst->bcount && aDst->buckets[indexDst].val < start)
-               {
-                       indexDst++;
-               }
+       ReebGraph *rg;
+       rg = MEM_callocN(sizeof(ReebGraph), "reeb graph");
+       
+       rg->totnodes = 0;
+       rg->emap = BLI_edgehash_new();
+       
+       
+       rg->free_arc = REEB_freeArc;
+       rg->free_node = NULL;
+       rg->radial_symmetry = REEB_RadialSymmetry;
+       rg->axial_symmetry = REEB_AxialSymmetry;
+       
+       return rg;
+}
 
-               while(indexSrc < aSrc->bcount && aSrc->buckets[indexSrc].val < start)
-               {
-                       indexSrc++;
-               }
-               
-               for( ;  indexDst < aDst->bcount &&
-                               indexSrc < aSrc->bcount &&
-                               aDst->buckets[indexDst].val <= end &&
-                               aSrc->buckets[indexSrc].val <= end
-                               
-                        ;      indexDst++, indexSrc++)
-               {
-                       mergeBuckets(aDst->buckets + indexDst, aSrc->buckets + indexSrc);
-               }
+void BIF_flagMultiArcs(ReebGraph *rg, int flag)
+{
+       for ( ; rg; rg = rg->link_up)
+       {
+               BLI_flagArcs((BGraph*)rg, flag);
        }
 }
 
-void allocArcBuckets(ReebArc *arc)
+ReebNode * addNode(ReebGraph *rg, EditVert *eve, float weight)
 {
-       int i;
-       float start = ceil(arc->v1->weight);
-       arc->bcount = (int)(floor(arc->v2->weight) - start) + 1;
+       ReebNode *node = NULL;
        
-       if (arc->bcount > 0)
+       node = MEM_callocN(sizeof(ReebNode), "reeb node");
+       
+       node->flag = 0; // clear flag on init
+       node->symmetry_level = 0;
+       node->arcs = NULL;
+       node->degree = 0;
+       node->weight = weight;
+       node->index = rg->totnodes;
+       VECCOPY(node->p, eve->co);      
+       
+       BLI_addtail(&rg->nodes, node);
+       rg->totnodes++;
+       
+       return node;
+}
+
+ReebNode * copyNode(ReebGraph *rg, ReebNode *node)
+{
+       ReebNode *cp_node = NULL;
+       
+       cp_node = MEM_callocN(sizeof(ReebNode), "reeb node copy");
+       
+       memcpy(cp_node, node, sizeof(ReebNode));
+       
+       cp_node->prev = NULL;
+       cp_node->next = NULL;
+       cp_node->arcs = NULL;
+       
+       cp_node->link_up = NULL;
+       cp_node->link_down = NULL;
+       
+       BLI_addtail(&rg->nodes, cp_node);
+       rg->totnodes++;
+       
+       return cp_node; 
+}
+
+void relinkNodes(ReebGraph *low_rg, ReebGraph *high_rg)
+{
+       ReebNode *low_node, *high_node;
+       
+       if (low_rg == NULL || high_rg == NULL)
        {
-               arc->buckets = MEM_callocN(sizeof(EmbedBucket) * arc->bcount, "embed bucket");
-               
-               for(i = 0; i < arc->bcount; i++)
+               return;
+       }
+       
+       for (low_node = low_rg->nodes.first; low_node; low_node = low_node->next)
+       {
+               for (high_node = high_rg->nodes.first; high_node; high_node = high_node->next)
                {
-                       arc->buckets[i].val = start + i;
+                       if (low_node->index == high_node->index)
+                       {
+                               high_node->link_down = low_node;
+                               low_node->link_up = high_node;
+                               break;
+                       }
                }
        }
-       else
+}
+
+ReebNode *BIF_otherNodeFromIndex(ReebArc *arc, ReebNode *node)
+{
+       return (arc->head->index == node->index) ? arc->tail : arc->head;
+}
+
+ReebNode *BIF_lowestLevelNode(ReebNode *node)
+{
+       while (node->link_down)
        {
-               arc->buckets = NULL;
+               node = node->link_down;
        }
        
+       return node;
 }
 
-void resizeArcBuckets(ReebArc *arc)
+ReebArc * copyArc(ReebGraph *rg, ReebArc *arc)
 {
-       EmbedBucket *oldBuckets = arc->buckets;
-       int oldBCount = arc->bcount;
+       ReebArc *cp_arc;
+       ReebNode *node;
        
-       allocArcBuckets(arc);
+       cp_arc = MEM_callocN(sizeof(ReebArc), "reeb arc copy");
+
+       memcpy(cp_arc, arc, sizeof(ReebArc));
        
-       if (oldBCount != 0 && arc->bcount != 0)
+       cp_arc->link_up = arc;
+       
+       cp_arc->head = NULL;
+       cp_arc->tail = NULL;
+
+       cp_arc->prev = NULL;
+       cp_arc->next = NULL;
+
+       cp_arc->edges.first = NULL;
+       cp_arc->edges.last = NULL;
+
+       /* copy buckets */      
+       cp_arc->buckets = MEM_callocN(sizeof(EmbedBucket) * cp_arc->bcount, "embed bucket");
+       memcpy(cp_arc->buckets, arc->buckets, sizeof(EmbedBucket) * cp_arc->bcount);
+       
+       /* copy faces map */
+       cp_arc->faces = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
+       mergeArcFaces(rg, cp_arc, arc);
+       
+       /* find corresponding head and tail */
+       for (node = rg->nodes.first; node && (cp_arc->head == NULL || cp_arc->tail == NULL); node = node->next)
        {
-               int oldStart = (int)oldBuckets[0].val;
-               int oldEnd = (int)oldBuckets[oldBCount - 1].val;
-               int newStart = (int)arc->buckets[0].val;
-               int newEnd = (int)arc->buckets[arc->bcount - 1].val;
-               int oldOffset = 0;
-               int newOffset = 0;
-               int len;
-               
-               if (oldStart < newStart)
+               if (node->index == arc->head->index)
                {
-                       oldOffset = newStart - oldStart;
+                       cp_arc->head = node;
                }
-               else
+               else if (node->index == arc->tail->index)
                {
-                       newOffset = oldStart - newStart;
+                       cp_arc->tail = node;
                }
-               
-               len = MIN2(oldEnd - (oldStart + oldOffset) + 1, newEnd - (newStart - newOffset) + 1);
-               
-               memcpy(arc->buckets + newOffset, oldBuckets + oldOffset, len * sizeof(EmbedBucket)); 
        }
+       
+       BLI_addtail(&rg->arcs, cp_arc);
+       
+       return cp_arc;
+}
 
-       if (oldBuckets != NULL)
+ReebGraph * copyReebGraph(ReebGraph *rg)
+{
+       ReebNode *node;
+       ReebArc *arc;
+       ReebGraph *cp_rg = newReebGraph();
+       
+       cp_rg->resolution = rg->resolution;
+       cp_rg->length = rg->length;
+       cp_rg->link_up = rg;
+
+       /* Copy nodes */        
+       for (node = rg->nodes.first; node; node = node->next)
        {
-               MEM_freeN(oldBuckets);
+               copyNode(cp_rg, node);
        }
+       
+       /* Copy arcs */
+       for (arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               copyArc(cp_rg, arc);
+       }
+       
+       BLI_buildAdjacencyList((BGraph*)cp_rg);
+       
+       return cp_rg;
 }
-/***************************************** UTILS **********************************************/
 
 ReebEdge * copyEdge(ReebEdge *edge)
 {
@@ -213,7 +349,9 @@ ReebEdge * copyEdge(ReebEdge *edge)
 void printArc(ReebArc *arc)
 {
        ReebEdge *edge;
-       printf("arc: (%i)%f -> (%i)%f\n", arc->v1->index, arc->v1->weight, arc->v2->index, arc->v2->weight);
+       ReebNode *head = (ReebNode*)arc->head;
+       ReebNode *tail = (ReebNode*)arc->tail;
+       printf("arc: (%i) %f -> (%i) %f\n", head->index, head->weight, tail->index, tail->weight);
        
        for(edge = arc->edges.first; edge ; edge = edge->next)
        {
@@ -221,51 +359,46 @@ void printArc(ReebArc *arc)
        }
 }
 
-void freeArc(ReebArc *arc)
+void flipArc(ReebArc *arc)
 {
-       BLI_freelistN(&arc->edges);
-       
-       if (arc->buckets)
-               MEM_freeN(arc->buckets);
+       ReebNode *tmp;
+       tmp = arc->head;
+       arc->head = arc->tail;
+       arc->tail = tmp;
        
-       MEM_freeN(arc);
+       flipArcBuckets(arc);
 }
 
-void freeGraph(ReebGraph *rg)
+#ifdef DEBUG_REEB_NODE
+void NodeDegreeDecrement(ReebGraph *rg, ReebNode *node)
 {
-       ReebArc *arc;
-       ReebNode *node;
-       
-       // free nodes
-       for( node = rg->nodes.first; node; node = node->next )
-       {
-               // Free adjacency lists
-               if (node->arcs != NULL)
-               {
-                       MEM_freeN(node->arcs);
-               }
-       }
-       BLI_freelistN(&rg->nodes);
-       
-       // free arcs
-       arc = rg->arcs.first;
-       while( arc )
+       node->degree--;
+
+       if (node->degree == 0)
        {
-               ReebArc *next = arc->next;
-               freeArc(arc);
-               arc = next;
+               printf("would remove node %i\n", node->index);
        }
-       
-       // free edge map
-       BLI_edgehash_free(rg->emap, NULL);
-       
-       MEM_freeN(rg);
 }
 
+void NodeDegreeIncrement(ReebGraph *rg, ReebNode *node)
+{
+//     if (node->degree == 0)
+//     {
+//             printf("first connect node %i\n", node->index);
+//     }
+
+       node->degree++;
+}
+
+#else
+#define NodeDegreeDecrement(rg, node) {node->degree--;}
+#define NodeDegreeIncrement(rg, node) {node->degree++;}
+#endif
+
 void repositionNodes(ReebGraph *rg)
 {
-       ReebArc *arc = NULL;
-       ReebNode *node = NULL;
+       BArc *arc = NULL;
+       BNode *node = NULL;
        
        // Reset node positions
        for(node = rg->nodes.first; node; node = node->next)
@@ -275,23 +408,24 @@ void repositionNodes(ReebGraph *rg)
        
        for(arc = rg->arcs.first; arc; arc = arc->next)
        {
-               if (arc->bcount > 0)
+               if (((ReebArc*)arc)->bcount > 0)
                {
                        float p[3];
                        
-                       VECCOPY(p, arc->buckets[0].p);
-                       VecMulf(p, 1.0f / arc->v1->degree);
-                       VecAddf(arc->v1->p, arc->v1->p, p);
+                       VECCOPY(p, ((ReebArc*)arc)->buckets[0].p);
+                       VecMulf(p, 1.0f / arc->head->degree);
+                       VecAddf(arc->head->p, arc->head->p, p);
                        
-                       VECCOPY(p, arc->buckets[arc->bcount - 1].p);
-                       VecMulf(p, 1.0f / arc->v2->degree);
-                       VecAddf(arc->v2->p, arc->v2->p, p);
+                       VECCOPY(p, ((ReebArc*)arc)->buckets[((ReebArc*)arc)->bcount - 1].p);
+                       VecMulf(p, 1.0f / arc->tail->degree);
+                       VecAddf(arc->tail->p, arc->tail->p, p);
                }
        }
 }
 
 void verifyNodeDegree(ReebGraph *rg)
 {
+#ifdef DEBUG_REEB
        ReebNode *node = NULL;
        ReebArc *arc = NULL;
 
@@ -300,7 +434,7 @@ void verifyNodeDegree(ReebGraph *rg)
                int count = 0;
                for(arc = rg->arcs.first; arc; arc = arc->next)
                {
-                       if (arc->v1 == node || arc->v2 == node)
+                       if (arc->head == node || arc->tail == node)
                        {
                                count++;
                        }
@@ -309,7 +443,12 @@ void verifyNodeDegree(ReebGraph *rg)
                {
                        printf("degree error in node %i: expected %i got %i\n", node->index, count, node->degree);
                }
+               if (node->degree == 0)
+               {
+                       printf("zero degree node %i with weight %f\n", node->index, node->weight);
+               }
        }
+#endif
 }
 
 void verifyBuckets(ReebGraph *rg)
@@ -318,6 +457,9 @@ void verifyBuckets(ReebGraph *rg)
        ReebArc *arc = NULL;
        for(arc = rg->arcs.first; arc; arc = arc->next)
        {
+               ReebNode *head = (ReebNode*)arc->head;
+               ReebNode *tail = (ReebNode*)arc->tail;
+
                if (arc->bcount > 0)
                {
                        int i;
@@ -330,1594 +472,3123 @@ void verifyBuckets(ReebGraph *rg)
                                }
                        }
                        
-                       if (ceil(arc->v1->weight) < arc->buckets[0].val)
+                       if (ceil(head->weight) < arc->buckets[0].val)
                        {
                                printArc(arc);
-                               printf("alloc error in first bucket: %f should be %f \n", arc->buckets[0].val, ceil(arc->v1->weight));
+                               printf("alloc error in first bucket: %f should be %f \n", arc->buckets[0].val, ceil(head->weight));
                        }
-                       if (floor(arc->v2->weight) < arc->buckets[arc->bcount - 1].val)
+                       if (floor(tail->weight) < arc->buckets[arc->bcount - 1].val)
                        {
                                printArc(arc);
-                               printf("alloc error in last bucket: %f should be %f \n", arc->buckets[arc->bcount - 1].val, floor(arc->v2->weight));
+                               printf("alloc error in last bucket: %f should be %f \n", arc->buckets[arc->bcount - 1].val, floor(tail->weight));
                        }
                }
        }
 #endif
 }
 
-/************************************** ADJACENCY LIST *************************************************/
-
-void addArcToNodeAdjacencyList(ReebNode *node, ReebArc *arc)
+void verifyFaces(ReebGraph *rg)
 {
-       ReebArc **arclist;
-
-       for(arclist = node->arcs; *arclist; arclist++)
-       {       }
+#ifdef DEBUG_REEB
+       int total = 0;
+       ReebArc *arc = NULL;
+       for(arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               total += BLI_ghash_size(arc->faces);
+       }
        
-       *arclist = arc;
+#endif
 }
 
-void buildAdjacencyList(ReebGraph *rg)
+void verifyMultiResolutionLinks(ReebGraph *rg, int level)
 {
-       ReebNode *node = NULL;
-       ReebArc *arc = NULL;
-
-       for(node = rg->nodes.first; node; node = node->next)
+#ifdef DEBUG_REEB
+       ReebGraph *lower_rg = rg->link_up;
+       
+       if (lower_rg)
        {
-               if (node->arcs != NULL)
+               ReebArc *arc;
+               
+               for (arc = rg->arcs.first; arc; arc = arc->next)
                {
-                       MEM_freeN(node->arcs);
+                       if (BLI_findindex(&lower_rg->arcs, arc->link_up) == -1)
+                       {
+                               printf("missing arc %p for level %i\n", arc->link_up, level);
+                               printf("Source arc was ---\n");
+                               printArc(arc);
+
+                               arc->link_up = NULL;
+                       }
                }
                
-               node->arcs = MEM_callocN((node->degree + 1) * sizeof(ReebArc*), "adjacency list");
+               
+               verifyMultiResolutionLinks(lower_rg, level + 1);
        }
+#endif
+}
+/***************************************** BUCKET UTILS **********************************************/
+
+void addVertToBucket(EmbedBucket *b, float co[3])
+{
+       b->nv++;
+       VecLerpf(b->p, b->p, co, 1.0f / b->nv);
+}
+
+void removeVertFromBucket(EmbedBucket *b, float co[3])
+{
+       VecMulf(b->p, (float)b->nv);
+       VecSubf(b->p, b->p, co);
+       b->nv--;
+       VecMulf(b->p, 1.0f / (float)b->nv);
+}
 
-       for(arc = rg->arcs.first; arc; arc= arc->next)
+void mergeBuckets(EmbedBucket *bDst, EmbedBucket *bSrc)
+{
+       if (bDst->nv > 0 && bSrc->nv > 0)
+       {
+               bDst->nv += bSrc->nv;
+               VecLerpf(bDst->p, bDst->p, bSrc->p, (float)bSrc->nv / (float)(bDst->nv));
+       }
+       else if (bSrc->nv > 0)
        {
-               addArcToNodeAdjacencyList(arc->v1, arc);
-               addArcToNodeAdjacencyList(arc->v2, arc);
+               bDst->nv = bSrc->nv;
+               VECCOPY(bDst->p, bSrc->p);
        }
 }
 
-int hasAdjacencyList(ReebGraph *rg)
+void mergeArcBuckets(ReebArc *aDst, ReebArc *aSrc, float start, float end)
 {
-       ReebNode *node;
-       
-       for(node = rg->nodes.first; node; node = node->next)
+       if (aDst->bcount > 0 && aSrc->bcount > 0)
        {
-               if (node->arcs == NULL)
+               int indexDst = 0, indexSrc = 0;
+               
+               start = MAX3(start, aDst->buckets[0].val, aSrc->buckets[0].val);
+               
+               while(indexDst < aDst->bcount && aDst->buckets[indexDst].val < start)
+               {
+                       indexDst++;
+               }
+
+               while(indexSrc < aSrc->bcount && aSrc->buckets[indexSrc].val < start)
+               {
+                       indexSrc++;
+               }
+               
+               for( ;  indexDst < aDst->bcount &&
+                               indexSrc < aSrc->bcount &&
+                               aDst->buckets[indexDst].val <= end &&
+                               aSrc->buckets[indexSrc].val <= end
+                               
+                        ;      indexDst++, indexSrc++)
                {
-                       return 0;
+                       mergeBuckets(aDst->buckets + indexDst, aSrc->buckets + indexSrc);
                }
        }
-       
-       return 1;
 }
 
-int countConnectedArcs(ReebGraph *rg, ReebNode *node)
+void flipArcBuckets(ReebArc *arc)
 {
-       int count = 0;
+       int i, j;
        
-       /* use adjacency list if present */
-       if (node->arcs)
+       for (i = 0, j = arc->bcount - 1; i < j; i++, j--)
        {
-               ReebArc **arcs;
+               EmbedBucket tmp;
+               
+               tmp = arc->buckets[i];
+               arc->buckets[i] = arc->buckets[j];
+               arc->buckets[j] = tmp;
+       }
+}
+
+void allocArcBuckets(ReebArc *arc)
+{
+       int i;
+       float start = ceil(arc->head->weight);
+       arc->bcount = (int)(floor(arc->tail->weight) - start) + 1;
        
-               for(arcs = node->arcs; *arcs; arcs++)
+       if (arc->bcount > 0)
+       {
+               arc->buckets = MEM_callocN(sizeof(EmbedBucket) * arc->bcount, "embed bucket");
+               
+               for(i = 0; i < arc->bcount; i++)
                {
-                       count++;
+                       arc->buckets[i].val = start + i;
                }
        }
        else
        {
-               ReebArc *arc;
-               for(arc = rg->arcs.first; arc; arc = arc->next)
-               {
-                       if (arc->v1 == node || arc->v2 == node)
-                       {
-                               count++;
-                       }
-               }
+               arc->buckets = NULL;
        }
        
-       return count;
 }
 
-/****************************************** SMOOTHING **************************************************/
-
-void postprocessGraph(ReebGraph *rg, char mode)
+void resizeArcBuckets(ReebArc *arc)
 {
-       ReebArc *arc;
-       float fac1 = 0, fac2 = 1, fac3 = 0;
+       EmbedBucket *oldBuckets = arc->buckets;
+       int oldBCount = arc->bcount;
+       
+       allocArcBuckets(arc);
+       
+       if (oldBCount != 0 && arc->bcount != 0)
+       {
+               int oldStart = (int)oldBuckets[0].val;
+               int oldEnd = (int)oldBuckets[oldBCount - 1].val;
+               int newStart = (int)arc->buckets[0].val;
+               int newEnd = (int)arc->buckets[arc->bcount - 1].val;
+               int oldOffset = 0;
+               int newOffset = 0;
+               int len;
+               
+               if (oldStart < newStart)
+               {
+                       oldOffset = newStart - oldStart;
+               }
+               else
+               {
+                       newOffset = oldStart - newStart;
+               }
+               
+               len = MIN2(oldEnd - (oldStart + oldOffset) + 1, newEnd - (newStart - newOffset) + 1);
+               
+               memcpy(arc->buckets + newOffset, oldBuckets + oldOffset, len * sizeof(EmbedBucket)); 
+       }
 
-       switch(mode)
+       if (oldBuckets != NULL)
        {
-       case SKGEN_AVERAGE:
-               fac1 = fac2 = fac3 = 1.0f / 3.0f;
-               break;
-       case SKGEN_SMOOTH:
-               fac1 = fac3 = 0.25f;
-               fac2 = 0.5f;
-               break;
-       case SKGEN_SHARPEN:
-               fac1 = fac2 = -0.25f;
-               fac2 = 1.5f;
-               break;
-       default:
-               error("Unknown post processing mode");
-               return;
+               MEM_freeN(oldBuckets);
        }
+}
+
+void reweightBuckets(ReebArc *arc)
+{
+       int i;
+       float start = ceil((arc->head)->weight);
        
-       for(arc = rg->arcs.first; arc; arc = arc->next)
+       if (arc->bcount > 0)
        {
-               EmbedBucket *buckets = arc->buckets;
-               int bcount = arc->bcount;
-               int index;
-
-               for(index = 1; index < bcount - 1; index++)
+               for(i = 0; i < arc->bcount; i++)
                {
-                       VecLerpf(buckets[index].p, buckets[index].p, buckets[index - 1].p, fac1 / (fac1 + fac2));
-                       VecLerpf(buckets[index].p, buckets[index].p, buckets[index + 1].p, fac3 / (fac1 + fac2 + fac3));
+                       arc->buckets[i].val = start + i;
                }
        }
 }
 
-/********************************************SORTING****************************************************/
-
-int compareNodesWeight(void *vnode1, void *vnode2)
+static void interpolateBuckets(ReebArc *arc, float *start_p, float *end_p, int start_index, int end_index)
 {
-       ReebNode *node1 = (ReebNode*)vnode1;
-       ReebNode *node2 = (ReebNode*)vnode2;
+       int total;
+       int j;
        
-       if (node1->weight < node2->weight)
+       total = end_index - start_index + 2;
+       
+       for (j = start_index; j <= end_index; j++)
        {
-               return -1;
+               EmbedBucket *empty = arc->buckets + j;
+               empty->nv = 1;
+               VecLerpf(empty->p, start_p, end_p, (float)(j - start_index + 1) / total);
        }
-       if (node1->weight > node2->weight)
+}
+
+void fillArcEmptyBuckets(ReebArc *arc)
+{
+       float *start_p, *end_p;
+       int start_index, end_index;
+       int missing = 0;
+       int i;
+       
+       start_p = arc->head->p;
+       
+       for(i = 0; i < arc->bcount; i++)
        {
-               return 1;
+               EmbedBucket *bucket = arc->buckets + i;
+               
+               if (missing)
+               {
+                       if (bucket->nv > 0)
+                       {
+                               missing = 0;
+                               
+                               end_p = bucket->p;
+                               end_index = i - 1;
+                               
+                               interpolateBuckets(arc, start_p, end_p, start_index, end_index);
+                       }
+               }
+               else
+               {
+                       if (bucket->nv == 0)
+                       {
+                               missing = 1;
+                               
+                               if (i > 0)
+                               {
+                                       start_p = arc->buckets[i - 1].p;
+                               }
+                               start_index = i;
+                       }
+               }
        }
-       else
+       
+       if (missing)
        {
-               return 0;
+               end_p = arc->tail->p;
+               end_index = arc->bcount - 1;
+               
+               interpolateBuckets(arc, start_p, end_p, start_index, end_index);
        }
 }
 
-void sortNodes(ReebGraph *rg)
+static void ExtendArcBuckets(ReebArc *arc)
 {
-       BLI_sortlist(&rg->nodes, compareNodesWeight);
-}
+       ReebArcIterator iter;
+       EmbedBucket *previous, *bucket, *last_bucket, *first_bucket;
+       float average_length = 0, length;
+       int padding_head = 0, padding_tail = 0;
+       
+       if (arc->bcount == 0)
+       {
+               return; /* failsafe, shouldn't happen */
+       }
+       
+       initArcIterator(&iter, arc, arc->head);
+       
+       for (   previous = nextBucket(&iter), bucket = nextBucket(&iter);
+                       bucket;
+                       previous = bucket, bucket = nextBucket(&iter)
+               )
+       {
+               average_length += VecLenf(previous->p, bucket->p);
+       }
+       average_length /= (arc->bcount - 1);
+       
+       first_bucket = arc->buckets;
+       last_bucket = arc->buckets + (arc->bcount - 1);
+       
+       length = VecLenf(first_bucket->p, arc->head->p);
+       if (length > 2 * average_length)
+       {
+               padding_head = (int)floor(length / average_length);
+       }
 
-int compareArcsWeight(void *varc1, void *varc2)
-{
-       ReebArc *arc1 = (ReebArc*)varc1;
-       ReebArc *arc2 = (ReebArc*)varc2;
+       length = VecLenf(last_bucket->p, arc->tail->p);
+       if (length > 2 * average_length)
+       {
+               padding_tail = (int)floor(length / average_length);
+       }
        
-       if (arc1->v1->weight < arc2->v1->weight)
+       if (padding_head + padding_tail > 0)
        {
-               return -1;
+               EmbedBucket *old_buckets = arc->buckets;
+               
+               arc->buckets = MEM_callocN(sizeof(EmbedBucket) * (padding_head + arc->bcount + padding_tail), "embed bucket");
+               memcpy(arc->buckets + padding_head, old_buckets, arc->bcount * sizeof(EmbedBucket));
+               
+               arc->bcount = padding_head + arc->bcount + padding_tail;
+               
+               MEM_freeN(old_buckets);
        }
-       if (arc1->v1->weight > arc2->v1->weight)
+       
+       if (padding_head > 0)
        {
-               return 1;
+               interpolateBuckets(arc, arc->head->p, first_bucket->p, 0, padding_head);
        }
-       else
+       
+       if (padding_tail > 0)
        {
-               return 0;
+               interpolateBuckets(arc, last_bucket->p, arc->tail->p, arc->bcount - padding_tail, arc->bcount - 1);
        }
 }
 
-void sortArcs(ReebGraph *rg)
+/* CALL THIS ONLY AFTER FILTERING, SINCE IT MESSES UP WEIGHT DISTRIBUTION */
+void extendGraphBuckets(ReebGraph *rg)
 {
-       BLI_sortlist(&rg->arcs, compareArcsWeight);
+       ReebArc *arc;
+       
+       for (arc = rg->arcs.first; arc; arc = arc->next)
+       {
+               ExtendArcBuckets(arc);
+       }
 }
 
-/****************************************** FILTERING **************************************************/
+/**************************************** LENGTH CALCULATIONS ****************************************/
 
-int compareArcs(void *varc1, void *varc2)
+void calculateArcLength(ReebArc *arc)
 {
-       ReebArc *arc1 = (ReebArc*)varc1;
-       ReebArc *arc2 = (ReebArc*)varc2;
-       float len1 = arc1->v2->weight - arc1->v1->weight;
-       float len2 = arc2->v2->weight - arc2->v1->weight;
+       ReebArcIterator iter;
+       EmbedBucket *bucket = NULL;
+       float *vec0, *vec1;
+
+       arc->length = 0;
        
-       if (len1 < len2)
-       {
-               return -1;
-       }
-       if (len1 > len2)
-       {
-               return 1;
-       }
-       else
+       initArcIterator(&iter, arc, arc->head);
+
+       bucket = nextBucket(&iter);
+       
+       vec0 = arc->head->p;
+       vec1 = arc->head->p; /* in case there's no embedding */
+       
+       while (bucket != NULL)
        {
-               return 0;
+               vec1 = bucket->p;
+               
+               arc->length += VecLenf(vec0, vec1);
+               
+               vec0 = vec1;
+               bucket = nextBucket(&iter);
        }
+       
+       arc->length += VecLenf(arc->tail->p, vec1);     
 }
 
-void filterArc(ReebGraph *rg, ReebNode *newNode, ReebNode *removedNode, ReebArc * srcArc, int merging)
+void calculateGraphLength(ReebGraph *rg)
 {
-       ReebArc *arc = NULL, *nextArc = NULL;
-
-       /* first pass, merge buckets for arcs that spawned the two nodes into the source arc*/
-       for(arc = rg->arcs.first; arc; arc = arc->next)
+       ReebArc *arc;
+       
+       for (arc = rg->arcs.first; arc; arc = arc->next)
        {
-               if (arc->v1 == srcArc->v1 && arc->v2 == srcArc->v2 && arc != srcArc)
-               {
-                       mergeArcBuckets(srcArc, arc, srcArc->v1->weight, srcArc->v2->weight);
-               }
+               calculateArcLength(arc);
        }
+}
 
-       /* second pass, replace removedNode by newNode, remove arcs that are collapsed in a loop */
-       arc = rg->arcs.first;
-       while(arc)
+/**************************************** SYMMETRY HANDLING ******************************************/
+
+void REEB_RadialSymmetry(BNode* root_node, RadialArc* ring, int count)
+{
+       ReebNode *node = (ReebNode*)root_node;
+       float axis[3];
+       int i;
+       
+       VECCOPY(axis, root_node->symmetry_axis);
+       
+       /* first pass, merge incrementally */
+       for (i = 0; i < count - 1; i++)
        {
-               nextArc = arc->next;
+               ReebNode *node1, *node2;
+               ReebArc *arc1, *arc2;
+               float tangent[3];
+               float normal[3];
+               int j = i + 1;
+
+               VecAddf(tangent, ring[i].n, ring[j].n);
+               Crossf(normal, tangent, axis);
                
-               if (arc->v1 == removedNode || arc->v2 == removedNode)
+               node1 = (ReebNode*)BLI_otherNode(ring[i].arc, root_node);
+               node2 = (ReebNode*)BLI_otherNode(ring[j].arc, root_node);
+               
+               arc1 = (ReebArc*)ring[i].arc;
+               arc2 = (ReebArc*)ring[j].arc;
+
+               /* mirror first node and mix with the second */
+               BLI_mirrorAlongAxis(node1->p, root_node->p, normal);
+               VecLerpf(node2->p, node2->p, node1->p, 1.0f / (j + 1));
+               
+               /* Merge buckets
+                * there shouldn't be any null arcs here, but just to be safe 
+                * */
+               if (arc1->bcount > 0 && arc2->bcount > 0)
                {
-                       if (arc->v1 == removedNode)
-                       {
-                               arc->v1 = newNode;
-                       }
-                       else
+                       ReebArcIterator iter1, iter2;
+                       EmbedBucket *bucket1 = NULL, *bucket2 = NULL;
+                       
+                       initArcIterator(&iter1, arc1, (ReebNode*)root_node);
+                       initArcIterator(&iter2, arc2, (ReebNode*)root_node);
+                       
+                       bucket1 = nextBucket(&iter1);
+                       bucket2 = nextBucket(&iter2);
+               
+                       /* Make sure they both start at the same value */       
+                       while(bucket1 && bucket1->val < bucket2->val)
                        {
-                               arc->v2 = newNode;
+                               bucket1 = nextBucket(&iter1);
                        }
-
-                       // Remove looped arcs                   
-                       if (arc->v1 == arc->v2)
+                       
+                       while(bucket2 && bucket2->val < bucket1->val)
                        {
-                               // v1 or v2 was already newNode, since we're removing an arc, decrement degree
-                               newNode->degree--;
-                               
-                               // If it's safeArc, it'll be removed later, so keep it for now
-                               if (arc != srcArc)
-                               {
-                                       BLI_remlink(&rg->arcs, arc);
-                                       freeArc(arc);
-                               }
+                               bucket2 = nextBucket(&iter2);
                        }
-                       // Remove flipped arcs
-                       else if (arc->v1->weight > arc->v2->weight)
+       
+       
+                       for ( ;bucket1 && bucket2; bucket1 = nextBucket(&iter1), bucket2 = nextBucket(&iter2))
                        {
-                               // Decrement degree from the other node
-                               OTHER_NODE(arc, newNode)->degree--;
+                               bucket2->nv += bucket1->nv; /* add counts */
                                
-                               BLI_remlink(&rg->arcs, arc);
-                               freeArc(arc);
-                       }
-                       else
-                       {
-                               newNode->degree++; // incrementing degree since we're adding an arc
-
-                               if (merging)
-                               {
-                                       // resize bucket list
-                                       resizeArcBuckets(arc);
-                                       mergeArcBuckets(arc, srcArc, arc->v1->weight, arc->v2->weight);
-                               }
+                               /* mirror on axis */
+                               BLI_mirrorAlongAxis(bucket1->p, root_node->p, normal);
+                               /* add bucket2 in bucket1 */
+                               VecLerpf(bucket2->p, bucket2->p, bucket1->p, (float)bucket1->nv / (float)(bucket2->nv));
                        }
                }
-               
-               arc = nextArc;
        }
-}
-
-void filterNullReebGraph(ReebGraph *rg)
-{
-       ReebArc *arc = NULL, *nextArc = NULL;
        
-       arc = rg->arcs.first;
-       while(arc)
+       /* second pass, mirror back on previous arcs */
+       for (i = count - 1; i > 0; i--)
        {
-               nextArc = arc->next;
-               // Only collapse arcs too short to have any embed bucket
-               if (arc->bcount == 0)
-               {
-                       ReebNode *newNode = arc->v1;
-                       ReebNode *removedNode = arc->v2;
-                       float blend;
-                       
-                       blend = (float)newNode->degree / (float)(newNode->degree + removedNode->degree); // blending factors
-                       
-                       //newNode->weight = FloatLerpf(newNode->weight, removedNode->weight, blend);
-                       VecLerpf(newNode->p, newNode->p, removedNode->p, blend);
-                       
-                       filterArc(rg, newNode, removedNode, arc, 0);
+               ReebNode *node1, *node2;
+               ReebArc *arc1, *arc2;
+               float tangent[3];
+               float normal[3];
+               int j = i - 1;
 
-                       // Reset nextArc, it might have changed
-                       nextArc = arc->next;
-                       
-                       BLI_remlink(&rg->arcs, arc);
-                       freeArc(arc);
-                       
-                       BLI_freelinkN(&rg->nodes, removedNode);
-               }
+               VecAddf(tangent, ring[i].n, ring[j].n);
+               Crossf(normal, tangent, axis);
                
-               arc = nextArc;
-       }
-}
-
-int filterInternalReebGraph(ReebGraph *rg, float threshold)
-{
-       ReebArc *arc = NULL, *nextArc = NULL;
-       int value = 0;
-       
-       BLI_sortlist(&rg->arcs, compareArcs);
-
-       arc = rg->arcs.first;
-       while(arc)
-       {
-               nextArc = arc->next;
-
-               // Only collapse non-terminal arcs that are shorter than threshold
-               if ((arc->v1->degree > 1 && arc->v2->degree > 1 && arc->v2->weight - arc->v1->weight < threshold))
-               {
-                       ReebNode *newNode = NULL;
-                       ReebNode *removedNode = NULL;
-                       
-                       /* Keep the node with the highestn number of connected arcs */
-                       if (arc->v1->degree >= arc->v2->degree)
-                       {
-                               newNode = arc->v1;
-                               removedNode = arc->v2;
-                       }
-                       else
-                       {
-                               newNode = arc->v2;
-                               removedNode = arc->v1;
-                       }
-                       
-                       filterArc(rg, newNode, removedNode, arc, 1);
-
-                       // Reset nextArc, it might have changed
-                       nextArc = arc->next;
-                       
-                       BLI_remlink(&rg->arcs, arc);
-                       freeArc(arc);
-                       
-                       BLI_freelinkN(&rg->nodes, removedNode);
-                       value = 1;
-               }
+               node1 = (ReebNode*)BLI_otherNode(ring[i].arc, root_node);
+               node2 = (ReebNode*)BLI_otherNode(ring[j].arc, root_node);
                
-               arc = nextArc;
-       }
-       
-       return value;
-}
-
-int filterExternalReebGraph(ReebGraph *rg, float threshold)
-{
-       ReebArc *arc = NULL, *nextArc = NULL;
-       int value = 0;
-       
-       BLI_sortlist(&rg->arcs, compareArcs);
-
-       arc = rg->arcs.first;
-       while(arc)
-       {
-               nextArc = arc->next;
+               arc1 = (ReebArc*)ring[i].arc;
+               arc2 = (ReebArc*)ring[j].arc;
 
-               // Only collapse terminal arcs that are shorter than threshold
-               if ((arc->v1->degree == 1 || arc->v2->degree == 1) && arc->v2->weight - arc->v1->weight < threshold)
+               /* copy first node than mirror */
+               VECCOPY(node2->p, node1->p);
+               BLI_mirrorAlongAxis(node2->p, root_node->p, normal);
+               
+               /* Copy buckets
+                * there shouldn't be any null arcs here, but just to be safe 
+                * */
+               if (arc1->bcount > 0 && arc2->bcount > 0)
                {
-                       ReebNode *terminalNode = NULL;
-                       ReebNode *middleNode = NULL;
-                       ReebNode *newNode = NULL;
-                       ReebNode *removedNode = NULL;
-                       int merging = 0;
+                       ReebArcIterator iter1, iter2;
+                       EmbedBucket *bucket1 = NULL, *bucket2 = NULL;
                        
-                       // Assign terminal and middle nodes
-                       if (arc->v1->degree == 1)
-                       {
-                               terminalNode = arc->v1;
-                               middleNode = arc->v2;
-                       }
-                       else
-                       {
-                               terminalNode = arc->v2;
-                               middleNode = arc->v1;
-                       }
+                       initArcIterator(&iter1, arc1, node);
+                       initArcIterator(&iter2, arc2, node);
                        
-                       // If middle node is a normal node, merge to terminal node
-                       if (middleNode->degree == 2)
-                       {
-                               merging = 1;
-                               newNode = terminalNode;
-                               removedNode = middleNode;
-                       }
-                       // Otherwise, just plain remove of the arc
-                       else
+                       bucket1 = nextBucket(&iter1);
+                       bucket2 = nextBucket(&iter2);
+               
+                       /* Make sure they both start at the same value */       
+                       while(bucket1 && bucket1->val < bucket2->val)
                        {
-                               merging = 0;
-                               newNode = middleNode;
-                               removedNode = terminalNode;
+                               bucket1 = nextBucket(&iter1);
                        }
                        
-                       // Merging arc
-                       if (merging)
+                       while(bucket2 && bucket2->val < bucket1->val)
                        {
-                               filterArc(rg, newNode, removedNode, arc, 1);
+                               bucket2 = nextBucket(&iter2);
                        }
-                       else
+       
+       
+                       for ( ;bucket1 && bucket2; bucket1 = nextBucket(&iter1), bucket2 = nextBucket(&iter2))
                        {
-                               // removing arc, so we need to decrease the degree of the remaining node
-                               newNode->degree--;
+                               /* copy and mirror back to bucket2 */                   
+                               bucket2->nv = bucket1->nv;
+                               VECCOPY(bucket2->p, bucket1->p);
+                               BLI_mirrorAlongAxis(bucket2->p, node->p, normal);
                        }
-
-                       // Reset nextArc, it might have changed
-                       nextArc = arc->next;
-                       
-                       BLI_remlink(&rg->arcs, arc);
-                       freeArc(arc);
-                       
-                       BLI_freelinkN(&rg->nodes, removedNode);
-                       value = 1;
                }
-               
-               arc = nextArc;
        }
-       
-       return value;
 }
 
-/************************************** WEIGHT SPREADING ***********************************************/
-
-int compareVerts( const void* a, const void* b )
+void REEB_AxialSymmetry(BNode* root_node, BNode* node1, BNode* node2, struct BArc* barc1, BArc* barc2)
 {
-       EditVert *va = *(EditVert**)a;
-       EditVert *vb = *(EditVert**)b;
-       int value = 0;
-       
-       if (va->tmp.fp < vb->tmp.fp)
-       {
-               value = -1;
-       }
-       else if (va->tmp.fp > vb->tmp.fp)
-       {
-               value = 1;
-       }
+       ReebArc *arc1, *arc2;
+       float nor[3], p[3];
 
-       return value;           
-}
+       arc1 = (ReebArc*)barc1;
+       arc2 = (ReebArc*)barc2;
 
-void spreadWeight(EditMesh *em)
-{
-       EditVert **verts, *eve;
-       float lastWeight = 0.0f;
-       int totvert = BLI_countlist(&em->verts);
-       int i;
-       int work_needed = 1;
+       VECCOPY(nor, root_node->symmetry_axis);
        
-       verts = MEM_callocN(sizeof(EditVert*) * totvert, "verts array");
+       /* mirror node2 along axis */
+       VECCOPY(p, node2->p);
+       BLI_mirrorAlongAxis(p, root_node->p, nor);
+
+       /* average with node1 */
+       VecAddf(node1->p, node1->p, p);
+       VecMulf(node1->p, 0.5f);
        
-       for(eve = em->verts.first, i = 0; eve; eve = eve->next, i++)
-       {
-               verts[i] = eve;
-       }
+       /* mirror back on node2 */
+       VECCOPY(node2->p, node1->p);
+       BLI_mirrorAlongAxis(node2->p, root_node->p, nor);
        
-       while(work_needed == 1)
+       /* Merge buckets
+        * there shouldn't be any null arcs here, but just to be safe 
+        * */
+       if (arc1->bcount > 0 && arc2->bcount > 0)
        {
-               work_needed = 0;
-               qsort(verts, totvert, sizeof(EditVert*), compareVerts);
+               ReebArcIterator iter1, iter2;
+               EmbedBucket *bucket1 = NULL, *bucket2 = NULL;
                
-               for(i = 0; i < totvert; i++)
+               initArcIterator(&iter1, arc1, (ReebNode*)root_node);
+               initArcIterator(&iter2, arc2, (ReebNode*)root_node);
+               
+               bucket1 = nextBucket(&iter1);
+               bucket2 = nextBucket(&iter2);
+       
+               /* Make sure they both start at the same value */       
+               while(bucket1 && bucket1->val < bucket2->val)
                {
-                       eve = verts[i];
+                       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 */
                        
-                       if (i == 0 || (eve->tmp.fp - lastWeight) > FLT_EPSILON)
-                       {
-                               lastWeight = eve->tmp.fp;
-                       }
-                       else
-                       {
-                               work_needed = 1;
-                               eve->tmp.fp = lastWeight + FLT_EPSILON * 2;
-                               lastWeight = eve->tmp.fp;
-                       }
+                       /* mirror on axis */
+                       BLI_mirrorAlongAxis(bucket2->p, root_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);
+                       BLI_mirrorAlongAxis(bucket2->p, root_node->p, nor);
                }
        }
-       
-       MEM_freeN(verts);
 }
-/*********************************** GRAPH AS TREE FUNCTIONS *******************************************/
 
-int subtreeDepth(ReebNode *node, ReebArc *rootArc)
+/************************************** ADJACENCY LIST *************************************************/
+
+
+/****************************************** SMOOTHING **************************************************/
+
+void postprocessGraph(ReebGraph *rg, char mode)
 {
-       int depth = 0;
-       
-       /* Base case, no arcs leading away */
-       if (node->arcs == NULL || *(node->arcs) == NULL)
+       ReebArc *arc;
+       float fac1 = 0, fac2 = 1, fac3 = 0;
+
+       switch(mode)
        {
-               return 0;
+       case SKGEN_AVERAGE:
+               fac1 = fac2 = fac3 = 1.0f / 3.0f;
+               break;
+       case SKGEN_SMOOTH:
+               fac1 = fac3 = 0.25f;
+               fac2 = 0.5f;
+               break;
+       case SKGEN_SHARPEN:
+               fac1 = fac2 = -0.25f;
+               fac2 = 1.5f;
+               break;
+       default:
+               error("Unknown post processing mode");
+               return;
        }
-       else
+       
+       for(arc = rg->arcs.first; arc; arc = arc->next)
        {
-               ReebArc ** pArc;
+               EmbedBucket *buckets = arc->buckets;
+               int bcount = arc->bcount;
+               int index;
 
-               for(pArc = node->arcs; *pArc; pArc++)
+               for(index = 1; index < bcount - 1; index++)
                {
-                       ReebArc *arc = *pArc;
-                       
-                       /* only arcs that go down the tree */
-                       if (arc != rootArc)
-                       {
-                               ReebNode *newNode = OTHER_NODE(arc, node);
-                               depth = MAX2(depth, subtreeDepth(newNode, arc));
-                       }
+                       VecLerpf(buckets[index].p, buckets[index].p, buckets[index - 1].p, fac1 / (fac1 + fac2));
+                       VecLerpf(buckets[index].p, buckets[index].p, buckets[index + 1].p, fac3 / (fac1 + fac2 + fac3));
                }
        }
-       
-       return depth + 1;
 }
 
-/*************************************** CYCLE DETECTION ***********************************************/
+/********************************************SORTING****************************************************/
 
-int detectCycle(ReebNode *node, ReebArc *srcArc)
+int compareNodesWeight(void *vnode1, void *vnode2)
 {
-       int value = 0;
+       ReebNode *node1 = (ReebNode*)vnode1;
+       ReebNode *node2 = (ReebNode*)vnode2;
        
-       if (node->flags == 0)
+       if (node1->weight < node2->weight)
        {
-               ReebArc ** pArc;
-
-               /* mark node as visited */
-               node->flags = 1;
-
-               for(pArc = node->arcs; *pArc && value == 0; pArc++)
-               {
-                       ReebArc *arc = *pArc;
-                       
-                       /* don't go back on the source arc */
-                       if (arc != srcArc)
-                       {
-                               value = detectCycle(OTHER_NODE(arc, node), arc);
-                       }
-               }
+               return -1;
+       }
+       if (node1->weight > node2->weight)
+       {
+               return 1;
        }
        else
        {
-               value = 1;
+               return 0;
        }
-       
-       return value;
 }
 
-int    isGraphCyclic(ReebGraph *rg)
+void sortNodes(ReebGraph *rg)
 {
-       ReebNode *node;
-       int value = 0;
-       
-       /* NEED TO CHECK IF ADJACENCY LIST EXIST */
+       BLI_sortlist(&rg->nodes, compareNodesWeight);
+}
+
+int compareArcsWeight(void *varc1, void *varc2)
+{
+       ReebArc *arc1 = (ReebArc*)varc1;
+       ReebArc *arc2 = (ReebArc*)varc2;
+       ReebNode *node1 = (ReebNode*)arc1->head; 
+       ReebNode *node2 = (ReebNode*)arc2->head; 
        
-       /* Mark all nodes as not visited */
-       for(node = rg->nodes.first; node; node = node->next)
+       if (node1->weight < node2->weight)
        {
-               node->flags = 0;
+               return -1;
        }
-
-       /* detectCycles in subgraphs */ 
-       for(node = rg->nodes.first; node && value == 0; node = node->next)
+       if (node1->weight > node2->weight)
        {
-               /* only for nodes in subgraphs that haven't been visited yet */
-               if (node->flags == 0)
-               {
-                       value = value || detectCycle(node, NULL);
-               }               
+               return 1;
+       }
+       else
+       {
+               return 0;
        }
-       
-       return value;
 }
 
-/******************************************** EXPORT ***************************************************/
-
-void exportNode(FILE *f, char *text, ReebNode *node)
+void sortArcs(ReebGraph *rg)
 {
-       fprintf(f, "%s i:%i w:%f d:%i %f %f %f\n", text, node->index, node->weight, node->degree, node->p[0], node->p[1], node->p[2]);
+       BLI_sortlist(&rg->arcs, compareArcsWeight);
 }
+/******************************************* JOINING ***************************************************/
 
-void exportGraph(ReebGraph *rg, int count)
+void reweightArc(ReebArc *arc, ReebNode *start_node, float start_weight)
 {
-#ifdef DEBUG_REEB
-       ReebArc *arc;
-       char filename[128];
-       FILE *f;
+       ReebNode *node;
+       float old_weight;
+       float end_weight = start_weight + (arc->tail->weight - arc->head->weight);
+       int i;
        
-       if (count == -1)
+       if (arc->tail == start_node)
        {
-               sprintf(filename, "test.txt");
+               flipArc(arc);
        }
-       else
+       
+       node = arc->tail;
+       
+       for (i = 0; i < node->degree; i++)
        {
-               sprintf(filename, "test%05i.txt", count);
+               ReebArc *next_arc = node->arcs[i];
+               
+               if (next_arc != arc) /* prevent backtracking */
+               {
+                       reweightArc(next_arc, node, end_weight);
+               }
        }
-       f = fopen(filename, "w");
 
-       for(arc = rg->arcs.first; arc; arc = arc->next)
+       /* update only if needed */     
+       if (arc->head->weight != start_weight)
        {
-               int i;
+               old_weight = arc->head->weight; /* backup head weight, other arcs need it intact, it will be fixed by the source arc */
                
-               exportNode(f, "v1", arc->v1);
+               arc->head->weight = start_weight;
+               arc->tail->weight = end_weight;
                
-               for(i = 0; i < arc->bcount; i++)
-               {
-                       fprintf(f, "b nv:%i %f %f %f\n", arc->buckets[i].nv, arc->buckets[i].p[0], arc->buckets[i].p[1], arc->buckets[i].p[2]);
-               }
+               reweightBuckets(arc);
+               resizeArcBuckets(arc);
+               fillArcEmptyBuckets(arc);
                
-               exportNode(f, "v2", arc->v2);
-       }       
-       
-       fclose(f);
-#endif
-}
-
-/***************************************** MAIN ALGORITHM **********************************************/
+               arc->head->weight = old_weight;