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