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