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