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