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