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