doxygen: blender/editors tagged.
[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 /** \file blender/editors/animation/keyframes_general.c
29  *  \ingroup edanimation
30  */
31
32
33 #include <stdlib.h>
34 #include <string.h>
35 #include <math.h>
36 #include <float.h>
37
38 #include "MEM_guardedalloc.h"
39
40 #include "BLI_blenlib.h"
41 #include "BLI_math.h"
42 #include "BLI_utildefines.h"
43
44 #include "DNA_anim_types.h"
45 #include "DNA_object_types.h"
46 #include "DNA_scene_types.h"
47
48
49 #include "BKE_fcurve.h"
50 #include "BKE_utildefines.h"
51 #include "BKE_report.h"
52 #include "BKE_library.h"
53 #include "BKE_global.h"
54
55 #include "RNA_access.h"
56 #include "RNA_enum_types.h"
57
58 #include "ED_anim_api.h"
59 #include "ED_keyframing.h"
60 #include "ED_keyframes_edit.h"
61
62 /* This file contains code for various keyframe-editing tools which are 'destructive'
63  * (i.e. they will modify the order of the keyframes, and change the size of the array).
64  * While some of these tools may eventually be moved out into blenkernel, for now, it is
65  * fine to have these calls here.
66  * 
67  * There are also a few tools here which cannot be easily coded for in the other system (yet).
68  * These may also be moved around at some point, but for now, they are best added here.
69  *
70  * - Joshua Leung, Dec 2008
71  */
72  
73 /* **************************************************** */
74
75 /* Only delete the nominated keyframe from provided F-Curve. 
76  * Not recommended to be used many times successively. For that
77  * there is delete_fcurve_keys(). 
78  */
79 void delete_fcurve_key(FCurve *fcu, int index, short do_recalc)
80 {
81         /* sanity check */
82         if (fcu == NULL) 
83                 return;
84                 
85         /* verify the index:
86          *      1) cannot be greater than the number of available keyframes
87          *      2) negative indices are for specifying a value from the end of the array
88          */
89         if (abs(index) >= fcu->totvert)
90                 return;
91         else if (index < 0)
92                 index += fcu->totvert;
93         
94         /* Delete this keyframe */
95         memmove(&fcu->bezt[index], &fcu->bezt[index+1], sizeof(BezTriple)*(fcu->totvert-index-1));
96         fcu->totvert--;
97
98         if (fcu->totvert == 0) {
99                 if (fcu->bezt)
100                         MEM_freeN(fcu->bezt);
101                 fcu->bezt= NULL;
102         }
103         
104         /* recalc handles - only if it won't cause problems */
105         if (do_recalc)
106                 calchandles_fcurve(fcu);
107 }
108
109 /* Delete selected keyframes in given F-Curve */
110 void delete_fcurve_keys(FCurve *fcu)
111 {
112         int i;
113         
114         if(fcu->bezt==NULL) /* ignore baked curves */
115                 return;
116     
117         /* Delete selected BezTriples */
118         for (i=0; i < fcu->totvert; i++) {
119                 if (fcu->bezt[i].f2 & SELECT) {
120                         memmove(&fcu->bezt[i], &fcu->bezt[i+1], sizeof(BezTriple)*(fcu->totvert-i-1));
121                         fcu->totvert--;
122                         i--;
123                 }
124         }
125         
126         /* Free the array of BezTriples if there are not keyframes */
127         if(fcu->totvert == 0)
128                 clear_fcurve_keys(fcu);
129 }
130
131
132 void clear_fcurve_keys(FCurve *fcu)
133 {
134         if (fcu->bezt)
135                 MEM_freeN(fcu->bezt);
136         fcu->bezt= NULL;
137
138         fcu->totvert= 0;
139 }
140
141 /* ---------------- */
142
143 /* duplicate selected keyframes for the given F-Curve */
144 void duplicate_fcurve_keys(FCurve *fcu)
145 {
146         BezTriple *newbezt;
147         int i;
148         
149         /* this can only work when there is an F-Curve, and also when there are some BezTriples */
150         if ELEM(NULL, fcu, fcu->bezt)
151                 return;
152         
153         for (i=0; i < fcu->totvert; i++) {
154                 /* If a key is selected */
155                 if (fcu->bezt[i].f2 & SELECT) {
156                         /* Expand the list */
157                         newbezt = MEM_callocN(sizeof(BezTriple) * (fcu->totvert+1), "beztriple");
158                         
159                         memcpy(newbezt, fcu->bezt, sizeof(BezTriple) * (i+1));
160                         memcpy(newbezt+i+1, fcu->bezt+i, sizeof(BezTriple));
161                         memcpy(newbezt+i+2, fcu->bezt+i+1, sizeof (BezTriple) *(fcu->totvert-(i+1)));
162                         fcu->totvert++;
163                         
164                         /* reassign pointers... (free old, and add new) */
165                         MEM_freeN(fcu->bezt);
166                         fcu->bezt=newbezt;
167                         
168                         /* Unselect the current key */
169                         BEZ_DESEL(&fcu->bezt[i]);
170                         i++;
171                         
172                         /* Select the copied key */
173                         BEZ_SEL(&fcu->bezt[i]);
174                 }
175         }
176 }
177
178 /* **************************************************** */
179 /* Various Tools */
180
181 /* Basic F-Curve 'cleanup' function that removes 'double points' and unnecessary keyframes on linear-segments only */
182 void clean_fcurve(FCurve *fcu, float thresh)
183 {
184         BezTriple *old_bezts, *bezt, *beztn;
185         BezTriple *lastb;
186         int totCount, i;
187         
188         /* check if any points  */
189         if ((fcu == NULL) || (fcu->totvert <= 1)) 
190                 return;
191         
192         /* make a copy of the old BezTriples, and clear IPO curve */
193         old_bezts = fcu->bezt;
194         totCount = fcu->totvert;        
195         fcu->bezt = NULL;
196         fcu->totvert = 0;
197         
198         /* now insert first keyframe, as it should be ok */
199         bezt = old_bezts;
200         insert_vert_fcurve(fcu, bezt->vec[1][0], bezt->vec[1][1], 0);
201         
202         /* Loop through BezTriples, comparing them. Skip any that do 
203          * not fit the criteria for "ok" points.
204          */
205         for (i=1; i<totCount; i++) {    
206                 float prev[2], cur[2], next[2];
207                 
208                 /* get BezTriples and their values */
209                 if (i < (totCount - 1)) {
210                         beztn = (old_bezts + (i+1));
211                         next[0]= beztn->vec[1][0]; next[1]= beztn->vec[1][1];
212                 }
213                 else {
214                         beztn = NULL;
215                         next[0] = next[1] = 0.0f;
216                 }
217                 lastb= (fcu->bezt + (fcu->totvert - 1));
218                 bezt= (old_bezts + i);
219                 
220                 /* get references for quicker access */
221                 prev[0] = lastb->vec[1][0]; prev[1] = lastb->vec[1][1];
222                 cur[0] = bezt->vec[1][0]; cur[1] = bezt->vec[1][1];
223                 
224                 /* check if current bezt occurs at same time as last ok */
225                 if (IS_EQT(cur[0], prev[0], thresh)) {
226                         /* If there is a next beztriple, and if occurs at the same time, only insert 
227                          * if there is a considerable distance between the points, and also if the 
228                          * current is further away than the next one is to the previous.
229                          */
230                         if (beztn && (IS_EQT(cur[0], next[0], thresh)) && 
231                                 (IS_EQT(next[1], prev[1], thresh)==0)) 
232                         {
233                                 /* only add if current is further away from previous */
234                                 if (cur[1] > next[1]) {
235                                         if (IS_EQT(cur[1], prev[1], thresh) == 0) {
236                                                 /* add new keyframe */
237                                                 insert_vert_fcurve(fcu, cur[0], cur[1], 0);
238                                         }
239                                 }
240                         }
241                         else {
242                                 /* only add if values are a considerable distance apart */
243                                 if (IS_EQT(cur[1], prev[1], thresh) == 0) {
244                                         /* add new keyframe */
245                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
246                                 }
247                         }
248                 }
249                 else {
250                         /* checks required are dependent on whether this is last keyframe or not */
251                         if (beztn) {
252                                 /* does current have same value as previous and next? */
253                                 if (IS_EQT(cur[1], prev[1], thresh) == 0) {
254                                         /* add new keyframe*/
255                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
256                                 }
257                                 else if (IS_EQT(cur[1], next[1], thresh) == 0) {
258                                         /* add new keyframe */
259                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
260                                 }
261                         }
262                         else {  
263                                 /* add if value doesn't equal that of previous */
264                                 if (IS_EQT(cur[1], prev[1], thresh) == 0) {
265                                         /* add new keyframe */
266                                         insert_vert_fcurve(fcu, cur[0], cur[1], 0);
267                                 }
268                         }
269                 }
270         }
271         
272         /* now free the memory used by the old BezTriples */
273         if (old_bezts)
274                 MEM_freeN(old_bezts);
275 }
276
277 /* ---------------- */
278
279 /* temp struct used for smooth_fcurve */
280 typedef struct tSmooth_Bezt {
281         float *h1, *h2, *h3;    /* bezt->vec[0,1,2][1] */
282 } tSmooth_Bezt;
283
284 /* Use a weighted moving-means method to reduce intensity of fluctuations */
285 void smooth_fcurve (FCurve *fcu)
286 {
287         BezTriple *bezt;
288         int i, x, totSel = 0;
289         
290         /* first loop through - count how many verts are selected, and fix up handles 
291          *      this is done for both modes
292          */
293         bezt= fcu->bezt;
294         for (i=0; i < fcu->totvert; i++, bezt++) {                                              
295                 if (BEZSELECTED(bezt)) {                                                        
296                         /* line point's handles up with point's vertical position */
297                         bezt->vec[0][1]= bezt->vec[2][1]= bezt->vec[1][1];
298                         if ((bezt->h1==HD_AUTO) || (bezt->h1==HD_VECT)) bezt->h1= HD_ALIGN;
299                         if ((bezt->h2==HD_AUTO) || (bezt->h2==HD_VECT)) bezt->h2= HD_ALIGN;
300                         
301                         /* add value to total */
302                         totSel++;
303                 }
304         }
305         
306         /* if any points were selected, allocate tSmooth_Bezt points to work on */
307         if (totSel >= 3) {
308                 tSmooth_Bezt *tarray, *tsb;
309                 
310                 /* allocate memory in one go */
311                 tsb= tarray= MEM_callocN(totSel*sizeof(tSmooth_Bezt), "tSmooth_Bezt Array");
312                 
313                 /* populate tarray with data of selected points */
314                 bezt= fcu->bezt;
315                 for (i=0, x=0; (i < fcu->totvert) && (x < totSel); i++, bezt++) {
316                         if (BEZSELECTED(bezt)) {
317                                 /* tsb simply needs pointer to vec, and index */
318                                 tsb->h1 = &bezt->vec[0][1];
319                                 tsb->h2 = &bezt->vec[1][1];
320                                 tsb->h3 = &bezt->vec[2][1];
321                                 
322                                 /* advance to the next tsb to populate */
323                                 if (x < totSel- 1) 
324                                         tsb++;
325                                 else
326                                         break;
327                         }
328                 }
329                         
330                 /* calculate the new smoothed F-Curve's with weighted averages:
331                  *      - this is done with two passes to avoid progressive corruption errors
332                  *      - uses 5 points for each operation (which stores in the relevant handles)
333                  *      -       previous: w/a ratio = 3:5:2:1:1
334                  *      -       next: w/a ratio = 1:1:2:5:3
335                  */
336                 
337                 /* round 1: calculate previous and next */ 
338                 tsb= tarray;
339                 for (i=0; i < totSel; i++, tsb++) {
340                         /* don't touch end points (otherwise, curves slowly explode) */
341                         if (ELEM(i, 0, (totSel-1)) == 0) {
342                                 const tSmooth_Bezt *tP1 = tsb - 1;
343                                 const tSmooth_Bezt *tP2 = (i-2 > 0) ? (tsb - 2) : (NULL);
344                                 const tSmooth_Bezt *tN1 = tsb + 1;
345                                 const tSmooth_Bezt *tN2 = (i+2 < totSel) ? (tsb + 2) : (NULL);
346                                 
347                                 const float p1 = *tP1->h2;
348                                 const float p2 = (tP2) ? (*tP2->h2) : (*tP1->h2);
349                                 const float c1 = *tsb->h2;
350                                 const float n1 = *tN1->h2;
351                                 const float n2 = (tN2) ? (*tN2->h2) : (*tN1->h2);
352                                 
353                                 /* calculate previous and next */
354                                 *tsb->h1= (3*p2 + 5*p1 + 2*c1 + n1 + n2) / 12;
355                                 *tsb->h3= (p2 + p1 + 2*c1 + 5*n1 + 3*n2) / 12;
356                         }
357                 }
358                 
359                 /* round 2: calculate new values and reset handles */
360                 tsb= tarray;
361                 for (i=0; i < totSel; i++, tsb++) {
362                         /* calculate new position by averaging handles */
363                         *tsb->h2 = (*tsb->h1 + *tsb->h3) / 2;
364                         
365                         /* reset handles now */
366                         *tsb->h1 = *tsb->h2;
367                         *tsb->h3 = *tsb->h2;
368                 }
369                 
370                 /* free memory required for tarray */
371                 MEM_freeN(tarray);
372         }
373         
374         /* recalculate handles */
375         calchandles_fcurve(fcu);
376 }
377
378 /* ---------------- */
379
380 /* little cache for values... */
381 typedef struct tempFrameValCache {
382         float frame, val;
383 } tempFrameValCache;
384
385
386 /* Evaluates the curves between each selected keyframe on each frame, and keys the value  */
387 void sample_fcurve (FCurve *fcu)
388 {
389         BezTriple *bezt, *start=NULL, *end=NULL;
390         tempFrameValCache *value_cache, *fp;
391         int sfra, range;
392         int i, n, nIndex;
393
394         if (fcu->bezt==NULL) /* ignore baked */
395                 return;
396         
397         /* find selected keyframes... once pair has been found, add keyframes  */
398         for (i=0, bezt=fcu->bezt; i < fcu->totvert; i++, bezt++) {
399                 /* check if selected, and which end this is */
400                 if (BEZSELECTED(bezt)) {
401                         if (start) {
402                                 /* set end */
403                                 end= bezt;
404                                 
405                                 /* cache values then add keyframes using these values, as adding
406                                  * keyframes while sampling will affect the outcome...
407                                  *      - only start sampling+adding from index=1, so that we don't overwrite original keyframe
408                                  */
409                                 range= (int)( ceil(end->vec[1][0] - start->vec[1][0]) );
410                                 sfra= (int)( floor(start->vec[1][0]) );
411                                 
412                                 if (range) {
413                                         value_cache= MEM_callocN(sizeof(tempFrameValCache)*range, "IcuFrameValCache");
414                                         
415                                         /*      sample values   */
416                                         for (n=1, fp=value_cache; n<range && fp; n++, fp++) {
417                                                 fp->frame= (float)(sfra + n);
418                                                 fp->val= evaluate_fcurve(fcu, fp->frame);
419                                         }
420                                         
421                                         /*      add keyframes with these, tagging as 'breakdowns'       */
422                                         for (n=1, fp=value_cache; n<range && fp; n++, fp++) {
423                                                 nIndex= insert_vert_fcurve(fcu, fp->frame, fp->val, 1);
424                                                 BEZKEYTYPE(fcu->bezt + nIndex)= BEZT_KEYTYPE_BREAKDOWN;
425                                         }
426                                         
427                                         /* free temp cache */
428                                         MEM_freeN(value_cache);
429                                         
430                                         /* as we added keyframes, we need to compensate so that bezt is at the right place */
431                                         bezt = fcu->bezt + i + range - 1;
432                                         i += (range - 1);
433                                 }
434                                 
435                                 /* bezt was selected, so it now marks the start of a whole new chain to search */
436                                 start= bezt;
437                                 end= NULL;
438                         }
439                         else {
440                                 /* just set start keyframe */
441                                 start= bezt;
442                                 end= NULL;
443                         }
444                 }
445         }
446         
447         /* recalculate channel's handles? */
448         calchandles_fcurve(fcu);
449 }
450
451 /* **************************************************** */
452 /* Copy/Paste Tools */
453 /* - The copy/paste buffer currently stores a set of temporary F-Curves containing only the keyframes 
454  *   that were selected in each of the original F-Curves
455  * - All pasted frames are offset by the same amount. This is calculated as the difference in the times of
456  *      the current frame and the 'first keyframe' (i.e. the earliest one in all channels).
457  * - The earliest frame is calculated per copy operation.
458  */
459
460 /* globals for copy/paste data (like for other copy/paste buffers) */
461 static ListBase animcopybuf = {NULL, NULL};
462 static float animcopy_firstframe= 999999999.0f;
463 static float animcopy_lastframe= -999999999.0f;
464 static float animcopy_cfra= 0.0;
465
466 /* datatype for use in copy/paste buffer */
467 typedef struct tAnimCopybufItem {
468         struct tAnimCopybufItem *next, *prev;
469         
470         ID *id;                         /* ID which owns the curve */
471         bActionGroup *grp;      /* Action Group */
472         char *rna_path;         /* RNA-Path */
473         int array_index;        /* array index */
474         
475         int totvert;            /* number of keyframes stored for this channel */
476         BezTriple *bezt;        /* keyframes in buffer */
477
478         short id_type;          /* Result of GS(id->name)*/
479 } tAnimCopybufItem;
480
481
482 /* This function frees any MEM_calloc'ed copy/paste buffer data */
483 // XXX find some header to put this in!
484 void free_anim_copybuf (void)
485 {
486         tAnimCopybufItem *aci, *acn;
487         
488         /* free each buffer element */
489         for (aci= animcopybuf.first; aci; aci= acn) {
490                 acn= aci->next;
491                 
492                 /* free keyframes */
493                 if (aci->bezt) 
494                         MEM_freeN(aci->bezt);
495                         
496                 /* free RNA-path */
497                 if (aci->rna_path)
498                         MEM_freeN(aci->rna_path);
499                         
500                 /* free ourself */
501                 BLI_freelinkN(&animcopybuf, aci);
502         }
503         
504         /* restore initial state */
505         animcopybuf.first= animcopybuf.last= NULL;
506         animcopy_firstframe= 999999999.0f;
507         animcopy_lastframe= -999999999.0f;
508 }
509
510 /* ------------------- */
511
512 /* This function adds data to the keyframes copy/paste buffer, freeing existing data first */
513 short copy_animedit_keys (bAnimContext *ac, ListBase *anim_data)
514 {       
515         bAnimListElem *ale;
516         Scene *scene= ac->scene;
517         
518         /* clear buffer first */
519         free_anim_copybuf();
520         
521         /* assume that each of these is an F-Curve */
522         for (ale= anim_data->first; ale; ale= ale->next) {
523                 FCurve *fcu= (FCurve *)ale->key_data;
524                 tAnimCopybufItem *aci;
525                 BezTriple *bezt, *nbezt, *newbuf;
526                 int i;
527                 
528                 /* firstly, check if F-Curve has any selected keyframes
529                  *      - skip if no selected keyframes found (so no need to create unnecessary copy-buffer data)
530                  *      - this check should also eliminate any problems associated with using sample-data
531                  */
532                 if (ANIM_fcurve_keyframes_loop(NULL, fcu, NULL, ANIM_editkeyframes_ok(BEZT_OK_SELECTED), NULL) == 0)
533                         continue;
534                 
535                 /* init copybuf item info */
536                 aci= MEM_callocN(sizeof(tAnimCopybufItem), "AnimCopybufItem");
537                 aci->id= ale->id;
538                 aci->id_type= GS(ale->id->name);
539                 aci->grp= fcu->grp;
540                 aci->rna_path= MEM_dupallocN(fcu->rna_path);
541                 aci->array_index= fcu->array_index;
542                 BLI_addtail(&animcopybuf, aci);
543                 
544                 /* add selected keyframes to buffer */
545                 // 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
546                 for (i=0, bezt=fcu->bezt; i < fcu->totvert; i++, bezt++) {
547                         if (BEZSELECTED(bezt)) {
548                                 /* add to buffer */
549                                 newbuf= MEM_callocN(sizeof(BezTriple)*(aci->totvert+1), "copybuf beztriple");
550                                 
551                                 /* assume that since we are just resizing the array, just copy all existing data across */
552                                 if (aci->bezt)
553                                         memcpy(newbuf, aci->bezt, sizeof(BezTriple)*(aci->totvert));
554                                 
555                                 /* copy current beztriple across too */
556                                 nbezt= &newbuf[aci->totvert];
557                                 *nbezt= *bezt;
558                                 
559                                 /* ensure copy buffer is selected so pasted keys are selected */
560                                 BEZ_SEL(nbezt);
561                                 
562                                 /* free old array and set the new */
563                                 if (aci->bezt) MEM_freeN(aci->bezt);
564                                 aci->bezt= newbuf;
565                                 aci->totvert++;
566                                 
567                                 /* check if this is the earliest frame encountered so far */
568                                 if (bezt->vec[1][0] < animcopy_firstframe)
569                                         animcopy_firstframe= bezt->vec[1][0];
570                                 if (bezt->vec[1][0] > animcopy_lastframe)
571                                         animcopy_lastframe= bezt->vec[1][0];
572                         }
573                 }
574                 
575         }
576         
577         /* check if anything ended up in the buffer */
578         if (ELEM(NULL, animcopybuf.first, animcopybuf.last))
579                 return -1;
580
581         /* incase 'relative' paste method is used */
582         animcopy_cfra= CFRA;
583
584         /* everything went fine */
585         return 0;
586 }
587
588 /* ------------------- */
589
590 /* most strict method: exact matches only */
591 static tAnimCopybufItem *pastebuf_match_path_full(FCurve *fcu, const short from_single, const short to_simple)
592 {
593         tAnimCopybufItem *aci;
594
595         for (aci= animcopybuf.first; aci; aci= aci->next) {
596                 /* check that paths exist */
597                 if (to_simple || (aci->rna_path && fcu->rna_path)) {
598                         if (to_simple || (strcmp(aci->rna_path, fcu->rna_path) == 0)) {
599                                 if ((from_single) || (aci->array_index == fcu->array_index))
600                                         break;
601                         }
602                 }
603         }
604
605         return aci;
606 }
607
608 /* medium match strictness: path match only (i.e. ignore ID) */
609 static tAnimCopybufItem *pastebuf_match_path_property(FCurve *fcu, const short from_single, const short UNUSED(to_simple))
610 {
611         tAnimCopybufItem *aci;
612
613         for (aci= animcopybuf.first; aci; aci= aci->next) {
614                 /* check that paths exist */
615                 if (aci->rna_path && fcu->rna_path) {
616                         /* find the property of the fcurve and compare against the end of the tAnimCopybufItem
617                          * more involved since it needs to to path lookups.
618                          * This is not 100% reliable since the user could be editing the curves on a path that wont
619                          * resolve, or a bone could be renamed after copying for eg. but in normal copy & paste
620                          * this should work out ok. 
621                          */
622                         if (BLI_findindex(which_libbase(G.main, aci->id_type), aci->id) == -1) {
623                                 /* pedantic but the ID could have been removed, and beats crashing! */
624                                 printf("paste_animedit_keys: error ID has been removed!\n");
625                         }
626                         else {
627                                 PointerRNA id_ptr, rptr;
628                                 PropertyRNA *prop;
629                                 
630                                 RNA_id_pointer_create(aci->id, &id_ptr);
631                                 RNA_path_resolve(&id_ptr, aci->rna_path, &rptr, &prop);
632                                 
633                                 if (prop) {
634                                         const char *identifier= RNA_property_identifier(prop);
635                                         int len_id = strlen(identifier);
636                                         int len_path = strlen(fcu->rna_path);
637                                         if (len_id <= len_path) {
638                                                 /* note, paths which end with "] will fail with this test - Animated ID Props */
639                                                 if (strcmp(identifier, fcu->rna_path + (len_path-len_id))==0) {
640                                                         if ((from_single) || (aci->array_index == fcu->array_index))
641                                                                 break;
642                                                 }
643                                         }
644                                 }
645                                 else {
646                                         printf("paste_animedit_keys: failed to resolve path id:%s, '%s'!\n", aci->id->name, aci->rna_path);
647                                 }
648                         }
649                 }
650         }
651
652         return aci;
653 }
654
655 /* least strict matching heuristic: indices only */
656 static tAnimCopybufItem *pastebuf_match_index_only(FCurve *fcu, const short from_single, const short UNUSED(to_simple))
657 {
658         tAnimCopybufItem *aci;
659
660         for (aci= animcopybuf.first; aci; aci= aci->next) {
661                 /* check that paths exist */
662                 if ((from_single) || (aci->array_index == fcu->array_index)) {
663                         break;
664                 }
665         }
666
667         return aci;
668 }
669
670 /* ................ */
671
672 /* helper for paste_animedit_keys() - performs the actual pasting */
673 static void paste_animedit_keys_fcurve(FCurve *fcu, tAnimCopybufItem *aci, float offset, const eKeyMergeMode merge_mode)
674 {
675         BezTriple *bezt;
676         int i;
677
678         /* First de-select existing FCuvre */
679         for (i=0, bezt=fcu->bezt; i < fcu->totvert; i++, bezt++) {
680                 bezt->f2 &= ~SELECT;
681         }
682
683         /* mix mode with existing data */
684         switch (merge_mode) {
685                 case KEYFRAME_PASTE_MERGE_MIX:
686                         /* do-nothing */
687                         break;
688                         
689                 case KEYFRAME_PASTE_MERGE_OVER:
690                         /* remove all keys */
691                         clear_fcurve_keys(fcu);
692                         break;
693                         
694                 case KEYFRAME_PASTE_MERGE_OVER_RANGE:
695                 case KEYFRAME_PASTE_MERGE_OVER_RANGE_ALL:
696                 {
697                         float f_min;
698                         float f_max;
699                         
700                         if (merge_mode==KEYFRAME_PASTE_MERGE_OVER_RANGE) {
701                                 f_min= aci->bezt[0].vec[1][0] + offset;
702                                 f_max= aci->bezt[aci->totvert-1].vec[1][0] + offset;
703                         }
704                         else { /* Entire Range */
705                                 f_min= animcopy_firstframe + offset;
706                                 f_max= animcopy_lastframe + offset;
707                         }
708                         
709                         /* remove keys in range */
710                         if (f_min < f_max) {
711                                 /* select verts in range for removal */
712                                 for (i=0, bezt=fcu->bezt; i < fcu->totvert; i++, bezt++) {
713                                         if ((f_min < bezt[0].vec[1][0]) && (bezt[0].vec[1][0] < f_max)) {
714                                                 bezt->f2 |= SELECT;
715                                         }
716                                 }
717                                 
718                                 /* remove frames in the range */
719                                 delete_fcurve_keys(fcu);
720                         }
721                         break;
722                 }
723         }
724         
725         /* just start pasting, with the the first keyframe on the current frame, and so on */
726         for (i=0, bezt=aci->bezt; i < aci->totvert; i++, bezt++) {                                              
727                 /* temporarily apply offset to src beztriple while copying */
728                 bezt->vec[0][0] += offset;
729                 bezt->vec[1][0] += offset;
730                 bezt->vec[2][0] += offset;
731                 
732                 /* insert the keyframe
733                  * NOTE: no special flags here for now
734                  */
735                 insert_bezt_fcurve(fcu, bezt, 0); 
736                 
737                 /* un-apply offset from src beztriple after copying */
738                 bezt->vec[0][0] -= offset;
739                 bezt->vec[1][0] -= offset;
740                 bezt->vec[2][0] -= offset;
741         }
742         
743         /* recalculate F-Curve's handles? */
744         calchandles_fcurve(fcu);
745 }
746
747 /* ------------------- */
748
749 EnumPropertyItem keyframe_paste_offset_items[] = {
750         {KEYFRAME_PASTE_OFFSET_CFRA_START, "START", 0, "Frame Start", "Paste keys starting at current frame"},
751         {KEYFRAME_PASTE_OFFSET_CFRA_END, "END", 0, "Frame End", "Paste keys ending at current frame"},
752         {KEYFRAME_PASTE_OFFSET_CFRA_RELATIVE, "RELATIVE", 0, "Frame Relative", "Paste keys relative to the current frame when copying"},
753         {KEYFRAME_PASTE_OFFSET_NONE, "NONE", 0, "No Offset", "Paste keys from original time"},
754         {0, NULL, 0, NULL, NULL}};
755
756 EnumPropertyItem keyframe_paste_merge_items[] = {
757         {KEYFRAME_PASTE_MERGE_MIX, "MIX", 0, "Mix", "Overlay existing with new keys"},
758         {KEYFRAME_PASTE_MERGE_OVER, "OVER_ALL", 0, "Overwrite All", "Replace all keys"},
759         {KEYFRAME_PASTE_MERGE_OVER_RANGE, "OVER_RANGE", 0, "Overwrite Range", "Overwrite keys in pasted range"},
760         {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."},
761         {0, NULL, 0, NULL, NULL}};
762
763
764 /* This function pastes data from the keyframes copy/paste buffer */
765 short paste_animedit_keys (bAnimContext *ac, ListBase *anim_data,
766                         const eKeyPasteOffset offset_mode, const eKeyMergeMode merge_mode)
767 {
768         bAnimListElem *ale;
769         
770         const Scene *scene= (ac->scene);
771         
772         const short from_single= (animcopybuf.first == animcopybuf.last);
773         const short to_simple= (anim_data->first == anim_data->last);
774         
775         float offset = 0.0f;
776         int pass;
777
778         /* check if buffer is empty */
779         if (animcopybuf.first == NULL) {
780                 BKE_report(ac->reports, RPT_WARNING, "No data in buffer to paste");
781                 return -1;
782         }
783
784         if (anim_data->first == NULL) {
785                 BKE_report(ac->reports, RPT_WARNING, "No FCurves to paste into");
786                 return -1;
787         }
788         
789         /* mathods of offset */
790         switch(offset_mode) {
791                 case KEYFRAME_PASTE_OFFSET_CFRA_START:
792                         offset= (float)(CFRA - animcopy_firstframe);
793                         break;
794                 case KEYFRAME_PASTE_OFFSET_CFRA_END:
795                         offset= (float)(CFRA - animcopy_lastframe);
796                         break;
797                 case KEYFRAME_PASTE_OFFSET_CFRA_RELATIVE:
798                         offset= (float)(CFRA - animcopy_cfra);
799                         break;
800                 case KEYFRAME_PASTE_OFFSET_NONE:
801                         offset= 0.0f;
802                         break;
803         }
804
805         if (from_single && to_simple) {
806                 /* 1:1 match, no tricky checking, just paste */
807                 FCurve *fcu;
808                 tAnimCopybufItem *aci;
809                 
810                 ale= anim_data->first;
811                 fcu= (FCurve *)ale->data;               /* destination F-Curve */
812                 aci= animcopybuf.first;
813                 
814                 paste_animedit_keys_fcurve(fcu, aci, offset, merge_mode);
815         }
816         else {
817                 /* from selected channels 
818                  *      This "passes" system aims to try to find "matching" channels to paste keyframes
819                  *      into with increasingly loose matching heuristics. The process finishes when at least
820                  *      one F-Curve has been pasted into.
821                  */
822                 for (pass= 0; pass < 3; pass++) {
823                         unsigned int totmatch= 0;
824                         
825                         for (ale= anim_data->first; ale; ale= ale->next) {
826                                 /* find buffer item to paste from 
827                                  *      - if names don't matter (i.e. only 1 channel in buffer), don't check id/group
828                                  *      - if names do matter, only check if id-type is ok for now (group check is not that important)
829                                  *      - most importantly, rna-paths should match (array indices are unimportant for now)
830                                  */
831                                 FCurve *fcu = (FCurve *)ale->data;              /* destination F-Curve */
832                                 tAnimCopybufItem *aci= NULL;
833                                 
834                                 switch (pass) {
835                                         case 0:
836                                                 /* most strict, must be exact path match data_path & index */
837                                                 aci= pastebuf_match_path_full(fcu, from_single, to_simple);
838                                                 break;
839                                         
840                                         case 1:
841                                                 /* less strict, just compare property names */
842                                                 aci= pastebuf_match_path_property(fcu, from_single, to_simple);
843                                                 break;
844                                         
845                                         case 2:
846                                                 /* Comparing properties gave no results, so just do index comparisons */
847                                                 aci= pastebuf_match_index_only(fcu, from_single, to_simple);
848                                                 break;
849                                 }
850                                 
851                                 /* copy the relevant data from the matching buffer curve */
852                                 if (aci) {
853                                         totmatch++;
854                                         paste_animedit_keys_fcurve(fcu, aci, offset, merge_mode);
855                                 }
856                         }
857                         
858                         /* dont continue if some fcurves were pasted */
859                         if (totmatch)
860                                 break;
861                 }
862         }
863         
864         return 0;
865 }
866
867 /* **************************************************** */