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