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