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