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