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