0585717e13e570f229230fa8afd3540b7bc8bf77
[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 <stddef.h>
9 #include <string.h>
10 #include <float.h>
11
12 #ifdef HAVE_CONFIG_H
13 #include <config.h>
14 #endif
15
16 #include "MEM_guardedalloc.h"
17
18 #include "DNA_anim_types.h"
19
20 #include "BLI_blenlib.h"
21 #include "BLI_arithb.h"
22 #include "BLI_noise.h"
23
24 #include "BKE_fcurve.h"
25 #include "BKE_curve.h" 
26 #include "BKE_global.h"
27 #include "BKE_idprop.h"
28 #include "BKE_utildefines.h"
29
30 #include "RNA_access.h"
31 #include "RNA_types.h"
32
33 #ifndef DISABLE_PYTHON
34 #include "BPY_extern.h" /* for BPY_pydriver_eval() */
35 #endif
36
37 #define SMALL -1.0e-10
38 #define SELECT 1
39
40 /* ************************** Data-Level Functions ************************* */
41
42 /* ---------------------- Freeing --------------------------- */
43
44 /* Frees the F-Curve itself too, so make sure BLI_remlink is called before calling this... */
45 void free_fcurve (FCurve *fcu) 
46 {
47         if (fcu == NULL) 
48                 return;
49         
50         /* free curve data */
51         if (fcu) {
52                 if (fcu->bezt) MEM_freeN(fcu->bezt);
53                 if (fcu->fpt) MEM_freeN(fcu->fpt);
54         }
55         
56         /* free RNA-path, as this were allocated when getting the path string */
57         if (fcu->rna_path)
58                 MEM_freeN(fcu->rna_path);
59         
60         /* free extra data - i.e. modifiers, and driver */
61         fcurve_free_driver(fcu);
62         fcurve_free_modifiers(fcu);
63         
64         /* free f-curve itself */
65         MEM_freeN(fcu);
66 }
67
68 /* Frees a list of F-Curves */
69 void free_fcurves (ListBase *list)
70 {
71         FCurve *fcu, *fcn;
72         
73         /* sanity check */
74         if (list == NULL)
75                 return;
76                 
77         /* free data - no need to call remlink before freeing each curve, 
78          * as we store reference to next, and freeing only touches the curve
79          * it's given
80          */
81         for (fcu= list->first; fcu; fcu= fcn) {
82                 fcn= fcu->next;
83                 free_fcurve(fcu);
84         }
85         
86         /* clear pointers just in case */
87         list->first= list->last= NULL;
88 }       
89
90 /* ---------------------- Copy --------------------------- */
91
92 /* duplicate an F-Curve */
93 FCurve *copy_fcurve (FCurve *fcu)
94 {
95         FCurve *fcu_d;
96         
97         /* sanity check */
98         if (fcu == NULL)
99                 return NULL;
100                 
101         /* make a copy */
102         fcu_d= MEM_dupallocN(fcu);
103         
104         fcu_d->next= fcu_d->prev= NULL;
105         fcu_d->grp= NULL;
106         
107         /* copy curve data */
108         fcu_d->bezt= MEM_dupallocN(fcu_d->bezt);
109         fcu_d->fpt= MEM_dupallocN(fcu_d->fpt);
110         
111         /* copy rna-path */
112         fcu_d->rna_path= MEM_dupallocN(fcu_d->rna_path);
113         
114         /* copy driver */
115         fcu_d->driver= fcurve_copy_driver(fcu_d->driver);
116         
117         /* copy modifiers */
118         fcurve_copy_modifiers(&fcu_d->modifiers, &fcu->modifiers);
119         
120         /* return new data */
121         return fcu_d;
122 }
123
124 /* duplicate a list of F-Curves */
125 void copy_fcurves (ListBase *dst, ListBase *src)
126 {
127         FCurve *dfcu, *sfcu;
128         
129         /* sanity checks */
130         if ELEM(NULL, dst, src)
131                 return;
132         
133         /* clear destination list first */
134         dst->first= dst->last= NULL;
135         
136         /* copy one-by-one */
137         for (sfcu= src->first; sfcu; sfcu= sfcu->next) {
138                 dfcu= copy_fcurve(sfcu);
139                 BLI_addtail(dst, dfcu);
140         }
141 }
142
143 /* ---------------------- Relink --------------------------- */
144
145 #if 0
146 /* uses id->newid to match pointers with other copied data 
147  *      - called after single-user or other such
148  */
149                         if (icu->driver)
150                                 ID_NEW(icu->driver->ob);
151 #endif
152
153 /* --------------------- Finding -------------------------- */
154
155 /* Find the F-Curve affecting the given RNA-access path + index, in the list of F-Curves provided */
156 FCurve *list_find_fcurve (ListBase *list, const char rna_path[], const int array_index)
157 {
158         FCurve *fcu;
159         
160         /* sanity checks */
161         if ( ELEM(NULL, list, rna_path) || (array_index < 0) )
162                 return NULL;
163         
164         /* check paths of curves, then array indices... */
165         for (fcu= list->first; fcu; fcu= fcu->next) {
166                 /* simple string-compare (this assumes that they have the same root...) */
167                 if (strcmp(fcu->rna_path, rna_path) == 0) {
168                         /* now check indicies */
169                         if (fcu->array_index == array_index)
170                                 return fcu;
171                 }
172         }
173         
174         /* return */
175         return NULL;
176 }
177
178 int on_keyframe_fcurve(FCurve *fcu, float cfra)
179 {
180         BezTriple *bezt;
181         int i;
182
183         bezt= fcu->bezt;
184         for (i=0; i<fcu->totvert; i++, bezt++)
185                 if(IS_EQ(bezt->vec[1][0], cfra))
186                         return 1;
187         
188         return 0;
189 }
190
191 /* Calculate the extents of F-Curve's data */
192 void calc_fcurve_bounds (FCurve *fcu, float *xmin, float *xmax, float *ymin, float *ymax)
193 {
194         float xminv=999999999.0f, xmaxv=-999999999.0f;
195         float yminv=999999999.0f, ymaxv=-999999999.0f;
196         short foundvert=0;
197         unsigned int i;
198         
199         if (fcu->totvert) {
200                 if (fcu->bezt) {
201                         /* frame range can be directly calculated from end verts */
202                         if (xmin || xmax) {
203                                 xminv= MIN2(xminv, fcu->bezt[0].vec[1][0]);
204                                 xmaxv= MAX2(xmaxv, fcu->bezt[fcu->totvert-1].vec[1][0]);
205                         }
206                         
207                         /* only loop over keyframes to find extents for values if needed */
208                         if (ymin || ymax) {
209                                 BezTriple *bezt;
210                                 
211                                 for (bezt=fcu->bezt, i=0; i < fcu->totvert; bezt++, i++) {
212                                         yminv= MIN2(yminv, bezt->vec[1][1]);
213                                         ymaxv= MAX2(ymaxv, bezt->vec[1][1]);
214                                 }
215                         }
216                 }
217                 else if (fcu->fpt) {
218                         /* frame range can be directly calculated from end verts */
219                         if (xmin || xmax) {
220                                 xminv= MIN2(xminv, fcu->fpt[0].vec[0]);
221                                 xmaxv= MAX2(xmaxv, fcu->fpt[fcu->totvert-1].vec[0]);
222                         }
223                         
224                         /* only loop over keyframes to find extents for values if needed */
225                         if (ymin || ymax) {
226                                 FPoint *fpt;
227                                 
228                                 for (fpt=fcu->fpt, i=0; i < fcu->totvert; fpt++, i++) {
229                                         yminv= MIN2(yminv, fpt->vec[1]);
230                                         ymaxv= MAX2(ymaxv, fpt->vec[1]);
231                                 }
232                         }
233                 }
234                 
235                 foundvert=1;
236         }
237         
238         /* minimum sizes are 1.0f */
239         if (foundvert) {
240                 if (xminv == xmaxv) xmaxv += 1.0f;
241                 if (yminv == ymaxv) ymaxv += 1.0f;
242                 
243                 if (xmin) *xmin= xminv;
244                 if (xmax) *xmax= xmaxv;
245                 
246                 if (ymin) *ymin= yminv;
247                 if (ymax) *ymax= ymaxv;
248         }
249         else {
250                 if (xmin) *xmin= 0.0f;
251                 if (xmax) *xmax= 0.0f;
252                 
253                 if (ymin) *ymin= 1.0f;
254                 if (ymax) *ymax= 1.0f;
255         }
256 }
257
258 /* Calculate the extents of F-Curve's keyframes */
259 void calc_fcurve_range (FCurve *fcu, float *start, float *end)
260 {
261         float min=999999999.0f, max=-999999999.0f;
262         short foundvert=0;
263
264         if (fcu->totvert) {
265                 if (fcu->bezt) {
266                         min= MIN2(min, fcu->bezt[0].vec[1][0]);
267                         max= MAX2(max, fcu->bezt[fcu->totvert-1].vec[1][0]);
268                 }
269                 else if (fcu->fpt) {
270                         min= MIN2(min, fcu->fpt[0].vec[0]);
271                         max= MAX2(max, fcu->fpt[fcu->totvert-1].vec[0]);
272                 }
273                 
274                 foundvert=1;
275         }
276         
277         /* minimum length is 1 frame */
278         if (foundvert) {
279                 if (min == max) max += 1.0f;
280                 *start= min;
281                 *end= max;
282         }
283         else {
284                 *start= 0.0f;
285                 *end= 1.0f;
286         }
287 }
288
289 /* ***************************** Keyframe Column Tools ********************************* */
290
291 /* add a BezTriple to a column */
292 void bezt_add_to_cfra_elem (ListBase *lb, BezTriple *bezt)
293 {
294         CfraElem *ce, *cen;
295         
296         for (ce= lb->first; ce; ce= ce->next) {
297                 /* double key? */
298                 if (ce->cfra == bezt->vec[1][0]) {
299                         if (bezt->f2 & SELECT) ce->sel= bezt->f2;
300                         return;
301                 }
302                 /* should key be inserted before this column? */
303                 else if (ce->cfra > bezt->vec[1][0]) break;
304         }
305         
306         /* create a new column */
307         cen= MEM_callocN(sizeof(CfraElem), "add_to_cfra_elem"); 
308         if (ce) BLI_insertlinkbefore(lb, ce, cen);
309         else BLI_addtail(lb, cen);
310
311         cen->cfra= bezt->vec[1][0];
312         cen->sel= bezt->f2;
313 }
314
315 /* ***************************** Samples Utilities ******************************* */
316 /* Some utilities for working with FPoints (i.e. 'sampled' animation curve data, such as
317  * data imported from BVH/Mocap files), which are specialised for use with high density datasets,
318  * which BezTriples/Keyframe data are ill equipped to do.
319  */
320  
321  
322 /* Basic sampling callback which acts as a wrapper for evaluate_fcurve() 
323  *      'data' arg here is unneeded here...
324  */
325 float fcurve_samplingcb_evalcurve (FCurve *fcu, void *data, float evaltime)
326 {
327         /* assume any interference from drivers on the curve is intended... */
328         return evaluate_fcurve(fcu, evaltime);
329
330
331  
332 /* Main API function for creating a set of sampled curve data, given some callback function 
333  * used to retrieve the values to store.
334  */
335 void fcurve_store_samples (FCurve *fcu, void *data, int start, int end, FcuSampleFunc sample_cb)
336 {
337         FPoint *fpt, *new_fpt;
338         int cfra;
339         
340         /* sanity checks */
341         // TODO: make these tests report errors using reports not printf's
342         if ELEM(NULL, fcu, sample_cb) {
343                 printf("Error: No F-Curve with F-Curve Modifiers to Bake\n");
344                 return;
345         }
346         if (start >= end) {
347                 printf("Error: Frame range for Sampled F-Curve creation is inappropriate \n");
348                 return;
349         }
350         
351         /* set up sample data */
352         fpt= new_fpt= MEM_callocN(sizeof(FPoint)*(end-start+1), "FPoint Samples");
353         
354         /* use the sampling callback at 1-frame intervals from start to end frames */
355         for (cfra= start; cfra <= end; cfra++, fpt++) {
356                 fpt->vec[0]= (float)cfra;
357                 fpt->vec[1]= sample_cb(fcu, data, (float)cfra);
358         }
359         
360         /* free any existing sample/keyframe data on curve  */
361         if (fcu->bezt) MEM_freeN(fcu->bezt);
362         if (fcu->fpt) MEM_freeN(fcu->fpt);
363         
364         /* store the samples */
365         fcu->bezt= NULL;
366         fcu->fpt= new_fpt;
367         fcu->totvert= end - start + 1;
368 }
369
370 /* ***************************** F-Curve Sanity ********************************* */
371 /* The functions here are used in various parts of Blender, usually after some editing
372  * of keyframe data has occurred. They ensure that keyframe data is properly ordered and
373  * that the handles are correctly 
374  */
375
376 /* This function recalculates the handles of an F-Curve 
377  * If the BezTriples have been rearranged, sort them first before using this.
378  */
379 void calchandles_fcurve (FCurve *fcu)
380 {
381         BezTriple *bezt, *prev, *next;
382         int a= fcu->totvert;
383
384         /* Error checking:
385          *      - need at least two points
386          *      - need bezier keys
387          *      - only bezier-interpolation has handles (for now)
388          */
389         if (ELEM(NULL, fcu, fcu->bezt) || (a < 2) /*|| ELEM(fcu->ipo, BEZT_IPO_CONST, BEZT_IPO_LIN)*/) 
390                 return;
391         
392         /* get initial pointers */
393         bezt= fcu->bezt;
394         prev= NULL;
395         next= (bezt + 1);
396         
397         /* loop over all beztriples, adjusting handles */
398         while (a--) {
399                 /* clamp timing of handles to be on either side of beztriple */
400                 if (bezt->vec[0][0] > bezt->vec[1][0]) bezt->vec[0][0]= bezt->vec[1][0];
401                 if (bezt->vec[2][0] < bezt->vec[1][0]) bezt->vec[2][0]= bezt->vec[1][0];
402                 
403                 /* calculate auto-handles */
404                 if (fcu->flag & FCURVE_AUTO_HANDLES) 
405                         calchandleNurb(bezt, prev, next, 2);    /* 2==special autohandle && keep extrema horizontal */
406                 else
407                         calchandleNurb(bezt, prev, next, 1);    /* 1==special autohandle */
408                 
409                 /* for automatic ease in and out */
410                 if ((bezt->h1==HD_AUTO) && (bezt->h2==HD_AUTO)) {
411                         /* only do this on first or last beztriple */
412                         if ((a == 0) || (a == fcu->totvert-1)) {
413                                 /* set both handles to have same horizontal value as keyframe */
414                                 if (fcu->extend == FCURVE_EXTRAPOLATE_CONSTANT) {
415                                         bezt->vec[0][1]= bezt->vec[2][1]= bezt->vec[1][1];
416                                 }
417                         }
418                 }
419                 
420                 /* advance pointers for next iteration */
421                 prev= bezt;
422                 if (a == 1) next= NULL;
423                 else next++;
424                 bezt++;
425         }
426 }
427
428 /* Use when F-Curve with handles has changed
429  * It treats all BezTriples with the following rules:
430  *  - PHASE 1: do types have to be altered?
431  *              -> Auto handles: become aligned when selection status is NOT(000 || 111)
432  *              -> Vector handles: become 'nothing' when (one half selected AND other not)
433  *  - PHASE 2: recalculate handles
434 */
435 void testhandles_fcurve (FCurve *fcu)
436 {
437         BezTriple *bezt;
438         unsigned int a;
439
440         /* only beztriples have handles (bpoints don't though) */
441         if ELEM(NULL, fcu, fcu->bezt)
442                 return;
443         
444         /* loop over beztriples */
445         for (a=0, bezt=fcu->bezt; a < fcu->totvert; a++, bezt++) {
446                 short flag= 0;
447                 
448                 /* flag is initialised as selection status
449                  * of beztriple control-points (labelled 0,1,2)
450                  */
451                 if (bezt->f1 & SELECT) flag |= (1<<0); // == 1
452                 if (bezt->f2 & SELECT) flag |= (1<<1); // == 2
453                 if (bezt->f3 & SELECT) flag |= (1<<2); // == 4
454                 
455                 /* one or two handles selected only */
456                 if (ELEM(flag, 0, 7)==0) {
457                         /* auto handles become aligned */
458                         if (bezt->h1==HD_AUTO)
459                                 bezt->h1= HD_ALIGN;
460                         if (bezt->h2==HD_AUTO)
461                                 bezt->h2= HD_ALIGN;
462                         
463                         /* vector handles become 'free' when only one half selected */
464                         if (bezt->h1==HD_VECT) {
465                                 /* only left half (1 or 2 or 1+2) */
466                                 if (flag < 4) 
467                                         bezt->h1= 0;
468                         }
469                         if (bezt->h2==HD_VECT) {
470                                 /* only right half (4 or 2+4) */
471                                 if (flag > 3) 
472                                         bezt->h2= 0;
473                         }
474                 }
475         }
476
477         /* recalculate handles */
478         calchandles_fcurve(fcu);
479 }
480
481 /* This function sorts BezTriples so that they are arranged in chronological order,
482  * as tools working on F-Curves expect that the BezTriples are in order.
483  */
484 void sort_time_fcurve (FCurve *fcu)
485 {
486         short ok= 1;
487         
488         /* keep adjusting order of beztriples until nothing moves (bubble-sort) */
489         while (ok) {
490                 ok= 0;
491                 
492                 /* currently, will only be needed when there are beztriples */
493                 if (fcu->bezt) {
494                         BezTriple *bezt;
495                         unsigned int a;
496                         
497                         /* loop over ALL points to adjust position in array and recalculate handles */
498                         for (a=0, bezt=fcu->bezt; a < fcu->totvert; a++, bezt++) {
499                                 /* check if thee's a next beztriple which we could try to swap with current */
500                                 if (a < (fcu->totvert-1)) {
501                                         /* swap if one is after the other (and indicate that order has changed) */
502                                         if (bezt->vec[1][0] > (bezt+1)->vec[1][0]) {
503                                                 SWAP(BezTriple, *bezt, *(bezt+1));
504                                                 ok= 1;
505                                         }
506                                         
507                                         /* if either one of both of the points exceeds crosses over the keyframe time... */
508                                         if ( (bezt->vec[0][0] > bezt->vec[1][0]) && (bezt->vec[2][0] < bezt->vec[1][0]) ) {
509                                                 /* swap handles if they have switched sides for some reason */
510                                                 SWAP(float, bezt->vec[0][0], bezt->vec[2][0]);
511                                                 SWAP(float, bezt->vec[0][1], bezt->vec[2][1]);
512                                         }
513                                         else {
514                                                 /* clamp handles */
515                                                 if (bezt->vec[0][0] > bezt->vec[1][0]) 
516                                                         bezt->vec[0][0]= bezt->vec[1][0];
517                                                 if (bezt->vec[2][0] < bezt->vec[1][0]) 
518                                                         bezt->vec[2][0]= bezt->vec[1][0];
519                                         }
520                                 }
521                         }
522                 }
523         }
524 }
525
526 /* This function tests if any BezTriples are out of order, thus requiring a sort */
527 short test_time_fcurve (FCurve *fcu)
528 {
529         unsigned int a;
530         
531         /* sanity checks */
532         if (fcu == NULL)
533                 return 0;
534         
535         /* currently, only need to test beztriples */
536         if (fcu->bezt) {
537                 BezTriple *bezt;
538                 
539                 /* loop through all BezTriples, stopping when one exceeds the one after it */
540                 for (a=0, bezt= fcu->bezt; a < (fcu->totvert - 1); a++, bezt++) {
541                         if (bezt->vec[1][0] > (bezt+1)->vec[1][0])
542                                 return 1;
543                 }
544         }
545         else if (fcu->fpt) {
546                 FPoint *fpt;
547                 
548                 /* loop through all FPoints, stopping when one exceeds the one after it */
549                 for (a=0, fpt= fcu->fpt; a < (fcu->totvert - 1); a++, fpt++) {
550                         if (fpt->vec[0] > (fpt+1)->vec[0])
551                                 return 1;
552                 }
553         }
554         
555         /* none need any swapping */
556         return 0;
557 }
558
559 /* ***************************** Drivers ********************************* */
560
561 /* Driver API --------------------------------- */
562
563 /* This frees the driver target itself */
564 void driver_free_target (ChannelDriver *driver, DriverTarget *dtar)
565 {
566         /* sanity checks */
567         if (dtar == NULL)
568                 return;
569                 
570         /* free target vars */
571         if (dtar->rna_path)
572                 MEM_freeN(dtar->rna_path);
573         
574         /* remove the target from the driver */
575         if (driver)
576                 BLI_freelinkN(&driver->targets, dtar);
577         else
578                 MEM_freeN(dtar);
579 }
580
581 /* Add a new driver target variable */
582 DriverTarget *driver_add_new_target (ChannelDriver *driver)
583 {
584         DriverTarget *dtar;
585         
586         /* sanity checks */
587         if (driver == NULL)
588                 return NULL;
589                 
590         /* make a new target */
591         dtar= MEM_callocN(sizeof(DriverTarget), "DriverTarget");
592         BLI_addtail(&driver->targets, dtar);
593         
594         /* give the target a 'unique' name */
595         strcpy(dtar->name, "var");
596         BLI_uniquename(&driver->targets, dtar, "var", '_', offsetof(DriverTarget, name), 64);
597         
598         /* return the target */
599         return dtar;
600 }
601
602 /* This frees the driver itself */
603 void fcurve_free_driver(FCurve *fcu)
604 {
605         ChannelDriver *driver;
606         DriverTarget *dtar, *dtarn;
607         
608         /* sanity checks */
609         if ELEM(NULL, fcu, fcu->driver)
610                 return;
611         driver= fcu->driver;
612         
613         /* free driver targets */
614         for (dtar= driver->targets.first; dtar; dtar= dtarn) {
615                 dtarn= dtar->next;
616                 driver_free_target(driver, dtar);
617         }
618         
619         /* free driver itself, then set F-Curve's point to this to NULL (as the curve may still be used) */
620         MEM_freeN(driver);
621         fcu->driver= NULL;
622 }
623
624 /* This makes a copy of the given driver */
625 ChannelDriver *fcurve_copy_driver (ChannelDriver *driver)
626 {
627         ChannelDriver *ndriver;
628         DriverTarget *dtar;
629         
630         /* sanity checks */
631         if (driver == NULL)
632                 return NULL;
633                 
634         /* copy all data */
635         ndriver= MEM_dupallocN(driver);
636         
637         /* copy targets */
638         ndriver->targets.first= ndriver->targets.last= NULL;
639         BLI_duplicatelist(&ndriver->targets, &driver->targets);
640         
641         for (dtar= ndriver->targets.first; dtar; dtar= dtar->next) {
642                 /* make a copy of target's rna path if available */
643                 if (dtar->rna_path)
644                         dtar->rna_path = MEM_dupallocN(dtar->rna_path);
645         }
646         
647         /* return the new driver */
648         return ndriver;
649 }
650
651 /* Driver Evaluation -------------------------- */
652
653 /* Helper function to obtain a value using RNA from the specified source (for evaluating drivers) */
654 float driver_get_target_value (ChannelDriver *driver, DriverTarget *dtar)
655 {
656         PointerRNA id_ptr, ptr;
657         PropertyRNA *prop;
658         ID *id;
659         char *path;
660         int index;
661         float value= 0.0f;
662         
663         /* sanity check */
664         if ELEM(NULL, driver, dtar)
665                 return 0.0f;
666         
667         /* get RNA-pointer for the ID-block given in target */
668         RNA_id_pointer_create(dtar->id, &id_ptr);
669         id= dtar->id;
670         path= dtar->rna_path;
671         index= dtar->array_index;
672         
673         /* error check for missing pointer... */
674         if (id == NULL) {
675                 printf("Error: driver doesn't have any valid target to use \n");
676                 if (G.f & G_DEBUG) printf("\tpath = %s [%d] \n", path, index);
677                 driver->flag |= DRIVER_FLAG_INVALID;
678                 return 0.0f;
679         }
680         
681         /* get property to read from, and get value as appropriate */
682         if (RNA_path_resolve(&id_ptr, path, &ptr, &prop)) {
683                 switch (RNA_property_type(prop)) {
684                         case PROP_BOOLEAN:
685                                 if (RNA_property_array_length(prop))
686                                         value= (float)RNA_property_boolean_get_index(&ptr, prop, index);
687                                 else
688                                         value= (float)RNA_property_boolean_get(&ptr, prop);
689                                 break;
690                         case PROP_INT:
691                                 if (RNA_property_array_length(prop))
692                                         value= (float)RNA_property_int_get_index(&ptr, prop, index);
693                                 else
694                                         value= (float)RNA_property_int_get(&ptr, prop);
695                                 break;
696                         case PROP_FLOAT:
697                                 if (RNA_property_array_length(prop))
698                                         value= RNA_property_float_get_index(&ptr, prop, index);
699                                 else
700                                         value= RNA_property_float_get(&ptr, prop);
701                                 break;
702                         case PROP_ENUM:
703                                 value= (float)RNA_property_enum_get(&ptr, prop);
704                                 break;
705                         default:
706                                 break;
707                 }
708         }
709         
710         return value;
711 }
712
713 /* Get two PoseChannels from the targets of the given Driver */
714 static void driver_get_target_pchans2 (ChannelDriver *driver, bPoseChannel **pchan1, bPoseChannel **pchan2)
715 {
716         DriverTarget *dtar;
717         short i = 0;
718         
719         /* before doing anything */
720         *pchan1= NULL;
721         *pchan2= NULL;
722         
723         /* only take the first two targets */
724         for (dtar= driver->targets.first; (dtar) && (i < 2); dtar=dtar->next, i++) {
725                 PointerRNA id_ptr, ptr;
726                 PropertyRNA *prop;
727                 
728                 /* get RNA-pointer for the ID-block given in target */
729                 if (dtar->id)
730                         RNA_id_pointer_create(dtar->id, &id_ptr);
731                 else
732                         continue;
733                 
734                 /* resolve path so that we have pointer to the right posechannel */
735                 if (RNA_path_resolve(&id_ptr, dtar->rna_path, &ptr, &prop)) {
736                         /* is pointer valid (i.e. pointing to an actual posechannel */
737                         if ((ptr.type == &RNA_PoseChannel) && (ptr.data)) {
738                                 /* first or second target? */
739                                 if (i)
740                                         *pchan1= ptr.data;
741                                 else
742                                         *pchan2= ptr.data;
743                         }
744                 }
745         }
746 }
747
748 /* Evaluate an Channel-Driver to get a 'time' value to use instead of "evaltime"
749  *      - "evaltime" is the frame at which F-Curve is being evaluated
750  *      - has to return a float value 
751  */
752 static float evaluate_driver (ChannelDriver *driver, float evaltime)
753 {
754         DriverTarget *dtar;
755         
756         /* check if driver can be evaluated */
757         if (driver->flag & DRIVER_FLAG_INVALID)
758                 return 0.0f;
759         
760         // TODO: the flags for individual targets need to be used too for more fine-grained support...
761         switch (driver->type) {
762                 case DRIVER_TYPE_AVERAGE: /* average values of driver targets */
763                 {
764                         /* check how many targets there are first (i.e. just one?) */
765                         if (driver->targets.first == driver->targets.last) {
766                                 /* just one target, so just use that */
767                                 dtar= driver->targets.first;
768                                 return driver_get_target_value(driver, dtar);
769                         }
770                         else {
771                                 /* more than one target, so average the values of the targets */
772                                 int tot = 0;
773                                 float value = 0.0f;
774                                 
775                                 /* loop through targets, adding (hopefully we don't get any overflow!) */
776                                 for (dtar= driver->targets.first; dtar; dtar=dtar->next) {
777                                         value += driver_get_target_value(driver, dtar); 
778                                         tot++;
779                                 }
780                                 
781                                 /* return the average of these */
782                                 return (value / (float)tot);
783                         }
784                 }
785                         break;
786                 
787                 case DRIVER_TYPE_PYTHON: /* expression */
788                 {
789 #ifndef DISABLE_PYTHON
790                         /* check for empty or invalid expression */
791                         if ( (driver->expression[0] == '\0') ||
792                                  (driver->flag & DRIVER_FLAG_INVALID) )
793                         {
794                                 return 0.0f;
795                         }
796                         
797                         /* this evaluates the expression using Python,and returns its result:
798                          *      - on errors it reports, then returns 0.0f
799                          */
800                         return BPY_pydriver_eval(driver);
801 #endif /* DISABLE_PYTHON*/
802                 }
803                         break;
804
805                 
806                 case DRIVER_TYPE_ROTDIFF: /* difference of rotations of 2 bones (should ideally be in same armature) */
807                 {
808                         bPoseChannel *pchan, *pchan2;
809                         float q1[4], q2[4], quat[4], angle;
810                         
811                         /* get pose channels, and check if we've got two */
812                         driver_get_target_pchans2(driver, &pchan, &pchan2);
813                         if (ELEM(NULL, pchan, pchan2)) {
814                                 /* disable this driver, since it doesn't work correctly... */
815                                 driver->flag |= DRIVER_FLAG_INVALID;
816                                 
817                                 /* check what the error was */
818                                 if ((pchan == NULL) && (pchan2 == NULL))
819                                         printf("Driver Evaluation Error: Rotational difference failed - first 2 targets invalid \n");
820                                 else if (pchan == NULL)
821                                         printf("Driver Evaluation Error: Rotational difference failed - first target not valid PoseChannel \n");
822                                 else if (pchan2 == NULL)
823                                         printf("Driver Evaluation Error: Rotational difference failed - second target not valid PoseChannel \n");
824                                         
825                                 /* stop here... */
826                                 return 0.0f;
827                         }                       
828                         
829                         /* use the final posed locations */
830                         Mat4ToQuat(pchan->pose_mat, q1);
831                         Mat4ToQuat(pchan2->pose_mat, q2);
832                         
833                         QuatInv(q1);
834                         QuatMul(quat, q1, q2);
835                         angle = 2.0f * (saacos(quat[0]));
836                         angle= ABS(angle);
837                         
838                         return (angle > M_PI) ? (float)((2.0f * M_PI) - angle) : (float)(angle);
839                 }
840                         break;
841                 
842                 default:
843                 {
844                         /* special 'hack' - just use stored value 
845                          *      This is currently used as the mechanism which allows animated settings to be able
846                          *      to be changed via the UI.
847                          */
848                         return driver->curval;
849                 }
850         }
851         
852         /* return 0.0f, as couldn't find relevant data to use */
853         return 0.0f;
854 }
855
856 /* ***************************** Curve Calculations ********************************* */
857
858 /* The total length of the handles is not allowed to be more
859  * than the horizontal distance between (v1-v4).
860  * This is to prevent curve loops.
861 */
862 void correct_bezpart (float *v1, float *v2, float *v3, float *v4)
863 {
864         float h1[2], h2[2], len1, len2, len, fac;
865         
866         /* calculate handle deltas */
867         h1[0]= v1[0] - v2[0];
868         h1[1]= v1[1] - v2[1];
869         
870         h2[0]= v4[0] - v3[0];
871         h2[1]= v4[1] - v3[1];
872         
873         /* calculate distances: 
874          *      - len   = span of time between keyframes 
875          *      - len1  = length of handle of start key
876          *      - len2  = length of handle of end key
877          */
878         len= v4[0]- v1[0];
879         len1= (float)fabs(h1[0]);
880         len2= (float)fabs(h2[0]);
881         
882         /* if the handles have no length, no need to do any corrections */
883         if ((len1+len2) == 0.0f) 
884                 return;
885                 
886         /* the two handles cross over each other, so force them
887          * apart using the proportion they overlap 
888          */
889         if ((len1+len2) > len) {
890                 fac= len / (len1+len2);
891                 
892                 v2[0]= (v1[0] - fac*h1[0]);
893                 v2[1]= (v1[1] - fac*h1[1]);
894                 
895                 v3[0]= (v4[0] - fac*h2[0]);
896                 v3[1]= (v4[1] - fac*h2[1]);
897         }
898 }
899
900 /* find root ('zero') */
901 int findzero (float x, float q0, float q1, float q2, float q3, float *o)
902 {
903         double c0, c1, c2, c3, a, b, c, p, q, d, t, phi;
904         int nr= 0;
905
906         c0= q0 - x;
907         c1= 3.0 * (q1 - q0);
908         c2= 3.0 * (q0 - 2.0*q1 + q2);
909         c3= q3 - q0 + 3.0 * (q1 - q2);
910         
911         if (c3 != 0.0) {
912                 a= c2/c3;
913                 b= c1/c3;
914                 c= c0/c3;
915                 a= a/3;
916                 
917                 p= b/3 - a*a;
918                 q= (2*a*a*a - a*b + c) / 2;
919                 d= q*q + p*p*p;
920                 
921                 if (d > 0.0) {
922                         t= sqrt(d);
923                         o[0]= (float)(Sqrt3d(-q+t) + Sqrt3d(-q-t) - a);
924                         
925                         if ((o[0] >= SMALL) && (o[0] <= 1.000001)) return 1;
926                         else return 0;
927                 }
928                 else if (d == 0.0) {
929                         t= Sqrt3d(-q);
930                         o[0]= (float)(2*t - a);
931                         
932                         if ((o[0] >= SMALL) && (o[0] <= 1.000001)) nr++;
933                         o[nr]= (float)(-t-a);
934                         
935                         if ((o[nr] >= SMALL) && (o[nr] <= 1.000001)) return nr+1;
936                         else return nr;
937                 }
938                 else {
939                         phi= acos(-q / sqrt(-(p*p*p)));
940                         t= sqrt(-p);
941                         p= cos(phi/3);
942                         q= sqrt(3 - 3*p*p);
943                         o[0]= (float)(2*t*p - a);
944                         
945                         if ((o[0] >= SMALL) && (o[0] <= 1.000001)) nr++;
946                         o[nr]= (float)(-t * (p + q) - a);
947                         
948                         if ((o[nr] >= SMALL) && (o[nr] <= 1.000001)) nr++;
949                         o[nr]= (float)(-t * (p - q) - a);
950                         
951                         if ((o[nr] >= SMALL) && (o[nr] <= 1.000001)) return nr+1;
952                         else return nr;
953                 }
954         }
955         else {
956                 a=c2;
957                 b=c1;
958                 c=c0;
959                 
960                 if (a != 0.0) {
961                         // discriminant
962                         p= b*b - 4*a*c;
963                         
964                         if (p > 0) {
965                                 p= sqrt(p);
966                                 o[0]= (float)((-b-p) / (2 * a));
967                                 
968                                 if ((o[0] >= SMALL) && (o[0] <= 1.000001)) nr++;
969                                 o[nr]= (float)((-b+p)/(2*a));
970                                 
971                                 if ((o[nr] >= SMALL) && (o[nr] <= 1.000001)) return nr+1;
972                                 else return nr;
973                         }
974                         else if (p == 0) {
975                                 o[0]= (float)(-b / (2 * a));
976                                 if ((o[0] >= SMALL) && (o[0] <= 1.000001)) return 1;
977                                 else return 0;
978                         }
979                 }
980                 else if (b != 0.0) {
981                         o[0]= (float)(-c/b);
982                         
983                         if ((o[0] >= SMALL) && (o[0] <= 1.000001)) return 1;
984                         else return 0;
985                 }
986                 else if (c == 0.0) {
987                         o[0]= 0.0;
988                         return 1;
989                 }
990                 
991                 return 0;       
992         }
993 }
994
995 void berekeny (float f1, float f2, float f3, float f4, float *o, int b)
996 {
997         float t, c0, c1, c2, c3;
998         int a;
999
1000         c0= f1;
1001         c1= 3.0f * (f2 - f1);
1002         c2= 3.0f * (f1 - 2.0f*f2 + f3);
1003         c3= f4 - f1 + 3.0f * (f2 - f3);
1004         
1005         for (a=0; a < b; a++) {
1006                 t= o[a];
1007                 o[a]= c0 + t*c1 + t*t*c2 + t*t*t*c3;
1008         }
1009 }
1010
1011 void berekenx (float *f, float *o, int b)
1012 {
1013         float t, c0, c1, c2, c3;
1014         int a;
1015
1016         c0= f[0];
1017         c1= 3.0f * (f[3] - f[0]);
1018         c2= 3.0f * (f[0] - 2.0f*f[3] + f[6]);
1019         c3= f[9] - f[0] + 3.0f * (f[3] - f[6]);
1020         
1021         for (a=0; a < b; a++) {
1022                 t= o[a];
1023                 o[a]= c0 + t*c1 + t*t*c2 + t*t*t*c3;
1024         }
1025 }
1026
1027
1028 /* -------------------------- */
1029
1030 /* Calculate F-Curve value for 'evaltime' using BezTriple keyframes */
1031 static float fcurve_eval_keyframes (FCurve *fcu, BezTriple *bezts, float evaltime)
1032 {
1033         BezTriple *bezt, *prevbezt, *lastbezt;
1034         float v1[2], v2[2], v3[2], v4[2], opl[32], dx, fac;
1035         unsigned int a;
1036         int b;
1037         float cvalue = 0.0f;
1038         
1039         /* get pointers */
1040         a= fcu->totvert-1;
1041         prevbezt= bezts;
1042         bezt= prevbezt+1;
1043         lastbezt= prevbezt + a;
1044         
1045         /* evaluation time at or past endpoints? */
1046         if (prevbezt->vec[1][0] >= evaltime) {
1047                 /* before or on first keyframe */
1048                 if ((fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (prevbezt->ipo != BEZT_IPO_CONST)) {
1049                         /* linear or bezier interpolation */
1050                         if (prevbezt->ipo==BEZT_IPO_LIN) {
1051                                 /* Use the next center point instead of our own handle for
1052                                  * linear interpolated extrapolate 
1053                                  */
1054                                 if (fcu->totvert == 1) 
1055                                         cvalue= prevbezt->vec[1][1];
1056                                 else {
1057                                         bezt = prevbezt+1;
1058                                         dx= prevbezt->vec[1][0] - evaltime;
1059                                         fac= bezt->vec[1][0] - prevbezt->vec[1][0];
1060                                         
1061                                         /* prevent division by zero */
1062                                         if (fac) {
1063                                                 fac= (bezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
1064                                                 cvalue= prevbezt->vec[1][1] - (fac * dx);
1065                                         }
1066                                         else 
1067                                                 cvalue= prevbezt->vec[1][1];
1068                                 }
1069                         } 
1070                         else {
1071                                 /* Use the first handle (earlier) of first BezTriple to calculate the
1072                                  * gradient and thus the value of the curve at evaltime
1073                                  */
1074                                 dx= prevbezt->vec[1][0] - evaltime;
1075                                 fac= prevbezt->vec[1][0] - prevbezt->vec[0][0];
1076                                 
1077                                 /* prevent division by zero */
1078                                 if (fac) {
1079                                         fac= (prevbezt->vec[1][1] - prevbezt->vec[0][1]) / fac;
1080                                         cvalue= prevbezt->vec[1][1] - (fac * dx);
1081                                 }
1082                                 else 
1083                                         cvalue= prevbezt->vec[1][1];
1084                         }
1085                 }
1086                 else {
1087                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation, 
1088                          * so just extend first keyframe's value 
1089                          */
1090                         cvalue= prevbezt->vec[1][1];
1091                 }
1092         }
1093         else if (lastbezt->vec[1][0] <= evaltime) {
1094                 /* after or on last keyframe */
1095                 if ((fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (lastbezt->ipo != BEZT_IPO_CONST)) {
1096                         /* linear or bezier interpolation */
1097                         if (lastbezt->ipo==BEZT_IPO_LIN) {
1098                                 /* Use the next center point instead of our own handle for
1099                                  * linear interpolated extrapolate 
1100                                  */
1101                                 if (fcu->totvert == 1) 
1102                                         cvalue= lastbezt->vec[1][1];
1103                                 else {
1104                                         prevbezt = lastbezt - 1;
1105                                         dx= evaltime - lastbezt->vec[1][0];
1106                                         fac= lastbezt->vec[1][0] - prevbezt->vec[1][0];
1107                                         
1108                                         /* prevent division by zero */
1109                                         if (fac) {
1110                                                 fac= (lastbezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
1111                                                 cvalue= lastbezt->vec[1][1] + (fac * dx);
1112                                         }
1113                                         else 
1114                                                 cvalue= lastbezt->vec[1][1];
1115                                 }
1116                         } 
1117                         else {
1118                                 /* Use the gradient of the second handle (later) of last BezTriple to calculate the
1119                                  * gradient and thus the value of the curve at evaltime
1120                                  */
1121                                 dx= evaltime - lastbezt->vec[1][0];
1122                                 fac= lastbezt->vec[2][0] - lastbezt->vec[1][0];
1123                                 
1124                                 /* prevent division by zero */
1125                                 if (fac) {
1126                                         fac= (lastbezt->vec[2][1] - lastbezt->vec[1][1]) / fac;
1127                                         cvalue= lastbezt->vec[1][1] + (fac * dx);
1128                                 }
1129                                 else 
1130                                         cvalue= lastbezt->vec[1][1];
1131                         }
1132                 }
1133                 else {
1134                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation, 
1135                          * so just extend last keyframe's value 
1136                          */
1137                         cvalue= lastbezt->vec[1][1];
1138                 }
1139         }
1140         else {
1141                 /* evaltime occurs somewhere in the middle of the curve */
1142                 for (a=0; prevbezt && bezt && (a < fcu->totvert-1); a++, prevbezt=bezt, bezt++) {  
1143                         /* evaltime occurs within the interval defined by these two keyframes */
1144                         if ((prevbezt->vec[1][0] <= evaltime) && (bezt->vec[1][0] >= evaltime)) {
1145                                 /* value depends on interpolation mode */
1146                                 if (prevbezt->ipo == BEZT_IPO_CONST) {
1147                                         /* constant (evaltime not relevant, so no interpolation needed) */
1148                                         cvalue= prevbezt->vec[1][1];
1149                                 }
1150                                 else if (prevbezt->ipo == BEZT_IPO_LIN) {
1151                                         /* linear - interpolate between values of the two keyframes */
1152                                         fac= bezt->vec[1][0] - prevbezt->vec[1][0];
1153                                         
1154                                         /* prevent division by zero */
1155                                         if (fac) {
1156                                                 fac= (evaltime - prevbezt->vec[1][0]) / fac;
1157                                                 cvalue= prevbezt->vec[1][1] + (fac * (bezt->vec[1][1] - prevbezt->vec[1][1]));
1158                                         }
1159                                         else
1160                                                 cvalue= prevbezt->vec[1][1];
1161                                 }
1162                                 else {
1163                                         /* bezier interpolation */
1164                                                 /* v1,v2 are the first keyframe and its 2nd handle */
1165                                         v1[0]= prevbezt->vec[1][0];
1166                                         v1[1]= prevbezt->vec[1][1];
1167                                         v2[0]= prevbezt->vec[2][0];
1168                                         v2[1]= prevbezt->vec[2][1];
1169                                                 /* v3,v4 are the last keyframe's 1st handle + the last keyframe */
1170                                         v3[0]= bezt->vec[0][0];
1171                                         v3[1]= bezt->vec[0][1];
1172                                         v4[0]= bezt->vec[1][0];
1173                                         v4[1]= bezt->vec[1][1];
1174                                         
1175                                         /* adjust handles so that they don't overlap (forming a loop) */
1176                                         correct_bezpart(v1, v2, v3, v4);
1177                                         
1178                                         /* try to get a value for this position - if failure, try another set of points */
1179                                         b= findzero(evaltime, v1[0], v2[0], v3[0], v4[0], opl);
1180                                         if (b) {
1181                                                 berekeny(v1[1], v2[1], v3[1], v4[1], opl, 1);
1182                                                 cvalue= opl[0];
1183                                                 break;
1184                                         }
1185                                 }
1186                         }
1187                 }
1188         }
1189         
1190         /* return value */
1191         return cvalue;
1192 }
1193
1194 /* Calculate F-Curve value for 'evaltime' using FPoint samples */
1195 static float fcurve_eval_samples (FCurve *fcu, FPoint *fpts, float evaltime)
1196 {
1197         FPoint *prevfpt, *lastfpt, *fpt;
1198         float cvalue= 0.0f;
1199         
1200         /* get pointers */
1201         prevfpt= fpts;
1202         lastfpt= prevfpt + fcu->totvert-1;
1203         
1204         /* evaluation time at or past endpoints? */
1205         if (prevfpt->vec[0] >= evaltime) {
1206                 /* before or on first sample, so just extend value */
1207                 cvalue= prevfpt->vec[1];
1208         }
1209         else if (lastfpt->vec[0] <= evaltime) {
1210                 /* after or on last sample, so just extend value */
1211                 cvalue= lastfpt->vec[1];
1212         }
1213         else {
1214                 /* find the one on the right frame (assume that these are spaced on 1-frame intervals) */
1215                 fpt= prevfpt + (int)(evaltime - prevfpt->vec[0]);
1216                 cvalue= fpt->vec[1];
1217         }
1218         
1219         /* return value */
1220         return cvalue;
1221 }
1222
1223 /* ******************************** F-Curve Modifiers ********************************* */
1224
1225 /* Template --------------------------- */
1226
1227 /* Each modifier defines a set of functions, which will be called at the appropriate
1228  * times. In addition to this, each modifier should have a type-info struct, where
1229  * its functions are attached for use. 
1230  */
1231  
1232 /* Template for type-info data:
1233  *      - make a copy of this when creating new modifiers, and just change the functions
1234  *        pointed to as necessary
1235  *      - although the naming of functions doesn't matter, it would help for code
1236  *        readability, to follow the same naming convention as is presented here
1237  *      - any functions that a constraint doesn't need to define, don't define
1238  *        for such cases, just use NULL 
1239  *      - these should be defined after all the functions have been defined, so that
1240  *        forward-definitions/prototypes don't need to be used!
1241  *      - keep this copy #if-def'd so that future constraints can get based off this
1242  */
1243 #if 0
1244 static FModifierTypeInfo FMI_MODNAME = {
1245         FMODIFIER_TYPE_MODNAME, /* type */
1246         sizeof(FMod_ModName), /* size */
1247         FMI_TYPE_SOME_ACTION, /* action type */
1248         FMI_REQUIRES_SOME_REQUIREMENT, /* requirements */
1249         "Modifier Name", /* name */
1250         "FMod_ModName", /* struct name */
1251         fcm_modname_free, /* free data */
1252         fcm_modname_relink, /* relink data */
1253         fcm_modname_copy, /* copy data */
1254         fcm_modname_new_data, /* new data */
1255         fcm_modname_verify, /* verify */
1256         fcm_modname_time, /* evaluate time */
1257         fcm_modname_evaluate /* evaluate */
1258 };
1259 #endif
1260
1261 /* Generator F-Curve Modifier --------------------------- */
1262
1263 /* Generators available:
1264  *      1) simple polynomial generator:
1265  *              - Exanded form - (y = C[0]*(x^(n)) + C[1]*(x^(n-1)) + ... + C[n])  
1266  *              - Factorised form - (y = (C[0][0]*x + C[0][1]) * (C[1][0]*x + C[1][1]) * ... * (C[n][0]*x + C[n][1]))
1267  *      2) simple builin 'functions':
1268  *              of the form (y = C[0] * fn( C[1]*x + C[2] ) + C[3])
1269  *         where fn() can be any one of:
1270  *              sin, cos, tan, ln, sqrt
1271  *      3) expression...
1272  */
1273
1274 static void fcm_generator_free (FModifier *fcm)
1275 {
1276         FMod_Generator *data= (FMod_Generator *)fcm->data;
1277         
1278         /* free polynomial coefficients array */
1279         if (data->coefficients)
1280                 MEM_freeN(data->coefficients);
1281 }
1282
1283 static void fcm_generator_copy (FModifier *fcm, FModifier *src)
1284 {
1285         FMod_Generator *gen= (FMod_Generator *)fcm->data;
1286         FMod_Generator *ogen= (FMod_Generator *)src->data;
1287         
1288         /* copy coefficients array? */
1289         if (ogen->coefficients)
1290                 gen->coefficients= MEM_dupallocN(ogen->coefficients);
1291 }
1292
1293 static void fcm_generator_new_data (void *mdata)
1294 {
1295         FMod_Generator *data= (FMod_Generator *)mdata;
1296         float *cp;
1297         
1298         /* set default generator to be linear 0-1 (gradient = 1, y-offset = 0) */
1299         data->poly_order= 1;
1300         data->arraysize= 2;
1301         cp= data->coefficients= MEM_callocN(sizeof(float)*2, "FMod_Generator_Coefs");
1302         cp[0] = 0; // y-offset 
1303         cp[1] = 1; // gradient
1304 }
1305
1306 static void fcm_generator_verify (FModifier *fcm)
1307 {
1308         FMod_Generator *data= (FMod_Generator *)fcm->data;
1309         
1310         /* requirements depend on mode */
1311         switch (data->mode) {
1312                 case FCM_GENERATOR_POLYNOMIAL: /* expanded polynomial expression */
1313                 {
1314                         /* arraysize needs to be order+1, so resize if not */
1315                         if (data->arraysize != (data->poly_order+1)) {
1316                                 float *nc;
1317                                 
1318                                 /* make new coefficients array, and copy over as much data as can fit */
1319                                 nc= MEM_callocN(sizeof(float)*(data->poly_order+1), "FMod_Generator_Coefs");
1320                                 
1321                                 if (data->coefficients) {
1322                                         if (data->arraysize > (data->poly_order+1))
1323                                                 memcpy(nc, data->coefficients, sizeof(float)*(data->poly_order+1));
1324                                         else
1325                                                 memcpy(nc, data->coefficients, sizeof(float)*data->arraysize);
1326                                                 
1327                                         /* free the old data */
1328                                         MEM_freeN(data->coefficients);
1329                                 }       
1330                                 
1331                                 /* set the new data */
1332                                 data->coefficients= nc;
1333                                 data->arraysize= data->poly_order+1;
1334                         }
1335                 }
1336                         break;
1337                 
1338                 case FCM_GENERATOR_POLYNOMIAL_FACTORISED: /* expanded polynomial expression */
1339                 {
1340                         /* arraysize needs to be 2*order, so resize if not */
1341                         if (data->arraysize != (data->poly_order * 2)) {
1342                                 float *nc;
1343                                 
1344                                 /* make new coefficients array, and copy over as much data as can fit */
1345                                 nc= MEM_callocN(sizeof(float)*(data->poly_order*2), "FMod_Generator_Coefs");
1346                                 
1347                                 if (data->coefficients) {
1348                                         if (data->arraysize > (data->poly_order * 2))
1349                                                 memcpy(nc, data->coefficients, sizeof(float)*(data->poly_order * 2));
1350                                         else
1351                                                 memcpy(nc, data->coefficients, sizeof(float)*data->arraysize);
1352                                                 
1353                                         /* free the old data */
1354                                         MEM_freeN(data->coefficients);
1355                                 }       
1356                                 
1357                                 /* set the new data */
1358                                 data->coefficients= nc;
1359                                 data->arraysize= data->poly_order * 2;
1360                         }
1361                 }
1362                         break;
1363                         
1364                 case FCM_GENERATOR_FUNCTION: /* builtin function */
1365                 {
1366                         /* arraysize needs to be 4*/
1367                         if (data->arraysize != 4) {
1368                                 float *nc;
1369                                 
1370                                 /* free the old data */
1371                                 if (data->coefficients)
1372                                         MEM_freeN(data->coefficients);
1373                                 
1374                                 /* make new coefficients array, and init using default values */
1375                                 nc= data->coefficients= MEM_callocN(sizeof(float)*4, "FMod_Generator_Coefs");
1376                                 data->arraysize= 4;
1377                                 
1378                                 nc[0]= 1.0f;
1379                                 nc[1]= 1.0f;
1380                                 nc[2]= 0.0f;
1381                                 nc[3]= 0.0f;
1382                         }
1383                 }
1384                         break;  
1385         }
1386 }
1387
1388 static void fcm_generator_evaluate (FCurve *fcu, FModifier *fcm, float *cvalue, float evaltime)
1389 {
1390         FMod_Generator *data= (FMod_Generator *)fcm->data;
1391         
1392         /* behaviour depends on mode 
1393          * NOTE: the data in its default state is fine too
1394          */
1395         switch (data->mode) {
1396                 case FCM_GENERATOR_POLYNOMIAL: /* expanded polynomial expression */
1397                 {
1398                         /* we overwrite cvalue with the sum of the polynomial */
1399                         float *powers = MEM_callocN(sizeof(float)*data->arraysize, "Poly Powers");
1400                         float value= 0.0f;
1401                         unsigned int i;
1402                         
1403                         /* for each x^n, precalculate value based on previous one first... this should be 
1404                          * faster that calling pow() for each entry
1405                          */
1406                         for (i=0; i < data->arraysize; i++) {
1407                                 /* first entry is x^0 = 1, otherwise, calculate based on previous */
1408                                 if (i)
1409                                         powers[i]= powers[i-1] * evaltime;
1410                                 else
1411                                         powers[0]= 1;
1412                         }
1413                         
1414                         /* for each coefficient, add to value, which we'll write to *cvalue in one go */
1415                         for (i=0; i < data->arraysize; i++)
1416                                 value += data->coefficients[i] * powers[i];
1417                         
1418                         /* only if something changed, write *cvalue in one go */
1419                         if (data->poly_order) {
1420                                 if (data->flag & FCM_GENERATOR_ADDITIVE)
1421                                         *cvalue += value;
1422                                 else
1423                                         *cvalue= value;
1424                         }
1425                                 
1426                         /* cleanup */
1427                         if (powers) 
1428                                 MEM_freeN(powers);
1429                 }
1430                         break;
1431                         
1432                 case FCM_GENERATOR_POLYNOMIAL_FACTORISED: /* factorised polynomial */
1433                 {
1434                         float value= 1.0f, *cp=NULL;
1435                         unsigned int i;
1436                         
1437                         /* for each coefficient pair, solve for that bracket before accumulating in value by multiplying */
1438                         for (cp=data->coefficients, i=0; (cp) && (i < data->poly_order); cp+=2, i++) 
1439                                 value *= (cp[0]*evaltime + cp[1]);
1440                                 
1441                         /* only if something changed, write *cvalue in one go */
1442                         if (data->poly_order) {
1443                                 if (data->flag & FCM_GENERATOR_ADDITIVE)
1444                                         *cvalue += value;
1445                                 else
1446                                         *cvalue= value;
1447                         }
1448                 }
1449                         break;
1450                         
1451                 case FCM_GENERATOR_FUNCTION: /* builtin function */
1452                 {
1453                         double arg= data->coefficients[1]*evaltime + data->coefficients[2];
1454                         double (*fn)(double v) = NULL;
1455                         
1456                         /* get function pointer to the func to use:
1457                          * WARNING: must perform special argument validation hereto guard against crashes  
1458                          */
1459                         switch (data->func_type)
1460                         {
1461                                 /* simple ones */                       
1462                                 case FCM_GENERATOR_FN_SIN: /* sine wave */
1463                                         fn= sin;
1464                                         break;
1465                                 case FCM_GENERATOR_FN_COS: /* cosine wave */
1466                                         fn= cos;
1467                                         break;
1468                                         
1469                                 /* validation required */
1470                                 case FCM_GENERATOR_FN_TAN: /* tangent wave */
1471                                 {
1472                                         /* check that argument is not on one of the discontinuities (i.e. 90deg, 270 deg, etc) */
1473                                         if IS_EQ(fmod((arg - M_PI_2), M_PI), 0.0) {
1474                                                 if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0)
1475                                                         *cvalue = 0.0f; /* no value possible here */
1476                                         }
1477                                         else
1478                                                 fn= tan;
1479                                 }
1480                                         break;
1481                                 case FCM_GENERATOR_FN_LN: /* natural log */
1482                                 {
1483                                         /* check that value is greater than 1? */
1484                                         if (arg > 1.0f) {
1485                                                 fn= log;
1486                                         }
1487                                         else {
1488                                                 if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0)
1489                                                         *cvalue = 0.0f; /* no value possible here */
1490                                         }
1491                                 }
1492                                         break;
1493                                 case FCM_GENERATOR_FN_SQRT: /* square root */
1494                                 {
1495                                         /* no negative numbers */
1496                                         if (arg > 0.0f) {
1497                                                 fn= sqrt;
1498                                         }
1499                                         else {
1500                                                 if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0)
1501                                                         *cvalue = 0.0f; /* no value possible here */
1502                                         }
1503                                 }
1504                                         break;
1505                                         
1506                                 default:
1507                                         printf("Invalid Function-Generator for F-Modifier - %d \n", data->func_type);
1508                         }
1509                         
1510                         /* execute function callback to set value if appropriate */
1511                         if (fn) {
1512                                 float value= (float)(data->coefficients[0]*fn(arg) + data->coefficients[3]);
1513                                 
1514                                 if (data->flag & FCM_GENERATOR_ADDITIVE)
1515                                         *cvalue += value;
1516                                 else
1517                                         *cvalue= value;
1518                         }
1519                 }
1520                         break;
1521
1522 #ifndef DISABLE_PYTHON
1523                 case FCM_GENERATOR_EXPRESSION: /* py-expression */
1524                         // TODO...
1525                         break;
1526 #endif /* DISABLE_PYTHON */
1527         }
1528 }
1529
1530 static FModifierTypeInfo FMI_GENERATOR = {
1531         FMODIFIER_TYPE_GENERATOR, /* type */
1532         sizeof(FMod_Generator), /* size */
1533         FMI_TYPE_GENERATE_CURVE, /* action type */
1534         FMI_REQUIRES_NOTHING, /* requirements */
1535         "Generator", /* name */
1536         "FMod_Generator", /* struct name */
1537         fcm_generator_free, /* free data */
1538         fcm_generator_copy, /* copy data */
1539         fcm_generator_new_data, /* new data */
1540         fcm_generator_verify, /* verify */
1541         NULL, /* evaluate time */
1542         fcm_generator_evaluate /* evaluate */
1543 };
1544
1545 /* Envelope F-Curve Modifier --------------------------- */
1546
1547 static void fcm_envelope_free (FModifier *fcm)
1548 {
1549         FMod_Envelope *env= (FMod_Envelope *)fcm->data;
1550         
1551         /* free envelope data array */
1552         if (env->data)
1553                 MEM_freeN(env->data);
1554 }
1555
1556 static void fcm_envelope_copy (FModifier *fcm, FModifier *src)
1557 {
1558         FMod_Envelope *env= (FMod_Envelope *)fcm->data;
1559         FMod_Envelope *oenv= (FMod_Envelope *)src->data;
1560         
1561         /* copy envelope data array */
1562         if (oenv->data)
1563                 env->data= MEM_dupallocN(oenv->data);
1564 }
1565
1566 static void fcm_envelope_new_data (void *mdata)
1567 {
1568         FMod_Envelope *env= (FMod_Envelope *)mdata;
1569         
1570         /* set default min/max ranges */
1571         env->min= -1.0f;
1572         env->max= 1.0f;
1573 }
1574
1575 static void fcm_envelope_verify (FModifier *fcm)
1576 {
1577         FMod_Envelope *env= (FMod_Envelope *)fcm->data;
1578         
1579         /* if the are points, perform bubble-sort on them, as user may have changed the order */
1580         if (env->data) {
1581                 // XXX todo...
1582         }
1583 }
1584
1585 static void fcm_envelope_evaluate (FCurve *fcu, FModifier *fcm, float *cvalue, float evaltime)
1586 {
1587         FMod_Envelope *env= (FMod_Envelope *)fcm->data;
1588         FCM_EnvelopeData *fed, *prevfed, *lastfed;
1589         float min=0.0f, max=0.0f, fac=0.0f;
1590         int a;
1591         
1592         /* get pointers */
1593         if (env->data == NULL) return;
1594         prevfed= env->data;
1595         fed= prevfed + 1;
1596         lastfed= prevfed + (env->totvert-1);
1597         
1598         /* get min/max values for envelope at evaluation time (relative to mid-value) */
1599         if (prevfed->time >= evaltime) {
1600                 /* before or on first sample, so just extend value */
1601                 min= prevfed->min;
1602                 max= prevfed->max;
1603         }
1604         else if (lastfed->time <= evaltime) {
1605                 /* after or on last sample, so just extend value */
1606                 min= lastfed->min;
1607                 max= lastfed->max;
1608         }
1609         else {
1610                 /* evaltime occurs somewhere between segments */
1611                 // TODO: implement binary search for this to make it faster?
1612                 for (a=0; prevfed && fed && (a < env->totvert-1); a++, prevfed=fed, fed++) {  
1613                         /* evaltime occurs within the interval defined by these two envelope points */
1614                         if ((prevfed->time <= evaltime) && (fed->time >= evaltime)) {
1615                                 float afac, bfac, diff;
1616                                 
1617                                 diff= fed->time - prevfed->time;
1618                                 afac= (evaltime - prevfed->time) / diff;
1619                                 bfac= (fed->time - evaltime) / diff;
1620                                 
1621                                 min= bfac*prevfed->min + afac*fed->min;
1622                                 max= bfac*prevfed->max + afac*fed->max;
1623                                 
1624                                 break;
1625                         }
1626                 }
1627         }
1628         
1629         /* adjust *cvalue 
1630          *      - fac is the ratio of how the current y-value corresponds to the reference range
1631          *      - thus, the new value is found by mapping the old range to the new!
1632          */
1633         fac= (*cvalue - (env->midval + env->min)) / (env->max - env->min);
1634         *cvalue= min + fac*(max - min); 
1635 }
1636
1637 static FModifierTypeInfo FMI_ENVELOPE = {
1638         FMODIFIER_TYPE_ENVELOPE, /* type */
1639         sizeof(FMod_Envelope), /* size */
1640         FMI_TYPE_REPLACE_VALUES, /* action type */
1641         0, /* requirements */
1642         "Envelope", /* name */
1643         "FMod_Envelope", /* struct name */
1644         fcm_envelope_free, /* free data */
1645         fcm_envelope_copy, /* copy data */
1646         fcm_envelope_new_data, /* new data */
1647         fcm_envelope_verify, /* verify */
1648         NULL, /* evaluate time */
1649         fcm_envelope_evaluate /* evaluate */
1650 };
1651
1652 /* Cycles F-Curve Modifier  --------------------------- */
1653
1654 /* This modifier changes evaltime to something that exists within the curve's frame-range, 
1655  * then re-evaluates modifier stack up to this point using the new time. This re-entrant behaviour
1656  * is very likely to be more time-consuming than the original approach... (which was tighly integrated into 
1657  * the calculation code...).
1658  *
1659  * 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
1660  * Possible TODO - store length of cycle information that can be initialised from the extents of the keyframes/sample-data, and adjusted
1661  *                              as appropriate
1662  */
1663
1664 /* temp data used during evaluation */
1665 typedef struct tFCMED_Cycles {
1666         float cycyofs;          /* y-offset to apply */
1667 } tFCMED_Cycles;
1668  
1669 static void fcm_cycles_new_data (void *mdata)
1670 {
1671         FMod_Cycles *data= (FMod_Cycles *)mdata;
1672         
1673         /* turn on cycles by default */
1674         data->before_mode= data->after_mode= FCM_EXTRAPOLATE_CYCLIC;
1675 }
1676
1677 static float fcm_cycles_time (FCurve *fcu, FModifier *fcm, float cvalue, float evaltime)
1678 {
1679         FMod_Cycles *data= (FMod_Cycles *)fcm->data;
1680         float prevkey[2], lastkey[2], cycyofs=0.0f;
1681         short side=0, mode=0;
1682         int cycles=0;
1683         
1684         /* check if modifier is first in stack, otherwise disable ourself... */
1685         // FIXME...
1686         if (fcm->prev) {
1687                 fcm->flag |= FMODIFIER_FLAG_DISABLED;
1688                 return evaltime;
1689         }
1690         
1691         /* calculate new evaltime due to cyclic interpolation */
1692         if (fcu && fcu->bezt) {
1693                 BezTriple *prevbezt= fcu->bezt;
1694                 BezTriple *lastbezt= prevbezt + fcu->totvert-1;
1695                 
1696                 prevkey[0]= prevbezt->vec[1][0];
1697                 prevkey[1]= prevbezt->vec[1][1];
1698                 
1699                 lastkey[0]= lastbezt->vec[1][0];
1700                 lastkey[1]= lastbezt->vec[1][1];
1701         }
1702         else if (fcu && fcu->fpt) {
1703                 FPoint *prevfpt= fcu->fpt;
1704                 FPoint *lastfpt= prevfpt + fcu->totvert-1;
1705                 
1706                 prevkey[0]= prevfpt->vec[0];
1707                 prevkey[1]= prevfpt->vec[1];
1708                 
1709                 lastkey[0]= lastfpt->vec[0];
1710                 lastkey[1]= lastfpt->vec[1];
1711         }
1712         else
1713                 return evaltime;
1714                 
1715         /* check if modifier will do anything
1716          *      1) if in data range, definitely don't do anything
1717          *      2) if before first frame or after last frame, make sure some cycling is in use
1718          */
1719         if (evaltime < prevkey[0]) {
1720                 if (data->before_mode)  {
1721                         side= -1;
1722                         mode= data->before_mode;
1723                         cycles= data->before_cycles;
1724                 }
1725         }
1726         else if (evaltime > lastkey[0]) {
1727                 if (data->after_mode) {
1728                         side= 1;
1729                         mode= data->after_mode;
1730                         cycles= data->after_cycles;
1731                 }
1732         }
1733         if ELEM(0, side, mode)
1734                 return evaltime;
1735                 
1736         /* find relative place within a cycle */
1737         {
1738                 float cycdx=0, cycdy=0, ofs=0;
1739                 float cycle= 0;
1740                 
1741                 /* ofs is start frame of cycle */
1742                 ofs= prevkey[0];
1743                 
1744                 /* calculate period and amplitude (total height) of a cycle */
1745                 cycdx= lastkey[0] - prevkey[0];
1746                 cycdy= lastkey[1] - prevkey[1];
1747                 
1748                 /* check if cycle is infinitely small, to be point of being impossible to use */
1749                 if (cycdx == 0)
1750                         return evaltime;
1751                         
1752                 /* calculate the 'number' of the cycle */
1753                 cycle= ((float)side * (evaltime - ofs) / cycdx);
1754                 
1755                 /* check that cyclic is still enabled for the specified time */
1756                 if (cycles == 0) {
1757                         /* catch this case so that we don't exit when we have cycles=0
1758                          * as this indicates infinite cycles...
1759                          */
1760                 }
1761                 else if (cycle > (cycles+1)) {
1762                         /* we are too far away from range to evaluate
1763                          * TODO: but we should still hold last value... 
1764                          */
1765                         return evaltime;
1766                 }
1767                 
1768                 /* check if 'cyclic extrapolation', and thus calculate y-offset for this cycle */
1769                 if (mode == FCM_EXTRAPOLATE_CYCLIC_OFFSET) {
1770                         cycyofs = (float)floor((evaltime - ofs) / cycdx);
1771                         cycyofs *= cycdy;
1772                 }
1773                 
1774                 /* calculate where in the cycle we are (overwrite evaltime to reflect this) */
1775                 if ((mode == FCM_EXTRAPOLATE_MIRROR) && ((int)(cycle) % 2)) {
1776                         /* when 'mirror' option is used and cycle number is odd, this cycle is played in reverse */
1777                         evaltime= (float)(lastkey[0] - fmod(evaltime-ofs, cycdx));
1778                 }
1779                 else {
1780                         /* the cycle is played normally... */
1781                         evaltime= (float)(fmod(evaltime-ofs, cycdx) + ofs);
1782                 }
1783                 if (evaltime < ofs) evaltime += cycdx;
1784         }
1785         
1786         /* store temp data if needed */
1787         if (mode == FCM_EXTRAPOLATE_CYCLIC_OFFSET) {
1788                 tFCMED_Cycles *edata;
1789                 
1790                 /* for now, this is just a float, but we could get more stuff... */
1791                 fcm->edata= edata= MEM_callocN(sizeof(tFCMED_Cycles), "tFCMED_Cycles");
1792                 edata->cycyofs= cycyofs;
1793         }
1794         
1795         /* return the new frame to evaluate */
1796         return evaltime;
1797 }
1798  
1799 static void fcm_cycles_evaluate (FCurve *fcu, FModifier *fcm, float *cvalue, float evaltime)
1800 {
1801         tFCMED_Cycles *edata= (tFCMED_Cycles *)fcm->edata;
1802         
1803         /* use temp data */
1804         if (edata) {
1805                 /* add cyclic offset - no need to check for now, otherwise the data wouldn't exist! */
1806                 *cvalue += edata->cycyofs;
1807                 
1808                 /* free temp data */
1809                 MEM_freeN(edata);
1810                 fcm->edata= NULL;
1811         }
1812 }
1813
1814 static FModifierTypeInfo FMI_CYCLES = {
1815         FMODIFIER_TYPE_CYCLES, /* type */
1816         sizeof(FMod_Cycles), /* size */
1817         FMI_TYPE_EXTRAPOLATION, /* action type */
1818         FMI_REQUIRES_ORIGINAL_DATA, /* requirements */
1819         "Cycles", /* name */
1820         "FMod_Cycles", /* struct name */
1821         NULL, /* free data */
1822         NULL, /* copy data */
1823         fcm_cycles_new_data, /* new data */
1824         NULL /*fcm_cycles_verify*/, /* verify */
1825         fcm_cycles_time, /* evaluate time */
1826         fcm_cycles_evaluate /* evaluate */
1827 };
1828
1829 /* Noise F-Curve Modifier  --------------------------- */
1830
1831 static void fcm_noise_new_data (void *mdata)
1832 {
1833         FMod_Noise *data= (FMod_Noise *)mdata;
1834         
1835         /* defaults */
1836         data->size= 1.0f;
1837         data->strength= 1.0f;
1838         data->phase= 1.0f;
1839         data->depth = 0;
1840         data->modification = FCM_NOISE_MODIF_REPLACE;
1841 }
1842  
1843 static void fcm_noise_evaluate (FCurve *fcu, FModifier *fcm, float *cvalue, float evaltime)
1844 {
1845         FMod_Noise *data= (FMod_Noise *)fcm->data;
1846         float noise;
1847         
1848         noise = BLI_turbulence(data->size, evaltime, data->phase, 0.f, data->depth);
1849         
1850         switch (data->modification) {
1851                 case FCM_NOISE_MODIF_ADD:
1852                         *cvalue= *cvalue + noise * data->strength;
1853                         break;
1854                 case FCM_NOISE_MODIF_SUBTRACT:
1855                         *cvalue= *cvalue - noise * data->strength;
1856                         break;
1857                 case FCM_NOISE_MODIF_MULTIPLY:
1858                         *cvalue= *cvalue * noise * data->strength;
1859                         break;
1860                 case FCM_NOISE_MODIF_REPLACE:
1861                 default:
1862                         *cvalue= *cvalue + (noise - 0.5f) * data->strength;
1863                         break;
1864         }
1865 }
1866
1867 static FModifierTypeInfo FMI_NOISE = {
1868         FMODIFIER_TYPE_NOISE, /* type */
1869         sizeof(FMod_Noise), /* size */
1870         FMI_TYPE_REPLACE_VALUES, /* action type */
1871         0, /* requirements */
1872         "Noise", /* name */
1873         "FMod_Noise", /* struct name */
1874         NULL, /* free data */
1875         NULL, /* copy data */
1876         fcm_noise_new_data, /* new data */
1877         NULL /*fcm_noise_verify*/, /* verify */
1878         NULL, /* evaluate time */
1879         fcm_noise_evaluate /* evaluate */
1880 };
1881
1882 /* Filter F-Curve Modifier --------------------------- */
1883
1884 #if 0 // XXX not yet implemented 
1885 static FModifierTypeInfo FMI_FILTER = {
1886         FMODIFIER_TYPE_FILTER, /* type */
1887         sizeof(FMod_Filter), /* size */
1888         FMI_TYPE_REPLACE_VALUES, /* action type */
1889         0, /* requirements */
1890         "Filter", /* name */
1891         "FMod_Filter", /* struct name */
1892         NULL, /* free data */
1893         NULL, /* copy data */
1894         NULL, /* new data */
1895         NULL /*fcm_filter_verify*/, /* verify */
1896         NULL, /* evlauate time */
1897         fcm_filter_evaluate /* evaluate */
1898 };
1899 #endif // XXX not yet implemented
1900
1901
1902 /* Python F-Curve Modifier --------------------------- */
1903
1904 static void fcm_python_free (FModifier *fcm)
1905 {
1906         FMod_Python *data= (FMod_Python *)fcm->data;
1907         
1908         /* id-properties */
1909         IDP_FreeProperty(data->prop);
1910         MEM_freeN(data->prop);
1911 }
1912
1913 static void fcm_python_new_data (void *mdata) 
1914 {
1915         FMod_Python *data= (FMod_Python *)mdata;
1916         
1917         /* everything should be set correctly by calloc, except for the prop->type constant.*/
1918         data->prop = MEM_callocN(sizeof(IDProperty), "PyFModifierProps");
1919         data->prop->type = IDP_GROUP;
1920 }
1921
1922 static void fcm_python_copy (FModifier *fcm, FModifier *src)
1923 {
1924         FMod_Python *pymod = (FMod_Python *)fcm->data;
1925         FMod_Python *opymod = (FMod_Python *)src->data;
1926         
1927         pymod->prop = IDP_CopyProperty(opymod->prop);
1928 }
1929
1930 static void fcm_python_evaluate (FCurve *fcu, FModifier *fcm, float *cvalue, float evaltime)
1931 {
1932 #ifndef DISABLE_PYTHON
1933         //FMod_Python *data= (FMod_Python *)fcm->data;
1934         
1935         /* FIXME... need to implement this modifier...
1936          *      It will need it execute a script using the custom properties 
1937          */
1938 #endif /* DISABLE_PYTHON */
1939 }
1940
1941 static FModifierTypeInfo FMI_PYTHON = {
1942         FMODIFIER_TYPE_PYTHON, /* type */
1943         sizeof(FMod_Python), /* size */
1944         FMI_TYPE_GENERATE_CURVE, /* action type */
1945         FMI_REQUIRES_RUNTIME_CHECK, /* requirements */
1946         "Python", /* name */
1947         "FMod_Python", /* struct name */
1948         fcm_python_free, /* free data */
1949         fcm_python_copy, /* copy data */
1950         fcm_python_new_data, /* new data */
1951         NULL /*fcm_python_verify*/, /* verify */
1952         NULL /*fcm_python_time*/, /* evaluate time */
1953         fcm_python_evaluate /* evaluate */
1954 };
1955
1956
1957 /* Limits F-Curve Modifier --------------------------- */
1958
1959 static float fcm_limits_time (FCurve *fcu, FModifier *fcm, float cvalue, float evaltime)
1960 {
1961         FMod_Limits *data= (FMod_Limits *)fcm->data;
1962         
1963         /* check for the time limits */
1964         if ((data->flag & FCM_LIMIT_XMIN) && (evaltime < data->rect.xmin))
1965                 return data->rect.xmin;
1966         if ((data->flag & FCM_LIMIT_XMAX) && (evaltime > data->rect.xmax))
1967                 return data->rect.xmax;
1968                 
1969         /* modifier doesn't change time */
1970         return evaltime;
1971 }
1972
1973 static void fcm_limits_evaluate (FCurve *fcu, FModifier *fcm, float *cvalue, float evaltime)
1974 {
1975         FMod_Limits *data= (FMod_Limits *)fcm->data;
1976         
1977         /* value limits now */
1978         if ((data->flag & FCM_LIMIT_YMIN) && (*cvalue < data->rect.ymin))
1979                 *cvalue= data->rect.ymin;
1980         if ((data->flag & FCM_LIMIT_YMAX) && (*cvalue > data->rect.ymax))
1981                 *cvalue= data->rect.ymax;
1982 }
1983
1984 static FModifierTypeInfo FMI_LIMITS = {
1985         FMODIFIER_TYPE_LIMITS, /* type */
1986         sizeof(FMod_Limits), /* size */
1987         FMI_TYPE_GENERATE_CURVE, /* action type */  /* XXX... err... */   
1988         FMI_REQUIRES_RUNTIME_CHECK, /* requirements */
1989         "Limits", /* name */
1990         "FMod_Limits", /* struct name */
1991         NULL, /* free data */
1992         NULL, /* copy data */
1993         NULL, /* new data */
1994         NULL, /* verify */
1995         fcm_limits_time, /* evaluate time */
1996         fcm_limits_evaluate /* evaluate */
1997 };
1998
1999 /* F-Curve Modifier API --------------------------- */
2000 /* All of the F-Curve Modifier api functions use FModifierTypeInfo structs to carry out
2001  * and operations that involve F-Curve modifier specific code.
2002  */
2003
2004 /* These globals only ever get directly accessed in this file */
2005 static FModifierTypeInfo *fmodifiersTypeInfo[FMODIFIER_NUM_TYPES];
2006 static short FMI_INIT= 1; /* when non-zero, the list needs to be updated */
2007
2008 /* This function only gets called when FMI_INIT is non-zero */
2009 static void fmods_init_typeinfo () 
2010 {
2011         fmodifiersTypeInfo[0]=  NULL;                                   /* 'Null' F-Curve Modifier */
2012         fmodifiersTypeInfo[1]=  &FMI_GENERATOR;                 /* Generator F-Curve Modifier */
2013         fmodifiersTypeInfo[2]=  &FMI_ENVELOPE;                  /* Envelope F-Curve Modifier */
2014         fmodifiersTypeInfo[3]=  &FMI_CYCLES;                    /* Cycles F-Curve Modifier */
2015         fmodifiersTypeInfo[4]=  &FMI_NOISE;                             /* Apply-Noise F-Curve Modifier */
2016         fmodifiersTypeInfo[5]=  NULL/*&FMI_FILTER*/;                    /* Filter F-Curve Modifier */  // XXX unimplemented
2017         fmodifiersTypeInfo[6]=  &FMI_PYTHON;                    /* Custom Python F-Curve Modifier */
2018         fmodifiersTypeInfo[7]=  &FMI_LIMITS;                    /* Limits F-Curve Modifier */
2019 }
2020
2021 /* This function should be used for getting the appropriate type-info when only
2022  * a F-Curve modifier type is known
2023  */
2024 FModifierTypeInfo *get_fmodifier_typeinfo (int type)
2025 {
2026         /* initialise the type-info list? */
2027         if (FMI_INIT) {
2028                 fmods_init_typeinfo();
2029                 FMI_INIT = 0;
2030         }
2031         
2032         /* only return for valid types */
2033         if ( (type >= FMODIFIER_TYPE_NULL) && 
2034                  (type <= FMODIFIER_NUM_TYPES ) ) 
2035         {
2036                 /* there shouldn't be any segfaults here... */
2037                 return fmodifiersTypeInfo[type];
2038         }
2039         else {
2040                 printf("No valid F-Curve Modifier type-info data available. Type = %i \n", type);
2041         }
2042         
2043         return NULL;
2044
2045  
2046 /* This function should always be used to get the appropriate type-info, as it
2047  * has checks which prevent segfaults in some weird cases.
2048  */
2049 FModifierTypeInfo *fmodifier_get_typeinfo (FModifier *fcm)
2050 {
2051         /* only return typeinfo for valid modifiers */
2052         if (fcm)
2053                 return get_fmodifier_typeinfo(fcm->type);
2054         else
2055                 return NULL;
2056 }
2057
2058 /* API --------------------------- */
2059
2060 /* Add a new F-Curve Modifier to the given F-Curve of a certain type */
2061 FModifier *fcurve_add_modifier (FCurve *fcu, int type)
2062 {
2063         FModifierTypeInfo *fmi= get_fmodifier_typeinfo(type);
2064         FModifier *fcm;
2065         
2066         /* sanity checks */
2067         if ELEM(NULL, fcu, fmi)
2068                 return NULL;
2069         
2070         /* special checks for whether modifier can be added */
2071         if ((fcu->modifiers.first) && (type == FMODIFIER_TYPE_CYCLES)) {
2072                 /* cycles modifier must be first in stack, so for now, don't add if it can't be */
2073                 // TODO: perhaps there is some better way, but for now, 
2074                 printf("Error: Cannot add 'Cycles' modifier to F-Curve, as 'Cycles' modifier can only be first in stack. \n");
2075                 return NULL;
2076         }
2077         
2078         /* add modifier itself */
2079         fcm= MEM_callocN(sizeof(FModifier), "F-Curve Modifier");
2080         fcm->type = type;
2081         fcm->flag = FMODIFIER_FLAG_EXPANDED;
2082         BLI_addtail(&fcu->modifiers, fcm);
2083         
2084         /* add modifier's data */
2085         fcm->data= MEM_callocN(fmi->size, fmi->structName);
2086                 
2087         /* init custom settings if necessary */
2088         if (fmi->new_data)      
2089                 fmi->new_data(fcm->data);
2090                 
2091         /* return modifier for further editing */
2092         return fcm;
2093 }
2094
2095 /* Duplicate all of the F-Curve Modifiers in the Modifier stacks */
2096 void fcurve_copy_modifiers (ListBase *dst, ListBase *src)
2097 {
2098         FModifier *fcm, *srcfcm;
2099         
2100         if ELEM(NULL, dst, src)
2101                 return;
2102         
2103         dst->first= dst->last= NULL;
2104         BLI_duplicatelist(dst, src);
2105         
2106         for (fcm=dst->first, srcfcm=src->first; fcm && srcfcm; srcfcm=srcfcm->next, fcm=fcm->next) {
2107                 FModifierTypeInfo *fmi= fmodifier_get_typeinfo(fcm);
2108                 
2109                 /* make a new copy of the F-Modifier's data */
2110                 fcm->data = MEM_dupallocN(fcm->data);
2111                 
2112                 /* only do specific constraints if required */
2113                 if (fmi && fmi->copy_data)
2114                         fmi->copy_data(fcm, srcfcm);
2115         }
2116 }
2117
2118 /* Remove and free the given F-Curve Modifier from the given F-Curve's stack  */
2119 void fcurve_remove_modifier (FCurve *fcu, FModifier *fcm)
2120 {
2121         FModifierTypeInfo *fmi= fmodifier_get_typeinfo(fcm);
2122         
2123         /* sanity check */
2124         if (fcm == NULL)
2125                 return;
2126         
2127         /* free modifier's special data (stored inside fcm->data) */
2128         if (fcm->data) {
2129                 if (fmi && fmi->free_data)
2130                         fmi->free_data(fcm);
2131                         
2132                 /* free modifier's data (fcm->data) */
2133                 MEM_freeN(fcm->data);
2134         }
2135         
2136         /* remove modifier from stack */
2137         if (fcu)
2138                 BLI_freelinkN(&fcu->modifiers, fcm);
2139         else {
2140                 // XXX this case can probably be removed some day, as it shouldn't happen...
2141                 printf("fcurve_remove_modifier() - no fcurve \n");
2142                 MEM_freeN(fcm);
2143         }
2144 }
2145
2146 /* Remove all of a given F-Curve's modifiers */
2147 void fcurve_free_modifiers (FCurve *fcu)
2148 {
2149         FModifier *fcm, *fmn;
2150         
2151         /* sanity check */
2152         if (fcu == NULL)
2153                 return;
2154         
2155         /* free each modifier in order - modifier is unlinked from list and freed */
2156         for (fcm= fcu->modifiers.first; fcm; fcm= fmn) {
2157                 fmn= fcm->next;
2158                 fcurve_remove_modifier(fcu, fcm);
2159         }
2160 }
2161
2162 /* Bake modifiers for given F-Curve to curve sample data, in the frame range defined
2163  * by start and end (inclusive).
2164  */
2165 void fcurve_bake_modifiers (FCurve *fcu, int start, int end)
2166 {
2167         ChannelDriver *driver;
2168         
2169         /* sanity checks */
2170         // TODO: make these tests report errors using reports not printf's
2171         if ELEM(NULL, fcu, fcu->modifiers.first) {
2172                 printf("Error: No F-Curve with F-Curve Modifiers to Bake\n");
2173                 return;
2174         }
2175         
2176         /* temporarily, disable driver while we sample, so that they don't influence the outcome */
2177         driver= fcu->driver;
2178         fcu->driver= NULL;
2179         
2180         /* bake the modifiers, by sampling the curve at each frame */
2181         fcurve_store_samples(fcu, NULL, start, end, fcurve_samplingcb_evalcurve);
2182         
2183         /* free the modifiers now */
2184         fcurve_free_modifiers(fcu);
2185         
2186         /* restore driver */
2187         fcu->driver= driver;
2188 }
2189
2190 /* Find the active F-Curve Modifier */
2191 FModifier *fcurve_find_active_modifier (FCurve *fcu)
2192 {
2193         FModifier *fcm;
2194         
2195         /* sanity checks */
2196         if ELEM(NULL, fcu, fcu->modifiers.first)
2197                 return NULL;
2198         
2199         /* loop over modifiers until 'active' one is found */
2200         for (fcm= fcu->modifiers.first; fcm; fcm= fcm->next) {
2201                 if (fcm->flag & FMODIFIER_FLAG_ACTIVE)
2202                         return fcm;
2203         }
2204         
2205         /* no modifier is active */
2206         return NULL;
2207 }
2208
2209 /* Set the active F-Curve Modifier */
2210 void fcurve_set_active_modifier (FCurve *fcu, FModifier *fcm)
2211 {
2212         FModifier *fm;
2213         
2214         /* sanity checks */
2215         if ELEM(NULL, fcu, fcu->modifiers.first)
2216                 return;
2217         
2218         /* deactivate all, and set current one active */
2219         for (fm= fcu->modifiers.first; fm; fm= fm->next)
2220                 fm->flag &= ~FMODIFIER_FLAG_ACTIVE;
2221         
2222         /* make given modifier active */
2223         if (fcm)
2224                 fcm->flag |= FMODIFIER_FLAG_ACTIVE;
2225 }
2226
2227 /* ***************************** F-Curve - Evaluation ********************************* */
2228
2229 /* Evaluate and return the value of the given F-Curve at the specified frame ("evaltime") 
2230  * Note: this is also used for drivers
2231  */
2232 float evaluate_fcurve (FCurve *fcu, float evaltime) 
2233 {
2234         FModifier *fcm;
2235         float cvalue= 0.0f;
2236         float devaltime;
2237         
2238         /* if there is a driver (only if this F-Curve is acting as 'driver'), evaluate it to find value to use as "evaltime" 
2239          * since drivers essentially act as alternative input (i.e. in place of 'time') for F-Curves
2240          *      - this value will also be returned as the value of the 'curve', if there are no keyframes
2241          */
2242         if (fcu->driver) {
2243                 /* evaltime now serves as input for the curve */
2244                 evaltime= cvalue= evaluate_driver(fcu->driver, evaltime);
2245         }
2246         
2247         /* evaluate time modifications imposed by some F-Curve Modifiers
2248          *      - this step acts as an optimisation to prevent the F-Curve stack being evaluated 
2249          *        several times by modifiers requesting the time be modified, as the final result
2250          *        would have required using the modified time
2251          *      - modifiers only ever recieve the unmodified time, as subsequent modifiers should be
2252          *        working on the 'global' result of the modified curve, not some localised segment,
2253          *        so nevaltime gets set to whatever the last time-modifying modifier likes...
2254          *      - we start from the end of the stack, as only the last one matters for now
2255          */
2256         devaltime= evaltime;
2257         
2258         for (fcm= fcu->modifiers.last; fcm; fcm= fcm->prev) {
2259                 FModifierTypeInfo *fmi= fmodifier_get_typeinfo(fcm);
2260                 
2261                 /* only evaluate if there's a callback for this */
2262                 // TODO: implement the 'influence' control feature...
2263                 if (fmi && fmi->evaluate_modifier_time) {
2264                         if ((fcm->flag & (FMODIFIER_FLAG_DISABLED|FMODIFIER_FLAG_MUTED)) == 0)
2265                                 devaltime= fmi->evaluate_modifier_time(fcu, fcm, cvalue, evaltime);
2266                         break;
2267                 }
2268         }
2269         
2270         /* evaluate curve-data 
2271          *      - 'devaltime' instead of 'evaltime', as this is the time that the last time-modifying 
2272          *        F-Curve modifier on the stack requested the curve to be evaluated at
2273          */
2274         if (fcu->bezt)
2275                 cvalue= fcurve_eval_keyframes(fcu, fcu->bezt, devaltime);
2276         else if (fcu->fpt)
2277                 cvalue= fcurve_eval_samples(fcu, fcu->fpt, devaltime);
2278         
2279         /* evaluate modifiers */
2280         for (fcm= fcu->modifiers.first; fcm; fcm= fcm->next) {
2281                 FModifierTypeInfo *fmi= fmodifier_get_typeinfo(fcm);
2282                 
2283                 /* only evaluate if there's a callback for this */
2284                 // TODO: implement the 'influence' control feature...
2285                 if (fmi && fmi->evaluate_modifier) {
2286                         if ((fcm->flag & (FMODIFIER_FLAG_DISABLED|FMODIFIER_FLAG_MUTED)) == 0)
2287                                 fmi->evaluate_modifier(fcu, fcm, &cvalue, evaltime);
2288                 }
2289         }
2290         
2291         /* if curve can only have integral values, perform truncation (i.e. drop the decimal part)
2292          * here so that the curve can be sampled correctly
2293          */
2294         if (fcu->flag & FCURVE_INT_VALUES)
2295                 cvalue= (float)((int)cvalue);
2296         
2297         /* return evaluated value */
2298         return cvalue;
2299 }
2300
2301 /* Calculate the value of the given F-Curve at the given frame, and set its curval */
2302 // TODO: will this be necessary?
2303 void calculate_fcurve (FCurve *fcu, float ctime)
2304 {
2305         /* calculate and set curval (evaluates driver too) */
2306         fcu->curval= evaluate_fcurve(fcu, ctime);
2307 }
2308