d0c0b1f99277f305b5287c4867657ede1c542e19
[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 cp_key(int start, int end, int tot, char *poin, Key *key, KeyBlock *k, int mode)
409 {
410         float ktot = 0.0, kd = 0.0;
411         int elemsize, poinsize = 0, a, *ofsp, ofs[32], flagflo=0;
412         char *k1;
413         char *cp, elemstr[8];
414
415         if(key->from==0) return;
416
417         if( GS(key->from->name)==ID_ME ) {
418                 ofs[0]= sizeof(MVert);
419                 ofs[1]= 0;
420                 poinsize= ofs[0];
421         }
422         else if( GS(key->from->name)==ID_LT ) {
423                 ofs[0]= sizeof(BPoint);
424                 ofs[1]= 0;
425                 poinsize= ofs[0];
426         }
427         else if( GS(key->from->name)==ID_CU ) {
428                 if(mode==KEY_BPOINT) ofs[0]= sizeof(BPoint);
429                 else ofs[0]= sizeof(BezTriple);
430                 
431                 ofs[1]= 0;
432                 poinsize= ofs[0];
433         }
434
435
436         if(end>tot) end= tot;
437         
438         k1= k->data;
439
440         if(tot != k->totelem) {
441                 ktot= 0.0;
442                 flagflo= 1;
443                 if(k->totelem) {
444                         kd= k->totelem/(float)tot;
445                 }
446                 else return;
447         }
448
449         /* this exception is needed for slurphing */
450         if(start!=0) {
451                 
452                 poin+= poinsize*start;
453                 
454                 if(flagflo) {
455                         ktot+= start*kd;
456                         a= (int)floor(ktot);
457                         if(a) {
458                                 ktot-= a;
459                                 k1+= a*key->elemsize;
460                         }
461                 }
462                 else k1+= start*key->elemsize;
463         }       
464         
465
466         if(mode==KEY_BEZTRIPLE) {
467                 elemstr[0]= 1;
468                 elemstr[1]= IPO_BEZTRIPLE;
469                 elemstr[2]= 0;
470         }
471         
472         /* just do it here, not above! */
473         elemsize= key->elemsize;
474         if(mode==KEY_BEZTRIPLE) elemsize*= 3;
475
476         for(a=start; a<end; a++) {
477                 cp= key->elemstr;
478                 if(mode==KEY_BEZTRIPLE) cp= elemstr;
479
480                 ofsp= ofs;
481                 
482                 while( cp[0] ) {
483                         
484                         switch(cp[1]) {
485                         case IPO_FLOAT:
486                                 
487                                 memcpy(poin, k1, 4*cp[0]);
488                                 poin+= ofsp[0];
489
490                                 break;
491                         case IPO_BPOINT:
492                                 memcpy(poin, k1, 3*4);
493                                 memcpy(poin+16, k1+12, 4);
494                                 
495                                 poin+= ofsp[0];                         
496
497                                 break;
498                         case IPO_BEZTRIPLE:
499                                 memcpy(poin, k1, 4*12);
500                                 poin+= ofsp[0]; 
501
502                                 break;
503                         }
504                         
505                         cp+= 2; ofsp++;
506                 }
507                 
508                 /* are we going to be nasty? */
509                 if(flagflo) {
510                         ktot+= kd;
511                         while(ktot>=1.0) {
512                                 ktot-= 1.0;
513                                 k1+= elemsize;
514                         }
515                 }
516                 else k1+= elemsize;
517                 
518                 if(mode==KEY_BEZTRIPLE) a+=2;
519         }
520 }
521
522 void cp_cu_key(Curve *cu, KeyBlock *kb, int start, int end)
523 {
524         Nurb *nu;
525         int a, step = 0, tot, a1, a2;
526         char *poin;
527
528         tot= count_curveverts(&cu->nurb);
529         nu= cu->nurb.first;
530         a= 0;
531         while(nu) {
532                 if(nu->bp) {
533                         
534                         step= nu->pntsu*nu->pntsv;
535                         
536                         /* exception because keys prefer to work with complete blocks */
537                         poin= (char *)nu->bp->vec;
538                         poin -= a*sizeof(BPoint);
539                         
540                         a1= MAX2(a, start);
541                         a2= MIN2(a+step, end);
542                         
543                         if(a1<a2) cp_key(a1, a2, tot, poin, cu->key, kb, KEY_BPOINT);
544                 }
545                 else if(nu->bezt) {
546                         
547                         step= 3*nu->pntsu;
548                         
549                         poin= (char *)nu->bezt->vec;
550                         poin -= a*sizeof(BezTriple);
551
552                         a1= MAX2(a, start);
553                         a2= MIN2(a+step, end);
554
555                         if(a1<a2) cp_key(a1, a2, tot, poin, cu->key, kb, KEY_BEZTRIPLE);
556                         
557                 }
558                 a+= step;
559                 nu=nu->next;
560         }
561 }
562
563
564 static void rel_flerp(int aantal, float *in, float *ref, float *out, float fac)
565 {
566         int a;
567
568         for(a=0; a<aantal; a++) {
569                 in[a]-= fac*(ref[a]-out[a]);
570         }
571 }
572
573
574
575 static void do_rel_key(int start, int end, int tot, char *basispoin, Key *key, float ctime, int mode)
576 {
577         KeyBlock *kb;
578         IpoCurve *icu;
579         int *ofsp, ofs[3], elemsize, a, b;
580         char *cp, *poin, *reffrom, *from, elemstr[8];
581         
582         if(key->from==0) return;
583         if(key->ipo==0) return;
584         
585         if( GS(key->from->name)==ID_ME ) {
586                 ofs[0]= sizeof(MVert);
587                 ofs[1]= 0;
588         }
589         else if( GS(key->from->name)==ID_LT ) {
590                 ofs[0]= sizeof(BPoint);
591                 ofs[1]= 0;
592         }
593         else if( GS(key->from->name)==ID_CU ) {
594                 if(mode==KEY_BPOINT) ofs[0]= sizeof(BPoint);
595                 else ofs[0]= sizeof(BezTriple);
596                 
597                 ofs[1]= 0;
598         }
599         
600         if(end>tot) end= tot;
601         
602         /* in case of beztriple */
603         elemstr[0]= 1;                          /* nr of ipofloats */
604         elemstr[1]= IPO_BEZTRIPLE;
605         elemstr[2]= 0;
606
607         /* just here, not above! */
608         elemsize= key->elemsize;
609         if(mode==KEY_BEZTRIPLE) elemsize*= 3;
610
611         /* step 1 init */
612         cp_key(start, end, tot, basispoin, key, key->refkey, mode);
613         
614         /* step 2: do it */
615         
616         a= 1;
617         kb= key->block.first;
618         while(kb) {
619                 
620                 if(kb!=key->refkey) {
621                         icu= find_ipocurve(key->ipo, kb->adrcode);
622                         
623                         a++;
624                         if(a==64) break;
625
626                         /* only with ipocurve, and no difference allowed */
627                         if(icu && kb->totelem==tot) {
628                                 
629                                 poin= basispoin;
630                                 reffrom= key->refkey->data;
631                                 from= kb->data;
632                                 
633                                 poin+= start*ofs[0];
634                                 reffrom+= key->elemsize*start;  // key elemsize yes!
635                                 from+= key->elemsize*start;
636                                 
637                                 for(b=start; b<end; b++) {
638                                 
639                                         cp= key->elemstr;       
640                                         if(mode==KEY_BEZTRIPLE) cp= elemstr;
641                                         
642                                         ofsp= ofs;
643                                         
644                                         while( cp[0] ) {        /* cp[0]==amount */
645                                                 
646                                                 switch(cp[1]) {
647                                                 case IPO_FLOAT:
648                                                         rel_flerp(cp[0], (float *)poin, (float *)reffrom, (float *)from, icu->curval);
649                                                         
650                                                         break;
651                                                 case IPO_BPOINT:
652                                                         rel_flerp(3, (float *)poin, (float *)reffrom, (float *)from, icu->curval);
653                                                         rel_flerp(1, (float *)(poin+16), (float *)(reffrom+16), (float *)(from+16), icu->curval);
654                         
655                                                         break;
656                                                 case IPO_BEZTRIPLE:
657                                                         rel_flerp(9, (float *)poin, (float *)reffrom, (float *)from, icu->curval);
658                         
659                                                         break;
660                                                 }
661                                                 
662                                                 poin+= ofsp[0];                         
663                                                 
664                                                 cp+= 2;
665                                                 ofsp++;
666                                         }
667                                         
668                                         reffrom+= elemsize;
669                                         from+= elemsize;
670                                         
671                                         if(mode==KEY_BEZTRIPLE) b+= 2;
672                                 }
673                         }
674                 }
675                 kb= kb->next;
676         }
677 }
678
679
680 static void do_key(int start, int end, int tot, char *poin, Key *key, KeyBlock **k, float *t, int mode)
681 {
682         float k1tot = 0.0, k2tot = 0.0, k3tot = 0.0, k4tot = 0.0;
683         float k1d = 0.0, k2d = 0.0, k3d = 0.0, k4d = 0.0;
684         int a, ofs[32], *ofsp;
685         int flagdo= 15, flagflo=0, elemsize, poinsize=0;
686         char *k1, *k2, *k3, *k4;
687         char *cp, elemstr[8];;
688
689         if(key->from==0) return;
690
691         if( GS(key->from->name)==ID_ME ) {
692                 ofs[0]= sizeof(MVert);
693                 ofs[1]= 0;
694                 poinsize= ofs[0];
695         }
696         else if( GS(key->from->name)==ID_LT ) {
697                 ofs[0]= sizeof(BPoint);
698                 ofs[1]= 0;
699                 poinsize= ofs[0];
700         }
701         else if( GS(key->from->name)==ID_CU ) {
702                 if(mode==KEY_BPOINT) ofs[0]= sizeof(BPoint);
703                 else ofs[0]= sizeof(BezTriple);
704                 
705                 ofs[1]= 0;
706                 poinsize= ofs[0];
707         }
708         
709         if(end>tot) end= tot;
710
711         k1= k[0]->data;
712         k2= k[1]->data;
713         k3= k[2]->data;
714         k4= k[3]->data;
715
716         /*  test for more or less points (per key!) */
717         if(tot != k[0]->totelem) {
718                 k1tot= 0.0;
719                 flagflo |= 1;
720                 if(k[0]->totelem) {
721                         k1d= k[0]->totelem/(float)tot;
722                 }
723                 else flagdo -= 1;
724         }
725         if(tot != k[1]->totelem) {
726                 k2tot= 0.0;
727                 flagflo |= 2;
728                 if(k[0]->totelem) {
729                         k2d= k[1]->totelem/(float)tot;
730                 }
731                 else flagdo -= 2;
732         }
733         if(tot != k[2]->totelem) {
734                 k3tot= 0.0;
735                 flagflo |= 4;
736                 if(k[0]->totelem) {
737                         k3d= k[2]->totelem/(float)tot;
738                 }
739                 else flagdo -= 4;
740         }
741         if(tot != k[3]->totelem) {
742                 k4tot= 0.0;
743                 flagflo |= 8;
744                 if(k[0]->totelem) {
745                         k4d= k[3]->totelem/(float)tot;
746                 }
747                 else flagdo -= 8;
748         }
749
750                 /* this exception needed for slurphing */
751         if(start!=0) {
752
753                 poin+= poinsize*start;
754                 
755                 if(flagdo & 1) {
756                         if(flagflo & 1) {
757                                 k1tot+= start*k1d;
758                                 a= (int)floor(k1tot);
759                                 if(a) {
760                                         k1tot-= a;
761                                         k1+= a*key->elemsize;
762                                 }
763                         }
764                         else k1+= start*key->elemsize;
765                 }
766                 if(flagdo & 2) {
767                         if(flagflo & 2) {
768                                 k2tot+= start*k2d;
769                                 a= (int)floor(k2tot);
770                                 if(a) {
771                                         k2tot-= a;
772                                         k2+= a*key->elemsize;
773                                 }
774                         }
775                         else k2+= start*key->elemsize;
776                 }
777                 if(flagdo & 4) {
778                         if(flagflo & 4) {
779                                 k3tot+= start*k3d;
780                                 a= (int)floor(k3tot);
781                                 if(a) {
782                                         k3tot-= a;
783                                         k3+= a*key->elemsize;
784                                 }
785                         }
786                         else k3+= start*key->elemsize;
787                 }
788                 if(flagdo & 8) {
789                         if(flagflo & 8) {
790                                 k4tot+= start*k4d;
791                                 a= (int)floor(k4tot);
792                                 if(a) {
793                                         k4tot-= a;
794                                         k4+= a*key->elemsize;
795                                 }
796                         }
797                         else k4+= start*key->elemsize;
798                 }
799
800         }
801
802         /* in case of beztriple */
803         elemstr[0]= 1;                          /* nr of ipofloats */
804         elemstr[1]= IPO_BEZTRIPLE;
805         elemstr[2]= 0;
806
807         /* only here, not above! */
808         elemsize= key->elemsize;
809         if(mode==KEY_BEZTRIPLE) elemsize*= 3;
810
811         for(a=start; a<end; a++) {
812         
813                 cp= key->elemstr;       
814                 if(mode==KEY_BEZTRIPLE) cp= elemstr;
815                 
816                 ofsp= ofs;
817                 
818                 while( cp[0] ) {        /* cp[0]==amount */
819                         
820                         switch(cp[1]) {
821                         case IPO_FLOAT:
822                                 flerp(cp[0], (float *)poin, (float *)k1, (float *)k2, (float *)k3, (float *)k4, t);
823                                 poin+= ofsp[0];                         
824
825                                 break;
826                         case IPO_BPOINT:
827                                 flerp(3, (float *)poin, (float *)k1, (float *)k2, (float *)k3, (float *)k4, t);
828                                 flerp(1, (float *)(poin+16), (float *)(k1+12), (float *)(k2+12), (float *)(k3+12), (float *)(k4+12), t);
829                                 
830                                 poin+= ofsp[0];                         
831
832                                 break;
833                         case IPO_BEZTRIPLE:
834                                 flerp(9, (void *)poin, (void *)k1, (void *)k2, (void *)k3, (void *)k4, t);
835                                 flerp(1, (float *)(poin+36), (float *)(k1+36), (float *)(k2+36), (float *)(k3+36), (float *)(k4+36), t);
836                                 poin+= ofsp[0];                         
837
838                                 break;
839                         }
840                         
841
842                         cp+= 2;
843                         ofsp++;
844                 }
845                 /* lets do it the difficult way: when keys have a different size */
846                 if(flagdo & 1) {
847                         if(flagflo & 1) {
848                                 k1tot+= k1d;
849                                 while(k1tot>=1.0) {
850                                         k1tot-= 1.0;
851                                         k1+= elemsize;
852                                 }
853                         }
854                         else k1+= elemsize;
855                 }
856                 if(flagdo & 2) {
857                         if(flagflo & 2) {
858                                 k2tot+= k2d;
859                                 while(k2tot>=1.0) {
860                                         k2tot-= 1.0;
861                                         k2+= elemsize;
862                                 }
863                         }
864                         else k2+= elemsize;
865                 }
866                 if(flagdo & 4) {
867                         if(flagflo & 4) {
868                                 k3tot+= k3d;
869                                 while(k3tot>=1.0) {
870                                         k3tot-= 1.0;
871                                         k3+= elemsize;
872                                 }
873                         }
874                         else k3+= elemsize;
875                 }
876                 if(flagdo & 8) {
877                         if(flagflo & 8) {
878                                 k4tot+= k4d;
879                                 while(k4tot>=1.0) {
880                                         k4tot-= 1.0;
881                                         k4+= elemsize;
882                                 }
883                         }
884                         else k4+= elemsize;
885                 }
886                 
887                 if(mode==KEY_BEZTRIPLE) a+= 2;
888         }
889 }
890
891 static int do_mesh_key(Mesh *me)
892 {
893         KeyBlock *k[4];
894         float cfra, ctime, t[4], delta, loc[3], size[3];
895         int a, flag = 0, step;
896         
897         if(me->totvert==0) return 0;
898         if(me->key==NULL) return 0;
899         if(me->key->block.first==NULL) return 0;
900         
901         if(me->key->slurph && me->key->type!=KEY_RELATIVE ) {
902                 delta= me->key->slurph;
903                 delta/= me->totvert;
904                 
905                 step= 1;
906                 if(me->totvert>100 && slurph_opt) {
907                         step= me->totvert/50;
908                         delta*= step;
909                         /* in do_key and cp_key the case a>tot is handled */
910                 }
911                 
912                 cfra= G.scene->r.cfra;
913                 
914                 for(a=0; a<me->totvert; a+=step, cfra+= delta) {
915                         
916                         ctime= bsystem_time(0, 0, cfra, 0.0);
917                         if(calc_ipo_spec(me->key->ipo, KEY_SPEED, &ctime)==0) {
918                                 ctime /= 100.0;
919                                 CLAMP(ctime, 0.0, 1.0);
920                         }
921                 
922                         flag= setkeys(ctime, &me->key->block, k, t, 0);
923                         if(flag==0) {
924                                 
925                                 do_key(a, a+step, me->totvert, (char *)me->mvert->co, me->key, k, t, 0);
926                         }
927                         else {
928                                 cp_key(a, a+step, me->totvert, (char *)me->mvert->co, me->key, k[2], 0);
929                         }
930                 }
931                 
932                 if(flag && k[2]==me->key->refkey) tex_space_mesh(me);
933                 else boundbox_mesh(me, loc, size);
934         }
935         else {
936                 
937                 ctime= bsystem_time(0, 0, (float)G.scene->r.cfra, 0.0);
938                 calc_ipo(me->key->ipo, ctime);  /* also all relative key positions */
939                 
940                 if(calc_ipo_spec(me->key->ipo, KEY_SPEED, &ctime)==0) {
941                         ctime /= 100.0;
942                         CLAMP(ctime, 0.0, 1.0);
943                 }
944                 
945                 if(me->key->type==KEY_RELATIVE) {
946                         do_rel_key(0, me->totvert, me->totvert, (char *)me->mvert->co, me->key, ctime, 0);
947                 }
948                 else {
949                         flag= setkeys(ctime, &me->key->block, k, t, 0);
950                         if(flag==0) {
951                                 
952                                 do_key(0, me->totvert, me->totvert, (char *)me->mvert->co, me->key, k, t, 0);
953                         }
954                         else {
955                                 cp_key(0, me->totvert, me->totvert, (char *)me->mvert->co, me->key, k[2], 0);
956         
957                         }
958                         
959                         if(flag && k[2]==me->key->refkey) tex_space_mesh(me);
960                         else boundbox_mesh(me, loc, size);
961                 }
962         }
963         return 1;
964 }
965
966 static void do_cu_key(Curve *cu, KeyBlock **k, float *t)
967 {
968         Nurb *nu;
969         int a, step = 0, tot;
970         char *poin;
971         
972         tot= count_curveverts(&cu->nurb);
973         nu= cu->nurb.first;
974         a= 0;
975         
976         while(nu) {
977                 if(nu->bp) {
978                         
979                         step= nu->pntsu*nu->pntsv;
980                         
981                         /* exception because keys prefer to work with complete blocks */
982                         poin= (char *)nu->bp->vec;
983                         poin -= a*sizeof(BPoint);
984                         
985                         do_key(a, a+step, tot, poin, cu->key, k, t, KEY_BPOINT);
986                 }
987                 else if(nu->bezt) {
988                         
989                         step= 3*nu->pntsu;
990                         
991                         poin= (char *)nu->bezt->vec;
992                         poin -= a*sizeof(BezTriple);
993
994                         do_key(a, a+step, tot, poin, cu->key, k, t, KEY_BEZTRIPLE);
995                         
996                 }
997                 a+= step;
998                 nu=nu->next;
999         }
1000 }
1001
1002 static void do_rel_cu_key(Curve *cu, float ctime)
1003 {
1004         Nurb *nu;
1005         int a, step = 0, tot;
1006         char *poin;
1007         
1008         tot= count_curveverts(&cu->nurb);
1009         nu= cu->nurb.first;
1010         a= 0;
1011         while(nu) {
1012                 if(nu->bp) {
1013                         
1014                         step= nu->pntsu*nu->pntsv;
1015                         
1016                         /* exception because keys prefer to work with complete blocks */
1017                         poin= (char *)nu->bp->vec;
1018                         poin -= a*sizeof(BPoint);
1019                         
1020                         do_rel_key(a, a+step, tot, poin, cu->key, ctime, KEY_BPOINT);
1021                 }
1022                 else if(nu->bezt) {
1023                         
1024                         step= 3*nu->pntsu;
1025                         
1026                         poin= (char *)nu->bezt->vec;
1027                         poin -= a*sizeof(BezTriple);
1028
1029                         do_rel_key(a, a+step, tot, poin, cu->key, ctime, KEY_BEZTRIPLE);
1030                 }
1031                 a+= step;
1032                 
1033                 nu=nu->next;
1034         }
1035 }
1036
1037 static int do_curve_key(Curve *cu)
1038 {
1039         KeyBlock *k[4];
1040         float cfra, ctime, t[4], delta;
1041         int a, flag = 0, step = 0, tot;
1042         
1043         tot= count_curveverts(&cu->nurb);
1044         
1045         if(tot==0) return 0;
1046         if(cu->key==NULL) return 0;
1047         if(cu->key->block.first==NULL) return 0;
1048         
1049         if(cu->key->slurph) {
1050                 delta= cu->key->slurph;
1051                 delta/= tot;
1052                 
1053                 step= 1;
1054                 if(tot>100 && slurph_opt) {
1055                         step= tot/50;
1056                         delta*= step;
1057                         /* in do_key and cp_key the case a>tot has been handled */
1058                 }
1059                 
1060                 cfra= G.scene->r.cfra;
1061                 
1062                 for(a=0; a<tot; a+=step, cfra+= delta) {
1063                         
1064                         ctime= bsystem_time(0, 0, cfra, 0.0);
1065                         if(calc_ipo_spec(cu->key->ipo, KEY_SPEED, &ctime)==0) {
1066                                 ctime /= 100.0;
1067                                 CLAMP(ctime, 0.0, 1.0);
1068                         }
1069                 
1070                         flag= setkeys(ctime, &cu->key->block, k, t, 0);
1071                         if(flag==0) {
1072                                 
1073                                 /* do_key(a, a+step, tot, (char *)cu->mvert->co, cu->key, k, t, 0); */
1074                         }
1075                         else {
1076                                 /* cp_key(a, a+step, tot, (char *)cu->mvert->co, cu->key, k[2],0); */
1077                         }
1078                 }
1079
1080                 if(flag && k[2]==cu->key->refkey) tex_space_curve(cu);
1081                 
1082                 
1083         }
1084         else {
1085                 
1086                 ctime= bsystem_time(0, 0, (float)G.scene->r.cfra, 0.0);
1087                 if(calc_ipo_spec(cu->key->ipo, KEY_SPEED, &ctime)==0) {
1088                         ctime /= 100.0;
1089                         CLAMP(ctime, 0.0, 1.0);
1090                 }
1091                 
1092                 if(cu->key->type==KEY_RELATIVE) {
1093                         do_rel_cu_key(cu, ctime);
1094                 }
1095                 else {
1096                         flag= setkeys(ctime, &cu->key->block, k, t, 0);
1097                         
1098                         if(flag==0) do_cu_key(cu, k, t);
1099                         else cp_cu_key(cu, k[2], 0, tot);
1100                                         
1101                         if(flag && k[2]==cu->key->refkey) tex_space_curve(cu);
1102                 }
1103         }
1104         
1105         return 1;
1106 }
1107
1108 static int do_latt_key(Lattice *lt)
1109 {
1110         KeyBlock *k[4];
1111         float delta, cfra, ctime, t[4];
1112         int a, tot, flag;
1113         
1114         if(lt->key==NULL) return 0;
1115         if(lt->key->block.first==NULL) return 0;
1116
1117         tot= lt->pntsu*lt->pntsv*lt->pntsw;
1118
1119         if(lt->key->slurph) {
1120                 delta= lt->key->slurph;
1121                 delta/= (float)tot;
1122                 
1123                 cfra= G.scene->r.cfra;
1124                 
1125                 for(a=0; a<tot; a++, cfra+= delta) {
1126                         
1127                         ctime= bsystem_time(0, 0, cfra, 0.0);
1128                         if(calc_ipo_spec(lt->key->ipo, KEY_SPEED, &ctime)==0) {
1129                                 ctime /= 100.0;
1130                                 CLAMP(ctime, 0.0, 1.0);
1131                         }
1132                 
1133                         flag= setkeys(ctime, &lt->key->block, k, t, 0);
1134                         if(flag==0) {
1135                                 
1136                                 do_key(a, a+1, tot, (char *)lt->def->vec, lt->key, k, t, 0);
1137                         }
1138                         else {
1139                                 cp_key(a, a+1, tot, (char *)lt->def->vec, lt->key, k[2], 0);
1140                         }
1141                 }               
1142         }
1143         else {
1144                 ctime= bsystem_time(0, 0, (float)G.scene->r.cfra, 0.0);
1145                 if(calc_ipo_spec(lt->key->ipo, KEY_SPEED, &ctime)==0) {
1146                         ctime /= 100.0;
1147                         CLAMP(ctime, 0.0, 1.0);
1148                 }
1149         
1150                 if(lt->key->type==KEY_RELATIVE) {
1151                         do_rel_key(0, tot, tot, (char *)lt->def->vec, lt->key, ctime, 0);
1152                 }
1153                 else {
1154
1155                         flag= setkeys(ctime, &lt->key->block, k, t, 0);
1156                         if(flag==0) {
1157                                 do_key(0, tot, tot, (char *)lt->def->vec, lt->key, k, t, 0);
1158                         }
1159                         else {
1160                                 cp_key(0, tot, tot, (char *)lt->def->vec, lt->key, k[2], 0);
1161                         }
1162                 }
1163         }
1164         
1165         if(lt->flag & LT_OUTSIDE) outside_lattice(lt);
1166         
1167         return 1;
1168 }
1169
1170 /* returns 1 when key applied */
1171 int do_ob_key(Object *ob)
1172 {
1173         if(ob->shapeflag & (OB_SHAPE_LOCK|OB_SHAPE_TEMPLOCK)) {
1174                 Key *key= ob_get_key(ob);
1175                 if(key) {
1176                         KeyBlock *kb= BLI_findlink(&key->block, ob->shapenr-1);
1177
1178                         if(kb==NULL) {
1179                                 kb= key->block.first;
1180                                 ob->shapenr= 1;
1181                         }
1182                         
1183                         if(ob->type==OB_MESH) {
1184                                 Mesh *me= ob->data;
1185                                 
1186                                 cp_key(0, me->totvert, me->totvert, (char *)me->mvert->co, key, kb, 0);
1187                         }
1188                         else if(ob->type==OB_LATTICE) {
1189                                 Lattice *lt= ob->data;
1190                                 int tot= lt->pntsu*lt->pntsv*lt->pntsw;
1191                                 
1192                                 cp_key(0, tot, tot, (char *)lt->def->vec, key, kb, 0);
1193                         }
1194                         else if ELEM(ob->type, OB_CURVE, OB_SURF) {
1195                                 Curve *cu= ob->data;
1196                                 int tot= count_curveverts(&cu->nurb);
1197                                 
1198                                 cp_cu_key(cu, kb, 0, tot);
1199                         }
1200                         return 1;
1201                 }
1202         }
1203         else {
1204                 if(ob->type==OB_MESH) return do_mesh_key( ob->data);
1205                 else if(ob->type==OB_CURVE) return do_curve_key( ob->data);
1206                 else if(ob->type==OB_SURF) return do_curve_key( ob->data);
1207                 else if(ob->type==OB_LATTICE) return do_latt_key( ob->data);
1208         }
1209         
1210         return 0;
1211 }
1212
1213 Key *ob_get_key(Object *ob)
1214 {
1215         
1216         if(ob->type==OB_MESH) {
1217                 Mesh *me= ob->data;
1218                 return me->key;
1219         }
1220         else if ELEM(ob->type, OB_CURVE, OB_SURF) {
1221                 Curve *cu= ob->data;
1222                 return cu->key;
1223         }
1224         else if(ob->type==OB_LATTICE) {
1225                 Lattice *lt= ob->data;
1226                 return lt->key;
1227         }
1228         return NULL;
1229 }
1230
1231 /* only the active keyblock */
1232 KeyBlock *ob_get_keyblock(Object *ob) 
1233 {
1234         Key *key= ob_get_key(ob);
1235         
1236         if (key) {
1237                 KeyBlock *kb= BLI_findlink(&key->block, ob->shapenr-1);
1238                 return kb;
1239         }
1240
1241         return NULL;
1242 }