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