sim: Remove "continue physics" code
[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_utildefines.h"
42
43 #include "DNA_anim_types.h"
44 #include "DNA_key_types.h"
45 #include "DNA_lattice_types.h"
46 #include "DNA_mesh_types.h"
47 #include "DNA_meshdata_types.h"
48 #include "DNA_object_types.h"
49 #include "DNA_scene_types.h"
50
51 #include "BKE_animsys.h"
52 #include "BKE_curve.h"
53 #include "BKE_customdata.h"
54 #include "BKE_deform.h"
55 #include "BKE_global.h"
56 #include "BKE_key.h"
57 #include "BKE_lattice.h"
58 #include "BKE_library.h"
59 #include "BKE_tessmesh.h"
60 #include "BKE_main.h"
61 #include "BKE_object.h"
62 #include "BKE_deform.h"
63 #include "BKE_scene.h"
64
65
66 #include "RNA_access.h"
67
68 #define KEY_MODE_DUMMY      0 /* use where mode isn't checked for */
69 #define KEY_MODE_BPOINT     1
70 #define KEY_MODE_BEZTRIPLE  2
71
72 /* old defines from DNA_ipo_types.h for data-type, stored in DNA - don't modify! */
73 #define IPO_FLOAT       4
74 #define IPO_BEZTRIPLE   100
75 #define IPO_BPOINT      101
76
77 /* extern, not threadsafe */
78 int slurph_opt = 1;
79
80
81 void BKE_key_free(Key *key)
82 {
83         KeyBlock *kb;
84         
85         BKE_free_animdata((ID *)key);
86         
87         while ( (kb = key->block.first) ) {
88                 
89                 if (kb->data) MEM_freeN(kb->data);
90                 
91                 BLI_remlink(&key->block, kb);
92                 MEM_freeN(kb);
93         }
94         
95 }
96
97 void BKE_key_free_nolib(Key *key)
98 {
99         KeyBlock *kb;
100         
101         while ( (kb = key->block.first) ) {
102                 
103                 if (kb->data) MEM_freeN(kb->data);
104                 
105                 BLI_remlink(&key->block, kb);
106                 MEM_freeN(kb);
107         }
108         
109 }
110
111 Key *BKE_key_add(ID *id)    /* common function */
112 {
113         Key *key;
114         char *el;
115         
116         key = BKE_libblock_alloc(&G.main->key, ID_KE, "Key");
117         
118         key->type = KEY_NORMAL;
119         key->from = id;
120
121         key->uidgen = 1;
122         
123         /* XXX the code here uses some defines which will soon be deprecated... */
124         switch (GS(id->name)) {
125                 case ID_ME:
126                         el = key->elemstr;
127
128                         el[0] = 3;
129                         el[1] = IPO_FLOAT;
130                         el[2] = 0;
131
132                         key->elemsize = 12;
133
134                         break;
135                 case ID_LT:
136                         el = key->elemstr;
137
138                         el[0] = 3;
139                         el[1] = IPO_FLOAT;
140                         el[2] = 0;
141
142                         key->elemsize = 12;
143
144                         break;
145                 case ID_CU:
146                         el = key->elemstr;
147
148                         el[0] = 4;
149                         el[1] = IPO_BPOINT;
150                         el[2] = 0;
151
152                         key->elemsize = 16;
153
154                         break;
155         }
156         
157         return key;
158 }
159
160 Key *BKE_key_copy(Key *key)
161 {
162         Key *keyn;
163         KeyBlock *kbn, *kb;
164         
165         if (key == NULL) return NULL;
166         
167         keyn = BKE_libblock_copy(&key->id);
168         
169         BLI_duplicatelist(&keyn->block, &key->block);
170         
171         kb = key->block.first;
172         kbn = keyn->block.first;
173         while (kbn) {
174                 
175                 if (kbn->data) kbn->data = MEM_dupallocN(kbn->data);
176                 if (kb == key->refkey) keyn->refkey = kbn;
177                 
178                 kbn = kbn->next;
179                 kb = kb->next;
180         }
181         
182         return keyn;
183 }
184
185
186 Key *BKE_key_copy_nolib(Key *key)
187 {
188         Key *keyn;
189         KeyBlock *kbn, *kb;
190         
191         if (key == 0) return 0;
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 void BKE_key_make_local(Key *key)
214 {
215
216         /* - only lib users: do nothing
217          * - only local users: set flag
218          * - mixed: make copy
219          */
220         if (key == NULL) return;
221         
222         key->id.lib = NULL;
223         new_id(NULL, &key->id, NULL);
224 }
225
226 /* Sort shape keys and Ipo curves after a change.  This assumes that at most
227  * one key was moved, which is a valid assumption for the places it's
228  * currently being called.
229  */
230
231 void BKE_key_sort(Key *key)
232 {
233         KeyBlock *kb;
234         KeyBlock *kb2;
235
236         /* locate the key which is out of position */ 
237         for (kb = key->block.first; kb; kb = kb->next)
238                 if ((kb->next) && (kb->pos > kb->next->pos))
239                         break;
240
241         /* if we find a key, move it */
242         if (kb) {
243                 kb = kb->next; /* next key is the out-of-order one */
244                 BLI_remlink(&key->block, kb);
245                 
246                 /* find the right location and insert before */
247                 for (kb2 = key->block.first; kb2; kb2 = kb2->next) {
248                         if (kb2->pos > kb->pos) {
249                                 BLI_insertlink(&key->block, kb2->prev, kb);
250                                 break;
251                         }
252                 }
253         }
254
255         /* new rule; first key is refkey, this to match drawing channels... */
256         key->refkey = key->block.first;
257 }
258
259 /**************** do the key ****************/
260
261 void key_curve_position_weights(float t, float data[4], int type)
262 {
263         float t2, t3, fc;
264         
265         if (type == KEY_LINEAR) {
266                 data[0] =          0.0f;
267                 data[1] = -t     + 1.0f;
268                 data[2] =  t;
269                 data[3] =          0.0f;
270         }
271         else if (type == KEY_CARDINAL) {
272                 t2 = t * t;
273                 t3 = t2 * t;
274                 fc = 0.71f;
275
276                 data[0] = -fc          * t3  + 2.0f * fc          * t2 - fc * t;
277                 data[1] =  (2.0f - fc) * t3  + (fc - 3.0f)        * t2 + 1.0f;
278                 data[2] =  (fc - 2.0f) * t3  + (3.0f - 2.0f * fc) * t2 + fc * t;
279                 data[3] =  fc          * t3  - fc * t2;
280         }
281         else if (type == KEY_BSPLINE) {
282                 t2 = t * t;
283                 t3 = t2 * t;
284
285                 data[0] = -0.16666666f * t3  + 0.5f * t2   - 0.5f * t    + 0.16666666f;
286                 data[1] =  0.5f        * t3  - t2                        + 0.66666666f;
287                 data[2] = -0.5f        * t3  + 0.5f * t2   + 0.5f * t    + 0.16666666f;
288                 data[3] =  0.16666666f * t3;
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 }
321
322 /* second derivative */
323 void key_curve_normal_weights(float t, float data[4], int type)
324 {
325         float fc;
326         
327         if (type == KEY_LINEAR) {
328                 data[0] = 0.0f;
329                 data[1] = 0.0f;
330                 data[2] = 0.0f;
331                 data[3] = 0.0f;
332         }
333         else if (type == KEY_CARDINAL) {
334                 fc = 0.71f;
335
336                 data[0] = -6.0f * fc          * t  + 4.0f * fc;
337                 data[1] =  6.0f * (2.0f - fc) * t  + 2.0f * (fc - 3.0f);
338                 data[2] =  6.0f * (fc - 2.0f) * t  + 2.0f * (3.0f - 2.0f * fc);
339                 data[3] =  6.0f * fc          * t  - 2.0f * fc;
340         }
341         else if (type == KEY_BSPLINE) {
342                 data[0] = -1.0f * t  + 1.0f;
343                 data[1] =  3.0f * t  - 2.0f;
344                 data[2] = -3.0f * t  + 1.0f;
345                 data[3] =  1.0f * t;
346         }
347 }
348
349 static int setkeys(float fac, ListBase *lb, KeyBlock *k[], float t[4], int cycl)
350 {
351         /* return 1 means k[2] is the position, return 0 means interpolate */
352         KeyBlock *k1, *firstkey;
353         float d, dpos, ofs = 0, lastpos;
354         short bsplinetype;
355
356         firstkey = lb->first;
357         k1 = lb->last;
358         lastpos = k1->pos;
359         dpos = lastpos - firstkey->pos;
360
361         if (fac < firstkey->pos) fac = firstkey->pos;
362         else if (fac > k1->pos) fac = k1->pos;
363
364         k1 = k[0] = k[1] = k[2] = k[3] = firstkey;
365         t[0] = t[1] = t[2] = t[3] = k1->pos;
366
367         /* if (fac < 0.0 || fac > 1.0) return 1; */
368
369         if (k1->next == NULL) return 1;
370
371         if (cycl) { /* pre-sort */
372                 k[2] = k1->next;
373                 k[3] = k[2]->next;
374                 if (k[3] == NULL) k[3] = k1;
375                 while (k1) {
376                         if (k1->next == NULL) k[0] = k1;
377                         k1 = k1->next;
378                 }
379                 /* k1 = k[1]; */ /* UNUSED */
380                 t[0] = k[0]->pos;
381                 t[1] += dpos;
382                 t[2] = k[2]->pos + dpos;
383                 t[3] = k[3]->pos + dpos;
384                 fac += dpos;
385                 ofs = dpos;
386                 if (k[3] == k[1]) {
387                         t[3] += dpos;
388                         ofs = 2.0f * dpos;
389                 }
390                 if (fac < t[1]) fac += dpos;
391                 k1 = k[3];
392         }
393         else {  /* pre-sort */
394                 k[2] = k1->next;
395                 t[2] = k[2]->pos;
396                 k[3] = k[2]->next;
397                 if (k[3] == NULL) k[3] = k[2];
398                 t[3] = k[3]->pos;
399                 k1 = k[3];
400         }
401         
402         while (t[2] < fac) {    /* find correct location */
403                 if (k1->next == NULL) {
404                         if (cycl) {
405                                 k1 = firstkey;
406                                 ofs += dpos;
407                         }
408                         else if (t[2] == t[3]) break;
409                 }
410                 else k1 = k1->next;
411
412                 t[0] = t[1];
413                 k[0] = k[1];
414                 t[1] = t[2];
415                 k[1] = k[2];
416                 t[2] = t[3];
417                 k[2] = k[3];
418                 t[3] = k1->pos + ofs;
419                 k[3] = k1;
420
421                 if (ofs > 2.1f + lastpos) break;
422         }
423         
424         bsplinetype = 0;
425         if (k[1]->type == KEY_BSPLINE || k[2]->type == KEY_BSPLINE) bsplinetype = 1;
426
427
428         if (cycl == 0) {
429                 if (bsplinetype == 0) {   /* B spline doesn't go through the control points */
430                         if (fac <= t[1]) {  /* fac for 1st key */
431                                 t[2] = t[1];
432                                 k[2] = k[1];
433                                 return 1;
434                         }
435                         if (fac >= t[2]) {  /* fac after 2nd key */
436                                 return 1;
437                         }
438                 }
439                 else if (fac > t[2]) {  /* last key */
440                         fac = t[2];
441                         k[3] = k[2];
442                         t[3] = t[2];
443                 }
444         }
445
446         d = t[2] - t[1];
447         if (d == 0.0f) {
448                 if (bsplinetype == 0) {
449                         return 1;  /* both keys equal */
450                 }
451         }
452         else {
453                 d = (fac - t[1]) / d;
454         }
455
456         /* interpolation */
457         key_curve_position_weights(d, t, k[1]->type);
458
459         if (k[1]->type != k[2]->type) {
460                 float t_other[4];
461                 key_curve_position_weights(d, t_other, k[2]->type);
462                 interp_v4_v4v4(t, t, t_other, d);
463         }
464
465         return 0;
466
467 }
468
469 static void flerp(int tot, float *in, float *f0, float *f1, float *f2, float *f3, float *t)
470 {
471         int a;
472
473         for (a = 0; a < tot; a++) {
474                 in[a] = t[0] * f0[a] + t[1] * f1[a] + t[2] * f2[a] + t[3] * f3[a];
475         }
476 }
477
478 static void rel_flerp(int tot, float *in, float *ref, float *out, float fac)
479 {
480         int a;
481         
482         for (a = 0; a < tot; a++) {
483                 in[a] -= fac * (ref[a] - out[a]);
484         }
485 }
486
487 static char *key_block_get_data(Key *key, KeyBlock *actkb, KeyBlock *kb, char **freedata)
488 {
489         if (kb == actkb) {
490                 /* this hack makes it possible to edit shape keys in
491                  * edit mode with shape keys blending applied */
492                 if (GS(key->from->name) == ID_ME) {
493                         Mesh *me;
494                         BMVert *eve;
495                         BMIter iter;
496                         float (*co)[3];
497                         int a;
498
499                         me = (Mesh *)key->from;
500
501                         if (me->edit_btmesh && me->edit_btmesh->bm->totvert == kb->totelem) {
502                                 a = 0;
503                                 co = MEM_callocN(sizeof(float) * 3 * me->edit_btmesh->bm->totvert, "key_block_get_data");
504
505                                 BM_ITER_MESH (eve, &iter, me->edit_btmesh->bm, BM_VERTS_OF_MESH) {
506                                         copy_v3_v3(co[a], eve->co);
507                                         a++;
508                                 }
509
510                                 *freedata = (char *)co;
511                                 return (char *)co;
512                         }
513                 }
514         }
515
516         *freedata = NULL;
517         return kb->data;
518 }
519
520
521 /* currently only the first value of 'ofs' may be set. */
522 static short key_pointer_size(const Key *key, const int mode, int *poinsize, int *ofs)
523 {
524         if (key->from == NULL) {
525                 return FALSE;
526         }
527
528         switch (GS(key->from->name)) {
529                 case ID_ME:
530                         *ofs = sizeof(float) * 3;
531                         *poinsize = *ofs;
532                         break;
533                 case ID_LT:
534                         *ofs = sizeof(float) * 3;
535                         *poinsize = *ofs;
536                         break;
537                 case ID_CU:
538                         if (mode == KEY_MODE_BPOINT) {
539                                 *ofs = sizeof(float) * 4;
540                                 *poinsize = *ofs;
541                         }
542                         else {
543                                 ofs[0] = sizeof(float) * 12;
544                                 *poinsize = (*ofs) / 3;
545                         }
546
547                         break;
548                 default:
549                         BLI_assert(!"invalid 'key->from' ID type");
550                         return FALSE;
551         }
552
553         return TRUE;
554 }
555
556 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)
557 {
558         float ktot = 0.0, kd = 0.0;
559         int elemsize, poinsize = 0, a, *ofsp, ofs[32], flagflo = 0;
560         char *k1, *kref, *freek1, *freekref;
561         char *cp, elemstr[8];
562
563         /* currently always 0, in future key_pointer_size may assign */
564         ofs[1] = 0;
565
566         if (!key_pointer_size(key, mode, &poinsize, &ofs[0]))
567                 return;
568
569         if (end > tot) end = tot;
570         
571         if (tot != kb->totelem) {
572                 ktot = 0.0;
573                 flagflo = 1;
574                 if (kb->totelem) {
575                         kd = kb->totelem / (float)tot;
576                 }
577                 else {
578                         return;
579                 }
580         }
581
582         k1 = key_block_get_data(key, actkb, kb, &freek1);
583         kref = key_block_get_data(key, actkb, key->refkey, &freekref);
584
585         /* this exception is needed for slurphing */
586         if (start != 0) {
587                 
588                 poin += poinsize * start;
589                 
590                 if (flagflo) {
591                         ktot += start * kd;
592                         a = (int)floor(ktot);
593                         if (a) {
594                                 ktot -= a;
595                                 k1 += a * key->elemsize;
596                         }
597                 }
598                 else k1 += start * key->elemsize;
599         }
600         
601         if (mode == KEY_MODE_BEZTRIPLE) {
602                 elemstr[0] = 1;
603                 elemstr[1] = IPO_BEZTRIPLE;
604                 elemstr[2] = 0;
605         }
606         
607         /* just do it here, not above! */
608         elemsize = key->elemsize;
609         if (mode == KEY_MODE_BEZTRIPLE) elemsize *= 3;
610
611         for (a = start; a < end; a++) {
612                 cp = key->elemstr;
613                 if (mode == KEY_MODE_BEZTRIPLE) cp = elemstr;
614
615                 ofsp = ofs;
616
617                 while (cp[0]) {
618
619                         switch (cp[1]) {
620                                 case IPO_FLOAT:
621                                         if (weights) {
622                                                 memcpy(poin, kref, sizeof(float) * 3);
623                                                 if (*weights != 0.0f)
624                                                         rel_flerp(cp[0], (float *)poin, (float *)kref, (float *)k1, *weights);
625                                                 weights++;
626                                         }
627                                         else {
628                                                 memcpy(poin, k1, sizeof(float) * 3);
629                                         }
630                                         break;
631                                 case IPO_BPOINT:
632                                         memcpy(poin, k1, sizeof(float) * 4);
633                                         break;
634                                 case IPO_BEZTRIPLE:
635                                         memcpy(poin, k1, sizeof(float) * 12);
636                                         break;
637                                 default:
638                                         /* should never happen */
639                                         if (freek1) MEM_freeN(freek1);
640                                         if (freekref) MEM_freeN(freekref);
641                                         BLI_assert(!"invalid 'cp[1]'");
642                                         return;
643                         }
644
645                         poin += *ofsp;
646                         cp += 2; ofsp++;
647                 }
648                 
649                 /* are we going to be nasty? */
650                 if (flagflo) {
651                         ktot += kd;
652                         while (ktot >= 1.0f) {
653                                 ktot -= 1.0f;
654                                 k1 += elemsize;
655                                 kref += elemsize;
656                         }
657                 }
658                 else {
659                         k1 += elemsize;
660                         kref += elemsize;
661                 }
662                 
663                 if (mode == KEY_MODE_BEZTRIPLE) {
664                         a += 2;
665                 }
666         }
667
668         if (freek1) MEM_freeN(freek1);
669         if (freekref) MEM_freeN(freekref);
670 }
671
672 static void cp_cu_key(Curve *cu, Key *key, KeyBlock *actkb, KeyBlock *kb, const int start, int end, char *out, const int tot)
673 {
674         Nurb *nu;
675         int a, step, a1, a2;
676
677         for (a = 0, nu = cu->nurb.first; nu; nu = nu->next, a += step) {
678                 if (nu->bp) {
679                         step = nu->pntsu * nu->pntsv;
680
681                         a1 = max_ii(a, start);
682                         a2 = min_ii(a + step, end);
683
684                         if (a1 < a2) cp_key(a1, a2, tot, out, key, actkb, kb, NULL, KEY_MODE_BPOINT);
685                 }
686                 else if (nu->bezt) {
687                         step = 3 * nu->pntsu;
688
689                         /* exception because keys prefer to work with complete blocks */
690                         a1 = max_ii(a, start);
691                         a2 = min_ii(a + step, end);
692
693                         if (a1 < a2) cp_key(a1, a2, tot, out, key, actkb, kb, NULL, KEY_MODE_BEZTRIPLE);
694                 }
695                 else {
696                         step = 0;
697                 }
698         }
699 }
700
701 void BKE_key_evaluate_relative(const int start, int end, const int tot, char *basispoin, Key *key, KeyBlock *actkb, const int mode)
702 {
703         KeyBlock *kb;
704         int *ofsp, ofs[3], elemsize, b;
705         char *cp, *poin, *reffrom, *from, elemstr[8];
706         int poinsize;
707
708         /* currently always 0, in future key_pointer_size may assign */
709         ofs[1] = 0;
710
711         if (!key_pointer_size(key, mode, &poinsize, &ofs[0]))
712                 return;
713
714         if (end > tot) end = tot;
715
716         /* in case of beztriple */
717         elemstr[0] = 1;              /* nr of ipofloats */
718         elemstr[1] = IPO_BEZTRIPLE;
719         elemstr[2] = 0;
720
721         /* just here, not above! */
722         elemsize = key->elemsize;
723         if (mode == KEY_MODE_BEZTRIPLE) elemsize *= 3;
724
725         /* step 1 init */
726         cp_key(start, end, tot, basispoin, key, actkb, key->refkey, NULL, mode);
727         
728         /* step 2: do it */
729         
730         for (kb = key->block.first; kb; kb = kb->next) {
731                 if (kb != key->refkey) {
732                         float icuval = kb->curval;
733                         
734                         /* only with value, and no difference allowed */
735                         if (!(kb->flag & KEYBLOCK_MUTE) && icuval != 0.0f && kb->totelem == tot) {
736                                 KeyBlock *refb;
737                                 float weight, *weights = kb->weights;
738                                 char *freefrom = NULL, *freereffrom = NULL;
739
740                                 /* reference now can be any block */
741                                 refb = BLI_findlink(&key->block, kb->relative);
742                                 if (refb == NULL) continue;
743                                 
744                                 poin = basispoin;
745                                 from = key_block_get_data(key, actkb, kb, &freefrom);
746                                 reffrom = key_block_get_data(key, actkb, refb, &freereffrom);
747
748                                 poin += start * poinsize;
749                                 reffrom += key->elemsize * start;  // key elemsize yes!
750                                 from += key->elemsize * start;
751                                 
752                                 for (b = start; b < end; b++) {
753                                 
754                                         weight = weights ? (*weights * icuval) : icuval;
755                                         
756                                         cp = key->elemstr;
757                                         if (mode == KEY_MODE_BEZTRIPLE) cp = elemstr;
758                                         
759                                         ofsp = ofs;
760                                         
761                                         while (cp[0]) {  /* (cp[0] == amount) */
762                                                 
763                                                 switch (cp[1]) {
764                                                         case IPO_FLOAT:
765                                                                 rel_flerp(3, (float *)poin, (float *)reffrom, (float *)from, weight);
766                                                                 break;
767                                                         case IPO_BPOINT:
768                                                                 rel_flerp(4, (float *)poin, (float *)reffrom, (float *)from, weight);
769                                                                 break;
770                                                         case IPO_BEZTRIPLE:
771                                                                 rel_flerp(12, (float *)poin, (float *)reffrom, (float *)from, weight);
772                                                                 break;
773                                                         default:
774                                                                 /* should never happen */
775                                                                 if (freefrom) MEM_freeN(freefrom);
776                                                                 if (freereffrom) MEM_freeN(freereffrom);
777                                                                 BLI_assert(!"invalid 'cp[1]'");
778                                                                 return;
779                                                 }
780
781                                                 poin += *ofsp;
782                                                 
783                                                 cp += 2;
784                                                 ofsp++;
785                                         }
786                                         
787                                         reffrom += elemsize;
788                                         from += elemsize;
789                                         
790                                         if (mode == KEY_MODE_BEZTRIPLE) b += 2;
791                                         if (weights) weights++;
792                                 }
793
794                                 if (freefrom) MEM_freeN(freefrom);
795                                 if (freereffrom) MEM_freeN(freereffrom);
796                         }
797                 }
798         }
799 }
800
801
802 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)
803 {
804         float k1tot = 0.0, k2tot = 0.0, k3tot = 0.0, k4tot = 0.0;
805         float k1d = 0.0, k2d = 0.0, k3d = 0.0, k4d = 0.0;
806         int a, ofs[32], *ofsp;
807         int flagdo = 15, flagflo = 0, elemsize, poinsize = 0;
808         char *k1, *k2, *k3, *k4, *freek1, *freek2, *freek3, *freek4;
809         char *cp, elemstr[8];
810
811         /* currently always 0, in future key_pointer_size may assign */
812         ofs[1] = 0;
813
814         if (!key_pointer_size(key, mode, &poinsize, &ofs[0]))
815                 return;
816         
817         if (end > tot) end = tot;
818
819         k1 = key_block_get_data(key, actkb, k[0], &freek1);
820         k2 = key_block_get_data(key, actkb, k[1], &freek2);
821         k3 = key_block_get_data(key, actkb, k[2], &freek3);
822         k4 = key_block_get_data(key, actkb, k[3], &freek4);
823
824         /*  test for more or less points (per key!) */
825         if (tot != k[0]->totelem) {
826                 k1tot = 0.0;
827                 flagflo |= 1;
828                 if (k[0]->totelem) {
829                         k1d = k[0]->totelem / (float)tot;
830                 }
831                 else flagdo -= 1;
832         }
833         if (tot != k[1]->totelem) {
834                 k2tot = 0.0;
835                 flagflo |= 2;
836                 if (k[0]->totelem) {
837                         k2d = k[1]->totelem / (float)tot;
838                 }
839                 else flagdo -= 2;
840         }
841         if (tot != k[2]->totelem) {
842                 k3tot = 0.0;
843                 flagflo |= 4;
844                 if (k[0]->totelem) {
845                         k3d = k[2]->totelem / (float)tot;
846                 }
847                 else flagdo -= 4;
848         }
849         if (tot != k[3]->totelem) {
850                 k4tot = 0.0;
851                 flagflo |= 8;
852                 if (k[0]->totelem) {
853                         k4d = k[3]->totelem / (float)tot;
854                 }
855                 else flagdo -= 8;
856         }
857
858         /* this exception needed for slurphing */
859         if (start != 0) {
860
861                 poin += poinsize * start;
862                 
863                 if (flagdo & 1) {
864                         if (flagflo & 1) {
865                                 k1tot += start * k1d;
866                                 a = (int)floor(k1tot);
867                                 if (a) {
868                                         k1tot -= a;
869                                         k1 += a * key->elemsize;
870                                 }
871                         }
872                         else k1 += start * key->elemsize;
873                 }
874                 if (flagdo & 2) {
875                         if (flagflo & 2) {
876                                 k2tot += start * k2d;
877                                 a = (int)floor(k2tot);
878                                 if (a) {
879                                         k2tot -= a;
880                                         k2 += a * key->elemsize;
881                                 }
882                         }
883                         else k2 += start * key->elemsize;
884                 }
885                 if (flagdo & 4) {
886                         if (flagflo & 4) {
887                                 k3tot += start * k3d;
888                                 a = (int)floor(k3tot);
889                                 if (a) {
890                                         k3tot -= a;
891                                         k3 += a * key->elemsize;
892                                 }
893                         }
894                         else k3 += start * key->elemsize;
895                 }
896                 if (flagdo & 8) {
897                         if (flagflo & 8) {
898                                 k4tot += start * k4d;
899                                 a = (int)floor(k4tot);
900                                 if (a) {
901                                         k4tot -= a;
902                                         k4 += a * key->elemsize;
903                                 }
904                         }
905                         else k4 += start * key->elemsize;
906                 }
907
908         }
909
910         /* in case of beztriple */
911         elemstr[0] = 1;              /* nr of ipofloats */
912         elemstr[1] = IPO_BEZTRIPLE;
913         elemstr[2] = 0;
914
915         /* only here, not above! */
916         elemsize = key->elemsize;
917         if (mode == KEY_MODE_BEZTRIPLE) elemsize *= 3;
918
919         for (a = start; a < end; a++) {
920         
921                 cp = key->elemstr;
922                 if (mode == KEY_MODE_BEZTRIPLE) cp = elemstr;
923                 
924                 ofsp = ofs;
925
926                 while (cp[0]) {  /* (cp[0] == amount) */
927
928                         switch (cp[1]) {
929                                 case IPO_FLOAT:
930                                         flerp(3, (float *)poin, (float *)k1, (float *)k2, (float *)k3, (float *)k4, t);
931                                         break;
932                                 case IPO_BPOINT:
933                                         flerp(4, (float *)poin, (float *)k1, (float *)k2, (float *)k3, (float *)k4, t);
934                                         break;
935                                 case IPO_BEZTRIPLE:
936                                         flerp(12, (void *)poin, (void *)k1, (void *)k2, (void *)k3, (void *)k4, t);
937                                         break;
938                                 default:
939                                         /* should never happen */
940                                         if (freek1) MEM_freeN(freek1);
941                                         if (freek2) MEM_freeN(freek2);
942                                         if (freek3) MEM_freeN(freek3);
943                                         if (freek4) MEM_freeN(freek4);
944                                         BLI_assert(!"invalid 'cp[1]'");
945                                         return;
946                         }
947                         
948                         poin += *ofsp;
949                         cp += 2;
950                         ofsp++;
951                 }
952                 /* lets do it the difficult way: when keys have a different size */
953                 if (flagdo & 1) {
954                         if (flagflo & 1) {
955                                 k1tot += k1d;
956                                 while (k1tot >= 1.0f) {
957                                         k1tot -= 1.0f;
958                                         k1 += elemsize;
959                                 }
960                         }
961                         else k1 += elemsize;
962                 }
963                 if (flagdo & 2) {
964                         if (flagflo & 2) {
965                                 k2tot += k2d;
966                                 while (k2tot >= 1.0f) {
967                                         k2tot -= 1.0f;
968                                         k2 += elemsize;
969                                 }
970                         }
971                         else k2 += elemsize;
972                 }
973                 if (flagdo & 4) {
974                         if (flagflo & 4) {
975                                 k3tot += k3d;
976                                 while (k3tot >= 1.0f) {
977                                         k3tot -= 1.0f;
978                                         k3 += elemsize;
979                                 }
980                         }
981                         else k3 += elemsize;
982                 }
983                 if (flagdo & 8) {
984                         if (flagflo & 8) {
985                                 k4tot += k4d;
986                                 while (k4tot >= 1.0f) {
987                                         k4tot -= 1.0f;
988                                         k4 += elemsize;
989                                 }
990                         }
991                         else k4 += elemsize;
992                 }
993                 
994                 if (mode == KEY_MODE_BEZTRIPLE) a += 2;
995         }
996
997         if (freek1) MEM_freeN(freek1);
998         if (freek2) MEM_freeN(freek2);
999         if (freek3) MEM_freeN(freek3);
1000         if (freek4) MEM_freeN(freek4);
1001 }
1002
1003 static float *get_weights_array(Object *ob, char *vgroup)
1004 {
1005         MDeformVert *dvert = NULL;
1006         BMEditMesh *em = NULL;
1007         BMIter iter;
1008         BMVert *eve;
1009         int totvert = 0, defgrp_index = 0;
1010         
1011         /* no vgroup string set? */
1012         if (vgroup[0] == 0) return NULL;
1013         
1014         /* gather dvert and totvert */
1015         if (ob->type == OB_MESH) {
1016                 Mesh *me = ob->data;
1017                 dvert = me->dvert;
1018                 totvert = me->totvert;
1019
1020                 if (me->edit_btmesh && me->edit_btmesh->bm->totvert == totvert)
1021                         em = me->edit_btmesh;
1022         }
1023         else if (ob->type == OB_LATTICE) {
1024                 Lattice *lt = ob->data;
1025                 dvert = lt->dvert;
1026                 totvert = lt->pntsu * lt->pntsv * lt->pntsw;
1027         }
1028         
1029         if (dvert == NULL) return NULL;
1030         
1031         /* find the group (weak loop-in-loop) */
1032         defgrp_index = defgroup_name_index(ob, vgroup);
1033         if (defgrp_index != -1) {
1034                 float *weights;
1035                 int i;
1036                 
1037                 weights = MEM_callocN(totvert * sizeof(float), "weights");
1038
1039                 if (em) {
1040                         BM_ITER_MESH_INDEX (eve, &iter, em->bm, BM_VERTS_OF_MESH, i) {
1041                                 dvert = CustomData_bmesh_get(&em->bm->vdata, eve->head.data, CD_MDEFORMVERT);
1042
1043                                 if (dvert) {
1044                                         weights[i] = defvert_find_weight(dvert, defgrp_index);
1045                                 }
1046                         }
1047                 }
1048                 else {
1049                         for (i = 0; i < totvert; i++, dvert++) {
1050                                 weights[i] = defvert_find_weight(dvert, defgrp_index);
1051                         }
1052                 }
1053
1054                 return weights;
1055         }
1056         return NULL;
1057 }
1058
1059 static void do_mesh_key(Scene *scene, Object *ob, Key *key, char *out, const int tot)
1060 {
1061         KeyBlock *k[4], *actkb = BKE_keyblock_from_object(ob);
1062         float t[4];
1063         int flag = 0;
1064
1065         if (key->slurph && key->type != KEY_RELATIVE) {
1066                 const float ctime_scaled = key->ctime / 100.0f;
1067                 float delta = (float)key->slurph / tot;
1068                 float cfra = (float)scene->r.cfra + scene->r.subframe;
1069                 int step, a;
1070
1071                 if (tot > 100 && slurph_opt) {
1072                         step = tot / 50;
1073                         delta *= step;
1074                         /* in do_key and cp_key the case a>tot is handled */
1075                 }
1076                 else {
1077                         step = 1;
1078                 }
1079
1080                 for (a = 0; a < tot; a += step, cfra += delta) {
1081                         flag = setkeys(ctime_scaled, &key->block, k, t, 0);
1082
1083                         if (flag == 0)
1084                                 do_key(a, a + step, tot, (char *)out, key, actkb, k, t, KEY_MODE_DUMMY);
1085                         else
1086                                 cp_key(a, a + step, tot, (char *)out, key, actkb, k[2], NULL, KEY_MODE_DUMMY);
1087                 }
1088         }
1089         else {
1090                 if (key->type == KEY_RELATIVE) {
1091                         KeyBlock *kb;
1092                         for (kb = key->block.first; kb; kb = kb->next) {
1093                                 kb->weights = get_weights_array(ob, kb->vgroup);
1094                         }
1095
1096                         BKE_key_evaluate_relative(0, tot, tot, (char *)out, key, actkb, KEY_MODE_DUMMY);
1097                         
1098                         for (kb = key->block.first; kb; kb = kb->next) {
1099                                 if (kb->weights) MEM_freeN(kb->weights);
1100                                 kb->weights = NULL;
1101                         }
1102                 }
1103                 else {
1104                         const float ctime_scaled = key->ctime / 100.0f;
1105
1106                         flag = setkeys(ctime_scaled, &key->block, k, t, 0);
1107
1108                         if (flag == 0)
1109                                 do_key(0, tot, tot, (char *)out, key, actkb, k, t, KEY_MODE_DUMMY);
1110                         else
1111                                 cp_key(0, tot, tot, (char *)out, key, actkb, k[2], NULL, KEY_MODE_DUMMY);
1112                 }
1113         }
1114 }
1115
1116 static void do_cu_key(Curve *cu, Key *key, KeyBlock *actkb, KeyBlock **k, float *t, char *out, const int tot)
1117 {
1118         Nurb *nu;
1119         int a, step;
1120         
1121         for (a = 0, nu = cu->nurb.first; nu; nu = nu->next, a += step) {
1122                 if (nu->bp) {
1123                         step = nu->pntsu * nu->pntsv;
1124                         do_key(a, a + step, tot, out, key, actkb, k, t, KEY_MODE_BPOINT);
1125                 }
1126                 else if (nu->bezt) {
1127                         step = 3 * nu->pntsu;
1128                         do_key(a, a + step, tot, out, key, actkb, k, t, KEY_MODE_BEZTRIPLE);
1129                 }
1130                 else {
1131                         step = 0;
1132                 }
1133         }
1134 }
1135
1136 static void do_rel_cu_key(Curve *cu, Key *key, KeyBlock *actkb, char *out, const int tot)
1137 {
1138         Nurb *nu;
1139         int a, step;
1140         
1141         for (a = 0, nu = cu->nurb.first; nu; nu = nu->next, a += step) {
1142                 if (nu->bp) {
1143                         step = nu->pntsu * nu->pntsv;
1144                         BKE_key_evaluate_relative(a, a + step, tot, out, key, actkb, KEY_MODE_BPOINT);
1145                 }
1146                 else if (nu->bezt) {
1147                         step = 3 * nu->pntsu;
1148                         BKE_key_evaluate_relative(a, a + step, tot, out, key, actkb, KEY_MODE_BEZTRIPLE);
1149                 }
1150                 else {
1151                         step = 0;
1152                 }
1153         }
1154 }
1155
1156 static void do_curve_key(Scene *scene, Object *ob, Key *key, char *out, const int tot)
1157 {
1158         Curve *cu = ob->data;
1159         KeyBlock *k[4], *actkb = BKE_keyblock_from_object(ob);
1160         float t[4];
1161         int flag = 0;
1162
1163         if (key->slurph && key->type != KEY_RELATIVE) {
1164                 const float ctime_scaled = key->ctime / 100.0f;
1165                 float delta = (float)key->slurph / tot;
1166                 float cfra = (float)scene->r.cfra + scene->r.subframe;
1167                 Nurb *nu;
1168                 int i = 0, remain = 0;
1169                 int step, a;
1170
1171                 if (tot > 100 && slurph_opt) {
1172                         step = tot / 50;
1173                         delta *= step;
1174                         /* in do_key and cp_key the case a>tot has been handled */
1175                 }
1176                 else {
1177                         step = 1;
1178                 }
1179
1180                 for (nu = cu->nurb.first; nu; nu = nu->next) {
1181                         int estep, mode;
1182
1183                         if (nu->bp) {
1184                                 mode = KEY_MODE_BPOINT;
1185                                 estep = nu->pntsu * nu->pntsv;
1186                         }
1187                         else if (nu->bezt) {
1188                                 mode = KEY_MODE_BEZTRIPLE;
1189                                 estep = 3 * nu->pntsu;
1190                         }
1191                         else {
1192                                 mode = 0;
1193                                 estep = 0;
1194                         }
1195
1196                         a = 0;
1197                         while (a < estep) {
1198                                 int count;
1199
1200                                 if (remain <= 0) {
1201                                         cfra += delta;
1202                                         flag = setkeys(ctime_scaled, &key->block, k, t, 0);
1203
1204                                         remain = step;
1205                                 }
1206
1207                                 count = min_ii(remain, estep);
1208                                 if (mode == KEY_MODE_BEZTRIPLE) {
1209                                         count += 3 - count % 3;
1210                                 }
1211
1212                                 if (flag == 0)
1213                                         do_key(i, i + count, tot, (char *)out, key, actkb, k, t, mode);
1214                                 else
1215                                         cp_key(i, i + count, tot, (char *)out, key, actkb, k[2], NULL, mode);
1216
1217                                 a += count;
1218                                 i += count;
1219                                 remain -= count;
1220                         }
1221                 }
1222         }
1223         else {
1224                 if (key->type == KEY_RELATIVE) {
1225                         do_rel_cu_key(cu, cu->key, actkb, out, tot);
1226                 }
1227                 else {
1228                         const float ctime_scaled = key->ctime / 100.0f;
1229
1230                         flag = setkeys(ctime_scaled, &key->block, k, t, 0);
1231
1232                         if (flag == 0) do_cu_key(cu, key, actkb, k, t, out, tot);
1233                         else cp_cu_key(cu, key, actkb, k[2], 0, tot, out, tot);
1234                 }
1235         }
1236 }
1237
1238 static void do_latt_key(Scene *scene, Object *ob, Key *key, char *out, const int tot)
1239 {
1240         Lattice *lt = ob->data;
1241         KeyBlock *k[4], *actkb = BKE_keyblock_from_object(ob);
1242         float t[4];
1243         int flag;
1244         
1245         if (key->slurph && key->type != KEY_RELATIVE) {
1246                 const float ctime_scaled = key->ctime / 100.0f;
1247                 float delta = (float)key->slurph / tot;
1248                 float cfra = (float)scene->r.cfra + scene->r.subframe;
1249                 int a;
1250
1251                 for (a = 0; a < tot; a++, cfra += delta) {
1252                         flag = setkeys(ctime_scaled, &key->block, k, t, 0);
1253
1254                         if (flag == 0)
1255                                 do_key(a, a + 1, tot, out, key, actkb, k, t, KEY_MODE_DUMMY);
1256                         else
1257                                 cp_key(a, a + 1, tot, out, key, actkb, k[2], NULL, KEY_MODE_DUMMY);
1258                 }
1259         }
1260         else {
1261                 if (key->type == KEY_RELATIVE) {
1262                         KeyBlock *kb;
1263                         
1264                         for (kb = key->block.first; kb; kb = kb->next)
1265                                 kb->weights = get_weights_array(ob, kb->vgroup);
1266                         
1267                         BKE_key_evaluate_relative(0, tot, tot, out, key, actkb, KEY_MODE_DUMMY);
1268                         
1269                         for (kb = key->block.first; kb; kb = kb->next) {
1270                                 if (kb->weights) MEM_freeN(kb->weights);
1271                                 kb->weights = NULL;
1272                         }
1273                 }
1274                 else {
1275                         const float ctime_scaled = key->ctime / 100.0f;
1276                         
1277                         flag = setkeys(ctime_scaled, &key->block, k, t, 0);
1278
1279                         if (flag == 0)
1280                                 do_key(0, tot, tot, (char *)out, key, actkb, k, t, KEY_MODE_DUMMY);
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(Scene *scene, Object *ob, int *r_totelem)
1291 {
1292         Key *key = BKE_key_from_object(ob);
1293         KeyBlock *actkb = BKE_keyblock_from_object(ob);
1294         char *out;
1295         int tot = 0, size = 0;
1296
1297         if (key == NULL || key->block.first == NULL)
1298                 return NULL;
1299
1300         /* compute size of output array */
1301         if (ob->type == OB_MESH) {
1302                 Mesh *me = ob->data;
1303
1304                 tot = me->totvert;
1305                 size = tot * 3 * sizeof(float);
1306         }
1307         else if (ob->type == OB_LATTICE) {
1308                 Lattice *lt = ob->data;
1309
1310                 tot = lt->pntsu * lt->pntsv * lt->pntsw;
1311                 size = tot * 3 * sizeof(float);
1312         }
1313         else if (ELEM(ob->type, OB_CURVE, OB_SURF)) {
1314                 Curve *cu = ob->data;
1315                 Nurb *nu;
1316
1317                 for (nu = cu->nurb.first; nu; nu = nu->next) {
1318                         if (nu->bezt) {
1319                                 tot += 3 * nu->pntsu;
1320                                 size += nu->pntsu * 12 * sizeof(float);
1321                         }
1322                         else if (nu->bp) {
1323                                 tot += nu->pntsu * nu->pntsv;
1324                                 size += nu->pntsu * nu->pntsv * 12 * sizeof(float);
1325                         }
1326                 }
1327         }
1328
1329         /* if nothing to interpolate, cancel */
1330         if (tot == 0 || size == 0)
1331                 return NULL;
1332         
1333         /* allocate array */
1334         out = MEM_callocN(size, "BKE_key_evaluate_object out");
1335
1336         /* prevent python from screwing this up? anyhoo, the from pointer could be dropped */
1337         key->from = (ID *)ob->data;
1338                 
1339         if (ob->shapeflag & OB_SHAPE_LOCK) {
1340                 /* shape locked, copy the locked shape instead of blending */
1341                 KeyBlock *kb = BLI_findlink(&key->block, ob->shapenr - 1);
1342                 
1343                 if (kb && (kb->flag & KEYBLOCK_MUTE))
1344                         kb = key->refkey;
1345
1346                 if (kb == NULL) {
1347                         kb = key->block.first;
1348                         ob->shapenr = 1;
1349                 }
1350                 
1351                 if (OB_TYPE_SUPPORT_VGROUP(ob->type)) {
1352                         float *weights = get_weights_array(ob, kb->vgroup);
1353
1354                         cp_key(0, tot, tot, out, key, actkb, kb, weights, 0);
1355
1356                         if (weights) MEM_freeN(weights);
1357                 }
1358                 else if (ELEM(ob->type, OB_CURVE, OB_SURF))
1359                         cp_cu_key(ob->data, key, actkb, kb, 0, tot, out, tot);
1360         }
1361         else {
1362                 /* do shapekey local drivers */
1363                 float ctime = (float)scene->r.cfra + scene->r.subframe;
1364
1365                 BKE_animsys_evaluate_animdata(scene, &key->id, key->adt, ctime, ADT_RECALC_DRIVERS);
1366                 
1367                 if (ob->type == OB_MESH) do_mesh_key(scene, ob, key, out, tot);
1368                 else if (ob->type == OB_LATTICE) do_latt_key(scene, ob, key, out, tot);
1369                 else if (ob->type == OB_CURVE) do_curve_key(scene, ob, key, out, tot);
1370                 else if (ob->type == OB_SURF) do_curve_key(scene, ob, key, out, tot);
1371         }
1372         
1373         if (r_totelem) {
1374                 *r_totelem = tot;
1375         }
1376         return (float *)out;
1377 }
1378
1379 Key *BKE_key_from_object(Object *ob)
1380 {
1381         if (ob == NULL) return NULL;
1382         
1383         if (ob->type == OB_MESH) {
1384                 Mesh *me = ob->data;
1385                 return me->key;
1386         }
1387         else if (ELEM(ob->type, OB_CURVE, OB_SURF)) {
1388                 Curve *cu = ob->data;
1389                 return cu->key;
1390         }
1391         else if (ob->type == OB_LATTICE) {
1392                 Lattice *lt = ob->data;
1393                 return lt->key;
1394         }
1395         return NULL;
1396 }
1397
1398 KeyBlock *BKE_keyblock_add(Key *key, const char *name)
1399 {
1400         KeyBlock *kb;
1401         float curpos = -0.1;
1402         int tot;
1403         
1404         kb = key->block.last;
1405         if (kb) curpos = kb->pos;
1406         
1407         kb = MEM_callocN(sizeof(KeyBlock), "Keyblock");
1408         BLI_addtail(&key->block, kb);
1409         kb->type = KEY_CARDINAL;
1410         
1411         tot = BLI_countlist(&key->block);
1412         if (name) {
1413                 BLI_strncpy(kb->name, name, sizeof(kb->name));
1414         }
1415         else {
1416                 if (tot == 1) BLI_strncpy(kb->name, "Basis", sizeof(kb->name));
1417                 else BLI_snprintf(kb->name, sizeof(kb->name), "Key %d", tot - 1);
1418         }
1419
1420         BLI_uniquename(&key->block, kb, "Key", '.', offsetof(KeyBlock, name), sizeof(kb->name));
1421
1422         kb->uid = key->uidgen++;
1423
1424         key->totkey++;
1425         if (key->totkey == 1) key->refkey = kb;
1426         
1427         kb->slidermin = 0.0f;
1428         kb->slidermax = 1.0f;
1429
1430         /**
1431          * \note caller may want to set this to current time, but don't do it here since we need to sort
1432          * which could cause problems in some cases, see #BKE_keyblock_add_ctime */
1433         kb->pos = curpos + 0.1f; /* only used for absolute shape keys */
1434
1435         return kb;
1436 }
1437
1438 /**
1439  * \note sorting is a problematic side effect in some cases,
1440  * better only do this explicitly by having its own function,
1441  *
1442  * \param key The key datablock to add to.
1443  * \param name Optional name for the new keyblock.
1444  * \param do_force always use ctime even for relative keys.
1445  */
1446 KeyBlock *BKE_keyblock_add_ctime(Key *key, const char *name, const short do_force)
1447 {
1448         KeyBlock *kb = BKE_keyblock_add(key, name);
1449
1450         if (do_force || (key->type != KEY_RELATIVE)) {
1451                 kb->pos = key->ctime / 100.0f;
1452                 BKE_key_sort(key);
1453         }
1454
1455         return kb;
1456 }
1457
1458 /* only the active keyblock */
1459 KeyBlock *BKE_keyblock_from_object(Object *ob) 
1460 {
1461         Key *key = BKE_key_from_object(ob);
1462         
1463         if (key) {
1464                 KeyBlock *kb = BLI_findlink(&key->block, ob->shapenr - 1);
1465                 return kb;
1466         }
1467
1468         return NULL;
1469 }
1470
1471 KeyBlock *BKE_keyblock_from_object_reference(Object *ob)
1472 {
1473         Key *key = BKE_key_from_object(ob);
1474         
1475         if (key)
1476                 return key->refkey;
1477
1478         return NULL;
1479 }
1480
1481 /* get the appropriate KeyBlock given an index */
1482 KeyBlock *BKE_keyblock_from_key(Key *key, int index)
1483 {
1484         KeyBlock *kb;
1485         int i;
1486         
1487         if (key) {
1488                 kb = key->block.first;
1489                 
1490                 for (i = 1; i < key->totkey; i++) {
1491                         kb = kb->next;
1492                         
1493                         if (index == i)
1494                                 return kb;
1495                 }
1496         }
1497         
1498         return NULL;
1499 }
1500
1501 /* get the appropriate KeyBlock given a name to search for */
1502 KeyBlock *BKE_keyblock_find_name(Key *key, const char name[])
1503 {
1504         return BLI_findstring(&key->block, name, offsetof(KeyBlock, name));
1505 }
1506
1507 /**
1508  * \brief copy shape-key attributes, but not key data.or name/uid
1509  */
1510 void BKE_keyblock_copy_settings(KeyBlock *kb_dst, const KeyBlock *kb_src)
1511 {
1512         kb_dst->pos        = kb_src->pos;
1513         kb_dst->curval     = kb_src->curval;
1514         kb_dst->type       = kb_src->type;
1515         kb_dst->relative   = kb_src->relative;
1516         BLI_strncpy(kb_dst->vgroup, kb_src->vgroup, sizeof(kb_dst->vgroup));
1517         kb_dst->slidermin  = kb_src->slidermin;
1518         kb_dst->slidermax  = kb_src->slidermax;
1519 }
1520
1521 /* Get RNA-Path for 'value' setting of the given ShapeKey 
1522  * NOTE: the user needs to free the returned string once they're finish with it
1523  */
1524 char *BKE_keyblock_curval_rnapath_get(Key *key, KeyBlock *kb)
1525 {
1526         PointerRNA ptr;
1527         PropertyRNA *prop;
1528         
1529         /* sanity checks */
1530         if (ELEM(NULL, key, kb))
1531                 return NULL;
1532         
1533         /* create the RNA pointer */
1534         RNA_pointer_create(&key->id, &RNA_ShapeKey, kb, &ptr);
1535         /* get pointer to the property too */
1536         prop = RNA_struct_find_property(&ptr, "value");
1537         
1538         /* return the path */
1539         return RNA_path_from_ID_to_property(&ptr, prop);
1540 }
1541
1542
1543 /* conversion functions */
1544
1545 /************************* Lattice ************************/
1546 void BKE_key_convert_from_lattice(Lattice *lt, KeyBlock *kb)
1547 {
1548         BPoint *bp;
1549         float *fp;
1550         int a, tot;
1551
1552         tot = lt->pntsu * lt->pntsv * lt->pntsw;
1553         if (tot == 0) return;
1554
1555         if (kb->data) MEM_freeN(kb->data);
1556
1557         kb->data = MEM_callocN(lt->key->elemsize * tot, "kb->data");
1558         kb->totelem = tot;
1559
1560         bp = lt->def;
1561         fp = kb->data;
1562         for (a = 0; a < kb->totelem; a++, fp += 3, bp++) {
1563                 copy_v3_v3(fp, bp->vec);
1564         }
1565 }
1566
1567 void BKE_key_convert_to_lattice(KeyBlock *kb, Lattice *lt)
1568 {
1569         BPoint *bp;
1570         float *fp;
1571         int a, tot;
1572
1573         bp = lt->def;
1574         fp = kb->data;
1575
1576         tot = lt->pntsu * lt->pntsv * lt->pntsw;
1577         tot = min_ii(kb->totelem, tot);
1578
1579         for (a = 0; a < tot; a++, fp += 3, bp++) {
1580                 copy_v3_v3(bp->vec, fp);
1581         }
1582 }
1583
1584 /************************* Curve ************************/
1585 void BKE_key_convert_from_curve(Curve *cu, KeyBlock *kb, ListBase *nurb)
1586 {
1587         Nurb *nu;
1588         BezTriple *bezt;
1589         BPoint *bp;
1590         float *fp;
1591         int a, tot;
1592
1593         /* count */
1594         tot = BKE_nurbList_verts_count(nurb);
1595         if (tot == 0) return;
1596
1597         if (kb->data) MEM_freeN(kb->data);
1598
1599         kb->data = MEM_callocN(cu->key->elemsize * tot, "kb->data");
1600         kb->totelem = tot;
1601
1602         nu = nurb->first;
1603         fp = kb->data;
1604         while (nu) {
1605
1606                 if (nu->bezt) {
1607                         bezt = nu->bezt;
1608                         a = nu->pntsu;
1609                         while (a--) {
1610                                 copy_v3_v3(fp, bezt->vec[0]);
1611                                 fp += 3;
1612                                 copy_v3_v3(fp, bezt->vec[1]);
1613                                 fp += 3;
1614                                 copy_v3_v3(fp, bezt->vec[2]);
1615                                 fp += 3;
1616                                 fp[0] = bezt->alfa;
1617                                 fp += 3; /* alphas */
1618                                 bezt++;
1619                         }
1620                 }
1621                 else {
1622                         bp = nu->bp;
1623                         a = nu->pntsu * nu->pntsv;
1624                         while (a--) {
1625                                 copy_v3_v3(fp, bp->vec);
1626                                 fp[3] = bp->alfa;
1627
1628                                 fp += 4;
1629                                 bp++;
1630                         }
1631                 }
1632                 nu = nu->next;
1633         }
1634 }
1635
1636 void BKE_key_convert_to_curve(KeyBlock *kb, Curve *UNUSED(cu), ListBase *nurb)
1637 {
1638         Nurb *nu;
1639         BezTriple *bezt;
1640         BPoint *bp;
1641         float *fp;
1642         int a, tot;
1643
1644         nu = nurb->first;
1645         fp = kb->data;
1646
1647         tot = BKE_nurbList_verts_count(nurb);
1648
1649         tot = min_ii(kb->totelem, tot);
1650
1651         while (nu && tot > 0) {
1652
1653                 if (nu->bezt) {
1654                         bezt = nu->bezt;
1655                         a = nu->pntsu;
1656                         while (a-- && tot > 0) {
1657                                 copy_v3_v3(bezt->vec[0], fp);
1658                                 fp += 3;
1659                                 copy_v3_v3(bezt->vec[1], fp);
1660                                 fp += 3;
1661                                 copy_v3_v3(bezt->vec[2], fp);
1662                                 fp += 3;
1663                                 bezt->alfa = fp[0];
1664                                 fp += 3; /* alphas */
1665
1666                                 tot -= 3;
1667                                 bezt++;
1668                         }
1669                 }
1670                 else {
1671                         bp = nu->bp;
1672                         a = nu->pntsu * nu->pntsv;
1673                         while (a-- && tot > 0) {
1674                                 copy_v3_v3(bp->vec, fp);
1675                                 bp->alfa = fp[3];
1676
1677                                 fp += 4;
1678                                 tot--;
1679                                 bp++;
1680                         }
1681                 }
1682                 nu = nu->next;
1683         }
1684 }
1685
1686 /************************* Mesh ************************/
1687 void BKE_key_convert_from_mesh(Mesh *me, KeyBlock *kb)
1688 {
1689         MVert *mvert;
1690         float *fp;
1691         int a;
1692
1693         if (me->totvert == 0) return;
1694
1695         if (kb->data) MEM_freeN(kb->data);
1696
1697         kb->data = MEM_callocN(me->key->elemsize * me->totvert, "kb->data");
1698         kb->totelem = me->totvert;
1699
1700         mvert = me->mvert;
1701         fp = kb->data;
1702         for (a = 0; a < kb->totelem; a++, fp += 3, mvert++) {
1703                 copy_v3_v3(fp, mvert->co);
1704
1705         }
1706 }
1707
1708 void BKE_key_convert_to_mesh(KeyBlock *kb, Mesh *me)
1709 {
1710         MVert *mvert;
1711         float *fp;
1712         int a, tot;
1713
1714         mvert = me->mvert;
1715         fp = kb->data;
1716
1717         tot = min_ii(kb->totelem, me->totvert);
1718
1719         for (a = 0; a < tot; a++, fp += 3, mvert++) {
1720                 copy_v3_v3(mvert->co, fp);
1721         }
1722 }
1723
1724 /************************* vert coords ************************/
1725 float (*BKE_key_convert_to_vertcos(Object *ob, KeyBlock *kb))[3]
1726 {
1727         float (*vertCos)[3], *co;
1728         float *fp = kb->data;
1729         int tot = 0, a;
1730
1731         /* Count of vertex coords in array */
1732         if (ob->type == OB_MESH) {
1733                 Mesh *me = (Mesh *)ob->data;
1734                 tot = me->totvert;
1735         }
1736         else if (ob->type == OB_LATTICE) {
1737                 Lattice *lt = (Lattice *)ob->data;
1738                 tot = lt->pntsu * lt->pntsv * lt->pntsw;
1739         }
1740         else if (ELEM(ob->type, OB_CURVE, OB_SURF)) {
1741                 Curve *cu = (Curve *)ob->data;
1742                 tot = BKE_nurbList_verts_count(&cu->nurb);
1743         }
1744
1745         if (tot == 0) return NULL;
1746
1747         vertCos = MEM_callocN(tot * sizeof(*vertCos), "BKE_key_convert_to_vertcos vertCos");
1748
1749         /* Copy coords to array */
1750         co = (float *)vertCos;
1751
1752         if (ELEM(ob->type, OB_MESH, OB_LATTICE)) {
1753                 for (a = 0; a < tot; a++, fp += 3, co += 3) {
1754                         copy_v3_v3(co, fp);
1755                 }
1756         }
1757         else if (ELEM(ob->type, OB_CURVE, OB_SURF)) {
1758                 Curve *cu = (Curve *)ob->data;
1759                 Nurb *nu = cu->nurb.first;
1760                 BezTriple *bezt;
1761                 BPoint *bp;
1762
1763                 while (nu) {
1764                         if (nu->bezt) {
1765                                 int i;
1766                                 bezt = nu->bezt;
1767                                 a = nu->pntsu;
1768
1769                                 while (a--) {
1770                                         for (i = 0; i < 3; i++) {
1771                                                 copy_v3_v3(co, fp);
1772                                                 fp += 3; co += 3;
1773                                         }
1774
1775                                         fp += 3; /* skip alphas */
1776
1777                                         bezt++;
1778                                 }
1779                         }
1780                         else {
1781                                 bp = nu->bp;
1782                                 a = nu->pntsu * nu->pntsv;
1783
1784                                 while (a--) {
1785                                         copy_v3_v3(co, fp);
1786
1787                                         fp += 4;
1788                                         co += 3;
1789
1790                                         bp++;
1791                                 }
1792                         }
1793
1794                         nu = nu->next;
1795                 }
1796         }
1797
1798         return vertCos;
1799 }
1800
1801 void BKE_key_convert_from_vertcos(Object *ob, KeyBlock *kb, float (*vertCos)[3])
1802 {
1803         float *co = (float *)vertCos, *fp;
1804         int tot = 0, a, elemsize;
1805
1806         if (kb->data) MEM_freeN(kb->data);
1807
1808         /* Count of vertex coords in array */
1809         if (ob->type == OB_MESH) {
1810                 Mesh *me = (Mesh *)ob->data;
1811                 tot = me->totvert;
1812                 elemsize = me->key->elemsize;
1813         }
1814         else if (ob->type == OB_LATTICE) {
1815                 Lattice *lt = (Lattice *)ob->data;
1816                 tot = lt->pntsu * lt->pntsv * lt->pntsw;
1817                 elemsize = lt->key->elemsize;
1818         }
1819         else if (ELEM(ob->type, OB_CURVE, OB_SURF)) {
1820                 Curve *cu = (Curve *)ob->data;
1821                 elemsize = cu->key->elemsize;
1822                 tot = BKE_nurbList_verts_count(&cu->nurb);
1823         }
1824
1825         if (tot == 0) {
1826                 kb->data = NULL;
1827                 return;
1828         }
1829
1830         fp = kb->data = MEM_callocN(tot * elemsize, "BKE_key_convert_to_vertcos vertCos");
1831
1832         /* Copy coords to keyblock */
1833
1834         if (ELEM(ob->type, OB_MESH, OB_LATTICE)) {
1835                 for (a = 0; a < tot; a++, fp += 3, co += 3) {
1836                         copy_v3_v3(fp, co);
1837                 }
1838         }
1839         else if (ELEM(ob->type, OB_CURVE, OB_SURF)) {
1840                 Curve *cu = (Curve *)ob->data;
1841                 Nurb *nu = cu->nurb.first;
1842                 BezTriple *bezt;
1843                 BPoint *bp;
1844
1845                 while (nu) {
1846                         if (nu->bezt) {
1847                                 int i;
1848                                 bezt = nu->bezt;
1849                                 a = nu->pntsu;
1850
1851                                 while (a--) {
1852                                         for (i = 0; i < 3; i++) {
1853                                                 copy_v3_v3(fp, co);
1854                                                 fp += 3; co += 3;
1855                                         }
1856
1857                                         fp += 3; /* skip alphas */
1858
1859                                         bezt++;
1860                                 }
1861                         }
1862                         else {
1863                                 bp = nu->bp;
1864                                 a = nu->pntsu * nu->pntsv;
1865
1866                                 while (a--) {
1867                                         copy_v3_v3(fp, co);
1868
1869                                         fp += 4;
1870                                         co += 3;
1871
1872                                         bp++;
1873                                 }
1874                         }
1875
1876                         nu = nu->next;
1877                 }
1878         }
1879 }
1880
1881 void BKE_key_convert_from_offset(Object *ob, KeyBlock *kb, float (*ofs)[3])
1882 {
1883         int a;
1884         float *co = (float *)ofs, *fp = kb->data;
1885
1886         if (ELEM(ob->type, OB_MESH, OB_LATTICE)) {
1887                 for (a = 0; a < kb->totelem; a++, fp += 3, co += 3) {
1888                         add_v3_v3(fp, co);
1889                 }
1890         }
1891         else if (ELEM(ob->type, OB_CURVE, OB_SURF)) {
1892                 Curve *cu = (Curve *)ob->data;
1893                 Nurb *nu = cu->nurb.first;
1894                 BezTriple *bezt;
1895                 BPoint *bp;
1896
1897                 while (nu) {
1898                         if (nu->bezt) {
1899                                 int i;
1900                                 bezt = nu->bezt;
1901                                 a = nu->pntsu;
1902
1903                                 while (a--) {
1904                                         for (i = 0; i < 3; i++) {
1905                                                 add_v3_v3(fp, co);
1906                                                 fp += 3; co += 3;
1907                                         }
1908
1909                                         fp += 3; /* skip alphas */
1910
1911                                         bezt++;
1912                                 }
1913                         }
1914                         else {
1915                                 bp = nu->bp;
1916                                 a = nu->pntsu * nu->pntsv;
1917
1918                                 while (a--) {
1919                                         add_v3_v3(fp, co);
1920
1921                                         fp += 4;
1922                                         co += 3;
1923
1924                                         bp++;
1925                                 }
1926                         }
1927
1928                         nu = nu->next;
1929                 }
1930         }
1931 }