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