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