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