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