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