Merge branch 'master' into blender2.8
[blender.git] / source / blender / blenkernel / intern / key.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/blenkernel/intern/key.c
29  *  \ingroup bke
30  */
31
32
33 #include <math.h>
34 #include <string.h>
35 #include <stddef.h>
36
37 #include "MEM_guardedalloc.h"
38
39 #include "BLI_blenlib.h"
40 #include "BLI_math_vector.h"
41 #include "BLI_string_utils.h"
42 #include "BLI_utildefines.h"
43
44 #include "BLT_translation.h"
45
46 #include "DNA_anim_types.h"
47 #include "DNA_key_types.h"
48 #include "DNA_lattice_types.h"
49 #include "DNA_mesh_types.h"
50 #include "DNA_meshdata_types.h"
51 #include "DNA_object_types.h"
52 #include "DNA_scene_types.h"
53
54 #include "BKE_animsys.h"
55 #include "BKE_curve.h"
56 #include "BKE_customdata.h"
57 #include "BKE_deform.h"
58 #include "BKE_global.h"
59 #include "BKE_key.h"
60 #include "BKE_lattice.h"
61 #include "BKE_library.h"
62 #include "BKE_main.h"
63 #include "BKE_mesh.h"
64 #include "BKE_editmesh.h"
65 #include "BKE_scene.h"
66
67
68 #include "RNA_access.h"
69
70 #define KEY_MODE_DUMMY      0 /* use where mode isn't checked for */
71 #define KEY_MODE_BPOINT     1
72 #define KEY_MODE_BEZTRIPLE  2
73
74 /* old defines from DNA_ipo_types.h for data-type, stored in DNA - don't modify! */
75 #define IPO_FLOAT       4
76 #define IPO_BEZTRIPLE   100
77 #define IPO_BPOINT      101
78
79 /* Internal use only. */
80 typedef struct WeightsArrayCache {
81         int num_defgroup_weights;
82         float **defgroup_weights;
83 } WeightsArrayCache;
84
85
86 /** Free (or release) any data used by this shapekey (does not free the key itself). */
87 void BKE_key_free(Key *key)
88 {
89         KeyBlock *kb;
90
91         BKE_animdata_free((ID *)key, false);
92
93         while ((kb = BLI_pophead(&key->block))) {
94                 if (kb->data)
95                         MEM_freeN(kb->data);
96                 MEM_freeN(kb);
97         }
98 }
99
100 void BKE_key_free_nolib(Key *key)
101 {
102         KeyBlock *kb;
103
104         while ((kb = BLI_pophead(&key->block))) {
105                 if (kb->data)
106                         MEM_freeN(kb->data);
107                 MEM_freeN(kb);
108         }
109 }
110
111 Key *BKE_key_add(Main *bmain, ID *id)    /* common function */
112 {
113         Key *key;
114         char *el;
115
116         key = BKE_libblock_alloc(bmain, ID_KE, "Key", 0);
117
118         key->type = KEY_NORMAL;
119         key->from = id;
120
121         key->uidgen = 1;
122
123         /* XXX the code here uses some defines which will soon be deprecated... */
124         switch (GS(id->name)) {
125                 case ID_ME:
126                         el = key->elemstr;
127
128                         el[0] = KEYELEM_FLOAT_LEN_COORD;
129                         el[1] = IPO_FLOAT;
130                         el[2] = 0;
131
132                         key->elemsize = sizeof(float[KEYELEM_FLOAT_LEN_COORD]);
133
134                         break;
135                 case ID_LT:
136                         el = key->elemstr;
137
138                         el[0] = KEYELEM_FLOAT_LEN_COORD;
139                         el[1] = IPO_FLOAT;
140                         el[2] = 0;
141
142                         key->elemsize = sizeof(float[KEYELEM_FLOAT_LEN_COORD]);
143
144                         break;
145                 case ID_CU:
146                         el = key->elemstr;
147
148                         el[0] = KEYELEM_ELEM_SIZE_CURVE;
149                         el[1] = IPO_BPOINT;
150                         el[2] = 0;
151
152                         key->elemsize = sizeof(float[KEYELEM_ELEM_SIZE_CURVE]);
153
154                         break;
155
156                 default:
157                         break;
158         }
159
160         return key;
161 }
162
163 /**
164  * Only copy internal data of ShapeKey ID from source to already allocated/initialized destination.
165  * You probably nerver want to use that directly, use id_copy or BKE_id_copy_ex for typical needs.
166  *
167  * WARNING! This function will not handle ID user count!
168  *
169  * \param flag: Copying options (see BKE_library.h's LIB_ID_COPY_... flags for more).
170  */
171 void BKE_key_copy_data(Main *UNUSED(bmain), Key *key_dst, const Key *key_src, const int UNUSED(flag))
172 {
173         BLI_duplicatelist(&key_dst->block, &key_src->block);
174
175         KeyBlock *kb_dst, *kb_src;
176         for (kb_src = key_src->block.first, kb_dst = key_dst->block.first;
177              kb_dst;
178              kb_src = kb_src->next, kb_dst = kb_dst->next)
179         {
180                 if (kb_dst->data) {
181                         kb_dst->data = MEM_dupallocN(kb_dst->data);
182                 }
183                 if (kb_src == key_src->refkey) {
184                         key_dst->refkey = kb_dst;
185                 }
186         }
187 }
188
189 Key *BKE_key_copy(Main *bmain, const Key *key)
190 {
191         Key *key_copy;
192         BKE_id_copy_ex(bmain, &key->id, (ID **)&key_copy, 0, false);
193         return key_copy;
194 }
195
196 /* XXX TODO get rid of this! */
197 Key *BKE_key_copy_nolib(Key *key)
198 {
199         Key *keyn;
200         KeyBlock *kbn, *kb;
201
202         keyn = MEM_dupallocN(key);
203
204         keyn->adt = NULL;
205
206         BLI_duplicatelist(&keyn->block, &key->block);
207
208         kb = key->block.first;
209         kbn = keyn->block.first;
210         while (kbn) {
211
212                 if (kbn->data) kbn->data = MEM_dupallocN(kbn->data);
213                 if (kb == key->refkey) keyn->refkey = kbn;
214
215                 kbn = kbn->next;
216                 kb = kb->next;
217         }
218
219         return keyn;
220 }
221
222 /* Sort shape keys and Ipo curves after a change.  This assumes that at most
223  * one key was moved, which is a valid assumption for the places it's
224  * currently being called.
225  */
226
227 void BKE_key_sort(Key *key)
228 {
229         KeyBlock *kb;
230         KeyBlock *kb2;
231
232         /* locate the key which is out of position */
233         for (kb = key->block.first; kb; kb = kb->next)
234                 if ((kb->next) && (kb->pos > kb->next->pos))
235                         break;
236
237         /* if we find a key, move it */
238         if (kb) {
239                 kb = kb->next; /* next key is the out-of-order one */
240                 BLI_remlink(&key->block, kb);
241
242                 /* find the right location and insert before */
243                 for (kb2 = key->block.first; kb2; kb2 = kb2->next) {
244                         if (kb2->pos > kb->pos) {
245                                 BLI_insertlinkafter(&key->block, kb2->prev, kb);
246                                 break;
247                         }
248                 }
249         }
250
251         /* new rule; first key is refkey, this to match drawing channels... */
252         key->refkey = key->block.first;
253 }
254
255 /**************** do the key ****************/
256
257 void key_curve_position_weights(float t, float data[4], int type)
258 {
259         float t2, t3, fc;
260
261         if (type == KEY_LINEAR) {
262                 data[0] =          0.0f;
263                 data[1] = -t     + 1.0f;
264                 data[2] =  t;
265                 data[3] =          0.0f;
266         }
267         else if (type == KEY_CARDINAL) {
268                 t2 = t * t;
269                 t3 = t2 * t;
270                 fc = 0.71f;
271
272                 data[0] = -fc          * t3  + 2.0f * fc          * t2 - fc * t;
273                 data[1] =  (2.0f - fc) * t3  + (fc - 3.0f)        * t2 + 1.0f;
274                 data[2] =  (fc - 2.0f) * t3  + (3.0f - 2.0f * fc) * t2 + fc * t;
275                 data[3] =  fc          * t3  - fc * t2;
276         }
277         else if (type == KEY_BSPLINE) {
278                 t2 = t * t;
279                 t3 = t2 * t;
280
281                 data[0] = -0.16666666f * t3  + 0.5f * t2   - 0.5f * t    + 0.16666666f;
282                 data[1] =  0.5f        * t3  - t2                        + 0.66666666f;
283                 data[2] = -0.5f        * t3  + 0.5f * t2   + 0.5f * t    + 0.16666666f;
284                 data[3] =  0.16666666f * t3;
285         }
286         else if (type == KEY_CATMULL_ROM) {
287                 t2 = t * t;
288                 t3 = t2 * t;
289                 fc = 0.5f;
290
291                 data[0] = -fc          * t3  + 2.0f * fc          * t2 - fc * t;
292                 data[1] =  (2.0f - fc) * t3  + (fc - 3.0f)        * t2 + 1.0f;
293                 data[2] =  (fc - 2.0f) * t3  + (3.0f - 2.0f * fc) * t2 + fc * t;
294                 data[3] =  fc          * t3  - fc * t2;
295         }
296 }
297
298 /* first derivative */
299 void key_curve_tangent_weights(float t, float data[4], int type)
300 {
301         float t2, fc;
302
303         if (type == KEY_LINEAR) {
304                 data[0] = 0.0f;
305                 data[1] = -1.0f;
306                 data[2] = 1.0f;
307                 data[3] = 0.0f;
308         }
309         else if (type == KEY_CARDINAL) {
310                 t2 = t * t;
311                 fc = 0.71f;
312
313                 data[0] = -3.0f * fc          * t2  + 4.0f * fc * t                  - fc;
314                 data[1] =  3.0f * (2.0f - fc) * t2  + 2.0f * (fc - 3.0f) * t;
315                 data[2] =  3.0f * (fc - 2.0f) * t2  + 2.0f * (3.0f - 2.0f * fc) * t  + fc;
316                 data[3] =  3.0f * fc          * t2  - 2.0f * fc * t;
317         }
318         else if (type == KEY_BSPLINE) {
319                 t2 = t * t;
320
321                 data[0] = -0.5f * t2  + t         - 0.5f;
322                 data[1] =  1.5f * t2  - t * 2.0f;
323                 data[2] = -1.5f * t2  + t         + 0.5f;
324                 data[3] =  0.5f * t2;
325         }
326         else if (type == KEY_CATMULL_ROM) {
327                 t2 = t * t;
328                 fc = 0.5f;
329
330                 data[0] = -3.0f * fc          * t2  + 4.0f * fc * t                  - fc;
331                 data[1] =  3.0f * (2.0f - fc) * t2  + 2.0f * (fc - 3.0f) * t;
332                 data[2] =  3.0f * (fc - 2.0f) * t2  + 2.0f * (3.0f - 2.0f * fc) * t  + fc;
333                 data[3] =  3.0f * fc          * t2  - 2.0f * fc * t;
334         }
335 }
336
337 /* second derivative */
338 void key_curve_normal_weights(float t, float data[4], int type)
339 {
340         float fc;
341
342         if (type == KEY_LINEAR) {
343                 data[0] = 0.0f;
344                 data[1] = 0.0f;
345                 data[2] = 0.0f;
346                 data[3] = 0.0f;
347         }
348         else if (type == KEY_CARDINAL) {
349                 fc = 0.71f;
350
351                 data[0] = -6.0f * fc          * t  + 4.0f * fc;
352                 data[1] =  6.0f * (2.0f - fc) * t  + 2.0f * (fc - 3.0f);
353                 data[2] =  6.0f * (fc - 2.0f) * t  + 2.0f * (3.0f - 2.0f * fc);
354                 data[3] =  6.0f * fc          * t  - 2.0f * fc;
355         }
356         else if (type == KEY_BSPLINE) {
357                 data[0] = -1.0f * t  + 1.0f;
358                 data[1] =  3.0f * t  - 2.0f;
359                 data[2] = -3.0f * t  + 1.0f;
360                 data[3] =  1.0f * t;
361         }
362         else if (type == KEY_CATMULL_ROM) {
363                 fc = 0.5f;
364
365                 data[0] = -6.0f * fc          * t  + 4.0f * fc;
366                 data[1] =  6.0f * (2.0f - fc) * t  + 2.0f * (fc - 3.0f);
367                 data[2] =  6.0f * (fc - 2.0f) * t  + 2.0f * (3.0f - 2.0f * fc);
368                 data[3] =  6.0f * fc          * t  - 2.0f * fc;
369         }
370 }
371
372 static int setkeys(float fac, ListBase *lb, KeyBlock *k[], float t[4], int cycl)
373 {
374         /* return 1 means k[2] is the position, return 0 means interpolate */
375         KeyBlock *k1, *firstkey;
376         float d, dpos, ofs = 0, lastpos;
377         short bsplinetype;
378
379         firstkey = lb->first;
380         k1 = lb->last;
381         lastpos = k1->pos;
382         dpos = lastpos - firstkey->pos;
383
384         if (fac < firstkey->pos) fac = firstkey->pos;
385         else if (fac > k1->pos) fac = k1->pos;
386
387         k1 = k[0] = k[1] = k[2] = k[3] = firstkey;
388         t[0] = t[1] = t[2] = t[3] = k1->pos;
389
390         /* if (fac < 0.0 || fac > 1.0) return 1; */
391
392         if (k1->next == NULL) return 1;
393
394         if (cycl) { /* pre-sort */
395                 k[2] = k1->next;
396                 k[3] = k[2]->next;
397                 if (k[3] == NULL) k[3] = k1;
398                 while (k1) {
399                         if (k1->next == NULL) k[0] = k1;
400                         k1 = k1->next;
401                 }
402                 /* k1 = k[1]; */ /* UNUSED */
403                 t[0] = k[0]->pos;
404                 t[1] += dpos;
405                 t[2] = k[2]->pos + dpos;
406                 t[3] = k[3]->pos + dpos;
407                 fac += dpos;
408                 ofs = dpos;
409                 if (k[3] == k[1]) {
410                         t[3] += dpos;
411                         ofs = 2.0f * dpos;
412                 }
413                 if (fac < t[1]) fac += dpos;
414                 k1 = k[3];
415         }
416         else {  /* pre-sort */
417                 k[2] = k1->next;
418                 t[2] = k[2]->pos;
419                 k[3] = k[2]->next;
420                 if (k[3] == NULL) k[3] = k[2];
421                 t[3] = k[3]->pos;
422                 k1 = k[3];
423         }
424
425         while (t[2] < fac) {    /* find correct location */
426                 if (k1->next == NULL) {
427                         if (cycl) {
428                                 k1 = firstkey;
429                                 ofs += dpos;
430                         }
431                         else if (t[2] == t[3]) {
432                                 break;
433                         }
434                 }
435                 else {
436                         k1 = k1->next;
437                 }
438
439                 t[0] = t[1];
440                 k[0] = k[1];
441                 t[1] = t[2];
442                 k[1] = k[2];
443                 t[2] = t[3];
444                 k[2] = k[3];
445                 t[3] = k1->pos + ofs;
446                 k[3] = k1;
447
448                 if (ofs > 2.1f + lastpos) break;
449         }
450
451         bsplinetype = 0;
452         if (k[1]->type == KEY_BSPLINE || k[2]->type == KEY_BSPLINE) bsplinetype = 1;
453
454
455         if (cycl == 0) {
456                 if (bsplinetype == 0) {   /* B spline doesn't go through the control points */
457                         if (fac <= t[1]) {  /* fac for 1st key */
458                                 t[2] = t[1];
459                                 k[2] = k[1];
460                                 return 1;
461                         }
462                         if (fac >= t[2]) {  /* fac after 2nd key */
463                                 return 1;
464                         }
465                 }
466                 else if (fac > t[2]) {  /* last key */
467                         fac = t[2];
468                         k[3] = k[2];
469                         t[3] = t[2];
470                 }
471         }
472
473         d = t[2] - t[1];
474         if (d == 0.0f) {
475                 if (bsplinetype == 0) {
476                         return 1;  /* both keys equal */
477                 }
478         }
479         else {
480                 d = (fac - t[1]) / d;
481         }
482
483         /* interpolation */
484         key_curve_position_weights(d, t, k[1]->type);
485
486         if (k[1]->type != k[2]->type) {
487                 float t_other[4];
488                 key_curve_position_weights(d, t_other, k[2]->type);
489                 interp_v4_v4v4(t, t, t_other, d);
490         }
491
492         return 0;
493
494 }
495
496 static void flerp(int tot, float *in, float *f0, float *f1, float *f2, float *f3, float *t)
497 {
498         int a;
499
500         for (a = 0; a < tot; a++) {
501                 in[a] = t[0] * f0[a] + t[1] * f1[a] + t[2] * f2[a] + t[3] * f3[a];
502         }
503 }
504
505 static void rel_flerp(int tot, float *in, float *ref, float *out, float fac)
506 {
507         int a;
508
509         for (a = 0; a < tot; a++) {
510                 in[a] -= fac * (ref[a] - out[a]);
511         }
512 }
513
514 static char *key_block_get_data(Key *key, KeyBlock *actkb, KeyBlock *kb, char **freedata)
515 {
516         if (kb == actkb) {
517                 /* this hack makes it possible to edit shape keys in
518                  * edit mode with shape keys blending applied */
519                 if (GS(key->from->name) == ID_ME) {
520                         Mesh *me;
521                         BMVert *eve;
522                         BMIter iter;
523                         float (*co)[3];
524                         int a;
525
526                         me = (Mesh *)key->from;
527
528                         if (me->edit_btmesh && me->edit_btmesh->bm->totvert == kb->totelem) {
529                                 a = 0;
530                                 co = MEM_mallocN(sizeof(float) * 3 * me->edit_btmesh->bm->totvert, "key_block_get_data");
531
532                                 BM_ITER_MESH (eve, &iter, me->edit_btmesh->bm, BM_VERTS_OF_MESH) {
533                                         copy_v3_v3(co[a], eve->co);
534                                         a++;
535                                 }
536
537                                 *freedata = (char *)co;
538                                 return (char *)co;
539                         }
540                 }
541         }
542
543         *freedata = NULL;
544         return kb->data;
545 }
546
547
548 /* currently only the first value of 'ofs' may be set. */
549 static bool key_pointer_size(const Key *key, const int mode, int *poinsize, int *ofs, int *step)
550 {
551         if (key->from == NULL) {
552                 return false;
553         }
554
555         *step = 1;
556
557         switch (GS(key->from->name)) {
558                 case ID_ME:
559                         *ofs = sizeof(float[KEYELEM_FLOAT_LEN_COORD]);
560                         *poinsize = *ofs;
561                         break;
562                 case ID_LT:
563                         *ofs = sizeof(float[KEYELEM_FLOAT_LEN_COORD]);
564                         *poinsize = *ofs;
565                         break;
566                 case ID_CU:
567                         if (mode == KEY_MODE_BPOINT) {
568                                 *ofs = sizeof(float[KEYELEM_FLOAT_LEN_BPOINT]);
569                                 *step = KEYELEM_ELEM_LEN_BPOINT;
570                         }
571                         else {
572                                 *ofs = sizeof(float[KEYELEM_FLOAT_LEN_BEZTRIPLE]);
573                                 *step = KEYELEM_ELEM_LEN_BEZTRIPLE;
574                         }
575                         *poinsize = sizeof(float[KEYELEM_ELEM_SIZE_CURVE]);
576                         break;
577                 default:
578                         BLI_assert(!"invalid 'key->from' ID type");
579                         return false;
580         }
581
582         return true;
583 }
584
585 static void cp_key(const int start, int end, const int tot, char *poin, Key *key, KeyBlock *actkb, KeyBlock *kb, float *weights, const int mode)
586 {
587         float ktot = 0.0, kd = 0.0;
588         int elemsize, poinsize = 0, a, step, *ofsp, ofs[32], flagflo = 0;
589         char *k1, *kref, *freek1, *freekref;
590         char *cp, elemstr[8];
591
592         /* currently always 0, in future key_pointer_size may assign */
593         ofs[1] = 0;
594
595         if (!key_pointer_size(key, mode, &poinsize, &ofs[0], &step))
596                 return;
597
598         if (end > tot) end = tot;
599
600         if (tot != kb->totelem) {
601                 ktot = 0.0;
602                 flagflo = 1;
603                 if (kb->totelem) {
604                         kd = kb->totelem / (float)tot;
605                 }
606                 else {
607                         return;
608                 }
609         }
610
611         k1 = key_block_get_data(key, actkb, kb, &freek1);
612         kref = key_block_get_data(key, actkb, key->refkey, &freekref);
613
614         /* this exception is needed curves with multiple splines */
615         if (start != 0) {
616
617                 poin += poinsize * start;
618
619                 if (flagflo) {
620                         ktot += start * kd;
621                         a = (int)floor(ktot);
622                         if (a) {
623                                 ktot -= a;
624                                 k1 += a * key->elemsize;
625                         }
626                 }
627                 else {
628                         k1 += start * key->elemsize;
629                 }
630         }
631
632         if (mode == KEY_MODE_BEZTRIPLE) {
633                 elemstr[0] = 1;
634                 elemstr[1] = IPO_BEZTRIPLE;
635                 elemstr[2] = 0;
636         }
637
638         /* just do it here, not above! */
639         elemsize = key->elemsize * step;
640
641         for (a = start; a < end; a += step) {
642                 cp = key->elemstr;
643                 if (mode == KEY_MODE_BEZTRIPLE) cp = elemstr;
644
645                 ofsp = ofs;
646
647                 while (cp[0]) {
648
649                         switch (cp[1]) {
650                                 case IPO_FLOAT:
651                                         if (weights) {
652                                                 memcpy(poin, kref, sizeof(float[KEYELEM_FLOAT_LEN_COORD]));
653                                                 if (*weights != 0.0f)
654                                                         rel_flerp(KEYELEM_FLOAT_LEN_COORD, (float *)poin, (float *)kref, (float *)k1, *weights);
655                                                 weights++;
656                                         }
657                                         else {
658                                                 memcpy(poin, k1, sizeof(float[KEYELEM_FLOAT_LEN_COORD]));
659                                         }
660                                         break;
661                                 case IPO_BPOINT:
662                                         memcpy(poin, k1, sizeof(float[KEYELEM_FLOAT_LEN_BPOINT]));
663                                         break;
664                                 case IPO_BEZTRIPLE:
665                                         memcpy(poin, k1, sizeof(float[KEYELEM_FLOAT_LEN_BEZTRIPLE]));
666                                         break;
667                                 default:
668                                         /* should never happen */
669                                         if (freek1) MEM_freeN(freek1);
670                                         if (freekref) MEM_freeN(freekref);
671                                         BLI_assert(!"invalid 'cp[1]'");
672                                         return;
673                         }
674
675                         poin += *ofsp;
676                         cp += 2; ofsp++;
677                 }
678
679                 /* are we going to be nasty? */
680                 if (flagflo) {
681                         ktot += kd;
682                         while (ktot >= 1.0f) {
683                                 ktot -= 1.0f;
684                                 k1 += elemsize;
685                                 kref += elemsize;
686                         }
687                 }
688                 else {
689                         k1 += elemsize;
690                         kref += elemsize;
691                 }
692         }
693
694         if (freek1) MEM_freeN(freek1);
695         if (freekref) MEM_freeN(freekref);
696 }
697
698 static void cp_cu_key(Curve *cu, Key *key, KeyBlock *actkb, KeyBlock *kb, const int start, int end, char *out, const int tot)
699 {
700         Nurb *nu;
701         int a, step, a1, a2;
702
703         for (a = 0, nu = cu->nurb.first; nu; nu = nu->next, a += step) {
704                 if (nu->bp) {
705                         step = KEYELEM_ELEM_LEN_BPOINT * nu->pntsu * nu->pntsv;
706
707                         a1 = max_ii(a, start);
708                         a2 = min_ii(a + step, end);
709
710                         if (a1 < a2) cp_key(a1, a2, tot, out, key, actkb, kb, NULL, KEY_MODE_BPOINT);
711                 }
712                 else if (nu->bezt) {
713                         step = KEYELEM_ELEM_LEN_BEZTRIPLE * nu->pntsu;
714
715                         /* exception because keys prefer to work with complete blocks */
716                         a1 = max_ii(a, start);
717                         a2 = min_ii(a + step, end);
718
719                         if (a1 < a2) cp_key(a1, a2, tot, out, key, actkb, kb, NULL, KEY_MODE_BEZTRIPLE);
720                 }
721                 else {
722                         step = 0;
723                 }
724         }
725 }
726
727 static void key_evaluate_relative(
728         const int start, int end, const int tot, char *basispoin, Key *key, KeyBlock *actkb,
729         float **per_keyblock_weights, const int mode)
730 {
731         KeyBlock *kb;
732         int *ofsp, ofs[3], elemsize, b, step;
733         char *cp, *poin, *reffrom, *from, elemstr[8];
734         int poinsize, keyblock_index;
735
736         /* currently always 0, in future key_pointer_size may assign */
737         ofs[1] = 0;
738
739         if (!key_pointer_size(key, mode, &poinsize, &ofs[0], &step))
740                 return;
741
742         if (end > tot) end = tot;
743
744         /* in case of beztriple */
745         elemstr[0] = 1;              /* nr of ipofloats */
746         elemstr[1] = IPO_BEZTRIPLE;
747         elemstr[2] = 0;
748
749         /* just here, not above! */
750         elemsize = key->elemsize * step;
751
752         /* step 1 init */
753         cp_key(start, end, tot, basispoin, key, actkb, key->refkey, NULL, mode);
754
755         /* step 2: do it */
756
757         for (kb = key->block.first, keyblock_index = 0; kb; kb = kb->next, keyblock_index++) {
758                 if (kb != key->refkey) {
759                         float icuval = kb->curval;
760
761                         /* only with value, and no difference allowed */
762                         if (!(kb->flag & KEYBLOCK_MUTE) && icuval != 0.0f && kb->totelem == tot) {
763                                 KeyBlock *refb;
764                                 float weight, *weights = per_keyblock_weights ? per_keyblock_weights[keyblock_index] : NULL;
765                                 char *freefrom = NULL, *freereffrom = NULL;
766
767                                 /* reference now can be any block */
768                                 refb = BLI_findlink(&key->block, kb->relative);
769                                 if (refb == NULL) continue;
770
771                                 poin = basispoin;
772                                 from = key_block_get_data(key, actkb, kb, &freefrom);
773                                 reffrom = key_block_get_data(key, actkb, refb, &freereffrom);
774
775                                 poin += start * poinsize;
776                                 reffrom += key->elemsize * start;  // key elemsize yes!
777                                 from += key->elemsize * start;
778
779                                 for (b = start; b < end; b += step) {
780
781                                         weight = weights ? (*weights * icuval) : icuval;
782
783                                         cp = key->elemstr;
784                                         if (mode == KEY_MODE_BEZTRIPLE) cp = elemstr;
785
786                                         ofsp = ofs;
787
788                                         while (cp[0]) {  /* (cp[0] == amount) */
789
790                                                 switch (cp[1]) {
791                                                         case IPO_FLOAT:
792                                                                 rel_flerp(KEYELEM_FLOAT_LEN_COORD, (float *)poin, (float *)reffrom, (float *)from, weight);
793                                                                 break;
794                                                         case IPO_BPOINT:
795                                                                 rel_flerp(KEYELEM_FLOAT_LEN_BPOINT, (float *)poin, (float *)reffrom, (float *)from, weight);
796                                                                 break;
797                                                         case IPO_BEZTRIPLE:
798                                                                 rel_flerp(KEYELEM_FLOAT_LEN_BEZTRIPLE, (float *)poin, (float *)reffrom, (float *)from, weight);
799                                                                 break;
800                                                         default:
801                                                                 /* should never happen */
802                                                                 if (freefrom) MEM_freeN(freefrom);
803                                                                 if (freereffrom) MEM_freeN(freereffrom);
804                                                                 BLI_assert(!"invalid 'cp[1]'");
805                                                                 return;
806                                                 }
807
808                                                 poin += *ofsp;
809
810                                                 cp += 2;
811                                                 ofsp++;
812                                         }
813
814                                         reffrom += elemsize;
815                                         from += elemsize;
816
817                                         if (weights) weights++;
818                                 }
819
820                                 if (freefrom) MEM_freeN(freefrom);
821                                 if (freereffrom) MEM_freeN(freereffrom);
822                         }
823                 }
824         }
825 }
826
827
828 static void do_key(const int start, int end, const int tot, char *poin, Key *key, KeyBlock *actkb, KeyBlock **k, float *t, const int mode)
829 {
830         float k1tot = 0.0, k2tot = 0.0, k3tot = 0.0, k4tot = 0.0;
831         float k1d = 0.0, k2d = 0.0, k3d = 0.0, k4d = 0.0;
832         int a, step, ofs[32], *ofsp;
833         int flagdo = 15, flagflo = 0, elemsize, poinsize = 0;
834         char *k1, *k2, *k3, *k4, *freek1, *freek2, *freek3, *freek4;
835         char *cp, elemstr[8];
836
837         /* currently always 0, in future key_pointer_size may assign */
838         ofs[1] = 0;
839
840         if (!key_pointer_size(key, mode, &poinsize, &ofs[0], &step))
841                 return;
842
843         if (end > tot) end = tot;
844
845         k1 = key_block_get_data(key, actkb, k[0], &freek1);
846         k2 = key_block_get_data(key, actkb, k[1], &freek2);
847         k3 = key_block_get_data(key, actkb, k[2], &freek3);
848         k4 = key_block_get_data(key, actkb, k[3], &freek4);
849
850         /*  test for more or less points (per key!) */
851         if (tot != k[0]->totelem) {
852                 k1tot = 0.0;
853                 flagflo |= 1;
854                 if (k[0]->totelem) {
855                         k1d = k[0]->totelem / (float)tot;
856                 }
857                 else {
858                         flagdo -= 1;
859                 }
860         }
861         if (tot != k[1]->totelem) {
862                 k2tot = 0.0;
863                 flagflo |= 2;
864                 if (k[0]->totelem) {
865                         k2d = k[1]->totelem / (float)tot;
866                 }
867                 else {
868                         flagdo -= 2;
869                 }
870         }
871         if (tot != k[2]->totelem) {
872                 k3tot = 0.0;
873                 flagflo |= 4;
874                 if (k[0]->totelem) {
875                         k3d = k[2]->totelem / (float)tot;
876                 }
877                 else {
878                         flagdo -= 4;
879                 }
880         }
881         if (tot != k[3]->totelem) {
882                 k4tot = 0.0;
883                 flagflo |= 8;
884                 if (k[0]->totelem) {
885                         k4d = k[3]->totelem / (float)tot;
886                 }
887                 else {
888                         flagdo -= 8;
889                 }
890         }
891
892         /* this exception is needed for curves with multiple splines */
893         if (start != 0) {
894
895                 poin += poinsize * start;
896
897                 if (flagdo & 1) {
898                         if (flagflo & 1) {
899                                 k1tot += start * k1d;
900                                 a = (int)floor(k1tot);
901                                 if (a) {
902                                         k1tot -= a;
903                                         k1 += a * key->elemsize;
904                                 }
905                         }
906                         else {
907                                 k1 += start * key->elemsize;
908                         }
909                 }
910                 if (flagdo & 2) {
911                         if (flagflo & 2) {
912                                 k2tot += start * k2d;
913                                 a = (int)floor(k2tot);
914                                 if (a) {
915                                         k2tot -= a;
916                                         k2 += a * key->elemsize;
917                                 }
918                         }
919                         else {
920                                 k2 += start * key->elemsize;
921                         }
922                 }
923                 if (flagdo & 4) {
924                         if (flagflo & 4) {
925                                 k3tot += start * k3d;
926                                 a = (int)floor(k3tot);
927                                 if (a) {
928                                         k3tot -= a;
929                                         k3 += a * key->elemsize;
930                                 }
931                         }
932                         else {
933                                 k3 += start * key->elemsize;
934                         }
935                 }
936                 if (flagdo & 8) {
937                         if (flagflo & 8) {
938                                 k4tot += start * k4d;
939                                 a = (int)floor(k4tot);
940                                 if (a) {
941                                         k4tot -= a;
942                                         k4 += a * key->elemsize;
943                                 }
944                         }
945                         else {
946                                 k4 += start * key->elemsize;
947                         }
948                 }
949
950         }
951
952         /* in case of beztriple */
953         elemstr[0] = 1;              /* nr of ipofloats */
954         elemstr[1] = IPO_BEZTRIPLE;
955         elemstr[2] = 0;
956
957         /* only here, not above! */
958         elemsize = key->elemsize * step;
959
960         for (a = start; a < end; a += step) {
961                 cp = key->elemstr;
962                 if (mode == KEY_MODE_BEZTRIPLE) cp = elemstr;
963
964                 ofsp = ofs;
965
966                 while (cp[0]) {  /* (cp[0] == amount) */
967
968                         switch (cp[1]) {
969                                 case IPO_FLOAT:
970                                         flerp(KEYELEM_FLOAT_LEN_COORD, (float *)poin, (float *)k1, (float *)k2, (float *)k3, (float *)k4, t);
971                                         break;
972                                 case IPO_BPOINT:
973                                         flerp(KEYELEM_FLOAT_LEN_BPOINT, (float *)poin, (float *)k1, (float *)k2, (float *)k3, (float *)k4, t);
974                                         break;
975                                 case IPO_BEZTRIPLE:
976                                         flerp(KEYELEM_FLOAT_LEN_BEZTRIPLE, (void *)poin, (void *)k1, (void *)k2, (void *)k3, (void *)k4, t);
977                                         break;
978                                 default:
979                                         /* should never happen */
980                                         if (freek1) MEM_freeN(freek1);
981                                         if (freek2) MEM_freeN(freek2);
982                                         if (freek3) MEM_freeN(freek3);
983                                         if (freek4) MEM_freeN(freek4);
984                                         BLI_assert(!"invalid 'cp[1]'");
985                                         return;
986                         }
987
988                         poin += *ofsp;
989                         cp += 2;
990                         ofsp++;
991                 }
992                 /* lets do it the difficult way: when keys have a different size */
993                 if (flagdo & 1) {
994                         if (flagflo & 1) {
995                                 k1tot += k1d;
996                                 while (k1tot >= 1.0f) {
997                                         k1tot -= 1.0f;
998                                         k1 += elemsize;
999                                 }
1000                         }
1001                         else {
1002                                 k1 += elemsize;
1003                         }
1004                 }
1005                 if (flagdo & 2) {
1006                         if (flagflo & 2) {
1007                                 k2tot += k2d;
1008                                 while (k2tot >= 1.0f) {
1009                                         k2tot -= 1.0f;
1010                                         k2 += elemsize;
1011                                 }
1012                         }
1013                         else {
1014                                 k2 += elemsize;
1015                         }
1016                 }
1017                 if (flagdo & 4) {
1018                         if (flagflo & 4) {
1019                                 k3tot += k3d;
1020                                 while (k3tot >= 1.0f) {
1021                                         k3tot -= 1.0f;
1022                                         k3 += elemsize;
1023                                 }
1024                         }
1025                         else {
1026                                 k3 += elemsize;
1027                         }
1028                 }
1029                 if (flagdo & 8) {
1030                         if (flagflo & 8) {
1031                                 k4tot += k4d;
1032                                 while (k4tot >= 1.0f) {
1033                                         k4tot -= 1.0f;
1034                                         k4 += elemsize;
1035                                 }
1036                         }
1037                         else {
1038                                 k4 += elemsize;
1039                         }
1040                 }
1041         }
1042
1043         if (freek1) MEM_freeN(freek1);
1044         if (freek2) MEM_freeN(freek2);
1045         if (freek3) MEM_freeN(freek3);
1046         if (freek4) MEM_freeN(freek4);
1047 }
1048
1049 static float *get_weights_array(Object *ob, char *vgroup, WeightsArrayCache *cache)
1050 {
1051         MDeformVert *dvert = NULL;
1052         BMEditMesh *em = NULL;
1053         BMIter iter;
1054         BMVert *eve;
1055         int totvert = 0, defgrp_index = 0;
1056
1057         /* no vgroup string set? */
1058         if (vgroup[0] == 0) return NULL;
1059
1060         /* gather dvert and totvert */
1061         if (ob->type == OB_MESH) {
1062                 Mesh *me = ob->data;
1063                 dvert = me->dvert;
1064                 totvert = me->totvert;
1065
1066                 if (me->edit_btmesh && me->edit_btmesh->bm->totvert == totvert)
1067                         em = me->edit_btmesh;
1068         }
1069         else if (ob->type == OB_LATTICE) {
1070                 Lattice *lt = ob->data;
1071                 dvert = lt->dvert;
1072                 totvert = lt->pntsu * lt->pntsv * lt->pntsw;
1073         }
1074
1075         if (dvert == NULL) return NULL;
1076
1077         /* find the group (weak loop-in-loop) */
1078         defgrp_index = defgroup_name_index(ob, vgroup);
1079         if (defgrp_index != -1) {
1080                 float *weights;
1081                 int i;
1082
1083                 if (cache) {
1084                         if (cache->defgroup_weights == NULL) {
1085                                 int num_defgroup = BLI_listbase_count(&ob->defbase);
1086                                 cache->defgroup_weights =
1087                                     MEM_callocN(sizeof(*cache->defgroup_weights) * num_defgroup,
1088                                                 "cached defgroup weights");
1089                                 cache->num_defgroup_weights = num_defgroup;
1090                         }
1091
1092                         if (cache->defgroup_weights[defgrp_index]) {
1093                                 return cache->defgroup_weights[defgrp_index];
1094                         }
1095                 }
1096
1097                 weights = MEM_mallocN(totvert * sizeof(float), "weights");
1098
1099                 if (em) {
1100                         const int cd_dvert_offset = CustomData_get_offset(&em->bm->vdata, CD_MDEFORMVERT);
1101                         BM_ITER_MESH_INDEX (eve, &iter, em->bm, BM_VERTS_OF_MESH, i) {
1102                                 dvert = BM_ELEM_CD_GET_VOID_P(eve, cd_dvert_offset);
1103                                 weights[i] = defvert_find_weight(dvert, defgrp_index);
1104                         }
1105                 }
1106                 else {
1107                         for (i = 0; i < totvert; i++, dvert++) {
1108                                 weights[i] = defvert_find_weight(dvert, defgrp_index);
1109                         }
1110                 }
1111
1112                 if (cache) {
1113                         cache->defgroup_weights[defgrp_index] = weights;
1114                 }
1115
1116                 return weights;
1117         }
1118         return NULL;
1119 }
1120
1121 static float **keyblock_get_per_block_weights(Object *ob, Key *key, WeightsArrayCache *cache)
1122 {
1123         KeyBlock *keyblock;
1124         float **per_keyblock_weights;
1125         int keyblock_index;
1126
1127         per_keyblock_weights =
1128                 MEM_mallocN(sizeof(*per_keyblock_weights) * key->totkey,
1129                             "per keyblock weights");
1130
1131         for (keyblock = key->block.first, keyblock_index = 0;
1132              keyblock;
1133              keyblock = keyblock->next, keyblock_index++)
1134         {
1135                 per_keyblock_weights[keyblock_index] = get_weights_array(ob, keyblock->vgroup, cache);
1136         }
1137
1138         return per_keyblock_weights;
1139 }
1140
1141 static void keyblock_free_per_block_weights(Key *key, float **per_keyblock_weights, WeightsArrayCache *cache)
1142 {
1143         int a;
1144
1145         if (cache) {
1146                 if (cache->num_defgroup_weights) {
1147                         for (a = 0; a < cache->num_defgroup_weights; a++) {
1148                                 if (cache->defgroup_weights[a]) {
1149                                         MEM_freeN(cache->defgroup_weights[a]);
1150                                 }
1151                         }
1152                         MEM_freeN(cache->defgroup_weights);
1153                 }
1154                 cache->defgroup_weights = NULL;
1155         }
1156         else {
1157                 for (a = 0; a < key->totkey; a++) {
1158                         if (per_keyblock_weights[a]) {
1159                                 MEM_freeN(per_keyblock_weights[a]);
1160                         }
1161                 }
1162         }
1163
1164         MEM_freeN(per_keyblock_weights);
1165 }
1166
1167 static void do_mesh_key(Object *ob, Key *key, char *out, const int tot)
1168 {
1169         KeyBlock *k[4], *actkb = BKE_keyblock_from_object(ob);
1170         float t[4];
1171         int flag = 0;
1172
1173         if (key->type == KEY_RELATIVE) {
1174                 WeightsArrayCache cache = {0, NULL};
1175                 float **per_keyblock_weights;
1176                 per_keyblock_weights = keyblock_get_per_block_weights(ob, key, &cache);
1177                 key_evaluate_relative(0, tot, tot, (char *)out, key, actkb, per_keyblock_weights, KEY_MODE_DUMMY);
1178                 keyblock_free_per_block_weights(key, per_keyblock_weights, &cache);
1179         }
1180         else {
1181                 const float ctime_scaled = key->ctime / 100.0f;
1182
1183                 flag = setkeys(ctime_scaled, &key->block, k, t, 0);
1184
1185                 if (flag == 0) {
1186                         do_key(0, tot, tot, (char *)out, key, actkb, k, t, KEY_MODE_DUMMY);
1187                 }
1188                 else {
1189                         cp_key(0, tot, tot, (char *)out, key, actkb, k[2], NULL, KEY_MODE_DUMMY);
1190                 }
1191         }
1192 }
1193
1194 static void do_cu_key(Curve *cu, Key *key, KeyBlock *actkb, KeyBlock **k, float *t, char *out, const int tot)
1195 {
1196         Nurb *nu;
1197         int a, step;
1198
1199         for (a = 0, nu = cu->nurb.first; nu; nu = nu->next, a += step) {
1200                 if (nu->bp) {
1201                         step = KEYELEM_ELEM_LEN_BPOINT * nu->pntsu * nu->pntsv;
1202                         do_key(a, a + step, tot, out, key, actkb, k, t, KEY_MODE_BPOINT);
1203                 }
1204                 else if (nu->bezt) {
1205                         step = KEYELEM_ELEM_LEN_BEZTRIPLE * nu->pntsu;
1206                         do_key(a, a + step, tot, out, key, actkb, k, t, KEY_MODE_BEZTRIPLE);
1207                 }
1208                 else {
1209                         step = 0;
1210                 }
1211         }
1212 }
1213
1214 static void do_rel_cu_key(Curve *cu, Key *key, KeyBlock *actkb, char *out, const int tot)
1215 {
1216         Nurb *nu;
1217         int a, step;
1218
1219         for (a = 0, nu = cu->nurb.first; nu; nu = nu->next, a += step) {
1220                 if (nu->bp) {
1221                         step = KEYELEM_ELEM_LEN_BPOINT * nu->pntsu * nu->pntsv;
1222                         key_evaluate_relative(a, a + step, tot, out, key, actkb, NULL, KEY_MODE_BPOINT);
1223                 }
1224                 else if (nu->bezt) {
1225                         step = KEYELEM_ELEM_LEN_BEZTRIPLE * nu->pntsu;
1226                         key_evaluate_relative(a, a + step, tot, out, key, actkb, NULL, KEY_MODE_BEZTRIPLE);
1227                 }
1228                 else {
1229                         step = 0;
1230                 }
1231         }
1232 }
1233
1234 static void do_curve_key(Object *ob, Key *key, char *out, const int tot)
1235 {
1236         Curve *cu = ob->data;
1237         KeyBlock *k[4], *actkb = BKE_keyblock_from_object(ob);
1238         float t[4];
1239         int flag = 0;
1240
1241         if (key->type == KEY_RELATIVE) {
1242                 do_rel_cu_key(cu, cu->key, actkb, out, tot);
1243         }
1244         else {
1245                 const float ctime_scaled = key->ctime / 100.0f;
1246
1247                 flag = setkeys(ctime_scaled, &key->block, k, t, 0);
1248
1249                 if (flag == 0) {
1250                         do_cu_key(cu, key, actkb, k, t, out, tot);
1251                 }
1252                 else {
1253                         cp_cu_key(cu, key, actkb, k[2], 0, tot, out, tot);
1254                 }
1255         }
1256 }
1257
1258 static void do_latt_key(Object *ob, Key *key, char *out, const int tot)
1259 {
1260         Lattice *lt = ob->data;
1261         KeyBlock *k[4], *actkb = BKE_keyblock_from_object(ob);
1262         float t[4];
1263         int flag;
1264
1265         if (key->type == KEY_RELATIVE) {
1266                 float **per_keyblock_weights;
1267                 per_keyblock_weights = keyblock_get_per_block_weights(ob, key, NULL);
1268                 key_evaluate_relative(0, tot, tot, (char *)out, key, actkb, per_keyblock_weights, KEY_MODE_DUMMY);
1269                 keyblock_free_per_block_weights(key, per_keyblock_weights, NULL);
1270         }
1271         else {
1272                 const float ctime_scaled = key->ctime / 100.0f;
1273
1274                 flag = setkeys(ctime_scaled, &key->block, k, t, 0);
1275
1276                 if (flag == 0) {
1277                         do_key(0, tot, tot, (char *)out, key, actkb, k, t, KEY_MODE_DUMMY);
1278                 }
1279                 else {
1280                         cp_key(0, tot, tot, (char *)out, key, actkb, k[2], NULL, KEY_MODE_DUMMY);
1281                 }
1282         }
1283
1284         if (lt->flag & LT_OUTSIDE) outside_lattice(lt);
1285 }
1286
1287 /* returns key coordinates (+ tilt) when key applied, NULL otherwise */
1288 float *BKE_key_evaluate_object_ex(
1289         Object *ob, int *r_totelem,
1290         float *arr, size_t arr_size)
1291 {
1292         Key *key = BKE_key_from_object(ob);
1293         KeyBlock *actkb = BKE_keyblock_from_object(ob);
1294         char *out;
1295         int tot = 0, size = 0;
1296
1297         if (key == NULL || BLI_listbase_is_empty(&key->block))
1298                 return NULL;
1299
1300         /* compute size of output array */
1301         if (ob->type == OB_MESH) {
1302                 Mesh *me = ob->data;
1303
1304                 tot = me->totvert;
1305                 size = tot * sizeof(float[KEYELEM_FLOAT_LEN_COORD]);
1306         }
1307         else if (ob->type == OB_LATTICE) {
1308                 Lattice *lt = ob->data;
1309
1310                 tot = lt->pntsu * lt->pntsv * lt->pntsw;
1311                 size = tot * sizeof(float[KEYELEM_FLOAT_LEN_COORD]);
1312         }
1313         else if (ELEM(ob->type, OB_CURVE, OB_SURF)) {
1314                 Curve *cu = ob->data;
1315
1316                 tot = BKE_keyblock_curve_element_count(&cu->nurb);
1317                 size = tot * sizeof(float[KEYELEM_ELEM_SIZE_CURVE]);
1318         }
1319
1320         /* if nothing to interpolate, cancel */
1321         if (tot == 0 || size == 0)
1322                 return NULL;
1323
1324         /* allocate array */
1325         if (arr == NULL) {
1326                 out = MEM_callocN(size, "BKE_key_evaluate_object out");
1327         }
1328         else {
1329                 if (arr_size != size) {
1330                         return NULL;
1331                 }
1332
1333                 out = (char *)arr;
1334         }
1335
1336         /* prevent python from screwing this up? anyhoo, the from pointer could be dropped */
1337         key->from = (ID *)ob->data;
1338
1339         if (ob->shapeflag & OB_SHAPE_LOCK) {
1340                 /* shape locked, copy the locked shape instead of blending */
1341                 KeyBlock *kb = BLI_findlink(&key->block, ob->shapenr - 1);
1342
1343                 if (kb && (kb->flag & KEYBLOCK_MUTE))
1344                         kb = key->refkey;
1345
1346                 if (kb == NULL) {
1347                         kb = key->block.first;
1348                         ob->shapenr = 1;
1349                 }
1350
1351                 if (OB_TYPE_SUPPORT_VGROUP(ob->type)) {
1352                         float *weights = get_weights_array(ob, kb->vgroup, NULL);
1353
1354                         cp_key(0, tot, tot, out, key, actkb, kb, weights, 0);
1355
1356                         if (weights) MEM_freeN(weights);
1357                 }
1358                 else if (ELEM(ob->type, OB_CURVE, OB_SURF))
1359                         cp_cu_key(ob->data, key, actkb, kb, 0, tot, out, tot);
1360         }
1361         else {
1362
1363                 if (ob->type == OB_MESH) do_mesh_key(ob, key, out, tot);
1364                 else if (ob->type == OB_LATTICE) do_latt_key(ob, key, out, tot);
1365                 else if (ob->type == OB_CURVE) do_curve_key(ob, key, out, tot);
1366                 else if (ob->type == OB_SURF) do_curve_key(ob, key, out, tot);
1367         }
1368
1369         if (r_totelem) {
1370                 *r_totelem = tot;
1371         }
1372         return (float *)out;
1373 }
1374
1375 float *BKE_key_evaluate_object(Object *ob, int *r_totelem)
1376 {
1377         return BKE_key_evaluate_object_ex(ob, r_totelem, NULL, 0);
1378 }
1379
1380 Key **BKE_key_from_id_p(ID *id)
1381 {
1382         switch (GS(id->name)) {
1383                 case ID_ME:
1384                 {
1385                         Mesh *me = (Mesh *)id;
1386                         return &me->key;
1387                 }
1388                 case ID_CU:
1389                 {
1390                         Curve *cu = (Curve *)id;
1391                         if (cu->vfont == NULL) {
1392                                 return &cu->key;
1393                         }
1394                         break;
1395                 }
1396                 case ID_LT:
1397                 {
1398                         Lattice *lt = (Lattice *)id;
1399                         return &lt->key;
1400                 }
1401                 default:
1402                         break;
1403         }
1404
1405         return NULL;
1406 }
1407
1408 Key *BKE_key_from_id(ID *id)
1409 {
1410         Key **key_p;
1411         key_p = BKE_key_from_id_p(id);
1412         if (key_p) {
1413                 return *key_p;
1414         }
1415
1416         return NULL;
1417 }
1418
1419 Key **BKE_key_from_object_p(Object *ob)
1420 {
1421         if (ob == NULL || ob->data == NULL)
1422                 return NULL;
1423
1424         return BKE_key_from_id_p(ob->data);
1425 }
1426
1427 Key *BKE_key_from_object(Object *ob)
1428 {
1429         Key **key_p;
1430         key_p = BKE_key_from_object_p(ob);
1431         if (key_p) {
1432                 return *key_p;
1433         }
1434
1435         return NULL;
1436 }
1437
1438 KeyBlock *BKE_keyblock_add(Key *key, const char *name)
1439 {
1440         KeyBlock *kb;
1441         float curpos = -0.1;
1442         int tot;
1443
1444         kb = key->block.last;
1445         if (kb) curpos = kb->pos;
1446
1447         kb = MEM_callocN(sizeof(KeyBlock), "Keyblock");
1448         BLI_addtail(&key->block, kb);
1449         kb->type = KEY_LINEAR;
1450
1451         tot = BLI_listbase_count(&key->block);
1452         if (name) {
1453                 BLI_strncpy(kb->name, name, sizeof(kb->name));
1454         }
1455         else {
1456                 if (tot == 1)
1457                         BLI_strncpy(kb->name, DATA_("Basis"), sizeof(kb->name));
1458                 else
1459                         BLI_snprintf(kb->name, sizeof(kb->name), DATA_("Key %d"), tot - 1);
1460         }
1461
1462         BLI_uniquename(&key->block, kb, DATA_("Key"), '.', offsetof(KeyBlock, name), sizeof(kb->name));
1463
1464         kb->uid = key->uidgen++;
1465
1466         key->totkey++;
1467         if (key->totkey == 1) key->refkey = kb;
1468
1469         kb->slidermin = 0.0f;
1470         kb->slidermax = 1.0f;
1471
1472         /**
1473          * \note caller may want to set this to current time, but don't do it here since we need to sort
1474          * which could cause problems in some cases, see #BKE_keyblock_add_ctime */
1475         kb->pos = curpos + 0.1f; /* only used for absolute shape keys */
1476
1477         return kb;
1478 }
1479
1480 /**
1481  * \note sorting is a problematic side effect in some cases,
1482  * better only do this explicitly by having its own function,
1483  *
1484  * \param key: The key datablock to add to.
1485  * \param name: Optional name for the new keyblock.
1486  * \param do_force: always use ctime even for relative keys.
1487  */
1488 KeyBlock *BKE_keyblock_add_ctime(Key *key, const char *name, const bool do_force)
1489 {
1490         KeyBlock *kb = BKE_keyblock_add(key, name);
1491         const float cpos = key->ctime / 100.0f;
1492
1493         /* In case of absolute keys, there is no point in adding more than one key with the same pos.
1494          * Hence only set new keybloc pos to current time if none previous one already use it.
1495          * Now at least people just adding absolute keys without touching to ctime
1496          * won't have to systematically use retiming func (and have ordering issues, too). See T39897.
1497          */
1498         if (!do_force && (key->type != KEY_RELATIVE)) {
1499                 KeyBlock *it_kb;
1500                 for (it_kb = key->block.first; it_kb; it_kb = it_kb->next) {
1501                         if (it_kb->pos == cpos) {
1502                                 return kb;
1503                         }
1504                 }
1505         }
1506         if (do_force || (key->type != KEY_RELATIVE)) {
1507                 kb->pos = cpos;
1508                 BKE_key_sort(key);
1509         }
1510
1511         return kb;
1512 }
1513
1514 /* only the active keyblock */
1515 KeyBlock *BKE_keyblock_from_object(Object *ob)
1516 {
1517         Key *key = BKE_key_from_object(ob);
1518
1519         if (key) {
1520                 KeyBlock *kb = BLI_findlink(&key->block, ob->shapenr - 1);
1521                 return kb;
1522         }
1523
1524         return NULL;
1525 }
1526
1527 KeyBlock *BKE_keyblock_from_object_reference(Object *ob)
1528 {
1529         Key *key = BKE_key_from_object(ob);
1530
1531         if (key)
1532                 return key->refkey;
1533
1534         return NULL;
1535 }
1536
1537 /* get the appropriate KeyBlock given an index */
1538 KeyBlock *BKE_keyblock_from_key(Key *key, int index)
1539 {
1540         KeyBlock *kb;
1541         int i;
1542
1543         if (key) {
1544                 kb = key->block.first;
1545
1546                 for (i = 1; i < key->totkey; i++) {
1547                         kb = kb->next;
1548
1549                         if (index == i)
1550                                 return kb;
1551                 }
1552         }
1553
1554         return NULL;
1555 }
1556
1557 /* get the appropriate KeyBlock given a name to search for */
1558 KeyBlock *BKE_keyblock_find_name(Key *key, const char name[])
1559 {
1560         return BLI_findstring(&key->block, name, offsetof(KeyBlock, name));
1561 }
1562
1563 /**
1564  * \brief copy shape-key attributes, but not key data.or name/uid
1565  */
1566 void BKE_keyblock_copy_settings(KeyBlock *kb_dst, const KeyBlock *kb_src)
1567 {
1568         kb_dst->pos        = kb_src->pos;
1569         kb_dst->curval     = kb_src->curval;
1570         kb_dst->type       = kb_src->type;
1571         kb_dst->relative   = kb_src->relative;
1572         BLI_strncpy(kb_dst->vgroup, kb_src->vgroup, sizeof(kb_dst->vgroup));
1573         kb_dst->slidermin  = kb_src->slidermin;
1574         kb_dst->slidermax  = kb_src->slidermax;
1575 }
1576
1577 /* Get RNA-Path for 'value' setting of the given ShapeKey
1578  * NOTE: the user needs to free the returned string once they're finish with it
1579  */
1580 char *BKE_keyblock_curval_rnapath_get(Key *key, KeyBlock *kb)
1581 {
1582         PointerRNA ptr;
1583         PropertyRNA *prop;
1584
1585         /* sanity checks */
1586         if (ELEM(NULL, key, kb))
1587                 return NULL;
1588
1589         /* create the RNA pointer */
1590         RNA_pointer_create(&key->id, &RNA_ShapeKey, kb, &ptr);
1591         /* get pointer to the property too */
1592         prop = RNA_struct_find_property(&ptr, "value");
1593
1594         /* return the path */
1595         return RNA_path_from_ID_to_property(&ptr, prop);
1596 }
1597
1598
1599 /* conversion functions */
1600
1601 /************************* Lattice ************************/
1602 void BKE_keyblock_update_from_lattice(Lattice *lt, KeyBlock *kb)
1603 {
1604         BPoint *bp;
1605         float (*fp)[3];
1606         int a, tot;
1607
1608         BLI_assert(kb->totelem == lt->pntsu * lt->pntsv * lt->pntsw);
1609
1610         tot = kb->totelem;
1611         if (tot == 0) return;
1612
1613         bp = lt->def;
1614         fp = kb->data;
1615         for (a = 0; a < kb->totelem; a++, fp++, bp++) {
1616                 copy_v3_v3(*fp, bp->vec);
1617         }
1618 }
1619
1620 void BKE_keyblock_convert_from_lattice(Lattice *lt, KeyBlock *kb)
1621 {
1622         int tot;
1623
1624         tot = lt->pntsu * lt->pntsv * lt->pntsw;
1625         if (tot == 0) return;
1626
1627         MEM_SAFE_FREE(kb->data);
1628
1629         kb->data = MEM_mallocN(lt->key->elemsize * tot, __func__);
1630         kb->totelem = tot;
1631
1632         BKE_keyblock_update_from_lattice(lt, kb);
1633 }
1634
1635 void BKE_keyblock_convert_to_lattice(KeyBlock *kb, Lattice *lt)
1636 {
1637         BPoint *bp;
1638         const float (*fp)[3];
1639         int a, tot;
1640
1641         bp = lt->def;
1642         fp = kb->data;
1643
1644         tot = lt->pntsu * lt->pntsv * lt->pntsw;
1645         tot = min_ii(kb->totelem, tot);
1646
1647         for (a = 0; a < tot; a++, fp++, bp++) {
1648                 copy_v3_v3(bp->vec, *fp);
1649         }
1650 }
1651
1652 /************************* Curve ************************/
1653
1654 int BKE_keyblock_curve_element_count(ListBase *nurb)
1655 {
1656         Nurb *nu;
1657         int tot = 0;
1658
1659         nu = nurb->first;
1660         while (nu) {
1661                 if (nu->bezt)
1662                         tot += KEYELEM_ELEM_LEN_BEZTRIPLE * nu->pntsu;
1663                 else if (nu->bp)
1664                         tot += KEYELEM_ELEM_LEN_BPOINT * nu->pntsu * nu->pntsv;
1665
1666                 nu = nu->next;
1667         }
1668         return tot;
1669 }
1670
1671 void BKE_keyblock_update_from_curve(Curve *UNUSED(cu), KeyBlock *kb, ListBase *nurb)
1672 {
1673         Nurb *nu;
1674         BezTriple *bezt;
1675         BPoint *bp;
1676         float *fp;
1677         int a, tot;
1678
1679         /* count */
1680         BLI_assert(BKE_keyblock_curve_element_count(nurb) == kb->totelem);
1681
1682         tot = kb->totelem;
1683         if (tot == 0) return;
1684
1685         fp = kb->data;
1686         for (nu = nurb->first; nu; nu = nu->next) {
1687                 if (nu->bezt) {
1688                         for (a = nu->pntsu, bezt = nu->bezt; a; a--, bezt++) {
1689                                 for (int i = 0; i < 3; i++) {
1690                                         copy_v3_v3(&fp[i * 3], bezt->vec[i]);
1691                                 }
1692                                 fp[9] = bezt->alfa;
1693                                 fp[10] = bezt->radius;
1694                                 fp += KEYELEM_FLOAT_LEN_BEZTRIPLE;
1695                         }
1696                 }
1697                 else {
1698                         for (a = nu->pntsu * nu->pntsv, bp = nu->bp; a; a--, bp++) {
1699                                 copy_v3_v3(fp, bp->vec);
1700                                 fp[3] = bp->alfa;
1701                                 fp[4] = bp->radius;
1702                                 fp += KEYELEM_FLOAT_LEN_BPOINT;
1703                         }
1704                 }
1705         }
1706 }
1707
1708 void BKE_keyblock_convert_from_curve(Curve *cu, KeyBlock *kb, ListBase *nurb)
1709 {
1710         int tot;
1711
1712         /* count */
1713         tot = BKE_keyblock_curve_element_count(nurb);
1714         if (tot == 0) return;
1715
1716         MEM_SAFE_FREE(kb->data);
1717
1718         kb->data = MEM_mallocN(cu->key->elemsize * tot, __func__);
1719         kb->totelem = tot;
1720
1721         BKE_keyblock_update_from_curve(cu, kb, nurb);
1722 }
1723
1724 void BKE_keyblock_convert_to_curve(KeyBlock *kb, Curve *UNUSED(cu), ListBase *nurb)
1725 {
1726         Nurb *nu;
1727         BezTriple *bezt;
1728         BPoint *bp;
1729         const float *fp;
1730         int a, tot;
1731
1732         tot = BKE_keyblock_curve_element_count(nurb);
1733         tot = min_ii(kb->totelem, tot);
1734
1735         fp = kb->data;
1736         for (nu = nurb->first; nu && tot > 0; nu = nu->next) {
1737                 if (nu->bezt) {
1738                         for (a = nu->pntsu, bezt = nu->bezt; a && (tot -= KEYELEM_ELEM_LEN_BEZTRIPLE) >= 0; a--, bezt++) {
1739                                 for (int i = 0; i < 3; i++) {
1740                                         copy_v3_v3(bezt->vec[i], &fp[i * 3]);
1741                                 }
1742                                 bezt->alfa = fp[9];
1743                                 bezt->radius = fp[10];
1744                                 fp += KEYELEM_FLOAT_LEN_BEZTRIPLE;
1745                         }
1746                 }
1747                 else {
1748                         for (a = nu->pntsu * nu->pntsv, bp = nu->bp; a && (tot -= KEYELEM_ELEM_LEN_BPOINT) >= 0; a--, bp++) {
1749                                 copy_v3_v3(bp->vec, fp);
1750                                 bp->alfa = fp[3];
1751                                 bp->radius = fp[4];
1752                                 fp += KEYELEM_FLOAT_LEN_BPOINT;
1753                         }
1754                 }
1755         }
1756 }
1757
1758 /************************* Mesh ************************/
1759 void BKE_keyblock_update_from_mesh(Mesh *me, KeyBlock *kb)
1760 {
1761         MVert *mvert;
1762         float (*fp)[3];
1763         int a, tot;
1764
1765         BLI_assert(me->totvert == kb->totelem);
1766
1767         tot = me->totvert;
1768         if (tot == 0) return;
1769
1770         mvert = me->mvert;
1771         fp = kb->data;
1772         for (a = 0; a < tot; a++, fp++, mvert++) {
1773                 copy_v3_v3(*fp, mvert->co);
1774         }
1775 }
1776
1777 void BKE_keyblock_convert_from_mesh(Mesh *me, Key *key, KeyBlock *kb)
1778 {
1779         const int len = me->totvert;
1780
1781         if (me->totvert == 0) return;
1782
1783         MEM_SAFE_FREE(kb->data);
1784
1785         kb->data = MEM_malloc_arrayN((size_t)len, (size_t)key->elemsize, __func__);
1786         kb->totelem = len;
1787
1788         BKE_keyblock_update_from_mesh(me, kb);
1789 }
1790
1791 void BKE_keyblock_convert_to_mesh(KeyBlock *kb, Mesh *me)
1792 {
1793         MVert *mvert;
1794         const float (*fp)[3];
1795         int a, tot;
1796
1797         mvert = me->mvert;
1798         fp = kb->data;
1799
1800         tot = min_ii(kb->totelem, me->totvert);
1801
1802         for (a = 0; a < tot; a++, fp++, mvert++) {
1803                 copy_v3_v3(mvert->co, *fp);
1804         }
1805 }
1806
1807 /**
1808  * Computes normals (vertices, polygons and/or loops ones) of given mesh for given shape key.
1809  *
1810  * \param kb: the KeyBlock to use to compute normals.
1811  * \param mesh: the Mesh to apply keyblock to.
1812  * \param r_vertnors: if non-NULL, an array of vectors, same length as number of vertices.
1813  * \param r_polynors: if non-NULL, an array of vectors, same length as number of polygons.
1814  * \param r_loopnors: if non-NULL, an array of vectors, same length as number of loops.
1815  */
1816 void BKE_keyblock_mesh_calc_normals(
1817         struct KeyBlock *kb, struct Mesh *mesh,
1818         float (*r_vertnors)[3], float (*r_polynors)[3], float (*r_loopnors)[3])
1819 {
1820         /* We use a temp, shallow copy of mesh to work. */
1821         Mesh me;
1822         bool free_polynors = false;
1823
1824         if (r_vertnors == NULL && r_polynors == NULL && r_loopnors == NULL) {
1825                 return;
1826         }
1827
1828         me = *mesh;
1829         me.mvert = MEM_dupallocN(mesh->mvert);
1830         CustomData_reset(&me.vdata);
1831         CustomData_reset(&me.edata);
1832         CustomData_reset(&me.pdata);
1833         CustomData_reset(&me.ldata);
1834         CustomData_reset(&me.fdata);
1835
1836         BKE_keyblock_convert_to_mesh(kb, &me);
1837
1838         if (r_polynors == NULL && r_loopnors != NULL) {
1839                 r_polynors = MEM_mallocN(sizeof(float[3]) * me.totpoly, __func__);
1840                 free_polynors = true;
1841         }
1842         BKE_mesh_calc_normals_poly(
1843                     me.mvert, r_vertnors, me.totvert, me.mloop, me.mpoly, me.totloop, me.totpoly, r_polynors, false);
1844
1845         if (r_loopnors) {
1846                 short (*clnors)[2] = CustomData_get_layer(&mesh->ldata, CD_CUSTOMLOOPNORMAL);  /* May be NULL. */
1847
1848                 BKE_mesh_normals_loop_split(
1849                         me.mvert, me.totvert, me.medge, me.totedge,
1850                         me.mloop, r_loopnors, me.totloop, me.mpoly, r_polynors, me.totpoly,
1851                         (me.flag & ME_AUTOSMOOTH) != 0, me.smoothresh, NULL, clnors, NULL);
1852         }
1853
1854         CustomData_free(&me.vdata, me.totvert);
1855         CustomData_free(&me.edata, me.totedge);
1856         CustomData_free(&me.pdata, me.totpoly);
1857         CustomData_free(&me.ldata, me.totloop);
1858         CustomData_free(&me.fdata, me.totface);
1859         MEM_freeN(me.mvert);
1860
1861         if (free_polynors) {
1862                 MEM_freeN(r_polynors);
1863         }
1864 }
1865
1866
1867 /************************* raw coords ************************/
1868 void BKE_keyblock_update_from_vertcos(Object *ob, KeyBlock *kb, float (*vertCos)[3])
1869 {
1870         float (*co)[3] = vertCos;
1871         float *fp = kb->data;
1872         int tot, a;
1873
1874 #ifndef NDEBUG
1875         if (ob->type == OB_LATTICE) {
1876                 Lattice *lt = ob->data;
1877                 BLI_assert((lt->pntsu * lt->pntsv * lt->pntsw) == kb->totelem);
1878         }
1879         else if (ELEM(ob->type, OB_CURVE, OB_SURF)) {
1880                 Curve *cu = ob->data;
1881                 BLI_assert(BKE_keyblock_curve_element_count(&cu->nurb) == kb->totelem);
1882         }
1883         else if (ob->type == OB_MESH) {
1884                 Mesh *me = ob->data;
1885                 BLI_assert(me->totvert == kb->totelem);
1886         }
1887         else {
1888                 BLI_assert(0 == kb->totelem);
1889         }
1890 #endif
1891
1892         tot = kb->totelem;
1893         if (tot == 0) return;
1894
1895         /* Copy coords to keyblock */
1896         if (ELEM(ob->type, OB_MESH, OB_LATTICE)) {
1897                 for (a = 0; a < tot; a++, fp += 3, co++) {
1898                         copy_v3_v3(fp, *co);
1899                 }
1900         }
1901         else if (ELEM(ob->type, OB_CURVE, OB_SURF)) {
1902                 Curve *cu = (Curve *)ob->data;
1903                 Nurb *nu;
1904                 BezTriple *bezt;
1905                 BPoint *bp;
1906
1907                 for (nu = cu->nurb.first; nu; nu = nu->next) {
1908                         if (nu->bezt) {
1909                                 for (a = nu->pntsu, bezt = nu->bezt; a; a--, bezt++) {
1910                                         for (int i = 0; i < 3; i++, co++) {
1911                                                 copy_v3_v3(&fp[i * 3], *co);
1912                                         }
1913                                         fp += KEYELEM_FLOAT_LEN_BEZTRIPLE;
1914                                 }
1915                         }
1916                         else {
1917                                 for (a = nu->pntsu * nu->pntsv, bp = nu->bp; a; a--, bp++, co++) {
1918                                         copy_v3_v3(fp, *co);
1919                                         fp += KEYELEM_FLOAT_LEN_BPOINT;
1920                                 }
1921                         }
1922                 }
1923         }
1924 }
1925
1926 void BKE_keyblock_convert_from_vertcos(Object *ob, KeyBlock *kb, float (*vertCos)[3])
1927 {
1928         int tot = 0, elemsize;
1929
1930         MEM_SAFE_FREE(kb->data);
1931
1932         /* Count of vertex coords in array */
1933         if (ob->type == OB_MESH) {
1934                 Mesh *me = (Mesh *)ob->data;
1935                 tot = me->totvert;
1936                 elemsize = me->key->elemsize;
1937         }
1938         else if (ob->type == OB_LATTICE) {
1939                 Lattice *lt = (Lattice *)ob->data;
1940                 tot = lt->pntsu * lt->pntsv * lt->pntsw;
1941                 elemsize = lt->key->elemsize;
1942         }
1943         else if (ELEM(ob->type, OB_CURVE, OB_SURF)) {
1944                 Curve *cu = (Curve *)ob->data;
1945                 elemsize = cu->key->elemsize;
1946                 tot = BKE_keyblock_curve_element_count(&cu->nurb);
1947         }
1948
1949         if (tot == 0) return;
1950
1951         kb->data = MEM_mallocN(tot * elemsize, __func__);
1952
1953         /* Copy coords to keyblock */
1954         BKE_keyblock_update_from_vertcos(ob, kb, vertCos);
1955 }
1956
1957 float (*BKE_keyblock_convert_to_vertcos(Object *ob, KeyBlock *kb))[3]
1958 {
1959         float (*vertCos)[3], (*co)[3];
1960         const float *fp = kb->data;
1961         int tot = 0, a;
1962
1963         /* Count of vertex coords in array */
1964         if (ob->type == OB_MESH) {
1965                 Mesh *me = (Mesh *)ob->data;
1966                 tot = me->totvert;
1967         }
1968         else if (ob->type == OB_LATTICE) {
1969                 Lattice *lt = (Lattice *)ob->data;
1970                 tot = lt->pntsu * lt->pntsv * lt->pntsw;
1971         }
1972         else if (ELEM(ob->type, OB_CURVE, OB_SURF)) {
1973                 Curve *cu = (Curve *)ob->data;
1974                 tot = BKE_nurbList_verts_count(&cu->nurb);
1975         }
1976
1977         if (tot == 0) return NULL;
1978
1979         co = vertCos = MEM_mallocN(tot * sizeof(*vertCos), __func__);
1980
1981         /* Copy coords to array */
1982         if (ELEM(ob->type, OB_MESH, OB_LATTICE)) {
1983                 for (a = 0; a < tot; a++, fp += 3, co++) {
1984                         copy_v3_v3(*co, fp);
1985                 }
1986         }
1987         else if (ELEM(ob->type, OB_CURVE, OB_SURF)) {
1988                 Curve *cu = (Curve *)ob->data;
1989                 Nurb *nu;
1990                 BezTriple *bezt;
1991                 BPoint *bp;
1992
1993                 for (nu = cu->nurb.first; nu; nu = nu->next) {
1994                         if (nu->bezt) {
1995                                 for (a = nu->pntsu, bezt = nu->bezt; a; a--, bezt++) {
1996                                         for (int i = 0; i < 3; i++, co++) {
1997                                                 copy_v3_v3(*co, &fp[i * 3]);
1998                                         }
1999                                         fp += KEYELEM_FLOAT_LEN_BEZTRIPLE;
2000                                 }
2001                         }
2002                         else {
2003                                 for (a = nu->pntsu * nu->pntsv, bp = nu->bp; a; a--, bp++, co++) {
2004                                         copy_v3_v3(*co, fp);
2005                                         fp += KEYELEM_FLOAT_LEN_BPOINT;
2006                                 }
2007                         }
2008                 }
2009         }
2010
2011         return vertCos;
2012 }
2013
2014 /************************* raw coord offsets ************************/
2015 void BKE_keyblock_update_from_offset(Object *ob, KeyBlock *kb, float (*ofs)[3])
2016 {
2017         int a;
2018         float *fp = kb->data;
2019
2020         if (ELEM(ob->type, OB_MESH, OB_LATTICE)) {
2021                 for (a = 0; a < kb->totelem; a++, fp += 3, ofs++) {
2022                         add_v3_v3(fp, *ofs);
2023                 }
2024         }
2025         else if (ELEM(ob->type, OB_CURVE, OB_SURF)) {
2026                 Curve *cu = (Curve *)ob->data;
2027                 Nurb *nu;
2028                 BezTriple *bezt;
2029                 BPoint *bp;
2030
2031                 for (nu = cu->nurb.first; nu; nu = nu->next) {
2032                         if (nu->bezt) {
2033                                 for (a = nu->pntsu, bezt = nu->bezt; a; a--, bezt++) {
2034                                         for (int i = 0; i < 3; i++, ofs++) {
2035                                                 add_v3_v3(&fp[i * 3], *ofs);
2036                                         }
2037                                         fp += KEYELEM_FLOAT_LEN_BEZTRIPLE;
2038                                 }
2039                         }
2040                         else {
2041                                 for (a = nu->pntsu * nu->pntsv, bp = nu->bp; a; a--, bp++, ofs++) {
2042                                         add_v3_v3(fp, *ofs);
2043                                         fp += KEYELEM_FLOAT_LEN_BPOINT;
2044                                 }
2045                         }
2046                 }
2047         }
2048 }
2049
2050 /* ==========================================================*/
2051
2052 /** Move shape key from org_index to new_index. Safe, clamps index to valid range, updates reference keys,
2053  * the object's active shape index, the 'frame' value in case of absolute keys, etc.
2054  * Note indices are expected in real values (not 'fake' shapenr +1 ones).
2055  *
2056  * \param org_index: if < 0, current object's active shape will be used as skey to move.
2057  * \return true if something was done, else false.
2058  */
2059 bool BKE_keyblock_move(Object *ob, int org_index, int new_index)
2060 {
2061         Key *key = BKE_key_from_object(ob);
2062         KeyBlock *kb;
2063         const int act_index = ob->shapenr - 1;
2064         const int totkey = key->totkey;
2065         int i;
2066         bool rev, in_range = false;
2067
2068         if (org_index < 0) {
2069                 org_index = act_index;
2070         }
2071
2072         CLAMP(new_index, 0, key->totkey - 1);
2073         CLAMP(org_index, 0, key->totkey - 1);
2074
2075         if (new_index == org_index) {
2076                 return false;
2077         }
2078
2079         rev = ((new_index - org_index) < 0) ? true : false;
2080
2081         /* We swap 'org' element with its previous/next neighbor (depending on direction of the move) repeatedly,
2082          * until we reach final position.
2083          * This allows us to only loop on the list once! */
2084         for (kb = (rev ? key->block.last : key->block.first), i = (rev ? totkey - 1 : 0);
2085              kb;
2086              kb = (rev ? kb->prev : kb->next), rev ? i-- : i++)
2087         {
2088                 if (i == org_index) {
2089                         in_range = true;  /* Start list items swapping... */
2090                 }
2091                 else if (i == new_index) {
2092                         in_range = false;  /* End list items swapping. */
2093                 }
2094
2095                 if (in_range) {
2096                         KeyBlock *other_kb = rev ? kb->prev : kb->next;
2097
2098                         /* Swap with previous/next list item. */
2099                         BLI_listbase_swaplinks(&key->block, kb, other_kb);
2100
2101                         /* Swap absolute positions. */
2102                         SWAP(float, kb->pos, other_kb->pos);
2103
2104                         kb = other_kb;
2105                 }
2106
2107                 /* Adjust relative indices, this has to be done on the whole list! */
2108                 if (kb->relative == org_index) {
2109                         kb->relative = new_index;
2110                 }
2111                 else if (kb->relative < org_index && kb->relative >= new_index) {
2112                         /* remove after, insert before this index */
2113                         kb->relative++;
2114                 }
2115                 else if (kb->relative > org_index && kb->relative <= new_index) {
2116                         /* remove before, insert after this index */
2117                         kb->relative--;
2118                 }
2119         }
2120
2121         /* Need to update active shape number if it's affected, same principle as for relative indices above. */
2122         if (org_index == act_index) {
2123                 ob->shapenr = new_index + 1;
2124         }
2125         else if (act_index < org_index && act_index >= new_index) {
2126                 ob->shapenr++;
2127         }
2128         else if (act_index > org_index && act_index <= new_index) {
2129                 ob->shapenr--;
2130         }
2131
2132         /* First key is always refkey, matches interface and BKE_key_sort */
2133         key->refkey = key->block.first;
2134
2135         return true;
2136 }
2137
2138 /**
2139  * Check if given keyblock (as index) is used as basis by others in given key.
2140  */
2141 bool BKE_keyblock_is_basis(Key *key, const int index)
2142 {
2143         KeyBlock *kb;
2144         int i;
2145
2146         if (key->type == KEY_RELATIVE) {
2147                 for (i = 0, kb = key->block.first; kb; i++, kb = kb->next) {
2148                         if ((i != index) && (kb->relative == index)) {
2149                                 return true;
2150                         }
2151                 }
2152         }
2153
2154         return false;
2155 }