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