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