Cleanup: style, use braces for blenkernel
[blender.git] / source / blender / blenkernel / intern / fmodifier.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup bke
22  */
23
24 #include <math.h>
25 #include <stdio.h>
26 #include <stddef.h>
27 #include <string.h>
28 #include <float.h>
29
30 #include "MEM_guardedalloc.h"
31
32 #include "CLG_log.h"
33
34 #include "DNA_anim_types.h"
35
36 #include "BLT_translation.h"
37
38 #include "BLI_blenlib.h"
39 #include "BLI_ghash.h"
40 #include "BLI_noise.h"
41 #include "BLI_math.h" /* windows needs for M_PI */
42 #include "BLI_utildefines.h"
43
44 #include "BKE_fcurve.h"
45 #include "BKE_idprop.h"
46
47 static CLG_LogRef LOG = {"bke.fmodifier"};
48
49 /* ******************************** F-Modifiers ********************************* */
50
51 /* Info ------------------------------- */
52
53 /* F-Modifiers are modifiers which operate on F-Curves. However, they can also be defined
54  * on NLA-Strips to affect all of the F-Curves referenced by the NLA-Strip.
55  */
56
57 /* Template --------------------------- */
58
59 /* Each modifier defines a set of functions, which will be called at the appropriate
60  * times. In addition to this, each modifier should have a type-info struct, where
61  * its functions are attached for use.
62  */
63
64 /* Template for type-info data:
65  * - make a copy of this when creating new modifiers, and just change the functions
66  *   pointed to as necessary
67  * - although the naming of functions doesn't matter, it would help for code
68  *   readability, to follow the same naming convention as is presented here
69  * - any functions that a constraint doesn't need to define, don't define
70  *   for such cases, just use NULL
71  * - these should be defined after all the functions have been defined, so that
72  *   forward-definitions/prototypes don't need to be used!
73  * - keep this copy #if-def'd so that future modifier can get based off this
74  */
75 #if 0
76 static FModifierTypeInfo FMI_MODNAME = {
77     FMODIFIER_TYPE_MODNAME,        /* type */
78     sizeof(FMod_ModName),          /* size */
79     FMI_TYPE_SOME_ACTION,          /* action type */
80     FMI_REQUIRES_SOME_REQUIREMENT, /* requirements */
81     "Modifier Name",               /* name */
82     "FMod_ModName",                /* struct name */
83     0,                             /* storage size */
84     fcm_modname_free,              /* free data */
85     fcm_modname_relink,            /* relink data */
86     fcm_modname_copy,              /* copy data */
87     fcm_modname_new_data,          /* new data */
88     fcm_modname_verify,            /* verify */
89     fcm_modname_time,              /* evaluate time */
90     fcm_modname_evaluate,          /* evaluate */
91 };
92 #endif
93
94 /* Generator F-Curve Modifier --------------------------- */
95
96 /* Generators available:
97  *  1) simple polynomial generator:
98  *     - Expanded form - (y = C[0]*(x^(n)) + C[1]*(x^(n-1)) + ... + C[n])
99  *     - Factorized form - (y = (C[0][0]*x + C[0][1]) * (C[1][0]*x + C[1][1]) * ... * (C[n][0]*x + C[n][1]))
100  */
101
102 static void fcm_generator_free(FModifier *fcm)
103 {
104   FMod_Generator *data = (FMod_Generator *)fcm->data;
105
106   /* free polynomial coefficients array */
107   if (data->coefficients) {
108     MEM_freeN(data->coefficients);
109   }
110 }
111
112 static void fcm_generator_copy(FModifier *fcm, const FModifier *src)
113 {
114   FMod_Generator *gen = (FMod_Generator *)fcm->data;
115   FMod_Generator *ogen = (FMod_Generator *)src->data;
116
117   /* copy coefficients array? */
118   if (ogen->coefficients) {
119     gen->coefficients = MEM_dupallocN(ogen->coefficients);
120   }
121 }
122
123 static void fcm_generator_new_data(void *mdata)
124 {
125   FMod_Generator *data = (FMod_Generator *)mdata;
126   float *cp;
127
128   /* set default generator to be linear 0-1 (gradient = 1, y-offset = 0) */
129   data->poly_order = 1;
130   data->arraysize = 2;
131   cp = data->coefficients = MEM_callocN(sizeof(float) * 2, "FMod_Generator_Coefs");
132   cp[0] = 0;  // y-offset
133   cp[1] = 1;  // gradient
134 }
135
136 static void fcm_generator_verify(FModifier *fcm)
137 {
138   FMod_Generator *data = (FMod_Generator *)fcm->data;
139
140   /* requirements depend on mode */
141   switch (data->mode) {
142     case FCM_GENERATOR_POLYNOMIAL: /* expanded polynomial expression */
143     {
144       const int arraysize_new = data->poly_order + 1;
145       /* arraysize needs to be order+1, so resize if not */
146       if (data->arraysize != arraysize_new) {
147         data->coefficients = MEM_recallocN(data->coefficients, sizeof(float) * arraysize_new);
148         data->arraysize = arraysize_new;
149       }
150       break;
151     }
152     case FCM_GENERATOR_POLYNOMIAL_FACTORISED: /* expanded polynomial expression */
153     {
154       const int arraysize_new = data->poly_order * 2;
155       /* arraysize needs to be (2 * order), so resize if not */
156       if (data->arraysize != arraysize_new) {
157         data->coefficients = MEM_recallocN(data->coefficients, sizeof(float) * arraysize_new);
158         data->arraysize = arraysize_new;
159       }
160       break;
161     }
162   }
163 }
164
165 static void fcm_generator_evaluate(
166     FCurve *UNUSED(fcu), FModifier *fcm, float *cvalue, float evaltime, void *UNUSED(storage))
167 {
168   FMod_Generator *data = (FMod_Generator *)fcm->data;
169
170   /* behavior depends on mode
171    * NOTE: the data in its default state is fine too
172    */
173   switch (data->mode) {
174     case FCM_GENERATOR_POLYNOMIAL: /* expanded polynomial expression */
175     {
176       /* we overwrite cvalue with the sum of the polynomial */
177       float *powers = MEM_callocN(sizeof(float) * data->arraysize, "Poly Powers");
178       float value = 0.0f;
179       unsigned int i;
180
181       /* for each x^n, precalculate value based on previous one first... this should be
182        * faster that calling pow() for each entry
183        */
184       for (i = 0; i < data->arraysize; i++) {
185         /* first entry is x^0 = 1, otherwise, calculate based on previous */
186         if (i) {
187           powers[i] = powers[i - 1] * evaltime;
188         }
189         else {
190           powers[0] = 1;
191         }
192       }
193
194       /* for each coefficient, add to value, which we'll write to *cvalue in one go */
195       for (i = 0; i < data->arraysize; i++) {
196         value += data->coefficients[i] * powers[i];
197       }
198
199       /* only if something changed, write *cvalue in one go */
200       if (data->poly_order) {
201         if (data->flag & FCM_GENERATOR_ADDITIVE) {
202           *cvalue += value;
203         }
204         else {
205           *cvalue = value;
206         }
207       }
208
209       /* cleanup */
210       if (powers) {
211         MEM_freeN(powers);
212       }
213       break;
214     }
215     case FCM_GENERATOR_POLYNOMIAL_FACTORISED: /* Factorized polynomial */
216     {
217       float value = 1.0f, *cp = NULL;
218       unsigned int i;
219
220       /* for each coefficient pair, solve for that bracket before accumulating in value by multiplying */
221       for (cp = data->coefficients, i = 0; (cp) && (i < (unsigned int)data->poly_order);
222            cp += 2, i++) {
223         value *= (cp[0] * evaltime + cp[1]);
224       }
225
226       /* only if something changed, write *cvalue in one go */
227       if (data->poly_order) {
228         if (data->flag & FCM_GENERATOR_ADDITIVE) {
229           *cvalue += value;
230         }
231         else {
232           *cvalue = value;
233         }
234       }
235       break;
236     }
237   }
238 }
239
240 static FModifierTypeInfo FMI_GENERATOR = {
241     FMODIFIER_TYPE_GENERATOR, /* type */
242     sizeof(FMod_Generator),   /* size */
243     FMI_TYPE_GENERATE_CURVE,  /* action type */
244     FMI_REQUIRES_NOTHING,     /* requirements */
245     N_("Generator"),          /* name */
246     "FMod_Generator",         /* struct name */
247     0,                        /* storage size */
248     fcm_generator_free,       /* free data */
249     fcm_generator_copy,       /* copy data */
250     fcm_generator_new_data,   /* new data */
251     fcm_generator_verify,     /* verify */
252     NULL,                     /* evaluate time */
253     fcm_generator_evaluate,   /* evaluate */
254 };
255
256 /* Built-In Function Generator F-Curve Modifier --------------------------- */
257
258 /* This uses the general equation for equations:
259  *   y = amplitude * fn(phase_multiplier * x + phase_offset) + y_offset
260  *
261  * where amplitude, phase_multiplier/offset, y_offset are user-defined coefficients,
262  * x is the evaluation 'time', and 'y' is the resultant value
263  *
264  * Functions available are
265  * sin, cos, tan, sinc (normalized sin), natural log, square root
266  */
267
268 static void fcm_fn_generator_new_data(void *mdata)
269 {
270   FMod_FunctionGenerator *data = (FMod_FunctionGenerator *)mdata;
271
272   /* set amplitude and phase multiplier to 1.0f so that something is generated */
273   data->amplitude = 1.0f;
274   data->phase_multiplier = 1.0f;
275 }
276
277 /* Unary 'normalized sine' function
278  * y = sin(PI + x) / (PI * x),
279  * except for x = 0 when y = 1.
280  */
281 static double sinc(double x)
282 {
283   if (fabs(x) < 0.0001) {
284     return 1.0;
285   }
286   else {
287     return sin(M_PI * x) / (M_PI * x);
288   }
289 }
290
291 static void fcm_fn_generator_evaluate(
292     FCurve *UNUSED(fcu), FModifier *fcm, float *cvalue, float evaltime, void *UNUSED(storage))
293 {
294   FMod_FunctionGenerator *data = (FMod_FunctionGenerator *)fcm->data;
295   double arg = data->phase_multiplier * evaltime + data->phase_offset;
296   double (*fn)(double v) = NULL;
297
298   /* get function pointer to the func to use:
299    * WARNING: must perform special argument validation hereto guard against crashes
300    */
301   switch (data->type) {
302     /* simple ones */
303     case FCM_GENERATOR_FN_SIN: /* sine wave */
304       fn = sin;
305       break;
306     case FCM_GENERATOR_FN_COS: /* cosine wave */
307       fn = cos;
308       break;
309     case FCM_GENERATOR_FN_SINC: /* normalized sine wave */
310       fn = sinc;
311       break;
312
313     /* validation required */
314     case FCM_GENERATOR_FN_TAN: /* tangent wave */
315     {
316       /* check that argument is not on one of the discontinuities (i.e. 90deg, 270 deg, etc) */
317       if (IS_EQ(fmod((arg - M_PI_2), M_PI), 0.0)) {
318         if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0) {
319           *cvalue = 0.0f; /* no value possible here */
320         }
321       }
322       else {
323         fn = tan;
324       }
325       break;
326     }
327     case FCM_GENERATOR_FN_LN: /* natural log */
328     {
329       /* check that value is greater than 1? */
330       if (arg > 1.0) {
331         fn = log;
332       }
333       else {
334         if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0) {
335           *cvalue = 0.0f; /* no value possible here */
336         }
337       }
338       break;
339     }
340     case FCM_GENERATOR_FN_SQRT: /* square root */
341     {
342       /* no negative numbers */
343       if (arg > 0.0) {
344         fn = sqrt;
345       }
346       else {
347         if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0) {
348           *cvalue = 0.0f; /* no value possible here */
349         }
350       }
351       break;
352     }
353     default:
354       CLOG_ERROR(&LOG, "Invalid Function-Generator for F-Modifier - %d", data->type);
355       break;
356   }
357
358   /* execute function callback to set value if appropriate */
359   if (fn) {
360     float value = (float)(data->amplitude * (float)fn(arg) + data->value_offset);
361
362     if (data->flag & FCM_GENERATOR_ADDITIVE) {
363       *cvalue += value;
364     }
365     else {
366       *cvalue = value;
367     }
368   }
369 }
370
371 static FModifierTypeInfo FMI_FN_GENERATOR = {
372     FMODIFIER_TYPE_FN_GENERATOR,    /* type */
373     sizeof(FMod_FunctionGenerator), /* size */
374     FMI_TYPE_GENERATE_CURVE,        /* action type */
375     FMI_REQUIRES_NOTHING,           /* requirements */
376     N_("Built-In Function"),        /* name */
377     "FMod_FunctionGenerator",       /* struct name */
378     0,                              /* storage size */
379     NULL,                           /* free data */
380     NULL,                           /* copy data */
381     fcm_fn_generator_new_data,      /* new data */
382     NULL,                           /* verify */
383     NULL,                           /* evaluate time */
384     fcm_fn_generator_evaluate,      /* evaluate */
385 };
386
387 /* Envelope F-Curve Modifier --------------------------- */
388
389 static void fcm_envelope_free(FModifier *fcm)
390 {
391   FMod_Envelope *env = (FMod_Envelope *)fcm->data;
392
393   /* free envelope data array */
394   if (env->data) {
395     MEM_freeN(env->data);
396   }
397 }
398
399 static void fcm_envelope_copy(FModifier *fcm, const FModifier *src)
400 {
401   FMod_Envelope *env = (FMod_Envelope *)fcm->data;
402   FMod_Envelope *oenv = (FMod_Envelope *)src->data;
403
404   /* copy envelope data array */
405   if (oenv->data) {
406     env->data = MEM_dupallocN(oenv->data);
407   }
408 }
409
410 static void fcm_envelope_new_data(void *mdata)
411 {
412   FMod_Envelope *env = (FMod_Envelope *)mdata;
413
414   /* set default min/max ranges */
415   env->min = -1.0f;
416   env->max = 1.0f;
417 }
418
419 static void fcm_envelope_verify(FModifier *fcm)
420 {
421   FMod_Envelope *env = (FMod_Envelope *)fcm->data;
422
423   /* if the are points, perform bubble-sort on them, as user may have changed the order */
424   if (env->data) {
425     /* XXX todo... */
426   }
427 }
428
429 static void fcm_envelope_evaluate(
430     FCurve *UNUSED(fcu), FModifier *fcm, float *cvalue, float evaltime, void *UNUSED(storage))
431 {
432   FMod_Envelope *env = (FMod_Envelope *)fcm->data;
433   FCM_EnvelopeData *fed, *prevfed, *lastfed;
434   float min = 0.0f, max = 0.0f, fac = 0.0f;
435   int a;
436
437   /* get pointers */
438   if (env->data == NULL) {
439     return;
440   }
441   prevfed = env->data;
442   fed = prevfed + 1;
443   lastfed = prevfed + (env->totvert - 1);
444
445   /* get min/max values for envelope at evaluation time (relative to mid-value) */
446   if (prevfed->time >= evaltime) {
447     /* before or on first sample, so just extend value */
448     min = prevfed->min;
449     max = prevfed->max;
450   }
451   else if (lastfed->time <= evaltime) {
452     /* after or on last sample, so just extend value */
453     min = lastfed->min;
454     max = lastfed->max;
455   }
456   else {
457     /* evaltime occurs somewhere between segments */
458     /* TODO: implement binary search for this to make it faster? */
459     for (a = 0; prevfed && fed && (a < env->totvert - 1); a++, prevfed = fed, fed++) {
460       /* evaltime occurs within the interval defined by these two envelope points */
461       if ((prevfed->time <= evaltime) && (fed->time >= evaltime)) {
462         float afac, bfac, diff;
463
464         diff = fed->time - prevfed->time;
465         afac = (evaltime - prevfed->time) / diff;
466         bfac = (fed->time - evaltime) / diff;
467
468         min = bfac * prevfed->min + afac * fed->min;
469         max = bfac * prevfed->max + afac * fed->max;
470
471         break;
472       }
473     }
474   }
475
476   /* adjust *cvalue
477    * - fac is the ratio of how the current y-value corresponds to the reference range
478    * - thus, the new value is found by mapping the old range to the new!
479    */
480   fac = (*cvalue - (env->midval + env->min)) / (env->max - env->min);
481   *cvalue = min + fac * (max - min);
482 }
483
484 static FModifierTypeInfo FMI_ENVELOPE = {
485     FMODIFIER_TYPE_ENVELOPE, /* type */
486     sizeof(FMod_Envelope),   /* size */
487     FMI_TYPE_REPLACE_VALUES, /* action type */
488     0,                       /* requirements */
489     N_("Envelope"),          /* name */
490     "FMod_Envelope",         /* struct name */
491     0,                       /* storage size */
492     fcm_envelope_free,       /* free data */
493     fcm_envelope_copy,       /* copy data */
494     fcm_envelope_new_data,   /* new data */
495     fcm_envelope_verify,     /* verify */
496     NULL,                    /* evaluate time */
497     fcm_envelope_evaluate,   /* evaluate */
498 };
499
500 /* exported function for finding points */
501
502 /* Binary search algorithm for finding where to insert Envelope Data Point.
503  * Returns the index to insert at (data already at that index will be offset if replace is 0)
504  */
505 #define BINARYSEARCH_FRAMEEQ_THRESH 0.0001f
506
507 int BKE_fcm_envelope_find_index(FCM_EnvelopeData array[],
508                                 float frame,
509                                 int arraylen,
510                                 bool *r_exists)
511 {
512   int start = 0, end = arraylen;
513   int loopbreaker = 0, maxloop = arraylen * 2;
514
515   /* initialize exists-flag first */
516   *r_exists = false;
517
518   /* sneaky optimizations (don't go through searching process if...):
519    * - keyframe to be added is to be added out of current bounds
520    * - keyframe to be added would replace one of the existing ones on bounds
521    */
522   if ((arraylen <= 0) || (array == NULL)) {
523     CLOG_WARN(&LOG, "encountered invalid array");
524     return 0;
525   }
526   else {
527     /* check whether to add before/after/on */
528     float framenum;
529
530     /* 'First' Point (when only one point, this case is used) */
531     framenum = array[0].time;
532     if (IS_EQT(frame, framenum, BINARYSEARCH_FRAMEEQ_THRESH)) {
533       *r_exists = true;
534       return 0;
535     }
536     else if (frame < framenum) {
537       return 0;
538     }
539
540     /* 'Last' Point */
541     framenum = array[(arraylen - 1)].time;
542     if (IS_EQT(frame, framenum, BINARYSEARCH_FRAMEEQ_THRESH)) {
543       *r_exists = true;
544       return (arraylen - 1);
545     }
546     else if (frame > framenum) {
547       return arraylen;
548     }
549   }
550
551   /* most of the time, this loop is just to find where to put it
552    * - 'loopbreaker' is just here to prevent infinite loops
553    */
554   for (loopbreaker = 0; (start <= end) && (loopbreaker < maxloop); loopbreaker++) {
555     /* compute and get midpoint */
556     int mid = start + ((end - start) /
557                        2); /* we calculate the midpoint this way to avoid int overflows... */
558     float midfra = array[mid].time;
559
560     /* check if exactly equal to midpoint */
561     if (IS_EQT(frame, midfra, BINARYSEARCH_FRAMEEQ_THRESH)) {
562       *r_exists = true;
563       return mid;
564     }
565
566     /* repeat in upper/lower half */
567     if (frame > midfra) {
568       start = mid + 1;
569     }
570     else if (frame < midfra) {
571       end = mid - 1;
572     }
573   }
574
575   /* print error if loop-limit exceeded */
576   if (loopbreaker == (maxloop - 1)) {
577     CLOG_ERROR(&LOG, "binary search was taking too long");
578
579     // include debug info
580     CLOG_ERROR(&LOG,
581                "\tround = %d: start = %d, end = %d, arraylen = %d",
582                loopbreaker,
583                start,
584                end,
585                arraylen);
586   }
587
588   /* not found, so return where to place it */
589   return start;
590 }
591 #undef BINARYSEARCH_FRAMEEQ_THRESH
592
593 /* Cycles F-Curve Modifier  --------------------------- */
594
595 /* This modifier changes evaltime to something that exists within the curve's frame-range,
596  * then re-evaluates modifier stack up to this point using the new time. This re-entrant behavior
597  * is very likely to be more time-consuming than the original approach... (which was tightly integrated into
598  * the calculation code...).
599  *
600  * NOTE: this needs to be at the start of the stack to be of use, as it needs to know the extents of the
601  * keyframes/sample-data.
602  *
603  * Possible TODO - store length of cycle information that can be initialized from the extents of the
604  * keyframes/sample-data, and adjusted as appropriate.
605  */
606
607 /* temp data used during evaluation */
608 typedef struct tFCMED_Cycles {
609   float cycyofs; /* y-offset to apply */
610 } tFCMED_Cycles;
611
612 static void fcm_cycles_new_data(void *mdata)
613 {
614   FMod_Cycles *data = (FMod_Cycles *)mdata;
615
616   /* turn on cycles by default */
617   data->before_mode = data->after_mode = FCM_EXTRAPOLATE_CYCLIC;
618 }
619
620 static float fcm_cycles_time(
621     FCurve *fcu, FModifier *fcm, float UNUSED(cvalue), float evaltime, void *storage_)
622 {
623   FMod_Cycles *data = (FMod_Cycles *)fcm->data;
624   tFCMED_Cycles *storage = storage_;
625   float prevkey[2], lastkey[2], cycyofs = 0.0f;
626   short side = 0, mode = 0;
627   int cycles = 0;
628   float ofs = 0;
629
630   /* Initialize storage. */
631   storage->cycyofs = 0;
632
633   /* check if modifier is first in stack, otherwise disable ourself... */
634   /* FIXME... */
635   if (fcm->prev) {
636     fcm->flag |= FMODIFIER_FLAG_DISABLED;
637     return evaltime;
638   }
639
640   /* calculate new evaltime due to cyclic interpolation */
641   if (fcu && fcu->bezt) {
642     BezTriple *prevbezt = fcu->bezt;
643     BezTriple *lastbezt = prevbezt + fcu->totvert - 1;
644
645     prevkey[0] = prevbezt->vec[1][0];
646     prevkey[1] = prevbezt->vec[1][1];
647
648     lastkey[0] = lastbezt->vec[1][0];
649     lastkey[1] = lastbezt->vec[1][1];
650   }
651   else if (fcu && fcu->fpt) {
652     FPoint *prevfpt = fcu->fpt;
653     FPoint *lastfpt = prevfpt + fcu->totvert - 1;
654
655     prevkey[0] = prevfpt->vec[0];
656     prevkey[1] = prevfpt->vec[1];
657
658     lastkey[0] = lastfpt->vec[0];
659     lastkey[1] = lastfpt->vec[1];
660   }
661   else {
662     return evaltime;
663   }
664
665   /* check if modifier will do anything
666    * 1) if in data range, definitely don't do anything
667    * 2) if before first frame or after last frame, make sure some cycling is in use
668    */
669   if (evaltime < prevkey[0]) {
670     if (data->before_mode) {
671       side = -1;
672       mode = data->before_mode;
673       cycles = data->before_cycles;
674       ofs = prevkey[0];
675     }
676   }
677   else if (evaltime > lastkey[0]) {
678     if (data->after_mode) {
679       side = 1;
680       mode = data->after_mode;
681       cycles = data->after_cycles;
682       ofs = lastkey[0];
683     }
684   }
685   if ((ELEM(0, side, mode))) {
686     return evaltime;
687   }
688
689   /* find relative place within a cycle */
690   {
691     float cycdx = 0, cycdy = 0;
692     float cycle = 0, cyct = 0;
693
694     /* calculate period and amplitude (total height) of a cycle */
695     cycdx = lastkey[0] - prevkey[0];
696     cycdy = lastkey[1] - prevkey[1];
697
698     /* check if cycle is infinitely small, to be point of being impossible to use */
699     if (cycdx == 0) {
700       return evaltime;
701     }
702
703     /* calculate the 'number' of the cycle */
704     cycle = ((float)side * (evaltime - ofs) / cycdx);
705
706     /* calculate the time inside the cycle */
707     cyct = fmod(evaltime - ofs, cycdx);
708
709     /* check that cyclic is still enabled for the specified time */
710     if (cycles == 0) {
711       /* catch this case so that we don't exit when we have (cycles = 0)
712        * as this indicates infinite cycles...
713        */
714     }
715     else if (cycle > cycles) {
716       /* we are too far away from range to evaluate
717        * TODO: but we should still hold last value...
718        */
719       return evaltime;
720     }
721
722     /* check if 'cyclic extrapolation', and thus calculate y-offset for this cycle */
723     if (mode == FCM_EXTRAPOLATE_CYCLIC_OFFSET) {
724       if (side < 0) {
725         cycyofs = (float)floor((evaltime - ofs) / cycdx);
726       }
727       else {
728         cycyofs = (float)ceil((evaltime - ofs) / cycdx);
729       }
730       cycyofs *= cycdy;
731     }
732
733     /* special case for cycle start/end */
734     if (cyct == 0.0f) {
735       evaltime = (side == 1 ? lastkey[0] : prevkey[0]);
736
737       if ((mode == FCM_EXTRAPOLATE_MIRROR) && ((int)cycle % 2)) {
738         evaltime = (side == 1 ? prevkey[0] : lastkey[0]);
739       }
740     }
741     /* calculate where in the cycle we are (overwrite evaltime to reflect this) */
742     else if ((mode == FCM_EXTRAPOLATE_MIRROR) && ((int)(cycle + 1) % 2)) {
743       /* when 'mirror' option is used and cycle number is odd, this cycle is played in reverse
744        * - for 'before' extrapolation, we need to flip in a different way, otherwise values past
745        *   then end of the curve get referenced (result of fmod will be negative, and with different phase)
746        */
747       if (side < 0) {
748         evaltime = prevkey[0] - cyct;
749       }
750       else {
751         evaltime = lastkey[0] - cyct;
752       }
753     }
754     else {
755       /* the cycle is played normally... */
756       evaltime = prevkey[0] + cyct;
757     }
758     if (evaltime < prevkey[0]) {
759       evaltime += cycdx;
760     }
761   }
762
763   /* store temp data if needed */
764   if (mode == FCM_EXTRAPOLATE_CYCLIC_OFFSET) {
765     storage->cycyofs = cycyofs;
766   }
767
768   /* return the new frame to evaluate */
769   return evaltime;
770 }
771
772 static void fcm_cycles_evaluate(FCurve *UNUSED(fcu),
773                                 FModifier *UNUSED(fcm),
774                                 float *cvalue,
775                                 float UNUSED(evaltime),
776                                 void *storage_)
777 {
778   tFCMED_Cycles *storage = storage_;
779   *cvalue += storage->cycyofs;
780 }
781
782 static FModifierTypeInfo FMI_CYCLES = {
783     FMODIFIER_TYPE_CYCLES,      /* type */
784     sizeof(FMod_Cycles),        /* size */
785     FMI_TYPE_EXTRAPOLATION,     /* action type */
786     FMI_REQUIRES_ORIGINAL_DATA, /* requirements */
787     N_("Cycles"),               /* name */
788     "FMod_Cycles",              /* struct name */
789     sizeof(tFCMED_Cycles),      /* storage size */
790     NULL,                       /* free data */
791     NULL,                       /* copy data */
792     fcm_cycles_new_data,        /* new data */
793     NULL /*fcm_cycles_verify*/, /* verify */
794     fcm_cycles_time,            /* evaluate time */
795     fcm_cycles_evaluate,        /* evaluate */
796 };
797
798 /* Noise F-Curve Modifier  --------------------------- */
799
800 static void fcm_noise_new_data(void *mdata)
801 {
802   FMod_Noise *data = (FMod_Noise *)mdata;
803
804   /* defaults */
805   data->size = 1.0f;
806   data->strength = 1.0f;
807   data->phase = 1.0f;
808   data->offset = 0.0f;
809   data->depth = 0;
810   data->modification = FCM_NOISE_MODIF_REPLACE;
811 }
812
813 static void fcm_noise_evaluate(
814     FCurve *UNUSED(fcu), FModifier *fcm, float *cvalue, float evaltime, void *UNUSED(storage))
815 {
816   FMod_Noise *data = (FMod_Noise *)fcm->data;
817   float noise;
818
819   /* generate noise using good ol' Blender Noise
820    * - 0.1 is passed as the 'z' value, otherwise evaluation fails for size = phase = 1
821    *   with evaltime being an integer (which happens when evaluating on frame by frame basis)
822    */
823   noise = BLI_turbulence(data->size, evaltime - data->offset, data->phase, 0.1f, data->depth);
824
825   /* combine the noise with existing motion data */
826   switch (data->modification) {
827     case FCM_NOISE_MODIF_ADD:
828       *cvalue = *cvalue + noise * data->strength;
829       break;
830     case FCM_NOISE_MODIF_SUBTRACT:
831       *cvalue = *cvalue - noise * data->strength;
832       break;
833     case FCM_NOISE_MODIF_MULTIPLY:
834       *cvalue = *cvalue * noise * data->strength;
835       break;
836     case FCM_NOISE_MODIF_REPLACE:
837     default:
838       *cvalue = *cvalue + (noise - 0.5f) * data->strength;
839       break;
840   }
841 }
842
843 static FModifierTypeInfo FMI_NOISE = {
844     FMODIFIER_TYPE_NOISE,      /* type */
845     sizeof(FMod_Noise),        /* size */
846     FMI_TYPE_REPLACE_VALUES,   /* action type */
847     0,                         /* requirements */
848     N_("Noise"),               /* name */
849     "FMod_Noise",              /* struct name */
850     0,                         /* storage size */
851     NULL,                      /* free data */
852     NULL,                      /* copy data */
853     fcm_noise_new_data,        /* new data */
854     NULL /*fcm_noise_verify*/, /* verify */
855     NULL,                      /* evaluate time */
856     fcm_noise_evaluate,        /* evaluate */
857 };
858
859 /* Python F-Curve Modifier --------------------------- */
860
861 static void fcm_python_free(FModifier *fcm)
862 {
863   FMod_Python *data = (FMod_Python *)fcm->data;
864
865   /* id-properties */
866   IDP_FreeProperty(data->prop);
867   MEM_freeN(data->prop);
868 }
869
870 static void fcm_python_new_data(void *mdata)
871 {
872   FMod_Python *data = (FMod_Python *)mdata;
873
874   /* everything should be set correctly by calloc, except for the prop->type constant.*/
875   data->prop = MEM_callocN(sizeof(IDProperty), "PyFModifierProps");
876   data->prop->type = IDP_GROUP;
877 }
878
879 static void fcm_python_copy(FModifier *fcm, const FModifier *src)
880 {
881   FMod_Python *pymod = (FMod_Python *)fcm->data;
882   FMod_Python *opymod = (FMod_Python *)src->data;
883
884   pymod->prop = IDP_CopyProperty(opymod->prop);
885 }
886
887 static void fcm_python_evaluate(FCurve *UNUSED(fcu),
888                                 FModifier *UNUSED(fcm),
889                                 float *UNUSED(cvalue),
890                                 float UNUSED(evaltime),
891                                 void *UNUSED(storage))
892 {
893 #ifdef WITH_PYTHON
894   //FMod_Python *data = (FMod_Python *)fcm->data;
895
896   /* FIXME... need to implement this modifier...
897    * It will need it execute a script using the custom properties
898    */
899 #endif /* WITH_PYTHON */
900 }
901
902 static FModifierTypeInfo FMI_PYTHON = {
903     FMODIFIER_TYPE_PYTHON,      /* type */
904     sizeof(FMod_Python),        /* size */
905     FMI_TYPE_GENERATE_CURVE,    /* action type */
906     FMI_REQUIRES_RUNTIME_CHECK, /* requirements */
907     N_("Python"),               /* name */
908     "FMod_Python",              /* struct name */
909     0,                          /* storage size */
910     fcm_python_free,            /* free data */
911     fcm_python_copy,            /* copy data */
912     fcm_python_new_data,        /* new data */
913     NULL /*fcm_python_verify*/, /* verify */
914     NULL /*fcm_python_time*/,   /* evaluate time */
915     fcm_python_evaluate,        /* evaluate */
916 };
917
918 /* Limits F-Curve Modifier --------------------------- */
919
920 static float fcm_limits_time(FCurve *UNUSED(fcu),
921                              FModifier *fcm,
922                              float UNUSED(cvalue),
923                              float evaltime,
924                              void *UNUSED(storage))
925 {
926   FMod_Limits *data = (FMod_Limits *)fcm->data;
927
928   /* check for the time limits */
929   if ((data->flag & FCM_LIMIT_XMIN) && (evaltime < data->rect.xmin)) {
930     return data->rect.xmin;
931   }
932   if ((data->flag & FCM_LIMIT_XMAX) && (evaltime > data->rect.xmax)) {
933     return data->rect.xmax;
934   }
935
936   /* modifier doesn't change time */
937   return evaltime;
938 }
939
940 static void fcm_limits_evaluate(FCurve *UNUSED(fcu),
941                                 FModifier *fcm,
942                                 float *cvalue,
943                                 float UNUSED(evaltime),
944                                 void *UNUSED(storage))
945 {
946   FMod_Limits *data = (FMod_Limits *)fcm->data;
947
948   /* value limits now */
949   if ((data->flag & FCM_LIMIT_YMIN) && (*cvalue < data->rect.ymin)) {
950     *cvalue = data->rect.ymin;
951   }
952   if ((data->flag & FCM_LIMIT_YMAX) && (*cvalue > data->rect.ymax)) {
953     *cvalue = data->rect.ymax;
954   }
955 }
956
957 static FModifierTypeInfo FMI_LIMITS = {
958     FMODIFIER_TYPE_LIMITS, /* type */
959     sizeof(FMod_Limits),   /* size */
960     FMI_TYPE_GENERATE_CURVE,
961     /* action type */           /* XXX... err... */
962     FMI_REQUIRES_RUNTIME_CHECK, /* requirements */
963     N_("Limits"),               /* name */
964     "FMod_Limits",              /* struct name */
965     0,                          /* storage size */
966     NULL,                       /* free data */
967     NULL,                       /* copy data */
968     NULL,                       /* new data */
969     NULL,                       /* verify */
970     fcm_limits_time,            /* evaluate time */
971     fcm_limits_evaluate,        /* evaluate */
972 };
973
974 /* Stepped F-Curve Modifier --------------------------- */
975
976 static void fcm_stepped_new_data(void *mdata)
977 {
978   FMod_Stepped *data = (FMod_Stepped *)mdata;
979
980   /* just need to set the step-size to 2-frames by default */
981   /* XXX: or would 5 be more normal? */
982   data->step_size = 2.0f;
983 }
984
985 static float fcm_stepped_time(FCurve *UNUSED(fcu),
986                               FModifier *fcm,
987                               float UNUSED(cvalue),
988                               float evaltime,
989                               void *UNUSED(storage))
990 {
991   FMod_Stepped *data = (FMod_Stepped *)fcm->data;
992   int snapblock;
993
994   /* check range clamping to see if we should alter the timing to achieve the desired results */
995   if (data->flag & FCM_STEPPED_NO_BEFORE) {
996     if (evaltime < data->start_frame) {
997       return evaltime;
998     }
999   }
1000   if (data->flag & FCM_STEPPED_NO_AFTER) {
1001     if (evaltime > data->end_frame) {
1002       return evaltime;
1003     }
1004   }
1005
1006   /* we snap to the start of the previous closest block of 'step_size' frames
1007    * after the start offset has been discarded
1008    * - i.e. round down
1009    */
1010   snapblock = (int)((evaltime - data->offset) / data->step_size);
1011
1012   /* reapply the offset, and multiple the snapblock by the size of the steps to get
1013    * the new time to evaluate at
1014    */
1015   return ((float)snapblock * data->step_size) + data->offset;
1016 }
1017
1018 static FModifierTypeInfo FMI_STEPPED = {
1019     FMODIFIER_TYPE_STEPPED, /* type */
1020     sizeof(FMod_Limits),    /* size */
1021     FMI_TYPE_GENERATE_CURVE,
1022     /* action type */           /* XXX... err... */
1023     FMI_REQUIRES_RUNTIME_CHECK, /* requirements */
1024     N_("Stepped"),              /* name */
1025     "FMod_Stepped",             /* struct name */
1026     0,                          /* storage size */
1027     NULL,                       /* free data */
1028     NULL,                       /* copy data */
1029     fcm_stepped_new_data,       /* new data */
1030     NULL,                       /* verify */
1031     fcm_stepped_time,           /* evaluate time */
1032     NULL,                       /* evaluate */
1033 };
1034
1035 /* F-Curve Modifier API --------------------------- */
1036 /* All of the F-Curve Modifier api functions use FModifierTypeInfo structs to carry out
1037  * and operations that involve F-Curve modifier specific code.
1038  */
1039
1040 /* These globals only ever get directly accessed in this file */
1041 static FModifierTypeInfo *fmodifiersTypeInfo[FMODIFIER_NUM_TYPES];
1042 static short FMI_INIT = 1; /* when non-zero, the list needs to be updated */
1043
1044 /* This function only gets called when FMI_INIT is non-zero */
1045 static void fmods_init_typeinfo(void)
1046 {
1047   fmodifiersTypeInfo[0] = NULL;              /* 'Null' F-Curve Modifier */
1048   fmodifiersTypeInfo[1] = &FMI_GENERATOR;    /* Generator F-Curve Modifier */
1049   fmodifiersTypeInfo[2] = &FMI_FN_GENERATOR; /* Built-In Function Generator F-Curve Modifier */
1050   fmodifiersTypeInfo[3] = &FMI_ENVELOPE;     /* Envelope F-Curve Modifier */
1051   fmodifiersTypeInfo[4] = &FMI_CYCLES;       /* Cycles F-Curve Modifier */
1052   fmodifiersTypeInfo[5] = &FMI_NOISE;        /* Apply-Noise F-Curve Modifier */
1053   fmodifiersTypeInfo[6] = NULL /*&FMI_FILTER*/; /* Filter F-Curve Modifier */  // XXX unimplemented
1054   fmodifiersTypeInfo[7] = &FMI_PYTHON;  /* Custom Python F-Curve Modifier */
1055   fmodifiersTypeInfo[8] = &FMI_LIMITS;  /* Limits F-Curve Modifier */
1056   fmodifiersTypeInfo[9] = &FMI_STEPPED; /* Stepped F-Curve Modifier */
1057 }
1058
1059 /* This function should be used for getting the appropriate type-info when only
1060  * a F-Curve modifier type is known
1061  */
1062 const FModifierTypeInfo *get_fmodifier_typeinfo(const int type)
1063 {
1064   /* initialize the type-info list? */
1065   if (FMI_INIT) {
1066     fmods_init_typeinfo();
1067     FMI_INIT = 0;
1068   }
1069
1070   /* only return for valid types */
1071   if ((type >= FMODIFIER_TYPE_NULL) && (type < FMODIFIER_NUM_TYPES)) {
1072     /* there shouldn't be any segfaults here... */
1073     return fmodifiersTypeInfo[type];
1074   }
1075   else {
1076     CLOG_ERROR(&LOG, "No valid F-Curve Modifier type-info data available. Type = %i", type);
1077   }
1078
1079   return NULL;
1080 }
1081
1082 /* This function should always be used to get the appropriate type-info, as it
1083  * has checks which prevent segfaults in some weird cases.
1084  */
1085 const FModifierTypeInfo *fmodifier_get_typeinfo(const FModifier *fcm)
1086 {
1087   /* only return typeinfo for valid modifiers */
1088   if (fcm) {
1089     return get_fmodifier_typeinfo(fcm->type);
1090   }
1091   else {
1092     return NULL;
1093   }
1094 }
1095
1096 /* API --------------------------- */
1097
1098 /* Add a new F-Curve Modifier to the given F-Curve of a certain type */
1099 FModifier *add_fmodifier(ListBase *modifiers, int type, FCurve *owner_fcu)
1100 {
1101   const FModifierTypeInfo *fmi = get_fmodifier_typeinfo(type);
1102   FModifier *fcm;
1103
1104   /* sanity checks */
1105   if (ELEM(NULL, modifiers, fmi)) {
1106     return NULL;
1107   }
1108
1109   /* special checks for whether modifier can be added */
1110   if ((modifiers->first) && (type == FMODIFIER_TYPE_CYCLES)) {
1111     /* cycles modifier must be first in stack, so for now, don't add if it can't be */
1112     /* TODO: perhaps there is some better way, but for now, */
1113     CLOG_STR_ERROR(&LOG,
1114                    "Cannot add 'Cycles' modifier to F-Curve, as 'Cycles' modifier can only be "
1115                    "first in stack.");
1116     return NULL;
1117   }
1118
1119   /* add modifier itself */
1120   fcm = MEM_callocN(sizeof(FModifier), "F-Curve Modifier");
1121   fcm->type = type;
1122   fcm->flag = FMODIFIER_FLAG_EXPANDED;
1123   fcm->curve = owner_fcu;
1124   fcm->influence = 1.0f;
1125   BLI_addtail(modifiers, fcm);
1126
1127   /* tag modifier as "active" if no other modifiers exist in the stack yet */
1128   if (BLI_listbase_is_single(modifiers)) {
1129     fcm->flag |= FMODIFIER_FLAG_ACTIVE;
1130   }
1131
1132   /* add modifier's data */
1133   fcm->data = MEM_callocN(fmi->size, fmi->structName);
1134
1135   /* init custom settings if necessary */
1136   if (fmi->new_data) {
1137     fmi->new_data(fcm->data);
1138   }
1139
1140   /* update the fcurve if the Cycles modifier is added */
1141   if ((owner_fcu) && (type == FMODIFIER_TYPE_CYCLES)) {
1142     calchandles_fcurve(owner_fcu);
1143   }
1144
1145   /* return modifier for further editing */
1146   return fcm;
1147 }
1148
1149 /* Make a copy of the specified F-Modifier */
1150 FModifier *copy_fmodifier(const FModifier *src)
1151 {
1152   const FModifierTypeInfo *fmi = fmodifier_get_typeinfo(src);
1153   FModifier *dst;
1154
1155   /* sanity check */
1156   if (src == NULL) {
1157     return NULL;
1158   }
1159
1160   /* copy the base data, clearing the links */
1161   dst = MEM_dupallocN(src);
1162   dst->next = dst->prev = NULL;
1163   dst->curve = NULL;
1164
1165   /* make a new copy of the F-Modifier's data */
1166   dst->data = MEM_dupallocN(src->data);
1167
1168   /* only do specific constraints if required */
1169   if (fmi && fmi->copy_data) {
1170     fmi->copy_data(dst, src);
1171   }
1172
1173   /* return the new modifier */
1174   return dst;
1175 }
1176
1177 /* Duplicate all of the F-Modifiers in the Modifier stacks */
1178 void copy_fmodifiers(ListBase *dst, const ListBase *src)
1179 {
1180   FModifier *fcm, *srcfcm;
1181
1182   if (ELEM(NULL, dst, src)) {
1183     return;
1184   }
1185
1186   BLI_listbase_clear(dst);
1187   BLI_duplicatelist(dst, src);
1188
1189   for (fcm = dst->first, srcfcm = src->first; fcm && srcfcm;
1190        srcfcm = srcfcm->next, fcm = fcm->next) {
1191     const FModifierTypeInfo *fmi = fmodifier_get_typeinfo(fcm);
1192
1193     /* make a new copy of the F-Modifier's data */
1194     fcm->data = MEM_dupallocN(fcm->data);
1195     fcm->curve = NULL;
1196
1197     /* only do specific constraints if required */
1198     if (fmi && fmi->copy_data) {
1199       fmi->copy_data(fcm, srcfcm);
1200     }
1201   }
1202 }
1203
1204 /* Remove and free the given F-Modifier from the given stack  */
1205 bool remove_fmodifier(ListBase *modifiers, FModifier *fcm)
1206 {
1207   const FModifierTypeInfo *fmi = fmodifier_get_typeinfo(fcm);
1208
1209   /* sanity check */
1210   if (fcm == NULL) {
1211     return false;
1212   }
1213
1214   /* removing the cycles modifier requires a handle update */
1215   FCurve *update_fcu = (fcm->type == FMODIFIER_TYPE_CYCLES) ? fcm->curve : NULL;
1216
1217   /* free modifier's special data (stored inside fcm->data) */
1218   if (fcm->data) {
1219     if (fmi && fmi->free_data) {
1220       fmi->free_data(fcm);
1221     }
1222
1223     /* free modifier's data (fcm->data) */
1224     MEM_freeN(fcm->data);
1225   }
1226
1227   /* remove modifier from stack */
1228   if (modifiers) {
1229     BLI_freelinkN(modifiers, fcm);
1230
1231     /* update the fcurve if the Cycles modifier is removed */
1232     if (update_fcu) {
1233       calchandles_fcurve(update_fcu);
1234     }
1235
1236     return true;
1237   }
1238   else {
1239     /* XXX this case can probably be removed some day, as it shouldn't happen... */
1240     CLOG_STR_ERROR(&LOG, "no modifier stack given");
1241     MEM_freeN(fcm);
1242     return false;
1243   }
1244 }
1245
1246 /* Remove all of a given F-Curve's modifiers */
1247 void free_fmodifiers(ListBase *modifiers)
1248 {
1249   FModifier *fcm, *fmn;
1250
1251   /* sanity check */
1252   if (modifiers == NULL) {
1253     return;
1254   }
1255
1256   /* free each modifier in order - modifier is unlinked from list and freed */
1257   for (fcm = modifiers->first; fcm; fcm = fmn) {
1258     fmn = fcm->next;
1259     remove_fmodifier(modifiers, fcm);
1260   }
1261 }
1262
1263 /* Find the active F-Modifier */
1264 FModifier *find_active_fmodifier(ListBase *modifiers)
1265 {
1266   FModifier *fcm;
1267
1268   /* sanity checks */
1269   if (ELEM(NULL, modifiers, modifiers->first)) {
1270     return NULL;
1271   }
1272
1273   /* loop over modifiers until 'active' one is found */
1274   for (fcm = modifiers->first; fcm; fcm = fcm->next) {
1275     if (fcm->flag & FMODIFIER_FLAG_ACTIVE) {
1276       return fcm;
1277     }
1278   }
1279
1280   /* no modifier is active */
1281   return NULL;
1282 }
1283
1284 /* Set the active F-Modifier */
1285 void set_active_fmodifier(ListBase *modifiers, FModifier *fcm)
1286 {
1287   FModifier *fm;
1288
1289   /* sanity checks */
1290   if (ELEM(NULL, modifiers, modifiers->first)) {
1291     return;
1292   }
1293
1294   /* deactivate all, and set current one active */
1295   for (fm = modifiers->first; fm; fm = fm->next) {
1296     fm->flag &= ~FMODIFIER_FLAG_ACTIVE;
1297   }
1298
1299   /* make given modifier active */
1300   if (fcm) {
1301     fcm->flag |= FMODIFIER_FLAG_ACTIVE;
1302   }
1303 }
1304
1305 /* Do we have any modifiers which match certain criteria
1306  * - mtype - type of modifier (if 0, doesn't matter)
1307  * - acttype - type of action to perform (if -1, doesn't matter)
1308  */
1309 bool list_has_suitable_fmodifier(ListBase *modifiers, int mtype, short acttype)
1310 {
1311   FModifier *fcm;
1312
1313   /* if there are no specific filtering criteria, just skip */
1314   if ((mtype == 0) && (acttype == 0)) {
1315     return (modifiers && modifiers->first);
1316   }
1317
1318   /* sanity checks */
1319   if (ELEM(NULL, modifiers, modifiers->first)) {
1320     return false;
1321   }
1322
1323   /* find the first mdifier fitting these criteria */
1324   for (fcm = modifiers->first; fcm; fcm = fcm->next) {
1325     const FModifierTypeInfo *fmi = fmodifier_get_typeinfo(fcm);
1326     short mOk = 1, aOk = 1; /* by default 1, so that when only one test, won't fail */
1327
1328     /* check if applicable ones are fulfilled */
1329     if (mtype) {
1330       mOk = (fcm->type == mtype);
1331     }
1332     if (acttype > -1) {
1333       aOk = (fmi->acttype == acttype);
1334     }
1335
1336     /* if both are ok, we've found a hit */
1337     if (mOk && aOk) {
1338       return true;
1339     }
1340   }
1341
1342   /* no matches */
1343   return false;
1344 }
1345
1346 /* Evaluation API --------------------------- */
1347
1348 uint evaluate_fmodifiers_storage_size_per_modifier(ListBase *modifiers)
1349 {
1350   /* Sanity checks. */
1351   if (ELEM(NULL, modifiers, modifiers->first)) {
1352     return 0;
1353   }
1354
1355   uint max_size = 0;
1356
1357   for (FModifier *fcm = modifiers->first; fcm; fcm = fcm->next) {
1358     const FModifierTypeInfo *fmi = fmodifier_get_typeinfo(fcm);
1359
1360     if (fmi == NULL) {
1361       continue;
1362     }
1363
1364     max_size = MAX2(max_size, fmi->storage_size);
1365   }
1366
1367   return max_size;
1368 }
1369
1370 /* helper function - calculate influence of FModifier */
1371 static float eval_fmodifier_influence(FModifier *fcm, float evaltime)
1372 {
1373   float influence;
1374
1375   /* sanity check */
1376   if (fcm == NULL) {
1377     return 0.0f;
1378   }
1379
1380   /* should we use influence stored in modifier or not
1381    * NOTE: this is really just a hack so that we don't need to version patch old files ;)
1382    */
1383   if (fcm->flag & FMODIFIER_FLAG_USEINFLUENCE) {
1384     influence = fcm->influence;
1385   }
1386   else {
1387     influence = 1.0f;
1388   }
1389
1390   /* restricted range or full range? */
1391   if (fcm->flag & FMODIFIER_FLAG_RANGERESTRICT) {
1392     if ((evaltime <= fcm->sfra) || (evaltime >= fcm->efra)) {
1393       /* out of range */
1394       return 0.0f;
1395     }
1396     else if ((evaltime > fcm->sfra) && (evaltime < fcm->sfra + fcm->blendin)) {
1397       /* blend in range */
1398       float a = fcm->sfra;
1399       float b = fcm->sfra + fcm->blendin;
1400       return influence * (evaltime - a) / (b - a);
1401     }
1402     else if ((evaltime < fcm->efra) && (evaltime > fcm->efra - fcm->blendout)) {
1403       /* blend out range */
1404       float a = fcm->efra;
1405       float b = fcm->efra - fcm->blendout;
1406       return influence * (evaltime - a) / (b - a);
1407     }
1408   }
1409
1410   /* just return the influence of the modifier */
1411   return influence;
1412 }
1413
1414 /* evaluate time modifications imposed by some F-Curve Modifiers
1415  * - this step acts as an optimization to prevent the F-Curve stack being evaluated
1416  *   several times by modifiers requesting the time be modified, as the final result
1417  *   would have required using the modified time
1418  * - modifiers only ever receive the unmodified time, as subsequent modifiers should be
1419  *   working on the 'global' result of the modified curve, not some localised segment,
1420  *   so nevaltime gets set to whatever the last time-modifying modifier likes...
1421  * - we start from the end of the stack, as only the last one matters for now
1422  *
1423  * Note: *fcu might be NULL
1424  */
1425 float evaluate_time_fmodifiers(FModifiersStackStorage *storage,
1426                                ListBase *modifiers,
1427                                FCurve *fcu,
1428                                float cvalue,
1429                                float evaltime)
1430 {
1431   /* sanity checks */
1432   if (ELEM(NULL, modifiers, modifiers->last)) {
1433     return evaltime;
1434   }
1435
1436   if (fcu && fcu->flag & FCURVE_MOD_OFF) {
1437     return evaltime;
1438   }
1439
1440   /* Starting from the end of the stack, calculate the time effects of various stacked modifiers
1441    * on the time the F-Curve should be evaluated at.
1442    *
1443    * This is done in reverse order to standard evaluation, as when this is done in standard
1444    * order, each modifier would cause jumps to other points in the curve, forcing all
1445    * previous ones to be evaluated again for them to be correct. However, if we did in the
1446    * reverse order as we have here, we can consider them a macro to micro type of waterfall
1447    * effect, which should get us the desired effects when using layered time manipulations
1448    * (such as multiple 'stepped' modifiers in sequence, causing different stepping rates)
1449    */
1450   uint fcm_index = storage->modifier_count - 1;
1451   for (FModifier *fcm = modifiers->last; fcm; fcm = fcm->prev, fcm_index--) {
1452     const FModifierTypeInfo *fmi = fmodifier_get_typeinfo(fcm);
1453
1454     if (fmi == NULL) {
1455       continue;
1456     }
1457
1458     /* if modifier cannot be applied on this frame (whatever scale it is on, it won't affect the results)
1459      * hence we shouldn't bother seeing what it would do given the chance
1460      */
1461     if ((fcm->flag & FMODIFIER_FLAG_RANGERESTRICT) == 0 ||
1462         ((fcm->sfra <= evaltime) && (fcm->efra >= evaltime))) {
1463       /* only evaluate if there's a callback for this */
1464       if (fmi->evaluate_modifier_time) {
1465         if ((fcm->flag & (FMODIFIER_FLAG_DISABLED | FMODIFIER_FLAG_MUTED)) == 0) {
1466           void *storage_ptr = POINTER_OFFSET(storage->buffer,
1467                                              fcm_index * storage->size_per_modifier);
1468
1469           float nval = fmi->evaluate_modifier_time(fcu, fcm, cvalue, evaltime, storage_ptr);
1470
1471           float influence = eval_fmodifier_influence(fcm, evaltime);
1472           evaltime = interpf(nval, evaltime, influence);
1473         }
1474       }
1475     }
1476   }
1477
1478   /* return the modified evaltime */
1479   return evaltime;
1480 }
1481
1482 /* Evaluates the given set of F-Curve Modifiers using the given data
1483  * Should only be called after evaluate_time_fmodifiers() has been called...
1484  */
1485 void evaluate_value_fmodifiers(FModifiersStackStorage *storage,
1486                                ListBase *modifiers,
1487                                FCurve *fcu,
1488                                float *cvalue,
1489                                float evaltime)
1490 {
1491   FModifier *fcm;
1492
1493   /* sanity checks */
1494   if (ELEM(NULL, modifiers, modifiers->first)) {
1495     return;
1496   }
1497
1498   if (fcu->flag & FCURVE_MOD_OFF) {
1499     return;
1500   }
1501
1502   /* evaluate modifiers */
1503   uint fcm_index = 0;
1504   for (fcm = modifiers->first; fcm; fcm = fcm->next, fcm_index++) {
1505     const FModifierTypeInfo *fmi = fmodifier_get_typeinfo(fcm);
1506
1507     if (fmi == NULL) {
1508       continue;
1509     }
1510
1511     /* only evaluate if there's a callback for this, and if F-Modifier can be evaluated on this frame */
1512     if ((fcm->flag & FMODIFIER_FLAG_RANGERESTRICT) == 0 ||
1513         ((fcm->sfra <= evaltime) && (fcm->efra >= evaltime))) {
1514       if (fmi->evaluate_modifier) {
1515         if ((fcm->flag & (FMODIFIER_FLAG_DISABLED | FMODIFIER_FLAG_MUTED)) == 0) {
1516           void *storage_ptr = POINTER_OFFSET(storage->buffer,
1517                                              fcm_index * storage->size_per_modifier);
1518
1519           float nval = *cvalue;
1520           fmi->evaluate_modifier(fcu, fcm, &nval, evaltime, storage_ptr);
1521
1522           float influence = eval_fmodifier_influence(fcm, evaltime);
1523           *cvalue = interpf(nval, *cvalue, influence);
1524         }
1525       }
1526     }
1527   }
1528 }
1529
1530 /* ---------- */
1531
1532 /* Bake modifiers for given F-Curve to curve sample data, in the frame range defined
1533  * by start and end (inclusive).
1534  */
1535 void fcurve_bake_modifiers(FCurve *fcu, int start, int end)
1536 {
1537   ChannelDriver *driver;
1538
1539   /* sanity checks */
1540   /* TODO: make these tests report errors using reports not CLOG's */
1541   if (ELEM(NULL, fcu, fcu->modifiers.first)) {
1542     CLOG_ERROR(&LOG, "No F-Curve with F-Curve Modifiers to Bake");
1543     return;
1544   }
1545
1546   /* temporarily, disable driver while we sample, so that they don't influence the outcome */
1547   driver = fcu->driver;
1548   fcu->driver = NULL;
1549
1550   /* bake the modifiers, by sampling the curve at each frame */
1551   fcurve_store_samples(fcu, NULL, start, end, fcurve_samplingcb_evalcurve);
1552
1553   /* free the modifiers now */
1554   free_fmodifiers(&fcu->modifiers);
1555
1556   /* restore driver */
1557   fcu->driver = driver;
1558 }