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