f0d9c48eb5e77325c20b483cbdf42c04993912c5
[blender.git] / source / blender / editors / animation / keyframes_general.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2008 Blender Foundation
19  * All rights reserved.
20  *
21  * Contributor(s): Joshua Leung
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 /** \file blender/editors/animation/keyframes_general.c
27  *  \ingroup edanimation
28  */
29
30
31 #include <stdlib.h>
32 #include <string.h>
33 #include <math.h>
34 #include <float.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "BLI_blenlib.h"
39 #include "BLI_utildefines.h"
40
41 #include "DNA_anim_types.h"
42 #include "DNA_object_types.h"
43 #include "DNA_scene_types.h"
44
45
46 #include "BKE_action.h"
47 #include "BKE_fcurve.h"
48 #include "BKE_report.h"
49 #include "BKE_library.h"
50 #include "BKE_global.h"
51 #include "BKE_deform.h"
52
53 #include "RNA_access.h"
54
55 #include "ED_anim_api.h"
56 #include "ED_keyframing.h"
57 #include "ED_keyframes_edit.h"
58
59 /* This file contains code for various keyframe-editing tools which are 'destructive'
60  * (i.e. they will modify the order of the keyframes, and change the size of the array).
61  * While some of these tools may eventually be moved out into blenkernel, for now, it is
62  * fine to have these calls here.
63  * 
64  * There are also a few tools here which cannot be easily coded for in the other system (yet).
65  * These may also be moved around at some point, but for now, they are best added here.
66  *
67  * - Joshua Leung, Dec 2008
68  */
69  
70 /* **************************************************** */
71
72 /* Only delete the nominated keyframe from provided F-Curve. 
73  * Not recommended to be used many times successively. For that
74  * there is delete_fcurve_keys(). 
75  */
76 void delete_fcurve_key(FCurve *fcu, int index, bool do_recalc)
77 {
78         /* sanity check */
79         if (fcu == NULL) 
80                 return;
81                 
82         /* verify the index:
83          *      1) cannot be greater than the number of available keyframes
84          *      2) negative indices are for specifying a value from the end of the array
85          */
86         if (abs(index) >= fcu->totvert)
87                 return;
88         else if (index < 0)
89                 index += fcu->totvert;
90         
91         /* Delete this keyframe */
92         memmove(&fcu->bezt[index], &fcu->bezt[index + 1], sizeof(BezTriple) * (fcu->totvert - index - 1));
93         fcu->totvert--;
94
95         if (fcu->totvert == 0) {
96                 if (fcu->bezt)
97                         MEM_freeN(fcu->bezt);
98                 fcu->bezt = NULL;
99         }
100         
101         /* recalc handles - only if it won't cause problems */
102         if (do_recalc)
103                 calchandles_fcurve(fcu);
104 }
105
106 /* Delete selected keyframes in given F-Curve */
107 bool delete_fcurve_keys(FCurve *fcu)
108 {
109         int i;
110         bool changed = false;
111         
112         if (fcu->bezt == NULL) /* ignore baked curves */
113                 return false;
114
115         /* Delete selected BezTriples */
116         for (i = 0; i < fcu->totvert; i++) {
117                 if (fcu->bezt[i].f2 & SELECT) {
118                         memmove(&fcu->bezt[i], &fcu->bezt[i + 1], sizeof(BezTriple) * (fcu->totvert - i - 1));
119                         fcu->totvert--;
120                         i--;
121                         changed = true;
122                 }
123         }
124         
125         /* Free the array of BezTriples if there are not keyframes */
126         if (fcu->totvert == 0)
127                 clear_fcurve_keys(fcu);
128
129         return changed;
130 }
131
132
133 void clear_fcurve_keys(FCurve *fcu)
134 {
135         if (fcu->bezt)
136                 MEM_freeN(fcu->bezt);
137         fcu->bezt = NULL;
138
139         fcu->totvert = 0;
140 }
141
142 /* ---------------- */
143
144 /* duplicate selected keyframes for the given F-Curve */
145 void duplicate_fcurve_keys(FCurve *fcu)
146 {
147         BezTriple *newbezt;
148         int i;
149         
150         /* this can only work when there is an F-Curve, and also when there are some BezTriples */
151         if (ELEM(NULL, fcu, fcu->bezt))
152                 return;
153         
154         for (i = 0; i < fcu->totvert; i++) {
155                 /* If a key is selected */
156                 if (fcu->bezt[i].f2 & SELECT) {
157                         /* Expand the list */
158                         newbezt = MEM_callocN(sizeof(BezTriple) * (fcu->totvert + 1), "beztriple");
159                         
160                         memcpy(newbezt, fcu->bezt, sizeof(BezTriple) * (i + 1));
161                         memcpy(newbezt + i + 1, fcu->bezt + i, sizeof(BezTriple));
162                         memcpy(newbezt + i + 2, fcu->bezt + i + 1, sizeof(BezTriple) * (fcu->totvert - (i + 1)));
163                         fcu->totvert++;
164                         
165                         /* reassign pointers... (free old, and add new) */
166                         MEM_freeN(fcu->bezt);
167                         fcu->bezt = newbezt;
168                         
169                         /* Unselect the current key */
170                         BEZT_DESEL_ALL(&fcu->bezt[i]);
171                         i++;
172                         
173                         /* Select the copied key */
174                         BEZT_SEL_ALL(&fcu->bezt[i]);
175                 }
176         }
177 }
178
179 /* **************************************************** */
180 /* Various Tools */
181
182 /* Basic F-Curve 'cleanup' function that removes 'double points' and unnecessary keyframes on linear-segments only
183  * optionally clears up curve if one keyframe with default value remains */
184 void clean_fcurve(struct bAnimContext *ac, bAnimListElem *ale, float thresh, bool cleardefault)
185 {
186         FCurve *fcu = (FCurve *)ale->key_data;
187         BezTriple *old_bezts, *bezt, *beztn;
188         BezTriple *lastb;
189         int totCount, i;
190         
191         /* check if any points  */
192         if ((fcu == NULL) || (fcu->bezt == NULL) || (fcu->totvert == 0) ||
193             (!cleardefault && fcu->totvert == 1))
194         {
195                 return;
196         }
197
198         /* make a copy of the old BezTriples, and clear F-Curve */
199         old_bezts = fcu->bezt;
200         totCount = fcu->totvert;
201         fcu->bezt = NULL;
202         fcu->totvert = 0;
203         
204         /* now insert first keyframe, as it should be ok */
205         bezt = old_bezts;
206         insert_vert_fcurve(fcu, bezt->vec[1][0], bezt->vec[1][1], 0);
207         if (!(bezt->f2 & SELECT)) {
208                 lastb = fcu->bezt;
209                 lastb->f1 = lastb->f2 = lastb->f3 = 0;
210         }
211         
212         /* Loop through BezTriples, comparing them. Skip any that do 
213          * not fit the criteria for "ok" points.
214          */
215         for (i = 1; i < totCount; i++) {
216                 float prev[2], cur[2], next[2];
217
218                 /* get BezTriples and their values */
219                 if (i < (totCount - 1)) {
220                         beztn = (old_bezts + (i + 1));
221                         next[0] = beztn->vec[1][0]; next[1] = beztn->vec[1][1];
222                 }
223                 else {
224                         beztn = NULL;
225                         next[0] = next[1] = 0.0f;
226                 }
227                 lastb = (fcu->bezt + (fcu->totvert - 1));
228                 bezt = (old_bezts + i);
229
230                 /* get references for quicker access */
231                 prev[0] = lastb->vec[1][0]; prev[1] = lastb->vec[1][1];
232                 cur[0] = bezt->vec[1][0]; cur[1] = bezt->vec[1][1];
233
234                 if (!(bezt->f2 & SELECT)) {
235                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
236                         lastb = (fcu->bezt + (fcu->totvert - 1));
237                         lastb->f1 = lastb->f2 = lastb->f3 = 0;
238                         continue;
239                 }
240                 
241                 /* check if current bezt occurs at same time as last ok */
242                 if (IS_EQT(cur[0], prev[0], thresh)) {
243                         /* If there is a next beztriple, and if occurs at the same time, only insert 
244                          * if there is a considerable distance between the points, and also if the 
245                          * current is further away than the next one is to the previous.
246                          */
247                         if (beztn && (IS_EQT(cur[0], next[0], thresh)) &&
248                             (IS_EQT(next[1], prev[1], thresh) == 0))
249                         {
250                                 /* only add if current is further away from previous */
251                                 if (cur[1] > next[1]) {
252                                         if (IS_EQT(cur[1], prev[1], thresh) == 0) {
253                                                 /* add new keyframe */
254                                                 insert_vert_fcurve(fcu, cur[0], cur[1], 0);
255                                         }
256                                 }
257                         }
258                         else {
259                                 /* only add if values are a considerable distance apart */
260                                 if (IS_EQT(cur[1], prev[1], thresh) == 0) {
261                                         /* add new keyframe */
262                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
263                                 }
264                         }
265                 }
266                 else {
267                         /* checks required are dependent on whether this is last keyframe or not */
268                         if (beztn) {
269                                 /* does current have same value as previous and next? */
270                                 if (IS_EQT(cur[1], prev[1], thresh) == 0) {
271                                         /* add new keyframe*/
272                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
273                                 }
274                                 else if (IS_EQT(cur[1], next[1], thresh) == 0) {
275                                         /* add new keyframe */
276                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
277                                 }
278                         }
279                         else {
280                                 /* add if value doesn't equal that of previous */
281                                 if (IS_EQT(cur[1], prev[1], thresh) == 0) {
282                                         /* add new keyframe */
283                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
284                                 }
285                         }
286                 }
287         }
288         
289         /* now free the memory used by the old BezTriples */
290         if (old_bezts)
291                 MEM_freeN(old_bezts);
292
293         /* final step, if there is just one key in fcurve, check if it's
294          * the default value and if is, remove fcurve completely. */
295         if (cleardefault && fcu->totvert == 1) {
296                 float default_value = 0.0f;
297                 PointerRNA id_ptr, ptr;
298                 PropertyRNA *prop;
299                 RNA_id_pointer_create(ale->id, &id_ptr);
300
301                 /* get property to read from, and get value as appropriate */
302                 if (RNA_path_resolve_property(&id_ptr, fcu->rna_path, &ptr, &prop)) {
303                         if (RNA_property_type(prop) == PROP_FLOAT)
304                                 default_value = RNA_property_float_get_default_index(&ptr, prop, fcu->array_index);
305                 }
306
307                 if (fcu->bezt->vec[1][1] == default_value) {
308                         clear_fcurve_keys(fcu);
309
310                         /* check if curve is really unused and if it is, return signal for deletion */
311                         if ((list_has_suitable_fmodifier(&fcu->modifiers, 0, FMI_TYPE_GENERATE_CURVE) == 0) &&
312                             (fcu->driver == NULL))
313                         {
314                                 AnimData *adt = ale->adt;
315                                 ANIM_fcurve_delete_from_animdata(ac, adt, fcu);
316                                 ale->key_data = NULL;
317                         }
318                 }
319         }
320 }
321
322 /* ---------------- */
323
324 /* temp struct used for smooth_fcurve */
325 typedef struct tSmooth_Bezt {
326         float *h1, *h2, *h3;    /* bezt->vec[0,1,2][1] */
327         float y1, y2, y3;       /* averaged before/new/after y-values */
328 } tSmooth_Bezt;
329
330 /* Use a weighted moving-means method to reduce intensity of fluctuations */
331 // TODO: introduce scaling factor for weighting falloff
332 void smooth_fcurve(FCurve *fcu)
333 {
334         BezTriple *bezt;
335         int i, x, totSel = 0;
336
337         if (fcu->bezt == NULL) {
338                 return;
339         }
340
341         /* first loop through - count how many verts are selected */
342         bezt = fcu->bezt;
343         for (i = 0; i < fcu->totvert; i++, bezt++) {
344                 if (BEZT_ISSEL_ANY(bezt))
345                         totSel++;
346         }
347         
348         /* if any points were selected, allocate tSmooth_Bezt points to work on */
349         if (totSel >= 3) {
350                 tSmooth_Bezt *tarray, *tsb;
351                 
352                 /* allocate memory in one go */
353                 tsb = tarray = MEM_callocN(totSel * sizeof(tSmooth_Bezt), "tSmooth_Bezt Array");
354                 
355                 /* populate tarray with data of selected points */
356                 bezt = fcu->bezt;
357                 for (i = 0, x = 0; (i < fcu->totvert) && (x < totSel); i++, bezt++) {
358                         if (BEZT_ISSEL_ANY(bezt)) {
359                                 /* tsb simply needs pointer to vec, and index */
360                                 tsb->h1 = &bezt->vec[0][1];
361                                 tsb->h2 = &bezt->vec[1][1];
362                                 tsb->h3 = &bezt->vec[2][1];
363                                 
364                                 /* advance to the next tsb to populate */
365                                 if (x < totSel - 1)
366                                         tsb++;
367                                 else
368                                         break;
369                         }
370                 }
371                         
372                 /* calculate the new smoothed F-Curve's with weighted averages:
373                  *      - this is done with two passes to avoid progressive corruption errors
374                  *      - uses 5 points for each operation (which stores in the relevant handles)
375                  *      -   previous: w/a ratio = 3:5:2:1:1
376                  *      -   next: w/a ratio = 1:1:2:5:3
377                  */
378                 
379                 /* round 1: calculate smoothing deltas and new values */ 
380                 tsb = tarray;
381                 for (i = 0; i < totSel; i++, tsb++) {
382                         /* don't touch end points (otherwise, curves slowly explode, as we don't have enough data there) */
383                         if (ELEM(i, 0, (totSel - 1)) == 0) {
384                                 const tSmooth_Bezt *tP1 = tsb - 1;
385                                 const tSmooth_Bezt *tP2 = (i - 2 > 0) ? (tsb - 2) : (NULL);
386                                 const tSmooth_Bezt *tN1 = tsb + 1;
387                                 const tSmooth_Bezt *tN2 = (i + 2 < totSel) ? (tsb + 2) : (NULL);
388                                 
389                                 const float p1 = *tP1->h2;
390                                 const float p2 = (tP2) ? (*tP2->h2) : (*tP1->h2);
391                                 const float c1 = *tsb->h2;
392                                 const float n1 = *tN1->h2;
393                                 const float n2 = (tN2) ? (*tN2->h2) : (*tN1->h2);
394                                 
395                                 /* calculate previous and next, then new position by averaging these */
396                                 tsb->y1 = (3 * p2 + 5 * p1 + 2 * c1 + n1 + n2) / 12;
397                                 tsb->y3 = (p2 + p1 + 2 * c1 + 5 * n1 + 3 * n2) / 12;
398                                 
399                                 tsb->y2 = (tsb->y1 + tsb->y3) / 2;
400                         }
401                 }
402                 
403                 /* round 2: apply new values */
404                 tsb = tarray;
405                 for (i = 0; i < totSel; i++, tsb++) {
406                         /* don't touch end points, as their values weren't touched above */
407                         if (ELEM(i, 0, (totSel - 1)) == 0) {
408                                 /* y2 takes the average of the 2 points */
409                                 *tsb->h2 = tsb->y2;
410                                 
411                                 /* handles are weighted between their original values and the averaged values */
412                                 *tsb->h1 = ((*tsb->h1) * 0.7f) + (tsb->y1 * 0.3f); 
413                                 *tsb->h3 = ((*tsb->h3) * 0.7f) + (tsb->y3 * 0.3f);
414                         }
415                 }
416                 
417                 /* free memory required for tarray */
418                 MEM_freeN(tarray);
419         }
420         
421         /* recalculate handles */
422         calchandles_fcurve(fcu);
423 }
424
425 /* ---------------- */
426
427 /* little cache for values... */
428 typedef struct TempFrameValCache {
429         float frame, val;
430 } TempFrameValCache;
431
432
433 /* Evaluates the curves between each selected keyframe on each frame, and keys the value  */
434 void sample_fcurve(FCurve *fcu)
435 {
436         BezTriple *bezt, *start = NULL, *end = NULL;
437         TempFrameValCache *value_cache, *fp;
438         int sfra, range;
439         int i, n, nIndex;
440
441         if (fcu->bezt == NULL) /* ignore baked */
442                 return;
443         
444         /* find selected keyframes... once pair has been found, add keyframes  */
445         for (i = 0, bezt = fcu->bezt; i < fcu->totvert; i++, bezt++) {
446                 /* check if selected, and which end this is */
447                 if (BEZT_ISSEL_ANY(bezt)) {
448                         if (start) {
449                                 /* set end */
450                                 end = bezt;
451                                 
452                                 /* cache values then add keyframes using these values, as adding
453                                  * keyframes while sampling will affect the outcome...
454                                  *      - only start sampling+adding from index=1, so that we don't overwrite original keyframe
455                                  */
456                                 range = (int)(ceil(end->vec[1][0] - start->vec[1][0]));
457                                 sfra = (int)(floor(start->vec[1][0]));
458                                 
459                                 if (range) {
460                                         value_cache = MEM_callocN(sizeof(TempFrameValCache) * range, "IcuFrameValCache");
461                                         
462                                         /* sample values */
463                                         for (n = 1, fp = value_cache; n < range && fp; n++, fp++) {
464                                                 fp->frame = (float)(sfra + n);
465                                                 fp->val = evaluate_fcurve(fcu, fp->frame);
466                                         }
467                                         
468                                         /* add keyframes with these, tagging as 'breakdowns' */
469                                         for (n = 1, fp = value_cache; n < range && fp; n++, fp++) {
470                                                 nIndex = insert_vert_fcurve(fcu, fp->frame, fp->val, 1);
471                                                 BEZKEYTYPE(fcu->bezt + nIndex) = BEZT_KEYTYPE_BREAKDOWN;
472                                         }
473                                         
474                                         /* free temp cache */
475                                         MEM_freeN(value_cache);
476                                         
477                                         /* as we added keyframes, we need to compensate so that bezt is at the right place */
478                                         bezt = fcu->bezt + i + range - 1;
479                                         i += (range - 1);
480                                 }
481                                 
482                                 /* bezt was selected, so it now marks the start of a whole new chain to search */
483                                 start = bezt;
484                                 end = NULL;
485                         }
486                         else {
487                                 /* just set start keyframe */
488                                 start = bezt;
489                                 end = NULL;
490                         }
491                 }
492         }
493         
494         /* recalculate channel's handles? */
495         calchandles_fcurve(fcu);
496 }
497
498 /* **************************************************** */
499 /* Copy/Paste Tools */
500 /* - The copy/paste buffer currently stores a set of temporary F-Curves containing only the keyframes 
501  *   that were selected in each of the original F-Curves
502  * - All pasted frames are offset by the same amount. This is calculated as the difference in the times of
503  *      the current frame and the 'first keyframe' (i.e. the earliest one in all channels).
504  * - The earliest frame is calculated per copy operation.
505  */
506
507 /* globals for copy/paste data (like for other copy/paste buffers) */
508 static ListBase animcopybuf = {NULL, NULL};
509 static float animcopy_firstframe = 999999999.0f;
510 static float animcopy_lastframe = -999999999.0f;
511 static float animcopy_cfra = 0.0;
512
513 /* datatype for use in copy/paste buffer */
514 typedef struct tAnimCopybufItem {
515         struct tAnimCopybufItem *next, *prev;
516         
517         ID *id;             /* ID which owns the curve */
518         bActionGroup *grp;  /* Action Group */
519         char *rna_path;     /* RNA-Path */
520         int array_index;    /* array index */
521         
522         int totvert;        /* number of keyframes stored for this channel */
523         BezTriple *bezt;    /* keyframes in buffer */
524
525         short id_type;      /* Result of GS(id->name)*/
526         bool  is_bone;      /* special flag for armature bones */
527 } tAnimCopybufItem;
528
529
530 /* This function frees any MEM_calloc'ed copy/paste buffer data */
531 // XXX find some header to put this in!
532 void free_anim_copybuf(void)
533 {
534         tAnimCopybufItem *aci, *acn;
535         
536         /* free each buffer element */
537         for (aci = animcopybuf.first; aci; aci = acn) {
538                 acn = aci->next;
539                 
540                 /* free keyframes */
541                 if (aci->bezt) 
542                         MEM_freeN(aci->bezt);
543                         
544                 /* free RNA-path */
545                 if (aci->rna_path)
546                         MEM_freeN(aci->rna_path);
547                         
548                 /* free ourself */
549                 BLI_freelinkN(&animcopybuf, aci);
550         }
551         
552         /* restore initial state */
553         BLI_listbase_clear(&animcopybuf);
554         animcopy_firstframe = 999999999.0f;
555         animcopy_lastframe = -999999999.0f;
556 }
557
558 /* ------------------- */
559
560 /* This function adds data to the keyframes copy/paste buffer, freeing existing data first */
561 short copy_animedit_keys(bAnimContext *ac, ListBase *anim_data)
562 {       
563         bAnimListElem *ale;
564         Scene *scene = ac->scene;
565         
566         /* clear buffer first */
567         free_anim_copybuf();
568         
569         /* assume that each of these is an F-Curve */
570         for (ale = anim_data->first; ale; ale = ale->next) {
571                 FCurve *fcu = (FCurve *)ale->key_data;
572                 tAnimCopybufItem *aci;
573                 BezTriple *bezt, *nbezt, *newbuf;
574                 int i;
575                 
576                 /* firstly, check if F-Curve has any selected keyframes
577                  *      - skip if no selected keyframes found (so no need to create unnecessary copy-buffer data)
578                  *      - this check should also eliminate any problems associated with using sample-data
579                  */
580                 if (ANIM_fcurve_keyframes_loop(NULL, fcu, NULL, ANIM_editkeyframes_ok(BEZT_OK_SELECTED), NULL) == 0)
581                         continue;
582                 
583                 /* init copybuf item info */
584                 aci = MEM_callocN(sizeof(tAnimCopybufItem), "AnimCopybufItem");
585                 aci->id = ale->id;
586                 aci->id_type = GS(ale->id->name);
587                 aci->grp = fcu->grp;
588                 aci->rna_path = MEM_dupallocN(fcu->rna_path);
589                 aci->array_index = fcu->array_index;
590                 
591                 /* detect if this is a bone. We do that here rather than during pasting because ID pointers will get invalidated if we undo.
592                  * storing the relevant information here helps avoiding crashes if we undo-repaste */
593                 if ((aci->id_type == ID_OB) && (((Object *)aci->id)->type == OB_ARMATURE) && aci->rna_path) {
594                         Object *ob = (Object *)aci->id;
595                         bPoseChannel *pchan;
596                         char *bone_name;
597
598                         bone_name = BLI_str_quoted_substrN(aci->rna_path, "pose.bones[");
599                         pchan = BKE_pose_channel_find_name(ob->pose, bone_name);
600                         if (pchan) {
601                                 aci->is_bone = true;
602                         }
603                         if (bone_name) MEM_freeN(bone_name);
604                 }
605                 
606                 BLI_addtail(&animcopybuf, aci);
607                 
608                 /* add selected keyframes to buffer */
609                 /* TODO: currently, we resize array every time we add a new vert -
610                  * this works ok as long as it is assumed only a few keys are copied */
611                 for (i = 0, bezt = fcu->bezt; i < fcu->totvert; i++, bezt++) {
612                         if (BEZT_ISSEL_ANY(bezt)) {
613                                 /* add to buffer */
614                                 newbuf = MEM_callocN(sizeof(BezTriple) * (aci->totvert + 1), "copybuf beztriple");
615                                 
616                                 /* assume that since we are just re-sizing the array, just copy all existing data across */
617                                 if (aci->bezt)
618                                         memcpy(newbuf, aci->bezt, sizeof(BezTriple) * (aci->totvert));
619                                 
620                                 /* copy current beztriple across too */
621                                 nbezt = &newbuf[aci->totvert];
622                                 *nbezt = *bezt;
623                                 
624                                 /* ensure copy buffer is selected so pasted keys are selected */
625                                 BEZT_SEL_ALL(nbezt);
626                                 
627                                 /* free old array and set the new */
628                                 if (aci->bezt) MEM_freeN(aci->bezt);
629                                 aci->bezt = newbuf;
630                                 aci->totvert++;
631                                 
632                                 /* check if this is the earliest frame encountered so far */
633                                 if (bezt->vec[1][0] < animcopy_firstframe)
634                                         animcopy_firstframe = bezt->vec[1][0];
635                                 if (bezt->vec[1][0] > animcopy_lastframe)
636                                         animcopy_lastframe = bezt->vec[1][0];
637                         }
638                 }
639                 
640         }
641         
642         /* check if anything ended up in the buffer */
643         if (ELEM(NULL, animcopybuf.first, animcopybuf.last))
644                 return -1;
645
646         /* in case 'relative' paste method is used */
647         animcopy_cfra = CFRA;
648
649         /* everything went fine */
650         return 0;
651 }
652
653 static void flip_names(tAnimCopybufItem *aci, char **name)
654 {
655         if (aci->is_bone) {
656                 char *str_start;
657                 if ((str_start = strstr(aci->rna_path, "pose.bones["))) {
658                         /* ninja coding, try to change the name */
659                         char bname_new[MAX_VGROUP_NAME];
660                         char *str_iter, *str_end;
661                         int length, prefix_l, postfix_l;
662
663                         str_start += 12;
664                         prefix_l = str_start - aci->rna_path;
665
666                         str_end = strchr(str_start, '\"');
667
668                         length = str_end - str_start;
669                         postfix_l = strlen(str_end);
670
671                         /* more ninja stuff, temporary substitute with NULL terminator */
672                         str_start[length] = 0;
673                         BKE_deform_flip_side_name(bname_new, str_start, false);
674                         str_start[length] = '\"';
675
676                         str_iter = *name = MEM_mallocN(sizeof(char) * (prefix_l + postfix_l + length + 1), "flipped_path");
677
678                         BLI_strncpy(str_iter, aci->rna_path, prefix_l + 1);
679                         str_iter += prefix_l;
680                         BLI_strncpy(str_iter, bname_new, length + 1);
681                         str_iter += length;
682                         BLI_strncpy(str_iter, str_end, postfix_l + 1);
683                         str_iter[postfix_l] = '\0';
684                 }
685         }
686 }
687
688 /* ------------------- */
689
690 /* most strict method: exact matches only */
691 static tAnimCopybufItem *pastebuf_match_path_full(FCurve *fcu, const short from_single, const short to_simple, bool flip)
692 {
693         tAnimCopybufItem *aci;
694
695         for (aci = animcopybuf.first; aci; aci = aci->next) {
696                 if (to_simple || (aci->rna_path && fcu->rna_path)) {
697                         if (!to_simple && flip && aci->is_bone && fcu->rna_path) {
698                                 if ((from_single) || (aci->array_index == fcu->array_index)) {
699                                         char *name = NULL;
700                                         flip_names(aci, &name);
701                                         if (STREQ(name, fcu->rna_path)) {
702                                                 MEM_freeN(name);
703                                                 break;
704                                         }
705                                         MEM_freeN(name);
706                                 }
707                         }
708                         else if (to_simple || STREQ(aci->rna_path, fcu->rna_path)) {
709                                 if ((from_single) || (aci->array_index == fcu->array_index)) {
710                                         break;
711                                 }
712                         }
713                 }
714         }
715
716         return aci;
717 }
718
719 /* medium match strictness: path match only (i.e. ignore ID) */
720 static tAnimCopybufItem *pastebuf_match_path_property(FCurve *fcu, const short from_single, const short UNUSED(to_simple))
721 {
722         tAnimCopybufItem *aci;
723
724         for (aci = animcopybuf.first; aci; aci = aci->next) {
725                 /* check that paths exist */
726                 if (aci->rna_path && fcu->rna_path) {
727                         /* find the property of the fcurve and compare against the end of the tAnimCopybufItem
728                          * more involved since it needs to to path lookups.
729                          * This is not 100% reliable since the user could be editing the curves on a path that wont
730                          * resolve, or a bone could be renamed after copying for eg. but in normal copy & paste
731                          * this should work out ok. 
732                          */
733                         if (BLI_findindex(which_libbase(G.main, aci->id_type), aci->id) == -1) {
734                                 /* pedantic but the ID could have been removed, and beats crashing! */
735                                 printf("paste_animedit_keys: error ID has been removed!\n");
736                         }
737                         else {
738                                 PointerRNA id_ptr, rptr;
739                                 PropertyRNA *prop;
740                                 
741                                 RNA_id_pointer_create(aci->id, &id_ptr);
742                                 
743                                 if (RNA_path_resolve_property(&id_ptr, aci->rna_path, &rptr, &prop)) {
744                                         const char *identifier = RNA_property_identifier(prop);
745                                         int len_id = strlen(identifier);
746                                         int len_path = strlen(fcu->rna_path);
747                                         if (len_id <= len_path) {
748                                                 /* note, paths which end with "] will fail with this test - Animated ID Props */
749                                                 if (STREQ(identifier, fcu->rna_path + (len_path - len_id))) {
750                                                         if ((from_single) || (aci->array_index == fcu->array_index))
751                                                                 break;
752                                                 }
753                                         }
754                                 }
755                                 else {
756                                         printf("paste_animedit_keys: failed to resolve path id:%s, '%s'!\n", aci->id->name, aci->rna_path);
757                                 }
758                         }
759                 }
760         }
761
762         return aci;
763 }
764
765 /* least strict matching heuristic: indices only */
766 static tAnimCopybufItem *pastebuf_match_index_only(FCurve *fcu, const short from_single, const short UNUSED(to_simple))
767 {
768         tAnimCopybufItem *aci;
769
770         for (aci = animcopybuf.first; aci; aci = aci->next) {
771                 /* check that paths exist */
772                 if ((from_single) || (aci->array_index == fcu->array_index)) {
773                         break;
774                 }
775         }
776
777         return aci;
778 }
779
780 /* ................ */
781
782 static void do_curve_mirror_flippping(tAnimCopybufItem *aci, BezTriple *bezt)
783 {
784         if (aci->is_bone) {
785                 const size_t slength = strlen(aci->rna_path);
786                 bool flip = false;
787                 if (BLI_strn_endswith(aci->rna_path, "location", slength) && aci->array_index == 0)
788                         flip = true;
789                 else if (BLI_strn_endswith(aci->rna_path, "rotation_quaternion", slength) && ELEM(aci->array_index, 2, 3))
790                         flip = true;
791                 else if (BLI_strn_endswith(aci->rna_path, "rotation_euler", slength) && ELEM(aci->array_index, 1, 2))
792                         flip = true;
793                 else if (BLI_strn_endswith(aci->rna_path, "rotation_axis_angle", slength) && ELEM(aci->array_index, 2, 3))
794                         flip = true;
795                 
796                 if (flip) {
797                         bezt->vec[0][1] = -bezt->vec[0][1];
798                         bezt->vec[1][1] = -bezt->vec[1][1];
799                         bezt->vec[2][1] = -bezt->vec[2][1];
800                 }
801         }
802 }
803
804 /* helper for paste_animedit_keys() - performs the actual pasting */
805 static void paste_animedit_keys_fcurve(FCurve *fcu, tAnimCopybufItem *aci, float offset, const eKeyMergeMode merge_mode, bool flip)
806 {
807         BezTriple *bezt;
808         int i;
809
810         /* First de-select existing FCurve's keyframes */
811         for (i = 0, bezt = fcu->bezt; i < fcu->totvert; i++, bezt++) {
812                 BEZT_DESEL_ALL(bezt);
813         }
814
815         /* mix mode with existing data */
816         switch (merge_mode) {
817                 case KEYFRAME_PASTE_MERGE_MIX:
818                         /* do-nothing */
819                         break;
820                         
821                 case KEYFRAME_PASTE_MERGE_OVER:
822                         /* remove all keys */
823                         clear_fcurve_keys(fcu);
824                         break;
825                         
826                 case KEYFRAME_PASTE_MERGE_OVER_RANGE:
827                 case KEYFRAME_PASTE_MERGE_OVER_RANGE_ALL:
828                 {
829                         float f_min;
830                         float f_max;
831                         
832                         if (merge_mode == KEYFRAME_PASTE_MERGE_OVER_RANGE) {
833                                 f_min = aci->bezt[0].vec[1][0] + offset;
834                                 f_max = aci->bezt[aci->totvert - 1].vec[1][0] + offset;
835                         }
836                         else { /* Entire Range */
837                                 f_min = animcopy_firstframe + offset;
838                                 f_max = animcopy_lastframe + offset;
839                         }
840                         
841                         /* remove keys in range */
842                         if (f_min < f_max) {
843                                 /* select verts in range for removal */
844                                 for (i = 0, bezt = fcu->bezt; i < fcu->totvert; i++, bezt++) {
845                                         if ((f_min < bezt[0].vec[1][0]) && (bezt[0].vec[1][0] < f_max)) {
846                                                 bezt->f2 |= SELECT;
847                                         }
848                                 }
849                                 
850                                 /* remove frames in the range */
851                                 delete_fcurve_keys(fcu);
852                         }
853                         break;
854                 }
855         }
856         
857         /* just start pasting, with the first keyframe on the current frame, and so on */
858         for (i = 0, bezt = aci->bezt; i < aci->totvert; i++, bezt++) {
859                 /* temporarily apply offset to src beztriple while copying */
860                 if (flip)
861                         do_curve_mirror_flippping(aci, bezt);
862                 
863                 bezt->vec[0][0] += offset;
864                 bezt->vec[1][0] += offset;
865                 bezt->vec[2][0] += offset;
866                 
867                 /* insert the keyframe
868                  * NOTE: we do not want to inherit handles from existing keyframes in this case!
869                  */
870                 
871                 insert_bezt_fcurve(fcu, bezt, INSERTKEY_OVERWRITE_FULL);
872                 
873                 /* un-apply offset from src beztriple after copying */
874                 bezt->vec[0][0] -= offset;
875                 bezt->vec[1][0] -= offset;
876                 bezt->vec[2][0] -= offset;
877                 
878                 if (flip)
879                         do_curve_mirror_flippping(aci, bezt);
880         }
881         
882         /* recalculate F-Curve's handles? */
883         calchandles_fcurve(fcu);
884 }
885
886 /* ------------------- */
887
888 EnumPropertyItem keyframe_paste_offset_items[] = {
889         {KEYFRAME_PASTE_OFFSET_CFRA_START, "START", 0, "Frame Start", "Paste keys starting at current frame"},
890         {KEYFRAME_PASTE_OFFSET_CFRA_END, "END", 0, "Frame End", "Paste keys ending at current frame"},
891         {KEYFRAME_PASTE_OFFSET_CFRA_RELATIVE, "RELATIVE", 0, "Frame Relative", "Paste keys relative to the current frame when copying"},
892         {KEYFRAME_PASTE_OFFSET_NONE, "NONE", 0, "No Offset", "Paste keys from original time"},
893         {0, NULL, 0, NULL, NULL}};
894
895 EnumPropertyItem keyframe_paste_merge_items[] = {
896         {KEYFRAME_PASTE_MERGE_MIX, "MIX", 0, "Mix", "Overlay existing with new keys"},
897         {KEYFRAME_PASTE_MERGE_OVER, "OVER_ALL", 0, "Overwrite All", "Replace all keys"},
898         {KEYFRAME_PASTE_MERGE_OVER_RANGE, "OVER_RANGE", 0, "Overwrite Range", "Overwrite keys in pasted range"},
899         {KEYFRAME_PASTE_MERGE_OVER_RANGE_ALL, "OVER_RANGE_ALL", 0, "Overwrite Entire Range", "Overwrite keys in pasted range, using the range of all copied keys"},
900         {0, NULL, 0, NULL, NULL}};
901
902
903 /**
904  * This function pastes data from the keyframes copy/paste buffer
905  *
906  * \return Status code is whether the method FAILED to do anything
907  */
908 short paste_animedit_keys(bAnimContext *ac, ListBase *anim_data,
909                           const eKeyPasteOffset offset_mode, const eKeyMergeMode merge_mode, bool flip)
910 {
911         bAnimListElem *ale;
912         
913         const Scene *scene = (ac->scene);
914         
915         const bool from_single = BLI_listbase_is_single(&animcopybuf);
916         const bool to_simple = BLI_listbase_is_single(anim_data);
917         
918         float offset = 0.0f;
919         int pass;
920
921         /* check if buffer is empty */
922         if (BLI_listbase_is_empty(&animcopybuf)) {
923                 BKE_report(ac->reports, RPT_ERROR, "No animation data in buffer to paste");
924                 return -1;
925         }
926
927         if (BLI_listbase_is_empty(anim_data)) {
928                 BKE_report(ac->reports, RPT_ERROR, "No selected F-Curves to paste into");
929                 return -1;
930         }
931         
932         /* mathods of offset */
933         switch (offset_mode) {
934                 case KEYFRAME_PASTE_OFFSET_CFRA_START:
935                         offset = (float)(CFRA - animcopy_firstframe);
936                         break;
937                 case KEYFRAME_PASTE_OFFSET_CFRA_END:
938                         offset = (float)(CFRA - animcopy_lastframe);
939                         break;
940                 case KEYFRAME_PASTE_OFFSET_CFRA_RELATIVE:
941                         offset = (float)(CFRA - animcopy_cfra);
942                         break;
943                 case KEYFRAME_PASTE_OFFSET_NONE:
944                         offset = 0.0f;
945                         break;
946         }
947
948         if (from_single && to_simple) {
949                 /* 1:1 match, no tricky checking, just paste */
950                 FCurve *fcu;
951                 tAnimCopybufItem *aci;
952                 
953                 ale = anim_data->first;
954                 fcu = (FCurve *)ale->data;  /* destination F-Curve */
955                 aci = animcopybuf.first;
956                 
957                 paste_animedit_keys_fcurve(fcu, aci, offset, merge_mode, false);
958                 ale->update |= ANIM_UPDATE_DEFAULT;
959         }
960         else {
961                 /* from selected channels 
962                  *  This "passes" system aims to try to find "matching" channels to paste keyframes
963                  *  into with increasingly loose matching heuristics. The process finishes when at least
964                  *  one F-Curve has been pasted into.
965                  */
966                 for (pass = 0; pass < 3; pass++) {
967                         unsigned int totmatch = 0;
968                         
969                         for (ale = anim_data->first; ale; ale = ale->next) {
970                                 /* find buffer item to paste from 
971                                  *      - if names don't matter (i.e. only 1 channel in buffer), don't check id/group
972                                  *      - if names do matter, only check if id-type is ok for now (group check is not that important)
973                                  *      - most importantly, rna-paths should match (array indices are unimportant for now)
974                                  */
975                                 AnimData *adt = ANIM_nla_mapping_get(ac, ale);
976                                 FCurve *fcu = (FCurve *)ale->data;  /* destination F-Curve */
977                                 tAnimCopybufItem *aci = NULL;
978                                 
979                                 switch (pass) {
980                                         case 0:
981                                                 /* most strict, must be exact path match data_path & index */
982                                                 aci = pastebuf_match_path_full(fcu, from_single, to_simple, flip);
983                                                 break;
984                                         
985                                         case 1:
986                                                 /* less strict, just compare property names */
987                                                 aci = pastebuf_match_path_property(fcu, from_single, to_simple);
988                                                 break;
989                                         
990                                         case 2:
991                                                 /* Comparing properties gave no results, so just do index comparisons */
992                                                 aci = pastebuf_match_index_only(fcu, from_single, to_simple);
993                                                 break;
994                                 }
995                                 
996                                 /* copy the relevant data from the matching buffer curve */
997                                 if (aci) {
998                                         totmatch++;
999                                         
1000                                         if (adt) {
1001                                                 ANIM_nla_mapping_apply_fcurve(adt, ale->key_data, 0, 1);
1002                                                 paste_animedit_keys_fcurve(fcu, aci, offset, merge_mode, flip);
1003                                                 ANIM_nla_mapping_apply_fcurve(adt, ale->key_data, 1, 1);
1004                                         }
1005                                         else {
1006                                                 paste_animedit_keys_fcurve(fcu, aci, offset, merge_mode, flip);
1007                                         }
1008                                 }
1009                                 
1010                                 ale->update |= ANIM_UPDATE_DEFAULT;
1011                         }
1012                         
1013                         /* don't continue if some fcurves were pasted */
1014                         if (totmatch)
1015                                 break;
1016                 }
1017         }
1018         
1019         ANIM_animdata_update(ac, anim_data);
1020
1021         return 0;
1022 }
1023
1024 /* **************************************************** */