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