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