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