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