f1ea39e45b9b5aef51c74a00f8cf89260a264f30
[blender.git] / source / blender / editors / armature / editarmature_retarget.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Martin Poirier
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  * autoarmature.c: Interface for automagically manipulating armature (retarget, created, ...)
22  */
23
24 /** \file blender/editors/armature/editarmature_retarget.c
25  *  \ingroup edarmature
26  */
27
28
29 #include <ctype.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <math.h> 
33 #include <float.h>
34
35 #include "MEM_guardedalloc.h"
36
37 #include "PIL_time.h"
38
39 #include "DNA_armature_types.h"
40 #include "DNA_constraint_types.h"
41 #include "DNA_scene_types.h"
42 #include "DNA_object_types.h"
43
44 #include "BLI_blenlib.h"
45 #include "BLI_math.h"
46 #include "BLI_utildefines.h"
47 #include "BLI_ghash.h"
48 #include "BLI_graph.h"
49 #include "BLI_rand.h"
50 #include "BLI_threads.h"
51
52 //#include "BDR_editobject.h"
53
54 #include "BKE_constraint.h"
55 #include "BKE_armature.h"
56 #include "BKE_context.h"
57
58 #include "ED_armature.h"
59 #include "ED_util.h"
60
61 #include "BIF_retarget.h"
62
63
64 //#include "mydevice.h"
65 #include "reeb.h" // FIX ME
66 //#include "blendef.h"
67
68 #include "armature_intern.h"
69
70 /************ RIG RETARGET DATA STRUCTURES ***************/
71
72 typedef struct MemoNode {
73         float   weight;
74         int     next;
75 } MemoNode;
76
77 typedef struct RetargetParam {
78         RigGraph        *rigg;
79         RigArc          *iarc;
80         RigNode         *inode_start;
81         bContext        *context;
82 } RetargetParam;
83
84 typedef enum 
85 {
86         RETARGET_LENGTH,
87         RETARGET_AGGRESSIVE
88 } RetargetMode; 
89
90 typedef enum
91 {
92         METHOD_BRUTE_FORCE = 0,
93         METHOD_MEMOIZE = 1
94 } RetargetMethod;
95
96 typedef enum
97 {
98         ARC_FREE = 0,
99         ARC_TAKEN = 1,
100         ARC_USED = 2
101 } ArcUsageFlags;
102
103 static RigGraph *GLOBAL_RIGG = NULL;
104
105 /*******************************************************************************************************/
106
107 void *exec_retargetArctoArc(void *param);
108
109 static void RIG_calculateEdgeAngles(RigEdge *edge_first, RigEdge *edge_second);
110 float rollBoneByQuat(EditBone *bone, float old_up_axis[3], float qrot[4]);
111
112 /* two levels */
113 #define SHAPE_LEVELS (SHAPE_RADIX * SHAPE_RADIX) 
114
115 /*********************************** EDITBONE UTILS ****************************************************/
116
117 static int countEditBoneChildren(ListBase *list, EditBone *parent)
118 {
119         EditBone *ebone;
120         int count = 0;
121         
122         for (ebone = list->first; ebone; ebone = ebone->next)
123         {
124                 if (ebone->parent == parent)
125                 {
126                         count++;
127                 }
128         }
129         
130         return count;
131 }
132
133 static EditBone* nextEditBoneChild(ListBase *list, EditBone *parent, int n)
134 {
135         EditBone *ebone;
136         
137         for (ebone = list->first; ebone; ebone = ebone->next)
138         {
139                 if (ebone->parent == parent)
140                 {
141                         if (n == 0)
142                         {
143                                 return ebone;
144                         }
145                         n--;
146                 }
147         }
148         
149         return NULL;
150 }
151
152 static void getEditBoneRollUpAxis(EditBone *bone, float roll, float up_axis[3])
153 {
154         float mat[3][3], nor[3];
155
156         sub_v3_v3v3(nor, bone->tail, bone->head);
157         
158         vec_roll_to_mat3(nor, roll, mat);
159         copy_v3_v3(up_axis, mat[2]);
160 }
161
162 static float rollBoneByQuatAligned(EditBone *bone, float old_up_axis[3], float qrot[4], float qroll[4], float aligned_axis[3])
163 {
164         float nor[3], new_up_axis[3], x_axis[3], z_axis[3];
165         
166         copy_v3_v3(new_up_axis, old_up_axis);
167         mul_qt_v3(qrot, new_up_axis);
168         
169         sub_v3_v3v3(nor, bone->tail, bone->head);
170         
171         cross_v3_v3v3(x_axis, nor, aligned_axis);
172         cross_v3_v3v3(z_axis, x_axis, nor);
173         
174         normalize_v3(new_up_axis);
175         normalize_v3(x_axis);
176         normalize_v3(z_axis);
177         
178         if (dot_v3v3(new_up_axis, x_axis) < 0)
179         {
180                 negate_v3(x_axis);
181         }
182         
183         if (dot_v3v3(new_up_axis, z_axis) < 0)
184         {
185                 negate_v3(z_axis);
186         }
187         
188         if (angle_normalized_v3v3(x_axis, new_up_axis) < angle_normalized_v3v3(z_axis, new_up_axis))
189         {
190                 rotation_between_vecs_to_quat(qroll, new_up_axis, x_axis); /* set roll rotation quat */
191                 return ED_rollBoneToVector(bone, x_axis, FALSE);
192         }
193         else
194         {
195                 rotation_between_vecs_to_quat(qroll, new_up_axis, z_axis); /* set roll rotation quat */
196                 return ED_rollBoneToVector(bone, z_axis, FALSE);
197         }
198 }
199
200 static float rollBoneByQuatJoint(RigEdge *edge, RigEdge *previous, float qrot[4], float qroll[4], float up_axis[3])
201 {
202         if (previous == NULL)
203         {
204                 /* default to up_axis if no previous */
205                 return rollBoneByQuatAligned(edge->bone, edge->up_axis, qrot, qroll, up_axis);
206         }
207         else
208         {
209                 float new_up_axis[3];
210                 float vec_first[3], vec_second[3], normal[3];
211                 
212                 if (previous->bone)
213                 {
214                         sub_v3_v3v3(vec_first, previous->bone->tail, previous->bone->head);
215                 } 
216                 else if (previous->prev->bone)
217                 {
218                         sub_v3_v3v3(vec_first, edge->bone->head, previous->prev->bone->tail);
219                 }
220                 else
221                 {
222                         /* default to up_axis if first bone in the chain is an offset */
223                         return rollBoneByQuatAligned(edge->bone, edge->up_axis, qrot, qroll, up_axis);
224                 }
225                 
226                 sub_v3_v3v3(vec_second, edge->bone->tail, edge->bone->head);
227         
228                 normalize_v3(vec_first);
229                 normalize_v3(vec_second);
230                 
231                 cross_v3_v3v3(normal, vec_first, vec_second);
232                 normalize_v3(normal);
233                 
234                 axis_angle_to_quat(qroll, vec_second, edge->up_angle);
235                 
236                 mul_qt_v3(qroll, normal);
237                         
238                 copy_v3_v3(new_up_axis, edge->up_axis);
239                 mul_qt_v3(qrot, new_up_axis);
240                 
241                 normalize_v3(new_up_axis);
242                 
243                 /* real qroll between normal and up_axis */
244                 rotation_between_vecs_to_quat(qroll, new_up_axis, normal);
245
246                 return ED_rollBoneToVector(edge->bone, normal, FALSE);
247         }
248 }
249
250 float rollBoneByQuat(EditBone *bone, float old_up_axis[3], float qrot[4])
251 {
252         float new_up_axis[3];
253         
254         copy_v3_v3(new_up_axis, old_up_axis);
255         mul_qt_v3(qrot, new_up_axis);
256         
257         return ED_rollBoneToVector(bone, new_up_axis, FALSE);
258 }
259
260 /************************************ DESTRUCTORS ******************************************************/
261
262 static void RIG_freeRigArc(BArc *arc)
263 {
264         BLI_freelistN(&((RigArc*)arc)->edges);
265 }
266
267 void RIG_freeRigGraph(BGraph *rg)
268 {
269         RigGraph *rigg = (RigGraph*)rg;
270         BNode *node;
271         BArc *arc;
272         
273 #ifdef USE_THREADS
274         BLI_destroy_worker(rigg->worker);
275 #endif
276         
277         if (rigg->link_mesh)
278         {
279                 REEB_freeGraph(rigg->link_mesh);
280         }
281         
282         for (arc = rg->arcs.first; arc; arc = arc->next)
283         {
284                 RIG_freeRigArc(arc);
285         }
286         BLI_freelistN(&rg->arcs);
287         
288         for (node = rg->nodes.first; node; node = node->next)
289         {
290                 BLI_freeNode(rg, (BNode*)node);
291         }
292         BLI_freelistN(&rg->nodes);
293         
294         BLI_freelistN(&rigg->controls);
295
296         BLI_ghash_free(rigg->bones_map, NULL, NULL);
297         BLI_ghash_free(rigg->controls_map, NULL, NULL);
298         
299         if (rigg->flag & RIG_FREE_BONELIST)
300         {
301                 BLI_freelistN(rigg->editbones);
302                 MEM_freeN(rigg->editbones);
303         }
304         
305         MEM_freeN(rg);
306 }
307
308 /************************************* ALLOCATORS ******************************************************/
309
310 static RigGraph *newRigGraph(void)
311 {
312         RigGraph *rg;
313         int totthread;
314         
315         rg = MEM_callocN(sizeof(RigGraph), "rig graph");
316         
317         rg->head = NULL;
318         
319         rg->bones_map = BLI_ghash_new(BLI_ghashutil_strhash, BLI_ghashutil_strcmp, "newRigGraph bones gh");
320         rg->controls_map = BLI_ghash_new(BLI_ghashutil_strhash, BLI_ghashutil_strcmp, "newRigGraph cont gh");
321         
322         rg->free_arc = RIG_freeRigArc;
323         rg->free_node = NULL;
324         
325 #ifdef USE_THREADS
326 //      if(G.scene->r.mode & R_FIXED_THREADS)
327 //      {
328 //              totthread = G.scene->r.threads;
329 //      }
330 //      else
331 //      {
332                 totthread = BLI_system_thread_count();
333 //      }
334         
335         rg->worker = BLI_create_worker(exec_retargetArctoArc, totthread, 20); /* fix number of threads */
336 #endif
337         
338         return rg;
339 }
340
341 static RigArc *newRigArc(RigGraph *rg)
342 {
343         RigArc *arc;
344         
345         arc = MEM_callocN(sizeof(RigArc), "rig arc");
346         arc->count = 0;
347         BLI_addtail(&rg->arcs, arc);
348         
349         return arc;
350 }
351
352 static RigControl *newRigControl(RigGraph *rg)
353 {
354         RigControl *ctrl;
355         
356         ctrl = MEM_callocN(sizeof(RigControl), "rig control");
357         
358         BLI_addtail(&rg->controls, ctrl);
359         
360         return ctrl;
361 }
362
363 static RigNode *newRigNodeHead(RigGraph *rg, RigArc *arc, float p[3])
364 {
365         RigNode *node;
366         node = MEM_callocN(sizeof(RigNode), "rig node");
367         BLI_addtail(&rg->nodes, node);
368
369         copy_v3_v3(node->p, p);
370         node->degree = 1;
371         node->arcs = NULL;
372         
373         arc->head = node;
374         
375         return node;
376 }
377
378 static void addRigNodeHead(RigGraph *UNUSED(rg), RigArc *arc, RigNode *node)
379 {
380         node->degree++;
381
382         arc->head = node;
383 }
384
385 static RigNode *newRigNode(RigGraph *rg, float p[3])
386 {
387         RigNode *node;
388         node = MEM_callocN(sizeof(RigNode), "rig node");
389         BLI_addtail(&rg->nodes, node);
390
391         copy_v3_v3(node->p, p);
392         node->degree = 0;
393         node->arcs = NULL;
394         
395         return node;
396 }
397
398 static RigNode *newRigNodeTail(RigGraph *rg, RigArc *arc, float p[3])
399 {
400         RigNode *node = newRigNode(rg, p);
401         
402         node->degree = 1;
403         arc->tail = node;
404
405         return node;
406 }
407
408 static void RIG_appendEdgeToArc(RigArc *arc, RigEdge *edge)
409 {
410         BLI_addtail(&arc->edges, edge);
411
412         if (edge->prev == NULL)
413         {
414                 copy_v3_v3(edge->head, arc->head->p);
415         }
416         else
417         {
418                 RigEdge *last_edge = edge->prev;
419                 copy_v3_v3(edge->head, last_edge->tail);
420                 RIG_calculateEdgeAngles(last_edge, edge);
421         }
422         
423         edge->length = len_v3v3(edge->head, edge->tail);
424         
425         arc->length += edge->length;
426         
427         arc->count += 1;
428 }
429
430 static void RIG_addEdgeToArc(RigArc *arc, float tail[3], EditBone *bone)
431 {
432         RigEdge *edge;
433
434         edge = MEM_callocN(sizeof(RigEdge), "rig edge");
435
436         copy_v3_v3(edge->tail, tail);
437         edge->bone = bone;
438         
439         if (bone)
440         {
441                 getEditBoneRollUpAxis(bone, bone->roll, edge->up_axis);
442         }
443         
444         RIG_appendEdgeToArc(arc, edge);
445 }
446 /************************************** CLONING TEMPLATES **********************************************/
447
448 static void renameTemplateBone(char *name, char *template_name, ListBase *editbones, char *side_string, char *num_string)
449 {
450         int i, j;
451         
452         for (i = 0, j = 0; i < (MAXBONENAME-1) && j < (MAXBONENAME-1) && template_name[i] != '\0'; i++)
453         {
454                 if (template_name[i] == '&')
455                 {
456                         if (template_name[i+1] == 'S' || template_name[i+1] == 's')
457                         {
458                                 j += sprintf(name + j, "%s", side_string);
459                                 i++;
460                         }
461                         else if (template_name[i+1] == 'N' || template_name[i+1] == 'n')
462                         {
463                                 j += sprintf(name + j, "%s", num_string);
464                                 i++;
465                         }
466                         else
467                         {
468                                 name[j] = template_name[i];
469                                 j++;
470                         }
471                 }
472                 else
473                 {
474                         name[j] = template_name[i];
475                         j++;
476                 }
477         }
478         
479         name[j] = '\0';
480         
481         unique_editbone_name(editbones, name, NULL);
482 }
483
484 static RigControl *cloneControl(RigGraph *rg, RigGraph *src_rg, RigControl *src_ctrl, GHash *ptr_hash, char *side_string, char *num_string)
485 {
486         RigControl *ctrl;
487         char name[MAXBONENAME];
488         
489         ctrl = newRigControl(rg);
490         
491         copy_v3_v3(ctrl->head, src_ctrl->head);
492         copy_v3_v3(ctrl->tail, src_ctrl->tail);
493         copy_v3_v3(ctrl->up_axis, src_ctrl->up_axis);
494         copy_v3_v3(ctrl->offset, src_ctrl->offset);
495         
496         ctrl->tail_mode = src_ctrl->tail_mode;
497         ctrl->flag = src_ctrl->flag;
498
499         renameTemplateBone(name, src_ctrl->bone->name, rg->editbones, side_string, num_string);
500         ctrl->bone = duplicateEditBoneObjects(src_ctrl->bone, name, rg->editbones, src_rg->ob, rg->ob);
501         ctrl->bone->flag &= ~(BONE_TIPSEL|BONE_SELECTED|BONE_ROOTSEL);
502         BLI_ghash_insert(ptr_hash, src_ctrl->bone, ctrl->bone);
503         
504         ctrl->link = src_ctrl->link;
505         ctrl->link_tail = src_ctrl->link_tail;
506         
507         return ctrl;
508 }
509
510 static RigArc *cloneArc(RigGraph *rg, RigGraph *src_rg, RigArc *src_arc, GHash *ptr_hash, char *side_string, char *num_string)
511 {
512         RigEdge *src_edge;
513         RigArc  *arc;
514         
515         arc = newRigArc(rg);
516         
517         arc->head = BLI_ghash_lookup(ptr_hash, src_arc->head);
518         arc->tail = BLI_ghash_lookup(ptr_hash, src_arc->tail);
519         
520         arc->head->degree++;
521         arc->tail->degree++;
522         
523         arc->length = src_arc->length;
524
525         arc->count = src_arc->count;
526         
527         for (src_edge = src_arc->edges.first; src_edge; src_edge = src_edge->next)
528         {
529                 RigEdge *edge;
530         
531                 edge = MEM_callocN(sizeof(RigEdge), "rig edge");
532
533                 copy_v3_v3(edge->head, src_edge->head);
534                 copy_v3_v3(edge->tail, src_edge->tail);
535                 copy_v3_v3(edge->up_axis, src_edge->up_axis);
536                 
537                 edge->length = src_edge->length;
538                 edge->angle = src_edge->angle;
539                 edge->up_angle = src_edge->up_angle;
540                 
541                 if (src_edge->bone != NULL)
542                 {
543                         char name[MAXBONENAME];
544                         renameTemplateBone(name, src_edge->bone->name, rg->editbones, side_string, num_string);
545                         edge->bone = duplicateEditBoneObjects(src_edge->bone, name, rg->editbones, src_rg->ob, rg->ob);
546                         edge->bone->flag &= ~(BONE_TIPSEL|BONE_SELECTED|BONE_ROOTSEL);
547                         BLI_ghash_insert(ptr_hash, src_edge->bone, edge->bone);
548                 }
549
550                 BLI_addtail(&arc->edges, edge);
551         }
552         
553         return arc;
554 }
555
556 static RigGraph *cloneRigGraph(RigGraph *src, ListBase *editbones, Object *ob, char *side_string, char *num_string)
557 {
558         GHash   *ptr_hash;      
559         RigNode *node;
560         RigArc  *arc;
561         RigControl *ctrl;
562         RigGraph *rg;
563         
564         ptr_hash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "cloneRigGraph gh");
565
566         rg = newRigGraph();
567         
568         rg->ob = ob;
569         rg->editbones = editbones;
570         
571         preEditBoneDuplicate(rg->editbones); /* prime bones for duplication */
572         preEditBoneDuplicate(src->editbones); /* prime bones for duplication */
573         
574         /* Clone nodes */
575         for (node = src->nodes.first; node; node = node->next)
576         {
577                 RigNode *cloned_node = newRigNode(rg, node->p);
578                 BLI_ghash_insert(ptr_hash, node, cloned_node);
579         }
580         
581         rg->head = BLI_ghash_lookup(ptr_hash, src->head);
582         
583         /* Clone arcs */
584         for (arc = src->arcs.first; arc; arc = arc->next)
585         {
586                 cloneArc(rg, src, arc, ptr_hash, side_string, num_string);
587         }
588         
589         /* Clone controls */
590         for (ctrl = src->controls.first; ctrl; ctrl = ctrl->next)
591         {
592                 cloneControl(rg, src, ctrl, ptr_hash, side_string, num_string);
593         }
594         
595         /* Relink bones properly */
596         for (arc = rg->arcs.first; arc; arc = arc->next)
597         {
598                 RigEdge *edge;
599                 
600                 for (edge = arc->edges.first; edge; edge = edge->next)
601                 {
602                         if (edge->bone != NULL)
603                         {
604                                 EditBone *bone;
605                                 
606                                 updateDuplicateSubtargetObjects(edge->bone, src->editbones, src->ob, rg->ob);
607
608                                 if (edge->bone->parent)
609                                 {                               
610                                         bone = BLI_ghash_lookup(ptr_hash, edge->bone->parent);
611                 
612                                         if (bone != NULL)
613                                         {
614                                                 edge->bone->parent = bone;
615                                         }
616                                         else
617                                         {
618                                                 /* disconnect since parent isn't cloned
619                                                  * this will only happen when cloning from selected bones 
620                                                  * */
621                                                 edge->bone->flag &= ~BONE_CONNECTED;
622                                         }
623                                 }
624                         }
625                 }
626         }
627         
628         for (ctrl = rg->controls.first; ctrl; ctrl = ctrl->next)
629         {
630                 EditBone *bone;
631                 
632                 updateDuplicateSubtargetObjects(ctrl->bone, src->editbones, src->ob, rg->ob);
633
634                 if (ctrl->bone->parent)
635                 {
636                         bone = BLI_ghash_lookup(ptr_hash, ctrl->bone->parent);
637                         
638                         if (bone != NULL)
639                         {
640                                 ctrl->bone->parent = bone;
641                         }
642                         else
643                         {
644                                 /* disconnect since parent isn't cloned
645                                  * this will only happen when cloning from selected bones 
646                                  * */
647                                 ctrl->bone->flag &= ~BONE_CONNECTED;
648                         }
649                 }
650
651                 ctrl->link = BLI_ghash_lookup(ptr_hash, ctrl->link);
652                 ctrl->link_tail = BLI_ghash_lookup(ptr_hash, ctrl->link_tail);
653         }
654         
655         BLI_ghash_free(ptr_hash, NULL, NULL);
656         
657         return rg;
658 }
659
660
661 /*******************************************************************************************************/
662
663 static void RIG_calculateEdgeAngles(RigEdge *edge_first, RigEdge *edge_second)
664 {
665         float vec_first[3], vec_second[3];
666         
667         sub_v3_v3v3(vec_first, edge_first->tail, edge_first->head); 
668         sub_v3_v3v3(vec_second, edge_second->tail, edge_second->head);
669
670         normalize_v3(vec_first);
671         normalize_v3(vec_second);
672         
673         edge_first->angle = angle_normalized_v3v3(vec_first, vec_second);
674         
675         if (edge_second->bone != NULL)
676         {
677                 float normal[3];
678
679                 cross_v3_v3v3(normal, vec_first, vec_second);
680                 normalize_v3(normal);
681
682                 edge_second->up_angle = angle_normalized_v3v3(normal, edge_second->up_axis);
683         }
684 }
685
686 /************************************ CONTROL BONES ****************************************************/
687
688 static void RIG_addControlBone(RigGraph *rg, EditBone *bone)
689 {
690         RigControl *ctrl = newRigControl(rg);
691         ctrl->bone = bone;
692         copy_v3_v3(ctrl->head, bone->head);
693         copy_v3_v3(ctrl->tail, bone->tail);
694         getEditBoneRollUpAxis(bone, bone->roll, ctrl->up_axis);
695         ctrl->tail_mode = TL_NONE;
696         
697         BLI_ghash_insert(rg->controls_map, bone->name, ctrl);
698 }
699
700 static int RIG_parentControl(RigControl *ctrl, EditBone *link)
701 {
702         if (link)
703         {
704                 float offset[3];
705                 int flag = 0;
706                 
707                 sub_v3_v3v3(offset, ctrl->bone->head, link->head);
708
709                 /* if root matches, check for direction too */          
710                 if (dot_v3v3(offset, offset) < 0.0001f)
711                 {
712                         float vbone[3], vparent[3];
713                         
714                         flag |= RIG_CTRL_FIT_ROOT;
715                         
716                         sub_v3_v3v3(vbone, ctrl->bone->tail, ctrl->bone->head);
717                         sub_v3_v3v3(vparent, link->tail, link->head);
718                         
719                         /* test for opposite direction */
720                         if (dot_v3v3(vbone, vparent) > 0)
721                         {
722                                 float nor[3];
723                                 float len;
724                                 
725                                 cross_v3_v3v3(nor, vbone, vparent);
726                                 
727                                 len = dot_v3v3(nor, nor);
728                                 if (len < 0.0001f)
729                                 {
730                                         flag |= RIG_CTRL_FIT_BONE;
731                                 }
732                         }
733                 }
734                 
735                 /* Bail out if old one is automatically better */
736                 if (flag < ctrl->flag)
737                 {
738                         return 0;
739                 }
740                 
741                 /* if there's already a link
742                  *      overwrite only if new link is higher in the chain */
743                 if (ctrl->link && flag == ctrl->flag)
744                 {
745                         EditBone *bone = NULL;
746                         
747                         for (bone = ctrl->link; bone; bone = bone->parent)
748                         {
749                                 /* if link is in the chain, break and use that one */
750                                 if (bone == link)
751                                 {
752                                         break;
753                                 }
754                         }
755                         
756                         /* not in chain, don't update link */
757                         if (bone == NULL)
758                         {
759                                 return 0;
760                         }
761                 }
762                 
763                 
764                 ctrl->link = link;
765                 ctrl->flag = flag;
766                 
767                 copy_v3_v3(ctrl->offset, offset);
768                 
769                 return 1;
770         }
771         
772         return 0;
773 }
774
775 static void RIG_reconnectControlBones(RigGraph *rg)
776 {
777         RigControl *ctrl;
778         int change = 1;
779         
780         /* first pass, link to deform bones */
781         for (ctrl = rg->controls.first; ctrl; ctrl = ctrl->next)
782         {
783                 bPoseChannel *pchan;
784                 bConstraint *con;
785                 int found = 0;
786                 
787                 /* DO SOME MAGIC HERE */
788                 for (pchan= rg->ob->pose->chanbase.first; pchan; pchan= pchan->next)
789                 {
790                         for (con= pchan->constraints.first; con; con= con->next) 
791                         {
792                                 bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
793                                 ListBase targets = {NULL, NULL};
794                                 bConstraintTarget *ct;
795                                 
796                                 /* constraint targets */
797                                 if (cti && cti->get_constraint_targets)
798                                 {
799                                         int target_index;
800                                         
801                                         cti->get_constraint_targets(con, &targets);
802                                         
803                                         for (target_index = 0, ct= targets.first; ct; target_index++, ct= ct->next)
804                                         {
805                                                 if ((ct->tar == rg->ob) && strcmp(ct->subtarget, ctrl->bone->name) == 0)
806                                                 {
807                                                         /* SET bone link to bone corresponding to pchan */
808                                                         EditBone *link = BLI_ghash_lookup(rg->bones_map, pchan->name);
809                                                         
810                                                         /* Making sure bone is in this armature */
811                                                         if (link != NULL)
812                                                         {
813                                                                 /* for pole targets, link to parent bone instead, if possible */
814                                                                 if (con->type == CONSTRAINT_TYPE_KINEMATIC && target_index == 1)
815                                                                 {
816                                                                         if (link->parent && BLI_ghash_haskey(rg->bones_map, link->parent->name))
817                                                                         {
818                                                                                 link = link->parent;
819                                                                         }
820                                                                 }
821                                                                 
822                                                                 found = RIG_parentControl(ctrl, link);
823                                                         }
824                                                 }
825                                         }
826                                         
827                                         if (cti->flush_constraint_targets)
828                                                 cti->flush_constraint_targets(con, &targets, 0);
829                                 }
830                         }
831                 }
832
833                 /* if not found yet, check parent */
834                 if (found == 0)
835                 {               
836                         if (ctrl->bone->parent)
837                         {
838                                 /* make sure parent is a deforming bone
839                                  * NULL if not
840                                  *  */
841                                 EditBone *link = BLI_ghash_lookup(rg->bones_map, ctrl->bone->parent->name);
842                                 
843                                 found = RIG_parentControl(ctrl, link);
844                         }
845                         
846                         /* check if bone is not superposed on another one */
847                         {
848                                 RigArc *arc;
849                                 RigArc *best_arc = NULL;
850                                 EditBone *link = NULL;
851                                 
852                                 for (arc = rg->arcs.first; arc; arc = arc->next)
853                                 {
854                                         RigEdge *edge;
855                                         for (edge = arc->edges.first; edge; edge = edge->next)
856                                         {
857                                                 if (edge->bone)
858                                                 {
859                                                         int fit = 0;
860                                                         
861                                                         fit = len_v3v3(ctrl->bone->head, edge->bone->head) < 0.0001f;
862                                                         fit = fit || len_v3v3(ctrl->bone->tail, edge->bone->tail) < 0.0001f;
863                                                         
864                                                         if (fit)
865                                                         {
866                                                                 /* pick the bone on the arc with the lowest symmetry level
867                                                                  * means you connect control to the trunk of the skeleton */
868                                                                 if (best_arc == NULL || arc->symmetry_level < best_arc->symmetry_level)
869                                                                 {
870                                                                         best_arc = arc;
871                                                                         link = edge->bone;
872                                                                 }
873                                                         }
874                                                 }
875                                         }
876                                 }
877                                 
878                                 found = RIG_parentControl(ctrl, link);
879                         }
880                 }
881                 
882                 /* if not found yet, check child */             
883                 if (found == 0)
884                 {
885                         RigArc *arc;
886                         RigArc *best_arc = NULL;
887                         EditBone *link = NULL;
888                         
889                         for (arc = rg->arcs.first; arc; arc = arc->next)
890                         {
891                                 RigEdge *edge;
892                                 for (edge = arc->edges.first; edge; edge = edge->next)
893                                 {
894                                         if (edge->bone && edge->bone->parent == ctrl->bone)
895                                         {
896                                                 /* pick the bone on the arc with the lowest symmetry level
897                                                  * means you connect control to the trunk of the skeleton */
898                                                 if (best_arc == NULL || arc->symmetry_level < best_arc->symmetry_level)
899                                                 {
900                                                         best_arc = arc;
901                                                         link = edge->bone;
902                                                 }
903                                         }
904                                 }
905                         }
906                         
907                         found = RIG_parentControl(ctrl, link);
908                 }
909
910         }
911         
912         
913         /* second pass, make chains in control bones */
914         while (change)
915         {
916                 change = 0;
917                 
918                 for (ctrl = rg->controls.first; ctrl; ctrl = ctrl->next)
919                 {
920                         /* if control is not linked yet */
921                         if (ctrl->link == NULL)
922                         {
923                                 bPoseChannel *pchan;
924                                 bConstraint *con;
925                                 RigControl *ctrl_parent = NULL;
926                                 RigControl *ctrl_child;
927                                 int found = 0;
928
929                                 if (ctrl->bone->parent)
930                                 {
931                                         ctrl_parent = BLI_ghash_lookup(rg->controls_map, ctrl->bone->parent->name);
932                                 }
933
934                                 /* check constraints first */
935                                 
936                                 /* DO SOME MAGIC HERE */
937                                 for (pchan= rg->ob->pose->chanbase.first; pchan; pchan= pchan->next)
938                                 {
939                                         for (con= pchan->constraints.first; con; con= con->next) 
940                                         {
941                                                 bConstraintTypeInfo *cti= constraint_get_typeinfo(con);
942                                                 ListBase targets = {NULL, NULL};
943                                                 bConstraintTarget *ct;
944                                                 
945                                                 /* constraint targets */
946                                                 if (cti && cti->get_constraint_targets)
947                                                 {
948                                                         cti->get_constraint_targets(con, &targets);
949                                                         
950                                                         for (ct= targets.first; ct; ct= ct->next)
951                                                         {
952                                                                 if ((ct->tar == rg->ob) && strcmp(ct->subtarget, ctrl->bone->name) == 0)
953                                                                 {
954                                                                         /* SET bone link to ctrl corresponding to pchan */
955                                                                         RigControl *link = BLI_ghash_lookup(rg->controls_map, pchan->name);
956
957                                                                         /* if owner is a control bone, link with it */                                                                  
958                                                                         if (link && link->link)
959                                                                         {
960                                                                                 RIG_parentControl(ctrl, link->bone);
961                                                                                 found = 1;
962                                                                                 break;
963                                                                         }
964                                                                 }
965                                                         }
966                                                         
967                                                         if (cti->flush_constraint_targets)
968                                                                 cti->flush_constraint_targets(con, &targets, 0);
969                                                 }
970                                         }
971                                 }                       
972
973                                 if (found == 0)
974                                 {
975                                         /* check if parent is already linked */
976                                         if (ctrl_parent && ctrl_parent->link)
977                                         {
978                                                 RIG_parentControl(ctrl, ctrl_parent->bone);
979                                                 change = 1;
980                                         }
981                                         else
982                                         {
983                                                 /* check childs */
984                                                 for (ctrl_child = rg->controls.first; ctrl_child; ctrl_child = ctrl_child->next)
985                                                 {
986                                                         /* if a child is linked, link to that one */
987                                                         if (ctrl_child->link && ctrl_child->bone->parent == ctrl->bone)
988                                                         {
989                                                                 RIG_parentControl(ctrl, ctrl_child->bone);
990                                                                 change = 1;
991                                                                 break;
992                                                         }
993                                                 }
994                                         }
995                                 }
996                         }
997                 }
998         }
999         
1000         /* third pass, link control tails */
1001         for (ctrl = rg->controls.first; ctrl; ctrl = ctrl->next)
1002         {
1003                 /* fit bone already means full match, so skip those */
1004                 if ((ctrl->flag & RIG_CTRL_FIT_BONE) == 0)
1005                 {
1006                         GHashIterator ghi;
1007                         
1008                         /* look on deform bones first */
1009                         BLI_ghashIterator_init(&ghi, rg->bones_map);
1010                         
1011                         for( ; !BLI_ghashIterator_isDone(&ghi); BLI_ghashIterator_step(&ghi))
1012                         {
1013                                 EditBone *bone = (EditBone*)BLI_ghashIterator_getValue(&ghi);
1014                                 
1015                                 /* don't link with parent */
1016                                 if (bone->parent != ctrl->bone)
1017                                 {
1018                                         if (len_v3v3(ctrl->bone->tail, bone->head) < 0.01f)
1019                                         {
1020                                                 ctrl->tail_mode = TL_HEAD;
1021                                                 ctrl->link_tail = bone;
1022                                                 break;
1023                                         }
1024                                         else if (len_v3v3(ctrl->bone->tail, bone->tail) < 0.01f)
1025                                         {
1026                                                 ctrl->tail_mode = TL_TAIL;
1027                                                 ctrl->link_tail = bone;
1028                                                 break;
1029                                         }
1030                                 }
1031                         }
1032                         
1033                         /* if we haven't found one yet, look in control bones */
1034                         if (ctrl->tail_mode == TL_NONE)
1035                         {
1036                         }
1037                 }
1038         }
1039         
1040 }
1041
1042 /*******************************************************************************************************/
1043
1044 static void RIG_joinArcs(RigGraph *rg, RigNode *node, RigArc *joined_arc1, RigArc *joined_arc2)
1045 {
1046         RigEdge *edge, *next_edge;
1047         
1048         /* ignore cases where joint is at start or end */
1049         if (joined_arc1->head == joined_arc2->head || joined_arc1->tail == joined_arc2->tail)
1050         {
1051                 return;
1052         }
1053         
1054         /* swap arcs to make sure arc1 is before arc2 */
1055         if (joined_arc1->head == joined_arc2->tail)
1056         {
1057                 RigArc *tmp = joined_arc1;
1058                 joined_arc1 = joined_arc2;
1059                 joined_arc2 = tmp;
1060         }
1061         
1062         for (edge = joined_arc2->edges.first; edge; edge = next_edge)
1063         {
1064                 next_edge = edge->next;
1065                 
1066                 RIG_appendEdgeToArc(joined_arc1, edge);
1067         }
1068         
1069         joined_arc1->tail = joined_arc2->tail;
1070         
1071         joined_arc2->edges.first = joined_arc2->edges.last = NULL;
1072         
1073         BLI_removeArc((BGraph*)rg, (BArc*)joined_arc2);
1074         
1075         BLI_removeNode((BGraph*)rg, (BNode*)node);
1076 }
1077
1078 static void RIG_removeNormalNodes(RigGraph *rg)
1079 {
1080         RigNode *node, *next_node;
1081         
1082         for (node = rg->nodes.first; node; node = next_node)
1083         {
1084                 next_node = node->next;
1085                 
1086                 if (node->degree == 2)
1087                 {
1088                         RigArc *arc, *joined_arc1 = NULL, *joined_arc2 = NULL;
1089                         
1090                         for (arc = rg->arcs.first; arc; arc = arc->next)
1091                         {
1092                                 if (arc->head == node || arc->tail == node)
1093                                 {
1094                                         if (joined_arc1 == NULL)
1095                                         {
1096                                                 joined_arc1 = arc;
1097                                         }
1098                                         else
1099                                         {
1100                                                 joined_arc2 = arc;
1101                                                 break;
1102                                         }
1103                                 }
1104                         }
1105                         
1106                         RIG_joinArcs(rg, node, joined_arc1, joined_arc2);
1107                 }
1108         }
1109 }
1110
1111 static void RIG_removeUneededOffsets(RigGraph *rg)
1112 {
1113         RigArc *arc;
1114         
1115         for (arc = rg->arcs.first; arc; arc = arc->next)
1116         {
1117                 RigEdge *first_edge, *last_edge;
1118                 
1119                 first_edge = arc->edges.first;
1120                 last_edge = arc->edges.last;
1121                 
1122                 if (first_edge->bone == NULL)
1123                 {
1124                         if (first_edge->bone == NULL && len_v3v3(first_edge->tail, arc->head->p) <= 0.001f)
1125                         {
1126                                 BLI_remlink(&arc->edges, first_edge);
1127                                 MEM_freeN(first_edge);
1128                         }
1129                         else if (arc->head->degree == 1)
1130                         {
1131                                 RigNode *new_node = (RigNode*)BLI_FindNodeByPosition((BGraph*)rg, first_edge->tail, 0.001f);
1132                                 
1133                                 if (new_node)
1134                                 {
1135                                         BLI_remlink(&arc->edges, first_edge);
1136                                         MEM_freeN(first_edge);
1137                                         BLI_replaceNodeInArc((BGraph*)rg, (BArc*)arc, (BNode*)new_node, (BNode*)arc->head);
1138                                 }
1139                                 else
1140                                 {
1141                                         RigEdge *next_edge = first_edge->next;
1142         
1143                                         if (next_edge)
1144                                         {
1145                                                 BLI_remlink(&arc->edges, first_edge);
1146                                                 MEM_freeN(first_edge);
1147                                                 
1148                                                 copy_v3_v3(arc->head->p, next_edge->head);
1149                                         }
1150                                 }
1151                         }
1152                         else
1153                         {
1154                                 /* check if all arc connected start with a null edge */
1155                                 RigArc *other_arc;
1156                                 for (other_arc = rg->arcs.first; other_arc; other_arc = other_arc->next)
1157                                 {
1158                                         if (other_arc != arc)
1159                                         {
1160                                                 RigEdge *test_edge;
1161                                                 if (other_arc->head == arc->head)
1162                                                 {
1163                                                         test_edge = other_arc->edges.first;
1164                                                         
1165                                                         if (test_edge->bone != NULL)
1166                                                         {
1167                                                                 break;
1168                                                         }
1169                                                 }
1170                                                 else if (other_arc->tail == arc->head)
1171                                                 {
1172                                                         test_edge = other_arc->edges.last;
1173                                                         
1174                                                         if (test_edge->bone != NULL)
1175                                                         {
1176                                                                 break;
1177                                                         }
1178                                                 }
1179                                         }
1180                                 }
1181                                 
1182                                 if (other_arc == NULL)
1183                                 {
1184                                         RigNode *new_node = (RigNode*)BLI_FindNodeByPosition((BGraph*)rg, first_edge->tail, 0.001);
1185                                         
1186                                         if (new_node)
1187                                         {
1188                                                 /* remove null edge in other arcs too */
1189                                                 for (other_arc = rg->arcs.first; other_arc; other_arc = other_arc->next)
1190                                                 {
1191                                                         if (other_arc != arc)
1192                                                         {
1193                                                                 RigEdge *test_edge;
1194                                                                 if (other_arc->head == arc->head)
1195                                                                 {
1196                                                                         BLI_replaceNodeInArc((BGraph*)rg, (BArc*)other_arc, (BNode*)new_node, (BNode*)other_arc->head);
1197                                                                         test_edge = other_arc->edges.first;
1198                                                                         BLI_remlink(&other_arc->edges, test_edge);
1199                                                                         MEM_freeN(test_edge);
1200                                                                 }
1201                                                                 else if (other_arc->tail == arc->head)
1202                                                                 {
1203                                                                         BLI_replaceNodeInArc((BGraph*)rg, (BArc*)other_arc, (BNode*)new_node, (BNode*)other_arc->tail);
1204                                                                         test_edge = other_arc->edges.last;
1205                                                                         BLI_remlink(&other_arc->edges, test_edge);
1206                                                                         MEM_freeN(test_edge);
1207                                                                 }
1208                                                         }
1209                                                 }
1210                                                 
1211                                                 BLI_remlink(&arc->edges, first_edge);
1212                                                 MEM_freeN(first_edge);
1213                                                 BLI_replaceNodeInArc((BGraph*)rg, (BArc*)arc, (BNode*)new_node, (BNode*)arc->head);
1214                                         }
1215                                         else
1216                                         {
1217                                                 RigEdge *next_edge = first_edge->next;
1218                 
1219                                                 if (next_edge)
1220                                                 {
1221                                                         BLI_remlink(&arc->edges, first_edge);
1222                                                         MEM_freeN(first_edge);
1223                                                         
1224                                                         copy_v3_v3(arc->head->p, next_edge->head);
1225                                                         
1226                                                         /* remove null edge in other arcs too */
1227                                                         for (other_arc = rg->arcs.first; other_arc; other_arc = other_arc->next)
1228                                                         {
1229                                                                 if (other_arc != arc)
1230                                                                 {
1231                                                                         RigEdge *test_edge;
1232                                                                         if (other_arc->head == arc->head)
1233                                                                         {
1234                                                                                 test_edge = other_arc->edges.first;
1235                                                                                 BLI_remlink(&other_arc->edges, test_edge);
1236                                                                                 MEM_freeN(test_edge);
1237                                                                         }
1238                                                                         else if (other_arc->tail == arc->head)
1239                                                                         {
1240                                                                                 test_edge = other_arc->edges.last;
1241                                                                                 BLI_remlink(&other_arc->edges, test_edge);
1242                                                                                 MEM_freeN(test_edge);
1243                                                                         }
1244                                                                 }
1245                                                         }
1246                                                 }
1247                                         }
1248                                 }
1249                         }
1250                 }
1251                 
1252                 if (last_edge->bone == NULL)
1253                 {
1254                         if (len_v3v3(last_edge->head, arc->tail->p) <= 0.001f)
1255                         {
1256                                 BLI_remlink(&arc->edges, last_edge);
1257                                 MEM_freeN(last_edge);
1258                         }
1259                         else if (arc->tail->degree == 1)
1260                         {
1261                                 RigNode *new_node = (RigNode*)BLI_FindNodeByPosition((BGraph*)rg, last_edge->head, 0.001f);
1262                                 
1263                                 if (new_node)
1264                                 {
1265                                         RigEdge *previous_edge = last_edge->prev;
1266                                         
1267                                         BLI_remlink(&arc->edges, last_edge);
1268                                         MEM_freeN(last_edge);
1269                                         BLI_replaceNodeInArc((BGraph*)rg, (BArc*)arc, (BNode*)new_node, (BNode*)arc->tail);
1270                                         
1271                                         /* set previous angle to 0, since there's no following edges */
1272                                         if (previous_edge)
1273                                         {
1274                                                 previous_edge->angle = 0;
1275                                         }
1276                                 }
1277                                 else
1278                                 {
1279                                         RigEdge *previous_edge = last_edge->prev;
1280         
1281                                         if (previous_edge)
1282                                         {
1283                                                 BLI_remlink(&arc->edges, last_edge);
1284                                                 MEM_freeN(last_edge);
1285                                                 
1286                                                 copy_v3_v3(arc->tail->p, previous_edge->tail);
1287                                                 previous_edge->angle = 0;
1288                                         }
1289                                 }
1290                         }
1291                 }
1292         }
1293 }
1294
1295 static void RIG_arcFromBoneChain(RigGraph *rg, ListBase *list, EditBone *root_bone, RigNode *starting_node, int selected)
1296 {
1297         EditBone *bone, *last_bone = root_bone;
1298         RigArc *arc = NULL;
1299         int contain_head = 0;
1300         
1301         for(bone = root_bone; bone; bone = nextEditBoneChild(list, bone, 0))
1302         {
1303                 int nb_children;
1304                 
1305                 if (selected == 0 || (bone->flag & BONE_SELECTED))
1306                 { 
1307                         if ((bone->flag & BONE_NO_DEFORM) == 0)
1308                         {
1309                                 BLI_ghash_insert(rg->bones_map, bone->name, bone);
1310                         
1311                                 if (arc == NULL)
1312                                 {
1313                                         arc = newRigArc(rg);
1314                                         
1315                                         if (starting_node == NULL)
1316                                         {
1317                                                 starting_node = newRigNodeHead(rg, arc, root_bone->head);
1318                                         }
1319                                         else
1320                                         {
1321                                                 addRigNodeHead(rg, arc, starting_node);
1322                                         }
1323                                 }
1324                                 
1325                                 if (bone->parent && (bone->flag & BONE_CONNECTED) == 0)
1326                                 {
1327                                         RIG_addEdgeToArc(arc, bone->head, NULL);
1328                                 }
1329                                 
1330                                 RIG_addEdgeToArc(arc, bone->tail, bone);
1331                                 
1332                                 last_bone = bone;
1333                                 
1334                                 if (strcmp(bone->name, "head") == 0)
1335                                 {
1336                                         contain_head = 1;
1337                                 }
1338                         }
1339                         else if ((bone->flag & BONE_EDITMODE_LOCKED) == 0) /* ignore locked bones */
1340                         {
1341                                 RIG_addControlBone(rg, bone);
1342                         }
1343                 }
1344                 
1345                 nb_children = countEditBoneChildren(list, bone);
1346                 if (nb_children > 1)
1347                 {
1348                         RigNode *end_node = NULL;
1349                         int i;
1350                         
1351                         if (arc != NULL)
1352                         {
1353                                 end_node = newRigNodeTail(rg, arc, bone->tail);
1354                         }
1355                         else
1356                         {
1357                                 end_node = newRigNode(rg, bone->tail);
1358                         }
1359
1360                         for (i = 0; i < nb_children; i++)
1361                         {
1362                                 root_bone = nextEditBoneChild(list, bone, i);
1363                                 RIG_arcFromBoneChain(rg, list, root_bone, end_node, selected);
1364                         }
1365                         
1366                         /* arc ends here, break */
1367                         break;
1368                 }
1369         }
1370         
1371         /* If the loop exited without forking */
1372         if (arc != NULL && bone == NULL)
1373         {
1374                 newRigNodeTail(rg, arc, last_bone->tail);
1375         }
1376
1377         if (contain_head)
1378         {
1379                 rg->head = arc->tail;
1380         }
1381 }
1382
1383 /*******************************************************************************************************/
1384 static void RIG_findHead(RigGraph *rg)
1385 {
1386         if (rg->head == NULL)
1387         {
1388                 if (BLI_countlist(&rg->arcs) == 1)
1389                 {
1390                         RigArc *arc = rg->arcs.first;
1391                         
1392                         rg->head = (RigNode*)arc->head;
1393                 }
1394                 else
1395                 {
1396                         RigArc *arc;
1397                         
1398                         for (arc = rg->arcs.first; arc; arc = arc->next)
1399                         {
1400                                 RigEdge *edge = arc->edges.last;
1401                                 
1402                                 if (edge->bone->flag & (BONE_TIPSEL|BONE_SELECTED))
1403                                 {
1404                                         rg->head = arc->tail;
1405                                         break;
1406                                 }
1407                         }
1408                 }
1409                 
1410                 if (rg->head == NULL)
1411                 {
1412                         rg->head = rg->nodes.first;
1413                 }
1414         }
1415 }
1416
1417 /*******************************************************************************************************/
1418
1419 static void RIG_printNode(RigNode *node, const char name[])
1420 {
1421         printf("%s %p %i <%0.3f, %0.3f, %0.3f>\n", name, (void *)node, node->degree, node->p[0], node->p[1], node->p[2]);
1422         
1423         if (node->symmetry_flag & SYM_TOPOLOGICAL)
1424         {
1425                 if (node->symmetry_flag & SYM_AXIAL)
1426                         printf("Symmetry AXIAL\n");
1427                 else if (node->symmetry_flag & SYM_RADIAL)
1428                         printf("Symmetry RADIAL\n");
1429                         
1430                 print_v3("symmetry axis", node->symmetry_axis);
1431         }
1432 }
1433
1434 void RIG_printArcBones(RigArc *arc)
1435 {
1436         RigEdge *edge;
1437
1438         for (edge = arc->edges.first; edge; edge = edge->next)
1439         {
1440                 if (edge->bone)
1441                         printf("%s ", edge->bone->name);
1442                 else
1443                         printf("---- ");
1444         }
1445         printf("\n");
1446 }
1447
1448 static void RIG_printCtrl(RigControl *ctrl, char *indent)
1449 {
1450         char text[128];
1451         
1452         printf("%sBone: %s\n", indent, ctrl->bone->name);
1453         printf("%sLink: %s\n", indent, ctrl->link ? ctrl->link->name : "!NONE!");
1454         
1455         BLI_snprintf(text, sizeof(text), "%soffset", indent);
1456         print_v3(text, ctrl->offset);
1457         
1458         printf("%sFlag: %i\n", indent, ctrl->flag);
1459 }
1460
1461 static void RIG_printLinkedCtrl(RigGraph *rg, EditBone *bone, int tabs)
1462 {
1463         RigControl *ctrl;
1464         char indent[64];
1465         char *s = indent;
1466         int i;
1467         
1468         for (i = 0; i < tabs; i++)
1469         {
1470                 s[0] = '\t';
1471                 s++;
1472         }
1473         s[0] = 0;
1474         
1475         for (ctrl = rg->controls.first; ctrl; ctrl = ctrl->next)
1476         {
1477                 if (ctrl->link == bone)
1478                 {
1479                         RIG_printCtrl(ctrl, indent);
1480                         RIG_printLinkedCtrl(rg, ctrl->bone, tabs + 1);
1481                 }
1482         }
1483 }
1484
1485 void RIG_printArc(RigGraph *rg, RigArc *arc)
1486 {
1487         RigEdge *edge;
1488
1489         RIG_printNode((RigNode*)arc->head, "head");
1490
1491         for (edge = arc->edges.first; edge; edge = edge->next)
1492         {
1493                 printf("\tinner joints %0.3f %0.3f %0.3f\n", edge->tail[0], edge->tail[1], edge->tail[2]);
1494                 printf("\t\tlength %f\n", edge->length);
1495                 printf("\t\tangle %f\n", edge->angle * 180 / M_PI);
1496                 if (edge->bone)
1497                 {
1498                         printf("\t\t%s\n", edge->bone->name);
1499                         RIG_printLinkedCtrl(rg, edge->bone, 3);
1500                 }
1501         }       
1502         printf("symmetry level: %i flag: %i group %i\n", arc->symmetry_level, arc->symmetry_flag, arc->symmetry_group);
1503
1504         RIG_printNode((RigNode*)arc->tail, "tail");
1505 }
1506
1507 void RIG_printGraph(RigGraph *rg)
1508 {
1509         RigArc *arc;
1510
1511         printf("---- ARCS ----\n");
1512         for (arc = rg->arcs.first; arc; arc = arc->next)
1513         {
1514                 RIG_printArc(rg, arc);  
1515                 printf("\n");
1516         }
1517
1518         if (rg->head)
1519         {
1520                 RIG_printNode(rg->head, "HEAD NODE:");
1521         }
1522         else
1523         {
1524                 printf("HEAD NODE: NONE\n");
1525         }       
1526 }
1527
1528 /*******************************************************************************************************/
1529
1530 RigGraph *RIG_graphFromArmature(const bContext *C, Object *ob, bArmature *arm)
1531 {
1532         Object *obedit = CTX_data_edit_object(C);
1533         Scene *scene = CTX_data_scene(C);
1534         EditBone *ebone;
1535         RigGraph *rg;
1536
1537         rg = newRigGraph();
1538         
1539         if (obedit == ob)
1540         {
1541                 rg->editbones = ((bArmature *)obedit->data)->edbo;
1542         }
1543         else
1544         {
1545                 rg->editbones = MEM_callocN(sizeof(ListBase), "EditBones");
1546                 make_boneList(rg->editbones, &arm->bonebase, NULL, NULL);
1547                 rg->flag |= RIG_FREE_BONELIST;
1548         }
1549         
1550         rg->ob = ob;
1551
1552         /* Do the rotations */
1553         for (ebone = rg->editbones->first; ebone; ebone=ebone->next){
1554                 if (ebone->parent == NULL)
1555                 {
1556                         RIG_arcFromBoneChain(rg, rg->editbones, ebone, NULL, 0);
1557                 }
1558         }
1559         
1560         BLI_removeDoubleNodes((BGraph*)rg, 0.001);
1561         
1562         RIG_removeNormalNodes(rg);
1563         
1564         RIG_removeUneededOffsets(rg);
1565         
1566         BLI_buildAdjacencyList((BGraph*)rg);
1567         
1568         RIG_findHead(rg);
1569
1570         BLI_markdownSymmetry((BGraph*)rg, (BNode*)rg->head, scene->toolsettings->skgen_symmetry_limit);
1571         
1572         RIG_reconnectControlBones(rg); /* after symmetry, because we use levels to find best match */
1573         
1574         if (BLI_isGraphCyclic((BGraph*)rg))
1575         {
1576                 printf("armature cyclic\n");
1577         }
1578         
1579         return rg;
1580 }
1581
1582 static RigGraph *armatureSelectedToGraph(bContext *C, Object *ob, bArmature *arm)
1583 {
1584         Object *obedit = CTX_data_edit_object(C);
1585         Scene *scene = CTX_data_scene(C);
1586         EditBone *ebone;
1587         RigGraph *rg;
1588
1589         rg = newRigGraph();
1590         
1591         if (obedit == ob)
1592         {
1593                 rg->editbones = arm->edbo;
1594         }
1595         else
1596         {
1597                 rg->editbones = MEM_callocN(sizeof(ListBase), "EditBones");
1598                 make_boneList(rg->editbones, &arm->bonebase, NULL, NULL);
1599                 rg->flag |= RIG_FREE_BONELIST;
1600         }
1601
1602         rg->ob = ob;
1603
1604         /* Do the rotations */
1605         for (ebone = rg->editbones->first; ebone; ebone=ebone->next){
1606                 if (ebone->parent == NULL)
1607                 {
1608                         RIG_arcFromBoneChain(rg, rg->editbones, ebone, NULL, 1);
1609                 }
1610         }
1611         
1612         BLI_removeDoubleNodes((BGraph*)rg, 0.001);
1613         
1614         RIG_removeNormalNodes(rg);
1615         
1616         RIG_removeUneededOffsets(rg);
1617         
1618         BLI_buildAdjacencyList((BGraph*)rg);
1619         
1620         RIG_findHead(rg);
1621
1622         BLI_markdownSymmetry((BGraph*)rg, (BNode*)rg->head, scene->toolsettings->skgen_symmetry_limit);
1623         
1624         RIG_reconnectControlBones(rg); /* after symmetry, because we use levels to find best match */
1625         
1626         if (BLI_isGraphCyclic((BGraph*)rg))
1627         {
1628                 printf("armature cyclic\n");
1629         }
1630         
1631         return rg;
1632 }
1633 /************************************ GENERATING *****************************************************/
1634
1635 #if 0
1636 static EditBone *add_editbonetolist(char *name, ListBase *list)
1637 {
1638         EditBone *bone= MEM_callocN(sizeof(EditBone), "eBone");
1639         
1640         BLI_strncpy(bone->name, name, sizeof(bone->name));
1641         unique_editbone_name(list, bone->name, NULL);
1642         
1643         BLI_addtail(list, bone);
1644         
1645         bone->flag |= BONE_TIPSEL;
1646         bone->weight= 1.0F;
1647         bone->dist= 0.25F;
1648         bone->xwidth= 0.1;
1649         bone->zwidth= 0.1;
1650         bone->ease1= 1.0;
1651         bone->ease2= 1.0;
1652         bone->rad_head= 0.10;
1653         bone->rad_tail= 0.05;
1654         bone->segments= 1;
1655         bone->layer=  1;//arm->layer;
1656         
1657         return bone;
1658 }
1659 #endif
1660
1661 #if 0 /* UNUSED */
1662 static void generateMissingArcsFromNode(RigGraph *rigg, ReebNode *node, int multi_level_limit)
1663 {
1664         while (node->multi_level > multi_level_limit && node->link_up)
1665         {
1666                 node = node->link_up;
1667         }
1668         
1669         while (node->multi_level < multi_level_limit && node->link_down)
1670         {
1671                 node = node->link_down;
1672         }
1673         
1674         if (node->multi_level == multi_level_limit)
1675         {
1676                 int i;
1677                 
1678                 for (i = 0; i < node->degree; i++)
1679                 {
1680                         ReebArc *earc = node->arcs[i];
1681                         
1682                         if (earc->flag == ARC_FREE && earc->head == node)
1683                         {
1684                                 ReebNode *other = BIF_otherNodeFromIndex(earc, node);
1685                                 
1686                                 earc->flag = ARC_USED;
1687                                 
1688                                 //generateBonesForArc(rigg, earc, node, other);
1689                                 generateMissingArcsFromNode(rigg, other, multi_level_limit);
1690                         }
1691                 }
1692         }
1693 }
1694
1695 static void generateMissingArcs(RigGraph *rigg)
1696 {
1697         ReebGraph *reebg;
1698         int multi_level_limit = 5;
1699         
1700         for (reebg = rigg->link_mesh; reebg; reebg = reebg->link_up)
1701         {
1702                 ReebArc *earc;
1703                 
1704                 for (earc = reebg->arcs.first; earc; earc = earc->next)
1705                 {
1706                         if (earc->flag == ARC_USED)
1707                         {
1708                                 generateMissingArcsFromNode(rigg, earc->head, multi_level_limit);
1709                                 generateMissingArcsFromNode(rigg, earc->tail, multi_level_limit);
1710                         }
1711                 }
1712         }
1713 }
1714 #endif
1715
1716 /************************************ RETARGETTING *****************************************************/
1717
1718 static void repositionControl(RigGraph *rigg, RigControl *ctrl, float head[3], float tail[3], float qrot[4], float resize);
1719
1720 static void repositionTailControl(RigGraph *rigg, RigControl *ctrl);
1721
1722 static void finalizeControl(RigGraph *rigg, RigControl *ctrl, float resize)
1723 {
1724         if ((ctrl->flag & RIG_CTRL_DONE) == RIG_CTRL_DONE)
1725         {
1726                 RigControl *ctrl_child;
1727
1728 #if 0           
1729                 printf("CTRL: %s LINK: %s", ctrl->bone->name, ctrl->link->name);
1730                 
1731                 if (ctrl->link_tail)
1732                 {
1733                         printf(" TAIL: %s", ctrl->link_tail->name);
1734                 }
1735                 
1736                 printf("\n");
1737 #endif
1738                 
1739                 /* if there was a tail link: apply link, recalc resize factor and qrot */
1740                 if (ctrl->tail_mode != TL_NONE)
1741                 {
1742                         float *tail_vec = NULL;
1743                         float v1[3], v2[3], qtail[4];
1744                         
1745                         if (ctrl->tail_mode == TL_TAIL)
1746                         {
1747                                 tail_vec = ctrl->link_tail->tail;
1748                         }
1749                         else if (ctrl->tail_mode == TL_HEAD)
1750                         {
1751                                 tail_vec = ctrl->link_tail->head;
1752                         }
1753                         
1754                         sub_v3_v3v3(v1, ctrl->bone->tail, ctrl->bone->head);
1755                         sub_v3_v3v3(v2, tail_vec, ctrl->bone->head);
1756                         
1757                         copy_v3_v3(ctrl->bone->tail, tail_vec);
1758                         
1759                         rotation_between_vecs_to_quat(qtail, v1, v2);
1760                         mul_qt_qtqt(ctrl->qrot, qtail, ctrl->qrot);
1761                         
1762                         resize = len_v3(v2) / len_v3v3(ctrl->head, ctrl->tail);
1763                 }
1764                 
1765                 ctrl->bone->roll = rollBoneByQuat(ctrl->bone, ctrl->up_axis, ctrl->qrot);
1766         
1767                 /* Cascade to connected control bones */
1768                 for (ctrl_child = rigg->controls.first; ctrl_child; ctrl_child = ctrl_child->next)
1769                 {
1770                         if (ctrl_child->link == ctrl->bone)
1771                         {
1772                                 repositionControl(rigg, ctrl_child, ctrl->bone->head, ctrl->bone->tail, ctrl->qrot, resize);
1773                         }
1774                         if (ctrl_child->link_tail == ctrl->bone)
1775                         {
1776                                 repositionTailControl(rigg, ctrl_child);
1777                         }
1778                 }
1779         }       
1780 }
1781
1782 static void repositionTailControl(RigGraph *rigg, RigControl *ctrl)
1783 {
1784         ctrl->flag |= RIG_CTRL_TAIL_DONE;
1785
1786         finalizeControl(rigg, ctrl, 1); /* resize will be recalculated anyway so we don't need it */
1787 }
1788
1789 static void repositionControl(RigGraph *rigg, RigControl *ctrl, float head[3], float UNUSED(tail[3]), float qrot[4], float resize)
1790 {
1791         float parent_offset[3], tail_offset[3];
1792         
1793         copy_v3_v3(parent_offset, ctrl->offset);
1794         mul_v3_fl(parent_offset, resize);
1795         mul_qt_v3(qrot, parent_offset);
1796         
1797         add_v3_v3v3(ctrl->bone->head, head, parent_offset); 
1798
1799         ctrl->flag |= RIG_CTRL_HEAD_DONE;
1800
1801         copy_qt_qt(ctrl->qrot, qrot);
1802
1803         if (ctrl->tail_mode == TL_NONE)
1804         {
1805                 sub_v3_v3v3(tail_offset, ctrl->tail, ctrl->head);
1806                 mul_v3_fl(tail_offset, resize);
1807                 mul_qt_v3(qrot, tail_offset);
1808
1809                 add_v3_v3v3(ctrl->bone->tail, ctrl->bone->head, tail_offset);
1810                 
1811                 ctrl->flag |= RIG_CTRL_TAIL_DONE;
1812         }
1813
1814         finalizeControl(rigg, ctrl, resize);
1815 }
1816
1817 static void repositionBone(bContext *C, RigGraph *rigg, RigEdge *edge, float vec0[3], float vec1[3], float up_axis[3])
1818 {
1819         Scene *scene = CTX_data_scene(C);
1820         EditBone *bone;
1821         RigControl *ctrl;
1822         float qrot[4], resize;
1823         float v1[3], v2[3];
1824         float l1, l2;
1825         
1826         bone = edge->bone;
1827         
1828         sub_v3_v3v3(v1, edge->tail, edge->head);
1829         sub_v3_v3v3(v2, vec1, vec0);
1830         
1831         l1 = normalize_v3(v1);
1832         l2 = normalize_v3(v2);
1833
1834         resize = l2 / l1;
1835         
1836         rotation_between_vecs_to_quat(qrot, v1, v2);
1837         
1838         copy_v3_v3(bone->head, vec0);
1839         copy_v3_v3(bone->tail, vec1);
1840         
1841         if (!is_zero_v3(up_axis))
1842         {
1843                 float qroll[4];
1844
1845                 if (scene->toolsettings->skgen_retarget_roll == SK_RETARGET_ROLL_VIEW)
1846                 {
1847                         bone->roll = rollBoneByQuatAligned(bone, edge->up_axis, qrot, qroll, up_axis);
1848                 }
1849                 else if (scene->toolsettings->skgen_retarget_roll == SK_RETARGET_ROLL_JOINT)
1850                 {
1851                         bone->roll = rollBoneByQuatJoint(edge, edge->prev, qrot, qroll, up_axis);
1852                 }
1853                 else
1854                 {
1855                         unit_qt(qroll);
1856                 }
1857                 
1858                 mul_qt_qtqt(qrot, qroll, qrot);
1859         }
1860         else
1861         {
1862                 bone->roll = rollBoneByQuat(bone, edge->up_axis, qrot);
1863         }
1864
1865         for (ctrl = rigg->controls.first; ctrl; ctrl = ctrl->next)
1866         {
1867                 if (ctrl->link == bone)
1868                 {
1869                         repositionControl(rigg, ctrl, vec0, vec1, qrot, resize);
1870                 }
1871                 if (ctrl->link_tail == bone)
1872                 {
1873                         repositionTailControl(rigg, ctrl);
1874                 }
1875         }
1876 }
1877
1878 static RetargetMode detectArcRetargetMode(RigArc *arc);
1879 static void retargetArctoArcLength(bContext *C, RigGraph *rigg, RigArc *iarc, RigNode *inode_start);
1880
1881
1882 static RetargetMode detectArcRetargetMode(RigArc *iarc)
1883 {
1884         RetargetMode mode = RETARGET_AGGRESSIVE;
1885         ReebArc *earc = iarc->link_mesh;
1886         RigEdge *edge;
1887         int large_angle = 0;
1888         float avg_angle = 0;
1889         /* float avg_length = 0; */ /* UNUSED */
1890         int nb_edges = 0;
1891         
1892         
1893         for (edge = iarc->edges.first; edge; edge = edge->next)
1894         {
1895                 avg_angle += edge->angle;
1896                 nb_edges++;
1897         }
1898         
1899         avg_angle /= nb_edges - 1; /* -1 because last edge doesn't have an angle */
1900
1901         /* avg_length = iarc->length / nb_edges; */  /* UNUSED */
1902         
1903         
1904         if (nb_edges > 2)
1905         {
1906                 for (edge = iarc->edges.first; edge; edge = edge->next)
1907                 {
1908                         if (fabs(edge->angle - avg_angle) > M_PI / 6)
1909                         {
1910                                 large_angle = 1;
1911                         }
1912                 }
1913         }
1914         else if (nb_edges == 2 && avg_angle > 0)
1915         {
1916                 large_angle = 1;
1917         }
1918                 
1919         
1920         if (large_angle == 0)
1921         {
1922                 mode = RETARGET_LENGTH;
1923         }
1924         
1925         if (earc->bcount <= (iarc->count - 1))
1926         {
1927                 mode = RETARGET_LENGTH;
1928         }
1929         
1930         return mode;
1931 }
1932
1933 #ifndef USE_THREADS
1934 static void printMovesNeeded(int *positions, int nb_positions)
1935 {
1936         int moves = 0;
1937         int i;
1938         
1939         for (i = 0; i < nb_positions; i++)
1940         {
1941                 moves += positions[i] - (i + 1);
1942         }
1943         
1944         printf("%i moves needed\n", moves);
1945 }
1946
1947 static void printPositions(int *positions, int nb_positions)
1948 {
1949         int i;
1950         
1951         for (i = 0; i < nb_positions; i++)
1952         {
1953                 printf("%i ", positions[i]);
1954         }
1955         printf("\n");
1956 }
1957 #endif
1958
1959 #define MAX_COST FLT_MAX /* FIX ME */
1960
1961 static float costDistance(BArcIterator *iter, float *vec0, float *vec1, int i0, int i1, float distance_weight)
1962 {
1963         EmbedBucket *bucket = NULL;
1964         float max_dist = 0;
1965         float v1[3], v2[3], c[3];
1966         float v1_inpf;
1967
1968         if (distance_weight > 0)
1969         {
1970                 sub_v3_v3v3(v1, vec0, vec1);
1971                 
1972                 v1_inpf = dot_v3v3(v1, v1);
1973                 
1974                 if (v1_inpf > 0)
1975                 {
1976                         int j;
1977                         for (j = i0 + 1; j < i1 - 1; j++)
1978                         {
1979                                 float dist;
1980                                 
1981                                 bucket = IT_peek(iter, j);
1982         
1983                                 sub_v3_v3v3(v2, bucket->p, vec1);
1984                 
1985                                 cross_v3_v3v3(c, v1, v2);
1986                                 
1987                                 dist = dot_v3v3(c, c) / v1_inpf;
1988                                 
1989                                 max_dist = dist > max_dist ? dist : max_dist;
1990                         }
1991                         
1992                         return distance_weight * max_dist;
1993                 }
1994                 else
1995                 {
1996                         return MAX_COST;
1997                 }
1998         }
1999         else
2000         {
2001                 return 0;
2002         }
2003 }
2004
2005 static float costAngle(float original_angle, float vec_first[3], float vec_second[3], float angle_weight)
2006 {
2007         if (angle_weight > 0)
2008         {
2009                 float current_angle;
2010                 
2011                 if (!is_zero_v3(vec_first) && !is_zero_v3(vec_second))
2012                 {
2013                         current_angle = saacos(dot_v3v3(vec_first, vec_second));
2014
2015                         return angle_weight * fabsf(current_angle - original_angle);
2016                 }
2017                 else
2018                 {
2019                         return angle_weight * (float)M_PI;
2020                 }
2021         }
2022         else
2023         {
2024                 return 0;
2025         }
2026 }
2027
2028 static float costLength(float original_length, float current_length, float length_weight)
2029 {
2030         if (current_length == 0)
2031         {
2032                 return MAX_COST;
2033         }
2034         else
2035         {
2036                 float length_ratio = fabs((current_length - original_length) / original_length);
2037                 return length_weight * length_ratio * length_ratio;
2038         }
2039 }
2040
2041 #if 0
2042 static float calcCostLengthDistance(BArcIterator *iter, float **vec_cache, RigEdge *edge, float *vec1, float *vec2, int i1, int i2)
2043 {
2044         float vec[3];
2045         float length;
2046
2047         sub_v3_v3v3(vec, vec2, vec1);
2048         length = normalize_v3(vec);
2049
2050         return costLength(edge->length, length) + costDistance(iter, vec1, vec2, i1, i2);
2051 }
2052 #endif
2053
2054 static float calcCostAngleLengthDistance(BArcIterator *iter, float **UNUSED(vec_cache), RigEdge *edge, float *vec0, float *vec1, float *vec2, int i1, int i2, float angle_weight, float length_weight, float distance_weight)
2055 {
2056         float vec_second[3], vec_first[3];
2057         float length2;
2058         float new_cost = 0;
2059
2060         sub_v3_v3v3(vec_second, vec2, vec1);
2061         length2 = normalize_v3(vec_second);
2062
2063
2064         /* Angle cost */        
2065         if (edge->prev)
2066         {
2067                 sub_v3_v3v3(vec_first, vec1, vec0); 
2068                 normalize_v3(vec_first);
2069                 
2070                 new_cost += costAngle(edge->prev->angle, vec_first, vec_second, angle_weight);
2071         }
2072
2073         /* Length cost */
2074         new_cost += costLength(edge->length, length2, length_weight);
2075
2076         /* Distance cost */
2077         new_cost += costDistance(iter, vec1, vec2, i1, i2, distance_weight);
2078
2079         return new_cost;
2080 }
2081
2082 static int indexMemoNode(int nb_positions, int previous, int current, int joints_left)
2083 {
2084         return joints_left * nb_positions * nb_positions + current * nb_positions + previous;
2085 }
2086
2087 static void copyMemoPositions(int *positions, MemoNode *table, int nb_positions, int joints_left)
2088 {
2089         int previous = 0, current = 0;
2090         int i = 0;
2091         
2092         for (i = 0; joints_left > 0; joints_left--, i++)
2093         {
2094                 MemoNode *node;
2095                 node = table + indexMemoNode(nb_positions, previous, current, joints_left);
2096                 
2097                 positions[i] = node->next;
2098                 
2099                 previous = current;
2100                 current = node->next;
2101         }
2102 }
2103
2104 static MemoNode * solveJoints(MemoNode *table, BArcIterator *iter, float **vec_cache, int nb_joints, int nb_positions, int previous, int current, RigEdge *edge, int joints_left, float angle_weight, float length_weight, float distance_weight)
2105 {
2106         MemoNode *node;
2107         int index = indexMemoNode(nb_positions, previous, current, joints_left);
2108         
2109         node = table + index;
2110         
2111         if (node->weight != 0)
2112         {
2113                 return node;
2114         }
2115         else if (joints_left == 0)
2116         {
2117                 float *vec0 = vec_cache[previous];
2118                 float *vec1 = vec_cache[current];
2119                 float *vec2 = vec_cache[nb_positions + 1];
2120
2121                 node->weight = calcCostAngleLengthDistance(iter, vec_cache, edge, vec0, vec1, vec2, current, iter->length, angle_weight, length_weight, distance_weight);
2122
2123                 return node;
2124         }
2125         else
2126         {
2127                 MemoNode *min_node = NULL;
2128                 float *vec0 = vec_cache[previous];
2129                 float *vec1 = vec_cache[current];
2130                 float min_weight= 0.0f;
2131                 int min_next= 0;
2132                 int next;
2133                 
2134                 for (next = current + 1; next <= nb_positions - (joints_left - 1); next++)
2135                 {
2136                         MemoNode *next_node;
2137                         float *vec2 = vec_cache[next];
2138                         float weight = 0.0f;
2139                         
2140                         /* ADD WEIGHT OF PREVIOUS - CURRENT - NEXT triple */
2141                         weight = calcCostAngleLengthDistance(iter, vec_cache, edge, vec0, vec1, vec2, current, next, angle_weight, length_weight, distance_weight);
2142                         
2143                         if (weight >= MAX_COST)
2144                         {
2145                                 continue;
2146                         }
2147                         
2148                         /* add node weight */
2149                         next_node = solveJoints(table, iter, vec_cache, nb_joints, nb_positions, current, next, edge->next, joints_left - 1, angle_weight, length_weight, distance_weight);
2150                         weight += next_node->weight;
2151                         
2152                         if (min_node == NULL || weight < min_weight)
2153                         {
2154                                 min_weight = weight;
2155                                 min_node = next_node;
2156                                 min_next = next;
2157                         }
2158                 }
2159                 
2160                 if (min_node)
2161                 {
2162                         node->weight = min_weight;
2163                         node->next = min_next;
2164                         return node;
2165                 }
2166                 else
2167                 {
2168                         node->weight = MAX_COST;
2169                         return node;
2170                 }
2171         }
2172         
2173 }
2174
2175 static int testFlipArc(RigArc *iarc, RigNode *inode_start)
2176 {
2177         ReebArc *earc = iarc->link_mesh;
2178         ReebNode *enode_start = BIF_NodeFromIndex(earc, inode_start->link_mesh);
2179         
2180         /* no flip needed if both nodes are the same */
2181         if ((enode_start == earc->head && inode_start == iarc->head) || (enode_start == earc->tail && inode_start == iarc->tail))
2182         {
2183                 return 0;
2184         }
2185         else
2186         {
2187                 return 1;
2188         }
2189 }
2190
2191 static void retargetArctoArcAggresive(bContext *C, RigGraph *rigg, RigArc *iarc, RigNode *inode_start)
2192 {
2193         ReebArcIterator arc_iter;
2194         BArcIterator *iter = (BArcIterator*)&arc_iter;
2195         RigEdge *edge;
2196         EmbedBucket *bucket = NULL;
2197         ReebNode *node_start, *node_end;
2198         ReebArc *earc = iarc->link_mesh;
2199         float angle_weight = 1.0; // GET FROM CONTEXT
2200         float length_weight = 1.0;
2201         float distance_weight = 1.0;
2202 #ifndef USE_THREADS
2203         float min_cost = FLT_MAX;
2204 #endif
2205         float *vec0, *vec1;
2206         int *best_positions;
2207         int nb_edges = BLI_countlist(&iarc->edges);
2208         int nb_joints = nb_edges - 1;
2209         RetargetMethod method = METHOD_MEMOIZE;
2210         int i;
2211         
2212         if (nb_joints > earc->bcount)
2213         {
2214                 printf("NOT ENOUGH BUCKETS!\n");
2215                 return;
2216         }
2217
2218         best_positions = MEM_callocN(sizeof(int) * nb_joints, "Best positions");
2219         
2220         if (testFlipArc(iarc, inode_start))
2221         {
2222                 node_start = earc->tail;
2223                 node_end = earc->head;
2224         }
2225         else
2226         {
2227                 node_start = earc->head;
2228                 node_end = earc->tail;
2229         }
2230
2231         /* equal number of joints and potential position, just fill them in */
2232         if (nb_joints == earc->bcount)
2233         {
2234                 int i;
2235                 
2236                 /* init with first values */
2237                 for (i = 0; i < nb_joints; i++)
2238                 {
2239                         best_positions[i] = i + 1;
2240                 }
2241         }
2242         if (method == METHOD_MEMOIZE)
2243         {
2244                 int nb_positions = earc->bcount;
2245                 int nb_memo_nodes = nb_positions * nb_positions * (nb_joints + 1);
2246                 MemoNode *table = MEM_callocN(nb_memo_nodes * sizeof(MemoNode), "memoization table");
2247 #ifndef USE_THREADS
2248                 MemoNode *result;
2249 #endif
2250                 float **positions_cache = MEM_callocN(sizeof(float*) * (nb_positions + 2), "positions cache");
2251                 int i;
2252                 
2253                 positions_cache[0] = node_start->p;
2254                 positions_cache[nb_positions + 1] = node_end->p;
2255                 
2256                 initArcIterator(iter, earc, node_start);
2257
2258                 for (i = 1; i <= nb_positions; i++)
2259                 {
2260                         EmbedBucket *bucket = IT_peek(iter, i);
2261                         positions_cache[i] = bucket->p;
2262                 }
2263
2264 #ifndef USE_THREADS
2265                 result = solveJoints(table, iter, positions_cache, nb_joints, earc->bcount, 0, 0, iarc->edges.first, nb_joints, angle_weight, length_weight, distance_weight);
2266                 min_cost = result->weight;
2267 #else
2268                 solveJoints(table, iter, positions_cache, nb_joints, earc->bcount, 0, 0, iarc->edges.first, nb_joints, angle_weight, length_weight, distance_weight);
2269 #endif
2270
2271                 copyMemoPositions(best_positions, table, earc->bcount, nb_joints);
2272
2273                 MEM_freeN(table);
2274                 MEM_freeN(positions_cache);
2275         }
2276
2277         vec0 = node_start->p;
2278         initArcIterator(iter, earc, node_start);
2279         
2280 #ifndef USE_THREADS
2281         printPositions(best_positions, nb_joints);
2282         printMovesNeeded(best_positions, nb_joints);
2283         printf("min_cost %f\n", min_cost);
2284         printf("buckets: %i\n", earc->bcount);
2285 #endif
2286
2287         /* set joints to best position */
2288         for (edge = iarc->edges.first, i = 0;
2289              edge;
2290              edge = edge->next, i++)
2291         {
2292                 float *no = NULL;
2293                 if (i < nb_joints)
2294                 {
2295                         bucket = IT_peek(iter, best_positions[i]);
2296                         vec1 = bucket->p;
2297                         no = bucket->no;
2298                 }
2299                 else
2300                 {
2301                         vec1 = node_end->p;
2302                         no = node_end->no;
2303                 }
2304                 
2305                 if (edge->bone)
2306                 {
2307                         repositionBone(C, rigg, edge, vec0, vec1, no);
2308                 }
2309                 
2310                 vec0 = vec1;
2311         }
2312
2313         MEM_freeN(best_positions);
2314 }
2315
2316 static void retargetArctoArcLength(bContext *C, RigGraph *rigg, RigArc *iarc, RigNode *inode_start)
2317 {
2318         ReebArcIterator arc_iter;
2319         BArcIterator *iter = (BArcIterator*)&arc_iter;
2320         ReebArc *earc = iarc->link_mesh;
2321         ReebNode *node_start, *node_end;
2322         RigEdge *edge;
2323         EmbedBucket *bucket = NULL;
2324         float embedding_length = 0;
2325         float *vec0 = NULL;
2326         float *vec1 = NULL;
2327         float *previous_vec = NULL;
2328
2329         
2330         if (testFlipArc(iarc, inode_start))
2331         {
2332                 node_start = (ReebNode*)earc->tail;
2333                 node_end = (ReebNode*)earc->head;
2334         }
2335         else
2336         {
2337                 node_start = (ReebNode*)earc->head;
2338                 node_end = (ReebNode*)earc->tail;
2339         }
2340         
2341         initArcIterator(iter, earc, node_start);
2342
2343         bucket = IT_next(iter);
2344         
2345         vec0 = node_start->p;
2346         
2347         while (bucket != NULL)
2348         {
2349                 vec1 = bucket->p;
2350                 
2351                 embedding_length += len_v3v3(vec0, vec1);
2352                 
2353                 vec0 = vec1;
2354                 bucket = IT_next(iter);
2355         }
2356         
2357         embedding_length += len_v3v3(node_end->p, vec1);
2358         
2359         /* fit bones */
2360         initArcIterator(iter, earc, node_start);
2361
2362         bucket = IT_next(iter);
2363
2364         vec0 = node_start->p;
2365         previous_vec = vec0;
2366         vec1 = bucket->p;
2367         
2368         for (edge = iarc->edges.first; edge; edge = edge->next)
2369         {
2370                 float new_bone_length = edge->length / iarc->length * embedding_length;
2371                 float *no = NULL;
2372                 float length = 0;
2373
2374                 while (bucket && new_bone_length > length)
2375                 {
2376                         length += len_v3v3(previous_vec, vec1);
2377                         bucket = IT_next(iter);
2378                         previous_vec = vec1;
2379                         vec1 = bucket->p;
2380                         no = bucket->no;
2381                 }
2382                 
2383                 if (bucket == NULL)
2384                 {
2385                         vec1 = node_end->p;
2386                         no = node_end->no;
2387                 }
2388
2389                 /* no need to move virtual edges (space between unconnected bones) */           
2390                 if (edge->bone)
2391                 {
2392                         repositionBone(C, rigg, edge, vec0, vec1, no);
2393                 }
2394                 
2395                 vec0 = vec1;
2396                 previous_vec = vec1;
2397         }
2398 }
2399
2400 static void retargetArctoArc(bContext *C, RigGraph *rigg, RigArc *iarc, RigNode *inode_start)
2401 {
2402 #ifdef USE_THREADS
2403         RetargetParam *p = MEM_callocN(sizeof(RetargetParam), "RetargetParam");
2404         
2405         p->rigg = rigg;
2406         p->iarc = iarc;
2407         p->inode_start = inode_start;
2408         p->context = C;
2409         
2410         BLI_insert_work(rigg->worker, p);
2411 #else
2412         RetargetParam p;
2413
2414         p.rigg = rigg;
2415         p.iarc = iarc;
2416         p.inode_start = inode_start;
2417         p.context = C;
2418         
2419         exec_retargetArctoArc(&p);
2420 #endif
2421 }
2422
2423 void *exec_retargetArctoArc(void *param)
2424 {
2425         RetargetParam *p = (RetargetParam*)param;
2426         RigGraph *rigg = p->rigg;
2427         RigArc *iarc = p->iarc;
2428         bContext *C = p->context;       
2429         RigNode *inode_start = p->inode_start;
2430         ReebArc *earc = iarc->link_mesh;
2431         
2432         if (BLI_countlist(&iarc->edges) == 1)
2433         {
2434                 RigEdge *edge = iarc->edges.first;
2435
2436                 if (testFlipArc(iarc, inode_start))
2437                 {
2438                         repositionBone(C, rigg, edge, earc->tail->p, earc->head->p, earc->head->no);
2439                 }
2440                 else
2441                 {
2442                         repositionBone(C, rigg, edge, earc->head->p, earc->tail->p, earc->tail->no);
2443                 }
2444         }
2445         else
2446         {
2447                 RetargetMode mode = detectArcRetargetMode(iarc);
2448                 
2449                 if (mode == RETARGET_AGGRESSIVE)
2450                 {
2451                         retargetArctoArcAggresive(C, rigg, iarc, inode_start);
2452                 }
2453                 else
2454                 {               
2455                         retargetArctoArcLength(C, rigg, iarc, inode_start);
2456                 }
2457         }
2458
2459 #ifdef USE_THREADS
2460         MEM_freeN(p);
2461 #endif
2462         
2463         return NULL;
2464 }
2465
2466 static void matchMultiResolutionNode(RigGraph *rigg, RigNode *inode, ReebNode *top_node)
2467 {
2468         ReebNode *enode = top_node;
2469         ReebGraph *reebg = BIF_graphForMultiNode(rigg->link_mesh, enode);
2470         int ishape, eshape;
2471         
2472         ishape = BLI_subtreeShape((BGraph*)rigg, (BNode*)inode, NULL, 0) % SHAPE_LEVELS;
2473         eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, NULL, 0) % SHAPE_LEVELS;
2474         
2475         inode->link_mesh = enode;
2476
2477         while (ishape == eshape && enode->link_down)
2478         {
2479                 inode->link_mesh = enode;
2480
2481                 enode = enode->link_down;
2482                 reebg = BIF_graphForMultiNode(rigg->link_mesh, enode); /* replace with call to link_down once that exists */
2483                 eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, NULL, 0) % SHAPE_LEVELS;
2484         } 
2485 }
2486
2487 static void markMultiResolutionChildArc(ReebNode *end_enode, ReebNode *enode)
2488 {
2489         int i;
2490         
2491         for(i = 0; i < enode->degree; i++)
2492         {
2493                 ReebArc *earc = (ReebArc*)enode->arcs[i];
2494                 
2495                 if (earc->flag == ARC_FREE)
2496                 {
2497                         earc->flag = ARC_TAKEN;
2498                         
2499                         if (earc->tail->degree > 1 && earc->tail != end_enode)
2500                         {
2501                                 markMultiResolutionChildArc(end_enode, earc->tail);
2502                         }
2503                         break;
2504                 }
2505         }
2506 }
2507
2508 static void markMultiResolutionArc(ReebArc *start_earc)
2509 {
2510         if (start_earc->link_up)
2511         {
2512                 ReebArc *earc;
2513                 for (earc = start_earc->link_up ; earc; earc = earc->link_up)
2514                 {
2515                         earc->flag = ARC_TAKEN;
2516                         
2517                         if (earc->tail->index != start_earc->tail->index)
2518                         {
2519                                 markMultiResolutionChildArc(earc->tail, earc->tail);
2520                         }
2521                 }
2522         }
2523 }
2524
2525 static void matchMultiResolutionArc(RigGraph *rigg, RigNode *start_node, RigArc *next_iarc, ReebArc *next_earc)
2526 {
2527         ReebNode *enode = next_earc->head;
2528         ReebGraph *reebg = BIF_graphForMultiNode(rigg->link_mesh, enode);
2529         int ishape, eshape;
2530
2531         ishape = BLI_subtreeShape((BGraph*)rigg, (BNode*)start_node, (BArc*)next_iarc, 1) % SHAPE_LEVELS;
2532         eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, (BArc*)next_earc, 1) % SHAPE_LEVELS;
2533         
2534         while (ishape != eshape && next_earc->link_up)
2535         {
2536                 next_earc->flag = ARC_TAKEN; // mark previous as taken, to prevent backtrack on lower levels
2537                 
2538                 next_earc = next_earc->link_up;
2539                 reebg = reebg->link_up;
2540                 enode = next_earc->head;
2541                 eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, (BArc*)next_earc, 1) % SHAPE_LEVELS;
2542         } 
2543
2544         next_earc->flag = ARC_USED;
2545         next_iarc->link_mesh = next_earc;
2546         
2547         /* mark all higher levels as taken too */
2548         markMultiResolutionArc(next_earc);
2549 //      while (next_earc->link_up)
2550 //      {
2551 //              next_earc = next_earc->link_up;
2552 //              next_earc->flag = ARC_TAKEN;
2553 //      }
2554 }
2555
2556 static void matchMultiResolutionStartingNode(RigGraph *rigg, ReebGraph *reebg, RigNode *inode)
2557 {
2558         ReebNode *enode;
2559         int ishape, eshape;
2560         
2561         enode = reebg->nodes.first;
2562         
2563         ishape = BLI_subtreeShape((BGraph*)rigg, (BNode*)inode, NULL, 0) % SHAPE_LEVELS;
2564         eshape = BLI_subtreeShape((BGraph*)rigg->link_mesh, (BNode*)enode, NULL, 0) % SHAPE_LEVELS;
2565         
2566         while (ishape != eshape && reebg->link_up)
2567         {
2568                 reebg = reebg->link_up;
2569                 
2570                 enode = reebg->nodes.first;
2571                 
2572                 eshape = BLI_subtreeShape((BGraph*)reebg, (BNode*)enode, NULL, 0) % SHAPE_LEVELS;
2573         } 
2574
2575         inode->link_mesh = enode;
2576 }
2577
2578 static void findCorrespondingArc(RigGraph *rigg, RigArc *start_arc, RigNode *start_node, RigArc *next_iarc, int root)
2579 {
2580         ReebNode *enode = start_node->link_mesh;
2581         ReebArc *next_earc;
2582         int symmetry_level = next_iarc->symmetry_level;
2583         int symmetry_group = next_iarc->symmetry_group;
2584         int symmetry_flag = next_iarc->symmetry_flag;
2585         int i;
2586         
2587         next_iarc->link_mesh = NULL;
2588                 
2589 //      if (root)
2590 //      {
2591 //              printf("-----------------------\n");
2592 //              printf("MATCHING LIMB\n");
2593 //              RIG_printArcBones(next_iarc);
2594 //      }
2595         
2596         for(i = 0; i < enode->degree; i++)
2597         {
2598                 next_earc = (ReebArc*)enode->arcs[i];
2599                 
2600 //              if (next_earc->flag == ARC_FREE)
2601 //              {
2602 //                      printf("candidate (level %i ?= %i) (flag %i ?= %i) (group %i ?= %i)\n",
2603 //                      symmetry_level, next_earc->symmetry_level,
2604 //                      symmetry_flag, next_earc->symmetry_flag, 
2605 //                      symmetry_group, next_earc->symmetry_flag);
2606 //              }
2607                 
2608                 if (next_earc->flag == ARC_FREE &&
2609                         next_earc->symmetry_flag == symmetry_flag &&
2610                         next_earc->symmetry_group == symmetry_group &&
2611                         next_earc->symmetry_level == symmetry_level)
2612                 {
2613 //                      printf("CORRESPONDING ARC FOUND\n");
2614 //                      printf("flag %i -- level %i -- flag %i -- group %i\n", next_earc->flag, next_earc->symmetry_level, next_earc->symmetry_flag, next_earc->symmetry_group);
2615                         
2616                         matchMultiResolutionArc(rigg, start_node, next_iarc, next_earc);
2617                         break;
2618                 }
2619         }
2620         
2621         /* not found, try at higher nodes (lower node might have filtered internal arcs, messing shape of tree */
2622         if (next_iarc->link_mesh == NULL)
2623         {
2624 //              printf("NO CORRESPONDING ARC FOUND - GOING TO HIGHER LEVELS\n");
2625                 
2626                 if (enode->link_up)
2627                 {
2628                         start_node->link_mesh = enode->link_up;
2629                         findCorrespondingArc(rigg, start_arc, start_node, next_iarc, 0);
2630                 }
2631         }
2632
2633         /* still not found, print debug info */
2634         if (root && next_iarc->link_mesh == NULL)
2635         {
2636                 start_node->link_mesh = enode; /* linking back with root node */
2637                 
2638 //              printf("NO CORRESPONDING ARC FOUND\n");
2639 //              RIG_printArcBones(next_iarc);
2640 //              
2641 //              printf("ON NODE %i, multilevel %i\n", enode->index, enode->multi_level);
2642 //              
2643 //              printf("LOOKING FOR\n");
2644 //              printf("flag %i -- level %i -- flag %i -- group %i\n", ARC_FREE, symmetry_level, symmetry_flag, symmetry_group);
2645 //              
2646 //              printf("CANDIDATES\n");
2647 //              for(i = 0; i < enode->degree; i++)
2648 //              {
2649 //                      next_earc = (ReebArc*)enode->arcs[i];
2650 //                      printf("flag %i -- level %i -- flag %i -- group %i\n", next_earc->flag, next_earc->symmetry_level, next_earc->symmetry_flag, next_earc->symmetry_group);
2651 //              }
2652                 
2653                 /* Emergency matching */
2654                 for(i = 0; i < enode->degree; i++)
2655                 {
2656                         next_earc = (ReebArc*)enode->arcs[i];
2657                         
2658                         if (next_earc->flag == ARC_FREE && next_earc->symmetry_level == symmetry_level)
2659                         {
2660 //                              printf("USING: \n");
2661 //                              printf("flag %i -- level %i -- flag %i -- group %i\n", next_earc->flag, next_earc->symmetry_level, next_earc->symmetry_flag, next_earc->symmetry_group);
2662                                 matchMultiResolutionArc(rigg, start_node, next_iarc, next_earc);
2663                                 break;
2664                         }
2665                 }
2666         }
2667
2668 }
2669
2670 static void retargetSubgraph(bContext *C, RigGraph *rigg, RigArc *start_arc, RigNode *start_node)
2671 {
2672         RigNode *inode = start_node;
2673         int i;
2674
2675         /* no start arc on first node */
2676         if (start_arc)
2677         {               
2678                 ReebNode *enode = start_node->link_mesh;
2679                 ReebArc *earc = start_arc->link_mesh;
2680                 
2681                 retargetArctoArc(C, rigg, start_arc, start_node);
2682                 
2683                 enode = BIF_otherNodeFromIndex(earc, enode);
2684                 inode = (RigNode*)BLI_otherNode((BArc*)start_arc, (BNode*)inode);
2685         
2686                 /* match with lowest node with correct shape */
2687                 matchMultiResolutionNode(rigg, inode, enode);
2688         }
2689         
2690         for(i = 0; i < inode->degree; i++)
2691         {
2692                 RigArc *next_iarc = (RigArc*)inode->arcs[i];
2693                 
2694                 /* no back tracking */
2695                 if (next_iarc != start_arc)
2696                 {
2697                         findCorrespondingArc(rigg, start_arc, inode, next_iarc, 1);
2698                         if (next_iarc->link_mesh)
2699                         {
2700                                 retargetSubgraph(C, rigg, next_iarc, inode);
2701                         }
2702                 }
2703         }
2704 }
2705
2706 static void finishRetarget(RigGraph *rigg)
2707 {
2708 #ifdef USE_THREADS
2709         BLI_end_worker(rigg->worker);
2710 #endif
2711 }
2712
2713 static void adjustGraphs(bContext *C, RigGraph *rigg)
2714 {
2715         bArmature *arm= rigg->ob->data;
2716         RigArc *arc;
2717         
2718         for (arc = rigg->arcs.first; arc; arc = arc->next)
2719         {
2720                 if (arc->link_mesh)
2721                 {
2722                         retargetArctoArc(C, rigg, arc, arc->head);
2723                 }
2724         }
2725
2726         finishRetarget(rigg);
2727
2728         /* Turn the list into an armature */
2729         arm->edbo = rigg->editbones;
2730         ED_armature_from_edit(rigg->ob);
2731         
2732         ED_undo_push(C, "Retarget Skeleton");
2733 }
2734
2735 static void retargetGraphs(bContext *C, RigGraph *rigg)
2736 {
2737         bArmature *arm= rigg->ob->data;
2738         ReebGraph *reebg = rigg->link_mesh;
2739         RigNode *inode;
2740         
2741         /* flag all ReebArcs as free */
2742         BIF_flagMultiArcs(reebg, ARC_FREE);
2743         
2744         /* return to first level */
2745         inode = rigg->head;
2746         
2747         matchMultiResolutionStartingNode(rigg, reebg, inode);
2748
2749         retargetSubgraph(C, rigg, NULL, inode);
2750         
2751         //generateMissingArcs(rigg);
2752         
2753         finishRetarget(rigg);
2754
2755         /* Turn the list into an armature */
2756         arm->edbo = rigg->editbones;
2757         ED_armature_from_edit(rigg->ob);
2758 }
2759
2760 const char *RIG_nameBone(RigGraph *rg, int arc_index, int bone_index)
2761 {
2762         RigArc *arc = BLI_findlink(&rg->arcs, arc_index);
2763         RigEdge *iedge;
2764
2765         if (arc == NULL)
2766         {
2767                 return "None";
2768         }
2769         
2770         if (bone_index == BLI_countlist(&arc->edges))
2771         {
2772                 return "Last joint";
2773         }
2774
2775         iedge = BLI_findlink(&arc->edges, bone_index);
2776         
2777         if (iedge == NULL)
2778         {
2779                 return "Done";
2780         }
2781         
2782         if (iedge->bone == NULL)
2783         {
2784                 return "Bone offset";
2785         }
2786         
2787         return iedge->bone->name;
2788 }
2789
2790 int RIG_nbJoints(RigGraph *rg)
2791 {
2792         RigArc *arc;
2793         int total = 0;
2794         
2795         total += BLI_countlist(&rg->nodes);
2796         
2797         for (arc = rg->arcs.first; arc; arc = arc->next)
2798         {
2799                 total += BLI_countlist(&arc->edges) - 1; /* -1 because end nodes are already counted */
2800         }
2801         
2802         return total;
2803 }
2804
2805 static void BIF_freeRetarget(void)
2806 {
2807         if (GLOBAL_RIGG)
2808         {
2809                 RIG_freeRigGraph((BGraph*)GLOBAL_RIGG);
2810                 GLOBAL_RIGG = NULL;
2811         }
2812 }
2813
2814 void BIF_retargetArmature(bContext *C)
2815 {
2816         ReebGraph *reebg;
2817         double start_time, end_time;
2818         double gstart_time, gend_time;
2819         double reeb_time, rig_time=0.0, retarget_time=0.0, total_time;
2820         
2821         gstart_time = start_time = PIL_check_seconds_timer();
2822         
2823         reebg = BIF_ReebGraphMultiFromEditMesh(C);
2824         
2825         end_time = PIL_check_seconds_timer();
2826         reeb_time = end_time - start_time;
2827         
2828         printf("Reeb Graph created\n");
2829
2830         CTX_DATA_BEGIN(C, Base*, base, selected_editable_bases) {
2831                 Object *ob = base->object;
2832
2833                 if (ob->type==OB_ARMATURE)
2834                 {
2835                         RigGraph *rigg;
2836                         bArmature *arm;
2837
2838                         arm = ob->data;
2839                 
2840                         /* Put the armature into editmode */
2841                         
2842                 
2843                         start_time = PIL_check_seconds_timer();
2844
2845                         rigg = RIG_graphFromArmature(C, ob, arm);
2846                         
2847                         end_time = PIL_check_seconds_timer();
2848                         rig_time = end_time - start_time;
2849
2850                         printf("Armature graph created\n");
2851         
2852                         //RIG_printGraph(rigg);
2853                         
2854                         rigg->link_mesh = reebg;
2855                         
2856                         printf("retargetting %s\n", ob->id.name);
2857                         
2858                         start_time = PIL_check_seconds_timer();
2859
2860                         retargetGraphs(C, rigg);
2861                         
2862                         end_time = PIL_check_seconds_timer();
2863                         retarget_time = end_time - start_time;
2864
2865                         BIF_freeRetarget();
2866                         
2867                         GLOBAL_RIGG = rigg;
2868                         
2869                         break; /* only one armature at a time */
2870                 }
2871         }
2872         CTX_DATA_END;
2873
2874         
2875         gend_time = PIL_check_seconds_timer();
2876
2877         total_time = gend_time - gstart_time;
2878
2879         printf("-----------\n");
2880         printf("runtime: \t%.3f\n", total_time);
2881         printf("reeb: \t\t%.3f (%.1f%%)\n", reeb_time, reeb_time / total_time * 100);
2882         printf("rig: \t\t%.3f (%.1f%%)\n", rig_time, rig_time / total_time * 100);
2883         printf("retarget: \t%.3f (%.1f%%)\n", retarget_time, retarget_time / total_time * 100);
2884         printf("-----------\n");
2885         
2886         ED_undo_push(C, "Retarget Skeleton");
2887
2888         // XXX  
2889 //      allqueue(REDRAWVIEW3D, 0);
2890 }
2891
2892 void BIF_retargetArc(bContext *C, ReebArc *earc, RigGraph *template_rigg)
2893 {
2894         Object *obedit = CTX_data_edit_object(C);
2895         Scene *scene = CTX_data_scene(C);
2896         bArmature *armedit = obedit->data;
2897         Object *ob;
2898         RigGraph *rigg;
2899         RigArc *iarc;
2900         char *side_string = scene->toolsettings->skgen_side_string;
2901         char *num_string = scene->toolsettings->skgen_num_string;
2902         int free_template = 0;
2903         
2904         if (template_rigg)
2905         {
2906                 ob = template_rigg->ob;         
2907         }
2908         else
2909         {
2910                 free_template = 1;
2911                 ob = obedit;
2912                 template_rigg = armatureSelectedToGraph(C, ob, ob->data);
2913         }
2914         
2915         if (template_rigg->arcs.first == NULL)
2916         {
2917 //              XXX
2918 //              error("No Template and no deforming bones selected");
2919                 return;
2920         }
2921         
2922         rigg = cloneRigGraph(template_rigg, armedit->edbo, obedit, side_string, num_string);
2923         
2924         iarc = rigg->arcs.first;
2925         
2926         iarc->link_mesh = earc;
2927         iarc->head->link_mesh = earc->head;
2928         iarc->tail->link_mesh = earc->tail;
2929         
2930         retargetArctoArc(C, rigg, iarc, iarc->head);
2931         
2932         finishRetarget(rigg);
2933         
2934         /* free template if it comes from the edit armature */
2935         if (free_template)
2936         {
2937                 RIG_freeRigGraph((BGraph*)template_rigg);
2938         }
2939         RIG_freeRigGraph((BGraph*)rigg);
2940         
2941         ED_armature_validate_active(armedit);
2942
2943 //      XXX
2944 //      allqueue(REDRAWVIEW3D, 0);
2945 }
2946
2947 void BIF_adjustRetarget(bContext *C)
2948 {
2949         if (GLOBAL_RIGG)
2950         {
2951                 adjustGraphs(C, GLOBAL_RIGG);
2952         }