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