merge with 2.5 at r18679
[blender.git] / source / blender / blenkernel / intern / fcurve.c
1 /* Testing code for new animation system in 2.5 
2  * Copyright 2009, Joshua Leung
3  */
4  
5
6 #include <math.h>
7 #include <stdio.h>
8 #include <string.h>
9
10 #ifdef HAVE_CONFIG_H
11 #include <config.h>
12 #endif
13
14 #include "MEM_guardedalloc.h"
15
16 #include "DNA_anim_types.h"
17
18 #include "BLI_blenlib.h"
19 #include "BLI_arithb.h"
20
21 #include "BKE_fcurve.h"
22 #include "BKE_curve.h" 
23 #include "BKE_idprop.h"
24 #include "BKE_utildefines.h"
25
26 #include "RNA_access.h"
27 #include "RNA_types.h"
28
29 #ifndef DISABLE_PYTHON
30 #include "BPY_extern.h" /* for BPY_pydriver_eval() */
31 #endif
32
33 #define SMALL -1.0e-10
34 #define SELECT 1
35
36 /* ************************** Data-Level Functions ************************* */
37
38 /* ---------------------- Freeing --------------------------- */
39
40 /* Frees the F-Curve itself too, so make sure BLI_remlink is called before calling this... */
41 void free_fcurve (FCurve *fcu) 
42 {
43         if (fcu == NULL) 
44                 return;
45         
46         /* free curve data */
47         if (fcu) {
48                 if (fcu->bezt) MEM_freeN(fcu->bezt);
49                 if (fcu->fpt) MEM_freeN(fcu->fpt);
50         }
51         
52         /* free RNA-path, as this were allocated when getting the path string */
53         if (fcu->rna_path)
54                 MEM_freeN(fcu->rna_path);
55         
56         /* free extra data - i.e. modifiers, and driver */
57         fcurve_free_driver(fcu);
58         fcurve_free_modifiers(fcu);
59         
60         /* free f-cruve itself */
61         MEM_freeN(fcu);
62 }
63
64 /* Frees a list of F-Curves */
65 void free_fcurves (ListBase *list)
66 {
67         FCurve *fcu, *fcn;
68         
69         /* sanity check */
70         if (list == NULL)
71                 return;
72                 
73         /* free data - no need to call remlink before freeing each curve, 
74          * as we store reference to next, and freeing only touches the curve
75          * it's given
76          */
77         for (fcu= list->first; fcu; fcu= fcn) {
78                 fcn= fcu->next;
79                 free_fcurve(fcu);
80         }
81         
82         /* clear pointers just in case */
83         list->first= list->last= NULL;
84 }       
85
86 /* ---------------------- Copy --------------------------- */
87
88 /* duplicate an F-Curve */
89 FCurve *copy_fcurve (FCurve *fcu)
90 {
91         FCurve *fcu_d;
92         
93         /* sanity check */
94         if (fcu == NULL)
95                 return NULL;
96                 
97         /* make a copy */
98         fcu_d= MEM_dupallocN(fcu);
99         fcu_d->next= fcu_d->prev= NULL;
100         
101         /* copy curve data */
102         fcu_d->bezt= MEM_dupallocN(fcu_d->bezt);
103         fcu_d->fpt= MEM_dupallocN(fcu_d->fpt);
104         
105         /* copy rna-path */
106         fcu_d->rna_path= MEM_dupallocN(fcu_d->rna_path);
107         
108         /* copy driver */
109         //fcurve_copy_driver();
110         
111         /* copy modifiers */
112         fcurve_copy_modifiers(&fcu_d->modifiers, &fcu->modifiers);
113         
114         /* return new data */
115         return fcu_d;
116 }
117
118 /* duplicate a list of F-Curves */
119 void copy_fcurves (ListBase *dst, ListBase *src)
120 {
121         FCurve *dfcu, *sfcu;
122         
123         /* sanity checks */
124         if ELEM(NULL, dst, src)
125                 return;
126         
127         /* clear destination list first */
128         dst->first= dst->last= NULL;
129         
130         /* copy one-by-one */
131         for (sfcu= src->first; sfcu; sfcu= sfcu->next) {
132                 dfcu= copy_fcurve(sfcu);
133                 BLI_addtail(dst, dfcu);
134         }
135 }
136
137 /* ---------------------- Relink --------------------------- */
138
139 #if 0
140 /* uses id->newid to match pointers with other copied data 
141  *      - called after single-user or other such
142  */
143                         if (icu->driver)
144                                 ID_NEW(icu->driver->ob);
145 #endif
146
147 /* --------------------- Finding -------------------------- */
148
149 /* Find the F-Curve affecting the given RNA-access path + index, in the list of F-Curves provided */
150 FCurve *list_find_fcurve (ListBase *list, const char rna_path[], const int array_index)
151 {
152         FCurve *fcu;
153         
154         /* sanity checks */
155         if ( ELEM(NULL, list, rna_path) || (array_index < 0) )
156                 return NULL;
157         
158         /* check paths of curves, then array indices... */
159         for (fcu= list->first; fcu; fcu= fcu->next) {
160                 /* simple string-compare (this assumes that they have the same root...) */
161                 if (strcmp(fcu->rna_path, rna_path) == 0) {
162                         /* now check indicies */
163                         if (fcu->array_index == array_index)
164                                 return fcu;
165                 }
166         }
167         
168         /* return */
169         return NULL;
170 }
171
172 /* Calculate the extents of F-Curve's keyframes */
173 void calc_fcurve_range (FCurve *fcu, float *start, float *end)
174 {
175         float min=999999999.0f, max=-999999999.0f;
176         short foundvert=0;
177
178         if (fcu->totvert) {
179                 if (fcu->bezt) {
180                         min= MIN2(min, fcu->bezt[0].vec[1][0]);
181                         max= MAX2(max, fcu->bezt[fcu->totvert-1].vec[1][0]);
182                 }
183                 else if (fcu->fpt) {
184                         min= MIN2(min, fcu->fpt[0].vec[0]);
185                         max= MAX2(max, fcu->fpt[fcu->totvert-1].vec[0]);
186                 }
187                 
188                 foundvert=1;
189         }
190         
191         /* minimum length is 1 frame */
192         if (foundvert) {
193                 if (min == max) max += 1.0f;
194                 *start= min;
195                 *end= max;
196         }
197         else {
198                 *start= 0.0f;
199                 *end= 1.0f;
200         }
201 }
202
203 /* ***************************** Keyframe Column Tools ********************************* */
204
205 /* add a BezTriple to a column */
206 void bezt_add_to_cfra_elem (ListBase *lb, BezTriple *bezt)
207 {
208         CfraElem *ce, *cen;
209         
210         for (ce= lb->first; ce; ce= ce->next) {
211                 /* double key? */
212                 if (ce->cfra == bezt->vec[1][0]) {
213                         if (bezt->f2 & SELECT) ce->sel= bezt->f2;
214                         return;
215                 }
216                 /* should key be inserted before this column? */
217                 else if (ce->cfra > bezt->vec[1][0]) break;
218         }
219         
220         /* create a new column */
221         cen= MEM_callocN(sizeof(CfraElem), "add_to_cfra_elem"); 
222         if (ce) BLI_insertlinkbefore(lb, ce, cen);
223         else BLI_addtail(lb, cen);
224
225         cen->cfra= bezt->vec[1][0];
226         cen->sel= bezt->f2;
227 }
228
229 /* ***************************** F-Curve Sanity ********************************* */
230 /* The functions here are used in various parts of Blender, usually after some editing
231  * of keyframe data has occurred. They ensure that keyframe data is properly ordered and
232  * that the handles are correctly 
233  */
234
235 /* This function recalculates the handles of an F-Curve 
236  * If the BezTriples have been rearranged, sort them first before using this.
237  */
238 void calchandles_fcurve (FCurve *fcu)
239 {
240         BezTriple *bezt, *prev, *next;
241         int a= fcu->totvert;
242
243         /* Error checking:
244          *      - need at least two points
245          *      - need bezier keys
246          *      - only bezier-interpolation has handles (for now)
247          */
248         if (ELEM(NULL, fcu, fcu->bezt) || (a < 2) /*|| ELEM(fcu->ipo, BEZT_IPO_CONST, BEZT_IPO_LIN)*/) 
249                 return;
250         
251         /* get initial pointers */
252         bezt= fcu->bezt;
253         prev= NULL;
254         next= (bezt + 1);
255         
256         /* loop over all beztriples, adjusting handles */
257         while (a--) {
258                 /* clamp timing of handles to be on either side of beztriple */
259                 if (bezt->vec[0][0] > bezt->vec[1][0]) bezt->vec[0][0]= bezt->vec[1][0];
260                 if (bezt->vec[2][0] < bezt->vec[1][0]) bezt->vec[2][0]= bezt->vec[1][0];
261                 
262                 /* calculate auto-handles */
263                 if (fcu->flag & FCURVE_AUTO_HANDLES) 
264                         calchandleNurb(bezt, prev, next, 2);    /* 2==special autohandle && keep extrema horizontal */
265                 else
266                         calchandleNurb(bezt, prev, next, 1);    /* 1==special autohandle */
267                 
268                 /* for automatic ease in and out */
269                 if ((bezt->h1==HD_AUTO) && (bezt->h2==HD_AUTO)) {
270                         /* only do this on first or last beztriple */
271                         if ((a == 0) || (a == fcu->totvert-1)) {
272                                 /* set both handles to have same horizontal value as keyframe */
273                                 if (fcu->extend == FCURVE_EXTRAPOLATE_CONSTANT) {
274                                         bezt->vec[0][1]= bezt->vec[2][1]= bezt->vec[1][1];
275                                 }
276                         }
277                 }
278                 
279                 /* advance pointers for next iteration */
280                 prev= bezt;
281                 if (a == 1) next= NULL;
282                 else next++;
283                 bezt++;
284         }
285 }
286
287 /* Use when F-Curve with handles has changed
288  * It treats all BezTriples with the following rules:
289  *  - PHASE 1: do types have to be altered?
290  *              -> Auto handles: become aligned when selection status is NOT(000 || 111)
291  *              -> Vector handles: become 'nothing' when (one half selected AND other not)
292  *  - PHASE 2: recalculate handles
293 */
294 void testhandles_fcurve (FCurve *fcu)
295 {
296         BezTriple *bezt;
297         int a;
298
299         /* only beztriples have handles (bpoints don't though) */
300         if ELEM(NULL, fcu, fcu->bezt)
301                 return;
302         
303         /* loop over beztriples */
304         for (a=0, bezt=fcu->bezt; a < fcu->totvert; a++, bezt++) {
305                 short flag= 0;
306                 
307                 /* flag is initialised as selection status
308                  * of beztriple control-points (labelled 0,1,2)
309                  */
310                 if (bezt->f1 & SELECT) flag |= (1<<0); // == 1
311                 if (bezt->f2 & SELECT) flag |= (1<<1); // == 2
312                 if (bezt->f3 & SELECT) flag |= (1<<2); // == 4
313                 
314                 /* one or two handles selected only */
315                 if (ELEM(flag, 0, 7)==0) {
316                         /* auto handles become aligned */
317                         if (bezt->h1==HD_AUTO)
318                                 bezt->h1= HD_ALIGN;
319                         if (bezt->h2==HD_AUTO)
320                                 bezt->h2= HD_ALIGN;
321                         
322                         /* vector handles become 'free' when only one half selected */
323                         if (bezt->h1==HD_VECT) {
324                                 /* only left half (1 or 2 or 1+2) */
325                                 if (flag < 4) 
326                                         bezt->h1= 0;
327                         }
328                         if (bezt->h2==HD_VECT) {
329                                 /* only right half (4 or 2+4) */
330                                 if (flag > 3) 
331                                         bezt->h2= 0;
332                         }
333                 }
334         }
335
336         /* recalculate handles */
337         calchandles_fcurve(fcu);
338 }
339
340 /* This function sorts BezTriples so that they are arranged in chronological order,
341  * as tools working on F-Curves expect that the BezTriples are in order.
342  */
343 void sort_time_fcurve (FCurve *fcu)
344 {
345         short ok= 1;
346         
347         /* keep adjusting order of beztriples until nothing moves (bubble-sort) */
348         while (ok) {
349                 ok= 0;
350                 
351                 /* currently, will only be needed when there are beztriples */
352                 if (fcu->bezt) {
353                         BezTriple *bezt;
354                         int a;
355                         
356                         /* loop over ALL points to adjust position in array and recalculate handles */
357                         for (a=0, bezt=fcu->bezt; a < fcu->totvert; a++, bezt++) {
358                                 /* check if thee's a next beztriple which we could try to swap with current */
359                                 if (a < (fcu->totvert-1)) {
360                                         /* swap if one is after the other (and indicate that order has changed) */
361                                         if (bezt->vec[1][0] > (bezt+1)->vec[1][0]) {
362                                                 SWAP(BezTriple, *bezt, *(bezt+1));
363                                                 ok= 1;
364                                         }
365                                         
366                                         /* if either one of both of the points exceeds crosses over the keyframe time... */
367                                         if ( (bezt->vec[0][0] > bezt->vec[1][0]) && (bezt->vec[2][0] < bezt->vec[1][0]) ) {
368                                                 /* swap handles if they have switched sides for some reason */
369                                                 SWAP(float, bezt->vec[0][0], bezt->vec[2][0]);
370                                                 SWAP(float, bezt->vec[0][1], bezt->vec[2][1]);
371                                         }
372                                         else {
373                                                 /* clamp handles */
374                                                 if (bezt->vec[0][0] > bezt->vec[1][0]) 
375                                                         bezt->vec[0][0]= bezt->vec[1][0];
376                                                 if (bezt->vec[2][0] < bezt->vec[1][0]) 
377                                                         bezt->vec[2][0]= bezt->vec[1][0];
378                                         }
379                                 }
380                         }
381                 }
382         }
383 }
384
385 /* This function tests if any BezTriples are out of order, thus requiring a sort */
386 short test_time_fcurve (FCurve *fcu)
387 {
388         int a;
389         
390         /* sanity checks */
391         if (fcu == NULL)
392                 return 0;
393         
394         /* currently, only need to test beztriples */
395         if (fcu->bezt) {
396                 BezTriple *bezt;
397                 
398                 /* loop through all BezTriples, stopping when one exceeds the one after it */
399                 for (a=0, bezt= fcu->bezt; a < (fcu->totvert - 1); a++, bezt++) {
400                         if (bezt->vec[1][0] > (bezt+1)->vec[1][0])
401                                 return 1;
402                 }
403         }
404         else if (fcu->fpt) {
405                 FPoint *fpt;
406                 
407                 /* loop through all FPoints, stopping when one exceeds the one after it */
408                 for (a=0, fpt= fcu->fpt; a < (fcu->totvert - 1); a++, fpt++) {
409                         if (fpt->vec[0] > (fpt+1)->vec[0])
410                                 return 1;
411                 }
412         }
413         
414         /* none need any swapping */
415         return 0;
416 }
417
418 /* ***************************** Drivers ********************************* */
419
420 /* Driver API --------------------------------- */
421
422 /* This frees the driver itself */
423 void fcurve_free_driver(FCurve *fcu)
424 {
425         ChannelDriver *driver;
426         
427         /* sanity checks */
428         if ELEM(NULL, fcu, fcu->driver)
429                 return;
430         driver= fcu->driver;
431         
432         /* free RNA-paths, as these were allocated when getting the path string */
433         if (driver->rna_path) MEM_freeN(driver->rna_path);
434         if (driver->rna_path2) MEM_freeN(driver->rna_path2);
435         
436         /* free driver itself, then set F-Curve's point to this to NULL (as the curve may still be used) */
437         MEM_freeN(driver);
438         fcu->driver= NULL;
439 }
440
441 /* Driver Evaluation -------------------------- */
442
443 /* Helper function to obtain a value using RNA from the specified source (for evaluating drivers) 
444  *      - target: used to specify which of the two driver-targets to use
445  */
446 static float driver_get_driver_value (ChannelDriver *driver, short target)
447 {
448         PointerRNA id_ptr, ptr;
449         PropertyRNA *prop;
450         char *path;
451         int index;
452         float value= 0.0f;
453         
454         /* get RNA-pointer for the ID-block given in driver */
455         if (target == 2) {
456                 /* second target */
457                 RNA_id_pointer_create(driver->id2, &id_ptr);
458                 path= driver->rna_path2;
459                 index= driver->array_index2;
460         }
461         else {
462                 /* first/main target */
463                 RNA_id_pointer_create(driver->id, &id_ptr);
464                 path= driver->rna_path;
465                 index= driver->array_index;
466         }
467         
468         /* get property to read from, and get value as appropriate */
469         if (RNA_path_resolve(&id_ptr, path, &ptr, &prop)) {
470                 switch (RNA_property_type(&ptr, prop)) {
471                         case PROP_BOOLEAN:
472                                 if (RNA_property_array_length(&ptr, prop))
473                                         value= (float)RNA_property_boolean_get_array(&ptr, prop, index);
474                                 else
475                                         value= (float)RNA_property_boolean_get(&ptr, prop);
476                                 break;
477                         case PROP_INT:
478                                 if (RNA_property_array_length(&ptr, prop))
479                                         value= (float)RNA_property_int_get_array(&ptr, prop, index);
480                                 else
481                                         value= (float)RNA_property_int_get(&ptr, prop);
482                                 break;
483                         case PROP_FLOAT:
484                                 if (RNA_property_array_length(&ptr, prop))
485                                         value= RNA_property_float_get_array(&ptr, prop, index);
486                                 else
487                                         value= RNA_property_float_get(&ptr, prop);
488                                 break;
489                         case PROP_ENUM:
490                                 value= (float)RNA_property_enum_get(&ptr, prop);
491                                 break;
492                         default:
493                                 break;
494                 }
495         }
496         
497         return value;
498 }
499
500 /* Evaluate an Channel-Driver to get a 'time' value to use instead of "evaltime"
501  *      - "evaltime" is the frame at which F-Curve is being evaluated
502  *      - has to return a float value 
503  */
504 static float evaluate_driver (ChannelDriver *driver, float evaltime)
505 {
506         /* check if driver can be evaluated */
507         if (driver->flag & DRIVER_FLAG_DISABLED)
508                 return 0.0f;
509         
510         switch (driver->type) {
511                 case DRIVER_TYPE_CHANNEL: /* channel/setting drivers channel/setting */
512                         return driver_get_driver_value(driver, 0);
513                         
514 #ifndef DISABLE_PYTHON
515                 case DRIVER_TYPE_PYTHON: /* expression */
516                 {
517                         /* check for empty or invalid expression */
518                         if ( (driver->expression[0] == '\0') ||
519                                  (driver->flag & DRIVER_FLAG_INVALID) )
520                         {
521                                 return 0.0f;
522                         }
523                         
524                         /* this evaluates the expression using Python,and returns its result:
525                          *      - on errors it reports, then returns 0.0f
526                          */
527                         //return BPY_pydriver_eval(driver); // XXX old func
528                         return 1.0f;
529                 }
530 #endif /* DISABLE_PYTHON*/
531                 
532                 case DRIVER_TYPE_ROTDIFF: /* difference of rotations of 2 bones (should be in same armature) */
533                 {
534                         /*
535                         float q1[4], q2[4], quat[4], angle;
536                         
537                         Mat4ToQuat(pchan->pose_mat, q1);
538                         Mat4ToQuat(pchan2->pose_mat, q2);
539                         
540                         QuatInv(q1);
541                         QuatMul(quat, q1, q2);
542                         angle = 2.0f * (saacos(quat[0]));
543                         angle= ABS(angle);
544                         
545                         return (angle > M_PI) ? (float)((2.0f * M_PI) - angle) : (float)(angle);
546                         */
547                 }
548                         break;
549                 
550                 default:
551                 {
552                         /* special 'hack' - just use stored value 
553                          *      This is currently used as the mechanism which allows animated settings to be able
554                          *      to be changed via the UI.
555                          */
556                         return driver->curval;
557                 }
558         }
559         
560         /* return 0.0f, as couldn't find relevant data to use */
561         return 0.0f;
562 }
563
564 /* ***************************** Curve Calculations ********************************* */
565
566 /* The total length of the handles is not allowed to be more
567  * than the horizontal distance between (v1-v4).
568  * This is to prevent curve loops.
569 */
570 void correct_bezpart (float *v1, float *v2, float *v3, float *v4)
571 {
572         float h1[2], h2[2], len1, len2, len, fac;
573         
574         /* calculate handle deltas */
575         h1[0]= v1[0] - v2[0];
576         h1[1]= v1[1] - v2[1];
577         
578         h2[0]= v4[0] - v3[0];
579         h2[1]= v4[1] - v3[1];
580         
581         /* calculate distances: 
582          *      - len   = span of time between keyframes 
583          *      - len1  = length of handle of start key
584          *      - len2  = length of handle of end key
585          */
586         len= v4[0]- v1[0];
587         len1= (float)fabs(h1[0]);
588         len2= (float)fabs(h2[0]);
589         
590         /* if the handles have no length, no need to do any corrections */
591         if ((len1+len2) == 0.0f) 
592                 return;
593                 
594         /* the two handles cross over each other, so force them
595          * apart using the proportion they overlap 
596          */
597         if ((len1+len2) > len) {
598                 fac= len / (len1+len2);
599                 
600                 v2[0]= (v1[0] - fac*h1[0]);
601                 v2[1]= (v1[1] - fac*h1[1]);
602                 
603                 v3[0]= (v4[0] - fac*h2[0]);
604                 v3[1]= (v4[1] - fac*h2[1]);
605         }
606 }
607
608 /* find root ('zero') */
609 int findzero (float x, float q0, float q1, float q2, float q3, float *o)
610 {
611         double c0, c1, c2, c3, a, b, c, p, q, d, t, phi;
612         int nr= 0;
613
614         c0= q0 - x;
615         c1= 3.0 * (q1 - q0);
616         c2= 3.0 * (q0 - 2.0*q1 + q2);
617         c3= q3 - q0 + 3.0 * (q1 - q2);
618         
619         if (c3 != 0.0) {
620                 a= c2/c3;
621                 b= c1/c3;
622                 c= c0/c3;
623                 a= a/3;
624                 
625                 p= b/3 - a*a;
626                 q= (2*a*a*a - a*b + c) / 2;
627                 d= q*q + p*p*p;
628                 
629                 if (d > 0.0) {
630                         t= sqrt(d);
631                         o[0]= (float)(Sqrt3d(-q+t) + Sqrt3d(-q-t) - a);
632                         
633                         if ((o[0] >= SMALL) && (o[0] <= 1.000001)) return 1;
634                         else return 0;
635                 }
636                 else if (d == 0.0) {
637                         t= Sqrt3d(-q);
638                         o[0]= (float)(2*t - a);
639                         
640                         if ((o[0] >= SMALL) && (o[0] <= 1.000001)) nr++;
641                         o[nr]= (float)(-t-a);
642                         
643                         if ((o[nr] >= SMALL) && (o[nr] <= 1.000001)) return nr+1;
644                         else return nr;
645                 }
646                 else {
647                         phi= acos(-q / sqrt(-(p*p*p)));
648                         t= sqrt(-p);
649                         p= cos(phi/3);
650                         q= sqrt(3 - 3*p*p);
651                         o[0]= (float)(2*t*p - a);
652                         
653                         if ((o[0] >= SMALL) && (o[0] <= 1.000001)) nr++;
654                         o[nr]= (float)(-t * (p + q) - a);
655                         
656                         if ((o[nr] >= SMALL) && (o[nr] <= 1.000001)) nr++;
657                         o[nr]= (float)(-t * (p - q) - a);
658                         
659                         if ((o[nr] >= SMALL) && (o[nr] <= 1.000001)) return nr+1;
660                         else return nr;
661                 }
662         }
663         else {
664                 a=c2;
665                 b=c1;
666                 c=c0;
667                 
668                 if (a != 0.0) {
669                         // discriminant
670                         p= b*b - 4*a*c;
671                         
672                         if (p > 0) {
673                                 p= sqrt(p);
674                                 o[0]= (float)((-b-p) / (2 * a));
675                                 
676                                 if ((o[0] >= SMALL) && (o[0] <= 1.000001)) nr++;
677                                 o[nr]= (float)((-b+p)/(2*a));
678                                 
679                                 if ((o[nr] >= SMALL) && (o[nr] <= 1.000001)) return nr+1;
680                                 else return nr;
681                         }
682                         else if (p == 0) {
683                                 o[0]= (float)(-b / (2 * a));
684                                 if ((o[0] >= SMALL) && (o[0] <= 1.000001)) return 1;
685                                 else return 0;
686                         }
687                 }
688                 else if (b != 0.0) {
689                         o[0]= (float)(-c/b);
690                         
691                         if ((o[0] >= SMALL) && (o[0] <= 1.000001)) return 1;
692                         else return 0;
693                 }
694                 else if (c == 0.0) {
695                         o[0]= 0.0;
696                         return 1;
697                 }
698                 
699                 return 0;       
700         }
701 }
702
703 void berekeny (float f1, float f2, float f3, float f4, float *o, int b)
704 {
705         float t, c0, c1, c2, c3;
706         int a;
707
708         c0= f1;
709         c1= 3.0f * (f2 - f1);
710         c2= 3.0f * (f1 - 2.0f*f2 + f3);
711         c3= f4 - f1 + 3.0f * (f2 - f3);
712         
713         for (a=0; a < b; a++) {
714                 t= o[a];
715                 o[a]= c0 + t*c1 + t*t*c2 + t*t*t*c3;
716         }
717 }
718
719 void berekenx (float *f, float *o, int b)
720 {
721         float t, c0, c1, c2, c3;
722         int a;
723
724         c0= f[0];
725         c1= 3.0f * (f[3] - f[0]);
726         c2= 3.0f * (f[0] - 2.0f*f[3] + f[6]);
727         c3= f[9] - f[0] + 3.0f * (f[3] - f[6]);
728         
729         for (a=0; a < b; a++) {
730                 t= o[a];
731                 o[a]= c0 + t*c1 + t*t*c2 + t*t*t*c3;
732         }
733 }
734
735
736 /* -------------------------- */
737
738 /* Calculate F-Curve value for 'evaltime' using BezTriple keyframes */
739 static float fcurve_eval_keyframes (FCurve *fcu, BezTriple *bezts, float evaltime)
740 {
741         BezTriple *bezt, *prevbezt, *lastbezt;
742         float v1[2], v2[2], v3[2], v4[2], opl[32], dx, fac;
743         int a, b;
744         float cvalue = 0.0f;
745         
746         /* get pointers */
747         a= fcu->totvert-1;
748         prevbezt= bezts;
749         bezt= prevbezt+1;
750         lastbezt= prevbezt + a;
751         
752         /* evaluation time at or past endpoints? */
753         if (prevbezt->vec[1][0] >= evaltime) {
754                 /* before or on first keyframe */
755                 if ((fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (prevbezt->ipo != BEZT_IPO_CONST)) {
756                         /* linear or bezier interpolation */
757                         if (prevbezt->ipo==BEZT_IPO_LIN) {
758                                 /* Use the next center point instead of our own handle for
759                                  * linear interpolated extrapolate 
760                                  */
761                                 if (fcu->totvert == 1) 
762                                         cvalue= prevbezt->vec[1][1];
763                                 else {
764                                         bezt = prevbezt+1;
765                                         dx= prevbezt->vec[1][0] - evaltime;
766                                         fac= bezt->vec[1][0] - prevbezt->vec[1][0];
767                                         
768                                         /* prevent division by zero */
769                                         if (fac) {
770                                                 fac= (bezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
771                                                 cvalue= prevbezt->vec[1][1] - (fac * dx);
772                                         }
773                                         else 
774                                                 cvalue= prevbezt->vec[1][1];
775                                 }
776                         } 
777                         else {
778                                 /* Use the first handle (earlier) of first BezTriple to calculate the
779                                  * gradient and thus the value of the curve at evaltime
780                                  */
781                                 dx= prevbezt->vec[1][0] - evaltime;
782                                 fac= prevbezt->vec[1][0] - prevbezt->vec[0][0];
783                                 
784                                 /* prevent division by zero */
785                                 if (fac) {
786                                         fac= (prevbezt->vec[1][1] - prevbezt->vec[0][1]) / fac;
787                                         cvalue= prevbezt->vec[1][1] - (fac * dx);
788                                 }
789                                 else 
790                                         cvalue= prevbezt->vec[1][1];
791                         }
792                 }
793                 else {
794                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation, 
795                          * so just extend first keyframe's value 
796                          */
797                         cvalue= prevbezt->vec[1][1];
798                 }
799         }
800         else if (lastbezt->vec[1][0] <= evaltime) {
801                 /* after or on last keyframe */
802                 if ((fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (lastbezt->ipo != BEZT_IPO_CONST)) {
803                         /* linear or bezier interpolation */
804                         if (lastbezt->ipo==BEZT_IPO_LIN) {
805                                 /* Use the next center point instead of our own handle for
806                                  * linear interpolated extrapolate 
807                                  */
808                                 if (fcu->totvert == 1) 
809                                         cvalue= lastbezt->vec[1][1];
810                                 else {
811                                         prevbezt = lastbezt - 1;
812                                         dx= evaltime - lastbezt->vec[1][0];
813                                         fac= lastbezt->vec[1][0] - prevbezt->vec[1][0];
814                                         
815                                         /* prevent division by zero */
816                                         if (fac) {
817                                                 fac= (lastbezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
818                                                 cvalue= lastbezt->vec[1][1] + (fac * dx);
819                                         }
820                                         else 
821                                                 cvalue= lastbezt->vec[1][1];
822                                 }
823                         } 
824                         else {
825                                 /* Use the gradient of the second handle (later) of last BezTriple to calculate the
826                                  * gradient and thus the value of the curve at evaltime
827                                  */
828                                 dx= evaltime - lastbezt->vec[1][0];
829                                 fac= lastbezt->vec[2][0] - lastbezt->vec[1][0];
830                                 
831                                 /* prevent division by zero */
832                                 if (fac) {
833                                         fac= (lastbezt->vec[2][1] - lastbezt->vec[1][1]) / fac;
834                                         cvalue= lastbezt->vec[1][1] + (fac * dx);
835                                 }
836                                 else 
837                                         cvalue= lastbezt->vec[1][1];
838                         }
839                 }
840                 else {
841                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation, 
842                          * so just extend last keyframe's value 
843                          */
844                         cvalue= lastbezt->vec[1][1];
845                 }
846         }
847         else {
848                 /* evaltime occurs somewhere in the middle of the curve */
849                 for (a=0; prevbezt && bezt && (a < fcu->totvert-1); a++, prevbezt=bezt, bezt++) {  
850                         /* evaltime occurs within the interval defined by these two keyframes */
851                         if ((prevbezt->vec[1][0] <= evaltime) && (bezt->vec[1][0] >= evaltime)) {
852                                 /* value depends on interpolation mode */
853                                 if (prevbezt->ipo == BEZT_IPO_CONST) {
854                                         /* constant (evaltime not relevant, so no interpolation needed) */
855                                         cvalue= prevbezt->vec[1][1];
856                                 }
857                                 else if (prevbezt->ipo == BEZT_IPO_LIN) {
858                                         /* linear - interpolate between values of the two keyframes */
859                                         fac= bezt->vec[1][0] - prevbezt->vec[1][0];
860                                         
861                                         /* prevent division by zero */
862                                         if (fac) {
863                                                 fac= (evaltime - prevbezt->vec[1][0]) / fac;
864                                                 cvalue= prevbezt->vec[1][1] + (fac * (bezt->vec[1][1] - prevbezt->vec[1][1]));
865                                         }
866                                         else
867                                                 cvalue= prevbezt->vec[1][1];
868                                 }
869                                 else {
870                                         /* bezier interpolation */
871                                                 /* v1,v2 are the first keyframe and its 2nd handle */
872                                         v1[0]= prevbezt->vec[1][0];
873                                         v1[1]= prevbezt->vec[1][1];
874                                         v2[0]= prevbezt->vec[2][0];
875                                         v2[1]= prevbezt->vec[2][1];
876                                                 /* v3,v4 are the last keyframe's 1st handle + the last keyframe */
877                                         v3[0]= bezt->vec[0][0];
878                                         v3[1]= bezt->vec[0][1];
879                                         v4[0]= bezt->vec[1][0];
880                                         v4[1]= bezt->vec[1][1];
881                                         
882                                         /* adjust handles so that they don't overlap (forming a loop) */
883                                         correct_bezpart(v1, v2, v3, v4);
884                                         
885                                         /* try to get a value for this position - if failure, try another set of points */
886                                         b= findzero(evaltime, v1[0], v2[0], v3[0], v4[0], opl);
887                                         if (b) {
888                                                 berekeny(v1[1], v2[1], v3[1], v4[1], opl, 1);
889                                                 cvalue= opl[0];
890                                                 break;
891                                         }
892                                 }
893                         }
894                 }
895         }
896         
897         /* return value */
898         return cvalue;
899 }
900
901 /* Calculate F-Curve value for 'evaltime' using FPoint samples */
902 static float fcurve_eval_samples (FCurve *fcu, FPoint *fpts, float evaltime)
903 {
904         FPoint *prevfpt, *lastfpt, *fpt;
905         float cvalue= 0.0f;
906         
907         /* get pointers */
908         prevfpt= fpts;
909         lastfpt= prevfpt + fcu->totvert-1;
910         
911         /* evaluation time at or past endpoints? */
912         if (prevfpt->vec[0] >= evaltime) {
913                 /* before or on first sample, so just extend value */
914                 cvalue= prevfpt->vec[1];
915         }
916         else if (lastfpt->vec[0] <= evaltime) {
917                 /* after or on last sample, so just extend value */
918                 cvalue= lastfpt->vec[1];
919         }
920         else {
921                 /* find the one on the right frame (assume that these are spaced on 1-frame intervals) */
922                 fpt= prevfpt + (int)(evaltime - prevfpt->vec[0]);
923                 cvalue= fpt->vec[1];
924         }
925         
926         /* return value */
927         return cvalue;
928 }
929
930 /* ******************************** F-Curve Modifiers ********************************* */
931
932 /* Template --------------------------- */
933
934 /* Each modifier defines a set of functions, which will be called at the appropriate
935  * times. In addition to this, each modifier should have a type-info struct, where
936  * its functions are attached for use. 
937  */
938  
939 /* Template for type-info data:
940  *      - make a copy of this when creating new modifiers, and just change the functions
941  *        pointed to as necessary
942  *      - although the naming of functions doesn't matter, it would help for code
943  *        readability, to follow the same naming convention as is presented here
944  *      - any functions that a constraint doesn't need to define, don't define
945  *        for such cases, just use NULL 
946  *      - these should be defined after all the functions have been defined, so that
947  *        forward-definitions/prototypes don't need to be used!
948  *      - keep this copy #if-def'd so that future constraints can get based off this
949  */
950 #if 0
951 static FModifierTypeInfo FMI_MODNAME = {
952         FMODIFIER_TYPE_MODNAME, /* type */
953         sizeof(FMod_ModName), /* size */
954         "Modifier Name", /* name */
955         "FMod_ModName", /* struct name */
956         fcm_modname_free, /* free data */
957         fcm_modname_relink, /* relink data */
958         fcm_modname_copy, /* copy data */
959         fcm_modname_new_data, /* new data */
960         fcm_modname_evaluate /* evaluate */
961 };
962 #endif
963
964 /* Generator F-Curve Modifier --------------------------- */
965
966 static void fcm_generator_free (FModifier *fcm)
967 {
968         FMod_Generator *data= (FMod_Generator *)fcm->data;
969         
970         /* free polynomial coefficients array */
971         if (data->poly_coefficients)
972                 MEM_freeN(data->poly_coefficients);
973 }
974
975 static void fcm_generator_copy (FModifier *fcm, FModifier *src)
976 {
977         FMod_Generator *gen= (FMod_Generator *)fcm->data;
978         FMod_Generator *ogen= (FMod_Generator *)src->data;
979         
980         /* copy polynomial coefficients array? */
981         if (ogen->poly_coefficients)
982                 gen->poly_coefficients= MEM_dupallocN(ogen->poly_coefficients);
983 }
984
985 static void fcm_generator_new_data (void *mdata)
986 {
987         FMod_Generator *data= (FMod_Generator *)mdata;
988         float *cp;
989         
990         /* set default generator to be linear 0-1 (gradient = 1, y-offset = 0) */
991         data->poly_order= 1;
992         cp= data->poly_coefficients= MEM_callocN(sizeof(float)*2, "FMod_Generator_Coefs");
993         cp[0] = 0; // y-offset 
994         cp[1] = 1; // gradient
995 }
996
997
998 static void fcm_generator_evaluate (FCurve *fcu, FModifier *fcm, float *cvalue, float evaltime)
999 {
1000         FMod_Generator *data= (FMod_Generator *)fcm->data;
1001         
1002         /* behaviour depends on mode (NOTE: we don't need to do anything...) */
1003         switch (data->mode) {
1004                 case FCM_GENERATOR_POLYNOMIAL: /* polynomial expression */
1005                 {
1006                         /* we overwrite cvalue with the sum of the polynomial */
1007                         float value= 0.0f, *cp = NULL;
1008                         unsigned int i;
1009                         
1010                         /* for each coefficient, add to value, which we'll write to *cvalue in one go */
1011                         // TODO: could this be more efficient (i.e. without need to recalc pow() everytime)
1012                         cp= data->poly_coefficients;
1013                         for (i=0; (i <= data->poly_order) && (cp); i++, cp++)
1014                                 value += (*cp) * pow(evaltime, i);
1015                         
1016                         /* only if something changed */
1017                         if (data->poly_order)
1018                                 *cvalue= value;
1019                 }
1020                         break;
1021
1022 #ifndef DISABLE_PYTHON
1023                 case FCM_GENERATOR_EXPRESSION: /* py-expression */
1024                         // TODO...
1025                         break;
1026 #endif /* DISABLE_PYTHON */
1027         }
1028 }
1029
1030 static FModifierTypeInfo FMI_GENERATOR = {
1031         FMODIFIER_TYPE_GENERATOR, /* type */
1032         sizeof(FMod_Generator), /* size */
1033         "Generator", /* name */
1034         "FMod_Generator", /* struct name */
1035         fcm_generator_free, /* free data */
1036         fcm_generator_copy, /* copy data */
1037         fcm_generator_new_data, /* new data */
1038         fcm_generator_evaluate /* evaluate */
1039 };
1040
1041 /* Envelope F-Curve Modifier --------------------------- */
1042
1043 static void fcm_envelope_free (FModifier *fcm)
1044 {
1045         FMod_Envelope *data= (FMod_Envelope *)fcm->data;
1046         
1047         /* free envelope data array */
1048         if (data->data)
1049                 MEM_freeN(data->data);
1050 }
1051
1052 static void fcm_envelope_copy (FModifier *fcm, FModifier *src)
1053 {
1054         FMod_Envelope *gen= (FMod_Envelope *)fcm->data;
1055         FMod_Envelope *ogen= (FMod_Envelope *)src->data;
1056         
1057         /* copy envelope data array */
1058         if (ogen->data)
1059                 gen->data= MEM_dupallocN(ogen->data);
1060 }
1061
1062 static void fcm_envelope_evaluate (FCurve *fcu, FModifier *fcm, float *cvalue, float evaltime)
1063 {
1064         FMod_Envelope *env= (FMod_Envelope *)fcm->data;
1065         FCM_EnvelopeData *fed, *prevfed, *lastfed;
1066         float min=0.0f, max=0.0f, fac=0.0f;
1067         int a;
1068         
1069         /* get pointers */
1070         if (env->data == NULL) return;
1071         prevfed= env->data;
1072         fed= prevfed + 1;
1073         lastfed= prevfed + env->totvert-1;
1074         
1075         /* get min/max values for envelope at evaluation time (relative to mid-value) */
1076         if (prevfed->time >= evaltime) {
1077                 /* before or on first sample, so just extend value */
1078                 min= prevfed->min;
1079                 max= prevfed->max;
1080         }
1081         else if (lastfed->time <= evaltime) {
1082                 /* after or on last sample, so just extend value */
1083                 min= lastfed->min;
1084                 max= lastfed->max;
1085         }
1086         else {
1087                 /* evaltime occurs somewhere between segments */
1088                 for (a=0; prevfed && fed && (a < env->totvert-1); a++, prevfed=fed, fed++) {  
1089                         /* evaltime occurs within the interval defined by these two envelope points */
1090                         if ((prevfed->time <= evaltime) && (fed->time >= evaltime)) {
1091                                 float afac, bfac, diff;
1092                                 
1093                                 diff= fed->time - prevfed->time;
1094                                 afac= (evaltime - prevfed->time) / diff;
1095                                 bfac= (fed->time - evaltime)/(diff);
1096                                 
1097                                 min= afac*prevfed->min + bfac*fed->min;
1098                                 max= afac*prevfed->max + bfac*fed->max;
1099                                 
1100                                 break;
1101                         }
1102                 }
1103         }
1104         
1105         /* adjust *cvalue 
1106          * NOTE: env->min/max are relative to env->midval, and can be either +ve OR -ve, so we add...
1107          */
1108         fac= (*cvalue - min) / (max - min);
1109         *cvalue= (env->midval + env->min) + (fac * (env->max - env->min)); 
1110 }
1111
1112 static FModifierTypeInfo FMI_ENVELOPE = {
1113         FMODIFIER_TYPE_ENVELOPE, /* type */
1114         sizeof(FMod_Envelope), /* size */
1115         "Envelope", /* name */
1116         "FMod_Envelope", /* struct name */
1117         fcm_envelope_free, /* free data */
1118         fcm_envelope_copy, /* copy data */
1119         NULL, /* new data */
1120         fcm_envelope_evaluate /* evaluate */
1121 };
1122
1123 /* Cycles F-Curve Modifier  --------------------------- */
1124
1125 /* This modifier changes evaltime to something that exists within the curve's frame-range, 
1126  * then re-evaluates modifier stack up to this point using the new time. This re-entrant behaviour
1127  * is very likely to be more time-consuming than the original approach... (which was tighly integrated into 
1128  * the calculation code...).
1129  *
1130  * NOTE: this needs to be at the start of the stack to be of use, as it needs to know the extents of the keyframes/sample-data
1131  * Possible TODO - store length of cycle information that can be initialised from the extents of the keyframes/sample-data, and adjusted
1132  *                              as appropriate
1133  */
1134
1135 static void fcm_cycles_evaluate (FCurve *fcu, FModifier *fcm, float *cvalue, float evaltime)
1136 {
1137         FMod_Cycles *data= (FMod_Cycles *)fcm->data;
1138         ListBase mods = {NULL, NULL};
1139         float prevkey[2], lastkey[2], cycyofs=0.0f;
1140         float new_value;
1141         short side=0, mode=0;
1142         int cycles=0;
1143         
1144         /* check if modifier is first in stack, otherwise disable ourself... */
1145         // FIXME...
1146         if (fcm->prev) {
1147                 fcm->flag |= FMODIFIER_FLAG_DISABLED;
1148                 return;
1149         }
1150         
1151         /* calculate new evaltime due to cyclic interpolation */
1152         if (fcu && fcu->bezt) {
1153                 BezTriple *prevbezt= fcu->bezt;
1154                 BezTriple *lastbezt= prevbezt + fcu->totvert-1;
1155                 
1156                 prevkey[0]= prevbezt->vec[1][0];
1157                 prevkey[1]= prevbezt->vec[1][1];
1158                 
1159                 lastkey[0]= lastbezt->vec[1][0];
1160                 lastkey[1]= lastbezt->vec[1][1];
1161         }
1162         else if (fcu && fcu->fpt) {
1163                 FPoint *prevfpt= fcu->fpt;
1164                 FPoint *lastfpt= prevfpt + fcu->totvert-1;
1165                 
1166                 prevkey[0]= prevfpt->vec[0];
1167                 prevkey[1]= prevfpt->vec[1];
1168                 
1169                 lastkey[0]= lastfpt->vec[0];
1170                 lastkey[1]= lastfpt->vec[1];
1171         }
1172         else
1173                 return;
1174                 
1175         /* check if modifier will do anything
1176          *      1) if in data range, definitely don't do anything
1177          *      2) if before first frame or after last frame, make sure some cycling is in use
1178          */
1179         if (evaltime < prevkey[0]) {
1180                 if (data->before_mode) {
1181                         side= -1;
1182                         mode= data->before_mode;
1183                         cycles= data->before_cycles;
1184                 }
1185         }
1186         else if (evaltime > lastkey[0]) {
1187                 if (data->after_mode) {
1188                         side= 1;
1189                         mode= data->after_mode;
1190                         cycles= data->after_cycles;
1191                 }
1192         }
1193         if ELEM(0, side, mode)
1194                 return;
1195                 
1196         /* extrapolation mode is 'cyclic' - find relative place within a cycle */
1197         // FIXME: adding the more fine-grained control of extrpolation mode
1198         {
1199                 float cycdx=0, cycdy=0, ofs=0;
1200                 
1201                 /* ofs is start frame of cycle */
1202                 ofs= prevkey[0];
1203                 
1204                 /* calculate period and amplitude (total height) of a cycle */
1205                 cycdx= lastkey[0] - prevkey[0];
1206                 cycdy= lastkey[1] - prevkey[1];
1207                 
1208                 /* check if cycle is infinitely small, to be point of being impossible to use */
1209                 if (cycdx == 0)
1210                         return;
1211                 /* check that cyclic is still enabled for the specified time */
1212                 if (cycles == 0) {
1213                         /* catch this case so that we don't exit when we have cycles=0
1214                          * as this indicates infinite cycles...
1215                          */
1216                 }
1217                 else if ( ((float)side * (evaltime - ofs) / cycdx) > cycles )
1218                         return;
1219                 
1220                 
1221                 /* check if 'cyclic extrapolation', and thus calculate y-offset for this cycle */
1222                 if (mode == FCM_EXTRAPOLATE_CYCLIC_OFFSET) {
1223                         cycyofs = (float)floor((evaltime - ofs) / cycdx);
1224                         cycyofs *= cycdy;
1225                 }
1226                 
1227                 /* calculate where in the cycle we are (overwrite evaltime to reflect this) */
1228                 evaltime= (float)(fmod(evaltime-ofs, cycdx) + ofs);
1229                 if (evaltime < ofs) evaltime += cycdx;
1230         }
1231         
1232         
1233         /* store modifiers after (and including ourself) before recalculating curve with new evaltime */
1234         mods= fcu->modifiers;
1235         fcu->modifiers.first= fcu->modifiers.last= NULL;
1236         
1237         /* re-enter the evaluation loop (but without the burden of evaluating any modifiers, so 'should' be relatively quick) */
1238         new_value= evaluate_fcurve(fcu, evaltime);
1239         
1240         /* restore modifiers, and set new value (don't assume everything is still ok after being re-entrant) */
1241         fcu->modifiers= mods;
1242         *cvalue= new_value + cycyofs;
1243 }
1244
1245 static FModifierTypeInfo FMI_CYCLES = {
1246         FMODIFIER_TYPE_CYCLES, /* type */
1247         sizeof(FMod_Cycles), /* size */
1248         "Cycles", /* name */
1249         "FMod_Cycles", /* struct name */
1250         NULL, /* free data */
1251         NULL, /* copy data */
1252         NULL, /* new data */
1253         fcm_cycles_evaluate /* evaluate */
1254 };
1255
1256 /* Noise F-Curve Modifier  --------------------------- */
1257
1258 #if 0 // XXX not yet implemented 
1259 static FModifierTypeInfo FMI_NOISE = {
1260         FMODIFIER_TYPE_NOISE, /* type */
1261         sizeof(FMod_Noise), /* size */
1262         "Noise", /* name */
1263         "FMod_Noise", /* struct name */
1264         NULL, /* free data */
1265         NULL, /* copy data */
1266         fcm_noise_new_data, /* new data */
1267         fcm_noise_evaluate /* evaluate */
1268 };
1269 #endif // XXX not yet implemented
1270
1271 /* Filter F-Curve Modifier --------------------------- */
1272
1273 #if 0 // XXX not yet implemented 
1274 static FModifierTypeInfo FMI_FILTER = {
1275         FMODIFIER_TYPE_FILTER, /* type */
1276         sizeof(FMod_Filter), /* size */
1277         "Filter", /* name */
1278         "FMod_Filter", /* struct name */
1279         NULL, /* free data */
1280         NULL, /* copy data */
1281         NULL, /* new data */
1282         fcm_filter_evaluate /* evaluate */
1283 };
1284 #endif // XXX not yet implemented
1285
1286
1287 /* Python F-Curve Modifier --------------------------- */
1288
1289 static void fcm_python_free (FModifier *fcm)
1290 {
1291         FMod_Python *data= (FMod_Python *)fcm->data;
1292         
1293         /* id-properties */
1294         IDP_FreeProperty(data->prop);
1295         MEM_freeN(data->prop);
1296 }
1297
1298 static void fcm_python_new_data (void *mdata) 
1299 {
1300         FMod_Python *data= (FMod_Python *)mdata;
1301         
1302         /* everything should be set correctly by calloc, except for the prop->type constant.*/
1303         data->prop = MEM_callocN(sizeof(IDProperty), "PyFModifierProps");
1304         data->prop->type = IDP_GROUP;
1305 }
1306
1307 static void fcm_python_copy (FModifier *fcm, FModifier *src)
1308 {
1309         FMod_Python *pymod = (FMod_Python *)fcm->data;
1310         FMod_Python *opymod = (FMod_Python *)src->data;
1311         
1312         pymod->prop = IDP_CopyProperty(opymod->prop);
1313 }
1314
1315 static void fcm_python_evaluate (FCurve *fcu, FModifier *fcm, float *cvalue, float evaltime)
1316 {
1317 #ifndef DISABLE_PYTHON
1318         //FMod_Python *data= (FMod_Python *)fcm->data;
1319         
1320         /* FIXME... need to implement this modifier...
1321          *      It will need it execute a script using the custom properties 
1322          */
1323 #endif /* DISABLE_PYTHON */
1324 }
1325
1326 static FModifierTypeInfo FMI_PYTHON = {
1327         FMODIFIER_TYPE_PYTHON, /* type */
1328         sizeof(FMod_Python), /* size */
1329         "Python", /* name */
1330         "FMod_Python", /* struct name */
1331         fcm_python_free, /* free data */
1332         fcm_python_copy, /* copy data */
1333         fcm_python_new_data, /* new data */
1334         fcm_python_evaluate /* evaluate */
1335 };
1336
1337
1338 /* F-Curve Modifier API --------------------------- */
1339 /* All of the F-Curve Modifier api functions use FModifierTypeInfo structs to carry out
1340  * and operations that involve F-Curve modifier specifc code.
1341  */
1342
1343 /* These globals only ever get directly accessed in this file */
1344 static FModifierTypeInfo *fmodifiersTypeInfo[FMODIFIER_NUM_TYPES];
1345 static short FMI_INIT= 1; /* when non-zero, the list needs to be updated */
1346
1347 /* This function only gets called when FMI_INIT is non-zero */
1348 static void fmods_init_typeinfo () {
1349         fmodifiersTypeInfo[0]=  NULL;                                   /* 'Null' F-Curve Modifier */
1350         fmodifiersTypeInfo[1]=  &FMI_GENERATOR;                 /* Generator F-Curve Modifier */
1351         fmodifiersTypeInfo[2]=  &FMI_ENVELOPE;                  /* Envelope F-Curve Modifier */
1352         fmodifiersTypeInfo[3]=  &FMI_CYCLES;                    /* Cycles F-Curve Modifier */
1353         fmodifiersTypeInfo[4]=  NULL/*&FMI_NOISE*/;                             /* Apply-Noise F-Curve Modifier */ // XXX unimplemented
1354         fmodifiersTypeInfo[5]=  NULL/*&FMI_FILTER*/;                    /* Filter F-Curve Modifier */  // XXX unimplemented
1355         fmodifiersTypeInfo[6]=  &FMI_PYTHON;                    /* Custom Python F-Curve Modifier */
1356 }
1357
1358 /* This function should be used for getting the appropriate type-info when only
1359  * a F-Curve modifier type is known
1360  */
1361 FModifierTypeInfo *get_fmodifier_typeinfo (int type)
1362 {
1363         /* initialise the type-info list? */
1364         if (FMI_INIT) {
1365                 fmods_init_typeinfo();
1366                 FMI_INIT = 0;
1367         }
1368         
1369         /* only return for valid types */
1370         if ( (type >= FMODIFIER_TYPE_NULL) && 
1371                  (type <= FMODIFIER_NUM_TYPES ) ) 
1372         {
1373                 /* there shouldn't be any segfaults here... */
1374                 return fmodifiersTypeInfo[type];
1375         }
1376         else {
1377                 printf("No valid F-Curve Modifier type-info data available. Type = %i \n", type);
1378         }
1379         
1380         return NULL;
1381
1382  
1383 /* This function should always be used to get the appropriate type-info, as it
1384  * has checks which prevent segfaults in some weird cases.
1385  */
1386 FModifierTypeInfo *fmodifier_get_typeinfo (FModifier *fcm)
1387 {
1388         /* only return typeinfo for valid modifiers */
1389         if (fcm)
1390                 return get_fmodifier_typeinfo(fcm->type);
1391         else
1392                 return NULL;
1393 }
1394
1395 /* API --------------------------- */
1396
1397 /* Add a new F-Curve Modifier to the given F-Curve of a certain type */
1398 FModifier *fcurve_add_modifier (FCurve *fcu, int type)
1399 {
1400         FModifierTypeInfo *fmi= get_fmodifier_typeinfo(type);
1401         FModifier *fcm;
1402         
1403         /* sanity checks */
1404         if ELEM(NULL, fcu, fmi)
1405                 return NULL;
1406         
1407         /* special checks for whether modifier can be added */
1408         if ((fcu->modifiers.first) && (type == FMODIFIER_TYPE_CYCLES)) {
1409                 /* cycles modifier must be first in stack, so for now, don't add if it can't be */
1410                 // TODO: perhaps there is some better way, but for now, 
1411                 printf("Error: Cannot add 'Cycles' modifier to F-Curve, as 'Cycles' modifier can only be first in stack. \n");
1412                 return NULL;
1413         }
1414         
1415         /* add modifier itself */
1416         fcm= MEM_callocN(sizeof(FModifier), "F-Curve Modifier");
1417         BLI_addtail(&fcu->modifiers, fcm);
1418         
1419         /* add modifier's data */
1420         fcm->data= MEM_callocN(fmi->size, "F-Curve Modifier Data");
1421                 
1422         /* init custom settings if necessary */
1423         if (fmi->new_data)      
1424                 fmi->new_data(fcm->data);
1425                 
1426         /* return modifier for further editing */
1427         return fcm;
1428 }
1429
1430 /* Duplicate all of the F-Curve Modifiers in the Modifier stacks */
1431 void fcurve_copy_modifiers (ListBase *dst, ListBase *src)
1432 {
1433         FModifier *fcm, *srcfcm;
1434         
1435         if ELEM(NULL, dst, src)
1436                 return;
1437         
1438         dst->first= dst->last= NULL;
1439         BLI_duplicatelist(dst, src);
1440         
1441         for (fcm=dst->first, srcfcm=src->first; fcm && srcfcm; srcfcm=srcfcm->next, fcm=fcm->next) {
1442                 FModifierTypeInfo *fmi= fmodifier_get_typeinfo(fcm);
1443                 
1444                 /* make a new copy of the F-Modifier's data */
1445                 fcm->data = MEM_dupallocN(fcm->data);
1446                 
1447                 /* only do specific constraints if required */
1448                 if (fmi && fmi->copy_data)
1449                         fmi->copy_data(fcm, srcfcm);
1450         }
1451 }
1452
1453 /* Remove and free the given F-Curve Modifier from the given F-Curve's stack  */
1454 void fcurve_remove_modifier (FCurve *fcu, FModifier *fcm)
1455 {
1456         FModifierTypeInfo *fmi= fmodifier_get_typeinfo(fcm);
1457         
1458         /* sanity check */
1459         if (fcm == NULL)
1460                 return;
1461         
1462         /* free modifier's special data (stored inside fcm->data) */
1463         if (fmi && fmi->free_data)
1464                 fmi->free_data(fcm);
1465                 
1466         /* free modifier's data (fcm->data) */
1467         MEM_freeN(fcm->data);
1468         
1469         /* remove modifier from stack */
1470         if (fcu)
1471                 BLI_freelinkN(&fcu->modifiers, fcm);
1472         else {
1473                 // XXX this case can probably be removed some day, as it shouldn't happen...
1474                 printf("fcurve_remove_modifier() - no fcurve \n");
1475                 MEM_freeN(fcm);
1476         }
1477 }
1478
1479 /* Remove all of a given F-Curve's modifiers */
1480 void fcurve_free_modifiers (FCurve *fcu)
1481 {
1482         FModifier *fcm, *fmn;
1483         
1484         /* sanity check */
1485         if (fcu == NULL)
1486                 return;
1487         
1488         /* free each modifier in order - modifier is unlinked from list and freed */
1489         for (fcm= fcu->modifiers.first; fcm; fcm= fmn) {
1490                 fmn= fcm->next;
1491                 fcurve_remove_modifier(fcu, fcm);
1492         }
1493 }
1494
1495 /* Bake modifiers for given F-Curve to curve sample data, in the frame range defined
1496  * by start and end (inclusive).
1497  */
1498 void fcurve_bake_modifiers (FCurve *fcu, int start, int end)
1499 {
1500         FPoint *fpt, *new_fpt;
1501         int cfra;
1502         
1503         /* sanity checks */
1504         // TODO: make these tests report errors using reports not printf's
1505         if ELEM(NULL, fcu, fcu->modifiers.first) {
1506                 printf("Error: No F-Curve with F-Curve Modifiers to Bake\n");
1507                 return;
1508         }
1509         if (start >= end) {
1510                 printf("Error: Frame range for F-Curve Modifier Baking inappropriate \n");
1511                 return;
1512         }
1513         
1514         /* set up sample data */
1515         fpt= new_fpt= MEM_callocN(sizeof(FPoint)*(end-start+1), "FPoint FModifier Samples");
1516         
1517         /* sample the curve at 1-frame intervals from start to end frames 
1518          *      - assume that any ChannelDriver possibly present did not interfere in any way
1519          */
1520         for (cfra= start; cfra <= end; cfra++, fpt++) {
1521                 fpt->vec[0]= (float)cfra;
1522                 fpt->vec[1]= evaluate_fcurve(fcu, (float)cfra);
1523         }
1524         
1525         /* free any existing sample/keyframe data on curve, and all modifiers */
1526         if (fcu->bezt) MEM_freeN(fcu->bezt);
1527         if (fcu->fpt) MEM_freeN(fcu->fpt);
1528         fcurve_free_modifiers(fcu);
1529         
1530         /* store the samples */
1531         fcu->fpt= new_fpt;
1532         fcu->totvert= end - start + 1;
1533 }
1534
1535 /* ***************************** F-Curve - Evaluation ********************************* */
1536
1537 /* Evaluate and return the value of the given F-Curve at the specified frame ("evaltime") 
1538  * Note: this is also used for drivers
1539  */
1540 // TODO: set up the modifier system...
1541 float evaluate_fcurve (FCurve *fcu, float evaltime) 
1542 {
1543         FModifier *fcm;
1544         float cvalue = 0.0f;
1545         
1546         /* if there is a driver (only if this F-Curve is acting as 'driver'), evaluate it to find value to use as "evaltime" 
1547          *      - this value will also be returned as the value of the 'curve', if there are no keyframes
1548          */
1549         if (fcu->driver) {
1550                 /* evaltime now serves as input for the curve */
1551                 evaltime= cvalue= evaluate_driver(fcu->driver, evaltime);
1552         }
1553         
1554         /* evaluate curve-data */
1555         if (fcu->bezt)
1556                 cvalue= fcurve_eval_keyframes(fcu, fcu->bezt, evaltime);
1557         else if (fcu->fpt)
1558                 cvalue= fcurve_eval_samples(fcu, fcu->fpt, evaltime);
1559         
1560         /* evaluate modifiers */
1561         for (fcm= fcu->modifiers.first; fcm; fcm= fcm->next) {
1562                 FModifierTypeInfo *fmi= fmodifier_get_typeinfo(fcm);
1563                 
1564                 /* only evaluate if there's a callback for this */
1565                 // TODO: implement the 'influence' control feature...
1566                 if (fmi && fmi->evaluate_modifier) {
1567                         if ((fcm->flag & FMODIFIER_FLAG_DISABLED) == 0)
1568                                 fmi->evaluate_modifier(fcu, fcm, &cvalue, evaltime);
1569                 }
1570         }
1571         
1572         /* return evaluated value */
1573         return cvalue;
1574 }
1575
1576 /* Calculate the value of the given F-Curve at the given frame, and set its curval */
1577 // TODO: will this be necessary?
1578 void calculate_fcurve (FCurve *fcu, float ctime)
1579 {
1580         /* calculate and set curval (evaluates driver too) */
1581         fcu->curval= evaluate_fcurve(fcu, ctime);
1582 }
1583