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