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