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