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