small merge needed for testing new animsys in 2.5 BGE, mixing own changes with merge...
[blender-staging.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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, 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_arithb.h"
37
38 #include "DNA_anim_types.h"
39 #include "DNA_action_types.h"
40 #include "DNA_curve_types.h"
41 #include "DNA_key_types.h"
42 #include "DNA_object_types.h"
43 #include "DNA_space_types.h"
44 #include "DNA_scene_types.h"
45
46 #include "BKE_action.h"
47 #include "BKE_fcurve.h"
48 #include "BKE_key.h"
49 #include "BKE_utildefines.h"
50
51 #include "ED_anim_api.h"
52 #include "ED_keyframing.h"
53 #include "ED_keyframes_edit.h"
54
55 /* This file contains code for various keyframe-editing tools which are 'destructive'
56  * (i.e. they will modify the order of the keyframes, and change the size of the array).
57  * While some of these tools may eventually be moved out into blenkernel, for now, it is
58  * fine to have these calls here.
59  * 
60  * There are also a few tools here which cannot be easily coded for in the other system (yet).
61  * These may also be moved around at some point, but for now, they 
62  *
63  * - Joshua Leung, Dec 2008
64  */
65  
66 /* **************************************************** */
67
68 /* Only delete the nominated keyframe from provided ipo-curve. 
69  * Not recommended to be used many times successively. For that
70  * there is delete_ipo_keys(). 
71  */
72 void delete_fcurve_key(FCurve *fcu, int index, short do_recalc)
73 {
74         /* firstly check that index is valid */
75         if (index < 0) 
76                 index *= -1;
77         if (fcu == NULL) 
78                 return;
79         if (index >= fcu->totvert)
80                 return;
81         
82         /*      Delete this key */
83         memmove(&fcu->bezt[index], &fcu->bezt[index+1], sizeof(BezTriple)*(fcu->totvert-index-1));
84         fcu->totvert--;
85         
86         /* recalc handles - only if it won't cause problems */
87         if (do_recalc)
88                 calchandles_fcurve(fcu);
89 }
90
91 /* Delete selected keyframes in given F-Curve */
92 void delete_fcurve_keys(FCurve *fcu)
93 {
94         int i;
95         
96         /* Delete selected BezTriples */
97         for (i=0; i < fcu->totvert; i++) {
98                 if (fcu->bezt[i].f2 & SELECT) {
99                         memmove(&fcu->bezt[i], &fcu->bezt[i+1], sizeof(BezTriple)*(fcu->totvert-i-1));
100                         fcu->totvert--;
101                         i--;
102                 }
103         }
104         
105         /* Free the array of BezTriples if there are not keyframes */
106         if (fcu->totvert == 0) {
107                 if (fcu->bezt) 
108                         MEM_freeN(fcu->bezt);
109                 fcu->bezt= NULL;
110         }
111         
112 #if 0 // XXX for now, we don't get rid of empty curves...
113         /* Only delete if there isn't an ipo-driver still hanging around on an empty curve */
114         if ((icu->totvert==0) && (icu->driver==NULL)) {
115                 BLI_remlink(&ipo->curve, icu);
116                 free_ipo_curve(icu);
117         }
118 #endif 
119 }
120
121 /* ---------------- */
122
123 /* duplicate selected keyframes for the given F-Curve */
124 void duplicate_fcurve_keys(FCurve *fcu)
125 {
126         BezTriple *newbezt;
127         int i;
128
129         if (fcu == NULL)
130                 return;
131         
132         // XXX this does not take into account sample data...
133         for (i=0; i < fcu->totvert; i++) {
134                 /* If a key is selected */
135                 if (fcu->bezt[i].f2 & SELECT) {
136                         /* Expand the list */
137                         newbezt = MEM_callocN(sizeof(BezTriple) * (fcu->totvert+1), "beztriple");
138                         
139                         memcpy(newbezt, fcu->bezt, sizeof(BezTriple) * (i+1));
140                         memcpy(newbezt+i+1, fcu->bezt+i, sizeof(BezTriple));
141                         memcpy(newbezt+i+2, fcu->bezt+i+1, sizeof (BezTriple) *(fcu->totvert-(i+1)));
142                         fcu->totvert++;
143                         
144                         /* reassign pointers... (free old, and add new) */
145                         MEM_freeN(fcu->bezt);
146                         fcu->bezt=newbezt;
147                         
148                         /* Unselect the current key */
149                         BEZ_DESEL(&fcu->bezt[i]);
150                         i++;
151                         
152                         /* Select the copied key */
153                         BEZ_SEL(&fcu->bezt[i]);
154                 }
155         }
156 }
157
158 /* **************************************************** */
159 /* Various Tools */
160
161 /* Basic IPO-Curve 'cleanup' function that removes 'double points' and unnecessary keyframes on linear-segments only */
162 void clean_fcurve(FCurve *fcu, float thresh)
163 {
164         BezTriple *old_bezts, *bezt, *beztn;
165         BezTriple *lastb;
166         int totCount, i;
167         
168         /* check if any points  */
169         if ((fcu == NULL) || (fcu->totvert <= 1)) 
170                 return;
171         
172         /* make a copy of the old BezTriples, and clear IPO curve */
173         old_bezts = fcu->bezt;
174         totCount = fcu->totvert;        
175         fcu->bezt = NULL;
176         fcu->totvert = 0;
177         
178         /* now insert first keyframe, as it should be ok */
179         bezt = old_bezts;
180         insert_vert_fcurve(fcu, bezt->vec[1][0], bezt->vec[1][1], 0);
181         
182         /* Loop through BezTriples, comparing them. Skip any that do 
183          * not fit the criteria for "ok" points.
184          */
185         for (i=1; i<totCount; i++) {    
186                 float prev[2], cur[2], next[2];
187                 
188                 /* get BezTriples and their values */
189                 if (i < (totCount - 1)) {
190                         beztn = (old_bezts + (i+1));
191                         next[0]= beztn->vec[1][0]; next[1]= beztn->vec[1][1];
192                 }
193                 else {
194                         beztn = NULL;
195                         next[0] = next[1] = 0.0f;
196                 }
197                 lastb= (fcu->bezt + (fcu->totvert - 1));
198                 bezt= (old_bezts + i);
199                 
200                 /* get references for quicker access */
201                 prev[0] = lastb->vec[1][0]; prev[1] = lastb->vec[1][1];
202                 cur[0] = bezt->vec[1][0]; cur[1] = bezt->vec[1][1];
203                 
204                 /* check if current bezt occurs at same time as last ok */
205                 if (IS_EQT(cur[0], prev[0], thresh)) {
206                         /* If there is a next beztriple, and if occurs at the same time, only insert 
207                          * if there is a considerable distance between the points, and also if the 
208                          * current is further away than the next one is to the previous.
209                          */
210                         if (beztn && (IS_EQT(cur[0], next[0], thresh)) && 
211                                 (IS_EQT(next[1], prev[1], thresh)==0)) 
212                         {
213                                 /* only add if current is further away from previous */
214                                 if (cur[1] > next[1]) {
215                                         if (IS_EQT(cur[1], prev[1], thresh) == 0) {
216                                                 /* add new keyframe */
217                                                 insert_vert_fcurve(fcu, cur[0], cur[1], 0);
218                                         }
219                                 }
220                         }
221                         else {
222                                 /* only add if values are a considerable distance apart */
223                                 if (IS_EQT(cur[1], prev[1], thresh) == 0) {
224                                         /* add new keyframe */
225                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
226                                 }
227                         }
228                 }
229                 else {
230                         /* checks required are dependent on whether this is last keyframe or not */
231                         if (beztn) {
232                                 /* does current have same value as previous and next? */
233                                 if (IS_EQT(cur[1], prev[1], thresh) == 0) {
234                                         /* add new keyframe*/
235                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
236                                 }
237                                 else if (IS_EQT(cur[1], next[1], thresh) == 0) {
238                                         /* add new keyframe */
239                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
240                                 }
241                         }
242                         else {  
243                                 /* add if value doesn't equal that of previous */
244                                 if (IS_EQT(cur[1], prev[1], thresh) == 0) {
245                                         /* add new keyframe */
246                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
247                                 }
248                         }
249                 }
250         }
251         
252         /* now free the memory used by the old BezTriples */
253         if (old_bezts)
254                 MEM_freeN(old_bezts);
255 }
256
257 /* ---------------- */
258
259 /* temp struct used for smooth_ipo */
260 typedef struct tSmooth_Bezt {
261         float *h1, *h2, *h3;    /* bezt->vec[0,1,2][1] */
262 } tSmooth_Bezt;
263
264 /* Use a weighted moving-means method to reduce intensity of fluctuations */
265 void smooth_fcurve (FCurve *fcu)
266 {
267         BezTriple *bezt;
268         int i, x, totSel = 0;
269         
270         /* first loop through - count how many verts are selected, and fix up handles 
271          *      this is done for both modes
272          */
273         bezt= fcu->bezt;
274         for (i=0; i < fcu->totvert; i++, bezt++) {                                              
275                 if (BEZSELECTED(bezt)) {                                                        
276                         /* line point's handles up with point's vertical position */
277                         bezt->vec[0][1]= bezt->vec[2][1]= bezt->vec[1][1];
278                         if ((bezt->h1==HD_AUTO) || (bezt->h1==HD_VECT)) bezt->h1= HD_ALIGN;
279                         if ((bezt->h2==HD_AUTO) || (bezt->h2==HD_VECT)) bezt->h2= HD_ALIGN;
280                         
281                         /* add value to total */
282                         totSel++;
283                 }
284         }
285         
286                 /* if any points were selected, allocate tSmooth_Bezt points to work on */
287                 if (totSel >= 3) {
288                         tSmooth_Bezt *tarray, *tsb;
289                         
290                         /* allocate memory in one go */
291                         tsb= tarray= MEM_callocN(totSel*sizeof(tSmooth_Bezt), "tSmooth_Bezt Array");
292                         
293                         /* populate tarray with data of selected points */
294                         bezt= fcu->bezt;
295                         for (i=0, x=0; (i < fcu->totvert) && (x < totSel); i++, bezt++) {
296                                 if (BEZSELECTED(bezt)) {
297                                         /* tsb simply needs pointer to vec, and index */
298                                         tsb->h1 = &bezt->vec[0][1];
299                                         tsb->h2 = &bezt->vec[1][1];
300                                         tsb->h3 = &bezt->vec[2][1];
301                                         
302                                         /* advance to the next tsb to populate */
303                                         if (x < totSel- 1) 
304                                                 tsb++;
305                                         else
306                                                 break;
307                                 }
308                         }
309                         
310         /* calculate the new smoothed F-Curve's with weighted averages:
311          *      - this is done with two passes
312          *      - uses 5 points for each operation (which stores in the relevant handles)
313          *      -       previous: w/a ratio = 3:5:2:1:1
314          *      -       next: w/a ratio = 1:1:2:5:3
315          */
316         
317         /* round 1: calculate previous and next */ 
318         tsb= tarray;
319         for (i=0; i < totSel; i++, tsb++) {
320                 /* don't touch end points (otherwise, curves slowly explode) */
321                 if (ELEM(i, 0, (totSel-1)) == 0) {
322                         const tSmooth_Bezt *tP1 = tsb - 1;
323                         const tSmooth_Bezt *tP2 = (i-2 > 0) ? (tsb - 2) : (NULL);
324                         const tSmooth_Bezt *tN1 = tsb + 1;
325                         const tSmooth_Bezt *tN2 = (i+2 < totSel) ? (tsb + 2) : (NULL);
326                         
327                         const float p1 = *tP1->h2;
328                         const float p2 = (tP2) ? (*tP2->h2) : (*tP1->h2);
329                         const float c1 = *tsb->h2;
330                         const float n1 = *tN1->h2;
331                         const float n2 = (tN2) ? (*tN2->h2) : (*tN1->h2);
332                         
333                         /* calculate previous and next */
334                         *tsb->h1= (3*p2 + 5*p1 + 2*c1 + n1 + n2) / 12;
335                         *tsb->h3= (p2 + p1 + 2*c1 + 5*n1 + 3*n2) / 12;
336                 }
337         }
338         
339         /* round 2: calculate new values and reset handles */
340         tsb= tarray;
341         for (i=0; i < totSel; i++, tsb++) {
342                 /* calculate new position by averaging handles */
343                 *tsb->h2 = (*tsb->h1 + *tsb->h3) / 2;
344                 
345                 /* reset handles now */
346                 *tsb->h1 = *tsb->h2;
347                 *tsb->h3 = *tsb->h2;
348         }
349         
350         /* free memory required for tarray */
351         MEM_freeN(tarray);
352 }
353         
354         /* recalculate handles */
355         calchandles_fcurve(fcu);
356 }
357
358 /* **************************************************** */
359 /* Copy/Paste Tools */
360 /* - The copy/paste buffer currently stores a set of temporary F-Curves containing only the keyframes 
361  *   that were selected in each of the original F-Curves
362  * - All pasted frames are offset by the same amount. This is calculated as the difference in the times of
363  *      the current frame and the 'first keyframe' (i.e. the earliest one in all channels).
364  * - The earliest frame is calculated per copy operation.
365  */
366
367 /* globals for copy/paste data (like for other copy/paste buffers) */
368 ListBase animcopybuf = {NULL, NULL};
369 static float animcopy_firstframe= 999999999.0f;
370
371 /* datatype for use in copy/paste buffer */
372 // XXX F-Curve editor should use this too
373 typedef struct tAnimCopybufItem {
374         struct tAnimCopybufItem *next, *prev;
375         
376         ID *id;                         /* ID which owns the curve */
377         bActionGroup *grp;      /* Action Group */
378         char *rna_path;         /* RNA-Path */
379         int array_index;        /* array index */
380         
381         int totvert;            /* number of keyframes stored for this channel */
382         BezTriple *bezt;        /* keyframes in buffer */
383 } tAnimCopybufItem;
384
385
386 /* This function frees any MEM_calloc'ed copy/paste buffer data */
387 // XXX find some header to put this in!
388 void free_anim_copybuf (void)
389 {
390         tAnimCopybufItem *aci, *acn;
391         
392         /* free each buffer element */
393         for (aci= animcopybuf.first; aci; aci= acn) {
394                 acn= aci->next;
395                 
396                 /* free keyframes */
397                 if (aci->bezt) 
398                         MEM_freeN(aci->bezt);
399                         
400                 /* free RNA-path */
401                 if (aci->rna_path)
402                         MEM_freeN(aci->rna_path);
403                         
404                 /* free ourself */
405                 BLI_freelinkN(&animcopybuf, aci);
406         }
407         
408         /* restore initial state */
409         animcopybuf.first= animcopybuf.last= NULL;
410         animcopy_firstframe= 999999999.0f;
411 }
412
413 /* ------------------- */
414
415 /* This function adds data to the keyframes copy/paste buffer, freeing existing data first */
416 short copy_animedit_keys (bAnimContext *ac, ListBase *anim_data)
417 {       
418         bAnimListElem *ale;
419         
420         /* clear buffer first */
421         free_anim_copybuf();
422         
423         /* assume that each of these is an F-Curve */
424         for (ale= anim_data->first; ale; ale= ale->next) {
425                 FCurve *fcu= (FCurve *)ale->key_data;
426                 tAnimCopybufItem *aci;
427                 BezTriple *bezt, *newbuf;
428                 int i;
429                 
430                 /* firstly, check if F-Curve has any selected keyframes
431                  *      - skip if no selected keyframes found (so no need to create unnecessary copy-buffer data)
432                  *      - this check should also eliminate any problems associated with using sample-data
433                  */
434                 if (ANIM_fcurve_keys_bezier_loop(NULL, fcu, NULL, ANIM_editkeyframes_ok(BEZT_OK_SELECTED), NULL) == 0)
435                         continue;
436                 
437                 /* init copybuf item info */
438                 aci= MEM_callocN(sizeof(tAnimCopybufItem), "AnimCopybufItem");
439                 aci->id= ale->id;
440                 aci->grp= fcu->grp;
441                 aci->rna_path= MEM_dupallocN(fcu->rna_path);
442                 aci->array_index= fcu->array_index;
443                 BLI_addtail(&animcopybuf, aci);
444                 
445                 /* add selected keyframes to buffer */
446                 // 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
447                 for (i=0, bezt=fcu->bezt; i < fcu->totvert; i++, bezt++) {
448                         if (BEZSELECTED(bezt)) {
449                                 /* add to buffer */
450                                 newbuf= MEM_callocN(sizeof(BezTriple)*(aci->totvert+1), "copybuf beztriple");
451                                 
452                                 /* assume that since we are just resizing the array, just copy all existing data across */
453                                 if (aci->bezt)
454                                         memcpy(newbuf, aci->bezt, sizeof(BezTriple)*(aci->totvert));
455                                 
456                                 /* copy current beztriple across too */
457                                 *(newbuf + aci->totvert)= *bezt; 
458                                 
459                                 /* free old array and set the new */
460                                 if (aci->bezt) MEM_freeN(aci->bezt);
461                                 aci->bezt= newbuf;
462                                 aci->totvert++;
463                                 
464                                 /* check if this is the earliest frame encountered so far */
465                                 if (bezt->vec[1][0] < animcopy_firstframe)
466                                         animcopy_firstframe= bezt->vec[1][0];
467                         }
468                 }
469                 
470         }
471         
472         /* check if anything ended up in the buffer */
473         if (ELEM(NULL, animcopybuf.first, animcopybuf.last))
474                 return -1;
475         
476         /* everything went fine */
477         return 0;
478 }
479
480 /* This function pastes data from the keyframes copy/paste buffer */
481 short paste_animedit_keys (bAnimContext *ac, ListBase *anim_data)
482 {
483         bAnimListElem *ale;
484         const Scene *scene= (ac->scene);
485         const float offset = (float)(CFRA - animcopy_firstframe);
486         short no_name= 0;
487         
488         /* check if buffer is empty */
489         if (ELEM(NULL, animcopybuf.first, animcopybuf.last)) {
490                 //error("No data in buffer to paste");
491                 return -1;
492         }
493         /* check if single channel in buffer (disregard names if so)  */
494         if (animcopybuf.first == animcopybuf.last)
495                 no_name= 1;
496         
497         /* from selected channels */
498         for (ale= anim_data->first; ale; ale= ale->next) {
499                 FCurve *fcu = (FCurve *)ale->data;              /* destination F-Curve */
500                 tAnimCopybufItem *aci= NULL;
501                 BezTriple *bezt;
502                 int i;
503                 
504                 /* find buffer item to paste from 
505                  *      - if names don't matter (i.e. only 1 channel in buffer), don't check id/group
506                  *      - if names do matter, only check if id-type is ok for now (group check is not that important)
507                  *      - most importantly, rna-paths should match (array indices are unimportant for now)
508                  */
509                 // TODO: the matching algorithm here is pathetic!
510                 for (aci= animcopybuf.first; aci; aci= aci->next) {
511                         /* check that paths exist */
512                         if (aci->rna_path && fcu->rna_path) {
513                                 if (strcmp(aci->rna_path, fcu->rna_path) == 0) {
514                                         /* should be a match unless there's more than one of these */
515                                         if ((no_name) || (aci->array_index == fcu->array_index)) 
516                                                 break;
517                                 }
518                         }
519                 }
520                 
521                 
522                 /* copy the relevant data from the matching buffer curve */
523                 if (aci) {
524                         /* just start pasting, with the the first keyframe on the current frame, and so on */
525                         for (i=0, bezt=aci->bezt; i < aci->totvert; i++, bezt++) {                                              
526                                 /* temporarily apply offset to src beztriple while copying */
527                                 bezt->vec[0][0] += offset;
528                                 bezt->vec[1][0] += offset;
529                                 bezt->vec[2][0] += offset;
530                                 
531                                 /* insert the keyframe */
532                                 insert_bezt_fcurve(fcu, bezt);
533                                 
534                                 /* un-apply offset from src beztriple after copying */
535                                 bezt->vec[0][0] -= offset;
536                                 bezt->vec[1][0] -= offset;
537                                 bezt->vec[2][0] -= offset;
538                         }
539                         
540                         /* recalculate F-Curve's handles? */
541                         calchandles_fcurve(fcu);
542                 }
543         }
544         
545         return 0;
546 }
547
548 /* **************************************************** */