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