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