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