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