a34da4377b1f9c1d3852bb9c276246c9662959d0
[blender.git] / source / blender / blenkernel / intern / key.c
1
2 /*  key.c      
3  *  
4  * 
5  * $Id$
6  *
7  * ***** BEGIN GPL LICENSE BLOCK *****
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU General Public License
11  * as published by the Free Software Foundation; either version 2
12  * of the License, or (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
24  * All rights reserved.
25  *
26  * The Original Code is: all of this file.
27  *
28  * Contributor(s): none yet.
29  *
30  * ***** END GPL LICENSE BLOCK *****
31  */
32
33 #include <math.h>
34 #include <string.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "DNA_curve_types.h"
39 #include "DNA_ipo_types.h"
40 #include "DNA_key_types.h"
41 #include "DNA_lattice_types.h"
42 #include "DNA_mesh_types.h"
43 #include "DNA_meshdata_types.h"
44 #include "DNA_object_types.h"
45 #include "DNA_scene_types.h"
46
47 #include "BKE_action.h"
48 #include "BKE_blender.h"
49 #include "BKE_curve.h"
50 #include "BKE_global.h"
51 #include "BKE_ipo.h"
52 #include "BKE_key.h"
53 #include "BKE_lattice.h"
54 #include "BKE_library.h"
55 #include "BKE_mesh.h"
56 #include "BKE_main.h"
57 #include "BKE_object.h"
58 #include "BKE_utildefines.h"
59
60 #include "BLI_blenlib.h"
61
62 #ifdef HAVE_CONFIG_H
63 #include <config.h>
64 #endif
65
66 #define KEY_BPOINT              1
67 #define KEY_BEZTRIPLE   2
68
69 int slurph_opt= 1;
70
71
72 void free_key(Key *key)
73 {
74         KeyBlock *kb;
75         
76         if(key->ipo) key->ipo->id.us--;
77         
78         
79         while( (kb= key->block.first) ) {
80                 
81                 if(kb->data) MEM_freeN(kb->data);
82                 
83                 BLI_remlink(&key->block, kb);
84                 MEM_freeN(kb);
85         }
86         
87 }
88
89 /* GS reads the memory pointed at in a specific ordering. There are,
90  * however two definitions for it. I have jotted them down here, both,
91  * but I think the first one is actually used. The thing is that
92  * big-endian systems might read this the wrong way round. OTOH, we
93  * constructed the IDs that are read out with this macro explicitly as
94  * well. I expect we'll sort it out soon... */
95
96 /* from blendef: */
97 #define GS(a)   (*((short *)(a)))
98
99 /* from misc_util: flip the bytes from x  */
100 /*  #define GS(x) (((unsigned char *)(x))[0] << 8 | ((unsigned char *)(x))[1]) */
101
102 Key *add_key(ID *id)    /* common function */
103 {
104         Key *key;
105         char *el;
106         
107         key= alloc_libblock(&G.main->key, ID_KE, "Key");
108         
109         key->type= KEY_NORMAL;
110         key->from= id;
111         
112         if( GS(id->name)==ID_ME) {
113                 el= key->elemstr;
114                 
115                 el[0]= 3;
116                 el[1]= IPO_FLOAT;
117                 el[2]= 0;
118                 
119                 key->elemsize= 12;
120         }
121         else if( GS(id->name)==ID_LT) {
122                 el= key->elemstr;
123                 
124                 el[0]= 3;
125                 el[1]= IPO_FLOAT;
126                 el[2]= 0;
127                 
128                 key->elemsize= 12;
129         }
130         else if( GS(id->name)==ID_CU) {
131                 el= key->elemstr;
132                 
133                 el[0]= 4;
134                 el[1]= IPO_BPOINT;
135                 el[2]= 0;
136                 
137                 key->elemsize= 16;
138         }
139         
140         return key;
141 }
142
143 Key *copy_key(Key *key)
144 {
145         Key *keyn;
146         KeyBlock *kbn, *kb;
147         
148         if(key==0) return 0;
149         
150         keyn= copy_libblock(key);
151         
152         keyn->ipo= copy_ipo(key->ipo);
153
154         BLI_duplicatelist(&keyn->block, &key->block);
155         
156         kb= key->block.first;
157         kbn= keyn->block.first;
158         while(kbn) {
159                 
160                 if(kbn->data) kbn->data= MEM_dupallocN(kbn->data);
161                 if( kb==key->refkey ) keyn->refkey= kbn;
162                 
163                 kbn= kbn->next;
164                 kb= kb->next;
165         }
166         
167         return keyn;
168 }
169
170 void make_local_key(Key *key)
171 {
172
173     /* - only lib users: do nothing
174     * - only local users: set flag
175     * - mixed: make copy
176     */
177     if(key==0) return;
178         
179         key->id.lib= 0;
180         new_id(0, (ID *)key, 0);
181         make_local_ipo(key->ipo);
182 }
183
184 /*
185  * Sort shape keys and Ipo curves after a change.  This assumes that at most
186  * one key was moved, which is a valid assumption for the places it's
187  * currently being called.
188  */
189
190 void sort_keys(Key *key)
191 {
192         KeyBlock *kb;
193         short i, adrcode;
194         IpoCurve *icu = NULL;
195         KeyBlock *kb2;
196
197         /* locate the key which is out of position */ 
198         for( kb= key->block.first; kb; kb= kb->next )
199                 if( kb->next && kb->pos > kb->next->pos )
200                         break;
201
202         /* if we find a key, move it */
203         if( kb ) {
204                 kb = kb->next; /* next key is the out-of-order one */
205                 BLI_remlink(&key->block, kb);
206
207                 /* find the right location and insert before */
208                 for( kb2=key->block.first; kb2; kb2= kb2->next ) {
209                         if( kb2->pos > kb->pos ) {
210                                 BLI_insertlink(&key->block, kb2->prev, kb);
211                                 break;
212                         }
213                 }
214
215                 /* if more than one Ipo curve, see if this key had a curve */
216
217                 if(key->ipo && key->ipo->curve.first != key->ipo->curve.last ) {
218                         for(icu= key->ipo->curve.first; icu; icu= icu->next) {
219                                 /* if we find the curve, remove it and reinsert in the 
220                                  right place */
221                                 if(icu->adrcode==kb->adrcode) {
222                                         IpoCurve *icu2;
223                                         BLI_remlink(&key->ipo->curve, icu);
224                                         for(icu2= key->ipo->curve.first; icu2; icu2= icu2->next) {
225                                                 if(icu2->adrcode >= kb2->adrcode) {
226                                                         BLI_insertlink(&key->ipo->curve, icu2->prev, icu);
227                                                         break;
228                                                 }
229                                         }
230                                         break;
231                                 }
232                         }
233                 }
234
235                 /* kb points at the moved key, icu at the moved ipo (if it exists).
236                  * go back now and renumber adrcodes */
237
238                 /* first new code */
239                 adrcode = kb2->adrcode;
240                 for( i = kb->adrcode - adrcode; i >= 0; --i, ++adrcode ) {
241                         /* if the next ipo curve matches the current key, renumber it */
242                         if(icu && icu->adrcode == kb->adrcode ) {
243                                 icu->adrcode = adrcode;
244                                 icu = icu->next;
245                         }
246                         /* renumber the shape key */
247                         kb->adrcode = adrcode;
248                         kb = kb->next;
249                 }
250         }
251
252         /* new rule; first key is refkey, this to match drawing channels... */
253         key->refkey= key->block.first;
254 }
255
256 /**************** do the key ****************/
257
258
259 void set_four_ipo(float d, float *data, int type)
260 {
261         float d2, d3, fc;
262         
263         if(type==KEY_LINEAR) {
264                 data[0]= 0.0f;
265                 data[1]= 1.0f-d;
266                 data[2]= d;
267                 data[3]= 0.0f;
268         }
269         else {
270                 d2= d*d;
271                 d3= d2*d;
272                 
273                 if(type==KEY_CARDINAL) {
274
275                         fc= 0.71f;
276                         
277                         data[0]= -fc*d3         +2.0f*fc*d2             -fc*d;
278                         data[1]= (2.0f-fc)*d3   +(fc-3.0f)*d2                           +1.0f;
279                         data[2]= (fc-2.0f)*d3   +(3.0f-2.0f*fc)*d2 +fc*d;
280                         data[3]= fc*d3                  -fc*d2;
281                 }
282                 else if(type==KEY_BSPLINE) {
283
284                         data[0]= -0.16666666f*d3        +0.5f*d2        -0.5f*d +0.16666666f;
285                         data[1]= 0.5f*d3                -d2                             +0.6666666f;
286                         data[2]= -0.5f*d3               +0.5f*d2        +0.5f*d +0.16666666f;
287                         data[3]= 0.16666666f*d3                 ;
288                 }
289         }
290 }
291
292 void set_afgeleide_four_ipo(float d, float *data, int type)
293 {
294         float d2, fc;
295         
296         if(type==KEY_LINEAR) {
297
298         }
299         else {
300                 d2= d*d;
301                 
302                 if(type==KEY_CARDINAL) {
303
304                         fc= 0.71f;
305                         
306                         data[0]= -3.0f*fc*d2            +4.0f*fc*d              -fc;
307                         data[1]= 3.0f*(2.0f-fc)*d2      +2.0f*(fc-3.0f)*d;
308                         data[2]= 3.0f*(fc-2.0f)*d2      +2.0f*(3.0f-2.0f*fc)*d +fc;
309                         data[3]= 3.0f*fc*d2                     -2.0f*fc*d;
310                 }
311                 else if(type==KEY_BSPLINE) {
312
313                         data[0]= -0.16666666f*3.0f*d2   +d      -0.5f;
314                         data[1]= 1.5f*d2                -2.0f*d;
315                         data[2]= -1.5f*d2               +d      +0.5f;
316                         data[3]= 0.16666666f*3.0f*d2                    ;
317                 }
318         }
319 }
320
321 static int setkeys(float fac, ListBase *lb, KeyBlock *k[], float *t, int cycl)
322 {
323         /* return 1 means k[2] is the position, return 0 means interpolate */
324         KeyBlock *k1, *firstkey;
325         float d, dpos, ofs=0, lastpos, temp, fval[4];
326         short bsplinetype;
327
328         firstkey= lb->first;
329         k1= lb->last;
330         lastpos= k1->pos;
331         dpos= lastpos - firstkey->pos;
332
333         if(fac < firstkey->pos) fac= firstkey->pos;
334         else if(fac > k1->pos) fac= k1->pos;
335
336         k1=k[0]=k[1]=k[2]=k[3]= firstkey;
337         t[0]=t[1]=t[2]=t[3]= k1->pos;
338
339         /* if(fac<0.0 || fac>1.0) return 1; */
340
341         if(k1->next==0) return 1;
342
343         if(cycl) {      /* pre-sort */
344                 k[2]= k1->next;
345                 k[3]= k[2]->next;
346                 if(k[3]==0) k[3]=k1;
347                 while(k1) {
348                         if(k1->next==0) k[0]=k1;
349                         k1=k1->next;
350                 }
351                 k1= k[1];
352                 t[0]= k[0]->pos;
353                 t[1]+= dpos;
354                 t[2]= k[2]->pos + dpos;
355                 t[3]= k[3]->pos + dpos;
356                 fac+= dpos;
357                 ofs= dpos;
358                 if(k[3]==k[1]) { 
359                         t[3]+= dpos; 
360                         ofs= 2.0f*dpos;
361                 }
362                 if(fac<t[1]) fac+= dpos;
363                 k1= k[3];
364         }
365         else {          /* pre-sort */
366                 k[2]= k1->next;
367                 t[2]= k[2]->pos;
368                 k[3]= k[2]->next;
369                 if(k[3]==0) k[3]= k[2];
370                 t[3]= k[3]->pos;
371                 k1= k[3];
372         }
373         
374         while( t[2]<fac ) {     /* find correct location */
375                 if(k1->next==0) {
376                         if(cycl) {
377                                 k1= firstkey;
378                                 ofs+= dpos;
379                         }
380                         else if(t[2]==t[3]) break;
381                 }
382                 else k1= k1->next;
383
384                 t[0]= t[1]; 
385                 k[0]= k[1];
386                 t[1]= t[2]; 
387                 k[1]= k[2];
388                 t[2]= t[3]; 
389                 k[2]= k[3];
390                 t[3]= k1->pos+ofs; 
391                 k[3]= k1;
392
393                 if(ofs>2.1+lastpos) break;
394         }
395         
396         bsplinetype= 0;
397         if(k[1]->type==KEY_BSPLINE || k[2]->type==KEY_BSPLINE) bsplinetype= 1;
398
399
400         if(cycl==0) {
401                 if(bsplinetype==0) {    /* B spline doesn't go through the control points */
402                         if(fac<=t[1]) {         /* fac for 1st key */
403                                 t[2]= t[1];
404                                 k[2]= k[1];
405                                 return 1;
406                         }
407                         if(fac>=t[2] ) {        /* fac after 2nd key */
408                                 return 1;
409                         }
410                 }
411                 else if(fac>t[2]) {     /* last key */
412                         fac= t[2];
413                         k[3]= k[2];
414                         t[3]= t[2];
415                 }
416         }
417
418         d= t[2]-t[1];
419         if(d==0.0) {
420                 if(bsplinetype==0) {
421                         return 1;       /* both keys equal */
422                 }
423         }
424         else d= (fac-t[1])/d;
425
426         /* interpolation */
427         
428         set_four_ipo(d, t, k[1]->type);
429
430         if(k[1]->type != k[2]->type) {
431                 set_four_ipo(d, fval, k[2]->type);
432                 
433                 temp= 1.0f-d;
434                 t[0]= temp*t[0]+ d*fval[0];
435                 t[1]= temp*t[1]+ d*fval[1];
436                 t[2]= temp*t[2]+ d*fval[2];
437                 t[3]= temp*t[3]+ d*fval[3];
438         }
439
440         return 0;
441
442 }
443
444 static void flerp(int aantal, float *in, float *f0, float *f1, float *f2, float *f3, float *t)  
445 {
446         int a;
447
448         for(a=0; a<aantal; a++) {
449                 in[a]= t[0]*f0[a]+t[1]*f1[a]+t[2]*f2[a]+t[3]*f3[a];
450         }
451 }
452
453 static void rel_flerp(int aantal, float *in, float *ref, float *out, float fac)
454 {
455         int a;
456         
457         for(a=0; a<aantal; a++) {
458                 in[a]-= fac*(ref[a]-out[a]);
459         }
460 }
461
462 static void cp_key(int start, int end, int tot, char *poin, Key *key, KeyBlock *k, float *weights, int mode)
463 {
464         float ktot = 0.0, kd = 0.0;
465         int elemsize, poinsize = 0, a, *ofsp, ofs[32], flagflo=0;
466         char *k1, *kref;
467         char *cp, elemstr[8];
468
469         if(key->from==NULL) return;
470
471         if( GS(key->from->name)==ID_ME ) {
472                 ofs[0]= sizeof(MVert);
473                 ofs[1]= 0;
474                 poinsize= ofs[0];
475         }
476         else if( GS(key->from->name)==ID_LT ) {
477                 ofs[0]= sizeof(BPoint);
478                 ofs[1]= 0;
479                 poinsize= ofs[0];
480         }
481         else if( GS(key->from->name)==ID_CU ) {
482                 if(mode==KEY_BPOINT) ofs[0]= sizeof(BPoint);
483                 else ofs[0]= sizeof(BezTriple);
484                 
485                 ofs[1]= 0;
486                 poinsize= ofs[0];
487         }
488
489
490         if(end>tot) end= tot;
491         
492         k1= k->data;
493         kref= key->refkey->data;
494         
495         if(tot != k->totelem) {
496                 ktot= 0.0;
497                 flagflo= 1;
498                 if(k->totelem) {
499                         kd= k->totelem/(float)tot;
500                 }
501                 else return;
502         }
503
504         /* this exception is needed for slurphing */
505         if(start!=0) {
506                 
507                 poin+= poinsize*start;
508                 
509                 if(flagflo) {
510                         ktot+= start*kd;
511                         a= (int)floor(ktot);
512                         if(a) {
513                                 ktot-= a;
514                                 k1+= a*key->elemsize;
515                         }
516                 }
517                 else k1+= start*key->elemsize;
518         }       
519         
520         if(mode==KEY_BEZTRIPLE) {
521                 elemstr[0]= 1;
522                 elemstr[1]= IPO_BEZTRIPLE;
523                 elemstr[2]= 0;
524         }
525         
526         /* just do it here, not above! */
527         elemsize= key->elemsize;
528         if(mode==KEY_BEZTRIPLE) elemsize*= 3;
529
530         for(a=start; a<end; a++) {
531                 cp= key->elemstr;
532                 if(mode==KEY_BEZTRIPLE) cp= elemstr;
533
534                 ofsp= ofs;
535                 
536                 while( cp[0] ) {
537                         
538                         switch(cp[1]) {
539                         case IPO_FLOAT:
540                                 
541                                 if(weights) {
542                                         memcpy(poin, kref, sizeof(float)*cp[0]);
543                                         if(*weights!=0.0f)
544                                                 rel_flerp(cp[0], (float *)poin, (float *)kref, (float *)k1, *weights);
545                                         weights++;
546                                 }
547                                 else 
548                                         memcpy(poin, k1, sizeof(float)*cp[0]);
549
550                                 poin+= ofsp[0];
551
552                                 break;
553                         case IPO_BPOINT:
554                                 memcpy(poin, k1, 3*sizeof(float));
555                                 memcpy(poin+4*sizeof(float), k1+3*sizeof(float), sizeof(float));
556                                 
557                                 poin+= ofsp[0];                         
558
559                                 break;
560                         case IPO_BEZTRIPLE:
561                                 memcpy(poin, k1, sizeof(float)*10);
562                                 poin+= ofsp[0]; 
563
564                                 break;
565                         }
566                         
567                         cp+= 2; ofsp++;
568                 }
569                 
570                 /* are we going to be nasty? */
571                 if(flagflo) {
572                         ktot+= kd;
573                         while(ktot>=1.0) {
574                                 ktot-= 1.0;
575                                 k1+= elemsize;
576                                 kref+= elemsize;
577                         }
578                 }
579                 else {
580                         k1+= elemsize;
581                         kref+= elemsize;
582                 }
583                 
584                 if(mode==KEY_BEZTRIPLE) a+=2;
585         }
586 }
587
588 void cp_cu_key(Curve *cu, KeyBlock *kb, int start, int end)
589 {
590         Nurb *nu;
591         int a, step = 0, tot, a1, a2;
592         char *poin;
593
594         tot= count_curveverts(&cu->nurb);
595         nu= cu->nurb.first;
596         a= 0;
597         while(nu) {
598                 if(nu->bp) {
599                         
600                         step= nu->pntsu*nu->pntsv;
601                         
602                         /* exception because keys prefer to work with complete blocks */
603                         poin= (char *)nu->bp->vec;
604                         poin -= a*sizeof(BPoint);
605                         
606                         a1= MAX2(a, start);
607                         a2= MIN2(a+step, end);
608                         
609                         if(a1<a2) cp_key(a1, a2, tot, poin, cu->key, kb, NULL, KEY_BPOINT);
610                 }
611                 else if(nu->bezt) {
612                         
613                         step= 3*nu->pntsu;
614                         
615                         poin= (char *)nu->bezt->vec;
616                         poin -= a*sizeof(BezTriple);
617
618                         a1= MAX2(a, start);
619                         a2= MIN2(a+step, end);
620
621                         if(a1<a2) cp_key(a1, a2, tot, poin, cu->key, kb, NULL, KEY_BEZTRIPLE);
622                         
623                 }
624                 a+= step;
625                 nu=nu->next;
626         }
627 }
628
629
630 void do_rel_key(int start, int end, int tot, char *basispoin, Key *key, int mode)
631 {
632         KeyBlock *kb;
633         int *ofsp, ofs[3], elemsize, b;
634         char *cp, *poin, *reffrom, *from, elemstr[8];
635         
636         if(key->from==NULL) return;
637         
638         if( GS(key->from->name)==ID_ME ) {
639                 ofs[0]= sizeof(MVert);
640                 ofs[1]= 0;
641         }
642         else if( GS(key->from->name)==ID_LT ) {
643                 ofs[0]= sizeof(BPoint);
644                 ofs[1]= 0;
645         }
646         else if( GS(key->from->name)==ID_CU ) {
647                 if(mode==KEY_BPOINT) ofs[0]= sizeof(BPoint);
648                 else ofs[0]= sizeof(BezTriple);
649                 
650                 ofs[1]= 0;
651         }
652         
653         if(end>tot) end= tot;
654         
655         /* in case of beztriple */
656         elemstr[0]= 1;                          /* nr of ipofloats */
657         elemstr[1]= IPO_BEZTRIPLE;
658         elemstr[2]= 0;
659
660         /* just here, not above! */
661         elemsize= key->elemsize;
662         if(mode==KEY_BEZTRIPLE) elemsize*= 3;
663
664         /* step 1 init */
665         cp_key(start, end, tot, basispoin, key, key->refkey, NULL, mode);
666         
667         /* step 2: do it */
668         
669         for(kb=key->block.first; kb; kb=kb->next) {
670                 if(kb!=key->refkey) {
671                         float icuval= kb->curval;
672                         
673                         /* only with value, and no difference allowed */
674                         if(!(kb->flag & KEYBLOCK_MUTE) && icuval!=0.0f && kb->totelem==tot) {
675                                 KeyBlock *refb;
676                                 float weight, *weights= kb->weights;
677                                 
678                                 poin= basispoin;
679                                 from= kb->data;
680                                 /* reference now can be any block */
681                                 refb= BLI_findlink(&key->block, kb->relative);
682                                 if(refb==NULL) continue;
683                                 reffrom= refb->data;
684                                 
685                                 poin+= start*ofs[0];
686                                 reffrom+= key->elemsize*start;  // key elemsize yes!
687                                 from+= key->elemsize*start;
688                                 
689                                 for(b=start; b<end; b++) {
690                                 
691                                         if(weights) 
692                                                 weight= *weights * icuval;
693                                         else
694                                                 weight= icuval;
695                                         
696                                         cp= key->elemstr;       
697                                         if(mode==KEY_BEZTRIPLE) cp= elemstr;
698                                         
699                                         ofsp= ofs;
700                                         
701                                         while( cp[0] ) {        /* cp[0]==amount */
702                                                 
703                                                 switch(cp[1]) {
704                                                 case IPO_FLOAT:
705                                                         rel_flerp(cp[0], (float *)poin, (float *)reffrom, (float *)from, weight);
706                                                         
707                                                         break;
708                                                 case IPO_BPOINT:
709                                                         rel_flerp(3, (float *)poin, (float *)reffrom, (float *)from, icuval);
710                                                         rel_flerp(1, (float *)(poin+16), (float *)(reffrom+16), (float *)(from+16), icuval);
711                         
712                                                         break;
713                                                 case IPO_BEZTRIPLE:
714                                                         rel_flerp(9, (float *)poin, (float *)reffrom, (float *)from, icuval);
715                         
716                                                         break;
717                                                 }
718                                                 
719                                                 poin+= ofsp[0];                         
720                                                 
721                                                 cp+= 2;
722                                                 ofsp++;
723                                         }
724                                         
725                                         reffrom+= elemsize;
726                                         from+= elemsize;
727                                         
728                                         if(mode==KEY_BEZTRIPLE) b+= 2;
729                                         if(weights) weights++;
730                                 }
731                         }
732                 }
733         }
734 }
735
736
737 static void do_key(int start, int end, int tot, char *poin, Key *key, KeyBlock **k, float *t, int mode)
738 {
739         float k1tot = 0.0, k2tot = 0.0, k3tot = 0.0, k4tot = 0.0;
740         float k1d = 0.0, k2d = 0.0, k3d = 0.0, k4d = 0.0;
741         int a, ofs[32], *ofsp;
742         int flagdo= 15, flagflo=0, elemsize, poinsize=0;
743         char *k1, *k2, *k3, *k4;
744         char *cp, elemstr[8];;
745
746         if(key->from==0) return;
747
748         if( GS(key->from->name)==ID_ME ) {
749                 ofs[0]= sizeof(MVert);
750                 ofs[1]= 0;
751                 poinsize= ofs[0];
752         }
753         else if( GS(key->from->name)==ID_LT ) {
754                 ofs[0]= sizeof(BPoint);
755                 ofs[1]= 0;
756                 poinsize= ofs[0];
757         }
758         else if( GS(key->from->name)==ID_CU ) {
759                 if(mode==KEY_BPOINT) ofs[0]= sizeof(BPoint);
760                 else ofs[0]= sizeof(BezTriple);
761                 
762                 ofs[1]= 0;
763                 poinsize= ofs[0];
764         }
765         
766         if(end>tot) end= tot;
767
768         k1= k[0]->data;
769         k2= k[1]->data;
770         k3= k[2]->data;
771         k4= k[3]->data;
772
773         /*  test for more or less points (per key!) */
774         if(tot != k[0]->totelem) {
775                 k1tot= 0.0;
776                 flagflo |= 1;
777                 if(k[0]->totelem) {
778                         k1d= k[0]->totelem/(float)tot;
779                 }
780                 else flagdo -= 1;
781         }
782         if(tot != k[1]->totelem) {
783                 k2tot= 0.0;
784                 flagflo |= 2;
785                 if(k[0]->totelem) {
786                         k2d= k[1]->totelem/(float)tot;
787                 }
788                 else flagdo -= 2;
789         }
790         if(tot != k[2]->totelem) {
791                 k3tot= 0.0;
792                 flagflo |= 4;
793                 if(k[0]->totelem) {
794                         k3d= k[2]->totelem/(float)tot;
795                 }
796                 else flagdo -= 4;
797         }
798         if(tot != k[3]->totelem) {
799                 k4tot= 0.0;
800                 flagflo |= 8;
801                 if(k[0]->totelem) {
802                         k4d= k[3]->totelem/(float)tot;
803                 }
804                 else flagdo -= 8;
805         }
806
807                 /* this exception needed for slurphing */
808         if(start!=0) {
809
810                 poin+= poinsize*start;
811                 
812                 if(flagdo & 1) {
813                         if(flagflo & 1) {
814                                 k1tot+= start*k1d;
815                                 a= (int)floor(k1tot);
816                                 if(a) {
817                                         k1tot-= a;
818                                         k1+= a*key->elemsize;
819                                 }
820                         }
821                         else k1+= start*key->elemsize;
822                 }
823                 if(flagdo & 2) {
824                         if(flagflo & 2) {
825                                 k2tot+= start*k2d;
826                                 a= (int)floor(k2tot);
827                                 if(a) {
828                                         k2tot-= a;
829                                         k2+= a*key->elemsize;
830                                 }
831                         }
832                         else k2+= start*key->elemsize;
833                 }
834                 if(flagdo & 4) {
835                         if(flagflo & 4) {
836                                 k3tot+= start*k3d;
837                                 a= (int)floor(k3tot);
838                                 if(a) {
839                                         k3tot-= a;
840                                         k3+= a*key->elemsize;
841                                 }
842                         }
843                         else k3+= start*key->elemsize;
844                 }
845                 if(flagdo & 8) {
846                         if(flagflo & 8) {
847                                 k4tot+= start*k4d;
848                                 a= (int)floor(k4tot);
849                                 if(a) {
850                                         k4tot-= a;
851                                         k4+= a*key->elemsize;
852                                 }
853                         }
854                         else k4+= start*key->elemsize;
855                 }
856
857         }
858
859         /* in case of beztriple */
860         elemstr[0]= 1;                          /* nr of ipofloats */
861         elemstr[1]= IPO_BEZTRIPLE;
862         elemstr[2]= 0;
863
864         /* only here, not above! */
865         elemsize= key->elemsize;
866         if(mode==KEY_BEZTRIPLE) elemsize*= 3;
867
868         for(a=start; a<end; a++) {
869         
870                 cp= key->elemstr;       
871                 if(mode==KEY_BEZTRIPLE) cp= elemstr;
872                 
873                 ofsp= ofs;
874                 
875                 while( cp[0] ) {        /* cp[0]==amount */
876                         
877                         switch(cp[1]) {
878                         case IPO_FLOAT:
879                                 flerp(cp[0], (float *)poin, (float *)k1, (float *)k2, (float *)k3, (float *)k4, t);
880                                 poin+= ofsp[0];                         
881
882                                 break;
883                         case IPO_BPOINT:
884                                 flerp(3, (float *)poin, (float *)k1, (float *)k2, (float *)k3, (float *)k4, t);
885                                 flerp(1, (float *)(poin+16), (float *)(k1+12), (float *)(k2+12), (float *)(k3+12), (float *)(k4+12), t);
886                                 
887                                 poin+= ofsp[0];                         
888
889                                 break;
890                         case IPO_BEZTRIPLE:
891                                 flerp(9, (void *)poin, (void *)k1, (void *)k2, (void *)k3, (void *)k4, t);
892                                 flerp(1, (float *)(poin+36), (float *)(k1+36), (float *)(k2+36), (float *)(k3+36), (float *)(k4+36), t);
893                                 poin+= ofsp[0];                         
894
895                                 break;
896                         }
897                         
898
899                         cp+= 2;
900                         ofsp++;
901                 }
902                 /* lets do it the difficult way: when keys have a different size */
903                 if(flagdo & 1) {
904                         if(flagflo & 1) {
905                                 k1tot+= k1d;
906                                 while(k1tot>=1.0) {
907                                         k1tot-= 1.0;
908                                         k1+= elemsize;
909                                 }
910                         }
911                         else k1+= elemsize;
912                 }
913                 if(flagdo & 2) {
914                         if(flagflo & 2) {
915                                 k2tot+= k2d;
916                                 while(k2tot>=1.0) {
917                                         k2tot-= 1.0;
918                                         k2+= elemsize;
919                                 }
920                         }
921                         else k2+= elemsize;
922                 }
923                 if(flagdo & 4) {
924                         if(flagflo & 4) {
925                                 k3tot+= k3d;
926                                 while(k3tot>=1.0) {
927                                         k3tot-= 1.0;
928                                         k3+= elemsize;
929                                 }
930                         }
931                         else k3+= elemsize;
932                 }
933                 if(flagdo & 8) {
934                         if(flagflo & 8) {
935                                 k4tot+= k4d;
936                                 while(k4tot>=1.0) {
937                                         k4tot-= 1.0;
938                                         k4+= elemsize;
939                                 }
940                         }
941                         else k4+= elemsize;
942                 }
943                 
944                 if(mode==KEY_BEZTRIPLE) a+= 2;
945         }
946 }
947
948 static float *get_weights_array(Object *ob, char *vgroup)
949 {
950         bDeformGroup *curdef;
951         MDeformVert *dvert= NULL;
952         int totvert= 0, index= 0;
953         
954         /* no vgroup string set? */
955         if(vgroup[0]==0) return NULL;
956         
957         /* gather dvert and totvert */
958         if(ob->type==OB_MESH) {
959                 Mesh *me= ob->data;
960                 dvert= me->dvert;
961                 totvert= me->totvert;
962         }
963         else if(ob->type==OB_LATTICE) {
964                 Lattice *lt= ob->data;
965                 dvert= lt->dvert;
966                 totvert= lt->pntsu*lt->pntsv*lt->pntsw;
967         }
968         
969         if(dvert==NULL) return NULL;
970         
971         /* find the group (weak loop-in-loop) */
972         for (curdef = ob->defbase.first; curdef; curdef=curdef->next, index++)
973                 if (!strcmp(curdef->name, vgroup))
974                         break;
975
976         if(curdef) {
977                 float *weights;
978                 int i, j;
979                 
980                 weights= MEM_callocN(totvert*sizeof(float), "weights");
981                 
982                 for (i=0; i < totvert; i++, dvert++) {
983                         for(j=0; j<dvert->totweight; j++) {
984                                 if (dvert->dw[j].def_nr == index) {
985                                         weights[i]= dvert->dw[j].weight;
986                                         break;
987                                 }
988                         }
989                 }
990                 return weights;
991         }
992         return NULL;
993 }
994
995 static int do_mesh_key(Object *ob, Mesh *me)
996 {
997         KeyBlock *k[4];
998         float cfra, ctime, t[4], delta, loc[3], size[3];
999         int a, flag = 0, step;
1000         
1001         if(me->totvert==0) return 0;
1002         if(me->key==NULL) return 0;
1003         if(me->key->block.first==NULL) return 0;
1004         
1005         /* prevent python from screwing this up? anyhoo, the from pointer could be dropped */
1006         me->key->from= (ID *)me;
1007         
1008         if(me->key->slurph && me->key->type!=KEY_RELATIVE ) {
1009                 delta= me->key->slurph;
1010                 delta/= me->totvert;
1011                 
1012                 step= 1;
1013                 if(me->totvert>100 && slurph_opt) {
1014                         step= me->totvert/50;
1015                         delta*= step;
1016                         /* in do_key and cp_key the case a>tot is handled */
1017                 }
1018                 
1019                 cfra= G.scene->r.cfra;
1020                 
1021                 for(a=0; a<me->totvert; a+=step, cfra+= delta) {
1022                         
1023                         ctime= bsystem_time(0, cfra, 0.0);
1024                         if(calc_ipo_spec(me->key->ipo, KEY_SPEED, &ctime)==0) {
1025                                 ctime /= 100.0;
1026                                 CLAMP(ctime, 0.0, 1.0);
1027                         }
1028                 
1029                         flag= setkeys(ctime, &me->key->block, k, t, 0);
1030                         if(flag==0) {
1031                                 
1032                                 do_key(a, a+step, me->totvert, (char *)me->mvert->co, me->key, k, t, 0);
1033                         }
1034                         else {
1035                                 cp_key(a, a+step, me->totvert, (char *)me->mvert->co, me->key, k[2], NULL, 0);
1036                         }
1037                 }
1038                 
1039                 if(flag && k[2]==me->key->refkey) tex_space_mesh(me);
1040                 else boundbox_mesh(me, loc, size);
1041         }
1042         else {
1043                 
1044                 if(me->key->type==KEY_RELATIVE) {
1045                         KeyBlock *kb;
1046                         
1047                         for(kb= me->key->block.first; kb; kb= kb->next)
1048                                 kb->weights= get_weights_array(ob, kb->vgroup);
1049
1050                         do_rel_key(0, me->totvert, me->totvert, (char *)me->mvert->co, me->key, 0);
1051                         
1052                         for(kb= me->key->block.first; kb; kb= kb->next) {
1053                                 if(kb->weights) MEM_freeN(kb->weights);
1054                                 kb->weights= NULL;
1055                         }
1056                 }
1057                 else {
1058                         ctime= bsystem_time(ob, G.scene->r.cfra, 0.0);
1059
1060                         if(calc_ipo_spec(me->key->ipo, KEY_SPEED, &ctime)==0) {
1061                                 ctime /= 100.0;
1062                                 CLAMP(ctime, 0.0, 1.0);
1063                         }
1064
1065                         flag= setkeys(ctime, &me->key->block, k, t, 0);
1066                         if(flag==0) {
1067                                 do_key(0, me->totvert, me->totvert, (char *)me->mvert->co, me->key, k, t, 0);
1068                         }
1069                         else {
1070                                 cp_key(0, me->totvert, me->totvert, (char *)me->mvert->co, me->key, k[2], NULL, 0);
1071                         }
1072                         
1073                         if(flag && k[2]==me->key->refkey) tex_space_mesh(me);
1074                         else boundbox_mesh(me, loc, size);
1075                 }
1076         }
1077         return 1;
1078 }
1079
1080 static void do_cu_key(Curve *cu, KeyBlock **k, float *t)
1081 {
1082         Nurb *nu;
1083         int a, step = 0, tot;
1084         char *poin;
1085         
1086         tot= count_curveverts(&cu->nurb);
1087         nu= cu->nurb.first;
1088         a= 0;
1089         
1090         while(nu) {
1091                 if(nu->bp) {
1092                         
1093                         step= nu->pntsu*nu->pntsv;
1094                         
1095                         /* exception because keys prefer to work with complete blocks */
1096                         poin= (char *)nu->bp->vec;
1097                         poin -= a*sizeof(BPoint);
1098                         
1099                         do_key(a, a+step, tot, poin, cu->key, k, t, KEY_BPOINT);
1100                 }
1101                 else if(nu->bezt) {
1102                         
1103                         step= 3*nu->pntsu;
1104                         
1105                         poin= (char *)nu->bezt->vec;
1106                         poin -= a*sizeof(BezTriple);
1107
1108                         do_key(a, a+step, tot, poin, cu->key, k, t, KEY_BEZTRIPLE);
1109                         
1110                 }
1111                 a+= step;
1112                 nu=nu->next;
1113         }
1114 }
1115
1116 static void do_rel_cu_key(Curve *cu, float ctime)
1117 {
1118         Nurb *nu;
1119         int a, step = 0, tot;
1120         char *poin;
1121         
1122         tot= count_curveverts(&cu->nurb);
1123         nu= cu->nurb.first;
1124         a= 0;
1125         while(nu) {
1126                 if(nu->bp) {
1127                         
1128                         step= nu->pntsu*nu->pntsv;
1129                         
1130                         /* exception because keys prefer to work with complete blocks */
1131                         poin= (char *)nu->bp->vec;
1132                         poin -= a*sizeof(BPoint);
1133                         
1134                         do_rel_key(a, a+step, tot, poin, cu->key, KEY_BPOINT);
1135                 }
1136                 else if(nu->bezt) {
1137                         
1138                         step= 3*nu->pntsu;
1139                         
1140                         poin= (char *)nu->bezt->vec;
1141                         poin -= a*sizeof(BezTriple);
1142
1143                         do_rel_key(a, a+step, tot, poin, cu->key, KEY_BEZTRIPLE);
1144                 }
1145                 a+= step;
1146                 
1147                 nu=nu->next;
1148         }
1149 }
1150
1151 static int do_curve_key(Curve *cu)
1152 {
1153         KeyBlock *k[4];
1154         float cfra, ctime, t[4], delta;
1155         int a, flag = 0, step = 0, tot;
1156         
1157         tot= count_curveverts(&cu->nurb);
1158         
1159         if(tot==0) return 0;
1160         if(cu->key==NULL) return 0;
1161         if(cu->key->block.first==NULL) return 0;
1162         
1163         if(cu->key->slurph) {
1164                 delta= cu->key->slurph;
1165                 delta/= tot;
1166                 
1167                 step= 1;
1168                 if(tot>100 && slurph_opt) {
1169                         step= tot/50;
1170                         delta*= step;
1171                         /* in do_key and cp_key the case a>tot has been handled */
1172                 }
1173                 
1174                 cfra= G.scene->r.cfra;
1175                 
1176                 for(a=0; a<tot; a+=step, cfra+= delta) {
1177                         
1178                         ctime= bsystem_time(0, cfra, 0.0);
1179                         if(calc_ipo_spec(cu->key->ipo, KEY_SPEED, &ctime)==0) {
1180                                 ctime /= 100.0;
1181                                 CLAMP(ctime, 0.0, 1.0);
1182                         }
1183                 
1184                         flag= setkeys(ctime, &cu->key->block, k, t, 0);
1185                         if(flag==0) {
1186                                 
1187                                 /* do_key(a, a+step, tot, (char *)cu->mvert->co, cu->key, k, t, 0); */
1188                         }
1189                         else {
1190                                 /* cp_key(a, a+step, tot, (char *)cu->mvert->co, cu->key, k[2],0); */
1191                         }
1192                 }
1193
1194                 if(flag && k[2]==cu->key->refkey) tex_space_curve(cu);
1195                 
1196                 
1197         }
1198         else {
1199                 
1200                 ctime= bsystem_time(NULL, (float)G.scene->r.cfra, 0.0);
1201                 
1202                 if(cu->key->type==KEY_RELATIVE) {
1203                         do_rel_cu_key(cu, ctime);
1204                 }
1205                 else {
1206                         if(calc_ipo_spec(cu->key->ipo, KEY_SPEED, &ctime)==0) {
1207                                 ctime /= 100.0;
1208                                 CLAMP(ctime, 0.0, 1.0);
1209                         }
1210                         
1211                         flag= setkeys(ctime, &cu->key->block, k, t, 0);
1212                         
1213                         if(flag==0) do_cu_key(cu, k, t);
1214                         else cp_cu_key(cu, k[2], 0, tot);
1215                                         
1216                         if(flag && k[2]==cu->key->refkey) tex_space_curve(cu);
1217                 }
1218         }
1219         
1220         return 1;
1221 }
1222
1223 static int do_latt_key(Object *ob, Lattice *lt)
1224 {
1225         KeyBlock *k[4];
1226         float delta, cfra, ctime, t[4];
1227         int a, tot, flag;
1228         
1229         if(lt->key==NULL) return 0;
1230         if(lt->key->block.first==NULL) return 0;
1231
1232         tot= lt->pntsu*lt->pntsv*lt->pntsw;
1233
1234         if(lt->key->slurph) {
1235                 delta= lt->key->slurph;
1236                 delta/= (float)tot;
1237                 
1238                 cfra= G.scene->r.cfra;
1239                 
1240                 for(a=0; a<tot; a++, cfra+= delta) {
1241                         
1242                         ctime= bsystem_time(0, cfra, 0.0);
1243                         if(calc_ipo_spec(lt->key->ipo, KEY_SPEED, &ctime)==0) {
1244                                 ctime /= 100.0;
1245                                 CLAMP(ctime, 0.0, 1.0);
1246                         }
1247                 
1248                         flag= setkeys(ctime, &lt->key->block, k, t, 0);
1249                         if(flag==0) {
1250                                 
1251                                 do_key(a, a+1, tot, (char *)lt->def->vec, lt->key, k, t, 0);
1252                         }
1253                         else {
1254                                 cp_key(a, a+1, tot, (char *)lt->def->vec, lt->key, k[2], NULL, 0);
1255                         }
1256                 }               
1257         }
1258         else {
1259                 ctime= bsystem_time(NULL, (float)G.scene->r.cfra, 0.0);
1260         
1261                 if(lt->key->type==KEY_RELATIVE) {
1262                         KeyBlock *kb;
1263                         
1264                         for(kb= lt->key->block.first; kb; kb= kb->next)
1265                                 kb->weights= get_weights_array(ob, kb->vgroup);
1266                         
1267                         do_rel_key(0, tot, tot, (char *)lt->def->vec, lt->key, 0);
1268                         
1269                         for(kb= lt->key->block.first; kb; kb= kb->next) {
1270                                 if(kb->weights) MEM_freeN(kb->weights);
1271                                 kb->weights= NULL;
1272                         }
1273                 }
1274                 else {
1275                         if(calc_ipo_spec(lt->key->ipo, KEY_SPEED, &ctime)==0) {
1276                                 ctime /= 100.0;
1277                                 CLAMP(ctime, 0.0, 1.0);
1278                         }
1279                         
1280                         flag= setkeys(ctime, &lt->key->block, k, t, 0);
1281                         if(flag==0) {
1282                                 do_key(0, tot, tot, (char *)lt->def->vec, lt->key, k, t, 0);
1283                         }
1284                         else {
1285                                 cp_key(0, tot, tot, (char *)lt->def->vec, lt->key, k[2], NULL, 0);
1286                         }
1287                 }
1288         }
1289         
1290         if(lt->flag & LT_OUTSIDE) outside_lattice(lt);
1291         
1292         return 1;
1293 }
1294
1295 /* returns 1 when key applied */
1296 int do_ob_key(Object *ob)
1297 {
1298         Key *key= ob_get_key(ob);
1299         
1300         if(key==NULL)
1301                 return 0;
1302                 
1303         if(ob->shapeflag & (OB_SHAPE_LOCK|OB_SHAPE_TEMPLOCK)) {
1304                 KeyBlock *kb= BLI_findlink(&key->block, ob->shapenr-1);
1305
1306                 if(kb && (kb->flag & KEYBLOCK_MUTE))
1307                         kb= key->refkey;
1308
1309                 if(kb==NULL) {
1310                         kb= key->block.first;
1311                         ob->shapenr= 1;
1312                 }
1313                 
1314                 if(ob->type==OB_MESH) {
1315                         Mesh *me= ob->data;
1316                         float *weights= get_weights_array(ob, kb->vgroup);
1317
1318                         cp_key(0, me->totvert, me->totvert, (char *)me->mvert->co, key, kb, weights, 0);
1319                         
1320                         if(weights) MEM_freeN(weights);
1321                 }
1322                 else if(ob->type==OB_LATTICE) {
1323                         Lattice *lt= ob->data;
1324                         float *weights= get_weights_array(ob, kb->vgroup);
1325                         int tot= lt->pntsu*lt->pntsv*lt->pntsw;
1326                         
1327                         cp_key(0, tot, tot, (char *)lt->def->vec, key, kb, weights, 0);
1328                         
1329                         if(weights) MEM_freeN(weights);
1330                 }
1331                 else if ELEM(ob->type, OB_CURVE, OB_SURF) {
1332                         Curve *cu= ob->data;
1333                         int tot= count_curveverts(&cu->nurb);
1334                         
1335                         cp_cu_key(cu, kb, 0, tot);
1336                 }
1337                 return 1;
1338         }
1339         else {
1340                 if(ob->ipoflag & OB_ACTION_KEY)
1341                         do_all_object_actions(ob);
1342                 else {
1343                         calc_ipo(key->ipo, bsystem_time(ob, G.scene->r.cfra, 0.0));
1344                         execute_ipo((ID *)key, key->ipo);
1345                 }
1346                 
1347                 if(ob->type==OB_MESH) return do_mesh_key(ob, ob->data);
1348                 else if(ob->type==OB_CURVE) return do_curve_key( ob->data);
1349                 else if(ob->type==OB_SURF) return do_curve_key( ob->data);
1350                 else if(ob->type==OB_LATTICE) return do_latt_key(ob, ob->data);
1351         }
1352         
1353         return 0;
1354 }
1355
1356 Key *ob_get_key(Object *ob)
1357 {
1358         if(ob==NULL) return NULL;
1359         
1360         if(ob->type==OB_MESH) {
1361                 Mesh *me= ob->data;
1362                 return me->key;
1363         }
1364         else if ELEM(ob->type, OB_CURVE, OB_SURF) {
1365                 Curve *cu= ob->data;
1366                 return cu->key;
1367         }
1368         else if(ob->type==OB_LATTICE) {
1369                 Lattice *lt= ob->data;
1370                 return lt->key;
1371         }
1372         return NULL;
1373 }
1374
1375 /* only the active keyblock */
1376 KeyBlock *ob_get_keyblock(Object *ob) 
1377 {
1378         Key *key= ob_get_key(ob);
1379         
1380         if (key) {
1381                 KeyBlock *kb= BLI_findlink(&key->block, ob->shapenr-1);
1382                 return kb;
1383         }
1384
1385         return NULL;
1386 }
1387
1388 /* get the appropriate KeyBlock given an index */
1389 KeyBlock *key_get_keyblock(Key *key, int index)
1390 {
1391         KeyBlock *kb;
1392         int i;
1393         
1394         if (key) {
1395                 kb= key->block.first;
1396                 
1397                 for (i= 1; i < key->totkey; i++) {
1398                         kb= kb->next;
1399                         
1400                         if (index==i)
1401                                 return kb;
1402                 }
1403         }
1404         
1405         return NULL;
1406 }