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