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