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