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