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