Own TODO item: sculpting on constructive modifiers
[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         float y1, y2, y3;               /* averaged before/new/after y-values */
283 } tSmooth_Bezt;
284
285 /* Use a weighted moving-means method to reduce intensity of fluctuations */
286 // TODO: introduce scaling factor for weighting falloff
287 void smooth_fcurve (FCurve *fcu)
288 {
289         BezTriple *bezt;
290         int i, x, totSel = 0;
291         
292         /* first loop through - count how many verts are selected */
293         bezt= fcu->bezt;
294         for (i=0; i < fcu->totvert; i++, bezt++) {                                              
295                 if (BEZSELECTED(bezt))
296                         totSel++;
297         }
298         
299         /* if any points were selected, allocate tSmooth_Bezt points to work on */
300         if (totSel >= 3) {
301                 tSmooth_Bezt *tarray, *tsb;
302                 
303                 /* allocate memory in one go */
304                 tsb= tarray= MEM_callocN(totSel*sizeof(tSmooth_Bezt), "tSmooth_Bezt Array");
305                 
306                 /* populate tarray with data of selected points */
307                 bezt= fcu->bezt;
308                 for (i=0, x=0; (i < fcu->totvert) && (x < totSel); i++, bezt++) {
309                         if (BEZSELECTED(bezt)) {
310                                 /* tsb simply needs pointer to vec, and index */
311                                 tsb->h1 = &bezt->vec[0][1];
312                                 tsb->h2 = &bezt->vec[1][1];
313                                 tsb->h3 = &bezt->vec[2][1];
314                                 
315                                 /* advance to the next tsb to populate */
316                                 if (x < totSel-1) 
317                                         tsb++;
318                                 else
319                                         break;
320                         }
321                 }
322                         
323                 /* calculate the new smoothed F-Curve's with weighted averages:
324                  *      - this is done with two passes to avoid progressive corruption errors
325                  *      - uses 5 points for each operation (which stores in the relevant handles)
326                  *      -       previous: w/a ratio = 3:5:2:1:1
327                  *      -       next: w/a ratio = 1:1:2:5:3
328                  */
329                 
330                 /* round 1: calculate smoothing deltas and new values */ 
331                 tsb= tarray;
332                 for (i=0; i < totSel; i++, tsb++) {
333                         /* don't touch end points (otherwise, curves slowly explode, as we don't have enough data there) */
334                         if (ELEM(i, 0, (totSel-1)) == 0) {
335                                 const tSmooth_Bezt *tP1 = tsb - 1;
336                                 const tSmooth_Bezt *tP2 = (i-2 > 0) ? (tsb - 2) : (NULL);
337                                 const tSmooth_Bezt *tN1 = tsb + 1;
338                                 const tSmooth_Bezt *tN2 = (i+2 < totSel) ? (tsb + 2) : (NULL);
339                                 
340                                 const float p1 = *tP1->h2;
341                                 const float p2 = (tP2) ? (*tP2->h2) : (*tP1->h2);
342                                 const float c1 = *tsb->h2;
343                                 const float n1 = *tN1->h2;
344                                 const float n2 = (tN2) ? (*tN2->h2) : (*tN1->h2);
345                                 
346                                 /* calculate previous and next, then new position by averaging these */
347                                 tsb->y1= (3*p2 + 5*p1 + 2*c1 + n1 + n2) / 12;
348                                 tsb->y3= (p2 + p1 + 2*c1 + 5*n1 + 3*n2) / 12;
349                                 
350                                 tsb->y2 = (tsb->y1 + tsb->y3) / 2;
351                         }
352                 }
353                 
354                 /* round 2: apply new values */
355                 tsb= tarray;
356                 for (i=0; i < totSel; i++, tsb++) {
357                         /* don't touch end points, as their values were't touched above */
358                         if (ELEM(i, 0, (totSel-1)) == 0) {
359                                 /* y2 takes the average of the 2 points */
360                                 *tsb->h2 = tsb->y2;
361                                 
362                                 /* handles are weighted between their original values and the averaged values */
363                                 *tsb->h1 = ((*tsb->h1) * 0.7f) + (tsb->y1 * 0.3f); 
364                                 *tsb->h3 = ((*tsb->h3) * 0.7f) + (tsb->y3 * 0.3f);
365                         }
366                 }
367                 
368                 /* free memory required for tarray */
369                 MEM_freeN(tarray);
370         }
371         
372         /* recalculate handles */
373         calchandles_fcurve(fcu);
374 }
375
376 /* ---------------- */
377
378 /* little cache for values... */
379 typedef struct tempFrameValCache {
380         float frame, val;
381 } tempFrameValCache;
382
383
384 /* Evaluates the curves between each selected keyframe on each frame, and keys the value  */
385 void sample_fcurve (FCurve *fcu)
386 {
387         BezTriple *bezt, *start=NULL, *end=NULL;
388         tempFrameValCache *value_cache, *fp;
389         int sfra, range;
390         int i, n, nIndex;
391
392         if (fcu->bezt==NULL) /* ignore baked */
393                 return;
394         
395         /* find selected keyframes... once pair has been found, add keyframes  */
396         for (i=0, bezt=fcu->bezt; i < fcu->totvert; i++, bezt++) {
397                 /* check if selected, and which end this is */
398                 if (BEZSELECTED(bezt)) {
399                         if (start) {
400                                 /* set end */
401                                 end= bezt;
402                                 
403                                 /* cache values then add keyframes using these values, as adding
404                                  * keyframes while sampling will affect the outcome...
405                                  *      - only start sampling+adding from index=1, so that we don't overwrite original keyframe
406                                  */
407                                 range= (int)( ceil(end->vec[1][0] - start->vec[1][0]) );
408                                 sfra= (int)( floor(start->vec[1][0]) );
409                                 
410                                 if (range) {
411                                         value_cache= MEM_callocN(sizeof(tempFrameValCache)*range, "IcuFrameValCache");
412                                         
413                                         /*      sample values   */
414                                         for (n=1, fp=value_cache; n<range && fp; n++, fp++) {
415                                                 fp->frame= (float)(sfra + n);
416                                                 fp->val= evaluate_fcurve(fcu, fp->frame);
417                                         }
418                                         
419                                         /*      add keyframes with these, tagging as 'breakdowns'       */
420                                         for (n=1, fp=value_cache; n<range && fp; n++, fp++) {
421                                                 nIndex= insert_vert_fcurve(fcu, fp->frame, fp->val, 1);
422                                                 BEZKEYTYPE(fcu->bezt + nIndex)= BEZT_KEYTYPE_BREAKDOWN;
423                                         }
424                                         
425                                         /* free temp cache */
426                                         MEM_freeN(value_cache);
427                                         
428                                         /* as we added keyframes, we need to compensate so that bezt is at the right place */
429                                         bezt = fcu->bezt + i + range - 1;
430                                         i += (range - 1);
431                                 }
432                                 
433                                 /* bezt was selected, so it now marks the start of a whole new chain to search */
434                                 start= bezt;
435                                 end= NULL;
436                         }
437                         else {
438                                 /* just set start keyframe */
439                                 start= bezt;
440                                 end= NULL;
441                         }
442                 }
443         }
444         
445         /* recalculate channel's handles? */
446         calchandles_fcurve(fcu);
447 }
448
449 /* **************************************************** */
450 /* Copy/Paste Tools */
451 /* - The copy/paste buffer currently stores a set of temporary F-Curves containing only the keyframes 
452  *   that were selected in each of the original F-Curves
453  * - All pasted frames are offset by the same amount. This is calculated as the difference in the times of
454  *      the current frame and the 'first keyframe' (i.e. the earliest one in all channels).
455  * - The earliest frame is calculated per copy operation.
456  */
457
458 /* globals for copy/paste data (like for other copy/paste buffers) */
459 static ListBase animcopybuf = {NULL, NULL};
460 static float animcopy_firstframe= 999999999.0f;
461 static float animcopy_lastframe= -999999999.0f;
462 static float animcopy_cfra= 0.0;
463
464 /* datatype for use in copy/paste buffer */
465 typedef struct tAnimCopybufItem {
466         struct tAnimCopybufItem *next, *prev;
467         
468         ID *id;                         /* ID which owns the curve */
469         bActionGroup *grp;      /* Action Group */
470         char *rna_path;         /* RNA-Path */
471         int array_index;        /* array index */
472         
473         int totvert;            /* number of keyframes stored for this channel */
474         BezTriple *bezt;        /* keyframes in buffer */
475
476         short id_type;          /* Result of GS(id->name)*/
477 } tAnimCopybufItem;
478
479
480 /* This function frees any MEM_calloc'ed copy/paste buffer data */
481 // XXX find some header to put this in!
482 void free_anim_copybuf (void)
483 {
484         tAnimCopybufItem *aci, *acn;
485         
486         /* free each buffer element */
487         for (aci= animcopybuf.first; aci; aci= acn) {
488                 acn= aci->next;
489                 
490                 /* free keyframes */
491                 if (aci->bezt) 
492                         MEM_freeN(aci->bezt);
493                         
494                 /* free RNA-path */
495                 if (aci->rna_path)
496                         MEM_freeN(aci->rna_path);
497                         
498                 /* free ourself */
499                 BLI_freelinkN(&animcopybuf, aci);
500         }
501         
502         /* restore initial state */
503         animcopybuf.first= animcopybuf.last= NULL;
504         animcopy_firstframe= 999999999.0f;
505         animcopy_lastframe= -999999999.0f;
506 }
507
508 /* ------------------- */
509
510 /* This function adds data to the keyframes copy/paste buffer, freeing existing data first */
511 short copy_animedit_keys (bAnimContext *ac, ListBase *anim_data)
512 {       
513         bAnimListElem *ale;
514         Scene *scene= ac->scene;
515         
516         /* clear buffer first */
517         free_anim_copybuf();
518         
519         /* assume that each of these is an F-Curve */
520         for (ale= anim_data->first; ale; ale= ale->next) {
521                 FCurve *fcu= (FCurve *)ale->key_data;
522                 tAnimCopybufItem *aci;
523                 BezTriple *bezt, *nbezt, *newbuf;
524                 int i;
525                 
526                 /* firstly, check if F-Curve has any selected keyframes
527                  *      - skip if no selected keyframes found (so no need to create unnecessary copy-buffer data)
528                  *      - this check should also eliminate any problems associated with using sample-data
529                  */
530                 if (ANIM_fcurve_keyframes_loop(NULL, fcu, NULL, ANIM_editkeyframes_ok(BEZT_OK_SELECTED), NULL) == 0)
531                         continue;
532                 
533                 /* init copybuf item info */
534                 aci= MEM_callocN(sizeof(tAnimCopybufItem), "AnimCopybufItem");
535                 aci->id= ale->id;
536                 aci->id_type= GS(ale->id->name);
537                 aci->grp= fcu->grp;
538                 aci->rna_path= MEM_dupallocN(fcu->rna_path);
539                 aci->array_index= fcu->array_index;
540                 BLI_addtail(&animcopybuf, aci);
541                 
542                 /* add selected keyframes to buffer */
543                 // 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
544                 for (i=0, bezt=fcu->bezt; i < fcu->totvert; i++, bezt++) {
545                         if (BEZSELECTED(bezt)) {
546                                 /* add to buffer */
547                                 newbuf= MEM_callocN(sizeof(BezTriple)*(aci->totvert+1), "copybuf beztriple");
548                                 
549                                 /* assume that since we are just resizing the array, just copy all existing data across */
550                                 if (aci->bezt)
551                                         memcpy(newbuf, aci->bezt, sizeof(BezTriple)*(aci->totvert));
552                                 
553                                 /* copy current beztriple across too */
554                                 nbezt= &newbuf[aci->totvert];
555                                 *nbezt= *bezt;
556                                 
557                                 /* ensure copy buffer is selected so pasted keys are selected */
558                                 BEZ_SEL(nbezt);
559                                 
560                                 /* free old array and set the new */
561                                 if (aci->bezt) MEM_freeN(aci->bezt);
562                                 aci->bezt= newbuf;
563                                 aci->totvert++;
564                                 
565                                 /* check if this is the earliest frame encountered so far */
566                                 if (bezt->vec[1][0] < animcopy_firstframe)
567                                         animcopy_firstframe= bezt->vec[1][0];
568                                 if (bezt->vec[1][0] > animcopy_lastframe)
569                                         animcopy_lastframe= bezt->vec[1][0];
570                         }
571                 }
572                 
573         }
574         
575         /* check if anything ended up in the buffer */
576         if (ELEM(NULL, animcopybuf.first, animcopybuf.last))
577                 return -1;
578
579         /* incase 'relative' paste method is used */
580         animcopy_cfra= CFRA;
581
582         /* everything went fine */
583         return 0;
584 }
585
586 /* ------------------- */
587
588 /* most strict method: exact matches only */
589 static tAnimCopybufItem *pastebuf_match_path_full(FCurve *fcu, const short from_single, const short to_simple)
590 {
591         tAnimCopybufItem *aci;
592
593         for (aci= animcopybuf.first; aci; aci= aci->next) {
594                 /* check that paths exist */
595                 if (to_simple || (aci->rna_path && fcu->rna_path)) {
596                         if (to_simple || (strcmp(aci->rna_path, fcu->rna_path) == 0)) {
597                                 if ((from_single) || (aci->array_index == fcu->array_index))
598                                         break;
599                         }
600                 }
601         }
602
603         return aci;
604 }
605
606 /* medium match strictness: path match only (i.e. ignore ID) */
607 static tAnimCopybufItem *pastebuf_match_path_property(FCurve *fcu, const short from_single, const short UNUSED(to_simple))
608 {
609         tAnimCopybufItem *aci;
610
611         for (aci= animcopybuf.first; aci; aci= aci->next) {
612                 /* check that paths exist */
613                 if (aci->rna_path && fcu->rna_path) {
614                         /* find the property of the fcurve and compare against the end of the tAnimCopybufItem
615                          * more involved since it needs to to path lookups.
616                          * This is not 100% reliable since the user could be editing the curves on a path that wont
617                          * resolve, or a bone could be renamed after copying for eg. but in normal copy & paste
618                          * this should work out ok. 
619                          */
620                         if (BLI_findindex(which_libbase(G.main, aci->id_type), aci->id) == -1) {
621                                 /* pedantic but the ID could have been removed, and beats crashing! */
622                                 printf("paste_animedit_keys: error ID has been removed!\n");
623                         }
624                         else {
625                                 PointerRNA id_ptr, rptr;
626                                 PropertyRNA *prop;
627                                 
628                                 RNA_id_pointer_create(aci->id, &id_ptr);
629                                 RNA_path_resolve(&id_ptr, aci->rna_path, &rptr, &prop);
630                                 
631                                 if (prop) {
632                                         const char *identifier= RNA_property_identifier(prop);
633                                         int len_id = strlen(identifier);
634                                         int len_path = strlen(fcu->rna_path);
635                                         if (len_id <= len_path) {
636                                                 /* note, paths which end with "] will fail with this test - Animated ID Props */
637                                                 if (strcmp(identifier, fcu->rna_path + (len_path-len_id))==0) {
638                                                         if ((from_single) || (aci->array_index == fcu->array_index))
639                                                                 break;
640                                                 }
641                                         }
642                                 }
643                                 else {
644                                         printf("paste_animedit_keys: failed to resolve path id:%s, '%s'!\n", aci->id->name, aci->rna_path);
645                                 }
646                         }
647                 }
648         }
649
650         return aci;
651 }
652
653 /* least strict matching heuristic: indices only */
654 static tAnimCopybufItem *pastebuf_match_index_only(FCurve *fcu, const short from_single, const short UNUSED(to_simple))
655 {
656         tAnimCopybufItem *aci;
657
658         for (aci= animcopybuf.first; aci; aci= aci->next) {
659                 /* check that paths exist */
660                 if ((from_single) || (aci->array_index == fcu->array_index)) {
661                         break;
662                 }
663         }
664
665         return aci;
666 }
667
668 /* ................ */
669
670 /* helper for paste_animedit_keys() - performs the actual pasting */
671 static void paste_animedit_keys_fcurve(FCurve *fcu, tAnimCopybufItem *aci, float offset, const eKeyMergeMode merge_mode)
672 {
673         BezTriple *bezt;
674         int i;
675
676         /* First de-select existing FCuvre */
677         for (i=0, bezt=fcu->bezt; i < fcu->totvert; i++, bezt++) {
678                 bezt->f2 &= ~SELECT;
679         }
680
681         /* mix mode with existing data */
682         switch (merge_mode) {
683                 case KEYFRAME_PASTE_MERGE_MIX:
684                         /* do-nothing */
685                         break;
686                         
687                 case KEYFRAME_PASTE_MERGE_OVER:
688                         /* remove all keys */
689                         clear_fcurve_keys(fcu);
690                         break;
691                         
692                 case KEYFRAME_PASTE_MERGE_OVER_RANGE:
693                 case KEYFRAME_PASTE_MERGE_OVER_RANGE_ALL:
694                 {
695                         float f_min;
696                         float f_max;
697                         
698                         if (merge_mode==KEYFRAME_PASTE_MERGE_OVER_RANGE) {
699                                 f_min= aci->bezt[0].vec[1][0] + offset;
700                                 f_max= aci->bezt[aci->totvert-1].vec[1][0] + offset;
701                         }
702                         else { /* Entire Range */
703                                 f_min= animcopy_firstframe + offset;
704                                 f_max= animcopy_lastframe + offset;
705                         }
706                         
707                         /* remove keys in range */
708                         if (f_min < f_max) {
709                                 /* select verts in range for removal */
710                                 for (i=0, bezt=fcu->bezt; i < fcu->totvert; i++, bezt++) {
711                                         if ((f_min < bezt[0].vec[1][0]) && (bezt[0].vec[1][0] < f_max)) {
712                                                 bezt->f2 |= SELECT;
713                                         }
714                                 }
715                                 
716                                 /* remove frames in the range */
717                                 delete_fcurve_keys(fcu);
718                         }
719                         break;
720                 }
721         }
722         
723         /* just start pasting, with the the first keyframe on the current frame, and so on */
724         for (i=0, bezt=aci->bezt; i < aci->totvert; i++, bezt++) {                                              
725                 /* temporarily apply offset to src beztriple while copying */
726                 bezt->vec[0][0] += offset;
727                 bezt->vec[1][0] += offset;
728                 bezt->vec[2][0] += offset;
729                 
730                 /* insert the keyframe
731                  * NOTE: no special flags here for now
732                  */
733                 insert_bezt_fcurve(fcu, bezt, 0); 
734                 
735                 /* un-apply offset from src beztriple after copying */
736                 bezt->vec[0][0] -= offset;
737                 bezt->vec[1][0] -= offset;
738                 bezt->vec[2][0] -= offset;
739         }
740         
741         /* recalculate F-Curve's handles? */
742         calchandles_fcurve(fcu);
743 }
744
745 /* ------------------- */
746
747 EnumPropertyItem keyframe_paste_offset_items[] = {
748         {KEYFRAME_PASTE_OFFSET_CFRA_START, "START", 0, "Frame Start", "Paste keys starting at current frame"},
749         {KEYFRAME_PASTE_OFFSET_CFRA_END, "END", 0, "Frame End", "Paste keys ending at current frame"},
750         {KEYFRAME_PASTE_OFFSET_CFRA_RELATIVE, "RELATIVE", 0, "Frame Relative", "Paste keys relative to the current frame when copying"},
751         {KEYFRAME_PASTE_OFFSET_NONE, "NONE", 0, "No Offset", "Paste keys from original time"},
752         {0, NULL, 0, NULL, NULL}};
753
754 EnumPropertyItem keyframe_paste_merge_items[] = {
755         {KEYFRAME_PASTE_MERGE_MIX, "MIX", 0, "Mix", "Overlay existing with new keys"},
756         {KEYFRAME_PASTE_MERGE_OVER, "OVER_ALL", 0, "Overwrite All", "Replace all keys"},
757         {KEYFRAME_PASTE_MERGE_OVER_RANGE, "OVER_RANGE", 0, "Overwrite Range", "Overwrite keys in pasted range"},
758         {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."},
759         {0, NULL, 0, NULL, NULL}};
760
761
762 /* This function pastes data from the keyframes copy/paste buffer */
763 short paste_animedit_keys (bAnimContext *ac, ListBase *anim_data,
764                         const eKeyPasteOffset offset_mode, const eKeyMergeMode merge_mode)
765 {
766         bAnimListElem *ale;
767         
768         const Scene *scene= (ac->scene);
769         
770         const short from_single= (animcopybuf.first == animcopybuf.last);
771         const short to_simple= (anim_data->first == anim_data->last);
772         
773         float offset = 0.0f;
774         int pass;
775
776         /* check if buffer is empty */
777         if (animcopybuf.first == NULL) {
778                 BKE_report(ac->reports, RPT_WARNING, "No data in buffer to paste");
779                 return -1;
780         }
781
782         if (anim_data->first == NULL) {
783                 BKE_report(ac->reports, RPT_WARNING, "No FCurves to paste into");
784                 return -1;
785         }
786         
787         /* mathods of offset */
788         switch(offset_mode) {
789                 case KEYFRAME_PASTE_OFFSET_CFRA_START:
790                         offset= (float)(CFRA - animcopy_firstframe);
791                         break;
792                 case KEYFRAME_PASTE_OFFSET_CFRA_END:
793                         offset= (float)(CFRA - animcopy_lastframe);
794                         break;
795                 case KEYFRAME_PASTE_OFFSET_CFRA_RELATIVE:
796                         offset= (float)(CFRA - animcopy_cfra);
797                         break;
798                 case KEYFRAME_PASTE_OFFSET_NONE:
799                         offset= 0.0f;
800                         break;
801         }
802
803         if (from_single && to_simple) {
804                 /* 1:1 match, no tricky checking, just paste */
805                 FCurve *fcu;
806                 tAnimCopybufItem *aci;
807                 
808                 ale= anim_data->first;
809                 fcu= (FCurve *)ale->data;               /* destination F-Curve */
810                 aci= animcopybuf.first;
811                 
812                 paste_animedit_keys_fcurve(fcu, aci, offset, merge_mode);
813         }
814         else {
815                 /* from selected channels 
816                  *      This "passes" system aims to try to find "matching" channels to paste keyframes
817                  *      into with increasingly loose matching heuristics. The process finishes when at least
818                  *      one F-Curve has been pasted into.
819                  */
820                 for (pass= 0; pass < 3; pass++) {
821                         unsigned int totmatch= 0;
822                         
823                         for (ale= anim_data->first; ale; ale= ale->next) {
824                                 /* find buffer item to paste from 
825                                  *      - if names don't matter (i.e. only 1 channel in buffer), don't check id/group
826                                  *      - if names do matter, only check if id-type is ok for now (group check is not that important)
827                                  *      - most importantly, rna-paths should match (array indices are unimportant for now)
828                                  */
829                                 FCurve *fcu = (FCurve *)ale->data;              /* destination F-Curve */
830                                 tAnimCopybufItem *aci= NULL;
831                                 
832                                 switch (pass) {
833                                         case 0:
834                                                 /* most strict, must be exact path match data_path & index */
835                                                 aci= pastebuf_match_path_full(fcu, from_single, to_simple);
836                                                 break;
837                                         
838                                         case 1:
839                                                 /* less strict, just compare property names */
840                                                 aci= pastebuf_match_path_property(fcu, from_single, to_simple);
841                                                 break;
842                                         
843                                         case 2:
844                                                 /* Comparing properties gave no results, so just do index comparisons */
845                                                 aci= pastebuf_match_index_only(fcu, from_single, to_simple);
846                                                 break;
847                                 }
848                                 
849                                 /* copy the relevant data from the matching buffer curve */
850                                 if (aci) {
851                                         totmatch++;
852                                         paste_animedit_keys_fcurve(fcu, aci, offset, merge_mode);
853                                 }
854                         }
855                         
856                         /* dont continue if some fcurves were pasted */
857                         if (totmatch)
858                                 break;
859                 }
860         }
861         
862         return 0;
863 }
864
865 /* **************************************************** */