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