add linklist stack macros, use where over allocating an array was previously done.
[blender.git] / source / blender / editors / transform / transform_conversions.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  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/editors/transform/transform_conversions.c
29  *  \ingroup edtransform
30  */
31
32
33 #ifndef WIN32
34 #include <unistd.h>
35 #else
36 #include <io.h>
37 #endif
38 #include <string.h>
39 #include <math.h>
40
41 #include "DNA_anim_types.h"
42 #include "DNA_armature_types.h"
43 #include "DNA_lattice_types.h"
44 #include "DNA_mesh_types.h"
45 #include "DNA_meta_types.h"
46 #include "DNA_node_types.h"
47 #include "DNA_screen_types.h"
48 #include "DNA_space_types.h"
49 #include "DNA_sequence_types.h"
50 #include "DNA_view3d_types.h"
51 #include "DNA_constraint_types.h"
52 #include "DNA_scene_types.h"
53 #include "DNA_meshdata_types.h"
54 #include "DNA_gpencil_types.h"
55 #include "DNA_movieclip_types.h"
56 #include "DNA_mask_types.h"
57
58 #include "MEM_guardedalloc.h"
59
60 #include "BLI_math.h"
61 #include "BLI_utildefines.h"
62 #include "BLI_smallhash.h"
63 #include "BLI_listbase.h"
64 #include "BLI_linklist_stack.h"
65 #include "BLI_string.h"
66 #include "BLI_rect.h"
67
68 #include "BKE_DerivedMesh.h"
69 #include "BKE_action.h"
70 #include "BKE_armature.h"
71 #include "BKE_constraint.h"
72 #include "BKE_context.h"
73 #include "BKE_curve.h"
74 #include "BKE_depsgraph.h"
75 #include "BKE_fcurve.h"
76 #include "BKE_global.h"
77 #include "BKE_gpencil.h"
78 #include "BKE_key.h"
79 #include "BKE_main.h"
80 #include "BKE_mesh.h"
81 #include "BKE_modifier.h"
82 #include "BKE_movieclip.h"
83 #include "BKE_nla.h"
84 #include "BKE_node.h"
85 #include "BKE_object.h"
86 #include "BKE_particle.h"
87 #include "BKE_pointcache.h"
88 #include "BKE_report.h"
89 #include "BKE_rigidbody.h"
90 #include "BKE_scene.h"
91 #include "BKE_sequencer.h"
92 #include "BKE_editmesh.h"
93 #include "BKE_tracking.h"
94 #include "BKE_mask.h"
95 #include "BKE_lattice.h"
96
97 #include "BIK_api.h"
98
99 #include "ED_anim_api.h"
100 #include "ED_armature.h"
101 #include "ED_particle.h"
102 #include "ED_image.h"
103 #include "ED_keyframing.h"
104 #include "ED_keyframes_edit.h"
105 #include "ED_object.h"
106 #include "ED_markers.h"
107 #include "ED_mesh.h"
108 #include "ED_node.h"
109 #include "ED_types.h"
110 #include "ED_uvedit.h"
111 #include "ED_clip.h"
112 #include "ED_mask.h"
113 #include "ED_util.h"  /* for crazyspace correction */
114
115 #include "WM_api.h"  /* for WM_event_add_notifier to deal with stabilization nodes */
116 #include "WM_types.h"
117
118 #include "UI_view2d.h"
119 #include "UI_interface.h"
120
121 #include "RNA_access.h"
122
123 #include "transform.h"
124 #include "bmesh.h"
125
126 /* when transforming islands */
127 struct TransIslandData {
128         float co[3];
129         float axismtx[3][3];
130 };
131
132 /* local function prototype - for Object/Bone Constraints */
133 static bool constraints_list_needinv(TransInfo *t, ListBase *list);
134
135 /* ************************** Functions *************************** */
136
137 static int trans_data_compare_dist(const void *a, const void *b)
138 {
139         const TransData *td_a = (const TransData *)a;
140         const TransData *td_b = (const TransData *)b;
141
142         if      (td_a->dist < td_b->dist) return -1;
143         else if (td_a->dist > td_b->dist) return  1;
144         else                              return  0;
145 }
146
147 static int trans_data_compare_rdist(const void *a, const void *b)
148 {
149         const TransData *td_a = (const TransData *)a;
150         const TransData *td_b = (const TransData *)b;
151
152         if      (td_a->rdist < td_b->rdist) return -1;
153         else if (td_a->rdist > td_b->rdist) return  1;
154         else                                return  0;
155 }
156
157 void sort_trans_data_dist(TransInfo *t)
158 {
159         TransData *start = t->data;
160         int i;
161
162         for (i = 0; i < t->total && start->flag & TD_SELECTED; i++)
163                 start++;
164         
165         if (i < t->total) {
166                 if (t->flag & T_PROP_CONNECTED)
167                         qsort(start, t->total - i, sizeof(TransData), trans_data_compare_dist);
168                 else
169                         qsort(start, t->total - i, sizeof(TransData), trans_data_compare_rdist);
170         }
171 }
172
173 static void sort_trans_data(TransInfo *t)
174 {
175         TransData *sel, *unsel;
176         TransData temp;
177         unsel = t->data;
178         sel = t->data;
179         sel += t->total - 1;
180         while (sel > unsel) {
181                 while (unsel->flag & TD_SELECTED) {
182                         unsel++;
183                         if (unsel == sel) {
184                                 return;
185                         }
186                 }
187                 while (!(sel->flag & TD_SELECTED)) {
188                         sel--;
189                         if (unsel == sel) {
190                                 return;
191                         }
192                 }
193                 temp = *unsel;
194                 *unsel = *sel;
195                 *sel = temp;
196                 sel--;
197                 unsel++;
198         }
199 }
200
201 /* distance calculated from not-selected vertex to nearest selected vertex
202  * warning; this is loops inside loop, has minor N^2 issues, but by sorting list it is OK */
203 static void set_prop_dist(TransInfo *t, const bool with_dist)
204 {
205         TransData *tob;
206         int a;
207
208         float _proj_vec[3];
209         const float *proj_vec = NULL;
210
211         if (t->flag & T_PROP_PROJECTED) {
212                 if (t->spacetype == SPACE_VIEW3D && t->ar && t->ar->regiontype == RGN_TYPE_WINDOW) {
213                         RegionView3D *rv3d = t->ar->regiondata;
214                         normalize_v3_v3(_proj_vec, rv3d->viewinv[2]);
215                         proj_vec = _proj_vec;
216                 }
217         }
218
219         for (a = 0, tob = t->data; a < t->total; a++, tob++) {
220
221                 tob->rdist = 0.0f; // init, it was mallocced
222
223                 if ((tob->flag & TD_SELECTED) == 0) {
224                         TransData *td;
225                         int i;
226                         float dist, vec[3];
227
228                         tob->rdist = -1.0f; // signal for next loop
229
230                         for (i = 0, td = t->data; i < t->total; i++, td++) {
231                                 if (td->flag & TD_SELECTED) {
232                                         sub_v3_v3v3(vec, tob->center, td->center);
233                                         mul_m3_v3(tob->mtx, vec);
234
235                                         if (proj_vec) {
236                                                 float vec_p[3];
237                                                 project_v3_v3v3(vec_p, vec, proj_vec);
238                                                 sub_v3_v3(vec, vec_p);
239                                         }
240
241                                         dist = len_squared_v3(vec);
242                                         if ((tob->rdist == -1.0f) || (dist < (tob->rdist * tob->rdist))) {
243                                                 tob->rdist = sqrtf(dist);
244                                         }
245                                 }
246                                 else {
247                                         break;  /* by definition transdata has selected items in beginning */
248                                 }
249                         }
250                         if (with_dist) {
251                                 tob->dist = tob->rdist;
252                         }
253                 }
254         }
255 }
256
257 /* ************************** CONVERSIONS ************************* */
258
259 /* ********************* texture space ********* */
260
261 static void createTransTexspace(TransInfo *t)
262 {
263         Scene *scene = t->scene;
264         TransData *td;
265         Object *ob;
266         ID *id;
267         short *texflag;
268
269         ob = OBACT;
270
271         if (ob == NULL) { // Shouldn't logically happen, but still...
272                 t->total = 0;
273                 return;
274         }
275
276         id = ob->data;
277         if (id == NULL || !ELEM3(GS(id->name), ID_ME, ID_CU, ID_MB)) {
278                 t->total = 0;
279                 return;
280         }
281
282         t->total = 1;
283         td = t->data = MEM_callocN(sizeof(TransData), "TransTexspace");
284         td->ext = t->ext = MEM_callocN(sizeof(TransDataExtension), "TransTexspace");
285
286         td->flag = TD_SELECTED;
287         copy_v3_v3(td->center, ob->obmat[3]);
288         td->ob = ob;
289
290         copy_m3_m4(td->mtx, ob->obmat);
291         copy_m3_m4(td->axismtx, ob->obmat);
292         normalize_m3(td->axismtx);
293         pseudoinverse_m3_m3(td->smtx, td->mtx, PSEUDOINVERSE_EPSILON);
294
295         if (BKE_object_obdata_texspace_get(ob, &texflag, &td->loc, &td->ext->size, &td->ext->rot)) {
296                 ob->dtx |= OB_TEXSPACE;
297                 *texflag &= ~ME_AUTOSPACE;
298         }
299
300         copy_v3_v3(td->iloc, td->loc);
301         copy_v3_v3(td->ext->irot, td->ext->rot);
302         copy_v3_v3(td->ext->isize, td->ext->size);
303 }
304
305 /* ********************* edge (for crease) ***** */
306
307 static void createTransEdge(TransInfo *t)
308 {
309         BMEditMesh *em = BKE_editmesh_from_object(t->obedit);
310         TransData *td = NULL;
311         BMEdge *eed;
312         BMIter iter;
313         float mtx[3][3], smtx[3][3];
314         int count = 0, countsel = 0;
315         int propmode = t->flag & T_PROP_EDIT;
316         int cd_edge_float_offset;
317
318         BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
319                 if (!BM_elem_flag_test(eed, BM_ELEM_HIDDEN)) {
320                         if (BM_elem_flag_test(eed, BM_ELEM_SELECT)) countsel++;
321                         if (propmode) count++;
322                 }
323         }
324
325         if (countsel == 0)
326                 return;
327
328         if (propmode) {
329                 t->total = count;
330         }
331         else {
332                 t->total = countsel;
333         }
334
335         td = t->data = MEM_callocN(t->total * sizeof(TransData), "TransCrease");
336
337         copy_m3_m4(mtx, t->obedit->obmat);
338         pseudoinverse_m3_m3(smtx, mtx, PSEUDOINVERSE_EPSILON);
339
340         /* create data we need */
341         if (t->mode == TFM_BWEIGHT) {
342                 BM_mesh_cd_flag_ensure(em->bm, BKE_mesh_from_object(t->obedit), ME_CDFLAG_EDGE_BWEIGHT);
343                 cd_edge_float_offset = CustomData_get_offset(&em->bm->edata, CD_BWEIGHT);
344         }
345         else { //if (t->mode == TFM_CREASE) {
346                 BLI_assert(t->mode == TFM_CREASE);
347                 BM_mesh_cd_flag_ensure(em->bm, BKE_mesh_from_object(t->obedit), ME_CDFLAG_EDGE_CREASE);
348                 cd_edge_float_offset = CustomData_get_offset(&em->bm->edata, CD_CREASE);
349         }
350
351         BLI_assert(cd_edge_float_offset != -1);
352
353         BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
354                 if (!BM_elem_flag_test(eed, BM_ELEM_HIDDEN) && (BM_elem_flag_test(eed, BM_ELEM_SELECT) || propmode)) {
355                         float *fl_ptr;
356                         /* need to set center for center calculations */
357                         mid_v3_v3v3(td->center, eed->v1->co, eed->v2->co);
358
359                         td->loc = NULL;
360                         if (BM_elem_flag_test(eed, BM_ELEM_SELECT))
361                                 td->flag = TD_SELECTED;
362                         else
363                                 td->flag = 0;
364
365                         copy_m3_m3(td->smtx, smtx);
366                         copy_m3_m3(td->mtx, mtx);
367
368                         td->ext = NULL;
369
370                         fl_ptr = BM_ELEM_CD_GET_VOID_P(eed, cd_edge_float_offset);
371                         td->val  =  fl_ptr;
372                         td->ival = *fl_ptr;
373
374                         td++;
375                 }
376         }
377 }
378
379 /* ********************* pose mode ************* */
380
381 static bKinematicConstraint *has_targetless_ik(bPoseChannel *pchan)
382 {
383         bConstraint *con = pchan->constraints.first;
384
385         for (; con; con = con->next) {
386                 if (con->type == CONSTRAINT_TYPE_KINEMATIC && (con->enforce != 0.0f)) {
387                         bKinematicConstraint *data = con->data;
388
389                         if (data->tar == NULL)
390                                 return data;
391                         if (data->tar->type == OB_ARMATURE && data->subtarget[0] == 0)
392                                 return data;
393                 }
394         }
395         return NULL;
396 }
397
398 static short apply_targetless_ik(Object *ob)
399 {
400         bPoseChannel *pchan, *parchan, *chanlist[256];
401         bKinematicConstraint *data;
402         int segcount, apply = 0;
403
404         /* now we got a difficult situation... we have to find the
405          * target-less IK pchans, and apply transformation to the all
406          * pchans that were in the chain */
407
408         for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) {
409                 data = has_targetless_ik(pchan);
410                 if (data && (data->flag & CONSTRAINT_IK_AUTO)) {
411
412                         /* fill the array with the bones of the chain (armature.c does same, keep it synced) */
413                         segcount = 0;
414
415                         /* exclude tip from chain? */
416                         if (!(data->flag & CONSTRAINT_IK_TIP))
417                                 parchan = pchan->parent;
418                         else
419                                 parchan = pchan;
420
421                         /* Find the chain's root & count the segments needed */
422                         for (; parchan; parchan = parchan->parent) {
423                                 chanlist[segcount] = parchan;
424                                 segcount++;
425
426                                 if (segcount == data->rootbone || segcount > 255) break;  // 255 is weak
427                         }
428                         for (; segcount; segcount--) {
429                                 Bone *bone;
430                                 float rmat[4][4] /*, tmat[4][4], imat[4][4]*/;
431
432                                 /* pose_mat(b) = pose_mat(b-1) * offs_bone * channel * constraint * IK  */
433                                 /* we put in channel the entire result of rmat = (channel * constraint * IK) */
434                                 /* pose_mat(b) = pose_mat(b-1) * offs_bone * rmat  */
435                                 /* rmat = pose_mat(b) * inv(pose_mat(b-1) * offs_bone ) */
436
437                                 parchan = chanlist[segcount - 1];
438                                 bone = parchan->bone;
439                                 bone->flag |= BONE_TRANSFORM;   /* ensures it gets an auto key inserted */
440
441                                 BKE_armature_mat_pose_to_bone(parchan, parchan->pose_mat, rmat);
442
443                                 /* apply and decompose, doesn't work for constraints or non-uniform scale well */
444                                 {
445                                         float rmat3[3][3], qrmat[3][3], imat3[3][3], smat[3][3];
446                                         
447                                         copy_m3_m4(rmat3, rmat);
448                                         
449                                         /* rotation */
450                                         /* [#22409] is partially caused by this, as slight numeric error introduced during
451                                          * the solving process leads to locked-axis values changing. However, we cannot modify
452                                          * the values here, or else there are huge discrepancies between IK-solver (interactive)
453                                          * and applied poses.
454                                          */
455                                         if (parchan->rotmode > 0)
456                                                 mat3_to_eulO(parchan->eul, parchan->rotmode, rmat3);
457                                         else if (parchan->rotmode == ROT_MODE_AXISANGLE)
458                                                 mat3_to_axis_angle(parchan->rotAxis, &parchan->rotAngle, rmat3);
459                                         else
460                                                 mat3_to_quat(parchan->quat, rmat3);
461                                         
462                                         /* for size, remove rotation */
463                                         /* causes problems with some constraints (so apply only if needed) */
464                                         if (data->flag & CONSTRAINT_IK_STRETCH) {
465                                                 if (parchan->rotmode > 0)
466                                                         eulO_to_mat3(qrmat, parchan->eul, parchan->rotmode);
467                                                 else if (parchan->rotmode == ROT_MODE_AXISANGLE)
468                                                         axis_angle_to_mat3(qrmat, parchan->rotAxis, parchan->rotAngle);
469                                                 else
470                                                         quat_to_mat3(qrmat, parchan->quat);
471                                                 
472                                                 invert_m3_m3(imat3, qrmat);
473                                                 mul_m3_m3m3(smat, rmat3, imat3);
474                                                 mat3_to_size(parchan->size, smat);
475                                         }
476                                         
477                                         /* causes problems with some constraints (e.g. childof), so disable this */
478                                         /* as it is IK shouldn't affect location directly */
479                                         /* copy_v3_v3(parchan->loc, rmat[3]); */
480                                 }
481
482                         }
483
484                         apply = 1;
485                         data->flag &= ~CONSTRAINT_IK_AUTO;
486                 }
487         }
488
489         return apply;
490 }
491
492 static void add_pose_transdata(TransInfo *t, bPoseChannel *pchan, Object *ob, TransData *td)
493 {
494         Bone *bone = pchan->bone;
495         float pmat[3][3], omat[3][3];
496         float cmat[3][3], tmat[3][3];
497         float vec[3];
498
499         copy_v3_v3(vec, pchan->pose_mat[3]);
500         copy_v3_v3(td->center, vec);
501
502         td->ob = ob;
503         td->flag = TD_SELECTED;
504         if (bone->flag & BONE_HINGE_CHILD_TRANSFORM) {
505                 td->flag |= TD_NOCENTER;
506         }
507
508         if (bone->flag & BONE_TRANSFORM_CHILD) {
509                 td->flag |= TD_NOCENTER;
510                 td->flag |= TD_NO_LOC;
511         }
512
513         td->protectflag = pchan->protectflag;
514
515         td->loc = pchan->loc;
516         copy_v3_v3(td->iloc, pchan->loc);
517
518         td->ext->size = pchan->size;
519         copy_v3_v3(td->ext->isize, pchan->size);
520
521         if (pchan->rotmode > 0) {
522                 td->ext->rot = pchan->eul;
523                 td->ext->rotAxis = NULL;
524                 td->ext->rotAngle = NULL;
525                 td->ext->quat = NULL;
526                 
527                 copy_v3_v3(td->ext->irot, pchan->eul);
528         }
529         else if (pchan->rotmode == ROT_MODE_AXISANGLE) {
530                 td->ext->rot = NULL;
531                 td->ext->rotAxis = pchan->rotAxis;
532                 td->ext->rotAngle = &pchan->rotAngle;
533                 td->ext->quat = NULL;
534                 
535                 td->ext->irotAngle = pchan->rotAngle;
536                 copy_v3_v3(td->ext->irotAxis, pchan->rotAxis);
537         }
538         else {
539                 td->ext->rot = NULL;
540                 td->ext->rotAxis = NULL;
541                 td->ext->rotAngle = NULL;
542                 td->ext->quat = pchan->quat;
543                 
544                 copy_qt_qt(td->ext->iquat, pchan->quat);
545         }
546         td->ext->rotOrder = pchan->rotmode;
547
548
549         /* proper way to get parent transform + own transform + constraints transform */
550         copy_m3_m4(omat, ob->obmat);
551
552         /* New code, using "generic" BKE_pchan_to_pose_mat(). */
553         {
554                 float rotscale_mat[4][4], loc_mat[4][4];
555                 float rpmat[3][3];
556
557                 BKE_pchan_to_pose_mat(pchan, rotscale_mat, loc_mat);
558                 if (t->mode == TFM_TRANSLATION)
559                         copy_m3_m4(pmat, loc_mat);
560                 else
561                         copy_m3_m4(pmat, rotscale_mat);
562
563                 /* Grrr! Exceptional case: When translating pose bones that are either Hinge or NoLocal,
564                  * and want align snapping, we just need both loc_mat and rotscale_mat.
565                  * So simply always store rotscale mat in td->ext, and always use it to apply rotations...
566                  * Ugly to need such hacks! :/ */
567                 copy_m3_m4(rpmat, rotscale_mat);
568
569                 if (constraints_list_needinv(t, &pchan->constraints)) {
570                         copy_m3_m4(tmat, pchan->constinv);
571                         invert_m3_m3(cmat, tmat);
572                         mul_serie_m3(td->mtx, pmat, omat, cmat, NULL, NULL, NULL, NULL, NULL);
573                         mul_serie_m3(td->ext->r_mtx, rpmat, omat, cmat, NULL, NULL, NULL, NULL, NULL);
574                 }
575                 else {
576                         mul_serie_m3(td->mtx, pmat, omat, NULL, NULL, NULL, NULL, NULL, NULL);
577                         mul_serie_m3(td->ext->r_mtx, rpmat, omat, NULL, NULL, NULL, NULL, NULL, NULL);
578                 }
579                 invert_m3_m3(td->ext->r_smtx, td->ext->r_mtx);
580         }
581
582         pseudoinverse_m3_m3(td->smtx, td->mtx, PSEUDOINVERSE_EPSILON);
583
584         /* exceptional case: rotate the pose bone which also applies transformation
585          * when a parentless bone has BONE_NO_LOCAL_LOCATION [] */
586         if (!ELEM(t->mode, TFM_TRANSLATION, TFM_RESIZE) && (pchan->bone->flag & BONE_NO_LOCAL_LOCATION)) {
587                 if (pchan->parent) {
588                         /* same as td->smtx but without pchan->bone->bone_mat */
589                         td->flag |= TD_PBONE_LOCAL_MTX_C;
590                         mul_m3_m3m3(td->ext->l_smtx, pchan->bone->bone_mat, td->smtx);
591                 }
592                 else {
593                         td->flag |= TD_PBONE_LOCAL_MTX_P;
594                 }
595         }
596         
597         /* for axismat we use bone's own transform */
598         copy_m3_m4(pmat, pchan->pose_mat);
599         mul_m3_m3m3(td->axismtx, omat, pmat);
600         normalize_m3(td->axismtx);
601
602         if (t->mode == TFM_BONESIZE) {
603                 bArmature *arm = t->poseobj->data;
604
605                 if (arm->drawtype == ARM_ENVELOPE) {
606                         td->loc = NULL;
607                         td->val = &bone->dist;
608                         td->ival = bone->dist;
609                 }
610                 else {
611                         // abusive storage of scale in the loc pointer :)
612                         td->loc = &bone->xwidth;
613                         copy_v3_v3(td->iloc, td->loc);
614                         td->val = NULL;
615                 }
616         }
617
618         /* in this case we can do target-less IK grabbing */
619         if (t->mode == TFM_TRANSLATION) {
620                 bKinematicConstraint *data = has_targetless_ik(pchan);
621                 if (data) {
622                         if (data->flag & CONSTRAINT_IK_TIP) {
623                                 copy_v3_v3(data->grabtarget, pchan->pose_tail);
624                         }
625                         else {
626                                 copy_v3_v3(data->grabtarget, pchan->pose_head);
627                         }
628                         td->loc = data->grabtarget;
629                         copy_v3_v3(td->iloc, td->loc);
630                         data->flag |= CONSTRAINT_IK_AUTO;
631
632                         /* only object matrix correction */
633                         copy_m3_m3(td->mtx, omat);
634                         pseudoinverse_m3_m3(td->smtx, td->mtx, PSEUDOINVERSE_EPSILON);
635                 }
636         }
637
638         /* store reference to first constraint */
639         td->con = pchan->constraints.first;
640 }
641
642 static void bone_children_clear_transflag(int mode, short around, ListBase *lb)
643 {
644         Bone *bone = lb->first;
645
646         for (; bone; bone = bone->next) {
647                 if ((bone->flag & BONE_HINGE) && (bone->flag & BONE_CONNECTED)) {
648                         bone->flag |= BONE_HINGE_CHILD_TRANSFORM;
649                 }
650                 else if ((bone->flag & BONE_TRANSFORM) &&
651                          (mode == TFM_ROTATION || mode == TFM_TRACKBALL) &&
652                          (around == V3D_LOCAL))
653                 {
654                         bone->flag |= BONE_TRANSFORM_CHILD;
655                 }
656                 else {
657                         bone->flag &= ~BONE_TRANSFORM;
658                 }
659
660                 bone_children_clear_transflag(mode, around, &bone->childbase);
661         }
662 }
663
664 /* sets transform flags in the bones
665  * returns total number of bones with BONE_TRANSFORM */
666 int count_set_pose_transflags(int *out_mode, short around, Object *ob)
667 {
668         bArmature *arm = ob->data;
669         bPoseChannel *pchan;
670         Bone *bone;
671         int mode = *out_mode;
672         int hastranslation = 0;
673         int total = 0;
674
675         for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) {
676                 bone = pchan->bone;
677                 if (PBONE_VISIBLE(arm, bone)) {
678                         if ((bone->flag & BONE_SELECTED))
679                                 bone->flag |= BONE_TRANSFORM;
680                         else
681                                 bone->flag &= ~BONE_TRANSFORM;
682                         
683                         bone->flag &= ~BONE_HINGE_CHILD_TRANSFORM;
684                         bone->flag &= ~BONE_TRANSFORM_CHILD;
685                 }
686                 else
687                         bone->flag &= ~BONE_TRANSFORM;
688         }
689
690         /* make sure no bone can be transformed when a parent is transformed */
691         /* since pchans are depsgraph sorted, the parents are in beginning of list */
692         if (mode != TFM_BONESIZE) {
693                 for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) {
694                         bone = pchan->bone;
695                         if (bone->flag & BONE_TRANSFORM)
696                                 bone_children_clear_transflag(mode, around, &bone->childbase);
697                 }
698         }
699         /* now count, and check if we have autoIK or have to switch from translate to rotate */
700         hastranslation = 0;
701
702         for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) {
703                 bone = pchan->bone;
704                 if (bone->flag & BONE_TRANSFORM) {
705                         total++;
706                         
707                         if (mode == TFM_TRANSLATION) {
708                                 if (has_targetless_ik(pchan) == NULL) {
709                                         if (pchan->parent && (pchan->bone->flag & BONE_CONNECTED)) {
710                                                 if (pchan->bone->flag & BONE_HINGE_CHILD_TRANSFORM)
711                                                         hastranslation = 1;
712                                         }
713                                         else if ((pchan->protectflag & OB_LOCK_LOC) != OB_LOCK_LOC)
714                                                 hastranslation = 1;
715                                 }
716                                 else
717                                         hastranslation = 1;
718                         }
719                 }
720         }
721
722         /* if there are no translatable bones, do rotation */
723         if (mode == TFM_TRANSLATION && !hastranslation) {
724                 *out_mode = TFM_ROTATION;
725         }
726
727         return total;
728 }
729
730
731 /* -------- Auto-IK ---------- */
732
733 /* adjust pose-channel's auto-ik chainlen */
734 static void pchan_autoik_adjust(bPoseChannel *pchan, short chainlen)
735 {
736         bConstraint *con;
737
738         /* don't bother to search if no valid constraints */
739         if ((pchan->constflag & (PCHAN_HAS_IK | PCHAN_HAS_TARGET)) == 0)
740                 return;
741
742         /* check if pchan has ik-constraint */
743         for (con = pchan->constraints.first; con; con = con->next) {
744                 if (con->type == CONSTRAINT_TYPE_KINEMATIC && (con->enforce != 0.0f)) {
745                         bKinematicConstraint *data = con->data;
746                         
747                         /* only accept if a temporary one (for auto-ik) */
748                         if (data->flag & CONSTRAINT_IK_TEMP) {
749                                 /* chainlen is new chainlen, but is limited by maximum chainlen */
750                                 if ((chainlen == 0) || (chainlen > data->max_rootbone))
751                                         data->rootbone = data->max_rootbone;
752                                 else
753                                         data->rootbone = chainlen;
754                         }
755                 }
756         }
757 }
758
759 /* change the chain-length of auto-ik */
760 void transform_autoik_update(TransInfo *t, short mode)
761 {
762         short *chainlen = &t->settings->autoik_chainlen;
763         bPoseChannel *pchan;
764
765         /* mode determines what change to apply to chainlen */
766         if (mode == 1) {
767                 /* mode=1 is from WHEELMOUSEDOWN... increases len */
768                 (*chainlen)++;
769         }
770         else if (mode == -1) {
771                 /* mode==-1 is from WHEELMOUSEUP... decreases len */
772                 if (*chainlen > 0) (*chainlen)--;
773         }
774
775         /* sanity checks (don't assume t->poseobj is set, or that it is an armature) */
776         if (ELEM(NULL, t->poseobj, t->poseobj->pose))
777                 return;
778
779         /* apply to all pose-channels */
780         for (pchan = t->poseobj->pose->chanbase.first; pchan; pchan = pchan->next) {
781                 pchan_autoik_adjust(pchan, *chainlen);
782         }
783 }
784
785 /* frees temporal IKs */
786 static void pose_grab_with_ik_clear(Object *ob)
787 {
788         bKinematicConstraint *data;
789         bPoseChannel *pchan;
790         bConstraint *con, *next;
791
792         for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) {
793                 /* clear all temporary lock flags */
794                 pchan->ikflag &= ~(BONE_IK_NO_XDOF_TEMP | BONE_IK_NO_YDOF_TEMP | BONE_IK_NO_ZDOF_TEMP);
795                 
796                 pchan->constflag &= ~(PCHAN_HAS_IK | PCHAN_HAS_TARGET);
797                 
798                 /* remove all temporary IK-constraints added */
799                 for (con = pchan->constraints.first; con; con = next) {
800                         next = con->next;
801                         if (con->type == CONSTRAINT_TYPE_KINEMATIC) {
802                                 data = con->data;
803                                 if (data->flag & CONSTRAINT_IK_TEMP) {
804                                         /* iTaSC needs clear for removed constraints */
805                                         BIK_clear_data(ob->pose);
806
807                                         BLI_remlink(&pchan->constraints, con);
808                                         MEM_freeN(con->data);
809                                         MEM_freeN(con);
810                                         continue;
811                                 }
812                                 pchan->constflag |= PCHAN_HAS_IK;
813                                 if (data->tar == NULL || (data->tar->type == OB_ARMATURE && data->subtarget[0] == 0))
814                                         pchan->constflag |= PCHAN_HAS_TARGET;
815                         }
816                 }
817         }
818 }
819
820 /* adds the IK to pchan - returns if added */
821 static short pose_grab_with_ik_add(bPoseChannel *pchan)
822 {
823         bKinematicConstraint *targetless = NULL;
824         bKinematicConstraint *data;
825         bConstraint *con;
826
827         /* Sanity check */
828         if (pchan == NULL)
829                 return 0;
830
831         /* Rule: not if there's already an IK on this channel */
832         for (con = pchan->constraints.first; con; con = con->next) {
833                 if (con->type == CONSTRAINT_TYPE_KINEMATIC) {
834                         data = con->data;
835                         
836                         if (data->tar == NULL || (data->tar->type == OB_ARMATURE && data->subtarget[0] == '\0')) {
837                                 /* make reference to constraint to base things off later (if it's the last targetless constraint encountered) */
838                                 targetless = (bKinematicConstraint *)con->data;
839                                 
840                                 /* but, if this is a targetless IK, we make it auto anyway (for the children loop) */
841                                 if (con->enforce != 0.0f) {
842                                         data->flag |= CONSTRAINT_IK_AUTO;
843                                         
844                                         /* if no chain length has been specified, just make things obey standard rotation locks too */
845                                         if (data->rootbone == 0) {
846                                                 for (; pchan; pchan = pchan->parent) {
847                                                         /* here, we set ik-settings for bone from pchan->protectflag */
848                                                         // XXX: careful with quats/axis-angle rotations where we're locking 4d components
849                                                         if (pchan->protectflag & OB_LOCK_ROTX) pchan->ikflag |= BONE_IK_NO_XDOF_TEMP;
850                                                         if (pchan->protectflag & OB_LOCK_ROTY) pchan->ikflag |= BONE_IK_NO_YDOF_TEMP;
851                                                         if (pchan->protectflag & OB_LOCK_ROTZ) pchan->ikflag |= BONE_IK_NO_ZDOF_TEMP;
852                                                 }
853                                         }
854                                         
855                                         return 0; 
856                                 }
857                         }
858                         
859                         if ((con->flag & CONSTRAINT_DISABLE) == 0 && (con->enforce != 0.0f))
860                                 return 0;
861                 }
862         }
863
864         con = BKE_add_pose_constraint(NULL, pchan, "TempConstraint", CONSTRAINT_TYPE_KINEMATIC);
865         pchan->constflag |= (PCHAN_HAS_IK | PCHAN_HAS_TARGET);    /* for draw, but also for detecting while pose solving */
866         data = con->data;
867         if (targetless) {
868                 /* if exists, use values from last targetless (but disabled) IK-constraint as base */
869                 *data = *targetless;
870         }
871         else
872                 data->flag = CONSTRAINT_IK_TIP;
873         data->flag |= CONSTRAINT_IK_TEMP | CONSTRAINT_IK_AUTO | CONSTRAINT_IK_POS;
874         copy_v3_v3(data->grabtarget, pchan->pose_tail);
875         data->rootbone = 0; /* watch-it! has to be 0 here, since we're still on the same bone for the first time through the loop [#25885] */
876         
877         /* we only include bones that are part of a continual connected chain */
878         do {
879                 /* here, we set ik-settings for bone from pchan->protectflag */
880                 // XXX: careful with quats/axis-angle rotations where we're locking 4d components
881                 if (pchan->protectflag & OB_LOCK_ROTX) pchan->ikflag |= BONE_IK_NO_XDOF_TEMP;
882                 if (pchan->protectflag & OB_LOCK_ROTY) pchan->ikflag |= BONE_IK_NO_YDOF_TEMP;
883                 if (pchan->protectflag & OB_LOCK_ROTZ) pchan->ikflag |= BONE_IK_NO_ZDOF_TEMP;
884                 
885                 /* now we count this pchan as being included */
886                 data->rootbone++;
887                 
888                 /* continue to parent, but only if we're connected to it */
889                 if (pchan->bone->flag & BONE_CONNECTED)
890                         pchan = pchan->parent;
891                 else
892                         pchan = NULL;
893         } while (pchan);
894
895         /* make a copy of maximum chain-length */
896         data->max_rootbone = data->rootbone;
897
898         return 1;
899 }
900
901 /* bone is a candidate to get IK, but we don't do it if it has children connected */
902 static short pose_grab_with_ik_children(bPose *pose, Bone *bone)
903 {
904         Bone *bonec;
905         short wentdeeper = 0, added = 0;
906
907         /* go deeper if children & children are connected */
908         for (bonec = bone->childbase.first; bonec; bonec = bonec->next) {
909                 if (bonec->flag & BONE_CONNECTED) {
910                         wentdeeper = 1;
911                         added += pose_grab_with_ik_children(pose, bonec);
912                 }
913         }
914         if (wentdeeper == 0) {
915                 bPoseChannel *pchan = BKE_pose_channel_find_name(pose, bone->name);
916                 if (pchan)
917                         added += pose_grab_with_ik_add(pchan);
918         }
919
920         return added;
921 }
922
923 /* main call which adds temporal IK chains */
924 static short pose_grab_with_ik(Object *ob)
925 {
926         bArmature *arm;
927         bPoseChannel *pchan, *parent;
928         Bone *bonec;
929         short tot_ik = 0;
930
931         if ((ob == NULL) || (ob->pose == NULL) || (ob->mode & OB_MODE_POSE) == 0)
932                 return 0;
933
934         arm = ob->data;
935
936         /* Rule: allow multiple Bones (but they must be selected, and only one ik-solver per chain should get added) */
937         for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) {
938                 if (pchan->bone->layer & arm->layer) {
939                         if (pchan->bone->flag & BONE_SELECTED) {
940                                 /* Rule: no IK for solitatry (unconnected) bones */
941                                 for (bonec = pchan->bone->childbase.first; bonec; bonec = bonec->next) {
942                                         if (bonec->flag & BONE_CONNECTED) {
943                                                 break;
944                                         }
945                                 }
946                                 if ((pchan->bone->flag & BONE_CONNECTED) == 0 && (bonec == NULL))
947                                         continue;
948
949                                 /* rule: if selected Bone is not a root bone, it gets a temporal IK */
950                                 if (pchan->parent) {
951                                         /* only adds if there's no IK yet (and no parent bone was selected) */
952                                         for (parent = pchan->parent; parent; parent = parent->parent) {
953                                                 if (parent->bone->flag & BONE_SELECTED)
954                                                         break;
955                                         }
956                                         if (parent == NULL)
957                                                 tot_ik += pose_grab_with_ik_add(pchan);
958                                 }
959                                 else {
960                                         /* rule: go over the children and add IK to the tips */
961                                         tot_ik += pose_grab_with_ik_children(ob->pose, pchan->bone);
962                                 }
963                         }
964                 }
965         }
966
967         /* iTaSC needs clear for new IK constraints */
968         if (tot_ik)
969                 BIK_clear_data(ob->pose);
970
971         return (tot_ik) ? 1 : 0;
972 }
973
974
975 /* only called with pose mode active object now */
976 static void createTransPose(TransInfo *t, Object *ob)
977 {
978         bArmature *arm;
979         bPoseChannel *pchan;
980         TransData *td;
981         TransDataExtension *tdx;
982         short ik_on = 0;
983         int i;
984
985         t->total = 0;
986
987         /* check validity of state */
988         arm = BKE_armature_from_object(ob);
989         if ((arm == NULL) || (ob->pose == NULL)) return;
990
991         if (arm->flag & ARM_RESTPOS) {
992                 if (ELEM(t->mode, TFM_DUMMY, TFM_BONESIZE) == 0) {
993                         // XXX use transform operator reports
994                         // BKE_report(op->reports, RPT_ERROR, "Cannot select linked when sync selection is enabled");
995                         return;
996                 }
997         }
998
999         /* do we need to add temporal IK chains? */
1000         if ((arm->flag & ARM_AUTO_IK) && t->mode == TFM_TRANSLATION) {
1001                 ik_on = pose_grab_with_ik(ob);
1002                 if (ik_on) t->flag |= T_AUTOIK;
1003         }
1004
1005         /* set flags and count total (warning, can change transform to rotate) */
1006         t->total = count_set_pose_transflags(&t->mode, t->around, ob);
1007
1008         if (t->total == 0) return;
1009
1010         t->flag |= T_POSE;
1011         t->poseobj = ob; /* we also allow non-active objects to be transformed, in weightpaint */
1012
1013         /* disable PET, its not usable in pose mode yet [#32444] */
1014         t->flag &= ~T_PROP_EDIT_ALL;
1015
1016         /* init trans data */
1017         td = t->data = MEM_callocN(t->total * sizeof(TransData), "TransPoseBone");
1018         tdx = t->ext = MEM_callocN(t->total * sizeof(TransDataExtension), "TransPoseBoneExt");
1019         for (i = 0; i < t->total; i++, td++, tdx++) {
1020                 td->ext = tdx;
1021                 td->val = NULL;
1022         }
1023
1024         /* use pose channels to fill trans data */
1025         td = t->data;
1026         for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) {
1027                 if (pchan->bone->flag & BONE_TRANSFORM) {
1028                         add_pose_transdata(t, pchan, ob, td);
1029                         td++;
1030                 }
1031         }
1032
1033         if (td != (t->data + t->total)) {
1034                 // XXX use transform operator reports
1035                 // BKE_report(op->reports, RPT_DEBUG, "Bone selection count error");
1036         }
1037
1038         /* initialize initial auto=ik chainlen's? */
1039         if (ik_on) transform_autoik_update(t, 0);
1040 }
1041
1042 /* ********************* armature ************** */
1043
1044 static void createTransArmatureVerts(TransInfo *t)
1045 {
1046         EditBone *ebo;
1047         bArmature *arm = t->obedit->data;
1048         ListBase *edbo = arm->edbo;
1049         TransData *td;
1050         float mtx[3][3], smtx[3][3], bonemat[3][3];
1051         
1052         /* special hack for envelope drawmode and scaling:
1053          *  to allow scaling the size of the envelope around single points,
1054          *      mode should become TFM_BONE_ENVELOPE in this case
1055          */
1056         // TODO: maybe we need a separate hotkey for it, but this is consistent with 2.4x for now
1057         if ((t->mode == TFM_RESIZE) && (arm->drawtype == ARM_ENVELOPE))
1058                 t->mode = TFM_BONE_ENVELOPE;
1059         
1060         t->total = 0;
1061         for (ebo = edbo->first; ebo; ebo = ebo->next) {
1062                 if (EBONE_VISIBLE(arm, ebo) && !(ebo->flag & BONE_EDITMODE_LOCKED)) {
1063                         if (t->mode == TFM_BONESIZE) {
1064                                 if (ebo->flag & BONE_SELECTED)
1065                                         t->total++;
1066                         }
1067                         else if (t->mode == TFM_BONE_ROLL) {
1068                                 if (ebo->flag & BONE_SELECTED)
1069                                         t->total++;
1070                         }
1071                         else {
1072                                 if (ebo->flag & BONE_TIPSEL)
1073                                         t->total++;
1074                                 if (ebo->flag & BONE_ROOTSEL)
1075                                         t->total++;
1076                         }
1077                 }
1078         }
1079
1080         if (!t->total) return;
1081
1082         copy_m3_m4(mtx, t->obedit->obmat);
1083         pseudoinverse_m3_m3(smtx, mtx, PSEUDOINVERSE_EPSILON);
1084
1085         td = t->data = MEM_callocN(t->total * sizeof(TransData), "TransEditBone");
1086
1087         for (ebo = edbo->first; ebo; ebo = ebo->next) {
1088                 ebo->oldlength = ebo->length;   // length==0.0 on extrude, used for scaling radius of bone points
1089
1090                 if (EBONE_VISIBLE(arm, ebo) && !(ebo->flag & BONE_EDITMODE_LOCKED)) {
1091                         if (t->mode == TFM_BONE_ENVELOPE) {
1092                                 if (ebo->flag & BONE_ROOTSEL) {
1093                                         td->val = &ebo->rad_head;
1094                                         td->ival = *td->val;
1095
1096                                         copy_v3_v3(td->center, ebo->head);
1097                                         td->flag = TD_SELECTED;
1098
1099                                         copy_m3_m3(td->smtx, smtx);
1100                                         copy_m3_m3(td->mtx, mtx);
1101
1102                                         td->loc = NULL;
1103                                         td->ext = NULL;
1104                                         td->ob = t->obedit;
1105
1106                                         td++;
1107                                 }
1108                                 if (ebo->flag & BONE_TIPSEL) {
1109                                         td->val = &ebo->rad_tail;
1110                                         td->ival = *td->val;
1111                                         copy_v3_v3(td->center, ebo->tail);
1112                                         td->flag = TD_SELECTED;
1113
1114                                         copy_m3_m3(td->smtx, smtx);
1115                                         copy_m3_m3(td->mtx, mtx);
1116
1117                                         td->loc = NULL;
1118                                         td->ext = NULL;
1119                                         td->ob = t->obedit;
1120
1121                                         td++;
1122                                 }
1123
1124                         }
1125                         else if (t->mode == TFM_BONESIZE) {
1126                                 if (ebo->flag & BONE_SELECTED) {
1127                                         if (arm->drawtype == ARM_ENVELOPE) {
1128                                                 td->loc = NULL;
1129                                                 td->val = &ebo->dist;
1130                                                 td->ival = ebo->dist;
1131                                         }
1132                                         else {
1133                                                 // abusive storage of scale in the loc pointer :)
1134                                                 td->loc = &ebo->xwidth;
1135                                                 copy_v3_v3(td->iloc, td->loc);
1136                                                 td->val = NULL;
1137                                         }
1138                                         copy_v3_v3(td->center, ebo->head);
1139                                         td->flag = TD_SELECTED;
1140
1141                                         /* use local bone matrix */
1142                                         ED_armature_ebone_to_mat3(ebo, bonemat);
1143                                         mul_m3_m3m3(td->mtx, mtx, bonemat);
1144                                         invert_m3_m3(td->smtx, td->mtx);
1145
1146                                         copy_m3_m3(td->axismtx, td->mtx);
1147                                         normalize_m3(td->axismtx);
1148
1149                                         td->ext = NULL;
1150                                         td->ob = t->obedit;
1151
1152                                         td++;
1153                                 }
1154                         }
1155                         else if (t->mode == TFM_BONE_ROLL) {
1156                                 if (ebo->flag & BONE_SELECTED) {
1157                                         td->loc = NULL;
1158                                         td->val = &(ebo->roll);
1159                                         td->ival = ebo->roll;
1160
1161                                         copy_v3_v3(td->center, ebo->head);
1162                                         td->flag = TD_SELECTED;
1163
1164                                         td->ext = NULL;
1165                                         td->ob = t->obedit;
1166
1167                                         td++;
1168                                 }
1169                         }
1170                         else {
1171                                 if (ebo->flag & BONE_TIPSEL) {
1172                                         copy_v3_v3(td->iloc, ebo->tail);
1173                                         copy_v3_v3(td->center, (t->around == V3D_LOCAL) ? ebo->head : td->iloc);
1174                                         td->loc = ebo->tail;
1175                                         td->flag = TD_SELECTED;
1176                                         if (ebo->flag & BONE_EDITMODE_LOCKED)
1177                                                 td->protectflag = OB_LOCK_LOC | OB_LOCK_ROT | OB_LOCK_SCALE;
1178
1179                                         copy_m3_m3(td->smtx, smtx);
1180                                         copy_m3_m3(td->mtx, mtx);
1181
1182                                         ED_armature_ebone_to_mat3(ebo, td->axismtx);
1183
1184                                         if ((ebo->flag & BONE_ROOTSEL) == 0) {
1185                                                 td->extra = ebo;
1186                                         }
1187
1188                                         td->ext = NULL;
1189                                         td->val = NULL;
1190                                         td->ob = t->obedit;
1191
1192                                         td++;
1193                                 }
1194                                 if (ebo->flag & BONE_ROOTSEL) {
1195                                         copy_v3_v3(td->iloc, ebo->head);
1196                                         copy_v3_v3(td->center, td->iloc);
1197                                         td->loc = ebo->head;
1198                                         td->flag = TD_SELECTED;
1199                                         if (ebo->flag & BONE_EDITMODE_LOCKED)
1200                                                 td->protectflag = OB_LOCK_LOC | OB_LOCK_ROT | OB_LOCK_SCALE;
1201
1202                                         copy_m3_m3(td->smtx, smtx);
1203                                         copy_m3_m3(td->mtx, mtx);
1204
1205                                         ED_armature_ebone_to_mat3(ebo, td->axismtx);
1206
1207                                         td->extra = ebo; /* to fix roll */
1208
1209                                         td->ext = NULL;
1210                                         td->val = NULL;
1211                                         td->ob = t->obedit;
1212
1213                                         td++;
1214                                 }
1215                         }
1216                 }
1217         }
1218 }
1219
1220 /* ********************* meta elements ********* */
1221
1222 static void createTransMBallVerts(TransInfo *t)
1223 {
1224         MetaBall *mb = (MetaBall *)t->obedit->data;
1225         MetaElem *ml;
1226         TransData *td;
1227         TransDataExtension *tx;
1228         float mtx[3][3], smtx[3][3];
1229         int count = 0, countsel = 0;
1230         int propmode = t->flag & T_PROP_EDIT;
1231
1232         /* count totals */
1233         for (ml = mb->editelems->first; ml; ml = ml->next) {
1234                 if (ml->flag & SELECT) countsel++;
1235                 if (propmode) count++;
1236         }
1237
1238         /* note: in prop mode we need at least 1 selected */
1239         if (countsel == 0) return;
1240
1241         if (propmode) t->total = count;
1242         else t->total = countsel;
1243
1244         td = t->data = MEM_callocN(t->total * sizeof(TransData), "TransObData(MBall EditMode)");
1245         tx = t->ext = MEM_callocN(t->total * sizeof(TransDataExtension), "MetaElement_TransExtension");
1246
1247         copy_m3_m4(mtx, t->obedit->obmat);
1248         pseudoinverse_m3_m3(smtx, mtx, PSEUDOINVERSE_EPSILON);
1249
1250         for (ml = mb->editelems->first; ml; ml = ml->next) {
1251                 if (propmode || (ml->flag & SELECT)) {
1252                         td->loc = &ml->x;
1253                         copy_v3_v3(td->iloc, td->loc);
1254                         copy_v3_v3(td->center, td->loc);
1255
1256                         quat_to_mat3(td->axismtx, ml->quat);
1257
1258                         if (ml->flag & SELECT) td->flag = TD_SELECTED | TD_USEQUAT | TD_SINGLESIZE;
1259                         else td->flag = TD_USEQUAT;
1260
1261                         copy_m3_m3(td->smtx, smtx);
1262                         copy_m3_m3(td->mtx, mtx);
1263
1264                         td->ext = tx;
1265
1266                         /* Radius of MetaElem (mass of MetaElem influence) */
1267                         if (ml->flag & MB_SCALE_RAD) {
1268                                 td->val = &ml->rad;
1269                                 td->ival = ml->rad;
1270                         }
1271                         else {
1272                                 td->val = &ml->s;
1273                                 td->ival = ml->s;
1274                         }
1275
1276                         /* expx/expy/expz determine "shape" of some MetaElem types */
1277                         tx->size = &ml->expx;
1278                         tx->isize[0] = ml->expx;
1279                         tx->isize[1] = ml->expy;
1280                         tx->isize[2] = ml->expz;
1281
1282                         /* quat is used for rotation of MetaElem */
1283                         tx->quat = ml->quat;
1284                         copy_qt_qt(tx->iquat, ml->quat);
1285
1286                         tx->rot = NULL;
1287
1288                         td++;
1289                         tx++;
1290                 }
1291         }
1292 }
1293
1294 /* ********************* curve/surface ********* */
1295
1296 static void calc_distanceCurveVerts(TransData *head, TransData *tail)
1297 {
1298         TransData *td, *td_near = NULL;
1299         for (td = head; td <= tail; td++) {
1300                 if (td->flag & TD_SELECTED) {
1301                         td_near = td;
1302                         td->dist = 0.0f;
1303                 }
1304                 else if (td_near) {
1305                         float dist;
1306                         dist = len_v3v3(td_near->center, td->center);
1307                         if (dist < (td - 1)->dist) {
1308                                 td->dist = (td - 1)->dist;
1309                         }
1310                         else {
1311                                 td->dist = dist;
1312                         }
1313                 }
1314                 else {
1315                         td->dist = FLT_MAX;
1316                         td->flag |= TD_NOTCONNECTED;
1317                 }
1318         }
1319         td_near = NULL;
1320         for (td = tail; td >= head; td--) {
1321                 if (td->flag & TD_SELECTED) {
1322                         td_near = td;
1323                         td->dist = 0.0f;
1324                 }
1325                 else if (td_near) {
1326                         float dist;
1327                         dist = len_v3v3(td_near->center, td->center);
1328                         if (td->flag & TD_NOTCONNECTED || dist < td->dist || (td + 1)->dist < td->dist) {
1329                                 td->flag &= ~TD_NOTCONNECTED;
1330                                 if (dist < (td + 1)->dist) {
1331                                         td->dist = (td + 1)->dist;
1332                                 }
1333                                 else {
1334                                         td->dist = dist;
1335                                 }
1336                         }
1337                 }
1338         }
1339 }
1340
1341 /* Utility function for getting the handle data from bezier's */
1342 static TransDataCurveHandleFlags *initTransDataCurveHandles(TransData *td, struct BezTriple *bezt)
1343 {
1344         TransDataCurveHandleFlags *hdata;
1345         td->flag |= TD_BEZTRIPLE;
1346         hdata = td->hdata = MEM_mallocN(sizeof(TransDataCurveHandleFlags), "CuHandle Data");
1347         hdata->ih1 = bezt->h1;
1348         hdata->h1 = &bezt->h1;
1349         hdata->ih2 = bezt->h2; /* in case the second is not selected */
1350         hdata->h2 = &bezt->h2;
1351         return hdata;
1352 }
1353
1354 static void createTransCurveVerts(TransInfo *t)
1355 {
1356         Curve *cu = t->obedit->data;
1357         TransData *td = NULL;
1358         Nurb *nu;
1359         BezTriple *bezt;
1360         BPoint *bp;
1361         float mtx[3][3], smtx[3][3];
1362         int a;
1363         int count = 0, countsel = 0;
1364         int propmode = t->flag & T_PROP_EDIT;
1365         short hide_handles = (cu->drawflag & CU_HIDE_HANDLES);
1366         ListBase *nurbs;
1367
1368         /* to be sure */
1369         if (cu->editnurb == NULL) return;
1370
1371         /* count total of vertices, check identical as in 2nd loop for making transdata! */
1372         nurbs = BKE_curve_editNurbs_get(cu);
1373         for (nu = nurbs->first; nu; nu = nu->next) {
1374                 if (nu->type == CU_BEZIER) {
1375                         for (a = 0, bezt = nu->bezt; a < nu->pntsu; a++, bezt++) {
1376                                 if (bezt->hide == 0) {
1377                                         if (hide_handles) {
1378                                                 if (bezt->f2 & SELECT) countsel += 3;
1379                                                 if (propmode) count += 3;
1380                                         }
1381                                         else {
1382                                                 if (bezt->f1 & SELECT) countsel++;
1383                                                 if (bezt->f2 & SELECT) countsel++;
1384                                                 if (bezt->f3 & SELECT) countsel++;
1385                                                 if (propmode) count += 3;
1386                                         }
1387                                 }
1388                         }
1389                 }
1390                 else {
1391                         for (a = nu->pntsu * nu->pntsv, bp = nu->bp; a > 0; a--, bp++) {
1392                                 if (bp->hide == 0) {
1393                                         if (propmode) count++;
1394                                         if (bp->f1 & SELECT) countsel++;
1395                                 }
1396                         }
1397                 }
1398         }
1399         /* note: in prop mode we need at least 1 selected */
1400         if (countsel == 0) return;
1401
1402         if (propmode) t->total = count;
1403         else t->total = countsel;
1404         t->data = MEM_callocN(t->total * sizeof(TransData), "TransObData(Curve EditMode)");
1405
1406         copy_m3_m4(mtx, t->obedit->obmat);
1407         pseudoinverse_m3_m3(smtx, mtx, PSEUDOINVERSE_EPSILON);
1408
1409         td = t->data;
1410         for (nu = nurbs->first; nu; nu = nu->next) {
1411                 if (nu->type == CU_BEZIER) {
1412                         TransData *head, *tail;
1413                         head = tail = td;
1414                         for (a = 0, bezt = nu->bezt; a < nu->pntsu; a++, bezt++) {
1415                                 if (bezt->hide == 0) {
1416                                         TransDataCurveHandleFlags *hdata = NULL;
1417                                         float axismtx[3][3];
1418
1419                                         if (t->around == V3D_LOCAL) {
1420                                                 float normal[3], plane[3];
1421
1422                                                 BKE_nurb_bezt_calc_normal(nu, bezt, normal);
1423                                                 BKE_nurb_bezt_calc_plane(nu, bezt, plane);
1424
1425                                                 if (createSpaceNormalTangent(axismtx, normal, plane)) {
1426                                                         /* pass */
1427                                                 }
1428                                                 else {
1429                                                         normalize_v3(normal);
1430                                                         axis_dominant_v3_to_m3(axismtx, normal);
1431                                                         invert_m3(axismtx);
1432                                                 }
1433                                         }
1434
1435                                         if (propmode ||
1436                                             ((bezt->f2 & SELECT) && hide_handles) ||
1437                                             ((bezt->f1 & SELECT) && hide_handles == 0))
1438                                         {
1439                                                 copy_v3_v3(td->iloc, bezt->vec[0]);
1440                                                 td->loc = bezt->vec[0];
1441                                                 copy_v3_v3(td->center, bezt->vec[(hide_handles || bezt->f2 & SELECT) ? 1 : 0]);
1442                                                 if (hide_handles) {
1443                                                         if (bezt->f2 & SELECT) td->flag = TD_SELECTED;
1444                                                         else td->flag = 0;
1445                                                 }
1446                                                 else {
1447                                                         if (bezt->f1 & SELECT) td->flag = TD_SELECTED;
1448                                                         else td->flag = 0;
1449                                                 }
1450                                                 td->ext = NULL;
1451                                                 td->val = NULL;
1452
1453                                                 hdata = initTransDataCurveHandles(td, bezt);
1454
1455                                                 copy_m3_m3(td->smtx, smtx);
1456                                                 copy_m3_m3(td->mtx, mtx);
1457                                                 if (t->around == V3D_LOCAL) {
1458                                                         copy_m3_m3(td->axismtx, axismtx);
1459                                                 }
1460
1461                                                 td++;
1462                                                 count++;
1463                                                 tail++;
1464                                         }
1465
1466                                         /* This is the Curve Point, the other two are handles */
1467                                         if (propmode || (bezt->f2 & SELECT)) {
1468                                                 copy_v3_v3(td->iloc, bezt->vec[1]);
1469                                                 td->loc = bezt->vec[1];
1470                                                 copy_v3_v3(td->center, td->loc);
1471                                                 if (bezt->f2 & SELECT) td->flag = TD_SELECTED;
1472                                                 else td->flag = 0;
1473                                                 td->ext = NULL;
1474
1475                                                 if (t->mode == TFM_CURVE_SHRINKFATTEN) { /* || t->mode==TFM_RESIZE) {*/ /* TODO - make points scale */
1476                                                         td->val = &(bezt->radius);
1477                                                         td->ival = bezt->radius;
1478                                                 }
1479                                                 else if (t->mode == TFM_TILT) {
1480                                                         td->val = &(bezt->alfa);
1481                                                         td->ival = bezt->alfa;
1482                                                 }
1483                                                 else {
1484                                                         td->val = NULL;
1485                                                 }
1486
1487                                                 copy_m3_m3(td->smtx, smtx);
1488                                                 copy_m3_m3(td->mtx, mtx);
1489                                                 if (t->around == V3D_LOCAL) {
1490                                                         copy_m3_m3(td->axismtx, axismtx);
1491                                                 }
1492
1493                                                 if ((bezt->f1 & SELECT) == 0 && (bezt->f3 & SELECT) == 0)
1494                                                         /* If the middle is selected but the sides arnt, this is needed */
1495                                                         if (hdata == NULL) { /* if the handle was not saved by the previous handle */
1496                                                                 hdata = initTransDataCurveHandles(td, bezt);
1497                                                         }
1498
1499                                                 td++;
1500                                                 count++;
1501                                                 tail++;
1502                                         }
1503                                         if (propmode ||
1504                                             ((bezt->f2 & SELECT) && hide_handles) ||
1505                                             ((bezt->f3 & SELECT) && hide_handles == 0))
1506                                         {
1507                                                 copy_v3_v3(td->iloc, bezt->vec[2]);
1508                                                 td->loc = bezt->vec[2];
1509                                                 copy_v3_v3(td->center, bezt->vec[(hide_handles || bezt->f2 & SELECT) ? 1 : 2]);
1510                                                 if (hide_handles) {
1511                                                         if (bezt->f2 & SELECT) td->flag = TD_SELECTED;
1512                                                         else td->flag = 0;
1513                                                 }
1514                                                 else {
1515                                                         if (bezt->f3 & SELECT) td->flag = TD_SELECTED;
1516                                                         else td->flag = 0;
1517                                                 }
1518                                                 td->ext = NULL;
1519                                                 td->val = NULL;
1520
1521                                                 if (hdata == NULL) { /* if the handle was not saved by the previous handle */
1522                                                         hdata = initTransDataCurveHandles(td, bezt);
1523                                                 }
1524
1525                                                 copy_m3_m3(td->smtx, smtx);
1526                                                 copy_m3_m3(td->mtx, mtx);
1527                                                 if (t->around == V3D_LOCAL) {
1528                                                         copy_m3_m3(td->axismtx, axismtx);
1529                                                 }
1530
1531                                                 td++;
1532                                                 count++;
1533                                                 tail++;
1534                                         }
1535
1536                                         (void)hdata;  /* quiet warning */
1537                                 }
1538                                 else if (propmode && head != tail) {
1539                                         calc_distanceCurveVerts(head, tail - 1);
1540                                         head = tail;
1541                                 }
1542                         }
1543                         if (propmode && head != tail)
1544                                 calc_distanceCurveVerts(head, tail - 1);
1545
1546                         /* TODO - in the case of tilt and radius we can also avoid allocating the initTransDataCurveHandles
1547                          * but for now just don't change handle types */
1548                         if (ELEM(t->mode, TFM_CURVE_SHRINKFATTEN, TFM_TILT) == 0) {
1549                                 /* sets the handles based on their selection, do this after the data is copied to the TransData */
1550                                 BKE_nurb_handles_test(nu);
1551                         }
1552                 }
1553                 else {
1554                         TransData *head, *tail;
1555                         head = tail = td;
1556                         for (a = nu->pntsu * nu->pntsv, bp = nu->bp; a > 0; a--, bp++) {
1557                                 if (bp->hide == 0) {
1558                                         if (propmode || (bp->f1 & SELECT)) {
1559                                                 copy_v3_v3(td->iloc, bp->vec);
1560                                                 td->loc = bp->vec;
1561                                                 copy_v3_v3(td->center, td->loc);
1562                                                 if (bp->f1 & SELECT) td->flag = TD_SELECTED;
1563                                                 else td->flag = 0;
1564                                                 td->ext = NULL;
1565
1566                                                 if (t->mode == TFM_CURVE_SHRINKFATTEN || t->mode == TFM_RESIZE) {
1567                                                         td->val = &(bp->radius);
1568                                                         td->ival = bp->radius;
1569                                                 }
1570                                                 else {
1571                                                         td->val = &(bp->alfa);
1572                                                         td->ival = bp->alfa;
1573                                                 }
1574
1575                                                 copy_m3_m3(td->smtx, smtx);
1576                                                 copy_m3_m3(td->mtx, mtx);
1577
1578                                                 td++;
1579                                                 count++;
1580                                                 tail++;
1581                                         }
1582                                 }
1583                                 else if (propmode && head != tail) {
1584                                         calc_distanceCurveVerts(head, tail - 1);
1585                                         head = tail;
1586                                 }
1587                         }
1588                         if (propmode && head != tail)
1589                                 calc_distanceCurveVerts(head, tail - 1);
1590                 }
1591         }
1592 }
1593
1594 /* ********************* lattice *************** */
1595
1596 static void createTransLatticeVerts(TransInfo *t)
1597 {
1598         Lattice *latt = ((Lattice *)t->obedit->data)->editlatt->latt;
1599         TransData *td = NULL;
1600         BPoint *bp, *actbp = BKE_lattice_active_point_get(latt);
1601         float mtx[3][3], smtx[3][3];
1602         int a;
1603         int count = 0, countsel = 0;
1604         int propmode = t->flag & T_PROP_EDIT;
1605
1606         bp = latt->def;
1607         a  = latt->pntsu * latt->pntsv * latt->pntsw;
1608         while (a--) {
1609                 if (bp->hide == 0) {
1610                         if (bp->f1 & SELECT) countsel++;
1611                         if (propmode) count++;
1612                 }
1613                 bp++;
1614         }
1615
1616         /* note: in prop mode we need at least 1 selected */
1617         if (countsel == 0) return;
1618
1619         if (propmode) t->total = count;
1620         else t->total = countsel;
1621         t->data = MEM_callocN(t->total * sizeof(TransData), "TransObData(Lattice EditMode)");
1622
1623         copy_m3_m4(mtx, t->obedit->obmat);
1624         pseudoinverse_m3_m3(smtx, mtx, PSEUDOINVERSE_EPSILON);
1625
1626         td = t->data;
1627         bp = latt->def;
1628         a  = latt->pntsu * latt->pntsv * latt->pntsw;
1629         while (a--) {
1630                 if (propmode || (bp->f1 & SELECT)) {
1631                         if (bp->hide == 0) {
1632                                 copy_v3_v3(td->iloc, bp->vec);
1633                                 td->loc = bp->vec;
1634                                 copy_v3_v3(td->center, td->loc);
1635                                 if (bp->f1 & SELECT) {
1636                                         td->flag = TD_SELECTED;
1637                                         if (actbp && bp == actbp) td->flag |= TD_ACTIVE;
1638                                 }
1639                                 else td->flag = 0;
1640                                 copy_m3_m3(td->smtx, smtx);
1641                                 copy_m3_m3(td->mtx, mtx);
1642
1643                                 td->ext = NULL;
1644                                 td->val = NULL;
1645
1646                                 td++;
1647                                 count++;
1648                         }
1649                 }
1650                 bp++;
1651         }
1652 }
1653
1654 /* ******************* particle edit **************** */
1655 static void createTransParticleVerts(bContext *C, TransInfo *t)
1656 {
1657         TransData *td = NULL;
1658         TransDataExtension *tx;
1659         Base *base = CTX_data_active_base(C);
1660         Object *ob = CTX_data_active_object(C);
1661         ParticleEditSettings *pset = PE_settings(t->scene);
1662         PTCacheEdit *edit = PE_get_current(t->scene, ob);
1663         ParticleSystem *psys = NULL;
1664         ParticleSystemModifierData *psmd = NULL;
1665         PTCacheEditPoint *point;
1666         PTCacheEditKey *key;
1667         float mat[4][4];
1668         int i, k, transformparticle;
1669         int count = 0, hasselected = 0;
1670         int propmode = t->flag & T_PROP_EDIT;
1671
1672         if (edit == NULL || t->settings->particle.selectmode == SCE_SELECT_PATH) return;
1673
1674         psys = edit->psys;
1675
1676         if (psys)
1677                 psmd = psys_get_modifier(ob, psys);
1678
1679         base->flag |= BA_HAS_RECALC_DATA;
1680
1681         for (i = 0, point = edit->points; i < edit->totpoint; i++, point++) {
1682                 point->flag &= ~PEP_TRANSFORM;
1683                 transformparticle = 0;
1684
1685                 if ((point->flag & PEP_HIDE) == 0) {
1686                         for (k = 0, key = point->keys; k < point->totkey; k++, key++) {
1687                                 if ((key->flag & PEK_HIDE) == 0) {
1688                                         if (key->flag & PEK_SELECT) {
1689                                                 hasselected = 1;
1690                                                 transformparticle = 1;
1691                                         }
1692                                         else if (propmode)
1693                                                 transformparticle = 1;
1694                                 }
1695                         }
1696                 }
1697
1698                 if (transformparticle) {
1699                         count += point->totkey;
1700                         point->flag |= PEP_TRANSFORM;
1701                 }
1702         }
1703
1704         /* note: in prop mode we need at least 1 selected */
1705         if (hasselected == 0) return;
1706
1707         t->total = count;
1708         td = t->data = MEM_callocN(t->total * sizeof(TransData), "TransObData(Particle Mode)");
1709
1710         if (t->mode == TFM_BAKE_TIME)
1711                 tx = t->ext = MEM_callocN(t->total * sizeof(TransDataExtension), "Particle_TransExtension");
1712         else
1713                 tx = t->ext = NULL;
1714
1715         unit_m4(mat);
1716
1717         invert_m4_m4(ob->imat, ob->obmat);
1718
1719         for (i = 0, point = edit->points; i < edit->totpoint; i++, point++) {
1720                 TransData *head, *tail;
1721                 head = tail = td;
1722
1723                 if (!(point->flag & PEP_TRANSFORM)) continue;
1724
1725                 if (psys && !(psys->flag & PSYS_GLOBAL_HAIR))
1726                         psys_mat_hair_to_global(ob, psmd->dm, psys->part->from, psys->particles + i, mat);
1727
1728                 for (k = 0, key = point->keys; k < point->totkey; k++, key++) {
1729                         if (key->flag & PEK_USE_WCO) {
1730                                 copy_v3_v3(key->world_co, key->co);
1731                                 mul_m4_v3(mat, key->world_co);
1732                                 td->loc = key->world_co;
1733                         }
1734                         else
1735                                 td->loc = key->co;
1736
1737                         copy_v3_v3(td->iloc, td->loc);
1738                         copy_v3_v3(td->center, td->loc);
1739
1740                         if (key->flag & PEK_SELECT)
1741                                 td->flag |= TD_SELECTED;
1742                         else if (!propmode)
1743                                 td->flag |= TD_SKIP;
1744
1745                         unit_m3(td->mtx);
1746                         unit_m3(td->smtx);
1747
1748                         /* don't allow moving roots */
1749                         if (k == 0 && pset->flag & PE_LOCK_FIRST && (!psys || !(psys->flag & PSYS_GLOBAL_HAIR)))
1750                                 td->protectflag |= OB_LOCK_LOC;
1751
1752                         td->ob = ob;
1753                         td->ext = tx;
1754                         if (t->mode == TFM_BAKE_TIME) {
1755                                 td->val = key->time;
1756                                 td->ival = *(key->time);
1757                                 /* abuse size and quat for min/max values */
1758                                 td->flag |= TD_NO_EXT;
1759                                 if (k == 0) tx->size = NULL;
1760                                 else tx->size = (key - 1)->time;
1761
1762                                 if (k == point->totkey - 1) tx->quat = NULL;
1763                                 else tx->quat = (key + 1)->time;
1764                         }
1765
1766                         td++;
1767                         if (tx)
1768                                 tx++;
1769                         tail++;
1770                 }
1771                 if (propmode && head != tail)
1772                         calc_distanceCurveVerts(head, tail - 1);
1773         }
1774 }
1775
1776 void flushTransParticles(TransInfo *t)
1777 {
1778         Scene *scene = t->scene;
1779         Object *ob = OBACT;
1780         PTCacheEdit *edit = PE_get_current(scene, ob);
1781         ParticleSystem *psys = edit->psys;
1782         ParticleSystemModifierData *psmd = NULL;
1783         PTCacheEditPoint *point;
1784         PTCacheEditKey *key;
1785         TransData *td;
1786         float mat[4][4], imat[4][4], co[3];
1787         int i, k, propmode = t->flag & T_PROP_EDIT;
1788
1789         if (psys)
1790                 psmd = psys_get_modifier(ob, psys);
1791
1792         /* we do transform in world space, so flush world space position
1793          * back to particle local space (only for hair particles) */
1794         td = t->data;
1795         for (i = 0, point = edit->points; i < edit->totpoint; i++, point++, td++) {
1796                 if (!(point->flag & PEP_TRANSFORM)) continue;
1797
1798                 if (psys && !(psys->flag & PSYS_GLOBAL_HAIR)) {
1799                         psys_mat_hair_to_global(ob, psmd->dm, psys->part->from, psys->particles + i, mat);
1800                         invert_m4_m4(imat, mat);
1801
1802                         for (k = 0, key = point->keys; k < point->totkey; k++, key++) {
1803                                 copy_v3_v3(co, key->world_co);
1804                                 mul_m4_v3(imat, co);
1805
1806
1807                                 /* optimization for proportional edit */
1808                                 if (!propmode || !compare_v3v3(key->co, co, 0.0001f)) {
1809                                         copy_v3_v3(key->co, co);
1810                                         point->flag |= PEP_EDIT_RECALC;
1811                                 }
1812                         }
1813                 }
1814                 else
1815                         point->flag |= PEP_EDIT_RECALC;
1816         }
1817
1818         PE_update_object(scene, OBACT, 1);
1819 }
1820
1821 /* ********************* mesh ****************** */
1822
1823 static bool bmesh_test_dist_add(BMVert *v, BMVert *v_other,
1824                                 float *dists, const float *dists_prev,
1825                                 float mtx[3][3])
1826 {
1827         if ((BM_elem_flag_test(v_other, BM_ELEM_SELECT) == 0) &&
1828             (BM_elem_flag_test(v_other, BM_ELEM_HIDDEN) == 0))
1829         {
1830                 const int i = BM_elem_index_get(v);
1831                 const int i_other = BM_elem_index_get(v_other);
1832                 float vec[3];
1833                 float dist_other;
1834                 sub_v3_v3v3(vec, v->co, v_other->co);
1835                 mul_m3_v3(mtx, vec);
1836
1837                 dist_other = dists_prev[i] + len_v3(vec);
1838                 if (dist_other < dists[i_other]) {
1839                         dists[i_other] = dist_other;
1840                         return true;
1841                 }
1842         }
1843
1844         return false;
1845 }
1846
1847 static void editmesh_set_connectivity_distance(BMesh *bm, float mtx[3][3], float *dists)
1848 {
1849         /* need to be very careful of feedback loops here, store previous dist's to avoid feedback */
1850         float *dists_prev = MEM_mallocN(bm->totvert * sizeof(float), __func__);
1851
1852         BLI_LINKSTACK_DECLARE(queue, BMVert *);
1853
1854         /* any BM_ELEM_TAG'd vertex is in 'queue_next', so we don't add in twice */
1855         BLI_LINKSTACK_DECLARE(queue_next, BMVert *);
1856
1857         BLI_LINKSTACK_INIT(queue);
1858         BLI_LINKSTACK_INIT(queue_next);
1859
1860         {
1861                 BMIter viter;
1862                 BMVert *v;
1863                 int i;
1864
1865                 BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
1866                         BM_elem_index_set(v, i); /* set_inline */
1867                         BM_elem_flag_disable(v, BM_ELEM_TAG);
1868
1869                         if (BM_elem_flag_test(v, BM_ELEM_SELECT) == 0 || BM_elem_flag_test(v, BM_ELEM_HIDDEN)) {
1870                                 dists[i] = FLT_MAX;
1871                         }
1872                         else {
1873                                 BLI_LINKSTACK_PUSH(queue, v);
1874
1875                                 dists[i] = 0.0f;
1876                         }
1877                 }
1878         }
1879
1880         do {
1881                 BMVert *v;
1882                 LinkNode *lnk;
1883
1884                 memcpy(dists_prev, dists, sizeof(float) * bm->totvert);
1885
1886                 while ((v = BLI_LINKSTACK_POP(queue))) {
1887                         BMIter iter;
1888                         BMEdge *e;
1889                         BMLoop *l;
1890
1891                         /* connected edge-verts */
1892                         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
1893                                 if (BM_elem_flag_test(e, BM_ELEM_HIDDEN) == 0) {
1894                                         BMVert *v_other = BM_edge_other_vert(e, v);
1895                                         if (bmesh_test_dist_add(v, v_other, dists, dists_prev, mtx)) {
1896                                                 if (BM_elem_flag_test(v_other, BM_ELEM_TAG) == 0) {
1897                                                         BM_elem_flag_enable(v_other, BM_ELEM_TAG);
1898                                                         BLI_LINKSTACK_PUSH(queue_next, v_other);
1899                                                 }
1900                                         }
1901                                 }
1902                         }
1903                         
1904                         /* connected face-verts (excluding adjacent verts) */
1905                         BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
1906                                 if ((BM_elem_flag_test(l->f, BM_ELEM_HIDDEN) == 0) && (l->f->len > 3)) {
1907                                         BMLoop *l_end = l->prev;
1908                                         l = l->next->next;
1909                                         do {
1910                                                 BMVert *v_other = l->v;
1911                                                 if (bmesh_test_dist_add(v, v_other, dists, dists_prev, mtx)) {
1912                                                         if (BM_elem_flag_test(v_other, BM_ELEM_TAG) == 0) {
1913                                                                 BM_elem_flag_enable(v_other, BM_ELEM_TAG);
1914                                                                 BLI_LINKSTACK_PUSH(queue_next, v_other);
1915                                                         }
1916                                                 }
1917                                         } while ((l = l->next) != l_end);
1918                                 }
1919                         }
1920                 }
1921
1922                 /* clear for the next loop */
1923                 for (lnk = queue_next; lnk; lnk = lnk->next) {
1924                         BM_elem_flag_disable((BMVert *)lnk->link, BM_ELEM_TAG);
1925                 }
1926
1927                 BLI_LINKSTACK_SWAP(queue, queue_next);
1928
1929                 /* none should be tagged now since 'queue_next' is empty */
1930                 BLI_assert(BM_iter_mesh_count_flag(BM_VERTS_OF_MESH, bm, BM_ELEM_TAG, true) == 0);
1931
1932         } while (BLI_LINKSTACK_SIZE(queue));
1933
1934         BLI_LINKSTACK_FREE(queue);
1935         BLI_LINKSTACK_FREE(queue_next);
1936
1937         MEM_freeN(dists_prev);
1938 }
1939
1940 static struct TransIslandData *editmesh_islands_info_calc(BMEditMesh *em, int *r_island_tot, int **r_island_vert_map)
1941 {
1942         BMesh *bm = em->bm;
1943         struct TransIslandData *trans_islands;
1944         char htype;
1945         char itype;
1946         int i;
1947
1948         /* group vars */
1949         int *groups_array;
1950         int (*group_index)[2];
1951         int group_tot;
1952         void **ele_array;
1953
1954         int *vert_map;
1955
1956         if (em->selectmode & (SCE_SELECT_VERTEX | SCE_SELECT_EDGE)) {
1957                 groups_array = MEM_mallocN(sizeof(*groups_array) * bm->totedgesel, __func__);
1958                 group_tot = BM_mesh_calc_edge_groups(bm, groups_array, &group_index,
1959                                                      NULL, NULL,
1960                                                      BM_ELEM_SELECT);
1961
1962                 htype = BM_EDGE;
1963                 itype = BM_VERTS_OF_EDGE;
1964
1965         }
1966         else {  /* (bm->selectmode & SCE_SELECT_FACE) */
1967                 groups_array = MEM_mallocN(sizeof(*groups_array) * bm->totfacesel, __func__);
1968                 group_tot = BM_mesh_calc_face_groups(bm, groups_array, &group_index,
1969                                                      NULL, NULL,
1970                                                      BM_ELEM_SELECT, BM_VERT);
1971
1972                 htype = BM_FACE;
1973                 itype = BM_VERTS_OF_FACE;
1974         }
1975
1976
1977         trans_islands = MEM_mallocN(sizeof(*trans_islands) * group_tot, __func__);
1978
1979         vert_map = MEM_mallocN(sizeof(*vert_map) * bm->totvert, __func__);
1980         /* we shouldn't need this, but with incorrect selection flushing
1981          * its possible we have a selected vertex thats not in a face, for now best not crash in that case. */
1982         fill_vn_i(vert_map, bm->totvert, -1);
1983
1984         EDBM_index_arrays_ensure(em, htype);
1985         ele_array = (htype == BM_FACE) ? (void **)em->face_index : (void **)em->edge_index;
1986
1987         BM_mesh_elem_index_ensure(bm, BM_VERT);
1988
1989         /* may be an edge OR a face array */
1990         for (i = 0; i < group_tot; i++) {
1991                 BMEditSelection ese = {NULL};
1992
1993                 const int fg_sta = group_index[i][0];
1994                 const int fg_len = group_index[i][1];
1995                 float co[3], no[3], tangent[3];
1996                 int j;
1997
1998                 zero_v3(co);
1999                 zero_v3(no);
2000                 zero_v3(tangent);
2001
2002                 ese.htype = htype;
2003
2004                 /* loop on each face in this group:
2005                  * - assign r_vert_map
2006                  * - calculate (co, no)
2007                  */
2008                 for (j = 0; j < fg_len; j++) {
2009                         float tmp_co[3], tmp_no[3], tmp_tangent[3];
2010
2011                         ese.ele = ele_array[groups_array[fg_sta + j]];
2012
2013                         BM_editselection_center(&ese, tmp_co);
2014                         BM_editselection_normal(&ese, tmp_no);
2015                         BM_editselection_plane(&ese, tmp_tangent);
2016
2017                         add_v3_v3(co, tmp_co);
2018                         add_v3_v3(no, tmp_no);
2019                         add_v3_v3(tangent, tmp_tangent);
2020
2021                         {
2022                                 /* setup vertex map */
2023                                 BMIter iter;
2024                                 BMVert *v;
2025
2026                                 /* connected edge-verts */
2027                                 BM_ITER_ELEM (v, &iter, ese.ele, itype) {
2028                                         vert_map[BM_elem_index_get(v)] = i;
2029                                 }
2030                         }
2031                 }
2032
2033                 mul_v3_v3fl(trans_islands[i].co, co, 1.0f / (float)fg_len);
2034
2035                 if (createSpaceNormalTangent(trans_islands[i].axismtx, no, tangent)) {
2036                         /* pass */
2037                 }
2038                 else {
2039                         normalize_v3(no);
2040                         axis_dominant_v3_to_m3(trans_islands[i].axismtx, no);
2041                         invert_m3(trans_islands[i].axismtx);
2042                 }
2043         }
2044
2045         MEM_freeN(groups_array);
2046         MEM_freeN(group_index);
2047
2048         *r_island_tot = group_tot;
2049         *r_island_vert_map = vert_map;
2050
2051         return trans_islands;
2052 }
2053
2054 /* way to overwrite what data is edited with transform */
2055 static void VertsToTransData(TransInfo *t, TransData *td, TransDataExtension *tx,
2056                              BMEditMesh *em, BMVert *eve, float *bweight,
2057                              struct TransIslandData *v_island)
2058 {
2059         BLI_assert(BM_elem_flag_test(eve, BM_ELEM_HIDDEN) == 0);
2060
2061         td->flag = 0;
2062         //if (key)
2063         //      td->loc = key->co;
2064         //else
2065         td->loc = eve->co;
2066         copy_v3_v3(td->iloc, td->loc);
2067
2068         if (v_island) {
2069                 copy_v3_v3(td->center, v_island->co);
2070                 copy_m3_m3(td->axismtx, v_island->axismtx);
2071         }
2072         else if (t->around == V3D_LOCAL) {
2073                 copy_v3_v3(td->center, td->loc);
2074
2075                 axis_dominant_v3_to_m3(td->axismtx, eve->no);
2076                 invert_m3(td->axismtx);
2077         }
2078         else {
2079                 copy_v3_v3(td->center, td->loc);
2080
2081                 /* Setting normals */
2082                 copy_v3_v3(td->axismtx[2], eve->no);
2083                 td->axismtx[0][0]        =
2084                     td->axismtx[0][1]    =
2085                     td->axismtx[0][2]    =
2086                     td->axismtx[1][0]    =
2087                     td->axismtx[1][1]    =
2088                     td->axismtx[1][2]    = 0.0f;
2089         }
2090
2091
2092         td->ext = NULL;
2093         td->val = NULL;
2094         td->extra = NULL;
2095         if (t->mode == TFM_BWEIGHT) {
2096                 td->val  =  bweight;
2097                 td->ival = *bweight;
2098         }
2099         else if (t->mode == TFM_SKIN_RESIZE) {
2100                 MVertSkin *vs = CustomData_bmesh_get(&em->bm->vdata,
2101                                                      eve->head.data,
2102                                                      CD_MVERT_SKIN);
2103                 /* skin node size */
2104                 td->ext = tx;
2105                 copy_v3_v3(tx->isize, vs->radius);
2106                 tx->size = vs->radius;
2107                 td->val = vs->radius;
2108         }
2109         else if (t->mode == TFM_SHRINKFATTEN) {
2110                 td->ext = tx;
2111                 tx->isize[0] = BM_vert_calc_shell_factor_ex(eve, BM_ELEM_SELECT);
2112         }
2113 }
2114
2115 static void createTransEditVerts(TransInfo *t)
2116 {
2117         TransData *tob = NULL;
2118         TransDataExtension *tx = NULL;
2119         BMEditMesh *em = BKE_editmesh_from_object(t->obedit);
2120         Mesh *me = t->obedit->data;
2121         BMesh *bm = em->bm;
2122         BMVert *eve;
2123         BMIter iter;
2124         BMVert *eve_act = NULL;
2125         float *mappedcos = NULL, *quats = NULL;
2126         float mtx[3][3], smtx[3][3], (*defmats)[3][3] = NULL, (*defcos)[3] = NULL;
2127         float *dists = NULL;
2128         int a;
2129         int propmode = (t->flag & T_PROP_EDIT) ? (t->flag & T_PROP_EDIT_ALL) : 0;
2130         int mirror = 0;
2131         int cd_vert_bweight_offset = -1;
2132         bool use_topology = (me->editflag & ME_EDIT_MIRROR_TOPO) != 0;
2133
2134         struct TransIslandData *island_info = NULL;
2135         int island_info_tot;
2136         int *island_vert_map = NULL;
2137
2138         if (t->flag & T_MIRROR) {
2139                 EDBM_verts_mirror_cache_begin(em, 0, false, (t->flag & T_PROP_EDIT) == 0, use_topology);
2140                 mirror = 1;
2141         }
2142
2143         /* quick check if we can transform */
2144         /* note: in prop mode we need at least 1 selected */
2145         if (em->selectmode & SCE_SELECT_VERTEX) {
2146                 if (bm->totvertsel == 0) {
2147                         goto cleanup;
2148                 }
2149         }
2150         else if (em->selectmode & SCE_SELECT_EDGE) {
2151                 if (bm->totvertsel == 0 || bm->totedgesel == 0) {
2152                         goto cleanup;
2153                 }
2154         }
2155         else if (em->selectmode & SCE_SELECT_FACE) {
2156                 if (bm->totvertsel == 0 || bm->totfacesel == 0) {
2157                         goto cleanup;
2158                 }
2159         }
2160         else {
2161                 BLI_assert(0);
2162         }
2163
2164
2165         /* check active */
2166         eve_act = BM_mesh_active_vert_get(bm);
2167
2168         if (t->mode == TFM_BWEIGHT) {
2169                 BM_mesh_cd_flag_ensure(bm, BKE_mesh_from_object(t->obedit), ME_CDFLAG_VERT_BWEIGHT);
2170                 cd_vert_bweight_offset = CustomData_get_offset(&bm->vdata, CD_BWEIGHT);
2171         }
2172
2173         if (propmode) {
2174                 unsigned int count = 0;
2175                 BM_ITER_MESH (eve, &iter, bm, BM_VERTS_OF_MESH) {
2176                         if (!BM_elem_flag_test(eve, BM_ELEM_HIDDEN)) {
2177                                 count++;
2178                         }
2179                 }
2180
2181                 t->total = count;
2182
2183                 /* allocating scratch arrays */
2184                 if (propmode & T_PROP_CONNECTED)
2185                         dists = MEM_mallocN(em->bm->totvert * sizeof(float), "scratch nears");
2186         }
2187         else {
2188                 t->total = bm->totvertsel;
2189         }
2190
2191         tob = t->data = MEM_callocN(t->total * sizeof(TransData), "TransObData(Mesh EditMode)");
2192         if (ELEM(t->mode, TFM_SKIN_RESIZE, TFM_SHRINKFATTEN)) {
2193                 /* warning, this is overkill, we only need 2 extra floats,
2194                  * but this stores loads of extra stuff, for TFM_SHRINKFATTEN its even more overkill
2195                  * since we may not use the 'alt' transform mode to maintain shell thickness,
2196                  * but with generic transform code its hard to lazy init vars */
2197                 tx = t->ext = MEM_callocN(t->total * sizeof(TransDataExtension),
2198                                           "TransObData ext");
2199         }
2200
2201         copy_m3_m4(mtx, t->obedit->obmat);
2202         /* we use a pseudoinverse so that when one of the axes is scaled to 0,
2203          * matrix inversion still works and we can still moving along the other */
2204         pseudoinverse_m3_m3(smtx, mtx, PSEUDOINVERSE_EPSILON);
2205
2206         if (propmode & T_PROP_CONNECTED) {
2207                 editmesh_set_connectivity_distance(em->bm, mtx, dists);
2208         }
2209
2210         if (t->around == V3D_LOCAL) {
2211                 island_info = editmesh_islands_info_calc(em, &island_info_tot, &island_vert_map);
2212         }
2213
2214         /* BMESH_TODO, crazy-space writing into the index values is BAD!, means we cant
2215          * use the values for vertex mirror - campbell */
2216
2217         /* detect CrazySpace [tm] */
2218         if (modifiers_getCageIndex(t->scene, t->obedit, NULL, 1) >= 0) {
2219                 if (modifiers_isCorrectableDeformed(t->obedit)) {
2220                         int totleft;
2221                         /* check if we can use deform matrices for modifier from the
2222                          * start up to stack, they are more accurate than quats */
2223                         totleft = editbmesh_get_first_deform_matrices(t->scene, t->obedit, em, &defmats, &defcos);
2224
2225                         /* if we still have more modifiers, also do crazyspace
2226                          * correction with quats, relative to the coordinates after
2227                          * the modifiers that support deform matrices (defcos) */
2228                         if (totleft > 0) {
2229                                 mappedcos = crazyspace_get_mapped_editverts(t->scene, t->obedit);
2230                                 quats = MEM_mallocN((t->total) * sizeof(float) * 4, "crazy quats");
2231                                 crazyspace_set_quats_editmesh(em, (float *)defcos, mappedcos, quats); /* BMESH_TODO, abuses vertex index, should use an int array */
2232                                 if (mappedcos)
2233                                         MEM_freeN(mappedcos);
2234                         }
2235
2236                         if (defcos)
2237                                 MEM_freeN(defcos);
2238                 }
2239         }
2240
2241         /* find out which half we do */
2242         if (mirror) {
2243                 BM_ITER_MESH (eve, &iter, bm, BM_VERTS_OF_MESH) {
2244                         if (BM_elem_flag_test(eve, BM_ELEM_SELECT) && eve->co[0] != 0.0f) {
2245                                 if (eve->co[0] < 0.0f) {
2246                                         t->mirror = -1;
2247                                         mirror = -1;
2248                                 }
2249                                 break;
2250                         }
2251                 }
2252         }
2253
2254         BM_ITER_MESH_INDEX (eve, &iter, bm, BM_VERTS_OF_MESH, a) {
2255                 if (!BM_elem_flag_test(eve, BM_ELEM_HIDDEN)) {
2256                         if (propmode || BM_elem_flag_test(eve, BM_ELEM_SELECT)) {
2257                                 struct TransIslandData *v_island = (island_info && island_vert_map[a] != -1) ?
2258                                                                    &island_info[island_vert_map[a]] : NULL;
2259                                 float *bweight = (cd_vert_bweight_offset != -1) ? BM_ELEM_CD_GET_VOID_P(eve, cd_vert_bweight_offset) : NULL;
2260
2261                                 VertsToTransData(t, tob, tx, em, eve, bweight, v_island);
2262                                 if (tx)
2263                                         tx++;
2264
2265                                 /* selected */
2266                                 if (BM_elem_flag_test(eve, BM_ELEM_SELECT))
2267                                         tob->flag |= TD_SELECTED;
2268
2269                                 /* active */
2270                                 if (eve == eve_act) tob->flag |= TD_ACTIVE;
2271
2272                                 if (propmode) {
2273                                         if (propmode & T_PROP_CONNECTED) {
2274                                                 tob->dist = dists[a];
2275                                         }
2276                                         else {
2277                                                 tob->flag |= TD_NOTCONNECTED;
2278                                                 tob->dist = FLT_MAX;
2279                                         }
2280                                 }
2281
2282                                 /* CrazySpace */
2283                                 if (defmats || (quats && BM_elem_index_get(eve) != -1)) {
2284                                         float mat[3][3], qmat[3][3], imat[3][3];
2285
2286                                         /* use both or either quat and defmat correction */
2287                                         if (quats && BM_elem_index_get(eve) != -1) {
2288                                                 quat_to_mat3(qmat, quats + 4 * BM_elem_index_get(eve));
2289
2290                                                 if (defmats)
2291                                                         mul_serie_m3(mat, mtx, qmat, defmats[a],
2292                                                                      NULL, NULL, NULL, NULL, NULL);
2293                                                 else
2294                                                         mul_m3_m3m3(mat, mtx, qmat);
2295                                         }
2296                                         else
2297                                                 mul_m3_m3m3(mat, mtx, defmats[a]);
2298
2299                                         invert_m3_m3(imat, mat);
2300
2301                                         copy_m3_m3(tob->smtx, imat);
2302                                         copy_m3_m3(tob->mtx, mat);
2303                                 }
2304                                 else {
2305                                         copy_m3_m3(tob->smtx, smtx);
2306                                         copy_m3_m3(tob->mtx, mtx);
2307                                 }
2308
2309                                 /* Mirror? */
2310                                 if ((mirror > 0 && tob->iloc[0] > 0.0f) || (mirror < 0 && tob->iloc[0] < 0.0f)) {
2311                                         BMVert *vmir = EDBM_verts_mirror_get(em, eve); //t->obedit, em, eve, tob->iloc, a);
2312                                         if (vmir && vmir != eve) {
2313                                                 tob->extra = vmir;
2314                                         }
2315                                 }
2316                                 tob++;
2317                         }
2318                 }
2319         }
2320         
2321         if (island_info) {
2322                 MEM_freeN(island_info);
2323                 MEM_freeN(island_vert_map);
2324         }
2325
2326         if (mirror != 0) {
2327                 tob = t->data;
2328                 for (a = 0; a < t->total; a++, tob++) {
2329                         if (ABS(tob->loc[0]) <= 0.00001f) {
2330                                 tob->flag |= TD_MIRROR_EDGE;
2331                         }
2332                 }
2333         }
2334
2335 cleanup:
2336         /* crazy space free */
2337         if (quats)
2338                 MEM_freeN(quats);
2339         if (defmats)
2340                 MEM_freeN(defmats);
2341         if (dists)
2342                 MEM_freeN(dists);
2343
2344         if (t->flag & T_MIRROR) {
2345                 EDBM_verts_mirror_cache_end(em);
2346         }
2347 }
2348
2349 /* *** NODE EDITOR *** */
2350 void flushTransNodes(TransInfo *t)
2351 {
2352         int a;
2353         TransData *td;
2354         TransData2D *td2d;
2355
2356         /* flush to 2d vector from internally used 3d vector */
2357         for (a = 0, td = t->data, td2d = t->data2d; a < t->total; a++, td++, td2d++) {
2358                 bNode *node = td->extra;
2359                 float vec[2];
2360                 
2361                 /* weirdo - but the node system is a mix of free 2d elements and dpi sensitive UI */
2362                 add_v2_v2v2(vec, td2d->loc, td2d->ih1);
2363                 node->locx = vec[0] / UI_DPI_FAC;
2364                 node->locy = vec[1] / UI_DPI_FAC;
2365         }
2366         
2367         /* handle intersection with noodles */
2368         if (t->total == 1) {
2369                 ED_node_link_intersect_test(t->sa, 1);
2370         }
2371 }
2372
2373 /* *** SEQUENCE EDITOR *** */
2374
2375 /* commented _only_ because the meta may have animation data which
2376  * needs moving too [#28158] */
2377
2378 #define SEQ_TX_NESTED_METAS
2379
2380 void flushTransSeq(TransInfo *t)
2381 {
2382         ListBase *seqbasep = BKE_sequencer_editing_get(t->scene, FALSE)->seqbasep; /* Editing null check already done */
2383         int a, new_frame, old_start;
2384         TransData *td = NULL;
2385         TransData2D *td2d = NULL;
2386         TransDataSeq *tdsq = NULL;
2387         Sequence *seq;
2388
2389
2390
2391         /* prevent updating the same seq twice
2392          * if the transdata order is changed this will mess up
2393          * but so will TransDataSeq */
2394         Sequence *seq_prev = NULL;
2395
2396         /* flush to 2d vector from internally used 3d vector */
2397         for (a = 0, td = t->data, td2d = t->data2d; a < t->total; a++, td++, td2d++) {
2398                 tdsq = (TransDataSeq *)td->extra;
2399                 seq = tdsq->seq;
2400                 old_start = seq->start;
2401                 new_frame = (int)floor(td2d->loc[0] + 0.5f);
2402
2403                 switch (tdsq->sel_flag) {
2404                         case SELECT:
2405 #ifdef SEQ_TX_NESTED_METAS
2406                                 if ((seq->depth != 0 || BKE_sequence_tx_test(seq))) /* for meta's, their children move */
2407                                         seq->start = new_frame - tdsq->start_offset;
2408 #else
2409                                 if (seq->type != SEQ_TYPE_META && (seq->depth != 0 || seq_tx_test(seq))) /* for meta's, their children move */
2410                                         seq->start = new_frame - tdsq->start_offset;
2411 #endif
2412                                 if (seq->depth == 0) {
2413                                         seq->machine = (int)floor(td2d->loc[1] + 0.5f);
2414                                         CLAMP(seq->machine, 1, MAXSEQ);
2415                                 }
2416                                 break;
2417                         case SEQ_LEFTSEL: /* no vertical transform  */
2418                                 BKE_sequence_tx_set_final_left(seq, new_frame);
2419                                 BKE_sequence_tx_handle_xlimits(seq, tdsq->flag & SEQ_LEFTSEL, tdsq->flag & SEQ_RIGHTSEL);
2420                                 BKE_sequence_single_fix(seq); /* todo - move this into aftertrans update? - old seq tx needed it anyway */
2421                                 break;
2422                         case SEQ_RIGHTSEL: /* no vertical transform  */
2423                                 BKE_sequence_tx_set_final_right(seq, new_frame);
2424                                 BKE_sequence_tx_handle_xlimits(seq, tdsq->flag & SEQ_LEFTSEL, tdsq->flag & SEQ_RIGHTSEL);
2425                                 BKE_sequence_single_fix(seq); /* todo - move this into aftertrans update? - old seq tx needed it anyway */
2426                                 break;
2427                 }
2428
2429                 if (seq != seq_prev) {
2430                         if (seq->depth == 0) {
2431                                 /* Calculate this strip and all nested strips
2432                                  * children are ALWAYS transformed first
2433                                  * so we don't need to do this in another loop. */
2434                                 BKE_sequence_calc(t->scene, seq);
2435                         }
2436                         else {
2437                                 BKE_sequence_calc_disp(t->scene, seq);
2438                         }
2439
2440                         if (tdsq->sel_flag == SELECT)
2441                                 BKE_sequencer_offset_animdata(t->scene, seq, seq->start - old_start);
2442                 }
2443                 seq_prev = seq;
2444         }
2445
2446
2447         if (ELEM(t->mode, TFM_SEQ_SLIDE, TFM_TIME_TRANSLATE)) { /* originally TFM_TIME_EXTEND, transform changes */
2448                 /* Special annoying case here, need to calc metas with TFM_TIME_EXTEND only */
2449
2450                 /* calc all meta's then effects [#27953] */
2451                 for (seq = seqbasep->first; seq; seq = seq->next) {
2452                         if (seq->type == SEQ_TYPE_META && seq->flag & SELECT) {
2453                                 BKE_sequence_calc(t->scene, seq);
2454                         }
2455                 }
2456                 for (seq = seqbasep->first; seq; seq = seq->next) {
2457                         if (seq->seq1 || seq->seq2 || seq->seq3) {
2458                                 BKE_sequence_calc(t->scene, seq);
2459                         }
2460                 }
2461         }
2462
2463         /* need to do the overlap check in a new loop otherwise adjacent strips
2464          * will not be updated and we'll get false positives */
2465         seq_prev = NULL;
2466         for (a = 0, td = t->data, td2d = t->data2d; a < t->total; a++, td++, td2d++) {
2467
2468                 tdsq = (TransDataSeq *)td->extra;
2469                 seq = tdsq->seq;
2470
2471                 if (seq != seq_prev) {
2472                         if (seq->depth == 0) {
2473                                 /* test overlap, displayes red outline */
2474                                 seq->flag &= ~SEQ_OVERLAP;
2475                                 if (BKE_sequence_test_overlap(seqbasep, seq)) {
2476                                         seq->flag |= SEQ_OVERLAP;
2477                                 }
2478                         }
2479                 }
2480                 seq_prev = seq;
2481         }
2482 }
2483
2484 /* ********************* UV ****************** */
2485
2486 static void UVsToTransData(SpaceImage *sima, TransData *td, TransData2D *td2d, float *uv, int selected)
2487 {
2488         float aspx, aspy;
2489
2490         ED_space_image_get_uv_aspect(sima, &aspx, &aspy);
2491
2492         /* uv coords are scaled by aspects. this is needed for rotations and
2493          * proportional editing to be consistent with the stretched uv coords
2494          * that are displayed. this also means that for display and numinput,
2495          * and when the the uv coords are flushed, these are converted each time */
2496         td2d->loc[0] = uv[0] * aspx;
2497         td2d->loc[1] = uv[1] * aspy;
2498         td2d->loc[2] = 0.0f;
2499         td2d->loc2d = uv;
2500
2501         td->flag = 0;
2502         td->loc = td2d->loc;
2503         copy_v3_v3(td->center, td->loc);
2504         copy_v3_v3(td->iloc, td->loc);
2505
2506         memset(td->axismtx, 0, sizeof(td->axismtx));
2507         td->axismtx[2][2] = 1.0f;
2508
2509         td->ext = NULL; td->val = NULL;
2510
2511         if (selected) {
2512                 td->flag |= TD_SELECTED;
2513                 td->dist = 0.0;
2514         }
2515         else {
2516                 td->dist = FLT_MAX;
2517         }
2518         unit_m3(td->mtx);
2519         unit_m3(td->smtx);
2520 }
2521
2522 static void createTransUVs(bContext *C, TransInfo *t)
2523 {
2524         SpaceImage *sima = CTX_wm_space_image(C);
2525         Image *ima = CTX_data_edit_image(C);
2526         Scene *scene = t->scene;
2527         ToolSettings *ts = CTX_data_tool_settings(C);
2528         TransData *td = NULL;
2529         TransData2D *td2d = NULL;
2530         MTexPoly *tf;
2531         MLoopUV *luv;
2532         BMEditMesh *em = BKE_editmesh_from_object(t->obedit);
2533         BMFace *efa;
2534         BMLoop *l;
2535         BMIter iter, liter;
2536         UvElementMap *elementmap = NULL;
2537         char *island_enabled = NULL;
2538         int count = 0, countsel = 0, count_rejected = 0;
2539         int propmode = t->flag & T_PROP_EDIT;
2540         int propconnected = t->flag & T_PROP_CONNECTED;
2541
2542         const int cd_loop_uv_offset = CustomData_get_offset(&em->bm->ldata, CD_MLOOPUV);
2543
2544         if (!ED_space_image_show_uvedit(sima, t->obedit)) return;
2545
2546         /* count */
2547         if (propconnected) {
2548                 /* create element map with island information */
2549                 if (ts->uv_flag & UV_SYNC_SELECTION) {
2550                         elementmap = EDBM_uv_element_map_create(em, false, true);
2551                 }
2552                 else {
2553                         elementmap = EDBM_uv_element_map_create(em, true, true);
2554                 }
2555                 island_enabled = MEM_callocN(sizeof(*island_enabled) * elementmap->totalIslands, "TransIslandData(UV Editing)");
2556         }
2557
2558         BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
2559                 tf = CustomData_bmesh_get(&em->bm->pdata, efa->head.data, CD_MTEXPOLY);
2560
2561                 if (!uvedit_face_visible_test(scene, ima, efa, tf)) {
2562                         BM_elem_flag_disable(efa, BM_ELEM_TAG);
2563                         continue;
2564                 }
2565
2566                 BM_elem_flag_enable(efa, BM_ELEM_TAG);
2567                 BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
2568                         if (uvedit_uv_select_test(scene, l, cd_loop_uv_offset)) {
2569                                 countsel++;
2570
2571                                 if (propconnected) {
2572                                         UvElement *element = ED_uv_element_get(elementmap, efa, l);
2573                                         island_enabled[element->island] = TRUE;
2574                                 }
2575
2576                         }
2577
2578                         if (propmode) {
2579                                 count++;
2580                         }
2581                 }
2582         }
2583
2584         /* note: in prop mode we need at least 1 selected */
2585         if (countsel == 0) return;
2586
2587         t->total = (propmode) ? count : countsel;
2588         t->data = MEM_callocN(t->total * sizeof(TransData), "TransObData(UV Editing)");
2589         /* for each 2d uv coord a 3d vector is allocated, so that they can be
2590          * treated just as if they were 3d verts */
2591         t->data2d = MEM_callocN(t->total * sizeof(TransData2D), "TransObData2D(UV Editing)");
2592
2593         if (sima->flag & SI_CLIP_UV)
2594                 t->flag |= T_CLIP_UV;
2595
2596         td = t->data;
2597         td2d = t->data2d;
2598
2599         BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
2600                 if (!BM_elem_flag_test(efa, BM_ELEM_TAG))
2601                         continue;
2602
2603                 BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
2604                         if (!propmode && !uvedit_uv_select_test(scene, l, cd_loop_uv_offset))
2605                                 continue;
2606
2607                         if (propconnected) {
2608                                 UvElement *element = ED_uv_element_get(elementmap, efa, l);
2609                                 if (!island_enabled[element->island]) {
2610                                         count_rejected++;
2611                                         continue;
2612                                 }
2613                         }
2614                         
2615                         luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
2616                         UVsToTransData(sima, td++, td2d++, luv->uv, uvedit_uv_select_test(scene, l, cd_loop_uv_offset));
2617                 }
2618         }
2619
2620         if (propconnected) {
2621                 t->total -= count_rejected;
2622                 EDBM_uv_element_map_free(elementmap);
2623                 MEM_freeN(island_enabled);
2624         }
2625
2626         if (sima->flag & SI_LIVE_UNWRAP)
2627                 ED_uvedit_live_unwrap_begin(t->scene, t->obedit);
2628 }
2629
2630 void flushTransUVs(TransInfo *t)
2631 {
2632         SpaceImage *sima = t->sa->spacedata.first;
2633         TransData2D *td;
2634         int a, width, height;
2635         float aspx, aspy, invx, invy;
2636
2637         ED_space_image_get_uv_aspect(sima, &aspx, &aspy);
2638         ED_space_image_get_size(sima, &width, &height);
2639         invx = 1.0f / aspx;
2640         invy = 1.0f / aspy;
2641
2642         /* flush to 2d vector from internally used 3d vector */
2643         for (a = 0, td = t->data2d; a < t->total; a++, td++) {
2644                 td->loc2d[0] = td->loc[0] * invx;
2645                 td->loc2d[1] = td->loc[1] * invy;
2646
2647                 if ((sima->flag & SI_PIXELSNAP) && (t->state != TRANS_CANCEL)) {
2648                         td->loc2d[0] = (float)floor(width * td->loc2d[0] + 0.5f) / width;
2649                         td->loc2d[1] = (float)floor(height * td->loc2d[1] + 0.5f) / height;
2650                 }
2651         }
2652 }
2653
2654 bool clipUVTransform(TransInfo *t, float vec[2], const bool resize)
2655 {
2656         TransData *td;
2657         int a, clipx = 1, clipy = 1;
2658         float aspx, aspy, min[2], max[2];
2659
2660         ED_space_image_get_uv_aspect(t->sa->spacedata.first, &aspx, &aspy);
2661         min[0] = min[1] = 0.0f;
2662         max[0] = aspx; max[1] = aspy;
2663
2664         for (a = 0, td = t->data; a < t->total; a++, td++) {
2665                 minmax_v2v2_v2(min, max, td->loc);
2666         }
2667
2668         if (resize) {
2669                 if (min[0] < 0.0f && t->center[0] > 0.0f && t->center[0] < aspx * 0.5f)
2670                         vec[0] *= t->center[0] / (t->center[0] - min[0]);
2671                 else if (max[0] > aspx && t->center[0] < aspx)
2672                         vec[0] *= (t->center[0] - aspx) / (t->center[0] - max[0]);
2673                 else
2674                         clipx = 0;
2675
2676                 if (min[1] < 0.0f && t->center[1] > 0.0f && t->center[1] < aspy * 0.5f)
2677                         vec[1] *= t->center[1] / (t->center[1] - min[1]);
2678                 else if (max[1] > aspy && t->center[1] < aspy)
2679                         vec[1] *= (t->center[1] - aspy) / (t->center[1] - max[1]);
2680                 else
2681                         clipy = 0;
2682         }
2683         else {
2684                 if (min[0] < 0.0f)
2685                         vec[0] -= min[0];
2686                 else if (max[0] > aspx)
2687                         vec[0] -= max[0] - aspx;
2688                 else
2689                         clipx = 0;
2690
2691                 if (min[1] < 0.0f)
2692                         vec[1] -= min[1];
2693                 else if (max[1] > aspy)
2694                         vec[1] -= max[1] - aspy;
2695                 else
2696                         clipy = 0;
2697         }
2698
2699         return (clipx || clipy);
2700 }
2701
2702 void clipUVData(TransInfo *t)
2703 {
2704         TransData *td = NULL;
2705         int a;
2706         float aspx, aspy;
2707
2708         ED_space_image_get_uv_aspect(t->sa->spacedata.first, &aspx, &aspy);
2709
2710         for (a = 0, td = t->data; a < t->total; a++, td++) {
2711                 if (td->flag & TD_NOACTION)
2712                         break;
2713
2714                 if ((td->flag & TD_SKIP) || (!td->loc))
2715                         continue;
2716
2717                 td->loc[0] = min_ff(max_ff(0.0f, td->loc[0]), aspx);
2718                 td->loc[1] = min_ff(max_ff(0.0f, td->loc[1]), aspy);
2719         }
2720 }
2721
2722 /* ********************* ANIMATION EDITORS (GENERAL) ************************* */
2723
2724 /* This function tests if a point is on the "mouse" side of the cursor/frame-marking */
2725 static bool FrameOnMouseSide(char side, float frame, float cframe)
2726 {
2727         /* both sides, so it doesn't matter */
2728         if (side == 'B') return true;
2729
2730         /* only on the named side */
2731         if (side == 'R')
2732                 return (frame >= cframe);
2733         else
2734                 return (frame <= cframe);
2735 }
2736
2737 /* ********************* NLA EDITOR ************************* */
2738
2739 static void createTransNlaData(bContext *C, TransInfo *t)
2740 {
2741         Scene *scene = t->scene;
2742         SpaceNla *snla = NULL;
2743         TransData *td = NULL;
2744         TransDataNla *tdn = NULL;
2745         
2746         bAnimContext ac;
2747         ListBase anim_data = {NULL, NULL};
2748         bAnimListElem *ale;
2749         int filter;
2750         
2751         int count = 0;
2752         
2753         /* determine what type of data we are operating on */
2754         if (ANIM_animdata_get_context(C, &ac) == 0)
2755                 return;
2756         snla = (SpaceNla *)ac.sl;
2757         
2758         /* filter data */
2759         filter = (ANIMFILTER_DATA_VISIBLE | ANIMFILTER_LIST_VISIBLE | ANIMFILTER_FOREDIT);
2760         ANIM_animdata_filter(&ac, &anim_data, filter, ac.data, ac.datatype);
2761         
2762         /* which side of the current frame should be allowed */
2763         if (t->mode == TFM_TIME_EXTEND) {
2764                 /* only side on which mouse is gets transformed */
2765                 float xmouse, ymouse;
2766                 
2767                 UI_view2d_region_to_view(&ac.ar->v2d, t->imval[0], t->imval[1], &xmouse, &ymouse);
2768                 t->frame_side = (xmouse > CFRA) ? 'R' : 'L';
2769         }
2770         else {
2771                 /* normal transform - both sides of current frame are considered */
2772                 t->frame_side = 'B';
2773         }
2774         
2775         /* loop 1: count how many strips are selected (consider each strip as 2 points) */
2776         for (ale = anim_data.first; ale; ale = ale->next) {
2777                 NlaTrack *nlt = (NlaTrack *)ale->data;
2778                 NlaStrip *strip;
2779                 
2780                 /* make some meta-strips for chains of selected strips */
2781                 BKE_nlastrips_make_metas(&nlt->strips, 1);
2782                 
2783                 /* only consider selected strips */
2784                 for (strip = nlt->strips.first; strip; strip = strip->next) {
2785                         // TODO: we can make strips have handles later on...
2786                         /* transition strips can't get directly transformed */
2787                         if (strip->type != NLASTRIP_TYPE_TRANSITION) {
2788                                 if (strip->flag & NLASTRIP_FLAG_SELECT) {
2789                                         if (FrameOnMouseSide(t->frame_side, strip->start, (float)CFRA)) count++;
2790                                         if (FrameOnMouseSide(t->frame_side, strip->end, (float)CFRA)) count++;
2791                                 }
2792                         }
2793                 }
2794         }
2795         
2796         /* stop if trying to build list if nothing selected */
2797         if (count == 0) {
2798                 /* clear temp metas that may have been created but aren't needed now 
2799                  * because they fell on the wrong side of CFRA
2800                  */
2801                 for (ale = anim_data.first; ale; ale = ale->next) {
2802                         NlaTrack *nlt = (NlaTrack *)ale->data;
2803                         BKE_nlastrips_clear_metas(&nlt->strips, 0, 1);
2804                 }
2805                 
2806                 /* cleanup temp list */
2807                 BLI_freelistN(&anim_data);
2808                 return;
2809         }
2810         
2811         /* allocate memory for data */
2812         t->total = count;
2813         
2814         t->data = MEM_callocN(t->total * sizeof(TransData), "TransData(NLA Editor)");
2815         td = t->data;
2816         t->customData = MEM_callocN(t->total * sizeof(TransDataNla), "TransDataNla (NLA Editor)");
2817         tdn = t->customData;
2818         t->flag |= T_FREE_CUSTOMDATA;
2819         
2820         /* loop 2: build transdata array */
2821         for (ale = anim_data.first; ale; ale = ale->next) {
2822                 /* only if a real NLA-track */
2823                 if (ale->type == ANIMTYPE_NLATRACK) {
2824                         AnimData *adt = ale->adt;
2825         &nbs