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