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