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