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