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