Driver Editing Tweaks:
[blender.git] / source / blender / blenkernel / intern / fcurve.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): Joshua Leung (full recode)
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29  
30
31 #include <math.h>
32 #include <stdio.h>
33 #include <stddef.h>
34 #include <string.h>
35 #include <float.h>
36
37 #ifdef HAVE_CONFIG_H
38 #include <config.h>
39 #endif
40
41 #include "MEM_guardedalloc.h"
42
43 #include "DNA_anim_types.h"
44
45 #include "BLI_blenlib.h"
46 #include "BLI_math.h"
47 #include "BLI_noise.h"
48
49 #include "BKE_fcurve.h"
50 #include "BKE_curve.h" 
51 #include "BKE_global.h"
52 #include "BKE_idprop.h"
53 #include "BKE_utildefines.h"
54
55 #include "RNA_access.h"
56 #include "RNA_types.h"
57
58 #ifndef DISABLE_PYTHON
59 #include "BPY_extern.h" 
60 #endif
61
62 #define SMALL -1.0e-10
63 #define SELECT 1
64
65 /* ************************** Data-Level Functions ************************* */
66
67 /* ---------------------- Freeing --------------------------- */
68
69 /* Frees the F-Curve itself too, so make sure BLI_remlink is called before calling this... */
70 void free_fcurve (FCurve *fcu) 
71 {
72         if (fcu == NULL) 
73                 return;
74         
75         /* free curve data */
76         if (fcu) {
77                 if (fcu->bezt) MEM_freeN(fcu->bezt);
78                 if (fcu->fpt) MEM_freeN(fcu->fpt);
79         }
80         
81         /* free RNA-path, as this were allocated when getting the path string */
82         if (fcu->rna_path)
83                 MEM_freeN(fcu->rna_path);
84         
85         /* free extra data - i.e. modifiers, and driver */
86         fcurve_free_driver(fcu);
87         free_fmodifiers(&fcu->modifiers);
88         
89         /* free f-curve itself */
90         MEM_freeN(fcu);
91 }
92
93 /* Frees a list of F-Curves */
94 void free_fcurves (ListBase *list)
95 {
96         FCurve *fcu, *fcn;
97         
98         /* sanity check */
99         if (list == NULL)
100                 return;
101                 
102         /* free data - no need to call remlink before freeing each curve, 
103          * as we store reference to next, and freeing only touches the curve
104          * it's given
105          */
106         for (fcu= list->first; fcu; fcu= fcn) {
107                 fcn= fcu->next;
108                 free_fcurve(fcu);
109         }
110         
111         /* clear pointers just in case */
112         list->first= list->last= NULL;
113 }       
114
115 /* ---------------------- Copy --------------------------- */
116
117 /* duplicate an F-Curve */
118 FCurve *copy_fcurve (FCurve *fcu)
119 {
120         FCurve *fcu_d;
121         
122         /* sanity check */
123         if (fcu == NULL)
124                 return NULL;
125                 
126         /* make a copy */
127         fcu_d= MEM_dupallocN(fcu);
128         
129         fcu_d->next= fcu_d->prev= NULL;
130         fcu_d->grp= NULL;
131         
132         /* copy curve data */
133         fcu_d->bezt= MEM_dupallocN(fcu_d->bezt);
134         fcu_d->fpt= MEM_dupallocN(fcu_d->fpt);
135         
136         /* copy rna-path */
137         fcu_d->rna_path= MEM_dupallocN(fcu_d->rna_path);
138         
139         /* copy driver */
140         fcu_d->driver= fcurve_copy_driver(fcu_d->driver);
141         
142         /* copy modifiers */
143         copy_fmodifiers(&fcu_d->modifiers, &fcu->modifiers);
144         
145         /* return new data */
146         return fcu_d;
147 }
148
149 /* duplicate a list of F-Curves */
150 void copy_fcurves (ListBase *dst, ListBase *src)
151 {
152         FCurve *dfcu, *sfcu;
153         
154         /* sanity checks */
155         if ELEM(NULL, dst, src)
156                 return;
157         
158         /* clear destination list first */
159         dst->first= dst->last= NULL;
160         
161         /* copy one-by-one */
162         for (sfcu= src->first; sfcu; sfcu= sfcu->next) {
163                 dfcu= copy_fcurve(sfcu);
164                 BLI_addtail(dst, dfcu);
165         }
166 }
167
168 /* ---------------------- Relink --------------------------- */
169
170 #if 0
171 /* uses id->newid to match pointers with other copied data 
172  *      - called after single-user or other such
173  */
174                         if (icu->driver)
175                                 ID_NEW(icu->driver->ob);
176 #endif
177
178 /* --------------------- Finding -------------------------- */
179
180 /* Find the F-Curve affecting the given RNA-access path + index, in the list of F-Curves provided */
181 FCurve *list_find_fcurve (ListBase *list, const char rna_path[], const int array_index)
182 {
183         FCurve *fcu;
184         
185         /* sanity checks */
186         if ( ELEM(NULL, list, rna_path) || (array_index < 0) )
187                 return NULL;
188         
189         /* check paths of curves, then array indices... */
190         for (fcu= list->first; fcu; fcu= fcu->next) {
191                 /* simple string-compare (this assumes that they have the same root...) */
192                 if (fcu->rna_path && !strcmp(fcu->rna_path, rna_path)) {
193                         /* now check indicies */
194                         if (fcu->array_index == array_index)
195                                 return fcu;
196                 }
197         }
198         
199         /* return */
200         return NULL;
201 }
202
203 /* threshold for binary-searching keyframes - threshold here should be good enough for now, but should become userpref */
204 #define BEZT_BINARYSEARCH_THRESH        0.00001f
205
206 /* Binary search algorithm for finding where to insert BezTriple. (for use by insert_bezt_fcurve)
207  * Returns the index to insert at (data already at that index will be offset if replace is 0)
208  */
209 int binarysearch_bezt_index (BezTriple array[], float frame, int arraylen, short *replace)
210 {
211         int start=0, end=arraylen;
212         int loopbreaker= 0, maxloop= arraylen * 2;
213         
214         /* initialise replace-flag first */
215         *replace= 0;
216         
217         /* sneaky optimisations (don't go through searching process if...):
218          *      - keyframe to be added is to be added out of current bounds
219          *      - keyframe to be added would replace one of the existing ones on bounds
220          */
221         if ((arraylen <= 0) || (array == NULL)) {
222                 printf("Warning: binarysearch_bezt_index() encountered invalid array \n");
223                 return 0;
224         }
225         else {
226                 /* check whether to add before/after/on */
227                 float framenum;
228                 
229                 /* 'First' Keyframe (when only one keyframe, this case is used) */
230                 framenum= array[0].vec[1][0];
231                 if (IS_EQT(frame, framenum, BEZT_BINARYSEARCH_THRESH)) {
232                         *replace = 1;
233                         return 0;
234                 }
235                 else if (frame < framenum)
236                         return 0;
237                         
238                 /* 'Last' Keyframe */
239                 framenum= array[(arraylen-1)].vec[1][0];
240                 if (IS_EQT(frame, framenum, BEZT_BINARYSEARCH_THRESH)) {
241                         *replace= 1;
242                         return (arraylen - 1);
243                 }
244                 else if (frame > framenum)
245                         return arraylen;
246         }
247         
248         
249         /* most of the time, this loop is just to find where to put it
250          * 'loopbreaker' is just here to prevent infinite loops 
251          */
252         for (loopbreaker=0; (start <= end) && (loopbreaker < maxloop); loopbreaker++) {
253                 /* compute and get midpoint */
254                 int mid = start + ((end - start) / 2);  /* we calculate the midpoint this way to avoid int overflows... */
255                 float midfra= array[mid].vec[1][0];
256                 
257                 /* check if exactly equal to midpoint */
258                 if (IS_EQT(frame, midfra, BEZT_BINARYSEARCH_THRESH)) {
259                         *replace = 1;
260                         return mid;
261                 }
262                 
263                 /* repeat in upper/lower half */
264                 if (frame > midfra)
265                         start= mid + 1;
266                 else if (frame < midfra)
267                         end= mid - 1;
268         }
269         
270         /* print error if loop-limit exceeded */
271         if (loopbreaker == (maxloop-1)) {
272                 printf("Error: binarysearch_bezt_index() was taking too long \n");
273                 
274                 // include debug info 
275                 printf("\tround = %d: start = %d, end = %d, arraylen = %d \n", loopbreaker, start, end, arraylen);
276         }
277         
278         /* not found, so return where to place it */
279         return start;
280 }
281
282 /* Calculate the extents of F-Curve's data */
283 void calc_fcurve_bounds (FCurve *fcu, float *xmin, float *xmax, float *ymin, float *ymax)
284 {
285         float xminv=999999999.0f, xmaxv=-999999999.0f;
286         float yminv=999999999.0f, ymaxv=-999999999.0f;
287         short foundvert=0;
288         unsigned int i;
289         
290         if (fcu->totvert) {
291                 if (fcu->bezt) {
292                         /* frame range can be directly calculated from end verts */
293                         if (xmin || xmax) {
294                                 xminv= MIN2(xminv, fcu->bezt[0].vec[1][0]);
295                                 xmaxv= MAX2(xmaxv, fcu->bezt[fcu->totvert-1].vec[1][0]);
296                         }
297                         
298                         /* only loop over keyframes to find extents for values if needed */
299                         if (ymin || ymax) {
300                                 BezTriple *bezt;
301                                 
302                                 for (bezt=fcu->bezt, i=0; i < fcu->totvert; bezt++, i++) {
303                                         if (bezt->vec[1][1] < yminv)
304                                                 yminv= bezt->vec[1][1];
305                                         if (bezt->vec[1][1] > ymaxv)
306                                                 ymaxv= bezt->vec[1][1];
307                                 }
308                         }
309                 }
310                 else if (fcu->fpt) {
311                         /* frame range can be directly calculated from end verts */
312                         if (xmin || xmax) {
313                                 xminv= MIN2(xminv, fcu->fpt[0].vec[0]);
314                                 xmaxv= MAX2(xmaxv, fcu->fpt[fcu->totvert-1].vec[0]);
315                         }
316                         
317                         /* only loop over keyframes to find extents for values if needed */
318                         if (ymin || ymax) {
319                                 FPoint *fpt;
320                                 
321                                 for (fpt=fcu->fpt, i=0; i < fcu->totvert; fpt++, i++) {
322                                         if (fpt->vec[1] < yminv)
323                                                 yminv= fpt->vec[1];
324                                         if (fpt->vec[1] > ymaxv)
325                                                 ymaxv= fpt->vec[1];
326                                 }
327                         }
328                 }
329                 
330                 foundvert=1;
331         }
332         
333         /* minimum sizes are 1.0f */
334         if (foundvert) {
335                 if (xminv == xmaxv) xmaxv += 1.0f;
336                 if (yminv == ymaxv) ymaxv += 1.0f;
337                 
338                 if (xmin) *xmin= xminv;
339                 if (xmax) *xmax= xmaxv;
340                 
341                 if (ymin) *ymin= yminv;
342                 if (ymax) *ymax= ymaxv;
343         }
344         else {
345                 if (xmin) *xmin= 0.0f;
346                 if (xmax) *xmax= 0.0f;
347                 
348                 if (ymin) *ymin= 1.0f;
349                 if (ymax) *ymax= 1.0f;
350         }
351 }
352
353 /* Calculate the extents of F-Curve's keyframes */
354 void calc_fcurve_range (FCurve *fcu, float *start, float *end)
355 {
356         float min=999999999.0f, max=-999999999.0f;
357         short foundvert=0;
358
359         if (fcu->totvert) {
360                 if (fcu->bezt) {
361                         min= MIN2(min, fcu->bezt[0].vec[1][0]);
362                         max= MAX2(max, fcu->bezt[fcu->totvert-1].vec[1][0]);
363                 }
364                 else if (fcu->fpt) {
365                         min= MIN2(min, fcu->fpt[0].vec[0]);
366                         max= MAX2(max, fcu->fpt[fcu->totvert-1].vec[0]);
367                 }
368                 
369                 foundvert=1;
370         }
371         
372         /* minimum length is 1 frame */
373         if (foundvert) {
374                 if (min == max) max += 1.0f;
375                 *start= min;
376                 *end= max;
377         }
378         else {
379                 *start= 0.0f;
380                 *end= 1.0f;
381         }
382 }
383
384 /* ***************************** Keyframe Column Tools ********************************* */
385
386 /* add a BezTriple to a column */
387 void bezt_add_to_cfra_elem (ListBase *lb, BezTriple *bezt)
388 {
389         CfraElem *ce, *cen;
390         
391         for (ce= lb->first; ce; ce= ce->next) {
392                 /* double key? */
393                 if (ce->cfra == bezt->vec[1][0]) {
394                         if (bezt->f2 & SELECT) ce->sel= bezt->f2;
395                         return;
396                 }
397                 /* should key be inserted before this column? */
398                 else if (ce->cfra > bezt->vec[1][0]) break;
399         }
400         
401         /* create a new column */
402         cen= MEM_callocN(sizeof(CfraElem), "add_to_cfra_elem"); 
403         if (ce) BLI_insertlinkbefore(lb, ce, cen);
404         else BLI_addtail(lb, cen);
405
406         cen->cfra= bezt->vec[1][0];
407         cen->sel= bezt->f2;
408 }
409
410 /* ***************************** Samples Utilities ******************************* */
411 /* Some utilities for working with FPoints (i.e. 'sampled' animation curve data, such as
412  * data imported from BVH/Mocap files), which are specialised for use with high density datasets,
413  * which BezTriples/Keyframe data are ill equipped to do.
414  */
415  
416  
417 /* Basic sampling callback which acts as a wrapper for evaluate_fcurve() 
418  *      'data' arg here is unneeded here...
419  */
420 float fcurve_samplingcb_evalcurve (FCurve *fcu, void *data, float evaltime)
421 {
422         /* assume any interference from drivers on the curve is intended... */
423         return evaluate_fcurve(fcu, evaltime);
424
425
426  
427 /* Main API function for creating a set of sampled curve data, given some callback function 
428  * used to retrieve the values to store.
429  */
430 void fcurve_store_samples (FCurve *fcu, void *data, int start, int end, FcuSampleFunc sample_cb)
431 {
432         FPoint *fpt, *new_fpt;
433         int cfra;
434         
435         /* sanity checks */
436         // TODO: make these tests report errors using reports not printf's
437         if ELEM(NULL, fcu, sample_cb) {
438                 printf("Error: No F-Curve with F-Curve Modifiers to Bake\n");
439                 return;
440         }
441         if (start >= end) {
442                 printf("Error: Frame range for Sampled F-Curve creation is inappropriate \n");
443                 return;
444         }
445         
446         /* set up sample data */
447         fpt= new_fpt= MEM_callocN(sizeof(FPoint)*(end-start+1), "FPoint Samples");
448         
449         /* use the sampling callback at 1-frame intervals from start to end frames */
450         for (cfra= start; cfra <= end; cfra++, fpt++) {
451                 fpt->vec[0]= (float)cfra;
452                 fpt->vec[1]= sample_cb(fcu, data, (float)cfra);
453         }
454         
455         /* free any existing sample/keyframe data on curve  */
456         if (fcu->bezt) MEM_freeN(fcu->bezt);
457         if (fcu->fpt) MEM_freeN(fcu->fpt);
458         
459         /* store the samples */
460         fcu->bezt= NULL;
461         fcu->fpt= new_fpt;
462         fcu->totvert= end - start + 1;
463 }
464
465 /* ***************************** F-Curve Sanity ********************************* */
466 /* The functions here are used in various parts of Blender, usually after some editing
467  * of keyframe data has occurred. They ensure that keyframe data is properly ordered and
468  * that the handles are correctly 
469  */
470
471 /* This function recalculates the handles of an F-Curve 
472  * If the BezTriples have been rearranged, sort them first before using this.
473  */
474 void calchandles_fcurve (FCurve *fcu)
475 {
476         BezTriple *bezt, *prev, *next;
477         int a= fcu->totvert;
478
479         /* Error checking:
480          *      - need at least two points
481          *      - need bezier keys
482          *      - only bezier-interpolation has handles (for now)
483          */
484         if (ELEM(NULL, fcu, fcu->bezt) || (a < 2) /*|| ELEM(fcu->ipo, BEZT_IPO_CONST, BEZT_IPO_LIN)*/) 
485                 return;
486         
487         /* get initial pointers */
488         bezt= fcu->bezt;
489         prev= NULL;
490         next= (bezt + 1);
491         
492         /* loop over all beztriples, adjusting handles */
493         while (a--) {
494                 /* clamp timing of handles to be on either side of beztriple */
495                 if (bezt->vec[0][0] > bezt->vec[1][0]) bezt->vec[0][0]= bezt->vec[1][0];
496                 if (bezt->vec[2][0] < bezt->vec[1][0]) bezt->vec[2][0]= bezt->vec[1][0];
497                 
498                 /* calculate auto-handles */
499                 if (fcu->flag & FCURVE_AUTO_HANDLES) 
500                         calchandleNurb(bezt, prev, next, 2);    /* 2==special autohandle && keep extrema horizontal */
501                 else
502                         calchandleNurb(bezt, prev, next, 1);    /* 1==special autohandle */
503                 
504                 /* for automatic ease in and out */
505                 if ((bezt->h1==HD_AUTO) && (bezt->h2==HD_AUTO)) {
506                         /* only do this on first or last beztriple */
507                         if ((a == 0) || (a == fcu->totvert-1)) {
508                                 /* set both handles to have same horizontal value as keyframe */
509                                 if (fcu->extend == FCURVE_EXTRAPOLATE_CONSTANT) {
510                                         bezt->vec[0][1]= bezt->vec[2][1]= bezt->vec[1][1];
511                                 }
512                         }
513                 }
514                 
515                 /* advance pointers for next iteration */
516                 prev= bezt;
517                 if (a == 1) next= NULL;
518                 else next++;
519                 bezt++;
520         }
521 }
522
523 /* Use when F-Curve with handles has changed
524  * It treats all BezTriples with the following rules:
525  *  - PHASE 1: do types have to be altered?
526  *              -> Auto handles: become aligned when selection status is NOT(000 || 111)
527  *              -> Vector handles: become 'nothing' when (one half selected AND other not)
528  *  - PHASE 2: recalculate handles
529 */
530 void testhandles_fcurve (FCurve *fcu)
531 {
532         BezTriple *bezt;
533         unsigned int a;
534
535         /* only beztriples have handles (bpoints don't though) */
536         if ELEM(NULL, fcu, fcu->bezt)
537                 return;
538         
539         /* loop over beztriples */
540         for (a=0, bezt=fcu->bezt; a < fcu->totvert; a++, bezt++) {
541                 short flag= 0;
542                 
543                 /* flag is initialised as selection status
544                  * of beztriple control-points (labelled 0,1,2)
545                  */
546                 if (bezt->f1 & SELECT) flag |= (1<<0); // == 1
547                 if (bezt->f2 & SELECT) flag |= (1<<1); // == 2
548                 if (bezt->f3 & SELECT) flag |= (1<<2); // == 4
549                 
550                 /* one or two handles selected only */
551                 if (ELEM(flag, 0, 7)==0) {
552                         /* auto handles become aligned */
553                         if (bezt->h1==HD_AUTO)
554                                 bezt->h1= HD_ALIGN;
555                         if (bezt->h2==HD_AUTO)
556                                 bezt->h2= HD_ALIGN;
557                         
558                         /* vector handles become 'free' when only one half selected */
559                         if (bezt->h1==HD_VECT) {
560                                 /* only left half (1 or 2 or 1+2) */
561                                 if (flag < 4) 
562                                         bezt->h1= 0;
563                         }
564                         if (bezt->h2==HD_VECT) {
565                                 /* only right half (4 or 2+4) */
566                                 if (flag > 3) 
567                                         bezt->h2= 0;
568                         }
569                 }
570         }
571
572         /* recalculate handles */
573         calchandles_fcurve(fcu);
574 }
575
576 /* This function sorts BezTriples so that they are arranged in chronological order,
577  * as tools working on F-Curves expect that the BezTriples are in order.
578  */
579 void sort_time_fcurve (FCurve *fcu)
580 {
581         short ok= 1;
582         
583         /* keep adjusting order of beztriples until nothing moves (bubble-sort) */
584         while (ok) {
585                 ok= 0;
586                 
587                 /* currently, will only be needed when there are beztriples */
588                 if (fcu->bezt) {
589                         BezTriple *bezt;
590                         unsigned int a;
591                         
592                         /* loop over ALL points to adjust position in array and recalculate handles */
593                         for (a=0, bezt=fcu->bezt; a < fcu->totvert; a++, bezt++) {
594                                 /* check if thee's a next beztriple which we could try to swap with current */
595                                 if (a < (fcu->totvert-1)) {
596                                         /* swap if one is after the other (and indicate that order has changed) */
597                                         if (bezt->vec[1][0] > (bezt+1)->vec[1][0]) {
598                                                 SWAP(BezTriple, *bezt, *(bezt+1));
599                                                 ok= 1;
600                                         }
601                                         
602                                         /* if either one of both of the points exceeds crosses over the keyframe time... */
603                                         if ( (bezt->vec[0][0] > bezt->vec[1][0]) && (bezt->vec[2][0] < bezt->vec[1][0]) ) {
604                                                 /* swap handles if they have switched sides for some reason */
605                                                 SWAP(float, bezt->vec[0][0], bezt->vec[2][0]);
606                                                 SWAP(float, bezt->vec[0][1], bezt->vec[2][1]);
607                                         }
608                                         else {
609                                                 /* clamp handles */
610                                                 if (bezt->vec[0][0] > bezt->vec[1][0]) 
611                                                         bezt->vec[0][0]= bezt->vec[1][0];
612                                                 if (bezt->vec[2][0] < bezt->vec[1][0]) 
613                                                         bezt->vec[2][0]= bezt->vec[1][0];
614                                         }
615                                 }
616                         }
617                 }
618         }
619 }
620
621 /* This function tests if any BezTriples are out of order, thus requiring a sort */
622 short test_time_fcurve (FCurve *fcu)
623 {
624         unsigned int a;
625         
626         /* sanity checks */
627         if (fcu == NULL)
628                 return 0;
629         
630         /* currently, only need to test beztriples */
631         if (fcu->bezt) {
632                 BezTriple *bezt;
633                 
634                 /* loop through all BezTriples, stopping when one exceeds the one after it */
635                 for (a=0, bezt= fcu->bezt; a < (fcu->totvert - 1); a++, bezt++) {
636                         if (bezt->vec[1][0] > (bezt+1)->vec[1][0])
637                                 return 1;
638                 }
639         }
640         else if (fcu->fpt) {
641                 FPoint *fpt;
642                 
643                 /* loop through all FPoints, stopping when one exceeds the one after it */
644                 for (a=0, fpt= fcu->fpt; a < (fcu->totvert - 1); a++, fpt++) {
645                         if (fpt->vec[0] > (fpt+1)->vec[0])
646                                 return 1;
647                 }
648         }
649         
650         /* none need any swapping */
651         return 0;
652 }
653
654 /* ***************************** Drivers ********************************* */
655
656 /* Driver API --------------------------------- */
657
658 /* This frees the driver target itself */
659 void driver_free_target (ChannelDriver *driver, DriverTarget *dtar)
660 {
661         /* sanity checks */
662         if (dtar == NULL)
663                 return;
664                 
665         /* free target vars */
666         if (dtar->rna_path)
667                 MEM_freeN(dtar->rna_path);
668         
669         /* remove the target from the driver */
670         if (driver)
671                 BLI_freelinkN(&driver->targets, dtar);
672         else
673                 MEM_freeN(dtar);
674 }
675
676 /* Add a new driver target variable */
677 DriverTarget *driver_add_new_target (ChannelDriver *driver)
678 {
679         DriverTarget *dtar;
680         
681         /* sanity checks */
682         if (driver == NULL)
683                 return NULL;
684                 
685         /* make a new target */
686         dtar= MEM_callocN(sizeof(DriverTarget), "DriverTarget");
687         BLI_addtail(&driver->targets, dtar);
688         
689         /* give the target a 'unique' name */
690         strcpy(dtar->name, "var");
691         BLI_uniquename(&driver->targets, dtar, "var", '_', offsetof(DriverTarget, name), 64);
692         
693         /* return the target */
694         return dtar;
695 }
696
697 /* This frees the driver itself */
698 void fcurve_free_driver(FCurve *fcu)
699 {
700         ChannelDriver *driver;
701         DriverTarget *dtar, *dtarn;
702         
703         /* sanity checks */
704         if ELEM(NULL, fcu, fcu->driver)
705                 return;
706         driver= fcu->driver;
707         
708         /* free driver targets */
709         for (dtar= driver->targets.first; dtar; dtar= dtarn) {
710                 dtarn= dtar->next;
711                 driver_free_target(driver, dtar);
712         }
713         
714         /* free driver itself, then set F-Curve's point to this to NULL (as the curve may still be used) */
715         MEM_freeN(driver);
716         fcu->driver= NULL;
717 }
718
719 /* This makes a copy of the given driver */
720 ChannelDriver *fcurve_copy_driver (ChannelDriver *driver)
721 {
722         ChannelDriver *ndriver;
723         DriverTarget *dtar;
724         
725         /* sanity checks */
726         if (driver == NULL)
727                 return NULL;
728                 
729         /* copy all data */
730         ndriver= MEM_dupallocN(driver);
731         
732         /* copy targets */
733         ndriver->targets.first= ndriver->targets.last= NULL;
734         BLI_duplicatelist(&ndriver->targets, &driver->targets);
735         
736         for (dtar= ndriver->targets.first; dtar; dtar= dtar->next) {
737                 /* make a copy of target's rna path if available */
738                 if (dtar->rna_path)
739                         dtar->rna_path = MEM_dupallocN(dtar->rna_path);
740         }
741         
742         /* return the new driver */
743         return ndriver;
744 }
745
746 /* Driver Evaluation -------------------------- */
747
748 /* Helper function to obtain a value using RNA from the specified source (for evaluating drivers) */
749 float driver_get_target_value (ChannelDriver *driver, DriverTarget *dtar)
750 {
751         PointerRNA id_ptr, ptr;
752         PropertyRNA *prop;
753         ID *id;
754         char *path;
755         int index;
756         float value= 0.0f;
757         
758         /* sanity check */
759         if ELEM(NULL, driver, dtar)
760                 return 0.0f;
761         
762         /* get RNA-pointer for the ID-block given in target */
763         RNA_id_pointer_create(dtar->id, &id_ptr);
764         id= dtar->id;
765         path= dtar->rna_path;
766         index= dtar->array_index;
767         
768         /* error check for missing pointer... */
769         if (id == NULL) {
770                 printf("Error: driver doesn't have any valid target to use \n");
771                 if (G.f & G_DEBUG) printf("\tpath = %s [%d] \n", path, index);
772                 driver->flag |= DRIVER_FLAG_INVALID;
773                 return 0.0f;
774         }
775         
776         /* get property to read from, and get value as appropriate */
777         if (RNA_path_resolve(&id_ptr, path, &ptr, &prop)) {
778                 switch (RNA_property_type(prop)) {
779                         case PROP_BOOLEAN:
780                                 if (RNA_property_array_length(&ptr, prop))
781                                         value= (float)RNA_property_boolean_get_index(&ptr, prop, index);
782                                 else
783                                         value= (float)RNA_property_boolean_get(&ptr, prop);
784                                 break;
785                         case PROP_INT:
786                                 if (RNA_property_array_length(&ptr, prop))
787                                         value= (float)RNA_property_int_get_index(&ptr, prop, index);
788                                 else
789                                         value= (float)RNA_property_int_get(&ptr, prop);
790                                 break;
791                         case PROP_FLOAT:
792                                 if (RNA_property_array_length(&ptr, prop))
793                                         value= RNA_property_float_get_index(&ptr, prop, index);
794                                 else
795                                         value= RNA_property_float_get(&ptr, prop);
796                                 break;
797                         case PROP_ENUM:
798                                 value= (float)RNA_property_enum_get(&ptr, prop);
799                                 break;
800                         default:
801                                 break;
802                 }
803         }
804         else {
805                 if (G.f & G_DEBUG)
806                         printf("Driver Evaluation Error: cannot resolve target for %s -> %s \n", id->name, path);
807                 
808                 driver->flag |= DRIVER_FLAG_INVALID;
809                 return 0.0f;
810         }
811         
812         return value;
813 }
814
815 /* Get two PoseChannels from the targets of the given Driver */
816 static void driver_get_target_pchans2 (ChannelDriver *driver, bPoseChannel **pchan1, bPoseChannel **pchan2)
817 {
818         DriverTarget *dtar;
819         short i = 0;
820         
821         /* before doing anything */
822         *pchan1= NULL;
823         *pchan2= NULL;
824         
825         /* only take the first two targets */
826         for (dtar= driver->targets.first; (dtar) && (i < 2); dtar=dtar->next, i++) {
827                 PointerRNA id_ptr, ptr;
828                 PropertyRNA *prop;
829                 
830                 /* get RNA-pointer for the ID-block given in target */
831                 if (dtar->id)
832                         RNA_id_pointer_create(dtar->id, &id_ptr);
833                 else
834                         continue;
835                 
836                 /* resolve path so that we have pointer to the right posechannel */
837                 if (RNA_path_resolve(&id_ptr, dtar->rna_path, &ptr, &prop)) {
838                         /* is pointer valid (i.e. pointing to an actual posechannel */
839                         if ((ptr.type == &RNA_PoseChannel) && (ptr.data)) {
840                                 /* first or second target? */
841                                 if (i)
842                                         *pchan1= ptr.data;
843                                 else
844                                         *pchan2= ptr.data;
845                         }
846                 }
847         }
848 }
849
850 /* Evaluate an Channel-Driver to get a 'time' value to use instead of "evaltime"
851  *      - "evaltime" is the frame at which F-Curve is being evaluated
852  *      - has to return a float value 
853  */
854 static float evaluate_driver (ChannelDriver *driver, float evaltime)
855 {
856         DriverTarget *dtar;
857         
858         /* check if driver can be evaluated */
859         if (driver->flag & DRIVER_FLAG_INVALID)
860                 return 0.0f;
861         
862         // TODO: the flags for individual targets need to be used too for more fine-grained support...
863         switch (driver->type) {
864                 case DRIVER_TYPE_AVERAGE: /* average values of driver targets */
865                 {
866                         /* check how many targets there are first (i.e. just one?) */
867                         if (driver->targets.first == driver->targets.last) {
868                                 /* just one target, so just use that */
869                                 dtar= driver->targets.first;
870                                 return driver_get_target_value(driver, dtar);
871                         }
872                         else {
873                                 /* more than one target, so average the values of the targets */
874                                 int tot = 0;
875                                 float value = 0.0f;
876                                 
877                                 /* loop through targets, adding (hopefully we don't get any overflow!) */
878                                 for (dtar= driver->targets.first; dtar; dtar=dtar->next) {
879                                         value += driver_get_target_value(driver, dtar); 
880                                         tot++;
881                                 }
882                                 
883                                 /* return the average of these */
884                                 return (value / (float)tot);
885                         }
886                 }
887                         break;
888                 
889                 case DRIVER_TYPE_PYTHON: /* expression */
890                 {
891 #ifndef DISABLE_PYTHON
892                         /* check for empty or invalid expression */
893                         if ( (driver->expression[0] == '\0') ||
894                                  (driver->flag & DRIVER_FLAG_INVALID) )
895                         {
896                                 return 0.0f;
897                         }
898                         
899                         /* this evaluates the expression using Python,and returns its result:
900                          *      - on errors it reports, then returns 0.0f
901                          */
902                         return BPY_pydriver_eval(driver);
903 #endif /* DISABLE_PYTHON*/
904                 }
905                         break;
906
907                 
908                 case DRIVER_TYPE_ROTDIFF: /* difference of rotations of 2 bones (should ideally be in same armature) */
909                 {
910                         bPoseChannel *pchan, *pchan2;
911                         float q1[4], q2[4], quat[4], angle;
912                         
913                         /* get pose channels, and check if we've got two */
914                         driver_get_target_pchans2(driver, &pchan, &pchan2);
915                         if (ELEM(NULL, pchan, pchan2)) {
916                                 /* disable this driver, since it doesn't work correctly... */
917                                 driver->flag |= DRIVER_FLAG_INVALID;
918                                 
919                                 /* check what the error was */
920                                 if ((pchan == NULL) && (pchan2 == NULL))
921                                         printf("Driver Evaluation Error: Rotational difference failed - first 2 targets invalid \n");
922                                 else if (pchan == NULL)
923                                         printf("Driver Evaluation Error: Rotational difference failed - first target not valid PoseChannel \n");
924                                 else if (pchan2 == NULL)
925                                         printf("Driver Evaluation Error: Rotational difference failed - second target not valid PoseChannel \n");
926                                         
927                                 /* stop here... */
928                                 return 0.0f;
929                         }                       
930                         
931                         /* use the final posed locations */
932                         mat4_to_quat(q1, pchan->pose_mat);
933                         mat4_to_quat(q2, pchan2->pose_mat);
934                         
935                         invert_qt(q1);
936                         mul_qt_qtqt(quat, q1, q2);
937                         angle = 2.0f * (saacos(quat[0]));
938                         angle= ABS(angle);
939                         
940                         return (angle > M_PI) ? (float)((2.0f * M_PI) - angle) : (float)(angle);
941                 }
942                         break;
943                 
944                 default:
945                 {
946                         /* special 'hack' - just use stored value 
947                          *      This is currently used as the mechanism which allows animated settings to be able
948                          *      to be changed via the UI.
949                          */
950                         return driver->curval;
951                 }
952         }
953         
954         /* return 0.0f, as couldn't find relevant data to use */
955         return 0.0f;
956 }
957
958 /* ***************************** Curve Calculations ********************************* */
959
960 /* The total length of the handles is not allowed to be more
961  * than the horizontal distance between (v1-v4).
962  * This is to prevent curve loops.
963 */
964 void correct_bezpart (float *v1, float *v2, float *v3, float *v4)
965 {
966         float h1[2], h2[2], len1, len2, len, fac;
967         
968         /* calculate handle deltas */
969         h1[0]= v1[0] - v2[0];
970         h1[1]= v1[1] - v2[1];
971         
972         h2[0]= v4[0] - v3[0];
973         h2[1]= v4[1] - v3[1];
974         
975         /* calculate distances: 
976          *      - len   = span of time between keyframes 
977          *      - len1  = length of handle of start key
978          *      - len2  = length of handle of end key
979          */
980         len= v4[0]- v1[0];
981         len1= (float)fabs(h1[0]);
982         len2= (float)fabs(h2[0]);
983         
984         /* if the handles have no length, no need to do any corrections */
985         if ((len1+len2) == 0.0f) 
986                 return;
987                 
988         /* the two handles cross over each other, so force them
989          * apart using the proportion they overlap 
990          */
991         if ((len1+len2) > len) {
992                 fac= len / (len1+len2);
993                 
994                 v2[0]= (v1[0] - fac*h1[0]);
995                 v2[1]= (v1[1] - fac*h1[1]);
996                 
997                 v3[0]= (v4[0] - fac*h2[0]);
998                 v3[1]= (v4[1] - fac*h2[1]);
999         }
1000 }
1001
1002 /* find root ('zero') */
1003 static int findzero (float x, float q0, float q1, float q2, float q3, float *o)
1004 {
1005         double c0, c1, c2, c3, a, b, c, p, q, d, t, phi;
1006         int nr= 0;
1007
1008         c0= q0 - x;
1009         c1= 3.0 * (q1 - q0);
1010         c2= 3.0 * (q0 - 2.0*q1 + q2);
1011         c3= q3 - q0 + 3.0 * (q1 - q2);
1012         
1013         if (c3 != 0.0) {
1014                 a= c2/c3;
1015                 b= c1/c3;
1016                 c= c0/c3;
1017                 a= a/3;
1018                 
1019                 p= b/3 - a*a;
1020                 q= (2*a*a*a - a*b + c) / 2;
1021                 d= q*q + p*p*p;
1022                 
1023                 if (d > 0.0) {
1024                         t= sqrt(d);
1025                         o[0]= (float)(sqrt3d(-q+t) + sqrt3d(-q-t) - a);
1026                         
1027                         if ((o[0] >= SMALL) && (o[0] <= 1.000001)) return 1;
1028                         else return 0;
1029                 }
1030                 else if (d == 0.0) {
1031                         t= sqrt3d(-q);
1032                         o[0]= (float)(2*t - a);
1033                         
1034                         if ((o[0] >= SMALL) && (o[0] <= 1.000001)) nr++;
1035                         o[nr]= (float)(-t-a);
1036                         
1037                         if ((o[nr] >= SMALL) && (o[nr] <= 1.000001)) return nr+1;
1038                         else return nr;
1039                 }
1040                 else {
1041                         phi= acos(-q / sqrt(-(p*p*p)));
1042                         t= sqrt(-p);
1043                         p= cos(phi/3);
1044                         q= sqrt(3 - 3*p*p);
1045                         o[0]= (float)(2*t*p - a);
1046                         
1047                         if ((o[0] >= SMALL) && (o[0] <= 1.000001)) nr++;
1048                         o[nr]= (float)(-t * (p + q) - a);
1049                         
1050                         if ((o[nr] >= SMALL) && (o[nr] <= 1.000001)) nr++;
1051                         o[nr]= (float)(-t * (p - q) - a);
1052                         
1053                         if ((o[nr] >= SMALL) && (o[nr] <= 1.000001)) return nr+1;
1054                         else return nr;
1055                 }
1056         }
1057         else {
1058                 a=c2;
1059                 b=c1;
1060                 c=c0;
1061                 
1062                 if (a != 0.0) {
1063                         // discriminant
1064                         p= b*b - 4*a*c;
1065                         
1066                         if (p > 0) {
1067                                 p= sqrt(p);
1068                                 o[0]= (float)((-b-p) / (2 * a));
1069                                 
1070                                 if ((o[0] >= SMALL) && (o[0] <= 1.000001)) nr++;
1071                                 o[nr]= (float)((-b+p)/(2*a));
1072                                 
1073                                 if ((o[nr] >= SMALL) && (o[nr] <= 1.000001)) return nr+1;
1074                                 else return nr;
1075                         }
1076                         else if (p == 0) {
1077                                 o[0]= (float)(-b / (2 * a));
1078                                 if ((o[0] >= SMALL) && (o[0] <= 1.000001)) return 1;
1079                                 else return 0;
1080                         }
1081                 }
1082                 else if (b != 0.0) {
1083                         o[0]= (float)(-c/b);
1084                         
1085                         if ((o[0] >= SMALL) && (o[0] <= 1.000001)) return 1;
1086                         else return 0;
1087                 }
1088                 else if (c == 0.0) {
1089                         o[0]= 0.0;
1090                         return 1;
1091                 }
1092                 
1093                 return 0;       
1094         }
1095 }
1096
1097 static void berekeny (float f1, float f2, float f3, float f4, float *o, int b)
1098 {
1099         float t, c0, c1, c2, c3;
1100         int a;
1101
1102         c0= f1;
1103         c1= 3.0f * (f2 - f1);
1104         c2= 3.0f * (f1 - 2.0f*f2 + f3);
1105         c3= f4 - f1 + 3.0f * (f2 - f3);
1106         
1107         for (a=0; a < b; a++) {
1108                 t= o[a];
1109                 o[a]= c0 + t*c1 + t*t*c2 + t*t*t*c3;
1110         }
1111 }
1112
1113 #if 0
1114 static void berekenx (float *f, float *o, int b)
1115 {
1116         float t, c0, c1, c2, c3;
1117         int a;
1118
1119         c0= f[0];
1120         c1= 3.0f * (f[3] - f[0]);
1121         c2= 3.0f * (f[0] - 2.0f*f[3] + f[6]);
1122         c3= f[9] - f[0] + 3.0f * (f[3] - f[6]);
1123         
1124         for (a=0; a < b; a++) {
1125                 t= o[a];
1126                 o[a]= c0 + t*c1 + t*t*c2 + t*t*t*c3;
1127         }
1128 }
1129 #endif
1130
1131
1132 /* -------------------------- */
1133
1134 /* Calculate F-Curve value for 'evaltime' using BezTriple keyframes */
1135 static float fcurve_eval_keyframes (FCurve *fcu, BezTriple *bezts, float evaltime)
1136 {
1137         BezTriple *bezt, *prevbezt, *lastbezt;
1138         float v1[2], v2[2], v3[2], v4[2], opl[32], dx, fac;
1139         unsigned int a;
1140         int b;
1141         float cvalue = 0.0f;
1142         
1143         /* get pointers */
1144         a= fcu->totvert-1;
1145         prevbezt= bezts;
1146         bezt= prevbezt+1;
1147         lastbezt= prevbezt + a;
1148         
1149         /* evaluation time at or past endpoints? */
1150         if (prevbezt->vec[1][0] >= evaltime) 
1151         {
1152                 /* before or on first keyframe */
1153                 if ( (fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (prevbezt->ipo != BEZT_IPO_CONST) &&
1154                         !(fcu->flag & FCURVE_DISCRETE_VALUES) ) 
1155                 {
1156                         /* linear or bezier interpolation */
1157                         if (prevbezt->ipo==BEZT_IPO_LIN) 
1158                         {
1159                                 /* Use the next center point instead of our own handle for
1160                                  * linear interpolated extrapolate 
1161                                  */
1162                                 if (fcu->totvert == 1) 
1163                                         cvalue= prevbezt->vec[1][1];
1164                                 else 
1165                                 {
1166                                         bezt = prevbezt+1;
1167                                         dx= prevbezt->vec[1][0] - evaltime;
1168                                         fac= bezt->vec[1][0] - prevbezt->vec[1][0];
1169                                         
1170                                         /* prevent division by zero */
1171                                         if (fac) {
1172                                                 fac= (bezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
1173                                                 cvalue= prevbezt->vec[1][1] - (fac * dx);
1174                                         }
1175                                         else 
1176                                                 cvalue= prevbezt->vec[1][1];
1177                                 }
1178                         } 
1179                         else 
1180                         {
1181                                 /* Use the first handle (earlier) of first BezTriple to calculate the
1182                                  * gradient and thus the value of the curve at evaltime
1183                                  */
1184                                 dx= prevbezt->vec[1][0] - evaltime;
1185                                 fac= prevbezt->vec[1][0] - prevbezt->vec[0][0];
1186                                 
1187                                 /* prevent division by zero */
1188                                 if (fac) {
1189                                         fac= (prevbezt->vec[1][1] - prevbezt->vec[0][1]) / fac;
1190                                         cvalue= prevbezt->vec[1][1] - (fac * dx);
1191                                 }
1192                                 else 
1193                                         cvalue= prevbezt->vec[1][1];
1194                         }
1195                 }
1196                 else 
1197                 {
1198                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation, 
1199                          * so just extend first keyframe's value 
1200                          */
1201                         cvalue= prevbezt->vec[1][1];
1202                 }
1203         }
1204         else if (lastbezt->vec[1][0] <= evaltime) 
1205         {
1206                 /* after or on last keyframe */
1207                 if ( (fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (lastbezt->ipo != BEZT_IPO_CONST) &&
1208                         !(fcu->flag & FCURVE_DISCRETE_VALUES) ) 
1209                 {
1210                         /* linear or bezier interpolation */
1211                         if (lastbezt->ipo==BEZT_IPO_LIN) 
1212                         {
1213                                 /* Use the next center point instead of our own handle for
1214                                  * linear interpolated extrapolate 
1215                                  */
1216                                 if (fcu->totvert == 1) 
1217                                         cvalue= lastbezt->vec[1][1];
1218                                 else 
1219                                 {
1220                                         prevbezt = lastbezt - 1;
1221                                         dx= evaltime - lastbezt->vec[1][0];
1222                                         fac= lastbezt->vec[1][0] - prevbezt->vec[1][0];
1223                                         
1224                                         /* prevent division by zero */
1225                                         if (fac) {
1226                                                 fac= (lastbezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
1227                                                 cvalue= lastbezt->vec[1][1] + (fac * dx);
1228                                         }
1229                                         else 
1230                                                 cvalue= lastbezt->vec[1][1];
1231                                 }
1232                         } 
1233                         else 
1234                         {
1235                                 /* Use the gradient of the second handle (later) of last BezTriple to calculate the
1236                                  * gradient and thus the value of the curve at evaltime
1237                                  */
1238                                 dx= evaltime - lastbezt->vec[1][0];
1239                                 fac= lastbezt->vec[2][0] - lastbezt->vec[1][0];
1240                                 
1241                                 /* prevent division by zero */
1242                                 if (fac) {
1243                                         fac= (lastbezt->vec[2][1] - lastbezt->vec[1][1]) / fac;
1244                                         cvalue= lastbezt->vec[1][1] + (fac * dx);
1245                                 }
1246                                 else 
1247                                         cvalue= lastbezt->vec[1][1];
1248                         }
1249                 }
1250                 else 
1251                 {
1252                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation, 
1253                          * so just extend last keyframe's value 
1254                          */
1255                         cvalue= lastbezt->vec[1][1];
1256                 }
1257         }
1258         else 
1259         {
1260                 /* evaltime occurs somewhere in the middle of the curve */
1261                 for (a=0; prevbezt && bezt && (a < fcu->totvert-1); a++, prevbezt=bezt, bezt++) 
1262                 {  
1263                         /* evaltime occurs within the interval defined by these two keyframes */
1264                         if ((prevbezt->vec[1][0] <= evaltime) && (bezt->vec[1][0] >= evaltime)) 
1265                         {
1266                                 /* value depends on interpolation mode */
1267                                 if ((prevbezt->ipo == BEZT_IPO_CONST) || (fcu->flag & FCURVE_DISCRETE_VALUES))
1268                                 {
1269                                         /* constant (evaltime not relevant, so no interpolation needed) */
1270                                         cvalue= prevbezt->vec[1][1];
1271                                 }
1272                                 else if (prevbezt->ipo == BEZT_IPO_LIN) 
1273                                 {
1274                                         /* linear - interpolate between values of the two keyframes */
1275                                         fac= bezt->vec[1][0] - prevbezt->vec[1][0];
1276                                         
1277                                         /* prevent division by zero */
1278                                         if (fac) {
1279                                                 fac= (evaltime - prevbezt->vec[1][0]) / fac;
1280                                                 cvalue= prevbezt->vec[1][1] + (fac * (bezt->vec[1][1] - prevbezt->vec[1][1]));
1281                                         }
1282                                         else
1283                                                 cvalue= prevbezt->vec[1][1];
1284                                 }
1285                                 else 
1286                                 {
1287                                         /* bezier interpolation */
1288                                                 /* v1,v2 are the first keyframe and its 2nd handle */
1289                                         v1[0]= prevbezt->vec[1][0];
1290                                         v1[1]= prevbezt->vec[1][1];
1291                                         v2[0]= prevbezt->vec[2][0];
1292                                         v2[1]= prevbezt->vec[2][1];
1293                                                 /* v3,v4 are the last keyframe's 1st handle + the last keyframe */
1294                                         v3[0]= bezt->vec[0][0];
1295                                         v3[1]= bezt->vec[0][1];
1296                                         v4[0]= bezt->vec[1][0];
1297                                         v4[1]= bezt->vec[1][1];
1298                                         
1299                                         /* adjust handles so that they don't overlap (forming a loop) */
1300                                         correct_bezpart(v1, v2, v3, v4);
1301                                         
1302                                         /* try to get a value for this position - if failure, try another set of points */
1303                                         b= findzero(evaltime, v1[0], v2[0], v3[0], v4[0], opl);
1304                                         if (b) {
1305                                                 berekeny(v1[1], v2[1], v3[1], v4[1], opl, 1);
1306                                                 cvalue= opl[0];
1307                                                 break;
1308                                         }
1309                                 }
1310                         }
1311                 }
1312         }
1313         
1314         /* return value */
1315         return cvalue;
1316 }
1317
1318 /* Calculate F-Curve value for 'evaltime' using FPoint samples */
1319 static float fcurve_eval_samples (FCurve *fcu, FPoint *fpts, float evaltime)
1320 {
1321         FPoint *prevfpt, *lastfpt, *fpt;
1322         float cvalue= 0.0f;
1323         
1324         /* get pointers */
1325         prevfpt= fpts;
1326         lastfpt= prevfpt + fcu->totvert-1;
1327         
1328         /* evaluation time at or past endpoints? */
1329         if (prevfpt->vec[0] >= evaltime) {
1330                 /* before or on first sample, so just extend value */
1331                 cvalue= prevfpt->vec[1];
1332         }
1333         else if (lastfpt->vec[0] <= evaltime) {
1334                 /* after or on last sample, so just extend value */
1335                 cvalue= lastfpt->vec[1];
1336         }
1337         else {
1338                 /* find the one on the right frame (assume that these are spaced on 1-frame intervals) */
1339                 fpt= prevfpt + (int)(evaltime - prevfpt->vec[0]);
1340                 cvalue= fpt->vec[1];
1341         }
1342         
1343         /* return value */
1344         return cvalue;
1345 }
1346
1347 /* ***************************** F-Curve - Evaluation ********************************* */
1348
1349 /* Evaluate and return the value of the given F-Curve at the specified frame ("evaltime") 
1350  * Note: this is also used for drivers
1351  */
1352 float evaluate_fcurve (FCurve *fcu, float evaltime) 
1353 {
1354         float cvalue= 0.0f;
1355         float devaltime;
1356         
1357         /* if there is a driver (only if this F-Curve is acting as 'driver'), evaluate it to find value to use as "evaltime" 
1358          * since drivers essentially act as alternative input (i.e. in place of 'time') for F-Curves
1359          *      - this value will also be returned as the value of the 'curve', if there are no keyframes
1360          */
1361         if (fcu->driver) {
1362                 /* evaltime now serves as input for the curve */
1363                 evaltime= cvalue= evaluate_driver(fcu->driver, evaltime);
1364         }
1365         
1366         /* evaluate modifiers which modify time to evaluate the base curve at */
1367         devaltime= evaluate_time_fmodifiers(&fcu->modifiers, fcu, cvalue, evaltime);
1368         
1369         /* evaluate curve-data 
1370          *      - 'devaltime' instead of 'evaltime', as this is the time that the last time-modifying 
1371          *        F-Curve modifier on the stack requested the curve to be evaluated at
1372          */
1373         if (fcu->bezt)
1374                 cvalue= fcurve_eval_keyframes(fcu, fcu->bezt, devaltime);
1375         else if (fcu->fpt)
1376                 cvalue= fcurve_eval_samples(fcu, fcu->fpt, devaltime);
1377         
1378         /* evaluate modifiers */
1379         evaluate_value_fmodifiers(&fcu->modifiers, fcu, &cvalue, evaltime);
1380         
1381         /* if curve can only have integral values, perform truncation (i.e. drop the decimal part)
1382          * here so that the curve can be sampled correctly
1383          */
1384         if (fcu->flag & FCURVE_INT_VALUES)
1385                 cvalue= (float)((int)cvalue);
1386         
1387         /* return evaluated value */
1388         return cvalue;
1389 }
1390
1391 /* Calculate the value of the given F-Curve at the given frame, and set its curval */
1392 void calculate_fcurve (FCurve *fcu, float ctime)
1393 {
1394         /* only calculate + set curval (overriding the existing value) if curve has 
1395          * any data which warrants this...
1396          */
1397         if ( (fcu->totvert) || (fcu->driver && !(fcu->driver->flag & DRIVER_FLAG_INVALID)) ||
1398                  list_has_suitable_fmodifier(&fcu->modifiers, 0, FMI_TYPE_GENERATE_CURVE) )
1399         {
1400                 /* calculate and set curval (evaluates driver too if necessary) */
1401                 fcu->curval= evaluate_fcurve(fcu, ctime);
1402         }
1403 }
1404