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