91a8b7047c45ae72acd93741e3026f7b4e74a1dc
[blender.git] / source / blender / editors / animation / keyframes_general.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2008 Blender Foundation
21  * All rights reserved.
22  *
23  * Contributor(s): Joshua Leung
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 #include <stdlib.h>
29 #include <string.h>
30 #include <math.h>
31 #include <float.h>
32
33 #include "MEM_guardedalloc.h"
34
35 #include "BLI_blenlib.h"
36 #include "BLI_math.h"
37
38 #include "DNA_anim_types.h"
39 #include "DNA_object_types.h"
40 #include "DNA_scene_types.h"
41
42
43 #include "BKE_action.h"
44 #include "BKE_fcurve.h"
45 #include "BKE_key.h"
46 #include "BKE_utildefines.h"
47
48 #include "ED_anim_api.h"
49 #include "ED_keyframing.h"
50 #include "ED_keyframes_edit.h"
51
52 /* This file contains code for various keyframe-editing tools which are 'destructive'
53  * (i.e. they will modify the order of the keyframes, and change the size of the array).
54  * While some of these tools may eventually be moved out into blenkernel, for now, it is
55  * fine to have these calls here.
56  * 
57  * There are also a few tools here which cannot be easily coded for in the other system (yet).
58  * These may also be moved around at some point, but for now, they are best added here.
59  *
60  * - Joshua Leung, Dec 2008
61  */
62  
63 /* **************************************************** */
64
65 /* Only delete the nominated keyframe from provided F-Curve. 
66  * Not recommended to be used many times successively. For that
67  * there is delete_fcurve_keys(). 
68  */
69 void delete_fcurve_key(FCurve *fcu, int index, short do_recalc)
70 {
71         /* sanity check */
72         if (fcu == NULL) 
73                 return;
74                 
75         /* verify the index:
76          *      1) cannot be greater than the number of available keyframes
77          *      2) negative indices are for specifying a value from the end of the array
78          */
79         if (abs(index) >= fcu->totvert)
80                 return;
81         else if (index < 0)
82                 index += fcu->totvert;
83         
84         /* Delete this keyframe */
85         memmove(&fcu->bezt[index], &fcu->bezt[index+1], sizeof(BezTriple)*(fcu->totvert-index-1));
86         fcu->totvert--;
87         
88         /* recalc handles - only if it won't cause problems */
89         if (do_recalc)
90                 calchandles_fcurve(fcu);
91 }
92
93 /* Delete selected keyframes in given F-Curve */
94 void delete_fcurve_keys(FCurve *fcu)
95 {
96         int i;
97         
98         if(fcu->bezt==NULL) /* ignore baked curves */
99                 return;
100     
101         /* Delete selected BezTriples */
102         for (i=0; i < fcu->totvert; i++) {
103                 if (fcu->bezt[i].f2 & SELECT) {
104                         memmove(&fcu->bezt[i], &fcu->bezt[i+1], sizeof(BezTriple)*(fcu->totvert-i-1));
105                         fcu->totvert--;
106                         i--;
107                 }
108         }
109         
110         /* Free the array of BezTriples if there are not keyframes */
111         if (fcu->totvert == 0) {
112                 if (fcu->bezt) 
113                         MEM_freeN(fcu->bezt);
114                 fcu->bezt= NULL;
115         }
116 }
117
118 /* ---------------- */
119
120 /* duplicate selected keyframes for the given F-Curve */
121 void duplicate_fcurve_keys(FCurve *fcu)
122 {
123         BezTriple *newbezt;
124         int i;
125         
126         /* this can only work when there is an F-Curve, and also when there are some BezTriples */
127         if ELEM(NULL, fcu, fcu->bezt)
128                 return;
129         
130         for (i=0; i < fcu->totvert; i++) {
131                 /* If a key is selected */
132                 if (fcu->bezt[i].f2 & SELECT) {
133                         /* Expand the list */
134                         newbezt = MEM_callocN(sizeof(BezTriple) * (fcu->totvert+1), "beztriple");
135                         
136                         memcpy(newbezt, fcu->bezt, sizeof(BezTriple) * (i+1));
137                         memcpy(newbezt+i+1, fcu->bezt+i, sizeof(BezTriple));
138                         memcpy(newbezt+i+2, fcu->bezt+i+1, sizeof (BezTriple) *(fcu->totvert-(i+1)));
139                         fcu->totvert++;
140                         
141                         /* reassign pointers... (free old, and add new) */
142                         MEM_freeN(fcu->bezt);
143                         fcu->bezt=newbezt;
144                         
145                         /* Unselect the current key */
146                         BEZ_DESEL(&fcu->bezt[i]);
147                         i++;
148                         
149                         /* Select the copied key */
150                         BEZ_SEL(&fcu->bezt[i]);
151                 }
152         }
153 }
154
155 /* **************************************************** */
156 /* Various Tools */
157
158 /* Basic F-Curve 'cleanup' function that removes 'double points' and unnecessary keyframes on linear-segments only */
159 void clean_fcurve(FCurve *fcu, float thresh)
160 {
161         BezTriple *old_bezts, *bezt, *beztn;
162         BezTriple *lastb;
163         int totCount, i;
164         
165         /* check if any points  */
166         if ((fcu == NULL) || (fcu->totvert <= 1)) 
167                 return;
168         
169         /* make a copy of the old BezTriples, and clear IPO curve */
170         old_bezts = fcu->bezt;
171         totCount = fcu->totvert;        
172         fcu->bezt = NULL;
173         fcu->totvert = 0;
174         
175         /* now insert first keyframe, as it should be ok */
176         bezt = old_bezts;
177         insert_vert_fcurve(fcu, bezt->vec[1][0], bezt->vec[1][1], 0);
178         
179         /* Loop through BezTriples, comparing them. Skip any that do 
180          * not fit the criteria for "ok" points.
181          */
182         for (i=1; i<totCount; i++) {    
183                 float prev[2], cur[2], next[2];
184                 
185                 /* get BezTriples and their values */
186                 if (i < (totCount - 1)) {
187                         beztn = (old_bezts + (i+1));
188                         next[0]= beztn->vec[1][0]; next[1]= beztn->vec[1][1];
189                 }
190                 else {
191                         beztn = NULL;
192                         next[0] = next[1] = 0.0f;
193                 }
194                 lastb= (fcu->bezt + (fcu->totvert - 1));
195                 bezt= (old_bezts + i);
196                 
197                 /* get references for quicker access */
198                 prev[0] = lastb->vec[1][0]; prev[1] = lastb->vec[1][1];
199                 cur[0] = bezt->vec[1][0]; cur[1] = bezt->vec[1][1];
200                 
201                 /* check if current bezt occurs at same time as last ok */
202                 if (IS_EQT(cur[0], prev[0], thresh)) {
203                         /* If there is a next beztriple, and if occurs at the same time, only insert 
204                          * if there is a considerable distance between the points, and also if the 
205                          * current is further away than the next one is to the previous.
206                          */
207                         if (beztn && (IS_EQT(cur[0], next[0], thresh)) && 
208                                 (IS_EQT(next[1], prev[1], thresh)==0)) 
209                         {
210                                 /* only add if current is further away from previous */
211                                 if (cur[1] > next[1]) {
212                                         if (IS_EQT(cur[1], prev[1], thresh) == 0) {
213                                                 /* add new keyframe */
214                                                 insert_vert_fcurve(fcu, cur[0], cur[1], 0);
215                                         }
216                                 }
217                         }
218                         else {
219                                 /* only add if values are a considerable distance apart */
220                                 if (IS_EQT(cur[1], prev[1], thresh) == 0) {
221                                         /* add new keyframe */
222                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
223                                 }
224                         }
225                 }
226                 else {
227                         /* checks required are dependent on whether this is last keyframe or not */
228                         if (beztn) {
229                                 /* does current have same value as previous and next? */
230                                 if (IS_EQT(cur[1], prev[1], thresh) == 0) {
231                                         /* add new keyframe*/
232                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
233                                 }
234                                 else if (IS_EQT(cur[1], next[1], thresh) == 0) {
235                                         /* add new keyframe */
236                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
237                                 }
238                         }
239                         else {  
240                                 /* add if value doesn't equal that of previous */
241                                 if (IS_EQT(cur[1], prev[1], thresh) == 0) {
242                                         /* add new keyframe */
243                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
244                                 }
245                         }
246                 }
247         }
248         
249         /* now free the memory used by the old BezTriples */
250         if (old_bezts)
251                 MEM_freeN(old_bezts);
252 }
253
254 /* ---------------- */
255
256 /* temp struct used for smooth_fcurve */
257 typedef struct tSmooth_Bezt {
258         float *h1, *h2, *h3;    /* bezt->vec[0,1,2][1] */
259 } tSmooth_Bezt;
260
261 /* Use a weighted moving-means method to reduce intensity of fluctuations */
262 void smooth_fcurve (FCurve *fcu)
263 {
264         BezTriple *bezt;
265         int i, x, totSel = 0;
266         
267         /* first loop through - count how many verts are selected, and fix up handles 
268          *      this is done for both modes
269          */
270         bezt= fcu->bezt;
271         for (i=0; i < fcu->totvert; i++, bezt++) {                                              
272                 if (BEZSELECTED(bezt)) {                                                        
273                         /* line point's handles up with point's vertical position */
274                         bezt->vec[0][1]= bezt->vec[2][1]= bezt->vec[1][1];
275                         if ((bezt->h1==HD_AUTO) || (bezt->h1==HD_VECT)) bezt->h1= HD_ALIGN;
276                         if ((bezt->h2==HD_AUTO) || (bezt->h2==HD_VECT)) bezt->h2= HD_ALIGN;
277                         
278                         /* add value to total */
279                         totSel++;
280                 }
281         }
282         
283         /* if any points were selected, allocate tSmooth_Bezt points to work on */
284         if (totSel >= 3) {
285                 tSmooth_Bezt *tarray, *tsb;
286                 
287                 /* allocate memory in one go */
288                 tsb= tarray= MEM_callocN(totSel*sizeof(tSmooth_Bezt), "tSmooth_Bezt Array");
289                 
290                 /* populate tarray with data of selected points */
291                 bezt= fcu->bezt;
292                 for (i=0, x=0; (i < fcu->totvert) && (x < totSel); i++, bezt++) {
293                         if (BEZSELECTED(bezt)) {
294                                 /* tsb simply needs pointer to vec, and index */
295                                 tsb->h1 = &bezt->vec[0][1];
296                                 tsb->h2 = &bezt->vec[1][1];
297                                 tsb->h3 = &bezt->vec[2][1];
298                                 
299                                 /* advance to the next tsb to populate */
300                                 if (x < totSel- 1) 
301                                         tsb++;
302                                 else
303                                         break;
304                         }
305                 }
306                         
307                 /* calculate the new smoothed F-Curve's with weighted averages:
308                  *      - this is done with two passes
309                  *      - uses 5 points for each operation (which stores in the relevant handles)
310                  *      -       previous: w/a ratio = 3:5:2:1:1
311                  *      -       next: w/a ratio = 1:1:2:5:3
312                  */
313                 
314                 /* round 1: calculate previous and next */ 
315                 tsb= tarray;
316                 for (i=0; i < totSel; i++, tsb++) {
317                         /* don't touch end points (otherwise, curves slowly explode) */
318                         if (ELEM(i, 0, (totSel-1)) == 0) {
319                                 const tSmooth_Bezt *tP1 = tsb - 1;
320                                 const tSmooth_Bezt *tP2 = (i-2 > 0) ? (tsb - 2) : (NULL);
321                                 const tSmooth_Bezt *tN1 = tsb + 1;
322                                 const tSmooth_Bezt *tN2 = (i+2 < totSel) ? (tsb + 2) : (NULL);
323                                 
324                                 const float p1 = *tP1->h2;
325                                 const float p2 = (tP2) ? (*tP2->h2) : (*tP1->h2);
326                                 const float c1 = *tsb->h2;
327                                 const float n1 = *tN1->h2;
328                                 const float n2 = (tN2) ? (*tN2->h2) : (*tN1->h2);
329                                 
330                                 /* calculate previous and next */
331                                 *tsb->h1= (3*p2 + 5*p1 + 2*c1 + n1 + n2) / 12;
332                                 *tsb->h3= (p2 + p1 + 2*c1 + 5*n1 + 3*n2) / 12;
333                         }
334                 }
335                 
336                 /* round 2: calculate new values and reset handles */
337                 tsb= tarray;
338                 for (i=0; i < totSel; i++, tsb++) {
339                         /* calculate new position by averaging handles */
340                         *tsb->h2 = (*tsb->h1 + *tsb->h3) / 2;
341                         
342                         /* reset handles now */
343                         *tsb->h1 = *tsb->h2;
344                         *tsb->h3 = *tsb->h2;
345                 }
346                 
347                 /* free memory required for tarray */
348                 MEM_freeN(tarray);
349         }
350         
351         /* recalculate handles */
352         calchandles_fcurve(fcu);
353 }
354
355 /* ---------------- */
356
357 /* little cache for values... */
358 typedef struct tempFrameValCache {
359         float frame, val;
360 } tempFrameValCache;
361
362
363 /* Evaluates the curves between each selected keyframe on each frame, and keys the value  */
364 void sample_fcurve (FCurve *fcu)
365 {
366         BezTriple *bezt, *start=NULL, *end=NULL;
367         tempFrameValCache *value_cache, *fp;
368         int sfra, range;
369         int i, n, nIndex;
370
371         if(fcu->bezt==NULL) /* ignore baked */
372                 return;
373         
374         /* find selected keyframes... once pair has been found, add keyframes  */
375         for (i=0, bezt=fcu->bezt; i < fcu->totvert; i++, bezt++) {
376                 /* check if selected, and which end this is */
377                 if (BEZSELECTED(bezt)) {
378                         if (start) {
379                                 /* set end */
380                                 end= bezt;
381                                 
382                                 /* cache values then add keyframes using these values, as adding
383                                  * keyframes while sampling will affect the outcome...
384                                  *      - only start sampling+adding from index=1, so that we don't overwrite original keyframe
385                                  */
386                                 range= (int)( ceil(end->vec[1][0] - start->vec[1][0]) );
387                                 sfra= (int)( floor(start->vec[1][0]) );
388                                 
389                                 if (range) {
390                                         value_cache= MEM_callocN(sizeof(tempFrameValCache)*range, "IcuFrameValCache");
391                                         
392                                         /*      sample values   */
393                                         for (n=1, fp=value_cache; n<range && fp; n++, fp++) {
394                                                 fp->frame= (float)(sfra + n);
395                                                 fp->val= evaluate_fcurve(fcu, fp->frame);
396                                         }
397                                         
398                                         /*      add keyframes with these, tagging as 'breakdowns'       */
399                                         for (n=1, fp=value_cache; n<range && fp; n++, fp++) {
400                                                 nIndex= insert_vert_fcurve(fcu, fp->frame, fp->val, 1);
401                                                 BEZKEYTYPE(fcu->bezt + nIndex)= BEZT_KEYTYPE_BREAKDOWN;
402                                         }
403                                         
404                                         /* free temp cache */
405                                         MEM_freeN(value_cache);
406                                         
407                                         /* as we added keyframes, we need to compensate so that bezt is at the right place */
408                                         bezt = fcu->bezt + i + range - 1;
409                                         i += (range - 1);
410                                 }
411                                 
412                                 /* bezt was selected, so it now marks the start of a whole new chain to search */
413                                 start= bezt;
414                                 end= NULL;
415                         }
416                         else {
417                                 /* just set start keyframe */
418                                 start= bezt;
419                                 end= NULL;
420                         }
421                 }
422         }
423         
424         /* recalculate channel's handles? */
425         calchandles_fcurve(fcu);
426 }
427
428 /* **************************************************** */
429 /* Copy/Paste Tools */
430 /* - The copy/paste buffer currently stores a set of temporary F-Curves containing only the keyframes 
431  *   that were selected in each of the original F-Curves
432  * - All pasted frames are offset by the same amount. This is calculated as the difference in the times of
433  *      the current frame and the 'first keyframe' (i.e. the earliest one in all channels).
434  * - The earliest frame is calculated per copy operation.
435  */
436
437 /* globals for copy/paste data (like for other copy/paste buffers) */
438 ListBase animcopybuf = {NULL, NULL};
439 static float animcopy_firstframe= 999999999.0f;
440
441 /* datatype for use in copy/paste buffer */
442 typedef struct tAnimCopybufItem {
443         struct tAnimCopybufItem *next, *prev;
444         
445         ID *id;                         /* ID which owns the curve */
446         bActionGroup *grp;      /* Action Group */
447         char *rna_path;         /* RNA-Path */
448         int array_index;        /* array index */
449         
450         int totvert;            /* number of keyframes stored for this channel */
451         BezTriple *bezt;        /* keyframes in buffer */
452 } tAnimCopybufItem;
453
454
455 /* This function frees any MEM_calloc'ed copy/paste buffer data */
456 // XXX find some header to put this in!
457 void free_anim_copybuf (void)
458 {
459         tAnimCopybufItem *aci, *acn;
460         
461         /* free each buffer element */
462         for (aci= animcopybuf.first; aci; aci= acn) {
463                 acn= aci->next;
464                 
465                 /* free keyframes */
466                 if (aci->bezt) 
467                         MEM_freeN(aci->bezt);
468                         
469                 /* free RNA-path */
470                 if (aci->rna_path)
471                         MEM_freeN(aci->rna_path);
472                         
473                 /* free ourself */
474                 BLI_freelinkN(&animcopybuf, aci);
475         }
476         
477         /* restore initial state */
478         animcopybuf.first= animcopybuf.last= NULL;
479         animcopy_firstframe= 999999999.0f;
480 }
481
482 /* ------------------- */
483
484 /* This function adds data to the keyframes copy/paste buffer, freeing existing data first */
485 short copy_animedit_keys (bAnimContext *ac, ListBase *anim_data)
486 {       
487         bAnimListElem *ale;
488         
489         /* clear buffer first */
490         free_anim_copybuf();
491         
492         /* assume that each of these is an F-Curve */
493         for (ale= anim_data->first; ale; ale= ale->next) {
494                 FCurve *fcu= (FCurve *)ale->key_data;
495                 tAnimCopybufItem *aci;
496                 BezTriple *bezt, *newbuf;
497                 int i;
498                 
499                 /* firstly, check if F-Curve has any selected keyframes
500                  *      - skip if no selected keyframes found (so no need to create unnecessary copy-buffer data)
501                  *      - this check should also eliminate any problems associated with using sample-data
502                  */
503                 if (ANIM_fcurve_keys_bezier_loop(NULL, fcu, NULL, ANIM_editkeyframes_ok(BEZT_OK_SELECTED), NULL) == 0)
504                         continue;
505                 
506                 /* init copybuf item info */
507                 aci= MEM_callocN(sizeof(tAnimCopybufItem), "AnimCopybufItem");
508                 aci->id= ale->id;
509                 aci->grp= fcu->grp;
510                 aci->rna_path= MEM_dupallocN(fcu->rna_path);
511                 aci->array_index= fcu->array_index;
512                 BLI_addtail(&animcopybuf, aci);
513                 
514                 /* add selected keyframes to buffer */
515                 // TODO: currently, we resize array everytime we add a new vert - this works ok as long as it is assumed only a few keys are copied
516                 for (i=0, bezt=fcu->bezt; i < fcu->totvert; i++, bezt++) {
517                         if (BEZSELECTED(bezt)) {
518                                 /* add to buffer */
519                                 newbuf= MEM_callocN(sizeof(BezTriple)*(aci->totvert+1), "copybuf beztriple");
520                                 
521                                 /* assume that since we are just resizing the array, just copy all existing data across */
522                                 if (aci->bezt)
523                                         memcpy(newbuf, aci->bezt, sizeof(BezTriple)*(aci->totvert));
524                                 
525                                 /* copy current beztriple across too */
526                                 *(newbuf + aci->totvert)= *bezt; 
527                                 
528                                 /* free old array and set the new */
529                                 if (aci->bezt) MEM_freeN(aci->bezt);
530                                 aci->bezt= newbuf;
531                                 aci->totvert++;
532                                 
533                                 /* check if this is the earliest frame encountered so far */
534                                 if (bezt->vec[1][0] < animcopy_firstframe)
535                                         animcopy_firstframe= bezt->vec[1][0];
536                         }
537                 }
538                 
539         }
540         
541         /* check if anything ended up in the buffer */
542         if (ELEM(NULL, animcopybuf.first, animcopybuf.last))
543                 return -1;
544         
545         /* everything went fine */
546         return 0;
547 }
548
549 /* This function pastes data from the keyframes copy/paste buffer */
550 short paste_animedit_keys (bAnimContext *ac, ListBase *anim_data)
551 {
552         bAnimListElem *ale;
553         const Scene *scene= (ac->scene);
554         const float offset = (float)(CFRA - animcopy_firstframe);
555         short no_name= 0;
556         
557         /* check if buffer is empty */
558         if (ELEM(NULL, animcopybuf.first, animcopybuf.last)) {
559                 //error("No data in buffer to paste");
560                 return -1;
561         }
562         /* check if single channel in buffer (disregard names if so)  */
563         if (animcopybuf.first == animcopybuf.last)
564                 no_name= 1;
565         
566         /* from selected channels */
567         for (ale= anim_data->first; ale; ale= ale->next) {
568                 FCurve *fcu = (FCurve *)ale->data;              /* destination F-Curve */
569                 tAnimCopybufItem *aci= NULL;
570                 BezTriple *bezt;
571                 int i;
572                 
573                 /* find buffer item to paste from 
574                  *      - if names don't matter (i.e. only 1 channel in buffer), don't check id/group
575                  *      - if names do matter, only check if id-type is ok for now (group check is not that important)
576                  *      - most importantly, rna-paths should match (array indices are unimportant for now)
577                  */
578                 // TODO: the matching algorithm here is pathetic!
579                 for (aci= animcopybuf.first; aci; aci= aci->next) {
580                         /* check that paths exist */
581                         if (aci->rna_path && fcu->rna_path) {
582                                 // FIXME: this breaks for bone names!
583                                 if (strcmp(aci->rna_path, fcu->rna_path) == 0) {
584                                         /* should be a match unless there's more than one of these */
585                                         if ((no_name) || (aci->array_index == fcu->array_index)) 
586                                                 break;
587                                 }
588                         }
589                 }
590                 
591                 
592                 /* copy the relevant data from the matching buffer curve */
593                 if (aci) {
594                         /* just start pasting, with the the first keyframe on the current frame, and so on */
595                         for (i=0, bezt=aci->bezt; i < aci->totvert; i++, bezt++) {                                              
596                                 /* temporarily apply offset to src beztriple while copying */
597                                 bezt->vec[0][0] += offset;
598                                 bezt->vec[1][0] += offset;
599                                 bezt->vec[2][0] += offset;
600                                 
601                                 /* insert the keyframe
602                                  * NOTE: no special flags here for now
603                                  */
604                                 insert_bezt_fcurve(fcu, bezt, 0); 
605                                 
606                                 /* un-apply offset from src beztriple after copying */
607                                 bezt->vec[0][0] -= offset;
608                                 bezt->vec[1][0] -= offset;
609                                 bezt->vec[2][0] -= offset;
610                         }
611                         
612                         /* recalculate F-Curve's handles? */
613                         calchandles_fcurve(fcu);
614                 }
615         }
616         
617         return 0;
618 }
619
620 /* **************************************************** */