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