FModifier Influence/BlendIn-Out
[blender.git] / source / blender / blenkernel / intern / fmodifier.c
1 /*
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
21  * All rights reserved.
22  *
23  * Contributor(s): Joshua Leung (full recode)
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/fmodifier.c
29  *  \ingroup bke
30  */
31
32
33
34 #include <math.h>
35 #include <stdio.h>
36 #include <stddef.h>
37 #include <string.h>
38 #include <float.h>
39
40 #include "MEM_guardedalloc.h"
41
42 #include "DNA_anim_types.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  *              - Factorised 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         /* behaviour 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: /* factorised 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         "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         "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         "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 behaviour
512  * is very likely to be more time-consuming than the original approach... (which was tighly 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 keyframes/sample-data
516  * Possible TODO - store length of cycle information that can be initialised from the extents of the keyframes/sample-data, and adjusted
517  *                              as appropriate
518  */
519
520 /* temp data used during evaluation */
521 typedef struct tFCMED_Cycles {
522         float cycyofs;          /* y-offset to apply */
523 } tFCMED_Cycles;
524  
525 static void fcm_cycles_new_data (void *mdata)
526 {
527         FMod_Cycles *data= (FMod_Cycles *)mdata;
528         
529         /* turn on cycles by default */
530         data->before_mode= data->after_mode= FCM_EXTRAPOLATE_CYCLIC;
531 }
532
533 static float fcm_cycles_time (FCurve *fcu, FModifier *fcm, float UNUSED(cvalue), float evaltime)
534 {
535         FMod_Cycles *data= (FMod_Cycles *)fcm->data;
536         float prevkey[2], lastkey[2], cycyofs=0.0f;
537         short side=0, mode=0;
538         int cycles=0, ofs=0;
539         
540         /* check if modifier is first in stack, otherwise disable ourself... */
541         // FIXME...
542         if (fcm->prev) {
543                 fcm->flag |= FMODIFIER_FLAG_DISABLED;
544                 return evaltime;
545         }
546         
547         /* calculate new evaltime due to cyclic interpolation */
548         if (fcu && fcu->bezt) {
549                 BezTriple *prevbezt= fcu->bezt;
550                 BezTriple *lastbezt= prevbezt + fcu->totvert-1;
551                 
552                 prevkey[0]= prevbezt->vec[1][0];
553                 prevkey[1]= prevbezt->vec[1][1];
554                 
555                 lastkey[0]= lastbezt->vec[1][0];
556                 lastkey[1]= lastbezt->vec[1][1];
557         }
558         else if (fcu && fcu->fpt) {
559                 FPoint *prevfpt= fcu->fpt;
560                 FPoint *lastfpt= prevfpt + fcu->totvert-1;
561                 
562                 prevkey[0]= prevfpt->vec[0];
563                 prevkey[1]= prevfpt->vec[1];
564                 
565                 lastkey[0]= lastfpt->vec[0];
566                 lastkey[1]= lastfpt->vec[1];
567         }
568         else
569                 return evaltime;
570                 
571         /* check if modifier will do anything
572          *      1) if in data range, definitely don't do anything
573          *      2) if before first frame or after last frame, make sure some cycling is in use
574          */
575         if (evaltime < prevkey[0]) {
576                 if (data->before_mode)  {
577                         side= -1;
578                         mode= data->before_mode;
579                         cycles= data->before_cycles;
580                         ofs= prevkey[0];
581                 }
582         }
583         else if (evaltime > lastkey[0]) {
584                 if (data->after_mode) {
585                         side= 1;
586                         mode= data->after_mode;
587                         cycles= data->after_cycles;
588                         ofs= lastkey[0];
589                 }
590         }
591         if ELEM(0, side, mode)
592                 return evaltime;
593                 
594         /* find relative place within a cycle */
595         {
596                 float cycdx=0, cycdy=0;
597                 float cycle= 0, cyct=0;
598                 
599                 /* calculate period and amplitude (total height) of a cycle */
600                 cycdx= lastkey[0] - prevkey[0];
601                 cycdy= lastkey[1] - prevkey[1];
602                 
603                 /* check if cycle is infinitely small, to be point of being impossible to use */
604                 if (cycdx == 0)
605                         return evaltime;
606                         
607                 /* calculate the 'number' of the cycle */
608                 cycle= ((float)side * (evaltime - ofs) / cycdx);
609
610                 /* calculate the time inside the cycle */
611                 cyct= fmod(evaltime - ofs, cycdx);
612                 
613                 /* check that cyclic is still enabled for the specified time */
614                 if (cycles == 0) {
615                         /* catch this case so that we don't exit when we have cycles=0
616                          * as this indicates infinite cycles...
617                          */
618                 }
619                 else if (cycle > cycles) {
620                         /* we are too far away from range to evaluate
621                          * TODO: but we should still hold last value... 
622                          */
623                         return evaltime;
624                 }
625                 
626                 /* check if 'cyclic extrapolation', and thus calculate y-offset for this cycle */
627                 if (mode == FCM_EXTRAPOLATE_CYCLIC_OFFSET) {
628                         if(side < 0)
629                                 cycyofs = (float)floor((evaltime - ofs) / cycdx);
630                         else
631                                 cycyofs = (float)ceil((evaltime - ofs) / cycdx);
632                         cycyofs *= cycdy;
633                 }
634
635                 /* special case for cycle start/end */
636                 if(cyct == 0.0f) {
637                         evaltime = (side == 1 ? lastkey[0] : prevkey[0]);
638
639                         if((mode == FCM_EXTRAPOLATE_MIRROR) && ((int)cycle % 2))
640                                 evaltime = (side == 1 ? prevkey[0] : lastkey[0]);
641                 }
642                 /* calculate where in the cycle we are (overwrite evaltime to reflect this) */
643                 else if ((mode == FCM_EXTRAPOLATE_MIRROR) && ((int)(cycle+1) % 2)) {
644                         /* when 'mirror' option is used and cycle number is odd, this cycle is played in reverse 
645                          *      - for 'before' extrapolation, we need to flip in a different way, otherwise values past
646                          *        then end of the curve get referenced (result of fmod will be negative, and with different phase)
647                          */
648                         if (side < 0)
649                                 evaltime= prevkey[0] - cyct;
650                         else
651                                 evaltime= lastkey[0] - cyct;
652                 }
653                 else {
654                         /* the cycle is played normally... */
655                         evaltime= prevkey[0] + cyct;
656                 }
657                 if (evaltime < prevkey[0]) evaltime += cycdx;
658         }
659         
660         /* store temp data if needed */
661         if (mode == FCM_EXTRAPOLATE_CYCLIC_OFFSET) {
662                 tFCMED_Cycles *edata;
663                 
664                 /* for now, this is just a float, but we could get more stuff... */
665                 fcm->edata= edata= MEM_callocN(sizeof(tFCMED_Cycles), "tFCMED_Cycles");
666                 edata->cycyofs= cycyofs;
667         }
668         
669         /* return the new frame to evaluate */
670         return evaltime;
671 }
672  
673 static void fcm_cycles_evaluate (FCurve *UNUSED(fcu), FModifier *fcm, float *cvalue, float UNUSED(evaltime))
674 {
675         tFCMED_Cycles *edata= (tFCMED_Cycles *)fcm->edata;
676         
677         /* use temp data */
678         if (edata) {
679                 /* add cyclic offset - no need to check for now, otherwise the data wouldn't exist! */
680                 *cvalue += edata->cycyofs;
681                 
682                 /* free temp data */
683                 MEM_freeN(edata);
684                 fcm->edata= NULL;
685         }
686 }
687
688 static FModifierTypeInfo FMI_CYCLES = {
689         FMODIFIER_TYPE_CYCLES, /* type */
690         sizeof(FMod_Cycles), /* size */
691         FMI_TYPE_EXTRAPOLATION, /* action type */
692         FMI_REQUIRES_ORIGINAL_DATA, /* requirements */
693         "Cycles", /* name */
694         "FMod_Cycles", /* struct name */
695         NULL, /* free data */
696         NULL, /* copy data */
697         fcm_cycles_new_data, /* new data */
698         NULL /*fcm_cycles_verify*/, /* verify */
699         fcm_cycles_time, /* evaluate time */
700         fcm_cycles_evaluate /* evaluate */
701 };
702
703 /* Noise F-Curve Modifier  --------------------------- */
704
705 static void fcm_noise_new_data (void *mdata)
706 {
707         FMod_Noise *data= (FMod_Noise *)mdata;
708         
709         /* defaults */
710         data->size= 1.0f;
711         data->strength= 1.0f;
712         data->phase= 1.0f;
713         data->depth = 0;
714         data->modification = FCM_NOISE_MODIF_REPLACE;
715 }
716  
717 static void fcm_noise_evaluate (FCurve *UNUSED(fcu), FModifier *fcm, float *cvalue, float evaltime)
718 {
719         FMod_Noise *data= (FMod_Noise *)fcm->data;
720         float noise;
721         
722         /* generate noise using good ol' Blender Noise
723          *      - 0.1 is passed as the 'z' value, otherwise evaluation fails for size = phase = 1
724          *        with evaltime being an integer (which happens when evaluating on frame by frame basis)
725          */
726         noise = BLI_turbulence(data->size, evaltime, data->phase, 0.1f, data->depth);
727         
728         /* combine the noise with existing motion data */
729         switch (data->modification) {
730                 case FCM_NOISE_MODIF_ADD:
731                         *cvalue= *cvalue + noise * data->strength;
732                         break;
733                 case FCM_NOISE_MODIF_SUBTRACT:
734                         *cvalue= *cvalue - noise * data->strength;
735                         break;
736                 case FCM_NOISE_MODIF_MULTIPLY:
737                         *cvalue= *cvalue * noise * data->strength;
738                         break;
739                 case FCM_NOISE_MODIF_REPLACE:
740                 default:
741                         *cvalue= *cvalue + (noise - 0.5f) * data->strength;
742                         break;
743         }
744 }
745
746 static FModifierTypeInfo FMI_NOISE = {
747         FMODIFIER_TYPE_NOISE, /* type */
748         sizeof(FMod_Noise), /* size */
749         FMI_TYPE_REPLACE_VALUES, /* action type */
750         0, /* requirements */
751         "Noise", /* name */
752         "FMod_Noise", /* struct name */
753         NULL, /* free data */
754         NULL, /* copy data */
755         fcm_noise_new_data, /* new data */
756         NULL /*fcm_noise_verify*/, /* verify */
757         NULL, /* evaluate time */
758         fcm_noise_evaluate /* evaluate */
759 };
760
761 /* Filter F-Curve Modifier --------------------------- */
762
763 #if 0 // XXX not yet implemented 
764 static FModifierTypeInfo FMI_FILTER = {
765         FMODIFIER_TYPE_FILTER, /* type */
766         sizeof(FMod_Filter), /* size */
767         FMI_TYPE_REPLACE_VALUES, /* action type */
768         0, /* requirements */
769         "Filter", /* name */
770         "FMod_Filter", /* struct name */
771         NULL, /* free data */
772         NULL, /* copy data */
773         NULL, /* new data */
774         NULL /*fcm_filter_verify*/, /* verify */
775         NULL, /* evlauate time */
776         fcm_filter_evaluate /* evaluate */
777 };
778 #endif // XXX not yet implemented
779
780
781 /* Python F-Curve Modifier --------------------------- */
782
783 static void fcm_python_free (FModifier *fcm)
784 {
785         FMod_Python *data= (FMod_Python *)fcm->data;
786         
787         /* id-properties */
788         IDP_FreeProperty(data->prop);
789         MEM_freeN(data->prop);
790 }
791
792 static void fcm_python_new_data (void *mdata) 
793 {
794         FMod_Python *data= (FMod_Python *)mdata;
795         
796         /* everything should be set correctly by calloc, except for the prop->type constant.*/
797         data->prop = MEM_callocN(sizeof(IDProperty), "PyFModifierProps");
798         data->prop->type = IDP_GROUP;
799 }
800
801 static void fcm_python_copy (FModifier *fcm, FModifier *src)
802 {
803         FMod_Python *pymod = (FMod_Python *)fcm->data;
804         FMod_Python *opymod = (FMod_Python *)src->data;
805         
806         pymod->prop = IDP_CopyProperty(opymod->prop);
807 }
808
809 static void fcm_python_evaluate (FCurve *UNUSED(fcu), FModifier *UNUSED(fcm), float *UNUSED(cvalue), float UNUSED(evaltime))
810 {
811 #ifdef WITH_PYTHON
812         //FMod_Python *data= (FMod_Python *)fcm->data;
813         
814         /* FIXME... need to implement this modifier...
815          *      It will need it execute a script using the custom properties 
816          */
817 #endif /* WITH_PYTHON */
818 }
819
820 static FModifierTypeInfo FMI_PYTHON = {
821         FMODIFIER_TYPE_PYTHON, /* type */
822         sizeof(FMod_Python), /* size */
823         FMI_TYPE_GENERATE_CURVE, /* action type */
824         FMI_REQUIRES_RUNTIME_CHECK, /* requirements */
825         "Python", /* name */
826         "FMod_Python", /* struct name */
827         fcm_python_free, /* free data */
828         fcm_python_copy, /* copy data */
829         fcm_python_new_data, /* new data */
830         NULL /*fcm_python_verify*/, /* verify */
831         NULL /*fcm_python_time*/, /* evaluate time */
832         fcm_python_evaluate /* evaluate */
833 };
834
835
836 /* Limits F-Curve Modifier --------------------------- */
837
838 static float fcm_limits_time (FCurve *UNUSED(fcu), FModifier *fcm, float UNUSED(cvalue), float evaltime)
839 {
840         FMod_Limits *data= (FMod_Limits *)fcm->data;
841         
842         /* check for the time limits */
843         if ((data->flag & FCM_LIMIT_XMIN) && (evaltime < data->rect.xmin))
844                 return data->rect.xmin;
845         if ((data->flag & FCM_LIMIT_XMAX) && (evaltime > data->rect.xmax))
846                 return data->rect.xmax;
847                 
848         /* modifier doesn't change time */
849         return evaltime;
850 }
851
852 static void fcm_limits_evaluate (FCurve *UNUSED(fcu), FModifier *fcm, float *cvalue, float UNUSED(evaltime))
853 {
854         FMod_Limits *data= (FMod_Limits *)fcm->data;
855         
856         /* value limits now */
857         if ((data->flag & FCM_LIMIT_YMIN) && (*cvalue < data->rect.ymin))
858                 *cvalue= data->rect.ymin;
859         if ((data->flag & FCM_LIMIT_YMAX) && (*cvalue > data->rect.ymax))
860                 *cvalue= data->rect.ymax;
861 }
862
863 static FModifierTypeInfo FMI_LIMITS = {
864         FMODIFIER_TYPE_LIMITS, /* type */
865         sizeof(FMod_Limits), /* size */
866         FMI_TYPE_GENERATE_CURVE, /* action type */  /* XXX... err... */   
867         FMI_REQUIRES_RUNTIME_CHECK, /* requirements */
868         "Limits", /* name */
869         "FMod_Limits", /* struct name */
870         NULL, /* free data */
871         NULL, /* copy data */
872         NULL, /* new data */
873         NULL, /* verify */
874         fcm_limits_time, /* evaluate time */
875         fcm_limits_evaluate /* evaluate */
876 };
877
878 /* Stepped F-Curve Modifier --------------------------- */
879
880 static void fcm_stepped_new_data (void *mdata) 
881 {
882         FMod_Stepped *data= (FMod_Stepped *)mdata;
883         
884         /* just need to set the step-size to 2-frames by default */
885         // XXX: or would 5 be more normal?
886         data->step_size = 2.0f;
887 }
888
889 static float fcm_stepped_time (FCurve *UNUSED(fcu), FModifier *fcm, float UNUSED(cvalue), float evaltime)
890 {
891         FMod_Stepped *data= (FMod_Stepped *)fcm->data;
892         int snapblock;
893         
894         /* check range clamping to see if we should alter the timing to achieve the desired results */
895         if (data->flag & FCM_STEPPED_NO_BEFORE) {
896                 if (evaltime < data->start_frame)
897                         return evaltime;
898         }
899         if (data->flag & FCM_STEPPED_NO_AFTER) {
900                 if (evaltime > data->end_frame)
901                         return evaltime;
902         }
903         
904         /* we snap to the start of the previous closest block of 'step_size' frames 
905          * after the start offset has been discarded 
906          *      - i.e. round down
907          */
908         snapblock = (int)((evaltime - data->offset) / data->step_size);
909         
910         /* reapply the offset, and multiple the snapblock by the size of the steps to get 
911          * the new time to evaluate at 
912          */
913         return ((float)snapblock * data->step_size) + data->offset;
914 }
915
916 static FModifierTypeInfo FMI_STEPPED = {
917         FMODIFIER_TYPE_STEPPED, /* type */
918         sizeof(FMod_Limits), /* size */
919         FMI_TYPE_GENERATE_CURVE, /* action type */  /* XXX... err... */   
920         FMI_REQUIRES_RUNTIME_CHECK, /* requirements */
921         "Stepped", /* name */
922         "FMod_Stepped", /* struct name */
923         NULL, /* free data */
924         NULL, /* copy data */
925         fcm_stepped_new_data, /* new data */
926         NULL, /* verify */
927         fcm_stepped_time, /* evaluate time */
928         NULL /* evaluate */
929 };
930
931 /* F-Curve Modifier API --------------------------- */
932 /* All of the F-Curve Modifier api functions use FModifierTypeInfo structs to carry out
933  * and operations that involve F-Curve modifier specific code.
934  */
935
936 /* These globals only ever get directly accessed in this file */
937 static FModifierTypeInfo *fmodifiersTypeInfo[FMODIFIER_NUM_TYPES];
938 static short FMI_INIT= 1; /* when non-zero, the list needs to be updated */
939
940 /* This function only gets called when FMI_INIT is non-zero */
941 static void fmods_init_typeinfo (void) 
942 {
943         fmodifiersTypeInfo[0]=  NULL;                                   /* 'Null' F-Curve Modifier */
944         fmodifiersTypeInfo[1]=  &FMI_GENERATOR;                 /* Generator F-Curve Modifier */
945         fmodifiersTypeInfo[2]=  &FMI_FN_GENERATOR;              /* Built-In Function Generator F-Curve Modifier */
946         fmodifiersTypeInfo[3]=  &FMI_ENVELOPE;                  /* Envelope F-Curve Modifier */
947         fmodifiersTypeInfo[4]=  &FMI_CYCLES;                    /* Cycles F-Curve Modifier */
948         fmodifiersTypeInfo[5]=  &FMI_NOISE;                             /* Apply-Noise F-Curve Modifier */
949         fmodifiersTypeInfo[6]=  NULL/*&FMI_FILTER*/;                    /* Filter F-Curve Modifier */  // XXX unimplemented
950         fmodifiersTypeInfo[7]=  &FMI_PYTHON;                    /* Custom Python F-Curve Modifier */
951         fmodifiersTypeInfo[8]=  &FMI_LIMITS;                    /* Limits F-Curve Modifier */
952         fmodifiersTypeInfo[9]=  &FMI_STEPPED;                   /* Stepped F-Curve Modifier */
953 }
954
955 /* This function should be used for getting the appropriate type-info when only
956  * a F-Curve modifier type is known
957  */
958 FModifierTypeInfo *get_fmodifier_typeinfo (int type)
959 {
960         /* initialise the type-info list? */
961         if (FMI_INIT) {
962                 fmods_init_typeinfo();
963                 FMI_INIT = 0;
964         }
965         
966         /* only return for valid types */
967         if ( (type >= FMODIFIER_TYPE_NULL) && 
968                  (type <= FMODIFIER_NUM_TYPES ) ) 
969         {
970                 /* there shouldn't be any segfaults here... */
971                 return fmodifiersTypeInfo[type];
972         }
973         else {
974                 printf("No valid F-Curve Modifier type-info data available. Type = %i \n", type);
975         }
976         
977         return NULL;
978
979  
980 /* This function should always be used to get the appropriate type-info, as it
981  * has checks which prevent segfaults in some weird cases.
982  */
983 FModifierTypeInfo *fmodifier_get_typeinfo (FModifier *fcm)
984 {
985         /* only return typeinfo for valid modifiers */
986         if (fcm)
987                 return get_fmodifier_typeinfo(fcm->type);
988         else
989                 return NULL;
990 }
991
992 /* API --------------------------- */
993
994 /* Add a new F-Curve Modifier to the given F-Curve of a certain type */
995 FModifier *add_fmodifier (ListBase *modifiers, int type)
996 {
997         FModifierTypeInfo *fmi= get_fmodifier_typeinfo(type);
998         FModifier *fcm;
999         
1000         /* sanity checks */
1001         if ELEM(NULL, modifiers, fmi)
1002                 return NULL;
1003         
1004         /* special checks for whether modifier can be added */
1005         if ((modifiers->first) && (type == FMODIFIER_TYPE_CYCLES)) {
1006                 /* cycles modifier must be first in stack, so for now, don't add if it can't be */
1007                 // TODO: perhaps there is some better way, but for now, 
1008                 printf("Error: Cannot add 'Cycles' modifier to F-Curve, as 'Cycles' modifier can only be first in stack. \n");
1009                 return NULL;
1010         }
1011         
1012         /* add modifier itself */
1013         fcm= MEM_callocN(sizeof(FModifier), "F-Curve Modifier");
1014         fcm->type = type;
1015         fcm->flag = FMODIFIER_FLAG_EXPANDED;
1016         fcm->influence = 1.0f;
1017         BLI_addtail(modifiers, fcm);
1018         
1019         /* tag modifier as "active" if no other modifiers exist in the stack yet */
1020         if (modifiers->first == modifiers->last)
1021                 fcm->flag |= FMODIFIER_FLAG_ACTIVE;
1022         
1023         /* add modifier's data */
1024         fcm->data= MEM_callocN(fmi->size, fmi->structName);
1025         
1026         /* init custom settings if necessary */
1027         if (fmi->new_data)      
1028                 fmi->new_data(fcm->data);
1029                 
1030         /* return modifier for further editing */
1031         return fcm;
1032 }
1033
1034 /* Make a copy of the specified F-Modifier */
1035 FModifier *copy_fmodifier (FModifier *src)
1036 {
1037         FModifierTypeInfo *fmi= fmodifier_get_typeinfo(src);
1038         FModifier *dst;
1039         
1040         /* sanity check */
1041         if (src == NULL)
1042                 return NULL;
1043                 
1044         /* copy the base data, clearing the links */
1045         dst = MEM_dupallocN(src);
1046         dst->next = dst->prev = NULL;
1047         
1048         /* make a new copy of the F-Modifier's data */
1049         dst->data = MEM_dupallocN(src->data);
1050         
1051         /* only do specific constraints if required */
1052         if (fmi && fmi->copy_data)
1053                 fmi->copy_data(dst, src);
1054                 
1055         /* return the new modifier */
1056         return dst;
1057 }
1058
1059 /* Duplicate all of the F-Modifiers in the Modifier stacks */
1060 void copy_fmodifiers (ListBase *dst, ListBase *src)
1061 {
1062         FModifier *fcm, *srcfcm;
1063         
1064         if ELEM(NULL, dst, src)
1065                 return;
1066         
1067         dst->first= dst->last= NULL;
1068         BLI_duplicatelist(dst, src);
1069         
1070         for (fcm=dst->first, srcfcm=src->first; fcm && srcfcm; srcfcm=srcfcm->next, fcm=fcm->next) {
1071                 FModifierTypeInfo *fmi= fmodifier_get_typeinfo(fcm);
1072                 
1073                 /* make a new copy of the F-Modifier's data */
1074                 fcm->data = MEM_dupallocN(fcm->data);
1075                 
1076                 /* only do specific constraints if required */
1077                 if (fmi && fmi->copy_data)
1078                         fmi->copy_data(fcm, srcfcm);
1079         }
1080 }
1081
1082 /* Remove and free the given F-Modifier from the given stack  */
1083 int remove_fmodifier (ListBase *modifiers, FModifier *fcm)
1084 {
1085         FModifierTypeInfo *fmi= fmodifier_get_typeinfo(fcm);
1086         
1087         /* sanity check */
1088         if (fcm == NULL)
1089                 return 0;
1090         
1091         /* free modifier's special data (stored inside fcm->data) */
1092         if (fcm->data) {
1093                 if (fmi && fmi->free_data)
1094                         fmi->free_data(fcm);
1095                         
1096                 /* free modifier's data (fcm->data) */
1097                 MEM_freeN(fcm->data);
1098         }
1099         
1100         /* remove modifier from stack */
1101         if (modifiers) {
1102                 BLI_freelinkN(modifiers, fcm);
1103                 return 1;
1104         } 
1105         else {
1106                 // XXX this case can probably be removed some day, as it shouldn't happen...
1107                 printf("remove_fmodifier() - no modifier stack given \n");
1108                 MEM_freeN(fcm);
1109                 return 0;
1110         }
1111 }
1112
1113 /* Remove all of a given F-Curve's modifiers */
1114 void free_fmodifiers (ListBase *modifiers)
1115 {
1116         FModifier *fcm, *fmn;
1117         
1118         /* sanity check */
1119         if (modifiers == NULL)
1120                 return;
1121         
1122         /* free each modifier in order - modifier is unlinked from list and freed */
1123         for (fcm= modifiers->first; fcm; fcm= fmn) {
1124                 fmn= fcm->next;
1125                 remove_fmodifier(modifiers, fcm);
1126         }
1127 }
1128
1129 /* Find the active F-Modifier */
1130 FModifier *find_active_fmodifier (ListBase *modifiers)
1131 {
1132         FModifier *fcm;
1133         
1134         /* sanity checks */
1135         if ELEM(NULL, modifiers, modifiers->first)
1136                 return NULL;
1137         
1138         /* loop over modifiers until 'active' one is found */
1139         for (fcm= modifiers->first; fcm; fcm= fcm->next) {
1140                 if (fcm->flag & FMODIFIER_FLAG_ACTIVE)
1141                         return fcm;
1142         }
1143         
1144         /* no modifier is active */
1145         return NULL;
1146 }
1147
1148 /* Set the active F-Modifier */
1149 void set_active_fmodifier (ListBase *modifiers, FModifier *fcm)
1150 {
1151         FModifier *fm;
1152         
1153         /* sanity checks */
1154         if ELEM(NULL, modifiers, modifiers->first)
1155                 return;
1156         
1157         /* deactivate all, and set current one active */
1158         for (fm= modifiers->first; fm; fm= fm->next)
1159                 fm->flag &= ~FMODIFIER_FLAG_ACTIVE;
1160         
1161         /* make given modifier active */
1162         if (fcm)
1163                 fcm->flag |= FMODIFIER_FLAG_ACTIVE;
1164 }
1165
1166 /* Do we have any modifiers which match certain criteria 
1167  *      - mtype - type of modifier (if 0, doesn't matter)
1168  *      - acttype - type of action to perform (if -1, doesn't matter)
1169  */
1170 short list_has_suitable_fmodifier (ListBase *modifiers, int mtype, short acttype)
1171 {
1172         FModifier *fcm;
1173         
1174         /* if there are no specific filtering criteria, just skip */
1175         if ((mtype == 0) && (acttype == 0))
1176                 return (modifiers && modifiers->first);
1177                 
1178         /* sanity checks */
1179         if ELEM(NULL, modifiers, modifiers->first)
1180                 return 0;
1181                 
1182         /* find the first mdifier fitting these criteria */
1183         for (fcm= modifiers->first; fcm; fcm= fcm->next) {
1184                 FModifierTypeInfo *fmi= fmodifier_get_typeinfo(fcm);
1185                 short mOk=1, aOk=1; /* by default 1, so that when only one test, won't fail */
1186                 
1187                 /* check if applicable ones are fullfilled */
1188                 if (mtype)
1189                         mOk= (fcm->type == mtype);
1190                 if (acttype > -1)
1191                         aOk= (fmi->acttype == acttype);
1192                         
1193                 /* if both are ok, we've found a hit */
1194                 if (mOk && aOk)
1195                         return 1;
1196         }
1197         
1198         /* no matches */
1199         return 0;
1200 }  
1201
1202 /* Evaluation API --------------------------- */
1203
1204 /* helper function - calculate influence of FModifier */
1205 static float eval_fmodifier_influence (FModifier *fcm, float evaltime)
1206 {
1207         float influence;
1208         
1209         /* sanity check */
1210         if (fcm == NULL) 
1211                 return 0.0f;
1212         
1213         /* should we use influence stored in modifier or not 
1214          * NOTE: this is really just a hack so that we don't need to version patch old files ;)
1215          */
1216         if (fcm->flag & FMODIFIER_FLAG_USEINFLUENCE)
1217                 influence = fcm->influence;
1218         else
1219                 influence = 1.0f;
1220                 
1221         /* restricted range or full range? */
1222         if (fcm->flag & FMODIFIER_FLAG_RANGERESTRICT) {
1223                 if ((evaltime <= fcm->sfra) || (evaltime >= fcm->efra)) {
1224                         /* out of range */
1225                         return 0.0f;
1226                 }
1227                 else if ((evaltime > fcm->sfra) && (evaltime < fcm->sfra + fcm->blendin)) {
1228                         /* blend in range */
1229                         float a = fcm->sfra;
1230                         float b = fcm->sfra + fcm->blendin;
1231                         return influence * (evaltime - a) / (b - a);
1232                 }
1233                 else if ((evaltime < fcm->efra) && (evaltime > fcm->efra - fcm->blendout)) {
1234                         /* blend out range */
1235                         float a = fcm->efra;
1236                         float b = fcm->efra - fcm->blendout;
1237                         return influence * (evaltime - a) / (b - a);
1238                 }
1239         }
1240         
1241         /* just return the influence of the modifier */
1242         return influence;
1243 }
1244
1245 /* evaluate time modifications imposed by some F-Curve Modifiers
1246  *      - this step acts as an optimisation to prevent the F-Curve stack being evaluated 
1247  *        several times by modifiers requesting the time be modified, as the final result
1248  *        would have required using the modified time
1249  *      - modifiers only ever receive the unmodified time, as subsequent modifiers should be
1250  *        working on the 'global' result of the modified curve, not some localised segment,
1251  *        so nevaltime gets set to whatever the last time-modifying modifier likes...
1252  *      - we start from the end of the stack, as only the last one matters for now
1253  */
1254 float evaluate_time_fmodifiers (ListBase *modifiers, FCurve *fcu, float cvalue, float evaltime)
1255 {
1256         FModifier *fcm;
1257         
1258         /* sanity checks */
1259         if ELEM(NULL, modifiers, modifiers->last)
1260                 return evaltime;
1261                 
1262         /* Starting from the end of the stack, calculate the time effects of various stacked modifiers 
1263          * on the time the F-Curve should be evaluated at. 
1264          *
1265          * This is done in reverse order to standard evaluation, as when this is done in standard
1266          * order, each modifier would cause jumps to other points in the curve, forcing all
1267          * previous ones to be evaluated again for them to be correct. However, if we did in the 
1268          * reverse order as we have here, we can consider them a macro to micro type of waterfall
1269          * effect, which should get us the desired effects when using layered time manipulations
1270          * (such as multiple 'stepped' modifiers in sequence, causing different stepping rates)
1271          */
1272         for (fcm= modifiers->last; fcm; fcm= fcm->prev) {
1273                 FModifierTypeInfo *fmi= fmodifier_get_typeinfo(fcm);
1274                 
1275                 if (fmi == NULL) 
1276                         continue;
1277                 
1278                 /* if modifier cannot be applied on this frame (whatever scale it is on, it won't affect the results)
1279                  * hence we shouldn't bother seeing what it would do given the chance
1280                  */
1281                 if ((fcm->flag & FMODIFIER_FLAG_RANGERESTRICT)==0 || 
1282                         ((fcm->sfra <= evaltime) && (fcm->efra >= evaltime)) )
1283                 {
1284                         /* only evaluate if there's a callback for this */
1285                         if (fmi->evaluate_modifier_time) {
1286                                 if ((fcm->flag & (FMODIFIER_FLAG_DISABLED|FMODIFIER_FLAG_MUTED)) == 0) {
1287                                         float influence = eval_fmodifier_influence(fcm, evaltime);
1288                                         float nval = fmi->evaluate_modifier_time(fcu, fcm, cvalue, evaltime);
1289                                         
1290                                         evaltime = interpf(nval, evaltime, influence);
1291                                 }
1292                         }
1293                 }
1294         }
1295         
1296         /* return the modified evaltime */
1297         return evaltime;
1298 }
1299
1300 /* Evalautes the given set of F-Curve Modifiers using the given data
1301  * Should only be called after evaluate_time_fmodifiers() has been called...
1302  */
1303 void evaluate_value_fmodifiers (ListBase *modifiers, FCurve *fcu, float *cvalue, float evaltime)
1304 {
1305         FModifier *fcm;
1306         
1307         /* sanity checks */
1308         if ELEM(NULL, modifiers, modifiers->first)
1309                 return;
1310         
1311         /* evaluate modifiers */
1312         for (fcm= modifiers->first; fcm; fcm= fcm->next) {
1313                 FModifierTypeInfo *fmi= fmodifier_get_typeinfo(fcm);
1314                 
1315                 if (fmi == NULL) 
1316                         continue;
1317                 
1318                 /* only evaluate if there's a callback for this, and if F-Modifier can be evaluated on this frame */
1319                 if ((fcm->flag & FMODIFIER_FLAG_RANGERESTRICT)==0 || 
1320                         ((fcm->sfra <= evaltime) && (fcm->efra >= evaltime)) )
1321                 {
1322                         if (fmi->evaluate_modifier) {
1323                                 if ((fcm->flag & (FMODIFIER_FLAG_DISABLED|FMODIFIER_FLAG_MUTED)) == 0) {
1324                                         float influence = eval_fmodifier_influence(fcm, evaltime);
1325                                         float nval = *cvalue;
1326                                         
1327                                         fmi->evaluate_modifier(fcu, fcm, &nval, evaltime);
1328                                         *cvalue = interpf(nval, *cvalue, influence);
1329                                 }
1330                         }
1331                 }
1332         }
1333
1334
1335 /* ---------- */
1336
1337 /* Bake modifiers for given F-Curve to curve sample data, in the frame range defined
1338  * by start and end (inclusive).
1339  */
1340 void fcurve_bake_modifiers (FCurve *fcu, int start, int end)
1341 {
1342         ChannelDriver *driver;
1343         
1344         /* sanity checks */
1345         // TODO: make these tests report errors using reports not printf's
1346         if ELEM(NULL, fcu, fcu->modifiers.first) {
1347                 printf("Error: No F-Curve with F-Curve Modifiers to Bake\n");
1348                 return;
1349         }
1350         
1351         /* temporarily, disable driver while we sample, so that they don't influence the outcome */
1352         driver= fcu->driver;
1353         fcu->driver= NULL;
1354         
1355         /* bake the modifiers, by sampling the curve at each frame */
1356         fcurve_store_samples(fcu, NULL, start, end, fcurve_samplingcb_evalcurve);
1357         
1358         /* free the modifiers now */
1359         free_fmodifiers(&fcu->modifiers);
1360         
1361         /* restore driver */
1362         fcu->driver= driver;
1363 }