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