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