Cleanup: style
[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_easing.h"
49 #include "BLI_threads.h"
50 #include "BLI_string_utils.h"
51 #include "BLI_utildefines.h"
52
53 #include "BLT_translation.h"
54
55 #include "BKE_fcurve.h"
56 #include "BKE_animsys.h"
57 #include "BKE_action.h"
58 #include "BKE_armature.h"
59 #include "BKE_constraint.h"
60 #include "BKE_context.h"
61 #include "BKE_curve.h" 
62 #include "BKE_global.h"
63 #include "BKE_object.h"
64 #include "BKE_nla.h"
65
66 #include "RNA_access.h"
67
68 #ifdef WITH_PYTHON
69 #include "BPY_extern.h" 
70 #endif
71
72 #define SMALL -1.0e-10
73 #define SELECT 1
74
75 #ifdef WITH_PYTHON
76 static ThreadMutex python_driver_lock = BLI_MUTEX_INITIALIZER;
77 #endif
78
79 /* ************************** Data-Level Functions ************************* */
80
81 /* ---------------------- Freeing --------------------------- */
82
83 /* Frees the F-Curve itself too, so make sure BLI_remlink is called before calling this... */
84 void free_fcurve(FCurve *fcu)
85 {
86         if (fcu == NULL) 
87                 return;
88
89         /* free curve data */
90         MEM_SAFE_FREE(fcu->bezt);
91         MEM_SAFE_FREE(fcu->fpt);
92         
93         /* free RNA-path, as this were allocated when getting the path string */
94         MEM_SAFE_FREE(fcu->rna_path);
95         
96         /* free extra data - i.e. modifiers, and driver */
97         fcurve_free_driver(fcu);
98         free_fmodifiers(&fcu->modifiers);
99         
100         /* free f-curve itself */
101         MEM_freeN(fcu);
102 }
103
104 /* Frees a list of F-Curves */
105 void free_fcurves(ListBase *list)
106 {
107         FCurve *fcu, *fcn;
108         
109         /* sanity check */
110         if (list == NULL)
111                 return;
112                 
113         /* free data - no need to call remlink before freeing each curve, 
114          * as we store reference to next, and freeing only touches the curve
115          * it's given
116          */
117         for (fcu = list->first; fcu; fcu = fcn) {
118                 fcn = fcu->next;
119                 free_fcurve(fcu);
120         }
121         
122         /* clear pointers just in case */
123         BLI_listbase_clear(list);
124 }       
125
126 /* ---------------------- Copy --------------------------- */
127
128 /* duplicate an F-Curve */
129 FCurve *copy_fcurve(const FCurve *fcu)
130 {
131         FCurve *fcu_d;
132         
133         /* sanity check */
134         if (fcu == NULL)
135                 return NULL;
136                 
137         /* make a copy */
138         fcu_d = MEM_dupallocN(fcu);
139         
140         fcu_d->next = fcu_d->prev = NULL;
141         fcu_d->grp = NULL;
142         
143         /* copy curve data */
144         fcu_d->bezt = MEM_dupallocN(fcu_d->bezt);
145         fcu_d->fpt = MEM_dupallocN(fcu_d->fpt);
146         
147         /* copy rna-path */
148         fcu_d->rna_path = MEM_dupallocN(fcu_d->rna_path);
149         
150         /* copy driver */
151         fcu_d->driver = fcurve_copy_driver(fcu_d->driver);
152         
153         /* copy modifiers */
154         copy_fmodifiers(&fcu_d->modifiers, &fcu->modifiers);
155         
156         /* return new data */
157         return fcu_d;
158 }
159
160 /* duplicate a list of F-Curves */
161 void copy_fcurves(ListBase *dst, ListBase *src)
162 {
163         FCurve *dfcu, *sfcu;
164         
165         /* sanity checks */
166         if (ELEM(NULL, dst, src))
167                 return;
168         
169         /* clear destination list first */
170         BLI_listbase_clear(dst);
171         
172         /* copy one-by-one */
173         for (sfcu = src->first; sfcu; sfcu = sfcu->next) {
174                 dfcu = copy_fcurve(sfcu);
175                 BLI_addtail(dst, dfcu);
176         }
177 }
178
179 /* ----------------- Finding F-Curves -------------------------- */
180
181 /* high level function to get an fcurve from C without having the rna */
182 FCurve *id_data_find_fcurve(ID *id, void *data, StructRNA *type, const char *prop_name, int index, bool *r_driven)
183 {
184         /* anim vars */
185         AnimData *adt = BKE_animdata_from_id(id);
186         FCurve *fcu = NULL;
187
188         /* rna vars */
189         PointerRNA ptr;
190         PropertyRNA *prop;
191         char *path;
192
193         if (r_driven)
194                 *r_driven = false;
195         
196         /* only use the current action ??? */
197         if (ELEM(NULL, adt, adt->action))
198                 return NULL;
199         
200         RNA_pointer_create(id, type, data, &ptr);
201         prop = RNA_struct_find_property(&ptr, prop_name);
202         
203         if (prop) {
204                 path = RNA_path_from_ID_to_property(&ptr, prop);
205                         
206                 if (path) {
207                         /* animation takes priority over drivers */
208                         if ((adt->action) && (adt->action->curves.first))
209                                 fcu = list_find_fcurve(&adt->action->curves, path, index);
210                         
211                         /* if not animated, check if driven */
212                         if ((fcu == NULL) && (adt->drivers.first)) {
213                                 fcu = list_find_fcurve(&adt->drivers, path, index);
214                                 if (fcu && r_driven)
215                                         *r_driven = true;
216                                 fcu = NULL;
217                         }
218                         
219                         MEM_freeN(path);
220                 }
221         }
222
223         return fcu;
224 }
225
226
227 /* Find the F-Curve affecting the given RNA-access path + index, in the list of F-Curves provided */
228 FCurve *list_find_fcurve(ListBase *list, const char rna_path[], const int array_index)
229 {
230         FCurve *fcu;
231         
232         /* sanity checks */
233         if (ELEM(NULL, list, rna_path) || (array_index < 0) )
234                 return NULL;
235         
236         /* check paths of curves, then array indices... */
237         for (fcu = list->first; fcu; fcu = fcu->next) {
238                 /* simple string-compare (this assumes that they have the same root...) */
239                 if (fcu->rna_path && STREQ(fcu->rna_path, rna_path)) {
240                         /* now check indices */
241                         if (fcu->array_index == array_index)
242                                 return fcu;
243                 }
244         }
245         
246         /* return */
247         return NULL;
248 }
249
250 /* quick way to loop over all fcurves of a given 'path' */
251 FCurve *iter_step_fcurve(FCurve *fcu_iter, const char rna_path[])
252 {
253         FCurve *fcu;
254         
255         /* sanity checks */
256         if (ELEM(NULL, fcu_iter, rna_path))
257                 return NULL;
258
259         /* check paths of curves, then array indices... */
260         for (fcu = fcu_iter; fcu; fcu = fcu->next) {
261                 /* simple string-compare (this assumes that they have the same root...) */
262                 if (fcu->rna_path && STREQ(fcu->rna_path, rna_path)) {
263                         return fcu;
264                 }
265         }
266
267         /* return */
268         return NULL;
269 }
270
271 /* Get list of LinkData's containing pointers to the F-Curves which control the types of data indicated 
272  * Lists...
273  *      - dst: list of LinkData's matching the criteria returned. 
274  *        List must be freed after use, and is assumed to be empty when passed.
275  *      - src: list of F-Curves to search through
276  * Filters...
277  *  - dataPrefix: i.e. 'pose.bones[' or 'nodes['
278  *  - dataName: name of entity within "" immediately following the prefix
279  */
280 int list_find_data_fcurves(ListBase *dst, ListBase *src, const char *dataPrefix, const char *dataName)
281 {
282         FCurve *fcu;
283         int matches = 0;
284         
285         /* sanity checks */
286         if (ELEM(NULL, dst, src, dataPrefix, dataName))
287                 return 0;
288         else if ((dataPrefix[0] == 0) || (dataName[0] == 0))
289                 return 0;
290         
291         /* search each F-Curve one by one */
292         for (fcu = src->first; fcu; fcu = fcu->next) {
293                 /* check if quoted string matches the path */
294                 if ((fcu->rna_path) && strstr(fcu->rna_path, dataPrefix)) {
295                         char *quotedName = BLI_str_quoted_substrN(fcu->rna_path, dataPrefix);
296                         
297                         if (quotedName) {
298                                 /* check if the quoted name matches the required name */
299                                 if (STREQ(quotedName, dataName)) {
300                                         LinkData *ld = MEM_callocN(sizeof(LinkData), __func__);
301                                         
302                                         ld->data = fcu;
303                                         BLI_addtail(dst, ld);
304                                         
305                                         matches++;
306                                 }
307                                 
308                                 /* always free the quoted string, since it needs freeing */
309                                 MEM_freeN(quotedName);
310                         }
311                 }
312         }
313         
314         /* return the number of matches */
315         return matches;
316 }
317
318 FCurve *rna_get_fcurve(
319         PointerRNA *ptr, PropertyRNA *prop, int rnaindex,
320         AnimData **r_adt,  bAction **r_action, bool *r_driven, bool *r_special)
321 {
322         return rna_get_fcurve_context_ui(NULL, ptr, prop, rnaindex, r_adt, r_action, r_driven, r_special);
323 }
324
325 FCurve *rna_get_fcurve_context_ui(
326         bContext *C, PointerRNA *ptr, PropertyRNA *prop, int rnaindex,
327         AnimData **r_animdata, bAction **r_action, bool *r_driven, bool *r_special)
328 {
329         FCurve *fcu = NULL;
330         PointerRNA tptr = *ptr;
331         
332         *r_driven = false;
333         *r_special = false;
334         
335         if (r_animdata) *r_animdata = NULL;
336         if (r_action) *r_action = NULL;
337         
338         /* Special case for NLA Control Curves... */
339         if (BKE_nlastrip_has_curves_for_property(ptr, prop)) {
340                 NlaStrip *strip = (NlaStrip *)ptr->data;
341                 
342                 /* Set the special flag, since it cannot be a normal action/driver
343                  * if we've been told to start looking here...
344                  */
345                 *r_special = true;
346                 
347                 /* The F-Curve either exists or it doesn't here... */
348                 fcu = list_find_fcurve(&strip->fcurves, RNA_property_identifier(prop), rnaindex);
349                 return fcu;
350         }
351         
352         /* there must be some RNA-pointer + property combon */
353         if (prop && tptr.id.data && RNA_property_animateable(&tptr, prop)) {
354                 AnimData *adt = BKE_animdata_from_id(tptr.id.data);
355                 int step = C ? 2 : 1;  /* Always 1 in case we have no context (can't check in 'ancestors' of given RNA ptr). */
356                 char *path = NULL;
357                 
358                 if (!adt && C) {
359                         path = BKE_animdata_driver_path_hack(C, &tptr, prop, NULL);
360                         adt = BKE_animdata_from_id(tptr.id.data);
361                         step--;
362                 }
363                 
364                 /* Standard F-Curve - Animation (Action) or Drivers */
365                 while (adt && step--) {
366                         if ((adt->action && adt->action->curves.first) || (adt->drivers.first)) {
367                                 /* XXX this function call can become a performance bottleneck */
368                                 if (step) {
369                                         path = RNA_path_from_ID_to_property(&tptr, prop);
370                                 }
371                                 
372                                 // XXX: the logic here is duplicated with a function up above
373                                 if (path) {
374                                         /* animation takes priority over drivers */
375                                         if (adt->action && adt->action->curves.first) {
376                                                 fcu = list_find_fcurve(&adt->action->curves, path, rnaindex);
377                                                 
378                                                 if (fcu && r_action)
379                                                         *r_action = adt->action;
380                                         }
381                                         
382                                         /* if not animated, check if driven */
383                                         if (!fcu && (adt->drivers.first)) {
384                                                 fcu = list_find_fcurve(&adt->drivers, path, rnaindex);
385                                                 
386                                                 if (fcu) {
387                                                         if (r_animdata) *r_animdata = adt;
388                                                         *r_driven = true;
389                                                 }
390                                         }
391                                         
392                                         if (fcu && r_action) {
393                                                 if (r_animdata) *r_animdata = adt;
394                                                 *r_action = adt->action;
395                                                 break;
396                                         }
397                                         else if (step) {
398                                                 char *tpath = BKE_animdata_driver_path_hack(C, &tptr, prop, path);
399                                                 if (tpath && tpath != path) {
400                                                         MEM_freeN(path);
401                                                         path = tpath;
402                                                         adt = BKE_animdata_from_id(tptr.id.data);
403                                                 }
404                                                 else {
405                                                         adt = NULL;
406                                                 }
407                                         }
408                                 }
409                         }
410                 }
411                 MEM_SAFE_FREE(path);
412         }
413         
414         return fcu;
415 }
416
417 /* ----------------- Finding Keyframes/Extents -------------------------- */
418
419 /* Binary search algorithm for finding where to insert BezTriple, with optional argument for precision required.
420  * Returns the index to insert at (data already at that index will be offset if replace is 0)
421  */
422 static int binarysearch_bezt_index_ex(BezTriple array[], float frame, int arraylen, float threshold, bool *r_replace)
423 {
424         int start = 0, end = arraylen;
425         int loopbreaker = 0, maxloop = arraylen * 2;
426         
427         /* initialize replace-flag first */
428         *r_replace = false;
429         
430         /* sneaky optimizations (don't go through searching process if...):
431          *      - keyframe to be added is to be added out of current bounds
432          *      - keyframe to be added would replace one of the existing ones on bounds
433          */
434         if ((arraylen <= 0) || (array == NULL)) {
435                 printf("Warning: binarysearch_bezt_index() encountered invalid array\n");
436                 return 0;
437         }
438         else {
439                 /* check whether to add before/after/on */
440                 float framenum;
441                 
442                 /* 'First' Keyframe (when only one keyframe, this case is used) */
443                 framenum = array[0].vec[1][0];
444                 if (IS_EQT(frame, framenum, threshold)) {
445                         *r_replace = true;
446                         return 0;
447                 }
448                 else if (frame < framenum)
449                         return 0;
450                         
451                 /* 'Last' Keyframe */
452                 framenum = array[(arraylen - 1)].vec[1][0];
453                 if (IS_EQT(frame, framenum, threshold)) {
454                         *r_replace = true;
455                         return (arraylen - 1);
456                 }
457                 else if (frame > framenum)
458                         return arraylen;
459         }
460         
461         
462         /* most of the time, this loop is just to find where to put it
463          * 'loopbreaker' is just here to prevent infinite loops 
464          */
465         for (loopbreaker = 0; (start <= end) && (loopbreaker < maxloop); loopbreaker++) {
466                 /* compute and get midpoint */
467                 int mid = start + ((end - start) / 2);  /* we calculate the midpoint this way to avoid int overflows... */
468                 float midfra = array[mid].vec[1][0];
469                 
470                 /* check if exactly equal to midpoint */
471                 if (IS_EQT(frame, midfra, threshold)) {
472                         *r_replace = true;
473                         return mid;
474                 }
475                 
476                 /* repeat in upper/lower half */
477                 if (frame > midfra)
478                         start = mid + 1;
479                 else if (frame < midfra)
480                         end = mid - 1;
481         }
482         
483         /* print error if loop-limit exceeded */
484         if (loopbreaker == (maxloop - 1)) {
485                 printf("Error: binarysearch_bezt_index() was taking too long\n");
486                 
487                 /* include debug info */
488                 printf("\tround = %d: start = %d, end = %d, arraylen = %d\n", loopbreaker, start, end, arraylen);
489         }
490         
491         /* not found, so return where to place it */
492         return start;
493 }
494
495
496 /* Binary search algorithm for finding where to insert BezTriple. (for use by insert_bezt_fcurve)
497  * Returns the index to insert at (data already at that index will be offset if replace is 0)
498  */
499 int binarysearch_bezt_index(BezTriple array[], float frame, int arraylen, bool *r_replace)
500 {
501         /* this is just a wrapper which uses the default threshold */
502         return binarysearch_bezt_index_ex(array, frame, arraylen, BEZT_BINARYSEARCH_THRESH, r_replace);
503 }
504
505 /* ...................................... */
506
507 /* helper for calc_fcurve_* functions -> find first and last BezTriple to be used */
508 static short get_fcurve_end_keyframes(FCurve *fcu, BezTriple **first, BezTriple **last,
509                                       const bool do_sel_only)
510 {
511         bool found = false;
512         
513         /* init outputs */
514         *first = NULL;
515         *last = NULL;
516         
517         /* sanity checks */
518         if (fcu->bezt == NULL)
519                 return found;
520         
521         /* only include selected items? */
522         if (do_sel_only) {
523                 BezTriple *bezt;
524                 unsigned int i;
525                 
526                 /* find first selected */
527                 bezt = fcu->bezt;
528                 for (i = 0; i < fcu->totvert; bezt++, i++) {
529                         if (BEZT_ISSEL_ANY(bezt)) {
530                                 *first = bezt;
531                                 found = true;
532                                 break;
533                         }
534                 }
535                 
536                 /* find last selected */
537                 bezt = ARRAY_LAST_ITEM(fcu->bezt, BezTriple, fcu->totvert);
538                 for (i = 0; i < fcu->totvert; bezt--, i++) {
539                         if (BEZT_ISSEL_ANY(bezt)) {
540                                 *last = bezt;
541                                 found = true;
542                                 break;
543                         }
544                 }
545         }
546         else {
547                 /* just full array */
548                 *first = fcu->bezt;
549                 *last = ARRAY_LAST_ITEM(fcu->bezt, BezTriple, fcu->totvert);
550                 found = true;
551         }
552         
553         return found;
554 }
555
556
557 /* Calculate the extents of F-Curve's data */
558 bool calc_fcurve_bounds(FCurve *fcu, float *xmin, float *xmax, float *ymin, float *ymax,
559                         const bool do_sel_only, const bool include_handles)
560 {
561         float xminv = 999999999.0f, xmaxv = -999999999.0f;
562         float yminv = 999999999.0f, ymaxv = -999999999.0f;
563         bool foundvert = false;
564         unsigned int i;
565         
566         if (fcu->totvert) {
567                 if (fcu->bezt) {
568                         BezTriple *bezt_first = NULL, *bezt_last = NULL;
569                         
570                         if (xmin || xmax) {
571                                 /* get endpoint keyframes */
572                                 foundvert = get_fcurve_end_keyframes(fcu, &bezt_first, &bezt_last, do_sel_only);
573                                 
574                                 if (bezt_first) {
575                                         BLI_assert(bezt_last != NULL);
576                                         
577                                         if (include_handles) {
578                                                 xminv = min_fff(xminv, bezt_first->vec[0][0], bezt_first->vec[1][0]);
579                                                 xmaxv = max_fff(xmaxv, bezt_last->vec[1][0],  bezt_last->vec[2][0]);
580                                         }
581                                         else {
582                                                 xminv = min_ff(xminv, bezt_first->vec[1][0]);
583                                                 xmaxv = max_ff(xmaxv, bezt_last->vec[1][0]);
584                                         }
585                                 }
586                         }
587                         
588                         /* only loop over keyframes to find extents for values if needed */
589                         if (ymin || ymax) {
590                                 BezTriple *bezt, *prevbezt = NULL;
591                                 
592                                 for (bezt = fcu->bezt, i = 0; i < fcu->totvert; prevbezt = bezt, bezt++, i++) {
593                                         if ((do_sel_only == false) || BEZT_ISSEL_ANY(bezt)) {
594                                                 /* keyframe itself */
595                                                 yminv = min_ff(yminv, bezt->vec[1][1]);
596                                                 ymaxv = max_ff(ymaxv, bezt->vec[1][1]);
597                                                 
598                                                 if (include_handles) {
599                                                         /* left handle - only if applicable 
600                                                          * NOTE: for the very first keyframe, the left handle actually has no bearings on anything
601                                                          */
602                                                         if (prevbezt && (prevbezt->ipo == BEZT_IPO_BEZ)) {
603                                                                 yminv = min_ff(yminv, bezt->vec[0][1]);
604                                                                 ymaxv = max_ff(ymaxv, bezt->vec[0][1]);
605                                                         }
606                                                         
607                                                         /* right handle - only if applicable */
608                                                         if (bezt->ipo == BEZT_IPO_BEZ) {
609                                                                 yminv = min_ff(yminv, bezt->vec[2][1]);
610                                                                 ymaxv = max_ff(ymaxv, bezt->vec[2][1]);
611                                                         }
612                                                 }
613                                                 
614                                                 foundvert = true;
615                                         }
616                                 }
617                         }
618                 }
619                 else if (fcu->fpt) {
620                         /* frame range can be directly calculated from end verts */
621                         if (xmin || xmax) {
622                                 xminv = min_ff(xminv, fcu->fpt[0].vec[0]);
623                                 xmaxv = max_ff(xmaxv, fcu->fpt[fcu->totvert - 1].vec[0]);
624                         }
625                         
626                         /* only loop over keyframes to find extents for values if needed */
627                         if (ymin || ymax) {
628                                 FPoint *fpt;
629                                 
630                                 for (fpt = fcu->fpt, i = 0; i < fcu->totvert; fpt++, i++) {
631                                         if (fpt->vec[1] < yminv)
632                                                 yminv = fpt->vec[1];
633                                         if (fpt->vec[1] > ymaxv)
634                                                 ymaxv = fpt->vec[1];
635                                         
636                                         foundvert = true;
637                                 }
638                         }
639                 }
640         }
641         
642         if (foundvert) {
643                 if (xmin) *xmin = xminv;
644                 if (xmax) *xmax = xmaxv;
645                 
646                 if (ymin) *ymin = yminv;
647                 if (ymax) *ymax = ymaxv;
648         }
649         else {
650                 if (G.debug & G_DEBUG)
651                         printf("F-Curve calc bounds didn't find anything, so assuming minimum bounds of 1.0\n");
652                         
653                 if (xmin) *xmin = 0.0f;
654                 if (xmax) *xmax = 1.0f;
655                 
656                 if (ymin) *ymin = 0.0f;
657                 if (ymax) *ymax = 1.0f;
658         }
659         
660         return foundvert;
661 }
662
663 /* Calculate the extents of F-Curve's keyframes */
664 bool calc_fcurve_range(FCurve *fcu, float *start, float *end,
665                        const bool do_sel_only, const bool do_min_length)
666 {
667         float min = 999999999.0f, max = -999999999.0f;
668         bool foundvert = false;
669
670         if (fcu->totvert) {
671                 if (fcu->bezt) {
672                         BezTriple *bezt_first = NULL, *bezt_last = NULL;
673                         
674                         /* get endpoint keyframes */
675                         get_fcurve_end_keyframes(fcu, &bezt_first, &bezt_last, do_sel_only);
676                         
677                         if (bezt_first) {
678                                 BLI_assert(bezt_last != NULL);
679                                 
680                                 min = min_ff(min, bezt_first->vec[1][0]);
681                                 max = max_ff(max, bezt_last->vec[1][0]);
682                                 
683                                 foundvert = true;
684                         }
685                 }
686                 else if (fcu->fpt) {
687                         min = min_ff(min, fcu->fpt[0].vec[0]);
688                         max = max_ff(max, fcu->fpt[fcu->totvert - 1].vec[0]);
689                         
690                         foundvert = true;
691                 }
692                 
693         }
694         
695         if (foundvert == false) {
696                 min = max = 0.0f;
697         }
698
699         if (do_min_length) {
700                 /* minimum length is 1 frame */
701                 if (min == max) {
702                         max += 1.0f;
703                 }
704         }
705
706         *start = min;
707         *end = max;
708
709         return foundvert;
710 }
711
712 /* ----------------- Status Checks -------------------------- */
713
714 /* Are keyframes on F-Curve of any use? 
715  * Usability of keyframes refers to whether they should be displayed,
716  * and also whether they will have any influence on the final result.
717  */
718 bool fcurve_are_keyframes_usable(FCurve *fcu)
719 {
720         /* F-Curve must exist */
721         if (fcu == NULL)
722                 return false;
723                 
724         /* F-Curve must not have samples - samples are mutually exclusive of keyframes */
725         if (fcu->fpt)
726                 return false;
727         
728         /* if it has modifiers, none of these should "drastically" alter the curve */
729         if (fcu->modifiers.first) {
730                 FModifier *fcm;
731
732                 /* check modifiers from last to first, as last will be more influential */
733                 /* TODO: optionally, only check modifier if it is the active one... */
734                 for (fcm = fcu->modifiers.last; fcm; fcm = fcm->prev) {
735                         /* ignore if muted/disabled */
736                         if (fcm->flag & (FMODIFIER_FLAG_DISABLED | FMODIFIER_FLAG_MUTED))
737                                 continue;
738                                 
739                         /* type checks */
740                         switch (fcm->type) {
741                                 /* clearly harmless - do nothing */
742                                 case FMODIFIER_TYPE_CYCLES:
743                                 case FMODIFIER_TYPE_STEPPED:
744                                 case FMODIFIER_TYPE_NOISE:
745                                         break;
746                                         
747                                 /* sometimes harmful - depending on whether they're "additive" or not */
748                                 case FMODIFIER_TYPE_GENERATOR:
749                                 {
750                                         FMod_Generator *data = (FMod_Generator *)fcm->data;
751                                         
752                                         if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0)
753                                                 return false;
754                                         break;
755                                 }
756                                 case FMODIFIER_TYPE_FN_GENERATOR:
757                                 {
758                                         FMod_FunctionGenerator *data = (FMod_FunctionGenerator *)fcm->data;
759                                         
760                                         if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0)
761                                                 return false;
762                                         break;
763                                 }
764                                 /* always harmful - cannot allow */
765                                 default:
766                                         return false;
767                         }
768                 }
769         }
770         
771         /* keyframes are usable */
772         return true;
773 }
774
775 bool BKE_fcurve_is_protected(FCurve *fcu)
776 {
777         return ((fcu->flag & FCURVE_PROTECTED) ||
778                 ((fcu->grp) && (fcu->grp->flag & AGRP_PROTECTED)));
779 }
780
781 /* Can keyframes be added to F-Curve? 
782  * Keyframes can only be added if they are already visible
783  */
784 bool fcurve_is_keyframable(FCurve *fcu)
785 {
786         /* F-Curve's keyframes must be "usable" (i.e. visible + have an effect on final result) */
787         if (fcurve_are_keyframes_usable(fcu) == 0)
788                 return false;
789                 
790         /* F-Curve must currently be editable too */
791         if (BKE_fcurve_is_protected(fcu))
792                 return false;
793         
794         /* F-Curve is keyframable */
795         return true;
796 }
797
798 /* ***************************** Keyframe Column Tools ********************************* */
799
800 /* add a BezTriple to a column */
801 void bezt_add_to_cfra_elem(ListBase *lb, BezTriple *bezt)
802 {
803         CfraElem *ce, *cen;
804         
805         for (ce = lb->first; ce; ce = ce->next) {
806                 /* double key? */
807                 if (ce->cfra == bezt->vec[1][0]) {
808                         if (bezt->f2 & SELECT) ce->sel = bezt->f2;
809                         return;
810                 }
811                 /* should key be inserted before this column? */
812                 else if (ce->cfra > bezt->vec[1][0]) break;
813         }
814         
815         /* create a new column */
816         cen = MEM_callocN(sizeof(CfraElem), "add_to_cfra_elem");
817         if (ce) BLI_insertlinkbefore(lb, ce, cen);
818         else BLI_addtail(lb, cen);
819
820         cen->cfra = bezt->vec[1][0];
821         cen->sel = bezt->f2;
822 }
823
824 /* ***************************** Samples Utilities ******************************* */
825 /* Some utilities for working with FPoints (i.e. 'sampled' animation curve data, such as
826  * data imported from BVH/Mocap files), which are specialized for use with high density datasets,
827  * which BezTriples/Keyframe data are ill equipped to do.
828  */
829  
830  
831 /* Basic sampling callback which acts as a wrapper for evaluate_fcurve() 
832  *      'data' arg here is unneeded here...
833  */
834 float fcurve_samplingcb_evalcurve(FCurve *fcu, void *UNUSED(data), float evaltime)
835 {
836         /* assume any interference from drivers on the curve is intended... */
837         return evaluate_fcurve(fcu, evaltime);
838
839
840  
841 /* Main API function for creating a set of sampled curve data, given some callback function 
842  * used to retrieve the values to store.
843  */
844 void fcurve_store_samples(FCurve *fcu, void *data, int start, int end, FcuSampleFunc sample_cb)
845 {
846         FPoint *fpt, *new_fpt;
847         int cfra;
848         
849         /* sanity checks */
850         /* TODO: make these tests report errors using reports not printf's */
851         if (ELEM(NULL, fcu, sample_cb)) {
852                 printf("Error: No F-Curve with F-Curve Modifiers to Bake\n");
853                 return;
854         }
855         if (start > end) {
856                 printf("Error: Frame range for Sampled F-Curve creation is inappropriate\n");
857                 return;
858         }
859         
860         /* set up sample data */
861         fpt = new_fpt = MEM_callocN(sizeof(FPoint) * (end - start + 1), "FPoint Samples");
862         
863         /* use the sampling callback at 1-frame intervals from start to end frames */
864         for (cfra = start; cfra <= end; cfra++, fpt++) {
865                 fpt->vec[0] = (float)cfra;
866                 fpt->vec[1] = sample_cb(fcu, data, (float)cfra);
867         }
868         
869         /* free any existing sample/keyframe data on curve  */
870         if (fcu->bezt) MEM_freeN(fcu->bezt);
871         if (fcu->fpt) MEM_freeN(fcu->fpt);
872         
873         /* store the samples */
874         fcu->bezt = NULL;
875         fcu->fpt = new_fpt;
876         fcu->totvert = end - start + 1;
877 }
878
879 /* ***************************** F-Curve Sanity ********************************* */
880 /* The functions here are used in various parts of Blender, usually after some editing
881  * of keyframe data has occurred. They ensure that keyframe data is properly ordered and
882  * that the handles are correctly 
883  */
884
885 /* Checks if the F-Curve has a Cycles modifier with simple settings that warrant transition smoothing */
886 bool BKE_fcurve_is_cyclic(FCurve *fcu)
887 {
888         FModifier *fcm = fcu->modifiers.first;
889
890         if (!fcm || fcm->type != FMODIFIER_TYPE_CYCLES)
891                 return false;
892
893         if (fcm->flag & (FMODIFIER_FLAG_DISABLED | FMODIFIER_FLAG_MUTED))
894                 return false;
895
896         if (fcm->flag & (FMODIFIER_FLAG_RANGERESTRICT | FMODIFIER_FLAG_USEINFLUENCE))
897                 return false;
898
899         FMod_Cycles *data = (FMod_Cycles *)fcm->data;
900
901         return data && data->after_cycles == 0 && data->before_cycles == 0 &&
902             ELEM(data->before_mode, FCM_EXTRAPOLATE_CYCLIC, FCM_EXTRAPOLATE_CYCLIC_OFFSET) &&
903             ELEM(data->after_mode, FCM_EXTRAPOLATE_CYCLIC, FCM_EXTRAPOLATE_CYCLIC_OFFSET);
904 }
905
906 /* Shifts 'in' by the difference in coordinates between 'to' and 'from', using 'out' as the output buffer.
907  * When 'to' and 'from' are end points of the loop, this moves the 'in' point one loop cycle.
908  */
909 static BezTriple *cycle_offset_triple(bool cycle, BezTriple *out, const BezTriple *in, const BezTriple *from, const BezTriple *to)
910 {
911         if (!cycle)
912                 return NULL;
913
914         memcpy(out, in, sizeof(BezTriple));
915
916         float delta[3];
917         sub_v3_v3v3(delta, to->vec[1], from->vec[1]);
918
919         for (int i = 0; i < 3; i++)
920                 add_v3_v3(out->vec[i], delta);
921
922         return out;
923 }
924
925 /* This function recalculates the handles of an F-Curve 
926  * If the BezTriples have been rearranged, sort them first before using this.
927  */
928 void calchandles_fcurve(FCurve *fcu)
929 {
930         BezTriple *bezt, *prev, *next;
931         int a = fcu->totvert;
932
933         /* Error checking:
934          *      - need at least two points
935          *      - need bezier keys
936          *      - only bezier-interpolation has handles (for now)
937          */
938         if (ELEM(NULL, fcu, fcu->bezt) || (a < 2) /*|| ELEM(fcu->ipo, BEZT_IPO_CONST, BEZT_IPO_LIN)*/) 
939                 return;
940
941         /* if the first modifier is Cycles, smooth the curve through the cycle */
942         BezTriple *first = &fcu->bezt[0], *last = &fcu->bezt[fcu->totvert - 1];
943         BezTriple tmp;
944
945         bool cycle = BKE_fcurve_is_cyclic(fcu) && BEZT_IS_AUTOH(first) && BEZT_IS_AUTOH(last);
946
947         /* get initial pointers */
948         bezt = fcu->bezt;
949         prev = cycle_offset_triple(cycle, &tmp, &fcu->bezt[fcu->totvert - 2], last, first);
950         next = (bezt + 1);
951         
952         /* loop over all beztriples, adjusting handles */
953         while (a--) {
954                 /* clamp timing of handles to be on either side of beztriple */
955                 if (bezt->vec[0][0] > bezt->vec[1][0]) bezt->vec[0][0] = bezt->vec[1][0];
956                 if (bezt->vec[2][0] < bezt->vec[1][0]) bezt->vec[2][0] = bezt->vec[1][0];
957                 
958                 /* calculate auto-handles */
959                 BKE_nurb_handle_calc(bezt, prev, next, true);
960                 
961                 /* for automatic ease in and out */
962                 if (BEZT_IS_AUTOH(bezt) && !cycle) {
963                         /* only do this on first or last beztriple */
964                         if ((a == 0) || (a == fcu->totvert - 1)) {
965                                 /* set both handles to have same horizontal value as keyframe */
966                                 if (fcu->extend == FCURVE_EXTRAPOLATE_CONSTANT) {
967                                         bezt->vec[0][1] = bezt->vec[2][1] = bezt->vec[1][1];
968                                 }
969                         }
970                 }
971                 
972                 /* advance pointers for next iteration */
973                 prev = bezt;
974
975                 if (a == 1) {
976                         next = cycle_offset_triple(cycle, &tmp, &fcu->bezt[1], first, last);
977                 }
978                 else {
979                         next++;
980                 }
981
982                 bezt++;
983         }
984 }
985
986 void testhandles_fcurve(FCurve *fcu, const bool use_handle)
987 {
988         BezTriple *bezt;
989         unsigned int a;
990
991         /* only beztriples have handles (bpoints don't though) */
992         if (ELEM(NULL, fcu, fcu->bezt))
993                 return;
994
995         /* loop over beztriples */
996         for (a = 0, bezt = fcu->bezt; a < fcu->totvert; a++, bezt++) {
997                 BKE_nurb_bezt_handle_test(bezt, use_handle);
998         }
999
1000         /* recalculate handles */
1001         calchandles_fcurve(fcu);
1002 }
1003
1004 /* This function sorts BezTriples so that they are arranged in chronological order,
1005  * as tools working on F-Curves expect that the BezTriples are in order.
1006  */
1007 void sort_time_fcurve(FCurve *fcu)
1008 {
1009         bool ok = true;
1010         
1011         /* keep adjusting order of beztriples until nothing moves (bubble-sort) */
1012         while (ok) {
1013                 ok = 0;
1014                 
1015                 /* currently, will only be needed when there are beztriples */
1016                 if (fcu->bezt) {
1017                         BezTriple *bezt;
1018                         unsigned int a;
1019                         
1020                         /* loop over ALL points to adjust position in array and recalculate handles */
1021                         for (a = 0, bezt = fcu->bezt; a < fcu->totvert; a++, bezt++) {
1022                                 /* check if thee's a next beztriple which we could try to swap with current */
1023                                 if (a < (fcu->totvert - 1)) {
1024                                         /* swap if one is after the other (and indicate that order has changed) */
1025                                         if (bezt->vec[1][0] > (bezt + 1)->vec[1][0]) {
1026                                                 SWAP(BezTriple, *bezt, *(bezt + 1));
1027                                                 ok = 1;
1028                                         }
1029                                         
1030                                         /* if either one of both of the points exceeds crosses over the keyframe time... */
1031                                         if ( (bezt->vec[0][0] > bezt->vec[1][0]) && (bezt->vec[2][0] < bezt->vec[1][0]) ) {
1032                                                 /* swap handles if they have switched sides for some reason */
1033                                                 swap_v2_v2(bezt->vec[0], bezt->vec[2]);
1034                                         }
1035                                         else {
1036                                                 /* clamp handles */
1037                                                 CLAMP_MAX(bezt->vec[0][0], bezt->vec[1][0]);
1038                                                 CLAMP_MIN(bezt->vec[2][0], bezt->vec[1][0]);
1039                                         }
1040                                 }
1041                         }
1042                 }
1043         }
1044 }
1045
1046 /* This function tests if any BezTriples are out of order, thus requiring a sort */
1047 short test_time_fcurve(FCurve *fcu)
1048 {
1049         unsigned int a;
1050         
1051         /* sanity checks */
1052         if (fcu == NULL)
1053                 return 0;
1054         
1055         /* currently, only need to test beztriples */
1056         if (fcu->bezt) {
1057                 BezTriple *bezt;
1058                 
1059                 /* loop through all BezTriples, stopping when one exceeds the one after it */
1060                 for (a = 0, bezt = fcu->bezt; a < (fcu->totvert - 1); a++, bezt++) {
1061                         if (bezt->vec[1][0] > (bezt + 1)->vec[1][0])
1062                                 return 1;
1063                 }
1064         }
1065         else if (fcu->fpt) {
1066                 FPoint *fpt;
1067                 
1068                 /* loop through all FPoints, stopping when one exceeds the one after it */
1069                 for (a = 0, fpt = fcu->fpt; a < (fcu->totvert - 1); a++, fpt++) {
1070                         if (fpt->vec[0] > (fpt + 1)->vec[0])
1071                                 return 1;
1072                 }
1073         }
1074         
1075         /* none need any swapping */
1076         return 0;
1077 }
1078
1079 /* ***************************** Drivers ********************************* */
1080
1081 /* Driver Variables --------------------------- */
1082
1083 /* TypeInfo for Driver Variables (dvti) */
1084 typedef struct DriverVarTypeInfo {
1085         /* evaluation callback */
1086         float (*get_value)(ChannelDriver *driver, DriverVar *dvar);
1087         
1088         /* allocation of target slots */
1089         int num_targets;                                        /* number of target slots required */
1090         const char *target_names[MAX_DRIVER_TARGETS];   /* UI names that should be given to the slots */
1091         short target_flags[MAX_DRIVER_TARGETS];                 /* flags defining the requirements for each slot */
1092 } DriverVarTypeInfo;
1093
1094 /* Macro to begin definitions */
1095 #define BEGIN_DVAR_TYPEDEF(type) \
1096         {
1097         
1098 /* Macro to end definitions */
1099 #define END_DVAR_TYPEDEF \
1100         }
1101
1102 /* ......... */
1103
1104 static ID *dtar_id_ensure_proxy_from(ID *id)
1105 {
1106         if (id && GS(id->name) == ID_OB && ((Object *)id)->proxy_from)
1107                 return (ID *)(((Object *)id)->proxy_from);
1108         return id;
1109 }
1110
1111 /* Helper function to obtain a value using RNA from the specified source (for evaluating drivers) */
1112 static float dtar_get_prop_val(ChannelDriver *driver, DriverTarget *dtar)
1113 {
1114         PointerRNA id_ptr, ptr;
1115         PropertyRNA *prop;
1116         ID *id;
1117         int index = -1;
1118         float value = 0.0f;
1119         
1120         /* sanity check */
1121         if (ELEM(NULL, driver, dtar))
1122                 return 0.0f;
1123         
1124         id = dtar_id_ensure_proxy_from(dtar->id);
1125         
1126         /* error check for missing pointer... */
1127         if (id == NULL) {
1128                 if (G.debug & G_DEBUG) {
1129                         printf("Error: driver has an invalid target to use (path = %s)\n", dtar->rna_path);
1130                 }
1131                 
1132                 driver->flag |= DRIVER_FLAG_INVALID;
1133                 dtar->flag   |= DTAR_FLAG_INVALID;
1134                 return 0.0f;
1135         }
1136         
1137         /* get RNA-pointer for the ID-block given in target */
1138         RNA_id_pointer_create(id, &id_ptr);
1139         
1140         /* get property to read from, and get value as appropriate */
1141         if (RNA_path_resolve_property_full(&id_ptr, dtar->rna_path, &ptr, &prop, &index)) {
1142                 if (RNA_property_array_check(prop)) {
1143                         /* array */
1144                         if ((index >= 0) && (index < RNA_property_array_length(&ptr, prop))) {
1145                                 switch (RNA_property_type(prop)) {
1146                                         case PROP_BOOLEAN:
1147                                                 value = (float)RNA_property_boolean_get_index(&ptr, prop, index);
1148                                                 break;
1149                                         case PROP_INT:
1150                                                 value = (float)RNA_property_int_get_index(&ptr, prop, index);
1151                                                 break;
1152                                         case PROP_FLOAT:
1153                                                 value = RNA_property_float_get_index(&ptr, prop, index);
1154                                                 break;
1155                                         default:
1156                                                 break;
1157                                 }
1158                         }
1159                         else {
1160                                 /* out of bounds */
1161                                 if (G.debug & G_DEBUG) {
1162                                         printf("Driver Evaluation Error: array index is out of bounds for %s -> %s (%d)", 
1163                                                id->name, dtar->rna_path, index);
1164                                 }
1165                                 
1166                                 driver->flag |= DRIVER_FLAG_INVALID;
1167                                 dtar->flag   |= DTAR_FLAG_INVALID;
1168                                 return 0.0f;
1169                         }
1170                 }
1171                 else {
1172                         /* not an array */
1173                         switch (RNA_property_type(prop)) {
1174                                 case PROP_BOOLEAN:
1175                                         value = (float)RNA_property_boolean_get(&ptr, prop);
1176                                         break;
1177                                 case PROP_INT:
1178                                         value = (float)RNA_property_int_get(&ptr, prop);
1179                                         break;
1180                                 case PROP_FLOAT:
1181                                         value = RNA_property_float_get(&ptr, prop);
1182                                         break;
1183                                 case PROP_ENUM:
1184                                         value = (float)RNA_property_enum_get(&ptr, prop);
1185                                         break;
1186                                 default:
1187                                         break;
1188                         }
1189                 }
1190         }
1191         else {
1192                 /* path couldn't be resolved */
1193                 if (G.debug & G_DEBUG) {
1194                         printf("Driver Evaluation Error: cannot resolve target for %s -> %s\n", id->name, dtar->rna_path);
1195                 }
1196                 
1197                 driver->flag |= DRIVER_FLAG_INVALID;
1198                 dtar->flag   |= DTAR_FLAG_INVALID;
1199                 return 0.0f;
1200         }
1201         
1202         /* if we're still here, we should be ok... */
1203         dtar->flag &= ~DTAR_FLAG_INVALID;
1204         return value;
1205 }
1206
1207 /**
1208  * Same as 'dtar_get_prop_val'. but get the RNA property.
1209  */
1210 bool driver_get_variable_property(
1211         ChannelDriver *driver, DriverTarget *dtar,
1212         PointerRNA *r_ptr, PropertyRNA **r_prop, int *r_index)
1213 {
1214         PointerRNA id_ptr;
1215         PointerRNA ptr;
1216         PropertyRNA *prop;
1217         ID *id;
1218         int index = -1;
1219
1220         /* sanity check */
1221         if (ELEM(NULL, driver, dtar))
1222                 return false;
1223
1224         id = dtar_id_ensure_proxy_from(dtar->id);
1225
1226         /* error check for missing pointer... */
1227         if (id == NULL) {
1228                 if (G.debug & G_DEBUG) {
1229                         printf("Error: driver has an invalid target to use (path = %s)\n", dtar->rna_path);
1230                 }
1231
1232                 driver->flag |= DRIVER_FLAG_INVALID;
1233                 dtar->flag   |= DTAR_FLAG_INVALID;
1234                 return false;
1235         }
1236
1237         /* get RNA-pointer for the ID-block given in target */
1238         RNA_id_pointer_create(id, &id_ptr);
1239
1240         /* get property to read from, and get value as appropriate */
1241         if (dtar->rna_path == NULL || dtar->rna_path[0] == '\0') {
1242                 ptr = PointerRNA_NULL;
1243                 prop = NULL; /* ok */
1244         }
1245         else if (RNA_path_resolve_property_full(&id_ptr, dtar->rna_path, &ptr, &prop, &index)) {
1246                 /* ok */
1247         }
1248         else {
1249                 /* path couldn't be resolved */
1250                 if (G.debug & G_DEBUG) {
1251                         printf("Driver Evaluation Error: cannot resolve target for %s -> %s\n", id->name, dtar->rna_path);
1252                 }
1253
1254                 ptr = PointerRNA_NULL;
1255                 *r_prop = NULL;
1256                 *r_index = -1;
1257
1258                 driver->flag |= DRIVER_FLAG_INVALID;
1259                 dtar->flag   |= DTAR_FLAG_INVALID;
1260                 return false;
1261         }
1262
1263         *r_ptr = ptr;
1264         *r_prop = prop;
1265         *r_index = index;
1266
1267         /* if we're still here, we should be ok... */
1268         dtar->flag &= ~DTAR_FLAG_INVALID;
1269         return true;
1270 }
1271
1272 #if 0
1273 /* Helper function to obtain a pointer to a Pose Channel (for evaluating drivers) */
1274 static bPoseChannel *dtar_get_pchan_ptr(ChannelDriver *driver, DriverTarget *dtar)
1275 {
1276         ID *id;
1277         /* sanity check */
1278         if (ELEM(NULL, driver, dtar))
1279                 return NULL;
1280
1281         id = dtar_id_ensure_proxy_from(dtar->id);
1282
1283         /* check if the ID here is a valid object */
1284         if (id && GS(id->name)) {
1285                 Object *ob = (Object *)id;
1286                 
1287                 /* get pose, and subsequently, posechannel */
1288                 return BKE_pose_channel_find_name(ob->pose, dtar->pchan_name);
1289         }
1290         else {
1291                 /* cannot find a posechannel this way */
1292                 return NULL;
1293         }
1294 }
1295 #endif
1296
1297 static short driver_check_valid_targets(ChannelDriver *driver, DriverVar *dvar)
1298 {
1299         short valid_targets = 0;
1300
1301         DRIVER_TARGETS_USED_LOOPER(dvar)
1302         {
1303                 Object *ob = (Object *)dtar_id_ensure_proxy_from(dtar->id);
1304
1305                 /* check if this target has valid data */
1306                 if ((ob == NULL) || (GS(ob->id.name) != ID_OB)) {
1307                         /* invalid target, so will not have enough targets */
1308                         driver->flag |= DRIVER_FLAG_INVALID;
1309                         dtar->flag |= DTAR_FLAG_INVALID;
1310                 }
1311                 else {
1312                         /* target seems to be OK now... */
1313                         dtar->flag &= ~DTAR_FLAG_INVALID;
1314                         valid_targets++;
1315                 }
1316         }
1317         DRIVER_TARGETS_LOOPER_END
1318
1319         return valid_targets;
1320 }
1321
1322 /* ......... */
1323
1324 /* evaluate 'single prop' driver variable */
1325 static float dvar_eval_singleProp(ChannelDriver *driver, DriverVar *dvar)
1326 {
1327         /* just evaluate the first target slot */
1328         return dtar_get_prop_val(driver, &dvar->targets[0]);
1329 }
1330
1331 /* evaluate 'rotation difference' driver variable */
1332 static float dvar_eval_rotDiff(ChannelDriver *driver, DriverVar *dvar)
1333 {
1334         short valid_targets = driver_check_valid_targets(driver, dvar);
1335
1336         /* make sure we have enough valid targets to use - all or nothing for now... */
1337         if (driver_check_valid_targets(driver, dvar) != 2) {
1338                 if (G.debug & G_DEBUG) {
1339                         printf("RotDiff DVar: not enough valid targets (n = %d) (a = %p, b = %p)\n",
1340                                 valid_targets, dvar->targets[0].id, dvar->targets[1].id);
1341                 }
1342                 return 0.0f;
1343         }
1344
1345         float (*mat[2])[4];
1346
1347         /* NOTE: for now, these are all just worldspace */
1348         for (int i = 0; i < 2; i++) {
1349                 /* get pointer to loc values to store in */
1350                 DriverTarget *dtar = &dvar->targets[i];
1351                 Object *ob = (Object *)dtar_id_ensure_proxy_from(dtar->id);
1352                 bPoseChannel *pchan;
1353
1354                 /* after the checks above, the targets should be valid here... */
1355                 BLI_assert((ob != NULL) && (GS(ob->id.name) == ID_OB));
1356
1357                 /* try to get posechannel */
1358                 pchan = BKE_pose_channel_find_name(ob->pose, dtar->pchan_name);
1359
1360                 /* check if object or bone */
1361                 if (pchan) {
1362                         /* bone */
1363                         mat[i] = pchan->pose_mat;
1364                 }
1365                 else {
1366                         /* object */
1367                         mat[i] = ob->obmat;
1368                 }
1369         }
1370
1371         float q1[4], q2[4], quat[4], angle;
1372
1373         /* use the final posed locations */
1374         mat4_to_quat(q1, mat[0]);
1375         mat4_to_quat(q2, mat[1]);
1376
1377         invert_qt_normalized(q1);
1378         mul_qt_qtqt(quat, q1, q2);
1379         angle = 2.0f * (saacos(quat[0]));
1380         angle = ABS(angle);
1381
1382         return (angle > (float)M_PI) ? (float)((2.0f * (float)M_PI) - angle) : (float)(angle);
1383 }
1384
1385 /* evaluate 'location difference' driver variable */
1386 /* TODO: this needs to take into account space conversions... */
1387 static float dvar_eval_locDiff(ChannelDriver *driver, DriverVar *dvar)
1388 {
1389         float loc1[3] = {0.0f, 0.0f, 0.0f};
1390         float loc2[3] = {0.0f, 0.0f, 0.0f};
1391         short valid_targets = driver_check_valid_targets(driver, dvar);
1392
1393         /* make sure we have enough valid targets to use - all or nothing for now... */
1394         if (valid_targets < dvar->num_targets) {
1395                 if (G.debug & G_DEBUG) {
1396                         printf("LocDiff DVar: not enough valid targets (n = %d) (a = %p, b = %p)\n",
1397                                 valid_targets, dvar->targets[0].id, dvar->targets[1].id);
1398                 }
1399                 return 0.0f;
1400         }
1401
1402         /* SECOND PASS: get two location values */
1403         /* NOTE: for now, these are all just worldspace */
1404         DRIVER_TARGETS_USED_LOOPER(dvar)
1405         {
1406                 /* get pointer to loc values to store in */
1407                 Object *ob = (Object *)dtar_id_ensure_proxy_from(dtar->id);
1408                 bPoseChannel *pchan;
1409                 float tmp_loc[3];
1410                 
1411                 /* after the checks above, the targets should be valid here... */
1412                 BLI_assert((ob != NULL) && (GS(ob->id.name) == ID_OB));
1413                 
1414                 /* try to get posechannel */
1415                 pchan = BKE_pose_channel_find_name(ob->pose, dtar->pchan_name);
1416                 
1417                 /* check if object or bone */
1418                 if (pchan) {
1419                         /* bone */
1420                         if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1421                                 if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1422                                         float mat[4][4];
1423                                         
1424                                         /* extract transform just like how the constraints do it! */
1425                                         copy_m4_m4(mat, pchan->pose_mat);
1426                                         BKE_constraint_mat_convertspace(ob, pchan, mat, CONSTRAINT_SPACE_POSE, CONSTRAINT_SPACE_LOCAL, false);
1427                                         
1428                                         /* ... and from that, we get our transform */
1429                                         copy_v3_v3(tmp_loc, mat[3]);
1430                                 }
1431                                 else {
1432                                         /* transform space (use transform values directly) */
1433                                         copy_v3_v3(tmp_loc, pchan->loc);
1434                                 }
1435                         }
1436                         else {
1437                                 /* convert to worldspace */
1438                                 copy_v3_v3(tmp_loc, pchan->pose_head);
1439                                 mul_m4_v3(ob->obmat, tmp_loc);
1440                         }
1441                 }
1442                 else {
1443                         /* object */
1444                         if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1445                                 if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1446                                         /* XXX: this should practically be the same as transform space... */
1447                                         float mat[4][4];
1448                                         
1449                                         /* extract transform just like how the constraints do it! */
1450                                         copy_m4_m4(mat, ob->obmat);
1451                                         BKE_constraint_mat_convertspace(ob, NULL, mat, CONSTRAINT_SPACE_WORLD, CONSTRAINT_SPACE_LOCAL, false);
1452                                         
1453                                         /* ... and from that, we get our transform */
1454                                         copy_v3_v3(tmp_loc, mat[3]);
1455                                 }
1456                                 else {
1457                                         /* transform space (use transform values directly) */
1458                                         copy_v3_v3(tmp_loc, ob->loc);
1459                                 }
1460                         }
1461                         else {
1462                                 /* worldspace */
1463                                 copy_v3_v3(tmp_loc, ob->obmat[3]);
1464                         }
1465                 }
1466                 
1467                 /* copy the location to the right place */
1468                 if (tarIndex) {
1469                         copy_v3_v3(loc2, tmp_loc);
1470                 }
1471                 else {
1472                         copy_v3_v3(loc1, tmp_loc);
1473                 }
1474         }
1475         DRIVER_TARGETS_LOOPER_END
1476         
1477         
1478         /* if we're still here, there should now be two targets to use,
1479          * so just take the length of the vector between these points 
1480          */
1481         return len_v3v3(loc1, loc2);
1482 }
1483
1484 /* evaluate 'transform channel' driver variable */
1485 static float dvar_eval_transChan(ChannelDriver *driver, DriverVar *dvar)
1486 {
1487         DriverTarget *dtar = &dvar->targets[0];
1488         Object *ob = (Object *)dtar_id_ensure_proxy_from(dtar->id);
1489         bPoseChannel *pchan;
1490         float mat[4][4];
1491         float oldEul[3] = {0.0f, 0.0f, 0.0f};
1492         bool use_eulers = false;
1493         short rot_order = ROT_MODE_EUL;
1494         
1495         /* check if this target has valid data */
1496         if ((ob == NULL) || (GS(ob->id.name) != ID_OB)) {
1497                 /* invalid target, so will not have enough targets */
1498                 driver->flag |= DRIVER_FLAG_INVALID;
1499                 dtar->flag   |= DTAR_FLAG_INVALID;
1500                 return 0.0f;
1501         }
1502         else {
1503                 /* target should be valid now */
1504                 dtar->flag &= ~DTAR_FLAG_INVALID;
1505         }
1506         
1507         /* try to get posechannel */
1508         pchan = BKE_pose_channel_find_name(ob->pose, dtar->pchan_name);
1509         
1510         /* check if object or bone, and get transform matrix accordingly 
1511          *      - "useEulers" code is used to prevent the problems associated with non-uniqueness
1512          *        of euler decomposition from matrices [#20870]
1513          *      - localspace is for [#21384], where parent results are not wanted
1514          *        but local-consts is for all the common "corrective-shapes-for-limbs" situations
1515          */
1516         if (pchan) {
1517                 /* bone */
1518                 if (pchan->rotmode > 0) {
1519                         copy_v3_v3(oldEul, pchan->eul);
1520                         rot_order = pchan->rotmode;
1521                         use_eulers = true;
1522                 }
1523                 
1524                 if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1525                         if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1526                                 /* just like how the constraints do it! */
1527                                 copy_m4_m4(mat, pchan->pose_mat);
1528                                 BKE_constraint_mat_convertspace(ob, pchan, mat, CONSTRAINT_SPACE_POSE, CONSTRAINT_SPACE_LOCAL, false);
1529                         }
1530                         else {
1531                                 /* specially calculate local matrix, since chan_mat is not valid 
1532                                  * since it stores delta transform of pose_mat so that deforms work
1533                                  * so it cannot be used here for "transform" space
1534                                  */
1535                                 BKE_pchan_to_mat4(pchan, mat);
1536                         }
1537                 }
1538                 else {
1539                         /* worldspace matrix */
1540                         mul_m4_m4m4(mat, ob->obmat, pchan->pose_mat);
1541                 }
1542         }
1543         else {
1544                 /* object */
1545                 if (ob->rotmode > 0) {
1546                         copy_v3_v3(oldEul, ob->rot);
1547                         rot_order = ob->rotmode;
1548                         use_eulers = true;
1549                 }
1550                 
1551                 if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1552                         if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1553                                 /* just like how the constraints do it! */
1554                                 copy_m4_m4(mat, ob->obmat);
1555                                 BKE_constraint_mat_convertspace(ob, NULL, mat, CONSTRAINT_SPACE_WORLD, CONSTRAINT_SPACE_LOCAL, false);
1556                         }
1557                         else {
1558                                 /* transforms to matrix */
1559                                 BKE_object_to_mat4(ob, mat);
1560                         }
1561                 }
1562                 else {
1563                         /* worldspace matrix - just the good-old one */
1564                         copy_m4_m4(mat, ob->obmat);
1565                 }
1566         }
1567         
1568         /* check which transform */
1569         if (dtar->transChan >= MAX_DTAR_TRANSCHAN_TYPES) {
1570                 /* not valid channel */
1571                 return 0.0f;
1572         }
1573         else if (dtar->transChan >= DTAR_TRANSCHAN_SCALEX) {
1574                 /* extract scale, and choose the right axis */
1575                 float scale[3];
1576                 
1577                 mat4_to_size(scale, mat);
1578                 return scale[dtar->transChan - DTAR_TRANSCHAN_SCALEX];
1579         }
1580         else if (dtar->transChan >= DTAR_TRANSCHAN_ROTX) {
1581                 /* extract rotation as eulers (if needed) 
1582                  *      - definitely if rotation order isn't eulers already
1583                  *      - if eulers, then we have 2 options:
1584                  *              a) decompose transform matrix as required, then try to make eulers from
1585                  *                 there compatible with original values
1586                  *              b) [NOT USED] directly use the original values (no decomposition) 
1587                  *                      - only an option for "transform space", if quality is really bad with a)
1588                  */
1589                 float eul[3];
1590                 
1591                 mat4_to_eulO(eul, rot_order, mat);
1592                 
1593                 if (use_eulers) {
1594                         compatible_eul(eul, oldEul);
1595                 }
1596                 
1597                 return eul[dtar->transChan - DTAR_TRANSCHAN_ROTX];
1598         }
1599         else {
1600                 /* extract location and choose right axis */
1601                 return mat[3][dtar->transChan];
1602         }
1603 }
1604
1605 /* ......... */
1606
1607 /* Table of Driver Varaiable Type Info Data */
1608 static DriverVarTypeInfo dvar_types[MAX_DVAR_TYPES] = {
1609         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_SINGLE_PROP)
1610                 dvar_eval_singleProp,     /* eval callback */
1611                 1,     /* number of targets used */
1612                 {"Property"},     /* UI names for targets */
1613                 {0}     /* flags */
1614         END_DVAR_TYPEDEF,
1615         
1616         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_ROT_DIFF)
1617                 dvar_eval_rotDiff,     /* eval callback */
1618                 2,     /* number of targets used */
1619                 {"Object/Bone 1", "Object/Bone 2"},     /* UI names for targets */
1620                 {DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY, DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY} /* flags */
1621         END_DVAR_TYPEDEF,
1622         
1623         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_LOC_DIFF)
1624                 dvar_eval_locDiff,     /* eval callback */
1625                 2,     /* number of targets used */
1626                 {"Object/Bone 1", "Object/Bone 2"},     /* UI names for targets */
1627                 {DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY, DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY} /* flags */
1628         END_DVAR_TYPEDEF,
1629         
1630         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_TRANSFORM_CHAN)
1631                 dvar_eval_transChan,     /* eval callback */
1632                 1,     /* number of targets used */
1633                 {"Object/Bone"},     /* UI names for targets */
1634                 {DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY}   /* flags */
1635         END_DVAR_TYPEDEF,
1636 };
1637
1638 /* Get driver variable typeinfo */
1639 static const DriverVarTypeInfo *get_dvar_typeinfo(int type)
1640 {
1641         /* check if valid type */
1642         if ((type >= 0) && (type < MAX_DVAR_TYPES))
1643                 return &dvar_types[type];
1644         else
1645                 return NULL;
1646 }
1647
1648 /* Driver API --------------------------------- */
1649
1650 /* Perform actual freeing driver variable and remove it from the given list */
1651 void driver_free_variable(ListBase *variables, DriverVar *dvar)
1652 {
1653         /* sanity checks */
1654         if (dvar == NULL)
1655                 return;
1656                 
1657         /* free target vars 
1658          *      - need to go over all of them, not just up to the ones that are used
1659          *        currently, since there may be some lingering RNA paths from 
1660          *    previous users needing freeing
1661          */
1662         DRIVER_TARGETS_LOOPER(dvar) 
1663         {
1664                 /* free RNA path if applicable */
1665                 if (dtar->rna_path)
1666                         MEM_freeN(dtar->rna_path);
1667         }
1668         DRIVER_TARGETS_LOOPER_END
1669         
1670         /* remove the variable from the driver */
1671         BLI_freelinkN(variables, dvar);
1672 }
1673
1674 /* Free the driver variable and do extra updates */
1675 void driver_free_variable_ex(ChannelDriver *driver, DriverVar *dvar)
1676 {
1677         /* remove and free the driver variable */
1678         driver_free_variable(&driver->variables, dvar);
1679         
1680 #ifdef WITH_PYTHON
1681         /* since driver variables are cached, the expression needs re-compiling too */
1682         if (driver->type == DRIVER_TYPE_PYTHON)
1683                 driver->flag |= DRIVER_FLAG_RENAMEVAR;
1684 #endif
1685 }
1686
1687 /* Copy driver variables from src_vars list to dst_vars list */
1688 void driver_variables_copy(ListBase *dst_vars, const ListBase *src_vars)
1689 {
1690         BLI_assert(BLI_listbase_is_empty(dst_vars));
1691         BLI_duplicatelist(dst_vars, src_vars);
1692         
1693         for (DriverVar *dvar = dst_vars->first; dvar; dvar = dvar->next) {
1694                 /* need to go over all targets so that we don't leave any dangling paths */
1695                 DRIVER_TARGETS_LOOPER(dvar) 
1696                 {
1697                         /* make a copy of target's rna path if available */
1698                         if (dtar->rna_path)
1699                                 dtar->rna_path = MEM_dupallocN(dtar->rna_path);
1700                 }
1701                 DRIVER_TARGETS_LOOPER_END
1702         }
1703 }
1704
1705 /* Change the type of driver variable */
1706 void driver_change_variable_type(DriverVar *dvar, int type)
1707 {
1708         const DriverVarTypeInfo *dvti = get_dvar_typeinfo(type);
1709         
1710         /* sanity check */
1711         if (ELEM(NULL, dvar, dvti))
1712                 return;
1713                 
1714         /* set the new settings */
1715         dvar->type = type;
1716         dvar->num_targets = dvti->num_targets;
1717         
1718         /* make changes to the targets based on the defines for these types 
1719          * NOTE: only need to make sure the ones we're using here are valid...
1720          */
1721         DRIVER_TARGETS_USED_LOOPER(dvar)
1722         {
1723                 short flags = dvti->target_flags[tarIndex];
1724                 
1725                 /* store the flags */
1726                 dtar->flag = flags;
1727                 
1728                 /* object ID types only, or idtype not yet initialized */
1729                 if ((flags & DTAR_FLAG_ID_OB_ONLY) || (dtar->idtype == 0))
1730                         dtar->idtype = ID_OB;
1731         }
1732         DRIVER_TARGETS_LOOPER_END
1733 }
1734
1735 /* Validate driver name (after being renamed) */
1736 void driver_variable_name_validate(DriverVar *dvar)
1737 {
1738         /* Special character blacklist */
1739         const char special_char_blacklist[] = {
1740             '~', '`', '!', '@', '#', '$', '%', '^', '&', '*', '+', '=', '-',
1741             '/', '\\', '?', ':', ';',  '<', '>', '{', '}', '[', ']', '|',
1742             ' ', '.', '\t', '\n', '\r'
1743         };
1744         
1745         /* sanity checks */
1746         if (dvar == NULL)
1747                 return;
1748         
1749         /* clear all invalid-name flags */
1750         dvar->flag &= ~DVAR_ALL_INVALID_FLAGS;
1751         
1752         /* 0) Zero-length identifiers are not allowed */
1753         if (dvar->name[0] == '\0') {
1754                 dvar->flag |= DVAR_FLAG_INVALID_EMPTY;
1755         }
1756         
1757         /* 1) Must start with a letter */
1758         /* XXX: We assume that valid unicode letters in other languages are ok too, hence the blacklisting */
1759         if (ELEM(dvar->name[0], '0', '1', '2', '3', '4', '5', '6', '7', '8', '9')) {
1760                 dvar->flag |= DVAR_FLAG_INVALID_START_NUM;
1761         }
1762         else if (dvar->name[0] == '_') {
1763                 /* NOTE: We don't allow names to start with underscores (i.e. it helps when ruling out security risks) */
1764                 dvar->flag |= DVAR_FLAG_INVALID_START_CHAR;
1765         }
1766         
1767         /* 2) Must not contain invalid stuff in the middle of the string */
1768         if (strchr(dvar->name, ' ')) {
1769                 dvar->flag |= DVAR_FLAG_INVALID_HAS_SPACE;
1770         }
1771         if (strchr(dvar->name, '.')) {
1772                 dvar->flag |= DVAR_FLAG_INVALID_HAS_DOT;
1773         }
1774         
1775         /* 3) Check for special characters - Either at start, or in the middle */
1776         for (int i = 0; i < sizeof(special_char_blacklist); i++) {
1777                 char *match = strchr(dvar->name, special_char_blacklist[i]);
1778                 
1779                 if (match == dvar->name)
1780                         dvar->flag |= DVAR_FLAG_INVALID_START_CHAR;
1781                 else if (match != NULL)
1782                         dvar->flag |= DVAR_FLAG_INVALID_HAS_SPECIAL;
1783         }
1784         
1785         /* 4) Check if the name is a reserved keyword
1786          * NOTE: These won't confuse Python, but it will be impossible to use the variable
1787          *       in an expression without Python misinterpreting what these are for
1788          */
1789 #ifdef WITH_PYTHON
1790         if (BPY_string_is_keyword(dvar->name)) {
1791                 dvar->flag |= DVAR_FLAG_INVALID_PY_KEYWORD;
1792         }
1793 #endif
1794
1795         /* If any these conditions match, the name is invalid */
1796         if (dvar->flag & DVAR_ALL_INVALID_FLAGS)
1797                 dvar->flag |= DVAR_FLAG_INVALID_NAME;
1798 }
1799
1800 /* Add a new driver variable */
1801 DriverVar *driver_add_new_variable(ChannelDriver *driver)
1802 {
1803         DriverVar *dvar;
1804         
1805         /* sanity checks */
1806         if (driver == NULL)
1807                 return NULL;
1808                 
1809         /* make a new variable */
1810         dvar = MEM_callocN(sizeof(DriverVar), "DriverVar");
1811         BLI_addtail(&driver->variables, dvar);
1812         
1813         /* give the variable a 'unique' name */
1814         strcpy(dvar->name, CTX_DATA_(BLT_I18NCONTEXT_ID_ACTION, "var"));
1815         BLI_uniquename(&driver->variables, dvar, CTX_DATA_(BLT_I18NCONTEXT_ID_ACTION, "var"), '_',
1816                        offsetof(DriverVar, name), sizeof(dvar->name));
1817         
1818         /* set the default type to 'single prop' */
1819         driver_change_variable_type(dvar, DVAR_TYPE_SINGLE_PROP);
1820         
1821 #ifdef WITH_PYTHON
1822         /* since driver variables are cached, the expression needs re-compiling too */
1823         if (driver->type == DRIVER_TYPE_PYTHON)
1824                 driver->flag |= DRIVER_FLAG_RENAMEVAR;
1825 #endif
1826         
1827         /* return the target */
1828         return dvar;
1829 }
1830
1831 /* This frees the driver itself */
1832 void fcurve_free_driver(FCurve *fcu)
1833 {
1834         ChannelDriver *driver;
1835         DriverVar *dvar, *dvarn;
1836         
1837         /* sanity checks */
1838         if (ELEM(NULL, fcu, fcu->driver))
1839                 return;
1840         driver = fcu->driver;
1841         
1842         /* free driver targets */
1843         for (dvar = driver->variables.first; dvar; dvar = dvarn) {
1844                 dvarn = dvar->next;
1845                 driver_free_variable_ex(driver, dvar);
1846         }
1847
1848 #ifdef WITH_PYTHON
1849         /* free compiled driver expression */
1850         if (driver->expr_comp)
1851                 BPY_DECREF(driver->expr_comp);
1852 #endif
1853
1854         /* free driver itself, then set F-Curve's point to this to NULL (as the curve may still be used) */
1855         MEM_freeN(driver);
1856         fcu->driver = NULL;
1857 }
1858
1859 /* This makes a copy of the given driver */
1860 ChannelDriver *fcurve_copy_driver(const ChannelDriver *driver)
1861 {
1862         ChannelDriver *ndriver;
1863         
1864         /* sanity checks */
1865         if (driver == NULL)
1866                 return NULL;
1867                 
1868         /* copy all data */
1869         ndriver = MEM_dupallocN(driver);
1870         ndriver->expr_comp = NULL;
1871         
1872         /* copy variables */
1873         BLI_listbase_clear(&ndriver->variables); /* to get rid of refs to non-copied data (that's still used on original) */ 
1874         driver_variables_copy(&ndriver->variables, &driver->variables);
1875         
1876         /* return the new driver */
1877         return ndriver;
1878 }
1879
1880 /* Driver Evaluation -------------------------- */
1881
1882 /* Evaluate a Driver Variable to get a value that contributes to the final */
1883 float driver_get_variable_value(ChannelDriver *driver, DriverVar *dvar)
1884 {
1885         const DriverVarTypeInfo *dvti;
1886
1887         /* sanity check */
1888         if (ELEM(NULL, driver, dvar))
1889                 return 0.0f;
1890         
1891         /* call the relevant callbacks to get the variable value 
1892          * using the variable type info, storing the obtained value
1893          * in dvar->curval so that drivers can be debugged
1894          */
1895         dvti = get_dvar_typeinfo(dvar->type);
1896         
1897         if (dvti && dvti->get_value)
1898                 dvar->curval = dvti->get_value(driver, dvar);
1899         else
1900                 dvar->curval = 0.0f;
1901         
1902         return dvar->curval;
1903 }
1904
1905 /* Evaluate an Channel-Driver to get a 'time' value to use instead of "evaltime"
1906  *      - "evaltime" is the frame at which F-Curve is being evaluated
1907  *  - has to return a float value
1908  */
1909 float evaluate_driver(PathResolvedRNA *anim_rna, ChannelDriver *driver, const float evaltime)
1910 {
1911         DriverVar *dvar;
1912         
1913         /* check if driver can be evaluated */
1914         if (driver->flag & DRIVER_FLAG_INVALID)
1915                 return 0.0f;
1916         
1917         switch (driver->type) {
1918                 case DRIVER_TYPE_AVERAGE: /* average values of driver targets */
1919                 case DRIVER_TYPE_SUM: /* sum values of driver targets */
1920                 {
1921                         /* check how many variables there are first (i.e. just one?) */
1922                         if (BLI_listbase_is_single(&driver->variables)) {
1923                                 /* just one target, so just use that */
1924                                 dvar = driver->variables.first;
1925                                 driver->curval = driver_get_variable_value(driver, dvar);
1926                         }
1927                         else {
1928                                 /* more than one target, so average the values of the targets */
1929                                 float value = 0.0f;
1930                                 int tot = 0;
1931                                 
1932                                 /* loop through targets, adding (hopefully we don't get any overflow!) */
1933                                 for (dvar = driver->variables.first; dvar; dvar = dvar->next) {
1934                                         value += driver_get_variable_value(driver, dvar);
1935                                         tot++;
1936                                 }
1937                                 
1938                                 /* perform operations on the total if appropriate */
1939                                 if (driver->type == DRIVER_TYPE_AVERAGE)
1940                                         driver->curval = tot ? (value / (float)tot) : 0.0f;
1941                                 else
1942                                         driver->curval = value;
1943                         }
1944                         break;
1945                 }
1946                 case DRIVER_TYPE_MIN: /* smallest value */
1947                 case DRIVER_TYPE_MAX: /* largest value */
1948                 {
1949                         float value = 0.0f;
1950                         
1951                         /* loop through the variables, getting the values and comparing them to existing ones */
1952                         for (dvar = driver->variables.first; dvar; dvar = dvar->next) {
1953                                 /* get value */
1954                                 float tmp_val = driver_get_variable_value(driver, dvar);
1955                                 
1956                                 /* store this value if appropriate */
1957                                 if (dvar->prev) {
1958                                         /* check if greater/smaller than the baseline */
1959                                         if (driver->type == DRIVER_TYPE_MAX) {
1960                                                 /* max? */
1961                                                 if (tmp_val > value) 
1962                                                         value = tmp_val;
1963                                         }
1964                                         else {
1965                                                 /* min? */
1966                                                 if (tmp_val < value) 
1967                                                         value = tmp_val;
1968                                         }
1969                                 }
1970                                 else {
1971                                         /* first item - make this the baseline for comparisons */
1972                                         value = tmp_val;
1973                                 }
1974                         }
1975                         
1976                         /* store value in driver */
1977                         driver->curval = value;
1978                         break;
1979                 }
1980                 case DRIVER_TYPE_PYTHON: /* expression */
1981                 {
1982 #ifdef WITH_PYTHON
1983                         /* check for empty or invalid expression */
1984                         if ( (driver->expression[0] == '\0') ||
1985                              (driver->flag & DRIVER_FLAG_INVALID) )
1986                         {
1987                                 driver->curval = 0.0f;
1988                         }
1989                         else {
1990                                 /* this evaluates the expression using Python, and returns its result:
1991                                  *  - on errors it reports, then returns 0.0f
1992                                  */
1993                                 BLI_mutex_lock(&python_driver_lock);
1994
1995                                 driver->curval = BPY_driver_exec(anim_rna, driver, evaltime);
1996
1997                                 BLI_mutex_unlock(&python_driver_lock);
1998                         }
1999 #else /* WITH_PYTHON*/
2000                         UNUSED_VARS(anim_rna, evaltime);
2001 #endif /* WITH_PYTHON*/
2002                         break;
2003                 }
2004                 default:
2005                 {
2006                         /* special 'hack' - just use stored value 
2007                          *      This is currently used as the mechanism which allows animated settings to be able
2008                          *  to be changed via the UI.
2009                          */
2010                         break;
2011                 }
2012         }
2013         
2014         /* return value for driver */
2015         return driver->curval;
2016 }
2017
2018 /* ***************************** Curve Calculations ********************************* */
2019
2020 /* The total length of the handles is not allowed to be more
2021  * than the horizontal distance between (v1-v4).
2022  * This is to prevent curve loops.
2023  */
2024 void correct_bezpart(float v1[2], float v2[2], float v3[2], float v4[2])
2025 {
2026         float h1[2], h2[2], len1, len2, len, fac;
2027         
2028         /* calculate handle deltas */
2029         h1[0] = v1[0] - v2[0];
2030         h1[1] = v1[1] - v2[1];
2031         
2032         h2[0] = v4[0] - v3[0];
2033         h2[1] = v4[1] - v3[1];
2034         
2035         /* calculate distances: 
2036          *  - len       = span of time between keyframes
2037          *      - len1  = length of handle of start key
2038          *      - len2  = length of handle of end key
2039          */
2040         len = v4[0] - v1[0];
2041         len1 = fabsf(h1[0]);
2042         len2 = fabsf(h2[0]);
2043         
2044         /* if the handles have no length, no need to do any corrections */
2045         if ((len1 + len2) == 0.0f)
2046                 return;
2047                 
2048         /* the two handles cross over each other, so force them
2049          * apart using the proportion they overlap 
2050          */
2051         if ((len1 + len2) > len) {
2052                 fac = len / (len1 + len2);
2053                 
2054                 v2[0] = (v1[0] - fac * h1[0]);
2055                 v2[1] = (v1[1] - fac * h1[1]);
2056                 
2057                 v3[0] = (v4[0] - fac * h2[0]);
2058                 v3[1] = (v4[1] - fac * h2[1]);
2059         }
2060 }
2061
2062 /* find root ('zero') */
2063 static int findzero(float x, float q0, float q1, float q2, float q3, float *o)
2064 {
2065         double c0, c1, c2, c3, a, b, c, p, q, d, t, phi;
2066         int nr = 0;
2067
2068         c0 = q0 - x;
2069         c1 = 3.0f * (q1 - q0);
2070         c2 = 3.0f * (q0 - 2.0f * q1 + q2);
2071         c3 = q3 - q0 + 3.0f * (q1 - q2);
2072         
2073         if (c3 != 0.0) {
2074                 a = c2 / c3;
2075                 b = c1 / c3;
2076                 c = c0 / c3;
2077                 a = a / 3;
2078
2079                 p = b / 3 - a * a;
2080                 q = (2 * a * a * a - a * b + c) / 2;
2081                 d = q * q + p * p * p;
2082                 
2083                 if (d > 0.0) {
2084                         t = sqrt(d);
2085                         o[0] = (float)(sqrt3d(-q + t) + sqrt3d(-q - t) - a);
2086                         
2087                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
2088                         else return 0;
2089                 }
2090                 else if (d == 0.0) {
2091                         t = sqrt3d(-q);
2092                         o[0] = (float)(2 * t - a);
2093                         
2094                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
2095                         o[nr] = (float)(-t - a);
2096                         
2097                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr + 1;
2098                         else return nr;
2099                 }
2100                 else {
2101                         phi = acos(-q / sqrt(-(p * p * p)));
2102                         t = sqrt(-p);
2103                         p = cos(phi / 3);
2104                         q = sqrt(3 - 3 * p * p);
2105                         o[0] = (float)(2 * t * p - a);
2106                         
2107                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
2108                         o[nr] = (float)(-t * (p + q) - a);
2109                         
2110                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) nr++;
2111                         o[nr] = (float)(-t * (p - q) - a);
2112                         
2113                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr + 1;
2114                         else return nr;
2115                 }
2116         }
2117         else {
2118                 a = c2;
2119                 b = c1;
2120                 c = c0;
2121                 
2122                 if (a != 0.0) {
2123                         /* discriminant */
2124                         p = b * b - 4 * a * c;
2125                         
2126                         if (p > 0) {
2127                                 p = sqrt(p);
2128                                 o[0] = (float)((-b - p) / (2 * a));
2129                                 
2130                                 if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
2131                                 o[nr] = (float)((-b + p) / (2 * a));
2132                                 
2133                                 if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr + 1;
2134                                 else return nr;
2135                         }
2136                         else if (p == 0) {
2137                                 o[0] = (float)(-b / (2 * a));
2138                                 if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
2139                                 else return 0;
2140                         }
2141                 }
2142                 else if (b != 0.0) {
2143                         o[0] = (float)(-c / b);
2144                         
2145                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
2146                         else return 0;
2147                 }
2148                 else if (c == 0.0) {
2149                         o[0] = 0.0;
2150                         return 1;
2151                 }
2152                 
2153                 return 0;
2154         }
2155 }
2156
2157 static void berekeny(float f1, float f2, float f3, float f4, float *o, int b)
2158 {
2159         float t, c0, c1, c2, c3;
2160         int a;
2161
2162         c0 = f1;
2163         c1 = 3.0f * (f2 - f1);
2164         c2 = 3.0f * (f1 - 2.0f * f2 + f3);
2165         c3 = f4 - f1 + 3.0f * (f2 - f3);
2166
2167         for (a = 0; a < b; a++) {
2168                 t = o[a];
2169                 o[a] = c0 + t * c1 + t * t * c2 + t * t * t * c3;
2170         }
2171 }
2172
2173 #if 0
2174 static void berekenx(float *f, float *o, int b)
2175 {
2176         float t, c0, c1, c2, c3;
2177         int a;
2178
2179         c0 = f[0];
2180         c1 = 3.0f * (f[3] - f[0]);
2181         c2 = 3.0f * (f[0] - 2.0f * f[3] + f[6]);
2182         c3 = f[9] - f[0] + 3.0f * (f[3] - f[6]);
2183
2184         for (a = 0; a < b; a++) {
2185                 t = o[a];
2186                 o[a] = c0 + t * c1 + t * t * c2 + t * t * t * c3;
2187         }
2188 }
2189 #endif
2190
2191
2192 /* -------------------------- */
2193
2194 /* Calculate F-Curve value for 'evaltime' using BezTriple keyframes */
2195 static float fcurve_eval_keyframes(FCurve *fcu, BezTriple *bezts, float evaltime)
2196 {
2197         const float eps = 1.e-8f;
2198         BezTriple *bezt, *prevbezt, *lastbezt;
2199         float v1[2], v2[2], v3[2], v4[2], opl[32], dx, fac;
2200         unsigned int a;
2201         int b;
2202         float cvalue = 0.0f;
2203         
2204         /* get pointers */
2205         a = fcu->totvert - 1;
2206         prevbezt = bezts;
2207         bezt = prevbezt + 1;
2208         lastbezt = prevbezt + a;
2209         
2210         /* evaluation time at or past endpoints? */
2211         if (prevbezt->vec[1][0] >= evaltime) {
2212                 /* before or on first keyframe */
2213                 if ( (fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (prevbezt->ipo != BEZT_IPO_CONST) &&
2214                      !(fcu->flag & FCURVE_DISCRETE_VALUES) )
2215                 {
2216                         /* linear or bezier interpolation */
2217                         if (prevbezt->ipo == BEZT_IPO_LIN) {
2218                                 /* Use the next center point instead of our own handle for
2219                                  * linear interpolated extrapolate 
2220                                  */
2221                                 if (fcu->totvert == 1) {
2222                                         cvalue = prevbezt->vec[1][1];
2223                                 }
2224                                 else {
2225                                         bezt = prevbezt + 1;
2226                                         dx = prevbezt->vec[1][0] - evaltime;
2227                                         fac = bezt->vec[1][0] - prevbezt->vec[1][0];
2228                                         
2229                                         /* prevent division by zero */
2230                                         if (fac) {
2231                                                 fac = (bezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
2232                                                 cvalue = prevbezt->vec[1][1] - (fac * dx);
2233                                         }
2234                                         else {
2235                                                 cvalue = prevbezt->vec[1][1];
2236                                         }
2237                                 }
2238                         }
2239                         else {
2240                                 /* Use the first handle (earlier) of first BezTriple to calculate the
2241                                  * gradient and thus the value of the curve at evaltime
2242                                  */
2243                                 dx = prevbezt->vec[1][0] - evaltime;
2244                                 fac = prevbezt->vec[1][0] - prevbezt->vec[0][0];
2245                                 
2246                                 /* prevent division by zero */
2247                                 if (fac) {
2248                                         fac = (prevbezt->vec[1][1] - prevbezt->vec[0][1]) / fac;
2249                                         cvalue = prevbezt->vec[1][1] - (fac * dx);
2250                                 }
2251                                 else {
2252                                         cvalue = prevbezt->vec[1][1];
2253                                 }
2254                         }
2255                 }
2256                 else {
2257                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation, 
2258                          * so just extend first keyframe's value 
2259                          */
2260                         cvalue = prevbezt->vec[1][1];
2261                 }
2262         }
2263         else if (lastbezt->vec[1][0] <= evaltime) {
2264                 /* after or on last keyframe */
2265                 if ( (fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (lastbezt->ipo != BEZT_IPO_CONST) &&
2266                      !(fcu->flag & FCURVE_DISCRETE_VALUES) )
2267                 {
2268                         /* linear or bezier interpolation */
2269                         if (lastbezt->ipo == BEZT_IPO_LIN) {
2270                                 /* Use the next center point instead of our own handle for
2271                                  * linear interpolated extrapolate 
2272                                  */
2273                                 if (fcu->totvert == 1) {
2274                                         cvalue = lastbezt->vec[1][1];
2275                                 }
2276                                 else {
2277                                         prevbezt = lastbezt - 1;
2278                                         dx = evaltime - lastbezt->vec[1][0];
2279                                         fac = lastbezt->vec[1][0] - prevbezt->vec[1][0];
2280                                         
2281                                         /* prevent division by zero */
2282                                         if (fac) {
2283                                                 fac = (lastbezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
2284                                                 cvalue = lastbezt->vec[1][1] + (fac * dx);
2285                                         }
2286                                         else {
2287                                                 cvalue = lastbezt->vec[1][1];
2288                                         }
2289                                 }
2290                         }
2291                         else {
2292                                 /* Use the gradient of the second handle (later) of last BezTriple to calculate the
2293                                  * gradient and thus the value of the curve at evaltime
2294                                  */
2295                                 dx = evaltime - lastbezt->vec[1][0];
2296                                 fac = lastbezt->vec[2][0] - lastbezt->vec[1][0];
2297                                 
2298                                 /* prevent division by zero */
2299                                 if (fac) {
2300                                         fac = (lastbezt->vec[2][1] - lastbezt->vec[1][1]) / fac;
2301                                         cvalue = lastbezt->vec[1][1] + (fac * dx);
2302                                 }
2303                                 else {
2304                                         cvalue = lastbezt->vec[1][1];
2305                                 }
2306                         }
2307                 }
2308                 else {
2309                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation, 
2310                          * so just extend last keyframe's value 
2311                          */
2312                         cvalue = lastbezt->vec[1][1];
2313                 }
2314         }
2315         else {
2316                 /* evaltime occurs somewhere in the middle of the curve */
2317                 bool exact = false;
2318                 
2319                 /* Use binary search to find appropriate keyframes...
2320                  * 
2321                  * The threshold here has the following constraints:
2322                  *    - 0.001   is too coarse   -> We get artifacts with 2cm driver movements at 1BU = 1m (see T40332)
2323                  *    - 0.00001 is too fine     -> Weird errors, like selecting the wrong keyframe range (see T39207), occur.
2324                  *                                 This lower bound was established in b888a32eee8147b028464336ad2404d8155c64dd
2325                  */
2326                 a = binarysearch_bezt_index_ex(bezts, evaltime, fcu->totvert, 0.0001, &exact);
2327                 if (G.debug & G_DEBUG) printf("eval fcurve '%s' - %f => %u/%u, %d\n", fcu->rna_path, evaltime, a, fcu->totvert, exact);
2328                 
2329                 if (exact) {
2330                         /* index returned must be interpreted differently when it sits on top of an existing keyframe 
2331                          * - that keyframe is the start of the segment we need (see action_bug_2.blend in T39207)
2332                          */
2333                         prevbezt = bezts + a;
2334                         bezt = (a < fcu->totvert - 1) ? (prevbezt + 1) : prevbezt;
2335                 }
2336                 else {
2337                         /* index returned refers to the keyframe that the eval-time occurs *before*
2338                          * - hence, that keyframe marks the start of the segment we're dealing with
2339                          */
2340                         bezt = bezts + a;
2341                         prevbezt = (a > 0) ? (bezt - 1) : bezt;
2342                 }
2343                 
2344                 /* use if the key is directly on the frame, rare cases this is needed else we get 0.0 instead. */
2345                 /* XXX: consult T39207 for examples of files where failure of these checks can cause issues */
2346                 if (exact) {
2347                         cvalue = prevbezt->vec[1][1];
2348                 }
2349                 else if (fabsf(bezt->vec[1][0] - evaltime) < eps) {
2350                         cvalue = bezt->vec[1][1];
2351                 }
2352                 /* evaltime occurs within the interval defined by these two keyframes */
2353                 else if ((prevbezt->vec[1][0] <= evaltime) && (bezt->vec[1][0] >= evaltime)) {
2354                         const float begin = prevbezt->vec[1][1];
2355                         const float change = bezt->vec[1][1] - prevbezt->vec[1][1];
2356                         const float duration = bezt->vec[1][0] - prevbezt->vec[1][0];
2357                         const float time = evaltime - prevbezt->vec[1][0];
2358                         const float amplitude = prevbezt->amplitude;
2359                         const float period = prevbezt->period;
2360                         
2361                         /* value depends on interpolation mode */
2362                         if ((prevbezt->ipo == BEZT_IPO_CONST) || (fcu->flag & FCURVE_DISCRETE_VALUES) || (duration == 0)) {
2363                                 /* constant (evaltime not relevant, so no interpolation needed) */
2364                                 cvalue = prevbezt->vec[1][1];
2365                         }
2366                         else {
2367                                 switch (prevbezt->ipo) {
2368                                         /* interpolation ...................................... */
2369                                         case BEZT_IPO_BEZ:
2370                                                 /* bezier interpolation */
2371                                                 /* (v1, v2) are the first keyframe and its 2nd handle */
2372                                                 v1[0] = prevbezt->vec[1][0];
2373                                                 v1[1] = prevbezt->vec[1][1];
2374                                                 v2[0] = prevbezt->vec[2][0];
2375                                                 v2[1] = prevbezt->vec[2][1];
2376                                                 /* (v3, v4) are the last keyframe's 1st handle + the last keyframe */
2377                                                 v3[0] = bezt->vec[0][0];
2378                                                 v3[1] = bezt->vec[0][1];
2379                                                 v4[0] = bezt->vec[1][0];
2380                                                 v4[1] = bezt->vec[1][1];
2381                                                 
2382                                                 if (fabsf(v1[1] - v4[1]) < FLT_EPSILON &&
2383                                                     fabsf(v2[1] - v3[1]) < FLT_EPSILON &&
2384                                                     fabsf(v3[1] - v4[1]) < FLT_EPSILON)
2385                                                 {
2386                                                         /* Optimisation: If all the handles are flat/at the same values,
2387                                                          * the value is simply the shared value (see T40372 -> F91346)
2388                                                          */
2389                                                         cvalue = v1[1];
2390                                                 }
2391                                                 else {
2392                                                         /* adjust handles so that they don't overlap (forming a loop) */
2393                                                         correct_bezpart(v1, v2, v3, v4);
2394                                                         
2395                                                         /* try to get a value for this position - if failure, try another set of points */
2396                                                         b = findzero(evaltime, v1[0], v2[0], v3[0], v4[0], opl);
2397                                                         if (b) {
2398                                                                 berekeny(v1[1], v2[1], v3[1], v4[1], opl, 1);
2399                                                                 cvalue = opl[0];
2400                                                                 /* break; */
2401                                                         }
2402                                                         else {
2403                                                                 if (G.debug & G_DEBUG) printf("    ERROR: findzero() failed at %f with %f %f %f %f\n", evaltime, v1[0], v2[0], v3[0], v4[0]);
2404                                                         }
2405                                                 }
2406                                                 break;
2407                                                 
2408                                         case BEZT_IPO_LIN:
2409                                                 /* linear - simply linearly interpolate between values of the two keyframes */
2410                                                 cvalue = BLI_easing_linear_ease(time, begin, change, duration);
2411                                                 break;
2412                                                 
2413                                         /* easing ............................................ */
2414                                         case BEZT_IPO_BACK:
2415                                                 switch (prevbezt->easing) {
2416                                                         case BEZT_IPO_EASE_IN:
2417                                                                 cvalue = BLI_easing_back_ease_in(time, begin, change, duration, prevbezt->back);
2418                                                                 break;
2419                                                         case BEZT_IPO_EASE_OUT:
2420                                                                 cvalue = BLI_easing_back_ease_out(time, begin, change, duration, prevbezt->back);
2421                                                                 break;
2422                                                         case BEZT_IPO_EASE_IN_OUT:
2423                                                                 cvalue = BLI_easing_back_ease_in_out(time, begin, change, duration, prevbezt->back);
2424                                                                 break;
2425                                                                 
2426                                                         default: /* default/auto: same as ease out */
2427                                                                 cvalue = BLI_easing_back_ease_out(time, begin, change, duration, prevbezt->back);
2428                                                                 break;
2429                                                 }
2430                                                 break;
2431                                         
2432                                         case BEZT_IPO_BOUNCE:
2433                                                 switch (prevbezt->easing) {
2434                                                         case BEZT_IPO_EASE_IN:
2435                                                                 cvalue = BLI_easing_bounce_ease_in(time, begin, change, duration);
2436                                                                 break;
2437                                                         case BEZT_IPO_EASE_OUT:
2438                                                                 cvalue = BLI_easing_bounce_ease_out(time, begin, change, duration);
2439                                                                 break;
2440                                                         case BEZT_IPO_EASE_IN_OUT:
2441                                                                 cvalue = BLI_easing_bounce_ease_in_out(time, begin, change, duration);
2442                                                                 break;
2443                                                                 
2444                                                         default: /* default/auto: same as ease out */
2445                                                                 cvalue = BLI_easing_bounce_ease_out(time, begin, change, duration);
2446                                                                 break;
2447                                                 }
2448                                                 break;
2449                                         
2450                                         case BEZT_IPO_CIRC:
2451                                                 switch (prevbezt->easing) {
2452                                                         case BEZT_IPO_EASE_IN:
2453                                                                 cvalue = BLI_easing_circ_ease_in(time, begin, change, duration);
2454                                                                 break;
2455                                                         case BEZT_IPO_EASE_OUT:
2456                                                                 cvalue = BLI_easing_circ_ease_out(time, begin, change, duration);
2457                                                                 break;
2458                                                         case BEZT_IPO_EASE_IN_OUT:
2459                                                                 cvalue = BLI_easing_circ_ease_in_out(time, begin, change, duration);
2460                                                                 break;
2461                                                                 
2462                                                         default: /* default/auto: same as ease in */
2463                                                                 cvalue = BLI_easing_circ_ease_in(time, begin, change, duration);
2464                                                                 break;
2465                                                 }
2466                                                 break;
2467
2468                                         case BEZT_IPO_CUBIC:
2469                                                 switch (prevbezt->easing) {
2470                                                         case BEZT_IPO_EASE_IN:
2471                                                                 cvalue = BLI_easing_cubic_ease_in(time, begin, change, duration);
2472                                                                 break;
2473                                                         case BEZT_IPO_EASE_OUT:
2474                                                                 cvalue = BLI_easing_cubic_ease_out(time, begin, change, duration);
2475                                                                 break;
2476                                                         case BEZT_IPO_EASE_IN_OUT:
2477                                                                 cvalue = BLI_easing_cubic_ease_in_out(time, begin, change, duration);
2478                                                                 break;
2479                                                                 
2480                                                         default: /* default/auto: same as ease in */
2481                                                                 cvalue = BLI_easing_cubic_ease_in(time, begin, change, duration);
2482                                                                 break;
2483                                                 }
2484                                                 break;
2485                                         
2486                                         case BEZT_IPO_ELASTIC:
2487                                                 switch (prevbezt->easing) {
2488                                                         case BEZT_IPO_EASE_IN:
2489                                                                 cvalue = BLI_easing_elastic_ease_in(time, begin, change, duration, amplitude, period);
2490                                                                 break;
2491                                                         case BEZT_IPO_EASE_OUT:
2492                                                                 cvalue = BLI_easing_elastic_ease_out(time, begin, change, duration, amplitude, period);
2493                                                                 break;
2494                                                         case BEZT_IPO_EASE_IN_OUT:
2495                                                                 cvalue = BLI_easing_elastic_ease_in_out(time, begin, change, duration, amplitude, period);
2496                                                                 break;
2497                                                                 
2498                                                         default: /* default/auto: same as ease out */
2499                                                                 cvalue = BLI_easing_elastic_ease_out(time, begin, change, duration, amplitude, period);
2500                                                                 break;
2501                                                 }
2502                                                 break;
2503                                         
2504                                         case BEZT_IPO_EXPO:
2505                                                 switch (prevbezt->easing) {
2506                                                         case BEZT_IPO_EASE_IN:
2507                                                                 cvalue = BLI_easing_expo_ease_in(time, begin, change, duration);
2508                                                                 break;
2509                                                         case BEZT_IPO_EASE_OUT:
2510                                                                 cvalue = BLI_easing_expo_ease_out(time, begin, change, duration);
2511                                                                 break;
2512                                                         case BEZT_IPO_EASE_IN_OUT:
2513                                                                 cvalue = BLI_easing_expo_ease_in_out(time, begin, change, duration);
2514                                                                 break;
2515                                                                 
2516                                                         default: /* default/auto: same as ease in */
2517                                                                 cvalue = BLI_easing_expo_ease_in(time, begin, change, duration);
2518                                                                 break;
2519                                                 }
2520                                                 break;
2521                                         
2522                                         case BEZT_IPO_QUAD:
2523                                                 switch (prevbezt->easing) {
2524                                                         case BEZT_IPO_EASE_IN:
2525                                                                 cvalue = BLI_easing_quad_ease_in(time, begin, change, duration);
2526                                                                 break;
2527                                                         case BEZT_IPO_EASE_OUT:
2528                                                                 cvalue = BLI_easing_quad_ease_out(time, begin, change, duration);
2529                                                                 break;
2530                                                         case BEZT_IPO_EASE_IN_OUT:
2531                                                                 cvalue = BLI_easing_quad_ease_in_out(time, begin, change, duration);
2532                                                                 break;
2533                                                         
2534                                                         default: /* default/auto: same as ease in */
2535                                                                 cvalue = BLI_easing_quad_ease_in(time, begin, change, duration);
2536                                                                 break;
2537                                                 }
2538                                                 break;
2539                                         
2540                                         case BEZT_IPO_QUART:
2541                                                 switch (prevbezt->easing) {
2542                                                         case BEZT_IPO_EASE_IN:
2543                                                                 cvalue = BLI_easing_quart_ease_in(time, begin, change, duration);
2544                                                                 break;
2545                                                         case BEZT_IPO_EASE_OUT:
2546                                                                 cvalue = BLI_easing_quart_ease_out(time, begin, change, duration);
2547                                                                 break;
2548                                                         case BEZT_IPO_EASE_IN_OUT:
2549                                                                 cvalue = BLI_easing_quart_ease_in_out(time, begin, change, duration);
2550                                                                 break;
2551                                                                 
2552                                                         default: /* default/auto: same as ease in */
2553                                                                 cvalue = BLI_easing_quart_ease_in(time, begin, change, duration);
2554                                                                 break;
2555                                                 }
2556                                                 break;
2557                                         
2558                                         case BEZT_IPO_QUINT:
2559                                                 switch (prevbezt->easing) {
2560                                                         case BEZT_IPO_EASE_IN:
2561                                                                 cvalue = BLI_easing_quint_ease_in(time, begin, change, duration);
2562                                                                 break;
2563                                                         case BEZT_IPO_EASE_OUT:
2564                                                                 cvalue = BLI_easing_quint_ease_out(time, begin, change, duration);
2565                                                                 break;
2566                                                         case BEZT_IPO_EASE_IN_OUT:
2567                                                                 cvalue = BLI_easing_quint_ease_in_out(time, begin, change, duration);
2568                                                                 break;
2569                                                                 
2570                                                         default: /* default/auto: same as ease in */
2571                                                                 cvalue = BLI_easing_quint_ease_in(time, begin, change, duration);
2572                                                                 break;
2573                                                 }
2574                                                 break;
2575                                         
2576                                         case BEZT_IPO_SINE:
2577                                                 switch (prevbezt->easing) {
2578                                                         case BEZT_IPO_EASE_IN:
2579                                                                 cvalue = BLI_easing_sine_ease_in(time, begin, change, duration);
2580                                                                 break;
2581                                                         case BEZT_IPO_EASE_OUT:
2582                                                                 cvalue = BLI_easing_sine_ease_out(time, begin, change, duration);
2583                                                                 break;
2584                                                         case BEZT_IPO_EASE_IN_OUT:
2585                                                                 cvalue = BLI_easing_sine_ease_in_out(time, begin, change, duration);
2586                                                                 break;
2587                                                                 
2588                                                         default: /* default/auto: same as ease in */
2589                                                                 cvalue = BLI_easing_sine_ease_in(time, begin, change, duration);
2590                                                                 break;
2591                                                 }
2592                                                 break;
2593                                         
2594                                         
2595                                         default:
2596                                                 cvalue = prevbezt->vec[1][1];
2597                                                 break;
2598                                 }
2599                         }
2600                 }
2601                 else {
2602                         if (G.debug & G_DEBUG) printf("   ERROR: failed eval - p=%f b=%f, t=%f (%f)\n", prevbezt->vec[1][0], bezt->vec[1][0], evaltime, fabsf(bezt->vec[1][0] - evaltime));
2603                 }
2604         }
2605         
2606         /* return value */
2607         return cvalue;
2608 }
2609
2610 /* Calculate F-Curve value for 'evaltime' using FPoint samples */
2611 static float fcurve_eval_samples(FCurve *fcu, FPoint *fpts, float evaltime)
2612 {
2613         FPoint *prevfpt, *lastfpt, *fpt;
2614         float cvalue = 0.0f;
2615         
2616         /* get pointers */
2617         prevfpt = fpts;
2618         lastfpt = prevfpt + fcu->totvert - 1;
2619         
2620         /* evaluation time at or past endpoints? */
2621         if (prevfpt->vec[0] >= evaltime) {
2622                 /* before or on first sample, so just extend value */
2623                 cvalue = prevfpt->vec[1];
2624         }
2625         else if (lastfpt->vec[0] <= evaltime) {
2626                 /* after or on last sample, so just extend value */
2627                 cvalue = lastfpt->vec[1];
2628         }
2629         else {
2630                 float t = fabsf(evaltime - floorf(evaltime));
2631                 
2632                 /* find the one on the right frame (assume that these are spaced on 1-frame intervals) */
2633                 fpt = prevfpt + ((int)evaltime - (int)prevfpt->vec[0]);
2634                 
2635                 /* if not exactly on the frame, perform linear interpolation with the next one */
2636                 if ((t != 0.0f) && (t < 1.0f))
2637                         cvalue = interpf(fpt->vec[1], (fpt + 1)->vec[1], 1.0f - t);
2638                 else
2639                         cvalue = fpt->vec[1];
2640         }
2641         
2642         /* return value */
2643         return cvalue;
2644 }
2645
2646 /* ***************************** F-Curve - Evaluation ********************************* */
2647
2648 /* Evaluate and return the value of the given F-Curve at the specified frame ("evaltime") 
2649  * Note: this is also used for drivers
2650  */
2651 static float evaluate_fcurve_ex(FCurve *fcu, float evaltime, float cvalue)
2652 {
2653         FModifierStackStorage *storage;
2654         float devaltime;
2655
2656         /* evaluate modifiers which modify time to evaluate the base curve at */
2657         storage = evaluate_fmodifiers_storage_new(&fcu->modifiers);
2658         devaltime = evaluate_time_fmodifiers(storage, &fcu->modifiers, fcu, cvalue, evaltime);
2659         
2660         /* evaluate curve-data 
2661          *      - 'devaltime' instead of 'evaltime', as this is the time that the last time-modifying 
2662          *        F-Curve modifier on the stack requested the curve to be evaluated at
2663          */
2664         if (fcu->bezt)
2665                 cvalue = fcurve_eval_keyframes(fcu, fcu->bezt, devaltime);
2666         else if (fcu->fpt)
2667                 cvalue = fcurve_eval_samples(fcu, fcu->fpt, devaltime);
2668         
2669         /* evaluate modifiers */
2670         evaluate_value_fmodifiers(storage, &fcu->modifiers, fcu, &cvalue, devaltime);
2671
2672         evaluate_fmodifiers_storage_free(storage);
2673
2674         /* if curve can only have integral values, perform truncation (i.e. drop the decimal part)
2675          * here so that the curve can be sampled correctly
2676          */
2677         if (fcu->flag & FCURVE_INT_VALUES)
2678                 cvalue = floorf(cvalue + 0.5f);
2679         
2680         /* return evaluated value */
2681         return cvalue;
2682 }
2683
2684 float evaluate_fcurve(FCurve *fcu, float evaltime)
2685 {
2686         BLI_assert(fcu->driver == NULL);
2687
2688         return evaluate_fcurve_ex(fcu, evaltime, 0.0);
2689 }
2690
2691 float evaluate_fcurve_driver(PathResolvedRNA *anim_rna, FCurve *fcu, float evaltime)
2692 {
2693         BLI_assert(fcu->driver != NULL);
2694         float cvalue = 0.0f;
2695
2696         /* if there is a driver (only if this F-Curve is acting as 'driver'), evaluate it to find value to use as "evaltime"
2697          * since drivers essentially act as alternative input (i.e. in place of 'time') for F-Curves
2698          */
2699         if (fcu->driver) {
2700                 /* evaltime now serves as input for the curve */
2701                 evaltime = evaluate_driver(anim_rna, fcu->driver, evaltime);
2702
2703                 /* only do a default 1-1 mapping if it's unlikely that anything else will set a value... */
2704                 if (fcu->totvert == 0) {
2705                         FModifier *fcm;
2706                         bool do_linear = true;
2707
2708                         /* out-of-range F-Modifiers will block, as will those which just plain overwrite the values
2709                          * XXX: additive is a bit more dicey; it really depends then if things are in range or not...
2710                          */
2711                         for (fcm = fcu->modifiers.first; fcm; fcm = fcm->next) {
2712                                 /* if there are range-restrictions, we must definitely block [#36950] */
2713                                 if ((fcm->flag & FMODIFIER_FLAG_RANGERESTRICT) == 0 ||
2714                                     ((fcm->sfra <= evaltime) && (fcm->efra >= evaltime)) )
2715                                 {
2716                                         /* within range: here it probably doesn't matter, though we'd want to check on additive... */
2717                                 }
2718                                 else {
2719                                         /* outside range: modifier shouldn't contribute to the curve here, though it does in other areas,
2720                                          * so neither should the driver!
2721                                          */
2722                                         do_linear = false;
2723                                 }
2724                         }
2725
2726                         /* only copy over results if none of the modifiers disagreed with this */
2727                         if (do_linear) {
2728                                 cvalue = evaltime;
2729                         }
2730                 }
2731         }
2732
2733         return evaluate_fcurve_ex(fcu, evaltime, cvalue);
2734 }
2735
2736 /* Calculate the value of the given F-Curve at the given frame, and set its curval */
2737 float calculate_fcurve(PathResolvedRNA *anim_rna, FCurve *fcu, float evaltime)
2738 {
2739         /* only calculate + set curval (overriding the existing value) if curve has 
2740          * any data which warrants this...
2741          */
2742         if ((fcu->totvert) || (fcu->driver && !(fcu->driver->flag & DRIVER_FLAG_INVALID)) ||
2743             list_has_suitable_fmodifier(&fcu->modifiers, 0, FMI_TYPE_GENERATE_CURVE))
2744         {
2745                 /* calculate and set curval (evaluates driver too if necessary) */
2746                 float curval;
2747                 if (fcu->driver) {
2748                         curval = evaluate_fcurve_driver(anim_rna, fcu, evaltime);
2749                 }
2750                 else {
2751                         curval = evaluate_fcurve(fcu, evaltime);
2752                 }
2753                 fcu->curval = curval;  /* debug display only, not thread safe! */
2754                 return curval;
2755         }
2756         else {
2757                 return 0.0f;
2758         }
2759 }
2760