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