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