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