svn merge ^/trunk/blender -r41075:41099
[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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 /** \file blender/blenkernel/intern/fcurve.c
31  *  \ingroup bke
32  */
33
34  
35
36 #include <math.h>
37 #include <stdio.h>
38 #include <stddef.h>
39 #include <string.h>
40 #include <float.h>
41
42 #include "MEM_guardedalloc.h"
43
44 #include "DNA_anim_types.h"
45 #include "DNA_constraint_types.h"
46 #include "DNA_object_types.h"
47
48 #include "BLI_blenlib.h"
49 #include "BLI_math.h"
50 #include "BLI_utildefines.h"
51
52 #include "BKE_fcurve.h"
53 #include "BKE_animsys.h"
54 #include "BKE_action.h"
55 #include "BKE_armature.h"
56 #include "BKE_constraint.h"
57 #include "BKE_curve.h" 
58 #include "BKE_global.h"
59 #include "BKE_object.h"
60 #include "BKE_utildefines.h"
61
62 #include "RNA_access.h"
63
64 #ifdef WITH_PYTHON
65 #include "BPY_extern.h" 
66 #endif
67
68 #define SMALL -1.0e-10
69 #define SELECT 1
70
71 /* ************************** Data-Level Functions ************************* */
72
73 /* ---------------------- Freeing --------------------------- */
74
75 /* Frees the F-Curve itself too, so make sure BLI_remlink is called before calling this... */
76 void free_fcurve (FCurve *fcu) 
77 {
78         if (fcu == NULL) 
79                 return;
80         
81         /* free curve data */
82         if (fcu) {
83                 if (fcu->bezt) MEM_freeN(fcu->bezt);
84                 if (fcu->fpt) MEM_freeN(fcu->fpt);
85         }
86         
87         /* free RNA-path, as this were allocated when getting the path string */
88         if (fcu->rna_path)
89                 MEM_freeN(fcu->rna_path);
90         
91         /* free extra data - i.e. modifiers, and driver */
92         fcurve_free_driver(fcu);
93         free_fmodifiers(&fcu->modifiers);
94         
95         /* free f-curve itself */
96         MEM_freeN(fcu);
97 }
98
99 /* Frees a list of F-Curves */
100 void free_fcurves (ListBase *list)
101 {
102         FCurve *fcu, *fcn;
103         
104         /* sanity check */
105         if (list == NULL)
106                 return;
107                 
108         /* free data - no need to call remlink before freeing each curve, 
109          * as we store reference to next, and freeing only touches the curve
110          * it's given
111          */
112         for (fcu= list->first; fcu; fcu= fcn) {
113                 fcn= fcu->next;
114                 free_fcurve(fcu);
115         }
116         
117         /* clear pointers just in case */
118         list->first= list->last= NULL;
119 }       
120
121 /* ---------------------- Copy --------------------------- */
122
123 /* duplicate an F-Curve */
124 FCurve *copy_fcurve (FCurve *fcu)
125 {
126         FCurve *fcu_d;
127         
128         /* sanity check */
129         if (fcu == NULL)
130                 return NULL;
131                 
132         /* make a copy */
133         fcu_d= MEM_dupallocN(fcu);
134         
135         fcu_d->next= fcu_d->prev= NULL;
136         fcu_d->grp= NULL;
137         
138         /* copy curve data */
139         fcu_d->bezt= MEM_dupallocN(fcu_d->bezt);
140         fcu_d->fpt= MEM_dupallocN(fcu_d->fpt);
141         
142         /* copy rna-path */
143         fcu_d->rna_path= MEM_dupallocN(fcu_d->rna_path);
144         
145         /* copy driver */
146         fcu_d->driver= fcurve_copy_driver(fcu_d->driver);
147         
148         /* copy modifiers */
149         copy_fmodifiers(&fcu_d->modifiers, &fcu->modifiers);
150         
151         /* return new data */
152         return fcu_d;
153 }
154
155 /* duplicate a list of F-Curves */
156 void copy_fcurves (ListBase *dst, ListBase *src)
157 {
158         FCurve *dfcu, *sfcu;
159         
160         /* sanity checks */
161         if ELEM(NULL, dst, src)
162                 return;
163         
164         /* clear destination list first */
165         dst->first= dst->last= NULL;
166         
167         /* copy one-by-one */
168         for (sfcu= src->first; sfcu; sfcu= sfcu->next) {
169                 dfcu= copy_fcurve(sfcu);
170                 BLI_addtail(dst, dfcu);
171         }
172 }
173
174 /* ----------------- Finding F-Curves -------------------------- */
175
176 /* high level function to get an fcurve from C without having the rna */
177 FCurve *id_data_find_fcurve(ID *id, void *data, StructRNA *type, const char *prop_name, int index, char *driven)
178 {
179         /* anim vars */
180         AnimData *adt= BKE_animdata_from_id(id);
181         FCurve *fcu= NULL;
182
183         /* rna vars */
184         PointerRNA ptr;
185         PropertyRNA *prop;
186         char *path;
187
188         if(driven)
189                 *driven = 0;
190         
191         /* only use the current action ??? */
192         if (ELEM(NULL, adt, adt->action))
193                 return NULL;
194         
195         RNA_pointer_create(id, type, data, &ptr);
196         prop = RNA_struct_find_property(&ptr, prop_name);
197         
198         if (prop) {
199                 path= RNA_path_from_ID_to_property(&ptr, prop);
200                         
201                 if (path) {
202                         /* animation takes priority over drivers */
203                         if ((adt->action) && (adt->action->curves.first))
204                                 fcu= list_find_fcurve(&adt->action->curves, path, index);
205                         
206                         /* if not animated, check if driven */
207                         if ((fcu == NULL) && (adt->drivers.first)) {
208                                 fcu= list_find_fcurve(&adt->drivers, path, index);
209                                 if(fcu && driven)
210                                         *driven = 1;
211                                 fcu = NULL;
212                         }
213                         
214                         MEM_freeN(path);
215                 }
216         }
217
218         return fcu;
219 }
220
221
222 /* Find the F-Curve affecting the given RNA-access path + index, in the list of F-Curves provided */
223 FCurve *list_find_fcurve (ListBase *list, const char rna_path[], const int array_index)
224 {
225         FCurve *fcu;
226         
227         /* sanity checks */
228         if ( ELEM(NULL, list, rna_path) || (array_index < 0) )
229                 return NULL;
230         
231         /* check paths of curves, then array indices... */
232         for (fcu= list->first; fcu; fcu= fcu->next) {
233                 /* simple string-compare (this assumes that they have the same root...) */
234                 if (fcu->rna_path && !strcmp(fcu->rna_path, rna_path)) {
235                         /* now check indices */
236                         if (fcu->array_index == array_index)
237                                 return fcu;
238                 }
239         }
240         
241         /* return */
242         return NULL;
243 }
244
245 /* quick way to loop over all fcurves of a given 'path' */
246 FCurve *iter_step_fcurve (FCurve *fcu_iter, const char rna_path[])
247 {
248         FCurve *fcu;
249         
250         /* sanity checks */
251         if (ELEM(NULL, fcu_iter, rna_path))
252                 return NULL;
253
254         /* check paths of curves, then array indices... */
255         for (fcu= fcu_iter; fcu; fcu= fcu->next) {
256                 /* simple string-compare (this assumes that they have the same root...) */
257                 if (fcu->rna_path && !strcmp(fcu->rna_path, rna_path)) {
258                         return fcu;
259                 }
260         }
261
262         /* return */
263         return NULL;
264 }
265
266 /* Get list of LinkData's containing pointers to the F-Curves which control the types of data indicated 
267  * Lists...
268  *      - dst: list of LinkData's matching the criteria returned. 
269  *        List must be freed after use, and is assumed to be empty when passed.
270  *      - src: list of F-Curves to search through
271  * Filters...
272  *      - dataPrefix: i.e. 'pose.bones[' or 'nodes['
273  *      - dataName: name of entity within "" immediately following the prefix
274  */
275 int list_find_data_fcurves (ListBase *dst, ListBase *src, const char *dataPrefix, const char *dataName)
276 {
277         FCurve *fcu;
278         int matches = 0;
279         
280         /* sanity checks */
281         if (ELEM4(NULL, dst, src, dataPrefix, dataName))
282                 return 0;
283         else if ((dataPrefix[0] == 0) || (dataName[0] == 0))
284                 return 0;
285         
286         /* search each F-Curve one by one */
287         for (fcu= src->first; fcu; fcu= fcu->next) {
288                 /* check if quoted string matches the path */
289                 if ((fcu->rna_path) && strstr(fcu->rna_path, dataPrefix)) {
290                         char *quotedName= BLI_getQuotedStr(fcu->rna_path, dataPrefix);
291                         
292                         if (quotedName) {
293                                 /* check if the quoted name matches the required name */
294                                 if (strcmp(quotedName, dataName) == 0) {
295                                         LinkData *ld= MEM_callocN(sizeof(LinkData), "list_find_data_fcurves");
296                                         
297                                         ld->data= fcu;
298                                         BLI_addtail(dst, ld);
299                                         
300                                         matches++;
301                                 }
302                                 
303                                 /* always free the quoted string, since it needs freeing */
304                                 MEM_freeN(quotedName);
305                         }
306                 }
307         }
308         
309         /* return the number of matches */
310         return matches;
311 }
312
313 FCurve *rna_get_fcurve (PointerRNA *ptr, PropertyRNA *prop, int rnaindex, bAction **action, int *driven)
314 {
315         FCurve *fcu= NULL;
316         
317         *driven= 0;
318         
319         /* there must be some RNA-pointer + property combon */
320         if (prop && ptr->id.data && RNA_property_animateable(ptr, prop)) {
321                 AnimData *adt= BKE_animdata_from_id(ptr->id.data);
322                 char *path;
323                 
324                 if (adt) {
325                         if ((adt->action && adt->action->curves.first) || (adt->drivers.first)) {
326                                 /* XXX this function call can become a performance bottleneck */
327                                 path= RNA_path_from_ID_to_property(ptr, prop);
328                                 
329                                 if (path) {
330                                         /* animation takes priority over drivers */
331                                         if (adt->action && adt->action->curves.first)
332                                                 fcu= list_find_fcurve(&adt->action->curves, path, rnaindex);
333                                         
334                                         /* if not animated, check if driven */
335                                         if (!fcu && (adt->drivers.first)) {
336                                                 fcu= list_find_fcurve(&adt->drivers, path, rnaindex);
337                                                 
338                                                 if (fcu)
339                                                         *driven= 1;
340                                         }
341                                         
342                                         if (fcu && action)
343                                                 *action= adt->action;
344                                         
345                                         MEM_freeN(path);
346                                 }
347                         }
348                 }
349         }
350         
351         return fcu;
352 }
353
354 /* ----------------- Finding Keyframes/Extents -------------------------- */
355
356 /* threshold for binary-searching keyframes - threshold here should be good enough for now, but should become userpref */
357 #define BEZT_BINARYSEARCH_THRESH        0.01f /* was 0.00001, but giving errors */
358
359 /* Binary search algorithm for finding where to insert BezTriple. (for use by insert_bezt_fcurve)
360  * Returns the index to insert at (data already at that index will be offset if replace is 0)
361  */
362 int binarysearch_bezt_index (BezTriple array[], float frame, int arraylen, short *replace)
363 {
364         int start=0, end=arraylen;
365         int loopbreaker= 0, maxloop= arraylen * 2;
366         
367         /* initialise replace-flag first */
368         *replace= 0;
369         
370         /* sneaky optimisations (don't go through searching process if...):
371          *      - keyframe to be added is to be added out of current bounds
372          *      - keyframe to be added would replace one of the existing ones on bounds
373          */
374         if ((arraylen <= 0) || (array == NULL)) {
375                 printf("Warning: binarysearch_bezt_index() encountered invalid array \n");
376                 return 0;
377         }
378         else {
379                 /* check whether to add before/after/on */
380                 float framenum;
381                 
382                 /* 'First' Keyframe (when only one keyframe, this case is used) */
383                 framenum= array[0].vec[1][0];
384                 if (IS_EQT(frame, framenum, BEZT_BINARYSEARCH_THRESH)) {
385                         *replace = 1;
386                         return 0;
387                 }
388                 else if (frame < framenum)
389                         return 0;
390                         
391                 /* 'Last' Keyframe */
392                 framenum= array[(arraylen-1)].vec[1][0];
393                 if (IS_EQT(frame, framenum, BEZT_BINARYSEARCH_THRESH)) {
394                         *replace= 1;
395                         return (arraylen - 1);
396                 }
397                 else if (frame > framenum)
398                         return arraylen;
399         }
400         
401         
402         /* most of the time, this loop is just to find where to put it
403          * 'loopbreaker' is just here to prevent infinite loops 
404          */
405         for (loopbreaker=0; (start <= end) && (loopbreaker < maxloop); loopbreaker++) {
406                 /* compute and get midpoint */
407                 int mid = start + ((end - start) / 2);  /* we calculate the midpoint this way to avoid int overflows... */
408                 float midfra= array[mid].vec[1][0];
409                 
410                 /* check if exactly equal to midpoint */
411                 if (IS_EQT(frame, midfra, BEZT_BINARYSEARCH_THRESH)) {
412                         *replace = 1;
413                         return mid;
414                 }
415                 
416                 /* repeat in upper/lower half */
417                 if (frame > midfra)
418                         start= mid + 1;
419                 else if (frame < midfra)
420                         end= mid - 1;
421         }
422         
423         /* print error if loop-limit exceeded */
424         if (loopbreaker == (maxloop-1)) {
425                 printf("Error: binarysearch_bezt_index() was taking too long \n");
426                 
427                 // include debug info 
428                 printf("\tround = %d: start = %d, end = %d, arraylen = %d \n", loopbreaker, start, end, arraylen);
429         }
430         
431         /* not found, so return where to place it */
432         return start;
433 }
434
435 /* ...................................... */
436
437 /* helper for calc_fcurve_* functions -> find first and last BezTriple to be used */
438 static void get_fcurve_end_keyframes (FCurve *fcu, BezTriple **first, BezTriple **last, const short selOnly)
439 {
440         /* init outputs */
441         *first = NULL;
442         *last = NULL;
443         
444         /* sanity checks */
445         if (fcu->bezt == NULL)
446                 return;
447         
448         /* only include selected items? */
449         if (selOnly) {
450                 BezTriple *bezt;
451                 unsigned int i;
452                 
453                 /* find first selected */
454                 bezt = fcu->bezt;
455                 for (i=0; i < fcu->totvert; bezt++, i++) {
456                         if (BEZSELECTED(bezt)) {
457                                 *first= bezt;
458                                 break;
459                         }
460                 }
461                 
462                 /* find last selected */
463                 bezt = ARRAY_LAST_ITEM(fcu->bezt, BezTriple, sizeof(BezTriple), fcu->totvert);
464                 for (i=0; i < fcu->totvert; bezt--, i++) {
465                         if (BEZSELECTED(bezt)) {
466                                 *last= bezt;
467                                 break;
468                         }
469                 }
470         }
471         else {
472                 /* just full array */
473                 *first = fcu->bezt;
474                 *last = ARRAY_LAST_ITEM(fcu->bezt, BezTriple, sizeof(BezTriple), fcu->totvert);
475         }
476 }
477
478
479 /* Calculate the extents of F-Curve's data */
480 void calc_fcurve_bounds (FCurve *fcu, float *xmin, float *xmax, float *ymin, float *ymax, const short selOnly)
481 {
482         float xminv=999999999.0f, xmaxv=-999999999.0f;
483         float yminv=999999999.0f, ymaxv=-999999999.0f;
484         short foundvert=0;
485         unsigned int i;
486         
487         if (fcu->totvert) {
488                 if (fcu->bezt) {
489                         BezTriple *bezt_first= NULL, *bezt_last= NULL;
490                         
491                         if (xmin || xmax) {
492                                 /* get endpoint keyframes */
493                                 get_fcurve_end_keyframes(fcu, &bezt_first, &bezt_last, selOnly);
494                                 
495                                 if (bezt_first) {
496                                         BLI_assert(bezt_last != NULL);
497                                         
498                                         xminv= MIN2(xminv, bezt_first->vec[1][0]);
499                                         xmaxv= MAX2(xmaxv, bezt_last->vec[1][0]);
500                                 }
501                         }
502                         
503                         /* only loop over keyframes to find extents for values if needed */
504                         if (ymin || ymax) {     
505                                 BezTriple *bezt;
506                                 
507                                 for (bezt=fcu->bezt, i=0; i < fcu->totvert; bezt++, i++) {
508                                         if ((selOnly == 0) || BEZSELECTED(bezt)) {
509                                                 if (bezt->vec[1][1] < yminv)
510                                                         yminv= bezt->vec[1][1];
511                                                 if (bezt->vec[1][1] > ymaxv)
512                                                         ymaxv= bezt->vec[1][1];
513                                         }
514                                 }
515                         }
516                 }
517                 else if (fcu->fpt) {
518                         /* frame range can be directly calculated from end verts */
519                         if (xmin || xmax) {
520                                 xminv= MIN2(xminv, fcu->fpt[0].vec[0]);
521                                 xmaxv= MAX2(xmaxv, fcu->fpt[fcu->totvert-1].vec[0]);
522                         }
523                         
524                         /* only loop over keyframes to find extents for values if needed */
525                         if (ymin || ymax) {
526                                 FPoint *fpt;
527                                 
528                                 for (fpt=fcu->fpt, i=0; i < fcu->totvert; fpt++, i++) {
529                                         if (fpt->vec[1] < yminv)
530                                                 yminv= fpt->vec[1];
531                                         if (fpt->vec[1] > ymaxv)
532                                                 ymaxv= fpt->vec[1];
533                                 }
534                         }
535                 }
536                 
537                 foundvert=1;
538         }
539         
540         if (foundvert) {
541                 if (xmin) *xmin= xminv;
542                 if (xmax) *xmax= xmaxv;
543                 
544                 if (ymin) *ymin= yminv;
545                 if (ymax) *ymax= ymaxv;
546         }
547         else {
548                 if (G.f & G_DEBUG)
549                         printf("F-Curve calc bounds didn't find anything, so assuming minimum bounds of 1.0\n");
550                         
551                 if (xmin) *xmin= 0.0f;
552                 if (xmax) *xmax= 1.0f;
553                 
554                 if (ymin) *ymin= 0.0f;
555                 if (ymax) *ymax= 1.0f;
556         }
557 }
558
559 /* Calculate the extents of F-Curve's keyframes */
560 void calc_fcurve_range (FCurve *fcu, float *start, float *end, const short selOnly)
561 {
562         float min=999999999.0f, max=-999999999.0f;
563         short foundvert=0;
564
565         if (fcu->totvert) {
566                 if (fcu->bezt) {
567                         BezTriple *bezt_first= NULL, *bezt_last= NULL;
568                         
569                         /* get endpoint keyframes */
570                         get_fcurve_end_keyframes(fcu, &bezt_first, &bezt_last, selOnly);
571                         
572                         if (bezt_first) {
573                                 BLI_assert(bezt_last != NULL);
574                                 
575                                 min= MIN2(min, bezt_first->vec[1][0]);
576                                 max= MAX2(max, bezt_last->vec[1][0]);
577                         }
578                 }
579                 else if (fcu->fpt) {
580                         min= MIN2(min, fcu->fpt[0].vec[0]);
581                         max= MAX2(max, fcu->fpt[fcu->totvert-1].vec[0]);
582                 }
583                 
584                 foundvert=1;
585         }
586         
587         /* minimum length is 1 frame */
588         if (foundvert) {
589                 if (min == max) max += 1.0f;
590                 *start= min;
591                 *end= max;
592         }
593         else {
594                 *start= 0.0f;
595                 *end= 1.0f;
596         }
597 }
598
599 /* ----------------- Status Checks -------------------------- */
600
601 /* Are keyframes on F-Curve of any use? 
602  * Usability of keyframes refers to whether they should be displayed,
603  * and also whether they will have any influence on the final result.
604  */
605 short fcurve_are_keyframes_usable (FCurve *fcu)
606 {
607         /* F-Curve must exist */
608         if (fcu == NULL)
609                 return 0;
610                 
611         /* F-Curve must not have samples - samples are mutually exclusive of keyframes */
612         if (fcu->fpt)
613                 return 0;
614         
615         /* if it has modifiers, none of these should "drastically" alter the curve */
616         if (fcu->modifiers.first) {
617                 FModifier *fcm;
618                 
619                 /* check modifiers from last to first, as last will be more influential */
620                 // TODO: optionally, only check modifier if it is the active one...
621                 for (fcm = fcu->modifiers.last; fcm; fcm = fcm->prev) {
622                         /* ignore if muted/disabled */
623                         if (fcm->flag & (FMODIFIER_FLAG_DISABLED|FMODIFIER_FLAG_MUTED))
624                                 continue;
625                                 
626                         /* type checks */
627                         switch (fcm->type) {
628                                 /* clearly harmless - do nothing */
629                                 case FMODIFIER_TYPE_CYCLES:
630                                 case FMODIFIER_TYPE_STEPPED:
631                                 case FMODIFIER_TYPE_NOISE:
632                                         break;
633                                         
634                                 /* sometimes harmful - depending on whether they're "additive" or not */
635                                 case FMODIFIER_TYPE_GENERATOR:
636                                 {
637                                         FMod_Generator *data = (FMod_Generator *)fcm->data;
638                                         
639                                         if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0)
640                                                 return 0;
641                                 }
642                                         break;
643                                 case FMODIFIER_TYPE_FN_GENERATOR:
644                                 {
645                                         FMod_FunctionGenerator *data = (FMod_FunctionGenerator *)fcm->data;
646                                         
647                                         if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0)
648                                                 return 0;
649                                 }
650                                         break;
651                                         
652                                 /* always harmful - cannot allow */
653                                 default:
654                                         return 0;
655                         }
656                 }
657         }
658         
659         /* keyframes are usable */
660         return 1;
661 }
662
663 /* Can keyframes be added to F-Curve? 
664  * Keyframes can only be added if they are already visible
665  */
666 short fcurve_is_keyframable (FCurve *fcu)
667 {
668         /* F-Curve's keyframes must be "usable" (i.e. visible + have an effect on final result) */
669         if (fcurve_are_keyframes_usable(fcu) == 0)
670                 return 0;
671                 
672         /* F-Curve must currently be editable too */
673         if ( (fcu->flag & FCURVE_PROTECTED) || ((fcu->grp) && (fcu->grp->flag & AGRP_PROTECTED)) )
674                 return 0;
675         
676         /* F-Curve is keyframable */
677         return 1;
678 }
679
680 /* ***************************** Keyframe Column Tools ********************************* */
681
682 /* add a BezTriple to a column */
683 void bezt_add_to_cfra_elem (ListBase *lb, BezTriple *bezt)
684 {
685         CfraElem *ce, *cen;
686         
687         for (ce= lb->first; ce; ce= ce->next) {
688                 /* double key? */
689                 if (ce->cfra == bezt->vec[1][0]) {
690                         if (bezt->f2 & SELECT) ce->sel= bezt->f2;
691                         return;
692                 }
693                 /* should key be inserted before this column? */
694                 else if (ce->cfra > bezt->vec[1][0]) break;
695         }
696         
697         /* create a new column */
698         cen= MEM_callocN(sizeof(CfraElem), "add_to_cfra_elem"); 
699         if (ce) BLI_insertlinkbefore(lb, ce, cen);
700         else BLI_addtail(lb, cen);
701
702         cen->cfra= bezt->vec[1][0];
703         cen->sel= bezt->f2;
704 }
705
706 /* ***************************** Samples Utilities ******************************* */
707 /* Some utilities for working with FPoints (i.e. 'sampled' animation curve data, such as
708  * data imported from BVH/Mocap files), which are specialized for use with high density datasets,
709  * which BezTriples/Keyframe data are ill equipped to do.
710  */
711  
712  
713 /* Basic sampling callback which acts as a wrapper for evaluate_fcurve() 
714  *      'data' arg here is unneeded here...
715  */
716 float fcurve_samplingcb_evalcurve (FCurve *fcu, void *UNUSED(data), float evaltime)
717 {
718         /* assume any interference from drivers on the curve is intended... */
719         return evaluate_fcurve(fcu, evaltime);
720
721
722  
723 /* Main API function for creating a set of sampled curve data, given some callback function 
724  * used to retrieve the values to store.
725  */
726 void fcurve_store_samples (FCurve *fcu, void *data, int start, int end, FcuSampleFunc sample_cb)
727 {
728         FPoint *fpt, *new_fpt;
729         int cfra;
730         
731         /* sanity checks */
732         // TODO: make these tests report errors using reports not printf's
733         if ELEM(NULL, fcu, sample_cb) {
734                 printf("Error: No F-Curve with F-Curve Modifiers to Bake\n");
735                 return;
736         }
737         if (start >= end) {
738                 printf("Error: Frame range for Sampled F-Curve creation is inappropriate \n");
739                 return;
740         }
741         
742         /* set up sample data */
743         fpt= new_fpt= MEM_callocN(sizeof(FPoint)*(end-start+1), "FPoint Samples");
744         
745         /* use the sampling callback at 1-frame intervals from start to end frames */
746         for (cfra= start; cfra <= end; cfra++, fpt++) {
747                 fpt->vec[0]= (float)cfra;
748                 fpt->vec[1]= sample_cb(fcu, data, (float)cfra);
749         }
750         
751         /* free any existing sample/keyframe data on curve  */
752         if (fcu->bezt) MEM_freeN(fcu->bezt);
753         if (fcu->fpt) MEM_freeN(fcu->fpt);
754         
755         /* store the samples */
756         fcu->bezt= NULL;
757         fcu->fpt= new_fpt;
758         fcu->totvert= end - start + 1;
759 }
760
761 /* ***************************** F-Curve Sanity ********************************* */
762 /* The functions here are used in various parts of Blender, usually after some editing
763  * of keyframe data has occurred. They ensure that keyframe data is properly ordered and
764  * that the handles are correctly 
765  */
766
767 /* This function recalculates the handles of an F-Curve 
768  * If the BezTriples have been rearranged, sort them first before using this.
769  */
770 void calchandles_fcurve (FCurve *fcu)
771 {
772         BezTriple *bezt, *prev, *next;
773         int a= fcu->totvert;
774
775         /* Error checking:
776          *      - need at least two points
777          *      - need bezier keys
778          *      - only bezier-interpolation has handles (for now)
779          */
780         if (ELEM(NULL, fcu, fcu->bezt) || (a < 2) /*|| ELEM(fcu->ipo, BEZT_IPO_CONST, BEZT_IPO_LIN)*/) 
781                 return;
782         
783         /* get initial pointers */
784         bezt= fcu->bezt;
785         prev= NULL;
786         next= (bezt + 1);
787         
788         /* loop over all beztriples, adjusting handles */
789         while (a--) {
790                 /* clamp timing of handles to be on either side of beztriple */
791                 if (bezt->vec[0][0] > bezt->vec[1][0]) bezt->vec[0][0]= bezt->vec[1][0];
792                 if (bezt->vec[2][0] < bezt->vec[1][0]) bezt->vec[2][0]= bezt->vec[1][0];
793                 
794                 /* calculate auto-handles */
795                 calchandleNurb(bezt, prev, next, 1);    /* 1==special autohandle */
796                 
797                 /* for automatic ease in and out */
798                 if (ELEM(bezt->h1,HD_AUTO,HD_AUTO_ANIM) && ELEM(bezt->h2,HD_AUTO,HD_AUTO_ANIM)) {
799                         /* only do this on first or last beztriple */
800                         if ((a == 0) || (a == fcu->totvert-1)) {
801                                 /* set both handles to have same horizontal value as keyframe */
802                                 if (fcu->extend == FCURVE_EXTRAPOLATE_CONSTANT) {
803                                         bezt->vec[0][1]= bezt->vec[2][1]= bezt->vec[1][1];
804                                 }
805                         }
806                 }
807                 
808                 /* advance pointers for next iteration */
809                 prev= bezt;
810                 if (a == 1) next= NULL;
811                 else next++;
812                 bezt++;
813         }
814 }
815
816 /* Use when F-Curve with handles has changed
817  * It treats all BezTriples with the following rules:
818  *  - PHASE 1: do types have to be altered?
819  *              -> Auto handles: become aligned when selection status is NOT(000 || 111)
820  *              -> Vector handles: become 'nothing' when (one half selected AND other not)
821  *  - PHASE 2: recalculate handles
822 */
823 void testhandles_fcurve (FCurve *fcu, const short use_handle)
824 {
825         BezTriple *bezt;
826         unsigned int a;
827
828         /* only beztriples have handles (bpoints don't though) */
829         if ELEM(NULL, fcu, fcu->bezt)
830                 return;
831         
832         /* loop over beztriples */
833         for (a=0, bezt=fcu->bezt; a < fcu->totvert; a++, bezt++) {
834                 short flag= 0;
835                 
836                 /* flag is initialised as selection status
837                  * of beztriple control-points (labelled 0,1,2)
838                  */
839                 if (bezt->f2 & SELECT) flag |= (1<<1); // == 2
840                 if(use_handle == FALSE) {
841                         if(flag & 2) {
842                                 flag |= (1<<0) | (1<<2);
843                         }
844                 }
845                 else {
846                         if (bezt->f1 & SELECT) flag |= (1<<0); // == 1
847                         if (bezt->f3 & SELECT) flag |= (1<<2); // == 4
848                 }
849                 
850                 /* one or two handles selected only */
851                 if (ELEM(flag, 0, 7)==0) {
852                         /* auto handles become aligned */
853                         if (ELEM(bezt->h1, HD_AUTO, HD_AUTO_ANIM))
854                                 bezt->h1= HD_ALIGN;
855                         if (ELEM(bezt->h2, HD_AUTO, HD_AUTO_ANIM))
856                                 bezt->h2= HD_ALIGN;
857                         
858                         /* vector handles become 'free' when only one half selected */
859                         if (bezt->h1==HD_VECT) {
860                                 /* only left half (1 or 2 or 1+2) */
861                                 if (flag < 4) 
862                                         bezt->h1= 0;
863                         }
864                         if (bezt->h2==HD_VECT) {
865                                 /* only right half (4 or 2+4) */
866                                 if (flag > 3) 
867                                         bezt->h2= 0;
868                         }
869                 }
870         }
871
872         /* recalculate handles */
873         calchandles_fcurve(fcu);
874 }
875
876 /* This function sorts BezTriples so that they are arranged in chronological order,
877  * as tools working on F-Curves expect that the BezTriples are in order.
878  */
879 void sort_time_fcurve (FCurve *fcu)
880 {
881         short ok= 1;
882         
883         /* keep adjusting order of beztriples until nothing moves (bubble-sort) */
884         while (ok) {
885                 ok= 0;
886                 
887                 /* currently, will only be needed when there are beztriples */
888                 if (fcu->bezt) {
889                         BezTriple *bezt;
890                         unsigned int a;
891                         
892                         /* loop over ALL points to adjust position in array and recalculate handles */
893                         for (a=0, bezt=fcu->bezt; a < fcu->totvert; a++, bezt++) {
894                                 /* check if thee's a next beztriple which we could try to swap with current */
895                                 if (a < (fcu->totvert-1)) {
896                                         /* swap if one is after the other (and indicate that order has changed) */
897                                         if (bezt->vec[1][0] > (bezt+1)->vec[1][0]) {
898                                                 SWAP(BezTriple, *bezt, *(bezt+1));
899                                                 ok= 1;
900                                         }
901                                         
902                                         /* if either one of both of the points exceeds crosses over the keyframe time... */
903                                         if ( (bezt->vec[0][0] > bezt->vec[1][0]) && (bezt->vec[2][0] < bezt->vec[1][0]) ) {
904                                                 /* swap handles if they have switched sides for some reason */
905                                                 SWAP(float, bezt->vec[0][0], bezt->vec[2][0]);
906                                                 SWAP(float, bezt->vec[0][1], bezt->vec[2][1]);
907                                         }
908                                         else {
909                                                 /* clamp handles */
910                                                 if (bezt->vec[0][0] > bezt->vec[1][0]) 
911                                                         bezt->vec[0][0]= bezt->vec[1][0];
912                                                 if (bezt->vec[2][0] < bezt->vec[1][0]) 
913                                                         bezt->vec[2][0]= bezt->vec[1][0];
914                                         }
915                                 }
916                         }
917                 }
918         }
919 }
920
921 /* This function tests if any BezTriples are out of order, thus requiring a sort */
922 short test_time_fcurve (FCurve *fcu)
923 {
924         unsigned int a;
925         
926         /* sanity checks */
927         if (fcu == NULL)
928                 return 0;
929         
930         /* currently, only need to test beztriples */
931         if (fcu->bezt) {
932                 BezTriple *bezt;
933                 
934                 /* loop through all BezTriples, stopping when one exceeds the one after it */
935                 for (a=0, bezt= fcu->bezt; a < (fcu->totvert - 1); a++, bezt++) {
936                         if (bezt->vec[1][0] > (bezt+1)->vec[1][0])
937                                 return 1;
938                 }
939         }
940         else if (fcu->fpt) {
941                 FPoint *fpt;
942                 
943                 /* loop through all FPoints, stopping when one exceeds the one after it */
944                 for (a=0, fpt= fcu->fpt; a < (fcu->totvert - 1); a++, fpt++) {
945                         if (fpt->vec[0] > (fpt+1)->vec[0])
946                                 return 1;
947                 }
948         }
949         
950         /* none need any swapping */
951         return 0;
952 }
953
954 /* ***************************** Drivers ********************************* */
955
956 /* Driver Variables --------------------------- */
957
958 /* TypeInfo for Driver Variables (dvti) */
959 typedef struct DriverVarTypeInfo {
960         /* evaluation callback */
961         float (*get_value)(ChannelDriver *driver, DriverVar *dvar);
962         
963         /* allocation of target slots */
964         int num_targets;                                                /* number of target slots required */
965         const char *target_names[MAX_DRIVER_TARGETS];   /* UI names that should be given to the slots */
966         int target_flags[MAX_DRIVER_TARGETS];   /* flags defining the requirements for each slot */
967 } DriverVarTypeInfo;
968
969 /* Macro to begin definitions */
970 #define BEGIN_DVAR_TYPEDEF(type) \
971         {
972         
973 /* Macro to end definitions */
974 #define END_DVAR_TYPEDEF \
975         }
976
977 /* ......... */
978
979 static ID *dtar_id_ensure_proxy_from(ID *id)
980 {
981         if (id && GS(id->name)==ID_OB && ((Object *)id)->proxy_from)
982                 return (ID *)(((Object *)id)->proxy_from);
983         return id;
984 }
985
986 /* Helper function to obtain a value using RNA from the specified source (for evaluating drivers) */
987 static float dtar_get_prop_val (ChannelDriver *driver, DriverTarget *dtar)
988 {
989         PointerRNA id_ptr, ptr;
990         PropertyRNA *prop;
991         ID *id;
992         int index;
993         float value= 0.0f;
994         
995         /* sanity check */
996         if ELEM(NULL, driver, dtar)
997                 return 0.0f;
998         
999         id= dtar_id_ensure_proxy_from(dtar->id);
1000         
1001         /* error check for missing pointer... */
1002         // TODO: tag the specific target too as having issues
1003         if (id == NULL) {
1004                 printf("Error: driver has an invalid target to use \n");
1005                 if (G.f & G_DEBUG) printf("\tpath = %s\n", dtar->rna_path);
1006                 driver->flag |= DRIVER_FLAG_INVALID;
1007                 return 0.0f;
1008         }
1009         
1010         /* get RNA-pointer for the ID-block given in target */
1011         RNA_id_pointer_create(id, &id_ptr);
1012         
1013         /* get property to read from, and get value as appropriate */
1014         if (RNA_path_resolve_full(&id_ptr, dtar->rna_path, &ptr, &prop, &index)) {
1015                 if(RNA_property_array_check(prop)) {
1016                         /* array */
1017                         if (index < RNA_property_array_length(&ptr, prop)) {    
1018                                 switch (RNA_property_type(prop)) {
1019                                 case PROP_BOOLEAN:
1020                                         value= (float)RNA_property_boolean_get_index(&ptr, prop, index);
1021                                         break;
1022                                 case PROP_INT:
1023                                         value= (float)RNA_property_int_get_index(&ptr, prop, index);
1024                                         break;
1025                                 case PROP_FLOAT:
1026                                         value= RNA_property_float_get_index(&ptr, prop, index);
1027                                         break;
1028                                 default:
1029                                         break;
1030                                 }
1031                         }
1032                 }
1033                 else {
1034                         /* not an array */
1035                         switch (RNA_property_type(prop)) {
1036                         case PROP_BOOLEAN:
1037                                 value= (float)RNA_property_boolean_get(&ptr, prop);
1038                                 break;
1039                         case PROP_INT:
1040                                 value= (float)RNA_property_int_get(&ptr, prop);
1041                                 break;
1042                         case PROP_FLOAT:
1043                                 value= RNA_property_float_get(&ptr, prop);
1044                                 break;
1045                         case PROP_ENUM:
1046                                 value= (float)RNA_property_enum_get(&ptr, prop);
1047                                 break;
1048                         default:
1049                                 break;
1050                         }
1051                 }
1052
1053         }
1054         else {
1055                 if (G.f & G_DEBUG)
1056                         printf("Driver Evaluation Error: cannot resolve target for %s -> %s \n", id->name, dtar->rna_path);
1057                 
1058                 driver->flag |= DRIVER_FLAG_INVALID;
1059                 return 0.0f;
1060         }
1061         
1062         return value;
1063 }
1064
1065 /* Helper function to obtain a pointer to a Pose Channel (for evaluating drivers) */
1066 static bPoseChannel *dtar_get_pchan_ptr (ChannelDriver *driver, DriverTarget *dtar)
1067 {
1068         ID *id;
1069         /* sanity check */
1070         if ELEM(NULL, driver, dtar)
1071                 return NULL;
1072
1073         id= dtar_id_ensure_proxy_from(dtar->id);
1074
1075         /* check if the ID here is a valid object */
1076         if (id && GS(id->name)) {
1077                 Object *ob= (Object *)id;
1078                 
1079                 /* get pose, and subsequently, posechannel */
1080                 return get_pose_channel(ob->pose, dtar->pchan_name);
1081         }
1082         else {
1083                 /* cannot find a posechannel this way */
1084                 return NULL;
1085         }
1086 }
1087
1088 /* ......... */
1089
1090 /* evaluate 'single prop' driver variable */
1091 static float dvar_eval_singleProp (ChannelDriver *driver, DriverVar *dvar)
1092 {
1093         /* just evaluate the first target slot */
1094         return dtar_get_prop_val(driver, &dvar->targets[0]);
1095 }
1096
1097 /* evaluate 'rotation difference' driver variable */
1098 static float dvar_eval_rotDiff (ChannelDriver *driver, DriverVar *dvar)
1099 {
1100         bPoseChannel *pchan, *pchan2;
1101         float q1[4], q2[4], quat[4], angle;
1102         
1103         /* get pose channels, and check if we've got two */
1104         pchan= dtar_get_pchan_ptr(driver, &dvar->targets[0]);
1105         pchan2= dtar_get_pchan_ptr(driver, &dvar->targets[1]);
1106         
1107         if (ELEM(NULL, pchan, pchan2)) {
1108                 /* disable this driver, since it doesn't work correctly... */
1109                 driver->flag |= DRIVER_FLAG_INVALID;
1110                 
1111                 /* check what the error was */
1112                 if ((pchan == NULL) && (pchan2 == NULL))
1113                         printf("Driver Evaluation Error: Rotational difference failed - first 2 targets invalid \n");
1114                 else if (pchan == NULL)
1115                         printf("Driver Evaluation Error: Rotational difference failed - first target not valid PoseChannel \n");
1116                 else if (pchan2 == NULL)
1117                         printf("Driver Evaluation Error: Rotational difference failed - second target not valid PoseChannel \n");
1118                         
1119                 /* stop here... */
1120                 return 0.0f;
1121         }                       
1122         
1123         /* use the final posed locations */
1124         mat4_to_quat(q1, pchan->pose_mat);
1125         mat4_to_quat(q2, pchan2->pose_mat);
1126         
1127         invert_qt(q1);
1128         mul_qt_qtqt(quat, q1, q2);
1129         angle = 2.0f * (saacos(quat[0]));
1130         angle= ABS(angle);
1131         
1132         return (angle > (float)M_PI) ? (float)((2.0f * (float)M_PI) - angle) : (float)(angle);
1133 }
1134
1135 /* evaluate 'location difference' driver variable */
1136 // TODO: this needs to take into account space conversions...
1137 static float dvar_eval_locDiff (ChannelDriver *driver, DriverVar *dvar)
1138 {
1139         float loc1[3] = {0.0f,0.0f,0.0f};
1140         float loc2[3] = {0.0f,0.0f,0.0f};
1141         
1142         /* get two location values */
1143         // NOTE: for now, these are all just worldspace
1144         DRIVER_TARGETS_USED_LOOPER(dvar)
1145         {
1146                 /* get pointer to loc values to store in */
1147                 Object *ob= (Object *)dtar_id_ensure_proxy_from(dtar->id);
1148                 bPoseChannel *pchan;
1149                 float tmp_loc[3];
1150                 
1151                 /* check if this target has valid data */
1152                 if ((ob == NULL) || (GS(ob->id.name) != ID_OB)) {
1153                         /* invalid target, so will not have enough targets */
1154                         driver->flag |= DRIVER_FLAG_INVALID;
1155                         return 0.0f;
1156                 }
1157                 
1158                 /* try to get posechannel */
1159                 pchan= get_pose_channel(ob->pose, dtar->pchan_name);
1160                 
1161                 /* check if object or bone */
1162                 if (pchan) {
1163                         /* bone */
1164                         if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1165                                 if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1166                                         float mat[4][4];
1167                                         
1168                                         /* extract transform just like how the constraints do it! */
1169                                         copy_m4_m4(mat, pchan->pose_mat);
1170                                         constraint_mat_convertspace(ob, pchan, mat, CONSTRAINT_SPACE_POSE, CONSTRAINT_SPACE_LOCAL);
1171                                         
1172                                         /* ... and from that, we get our transform */
1173                                         VECCOPY(tmp_loc, mat[3]);
1174                                 }
1175                                 else {
1176                                         /* transform space (use transform values directly) */
1177                                         VECCOPY(tmp_loc, pchan->loc);
1178                                 }
1179                         }
1180                         else {
1181                                 /* convert to worldspace */
1182                                 VECCOPY(tmp_loc, pchan->pose_head);
1183                                 mul_m4_v3(ob->obmat, tmp_loc);
1184                         }
1185                 }
1186                 else {
1187                         /* object */
1188                         if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1189                                 if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1190                                         // XXX: this should practically be the same as transform space...
1191                                         float mat[4][4];
1192                                         
1193                                         /* extract transform just like how the constraints do it! */
1194                                         copy_m4_m4(mat, ob->obmat);
1195                                         constraint_mat_convertspace(ob, NULL, mat, CONSTRAINT_SPACE_WORLD, CONSTRAINT_SPACE_LOCAL);
1196                                         
1197                                         /* ... and from that, we get our transform */
1198                                         VECCOPY(tmp_loc, mat[3]);
1199                                 }
1200                                 else {
1201                                         /* transform space (use transform values directly) */
1202                                         VECCOPY(tmp_loc, ob->loc);
1203                                 }
1204                         }
1205                         else {
1206                                 /* worldspace */
1207                                 VECCOPY(tmp_loc, ob->obmat[3]); 
1208                         }
1209                 }
1210                 
1211                 /* copy the location to the right place */
1212                 if (tarIndex) {
1213                         VECCOPY(loc2, tmp_loc);
1214                 }
1215                 else {
1216                         VECCOPY(loc1, tmp_loc);
1217                 }
1218         }
1219         DRIVER_TARGETS_LOOPER_END
1220         
1221         
1222         /* if we're still here, there should now be two targets to use,
1223          * so just take the length of the vector between these points 
1224          */
1225         return len_v3v3(loc1, loc2);
1226 }
1227
1228 /* evaluate 'transform channel' driver variable */
1229 static float dvar_eval_transChan (ChannelDriver *driver, DriverVar *dvar)
1230 {
1231         DriverTarget *dtar= &dvar->targets[0];
1232         Object *ob= (Object *)dtar_id_ensure_proxy_from(dtar->id);
1233         bPoseChannel *pchan;
1234         float mat[4][4];
1235         float oldEul[3] = {0.0f,0.0f,0.0f};
1236         short useEulers=0, rotOrder=ROT_MODE_EUL;
1237         
1238         /* check if this target has valid data */
1239         if ((ob == NULL) || (GS(ob->id.name) != ID_OB)) {
1240                 /* invalid target, so will not have enough targets */
1241                 driver->flag |= DRIVER_FLAG_INVALID;
1242                 return 0.0f;
1243         }
1244         
1245         /* try to get posechannel */
1246         pchan= get_pose_channel(ob->pose, dtar->pchan_name);
1247         
1248         /* check if object or bone, and get transform matrix accordingly 
1249          *      - "useEulers" code is used to prevent the problems associated with non-uniqueness
1250          *        of euler decomposition from matrices [#20870]
1251          *      - localspace is for [#21384], where parent results are not wanted
1252          *        but local-consts is for all the common "corrective-shapes-for-limbs" situations
1253          */
1254         if (pchan) {
1255                 /* bone */
1256                 if (pchan->rotmode > 0) {
1257                         VECCOPY(oldEul, pchan->eul);
1258                         rotOrder= pchan->rotmode;
1259                         useEulers = 1;
1260                 }
1261                 
1262                 if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1263                         if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1264                                 /* just like how the constraints do it! */
1265                                 copy_m4_m4(mat, pchan->pose_mat);
1266                                 constraint_mat_convertspace(ob, pchan, mat, CONSTRAINT_SPACE_POSE, CONSTRAINT_SPACE_LOCAL);
1267                         }
1268                         else {
1269                                 /* specially calculate local matrix, since chan_mat is not valid 
1270                                  * since it stores delta transform of pose_mat so that deforms work
1271                                  * so it cannot be used here for "transform" space
1272                                  */
1273                                 pchan_to_mat4(pchan, mat);
1274                         }
1275                 }
1276                 else {
1277                         /* worldspace matrix */
1278                         mul_m4_m4m4(mat, pchan->pose_mat, ob->obmat);
1279                 }
1280         }
1281         else {
1282                 /* object */
1283                 if (ob->rotmode > 0) {
1284                         VECCOPY(oldEul, ob->rot);
1285                         rotOrder= ob->rotmode;
1286                         useEulers = 1;
1287                 }
1288                 
1289                 if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1290                         if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1291                                 /* just like how the constraints do it! */
1292                                 copy_m4_m4(mat, ob->obmat);
1293                                 constraint_mat_convertspace(ob, NULL, mat, CONSTRAINT_SPACE_WORLD, CONSTRAINT_SPACE_LOCAL);
1294                         }
1295                         else {
1296                                 /* transforms to matrix */
1297                                 object_to_mat4(ob, mat);
1298                         }
1299                 }
1300                 else {
1301                         /* worldspace matrix - just the good-old one */
1302                         copy_m4_m4(mat, ob->obmat);
1303                 }
1304         }
1305         
1306         /* check which transform */
1307         if (dtar->transChan >= MAX_DTAR_TRANSCHAN_TYPES) {
1308                 /* not valid channel */
1309                 return 0.0f;
1310         }
1311         else if (dtar->transChan >= DTAR_TRANSCHAN_SCALEX) {
1312                 /* extract scale, and choose the right axis */
1313                 float scale[3];
1314                 
1315                 mat4_to_size(scale, mat);
1316                 return scale[dtar->transChan - DTAR_TRANSCHAN_SCALEX];
1317         }
1318         else if (dtar->transChan >= DTAR_TRANSCHAN_ROTX) {
1319                 /* extract rotation as eulers (if needed) 
1320                  *      - definitely if rotation order isn't eulers already
1321                  *      - if eulers, then we have 2 options:
1322                  *              a) decompose transform matrix as required, then try to make eulers from
1323                  *                 there compatible with original values
1324                  *              b) [NOT USED] directly use the original values (no decomposition) 
1325                  *                      - only an option for "transform space", if quality is really bad with a)
1326                  */
1327                 float eul[3];
1328                 
1329                 mat4_to_eulO(eul, rotOrder, mat);
1330                 
1331                 if (useEulers) {
1332                         compatible_eul(eul, oldEul);
1333                 }
1334                 
1335                 return eul[dtar->transChan - DTAR_TRANSCHAN_ROTX];
1336         }
1337         else {
1338                 /* extract location and choose right axis */
1339                 return mat[3][dtar->transChan];
1340         }
1341 }
1342
1343 /* ......... */
1344
1345 /* Table of Driver Varaiable Type Info Data */
1346 static DriverVarTypeInfo dvar_types[MAX_DVAR_TYPES] = {
1347         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_SINGLE_PROP)
1348                 dvar_eval_singleProp, /* eval callback */
1349                 1, /* number of targets used */
1350                 {"Property"}, /* UI names for targets */
1351                 {0} /* flags */
1352         END_DVAR_TYPEDEF,
1353         
1354         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_ROT_DIFF)
1355                 dvar_eval_rotDiff, /* eval callback */
1356                 2, /* number of targets used */
1357                 {"Bone 1", "Bone 2"}, /* UI names for targets */
1358                 {DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY, DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY} /* flags */
1359         END_DVAR_TYPEDEF,
1360         
1361         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_LOC_DIFF)
1362                 dvar_eval_locDiff, /* eval callback */
1363                 2, /* number of targets used */
1364                 {"Object/Bone 1", "Object/Bone 2"}, /* UI names for targets */
1365                 {DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY, DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY} /* flags */
1366         END_DVAR_TYPEDEF,
1367         
1368         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_TRANSFORM_CHAN)
1369                 dvar_eval_transChan, /* eval callback */
1370                 1, /* number of targets used */
1371                 {"Object/Bone"}, /* UI names for targets */
1372                 {DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY} /* flags */
1373         END_DVAR_TYPEDEF,
1374 };
1375
1376 /* Get driver variable typeinfo */
1377 static DriverVarTypeInfo *get_dvar_typeinfo (int type)
1378 {
1379         /* check if valid type */
1380         if ((type >= 0) && (type < MAX_DVAR_TYPES))
1381                 return &dvar_types[type];
1382         else
1383                 return NULL;
1384 }
1385
1386 /* Driver API --------------------------------- */
1387
1388 /* This frees the driver variable itself */
1389 void driver_free_variable (ChannelDriver *driver, DriverVar *dvar)
1390 {
1391         /* sanity checks */
1392         if (dvar == NULL)
1393                 return;
1394                 
1395         /* free target vars 
1396          *      - need to go over all of them, not just up to the ones that are used
1397          *        currently, since there may be some lingering RNA paths from 
1398          *        previous users needing freeing
1399          */
1400         DRIVER_TARGETS_LOOPER(dvar) 
1401         {
1402                 /* free RNA path if applicable */
1403                 if (dtar->rna_path)
1404                         MEM_freeN(dtar->rna_path);
1405         }
1406         DRIVER_TARGETS_LOOPER_END
1407         
1408         /* remove the variable from the driver */
1409         if (driver)
1410                 BLI_freelinkN(&driver->variables, dvar);
1411         else
1412                 MEM_freeN(dvar);
1413
1414 #ifdef WITH_PYTHON
1415         /* since driver variables are cached, the expression needs re-compiling too */
1416         if(driver->type==DRIVER_TYPE_PYTHON)
1417                 driver->flag |= DRIVER_FLAG_RENAMEVAR;
1418 #endif
1419 }
1420
1421 /* Change the type of driver variable */
1422 void driver_change_variable_type (DriverVar *dvar, int type)
1423 {
1424         DriverVarTypeInfo *dvti= get_dvar_typeinfo(type);
1425         
1426         /* sanity check */
1427         if (ELEM(NULL, dvar, dvti))
1428                 return;
1429                 
1430         /* set the new settings */
1431         dvar->type= type;
1432         dvar->num_targets= dvti->num_targets;
1433         
1434         /* make changes to the targets based on the defines for these types 
1435          * NOTE: only need to make sure the ones we're using here are valid...
1436          */
1437         DRIVER_TARGETS_USED_LOOPER(dvar)
1438         {
1439                 int flags = dvti->target_flags[tarIndex];
1440                 
1441                 /* store the flags */
1442                 dtar->flag = flags;
1443                 
1444                 /* object ID types only, or idtype not yet initialised*/
1445                 if ((flags & DTAR_FLAG_ID_OB_ONLY) || (dtar->idtype == 0))
1446                         dtar->idtype= ID_OB;
1447         }
1448         DRIVER_TARGETS_LOOPER_END
1449 }
1450
1451 /* Add a new driver variable */
1452 DriverVar *driver_add_new_variable (ChannelDriver *driver)
1453 {
1454         DriverVar *dvar;
1455         
1456         /* sanity checks */
1457         if (driver == NULL)
1458                 return NULL;
1459                 
1460         /* make a new variable */
1461         dvar= MEM_callocN(sizeof(DriverVar), "DriverVar");
1462         BLI_addtail(&driver->variables, dvar);
1463         
1464         /* give the variable a 'unique' name */
1465         strcpy(dvar->name, "var");
1466         BLI_uniquename(&driver->variables, dvar, "var", '_', offsetof(DriverVar, name), sizeof(dvar->name));
1467         
1468         /* set the default type to 'single prop' */
1469         driver_change_variable_type(dvar, DVAR_TYPE_SINGLE_PROP);
1470         
1471 #ifdef WITH_PYTHON
1472         /* since driver variables are cached, the expression needs re-compiling too */
1473         if (driver->type==DRIVER_TYPE_PYTHON)
1474                 driver->flag |= DRIVER_FLAG_RENAMEVAR;
1475 #endif
1476
1477         /* return the target */
1478         return dvar;
1479 }
1480
1481 /* This frees the driver itself */
1482 void fcurve_free_driver(FCurve *fcu)
1483 {
1484         ChannelDriver *driver;
1485         DriverVar *dvar, *dvarn;
1486         
1487         /* sanity checks */
1488         if ELEM(NULL, fcu, fcu->driver)
1489                 return;
1490         driver= fcu->driver;
1491         
1492         /* free driver targets */
1493         for (dvar= driver->variables.first; dvar; dvar= dvarn) {
1494                 dvarn= dvar->next;
1495                 driver_free_variable(driver, dvar);
1496         }
1497
1498 #ifdef WITH_PYTHON
1499         /* free compiled driver expression */
1500         if (driver->expr_comp)
1501                 BPY_DECREF(driver->expr_comp);
1502 #endif
1503
1504         /* free driver itself, then set F-Curve's point to this to NULL (as the curve may still be used) */
1505         MEM_freeN(driver);
1506         fcu->driver= NULL;
1507 }
1508
1509 /* This makes a copy of the given driver */
1510 ChannelDriver *fcurve_copy_driver (ChannelDriver *driver)
1511 {
1512         ChannelDriver *ndriver;
1513         DriverVar *dvar;
1514         
1515         /* sanity checks */
1516         if (driver == NULL)
1517                 return NULL;
1518                 
1519         /* copy all data */
1520         ndriver= MEM_dupallocN(driver);
1521         ndriver->expr_comp= NULL;
1522         
1523         /* copy variables */
1524         ndriver->variables.first= ndriver->variables.last= NULL;
1525         BLI_duplicatelist(&ndriver->variables, &driver->variables);
1526         
1527         for (dvar= ndriver->variables.first; dvar; dvar= dvar->next) {  
1528                 /* need to go over all targets so that we don't leave any dangling paths */
1529                 DRIVER_TARGETS_LOOPER(dvar) 
1530                 {       
1531                         /* make a copy of target's rna path if available */
1532                         if (dtar->rna_path)
1533                                 dtar->rna_path = MEM_dupallocN(dtar->rna_path);
1534                 }
1535                 DRIVER_TARGETS_LOOPER_END
1536         }
1537         
1538         /* return the new driver */
1539         return ndriver;
1540 }
1541
1542 /* Driver Evaluation -------------------------- */
1543
1544 /* Evaluate a Driver Variable to get a value that contributes to the final */
1545 float driver_get_variable_value (ChannelDriver *driver, DriverVar *dvar)
1546 {
1547         DriverVarTypeInfo *dvti;
1548
1549         /* sanity check */
1550         if (ELEM(NULL, driver, dvar))
1551                 return 0.0f;
1552         
1553         /* call the relevant callbacks to get the variable value 
1554          * using the variable type info, storing the obtained value
1555          * in dvar->curval so that drivers can be debugged
1556          */
1557         dvti= get_dvar_typeinfo(dvar->type);
1558         
1559         if (dvti && dvti->get_value)
1560                 dvar->curval= dvti->get_value(driver, dvar);
1561         else
1562                 dvar->curval= 0.0f;
1563         
1564         return dvar->curval;
1565 }
1566
1567 /* Evaluate an Channel-Driver to get a 'time' value to use instead of "evaltime"
1568  *      - "evaltime" is the frame at which F-Curve is being evaluated
1569  *      - has to return a float value 
1570  */
1571 static float evaluate_driver (ChannelDriver *driver, float UNUSED(evaltime))
1572 {
1573         DriverVar *dvar;
1574         
1575         /* check if driver can be evaluated */
1576         if (driver->flag & DRIVER_FLAG_INVALID)
1577                 return 0.0f;
1578         
1579         switch (driver->type) {
1580                 case DRIVER_TYPE_AVERAGE: /* average values of driver targets */
1581                 case DRIVER_TYPE_SUM: /* sum values of driver targets */
1582                 {
1583                         /* check how many variables there are first (i.e. just one?) */
1584                         if (driver->variables.first == driver->variables.last) {
1585                                 /* just one target, so just use that */
1586                                 dvar= driver->variables.first;
1587                                 driver->curval= driver_get_variable_value(driver, dvar);
1588                         }
1589                         else {
1590                                 /* more than one target, so average the values of the targets */
1591                                 float value = 0.0f;
1592                                 int tot = 0;
1593                                 
1594                                 /* loop through targets, adding (hopefully we don't get any overflow!) */
1595                                 for (dvar= driver->variables.first; dvar; dvar=dvar->next) {
1596                                         value += driver_get_variable_value(driver, dvar);
1597                                         tot++;
1598                                 }
1599                                 
1600                                 /* perform operations on the total if appropriate */
1601                                 if (driver->type == DRIVER_TYPE_AVERAGE)
1602                                         driver->curval= (value / (float)tot);
1603                                 else
1604                                         driver->curval= value;
1605                         }
1606                 }
1607                         break;
1608                         
1609                 case DRIVER_TYPE_MIN: /* smallest value */
1610                 case DRIVER_TYPE_MAX: /* largest value */
1611                 {
1612                         float value = 0.0f;
1613                         
1614                         /* loop through the variables, getting the values and comparing them to existing ones */
1615                         for (dvar= driver->variables.first; dvar; dvar= dvar->next) {
1616                                 /* get value */
1617                                 float tmp_val= driver_get_variable_value(driver, dvar);
1618                                 
1619                                 /* store this value if appropriate */
1620                                 if (dvar->prev) {
1621                                         /* check if greater/smaller than the baseline */
1622                                         if (driver->type == DRIVER_TYPE_MAX) {
1623                                                 /* max? */
1624                                                 if (tmp_val > value) 
1625                                                         value= tmp_val;
1626                                         }
1627                                         else {
1628                                                 /* min? */
1629                                                 if (tmp_val < value) 
1630                                                         value= tmp_val;
1631                                         }
1632                                 }
1633                                 else {
1634                                         /* first item - make this the baseline for comparisons */
1635                                         value= tmp_val;
1636                                 }
1637                         }
1638                         
1639                         /* store value in driver */
1640                         driver->curval= value;
1641                 }
1642                         break;
1643                         
1644                 case DRIVER_TYPE_PYTHON: /* expression */
1645                 {
1646 #ifdef WITH_PYTHON
1647                         /* check for empty or invalid expression */
1648                         if ( (driver->expression[0] == '\0') ||
1649                                  (driver->flag & DRIVER_FLAG_INVALID) )
1650                         {
1651                                 driver->curval= 0.0f;
1652                         }
1653                         else
1654                         {
1655                                 /* this evaluates the expression using Python,and returns its result:
1656                                  *      - on errors it reports, then returns 0.0f
1657                                  */
1658                                 driver->curval= BPY_driver_exec(driver);
1659                         }
1660 #endif /* WITH_PYTHON*/
1661                 }
1662                         break;
1663                 
1664                 default:
1665                 {
1666                         /* special 'hack' - just use stored value 
1667                          *      This is currently used as the mechanism which allows animated settings to be able
1668                          *      to be changed via the UI.
1669                          */
1670                 }
1671         }
1672         
1673         /* return value for driver */
1674         return driver->curval;
1675 }
1676
1677 /* ***************************** Curve Calculations ********************************* */
1678
1679 /* The total length of the handles is not allowed to be more
1680  * than the horizontal distance between (v1-v4).
1681  * This is to prevent curve loops.
1682 */
1683 void correct_bezpart (float *v1, float *v2, float *v3, float *v4)
1684 {
1685         float h1[2], h2[2], len1, len2, len, fac;
1686         
1687         /* calculate handle deltas */
1688         h1[0]= v1[0] - v2[0];
1689         h1[1]= v1[1] - v2[1];
1690         
1691         h2[0]= v4[0] - v3[0];
1692         h2[1]= v4[1] - v3[1];
1693         
1694         /* calculate distances: 
1695          *      - len   = span of time between keyframes 
1696          *      - len1  = length of handle of start key
1697          *      - len2  = length of handle of end key
1698          */
1699         len= v4[0]- v1[0];
1700         len1= (float)fabs(h1[0]);
1701         len2= (float)fabs(h2[0]);
1702         
1703         /* if the handles have no length, no need to do any corrections */
1704         if ((len1+len2) == 0.0f) 
1705                 return;
1706                 
1707         /* the two handles cross over each other, so force them
1708          * apart using the proportion they overlap 
1709          */
1710         if ((len1+len2) > len) {
1711                 fac= len / (len1+len2);
1712                 
1713                 v2[0]= (v1[0] - fac*h1[0]);
1714                 v2[1]= (v1[1] - fac*h1[1]);
1715                 
1716                 v3[0]= (v4[0] - fac*h2[0]);
1717                 v3[1]= (v4[1] - fac*h2[1]);
1718         }
1719 }
1720
1721 /* find root ('zero') */
1722 static int findzero (float x, float q0, float q1, float q2, float q3, float *o)
1723 {
1724         double c0, c1, c2, c3, a, b, c, p, q, d, t, phi;
1725         int nr= 0;
1726
1727         c0= q0 - x;
1728         c1= 3.0f * (q1 - q0);
1729         c2= 3.0f * (q0 - 2.0f*q1 + q2);
1730         c3= q3 - q0 + 3.0f * (q1 - q2);
1731         
1732         if (c3 != 0.0) {
1733                 a= c2/c3;
1734                 b= c1/c3;
1735                 c= c0/c3;
1736                 a= a/3;
1737                 
1738                 p= b/3 - a*a;
1739                 q= (2*a*a*a - a*b + c) / 2;
1740                 d= q*q + p*p*p;
1741                 
1742                 if (d > 0.0) {
1743                         t= sqrt(d);
1744                         o[0]= (float)(sqrt3d(-q+t) + sqrt3d(-q-t) - a);
1745                         
1746                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
1747                         else return 0;
1748                 }
1749                 else if (d == 0.0) {
1750                         t= sqrt3d(-q);
1751                         o[0]= (float)(2*t - a);
1752                         
1753                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
1754                         o[nr]= (float)(-t-a);
1755                         
1756                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr+1;
1757                         else return nr;
1758                 }
1759                 else {
1760                         phi= acos(-q / sqrt(-(p*p*p)));
1761                         t= sqrt(-p);
1762                         p= cos(phi/3);
1763                         q= sqrt(3 - 3*p*p);
1764                         o[0]= (float)(2*t*p - a);
1765                         
1766                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
1767                         o[nr]= (float)(-t * (p + q) - a);
1768                         
1769                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) nr++;
1770                         o[nr]= (float)(-t * (p - q) - a);
1771                         
1772                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr+1;
1773                         else return nr;
1774                 }
1775         }
1776         else {
1777                 a=c2;
1778                 b=c1;
1779                 c=c0;
1780                 
1781                 if (a != 0.0) {
1782                         // discriminant
1783                         p= b*b - 4*a*c;
1784                         
1785                         if (p > 0) {
1786                                 p= sqrt(p);
1787                                 o[0]= (float)((-b-p) / (2 * a));
1788                                 
1789                                 if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
1790                                 o[nr]= (float)((-b+p)/(2*a));
1791                                 
1792                                 if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr+1;
1793                                 else return nr;
1794                         }
1795                         else if (p == 0) {
1796                                 o[0]= (float)(-b / (2 * a));
1797                                 if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
1798                                 else return 0;
1799                         }
1800                 }
1801                 else if (b != 0.0) {
1802                         o[0]= (float)(-c/b);
1803                         
1804                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
1805                         else return 0;
1806                 }
1807                 else if (c == 0.0) {
1808                         o[0]= 0.0;
1809                         return 1;
1810                 }
1811                 
1812                 return 0;       
1813         }
1814 }
1815
1816 static void berekeny (float f1, float f2, float f3, float f4, float *o, int b)
1817 {
1818         float t, c0, c1, c2, c3;
1819         int a;
1820
1821         c0= f1;
1822         c1= 3.0f * (f2 - f1);
1823         c2= 3.0f * (f1 - 2.0f*f2 + f3);
1824         c3= f4 - f1 + 3.0f * (f2 - f3);
1825         
1826         for (a=0; a < b; a++) {
1827                 t= o[a];
1828                 o[a]= c0 + t*c1 + t*t*c2 + t*t*t*c3;
1829         }
1830 }
1831
1832 #if 0
1833 static void berekenx (float *f, float *o, int b)
1834 {
1835         float t, c0, c1, c2, c3;
1836         int a;
1837
1838         c0= f[0];
1839         c1= 3.0f * (f[3] - f[0]);
1840         c2= 3.0f * (f[0] - 2.0f*f[3] + f[6]);
1841         c3= f[9] - f[0] + 3.0f * (f[3] - f[6]);
1842         
1843         for (a=0; a < b; a++) {
1844                 t= o[a];
1845                 o[a]= c0 + t*c1 + t*t*c2 + t*t*t*c3;
1846         }
1847 }
1848 #endif
1849
1850
1851 /* -------------------------- */
1852
1853 /* Calculate F-Curve value for 'evaltime' using BezTriple keyframes */
1854 static float fcurve_eval_keyframes (FCurve *fcu, BezTriple *bezts, float evaltime)
1855 {
1856         BezTriple *bezt, *prevbezt, *lastbezt;
1857         float v1[2], v2[2], v3[2], v4[2], opl[32], dx, fac;
1858         unsigned int a;
1859         int b;
1860         float cvalue = 0.0f;
1861         
1862         /* get pointers */
1863         a= fcu->totvert-1;
1864         prevbezt= bezts;
1865         bezt= prevbezt+1;
1866         lastbezt= prevbezt + a;
1867         
1868         /* evaluation time at or past endpoints? */
1869         if (prevbezt->vec[1][0] >= evaltime) 
1870         {
1871                 /* before or on first keyframe */
1872                 if ( (fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (prevbezt->ipo != BEZT_IPO_CONST) &&
1873                         !(fcu->flag & FCURVE_DISCRETE_VALUES) ) 
1874                 {
1875                         /* linear or bezier interpolation */
1876                         if (prevbezt->ipo==BEZT_IPO_LIN) 
1877                         {
1878                                 /* Use the next center point instead of our own handle for
1879                                  * linear interpolated extrapolate 
1880                                  */
1881                                 if (fcu->totvert == 1) 
1882                                         cvalue= prevbezt->vec[1][1];
1883                                 else 
1884                                 {
1885                                         bezt = prevbezt+1;
1886                                         dx= prevbezt->vec[1][0] - evaltime;
1887                                         fac= bezt->vec[1][0] - prevbezt->vec[1][0];
1888                                         
1889                                         /* prevent division by zero */
1890                                         if (fac) {
1891                                                 fac= (bezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
1892                                                 cvalue= prevbezt->vec[1][1] - (fac * dx);
1893                                         }
1894                                         else 
1895                                                 cvalue= prevbezt->vec[1][1];
1896                                 }
1897                         } 
1898                         else 
1899                         {
1900                                 /* Use the first handle (earlier) of first BezTriple to calculate the
1901                                  * gradient and thus the value of the curve at evaltime
1902                                  */
1903                                 dx= prevbezt->vec[1][0] - evaltime;
1904                                 fac= prevbezt->vec[1][0] - prevbezt->vec[0][0];
1905                                 
1906                                 /* prevent division by zero */
1907                                 if (fac) {
1908                                         fac= (prevbezt->vec[1][1] - prevbezt->vec[0][1]) / fac;
1909                                         cvalue= prevbezt->vec[1][1] - (fac * dx);
1910                                 }
1911                                 else 
1912                                         cvalue= prevbezt->vec[1][1];
1913                         }
1914                 }
1915                 else 
1916                 {
1917                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation, 
1918                          * so just extend first keyframe's value 
1919                          */
1920                         cvalue= prevbezt->vec[1][1];
1921                 }
1922         }
1923         else if (lastbezt->vec[1][0] <= evaltime) 
1924         {
1925                 /* after or on last keyframe */
1926                 if ( (fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (lastbezt->ipo != BEZT_IPO_CONST) &&
1927                         !(fcu->flag & FCURVE_DISCRETE_VALUES) ) 
1928                 {
1929                         /* linear or bezier interpolation */
1930                         if (lastbezt->ipo==BEZT_IPO_LIN) 
1931                         {
1932                                 /* Use the next center point instead of our own handle for
1933                                  * linear interpolated extrapolate 
1934                                  */
1935                                 if (fcu->totvert == 1) 
1936                                         cvalue= lastbezt->vec[1][1];
1937                                 else 
1938                                 {
1939                                         prevbezt = lastbezt - 1;
1940                                         dx= evaltime - lastbezt->vec[1][0];
1941                                         fac= lastbezt->vec[1][0] - prevbezt->vec[1][0];
1942                                         
1943                                         /* prevent division by zero */
1944                                         if (fac) {
1945                                                 fac= (lastbezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
1946                                                 cvalue= lastbezt->vec[1][1] + (fac * dx);
1947                                         }
1948                                         else 
1949                                                 cvalue= lastbezt->vec[1][1];
1950                                 }
1951                         } 
1952                         else 
1953                         {
1954                                 /* Use the gradient of the second handle (later) of last BezTriple to calculate the
1955                                  * gradient and thus the value of the curve at evaltime
1956                                  */
1957                                 dx= evaltime - lastbezt->vec[1][0];
1958                                 fac= lastbezt->vec[2][0] - lastbezt->vec[1][0];
1959                                 
1960                                 /* prevent division by zero */
1961                                 if (fac) {
1962                                         fac= (lastbezt->vec[2][1] - lastbezt->vec[1][1]) / fac;
1963                                         cvalue= lastbezt->vec[1][1] + (fac * dx);
1964                                 }
1965                                 else 
1966                                         cvalue= lastbezt->vec[1][1];
1967                         }
1968                 }
1969                 else 
1970                 {
1971                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation, 
1972                          * so just extend last keyframe's value 
1973                          */
1974                         cvalue= lastbezt->vec[1][1];
1975                 }
1976         }
1977         else 
1978         {
1979                 /* evaltime occurs somewhere in the middle of the curve */
1980                 for (a=0; prevbezt && bezt && (a < fcu->totvert-1); a++, prevbezt=bezt, bezt++) 
1981                 {
1982                         /* use if the key is directly on the frame, rare cases this is needed else we get 0.0 instead. */
1983                         if(fabs(bezt->vec[1][0] - evaltime) < SMALL_NUMBER) {
1984                                 cvalue= bezt->vec[1][1];
1985                         }
1986                         /* evaltime occurs within the interval defined by these two keyframes */
1987                         else if ((prevbezt->vec[1][0] <= evaltime) && (bezt->vec[1][0] >= evaltime))
1988                         {
1989                                 /* value depends on interpolation mode */
1990                                 if ((prevbezt->ipo == BEZT_IPO_CONST) || (fcu->flag & FCURVE_DISCRETE_VALUES))
1991                                 {
1992                                         /* constant (evaltime not relevant, so no interpolation needed) */
1993                                         cvalue= prevbezt->vec[1][1];
1994                                 }
1995                                 else if (prevbezt->ipo == BEZT_IPO_LIN) 
1996                                 {
1997                                         /* linear - interpolate between values of the two keyframes */
1998                                         fac= bezt->vec[1][0] - prevbezt->vec[1][0];
1999                                         
2000                                         /* prevent division by zero */
2001                                         if (fac) {
2002                                                 fac= (evaltime - prevbezt->vec[1][0]) / fac;
2003                                                 cvalue= prevbezt->vec[1][1] + (fac * (bezt->vec[1][1] - prevbezt->vec[1][1]));
2004                                         }
2005                                         else
2006                                                 cvalue= prevbezt->vec[1][1];
2007                                 }
2008                                 else 
2009                                 {
2010                                         /* bezier interpolation */
2011                                                 /* v1,v2 are the first keyframe and its 2nd handle */
2012                                         v1[0]= prevbezt->vec[1][0];
2013                                         v1[1]= prevbezt->vec[1][1];
2014                                         v2[0]= prevbezt->vec[2][0];
2015                                         v2[1]= prevbezt->vec[2][1];
2016                                                 /* v3,v4 are the last keyframe's 1st handle + the last keyframe */
2017                                         v3[0]= bezt->vec[0][0];
2018                                         v3[1]= bezt->vec[0][1];
2019                                         v4[0]= bezt->vec[1][0];
2020                                         v4[1]= bezt->vec[1][1];
2021                                         
2022                                         /* adjust handles so that they don't overlap (forming a loop) */
2023                                         correct_bezpart(v1, v2, v3, v4);
2024                                         
2025                                         /* try to get a value for this position - if failure, try another set of points */
2026                                         b= findzero(evaltime, v1[0], v2[0], v3[0], v4[0], opl);
2027                                         if (b) {
2028                                                 berekeny(v1[1], v2[1], v3[1], v4[1], opl, 1);
2029                                                 cvalue= opl[0];
2030                                                 break;
2031                                         }
2032                                 }
2033                         }
2034                 }
2035         }
2036         
2037         /* return value */
2038         return cvalue;
2039 }
2040
2041 /* Calculate F-Curve value for 'evaltime' using FPoint samples */
2042 static float fcurve_eval_samples (FCurve *fcu, FPoint *fpts, float evaltime)
2043 {
2044         FPoint *prevfpt, *lastfpt, *fpt;
2045         float cvalue= 0.0f;
2046         
2047         /* get pointers */
2048         prevfpt= fpts;
2049         lastfpt= prevfpt + fcu->totvert-1;
2050         
2051         /* evaluation time at or past endpoints? */
2052         if (prevfpt->vec[0] >= evaltime) {
2053                 /* before or on first sample, so just extend value */
2054                 cvalue= prevfpt->vec[1];
2055         }
2056         else if (lastfpt->vec[0] <= evaltime) {
2057                 /* after or on last sample, so just extend value */
2058                 cvalue= lastfpt->vec[1];
2059         }
2060         else {
2061                 float t= (float)abs(evaltime - (int)evaltime);
2062                 
2063                 /* find the one on the right frame (assume that these are spaced on 1-frame intervals) */
2064                 fpt= prevfpt + (int)(evaltime - prevfpt->vec[0]);
2065                 
2066                 /* if not exactly on the frame, perform linear interpolation with the next one */
2067                 if (t != 0.0f) 
2068                         cvalue= interpf(fpt->vec[1], (fpt+1)->vec[1], t);
2069                 else
2070                         cvalue= fpt->vec[1];
2071         }
2072         
2073         /* return value */
2074         return cvalue;
2075 }
2076
2077 /* ***************************** F-Curve - Evaluation ********************************* */
2078
2079 /* Evaluate and return the value of the given F-Curve at the specified frame ("evaltime") 
2080  * Note: this is also used for drivers
2081  */
2082 float evaluate_fcurve (FCurve *fcu, float evaltime) 
2083 {
2084         float cvalue= 0.0f;
2085         float devaltime;
2086         
2087         /* if there is a driver (only if this F-Curve is acting as 'driver'), evaluate it to find value to use as "evaltime" 
2088          * since drivers essentially act as alternative input (i.e. in place of 'time') for F-Curves
2089          *      - this value will also be returned as the value of the 'curve', if there are no keyframes
2090          */
2091         if (fcu->driver) {
2092                 /* evaltime now serves as input for the curve */
2093                 evaltime= cvalue= evaluate_driver(fcu->driver, evaltime);
2094         }
2095         
2096         /* evaluate modifiers which modify time to evaluate the base curve at */
2097         devaltime= evaluate_time_fmodifiers(&fcu->modifiers, fcu, cvalue, evaltime);
2098         
2099         /* evaluate curve-data 
2100          *      - 'devaltime' instead of 'evaltime', as this is the time that the last time-modifying 
2101          *        F-Curve modifier on the stack requested the curve to be evaluated at
2102          */
2103         if (fcu->bezt)
2104                 cvalue= fcurve_eval_keyframes(fcu, fcu->bezt, devaltime);
2105         else if (fcu->fpt)
2106                 cvalue= fcurve_eval_samples(fcu, fcu->fpt, devaltime);
2107         
2108         /* evaluate modifiers */
2109         evaluate_value_fmodifiers(&fcu->modifiers, fcu, &cvalue, evaltime);
2110         
2111         /* if curve can only have integral values, perform truncation (i.e. drop the decimal part)
2112          * here so that the curve can be sampled correctly
2113          */
2114         if (fcu->flag & FCURVE_INT_VALUES)
2115                 cvalue= floorf(cvalue + 0.5f);
2116         
2117         /* return evaluated value */
2118         return cvalue;
2119 }
2120
2121 /* Calculate the value of the given F-Curve at the given frame, and set its curval */
2122 void calculate_fcurve (FCurve *fcu, float ctime)
2123 {
2124         /* only calculate + set curval (overriding the existing value) if curve has 
2125          * any data which warrants this...
2126          */
2127         if ( (fcu->totvert) || (fcu->driver && !(fcu->driver->flag & DRIVER_FLAG_INVALID)) ||
2128                  list_has_suitable_fmodifier(&fcu->modifiers, 0, FMI_TYPE_GENERATE_CURVE) )
2129         {
2130                 /* calculate and set curval (evaluates driver too if necessary) */
2131                 fcu->curval= evaluate_fcurve(fcu, ctime);
2132         }
2133 }
2134