source/blender/blenkernel/intern/fcurve.c

   1 /*
   2  * $Id$
   3  *
   4  * ***** BEGIN GPL LICENSE BLOCK *****
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License
   8  * as published by the Free Software Foundation; either version 2
   9  * of the License, or (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  19  *
  20  * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
  21  * All rights reserved.
  22  *
  23  * The Original Code is: all of this file.
  24  *
  25  * Contributor(s): Joshua Leung (full recode)
  26  *
  27  * ***** END GPL LICENSE BLOCK *****
  28  */
  29
  30 /** \file blender/blenkernel/intern/fcurve.c
  31  *  \ingroup bke
  32  */
  33
  34
  35
  36 #include <math.h>
  37 #include <stdio.h>
  38 #include <stddef.h>
  39 #include <string.h>
  40 #include <float.h>
  41
  42 #include "MEM_guardedalloc.h"
  43
  44 #include "DNA_anim_types.h"
  45 #include "DNA_constraint_types.h"
  46 #include "DNA_object_types.h"
  47
  48 #include "BLI_blenlib.h"
  49 #include "BLI_math.h"
  50 #include "BLI_utildefines.h"
  51
  52 #include "BKE_fcurve.h"
  53 #include "BKE_animsys.h"
  54 #include "BKE_action.h"
  55 #include "BKE_armature.h"
  56 #include "BKE_constraint.h"
  57 #include "BKE_curve.h"
  58 #include "BKE_global.h"
  59 #include "BKE_object.h"
  60 #include "BKE_utildefines.h"
  61
  62 #include "RNA_access.h"
  63
  64 #ifdef WITH_PYTHON
  65 #include "BPY_extern.h"
  66 #endif
  67
  68 #define SMALL -1.0e-10
  69 #define SELECT 1
  70
  71 /* ************************** Data-Level Functions ************************* */
  72
  73 /* ---------------------- Freeing --------------------------- */
  74
  75 /* Frees the F-Curve itself too, so make sure BLI_remlink is called before calling this... */
  76 void free_fcurve (FCurve *fcu)
  77 {
  78         if (fcu == NULL)
  79                 return;
  80
  81         /* free curve data */
  82         if (fcu) {
  83                 if (fcu->bezt) MEM_freeN(fcu->bezt);
  84                 if (fcu->fpt) MEM_freeN(fcu->fpt);
  85         }
  86
  87         /* free RNA-path, as this were allocated when getting the path string */
  88         if (fcu->rna_path)
  89                 MEM_freeN(fcu->rna_path);
  90
  91         /* free extra data - i.e. modifiers, and driver */
  92         fcurve_free_driver(fcu);
  93         free_fmodifiers(&fcu->modifiers);
  94
  95         /* free f-curve itself */
  96         MEM_freeN(fcu);
  97 }
  98
  99 /* Frees a list of F-Curves */
 100 void free_fcurves (ListBase *list)
 101 {
 102         FCurve *fcu, *fcn;
 103
 104         /* sanity check */
 105         if (list == NULL)
 106                 return;
 107
 108         /* free data - no need to call remlink before freeing each curve,
 109          * as we store reference to next, and freeing only touches the curve
 110          * it's given
 111          */
 112         for (fcu= list->first; fcu; fcu= fcn) {
 113                 fcn= fcu->next;
 114                 free_fcurve(fcu);
 115         }
 116
 117         /* clear pointers just in case */
 118         list->first= list->last= NULL;
 119 }
 120
 121 /* ---------------------- Copy --------------------------- */
 122
 123 /* duplicate an F-Curve */
 124 FCurve *copy_fcurve (FCurve *fcu)
 125 {
 126         FCurve *fcu_d;
 127
 128         /* sanity check */
 129         if (fcu == NULL)
 130                 return NULL;
 131
 132         /* make a copy */
 133         fcu_d= MEM_dupallocN(fcu);
 134
 135         fcu_d->next= fcu_d->prev= NULL;
 136         fcu_d->grp= NULL;
 137
 138         /* copy curve data */
 139         fcu_d->bezt= MEM_dupallocN(fcu_d->bezt);
 140         fcu_d->fpt= MEM_dupallocN(fcu_d->fpt);
 141
 142         /* copy rna-path */
 143         fcu_d->rna_path= MEM_dupallocN(fcu_d->rna_path);
 144
 145         /* copy driver */
 146         fcu_d->driver= fcurve_copy_driver(fcu_d->driver);
 147
 148         /* copy modifiers */
 149         copy_fmodifiers(&fcu_d->modifiers, &fcu->modifiers);
 150
 151         /* return new data */
 152         return fcu_d;
 153 }
 154
 155 /* duplicate a list of F-Curves */
 156 void copy_fcurves (ListBase *dst, ListBase *src)
 157 {
 158         FCurve *dfcu, *sfcu;
 159
 160         /* sanity checks */
 161         if ELEM(NULL, dst, src)
 162                 return;
 163
 164         /* clear destination list first */
 165         dst->first= dst->last= NULL;
 166
 167         /* copy one-by-one */
 168         for (sfcu= src->first; sfcu; sfcu= sfcu->next) {
 169                 dfcu= copy_fcurve(sfcu);
 170                 BLI_addtail(dst, dfcu);
 171         }
 172 }
 173
 174 /* ----------------- Finding F-Curves -------------------------- */
 175
 176 /* high level function to get an fcurve from C without having the rna */
 177 FCurve *id_data_find_fcurve(ID *id, void *data, StructRNA *type, const char *prop_name, int index, char *driven)
 178 {
 179         /* anim vars */
 180         AnimData *adt= BKE_animdata_from_id(id);
 181         FCurve *fcu= NULL;
 182
 183         /* rna vars */
 184         PointerRNA ptr;
 185         PropertyRNA *prop;
 186         char *path;
 187
 188         if(driven)
 189                 *driven = 0;
 190
 191         /* only use the current action ??? */
 192         if (ELEM(NULL, adt, adt->action))
 193                 return NULL;
 194
 195         RNA_pointer_create(id, type, data, &ptr);
 196         prop = RNA_struct_find_property(&ptr, prop_name);
 197
 198         if (prop) {
 199                 path= RNA_path_from_ID_to_property(&ptr, prop);
 200
 201                 if (path) {
 202                         /* animation takes priority over drivers */
 203                         if ((adt->action) && (adt->action->curves.first))
 204                                 fcu= list_find_fcurve(&adt->action->curves, path, index);
 205
 206                         /* if not animated, check if driven */
 207                         if ((fcu == NULL) && (adt->drivers.first)) {
 208                                 fcu= list_find_fcurve(&adt->drivers, path, index);
 209                                 if(fcu && driven)
 210                                         *driven = 1;
 211                                 fcu = NULL;
 212                         }
 213
 214                         MEM_freeN(path);
 215                 }
 216         }
 217
 218         return fcu;
 219 }
 220
 221
 222 /* Find the F-Curve affecting the given RNA-access path + index, in the list of F-Curves provided */
 223 FCurve *list_find_fcurve (ListBase *list, const char rna_path[], const int array_index)
 224 {
 225         FCurve *fcu;
 226
 227         /* sanity checks */
 228         if ( ELEM(NULL, list, rna_path) || (array_index < 0) )
 229                 return NULL;
 230
 231         /* check paths of curves, then array indices... */
 232         for (fcu= list->first; fcu; fcu= fcu->next) {
 233                 /* simple string-compare (this assumes that they have the same root...) */
 234                 if (fcu->rna_path && !strcmp(fcu->rna_path, rna_path)) {
 235                         /* now check indices */
 236                         if (fcu->array_index == array_index)
 237                                 return fcu;
 238                 }
 239         }
 240
 241         /* return */
 242         return NULL;
 243 }
 244
 245 /* quick way to loop over all fcurves of a given 'path' */
 246 FCurve *iter_step_fcurve (FCurve *fcu_iter, const char rna_path[])
 247 {
 248         FCurve *fcu;
 249
 250         /* sanity checks */
 251         if (ELEM(NULL, fcu_iter, rna_path))
 252                 return NULL;
 253
 254         /* check paths of curves, then array indices... */
 255         for (fcu= fcu_iter; fcu; fcu= fcu->next) {
 256                 /* simple string-compare (this assumes that they have the same root...) */
 257                 if (fcu->rna_path && !strcmp(fcu->rna_path, rna_path)) {
 258                         return fcu;
 259                 }
 260         }
 261
 262         /* return */
 263         return NULL;
 264 }
 265
 266 /* Get list of LinkData's containing pointers to the F-Curves which control the types of data indicated
 267  * Lists...
 268  *      - dst: list of LinkData's matching the criteria returned.
 269  *        List must be freed after use, and is assumed to be empty when passed.
 270  *      - src: list of F-Curves to search through
 271  * Filters...
 272  *      - dataPrefix: i.e. 'pose.bones[' or 'nodes['
 273  *      - dataName: name of entity within "" immediately following the prefix
 274  */
 275 int list_find_data_fcurves (ListBase *dst, ListBase *src, const char *dataPrefix, const char *dataName)
 276 {
 277         FCurve *fcu;
 278         int matches = 0;
 279
 280         /* sanity checks */
 281         if (ELEM4(NULL, dst, src, dataPrefix, dataName))
 282                 return 0;
 283         else if ((dataPrefix[0] == 0) || (dataName[0] == 0))
 284                 return 0;
 285
 286         /* search each F-Curve one by one */
 287         for (fcu= src->first; fcu; fcu= fcu->next) {
 288                 /* check if quoted string matches the path */
 289                 if ((fcu->rna_path) && strstr(fcu->rna_path, dataPrefix)) {
 290                         char *quotedName= BLI_getQuotedStr(fcu->rna_path, dataPrefix);
 291
 292                         if (quotedName) {
 293                                 /* check if the quoted name matches the required name */
 294                                 if (strcmp(quotedName, dataName) == 0) {
 295                                         LinkData *ld= MEM_callocN(sizeof(LinkData), "list_find_data_fcurves");
 296
 297                                         ld->data= fcu;
 298                                         BLI_addtail(dst, ld);
 299
 300                                         matches++;
 301                                 }
 302
 303                                 /* always free the quoted string, since it needs freeing */
 304                                 MEM_freeN(quotedName);
 305                         }
 306                 }
 307         }
 308
 309         /* return the number of matches */
 310         return matches;
 311 }
 312
 313 FCurve *rna_get_fcurve (PointerRNA *ptr, PropertyRNA *prop, int rnaindex, bAction **action, int *driven)
 314 {
 315         FCurve *fcu= NULL;
 316
 317         *driven= 0;
 318
 319         /* there must be some RNA-pointer + property combon */
 320         if (prop && ptr->id.data && RNA_property_animateable(ptr, prop)) {
 321                 AnimData *adt= BKE_animdata_from_id(ptr->id.data);
 322                 char *path;
 323
 324                 if (adt) {
 325                         if ((adt->action && adt->action->curves.first) || (adt->drivers.first)) {
 326                                 /* XXX this function call can become a performance bottleneck */
 327                                 path= RNA_path_from_ID_to_property(ptr, prop);
 328
 329                                 if (path) {
 330                                         /* animation takes priority over drivers */
 331                                         if (adt->action && adt->action->curves.first)
 332                                                 fcu= list_find_fcurve(&adt->action->curves, path, rnaindex);
 333
 334                                         /* if not animated, check if driven */
 335                                         if (!fcu && (adt->drivers.first)) {
 336                                                 fcu= list_find_fcurve(&adt->drivers, path, rnaindex);
 337
 338                                                 if (fcu)
 339                                                         *driven= 1;
 340                                         }
 341
 342                                         if (fcu && action)
 343                                                 *action= adt->action;
 344
 345                                         MEM_freeN(path);
 346                                 }
 347                         }
 348                 }
 349         }
 350
 351         return fcu;
 352 }
 353
 354 /* ----------------- Finding Keyframes/Extents -------------------------- */
 355
 356 /* threshold for binary-searching keyframes - threshold here should be good enough for now, but should become userpref */
 357 #define BEZT_BINARYSEARCH_THRESH        0.01f /* was 0.00001, but giving errors */
 358
 359 /* Binary search algorithm for finding where to insert BezTriple. (for use by insert_bezt_fcurve)
 360  * Returns the index to insert at (data already at that index will be offset if replace is 0)
 361  */
 362 int binarysearch_bezt_index (BezTriple array[], float frame, int arraylen, short *replace)
 363 {
 364         int start=0, end=arraylen;
 365         int loopbreaker= 0, maxloop= arraylen * 2;
 366
 367         /* initialise replace-flag first */
 368         *replace= 0;
 369
 370         /* sneaky optimisations (don't go through searching process if...):
 371          *      - keyframe to be added is to be added out of current bounds
 372          *      - keyframe to be added would replace one of the existing ones on bounds
 373          */
 374         if ((arraylen <= 0) || (array == NULL)) {
 375                 printf("Warning: binarysearch_bezt_index() encountered invalid array \n");
 376                 return 0;
 377         }
 378         else {
 379                 /* check whether to add before/after/on */
 380                 float framenum;
 381
 382                 /* 'First' Keyframe (when only one keyframe, this case is used) */
 383                 framenum= array[0].vec[1][0];
 384                 if (IS_EQT(frame, framenum, BEZT_BINARYSEARCH_THRESH)) {
 385                         *replace = 1;
 386                         return 0;
 387                 }
 388                 else if (frame < framenum)
 389                         return 0;
 390
 391                 /* 'Last' Keyframe */
 392                 framenum= array[(arraylen-1)].vec[1][0];
 393                 if (IS_EQT(frame, framenum, BEZT_BINARYSEARCH_THRESH)) {
 394                         *replace= 1;
 395                         return (arraylen - 1);
 396                 }
 397                 else if (frame > framenum)
 398                         return arraylen;
 399         }
 400
 401
 402         /* most of the time, this loop is just to find where to put it
 403          * 'loopbreaker' is just here to prevent infinite loops
 404          */
 405         for (loopbreaker=0; (start <= end) && (loopbreaker < maxloop); loopbreaker++) {
 406                 /* compute and get midpoint */
 407                 int mid = start + ((end - start) / 2);  /* we calculate the midpoint this way to avoid int overflows... */
 408                 float midfra= array[mid].vec[1][0];
 409
 410                 /* check if exactly equal to midpoint */
 411                 if (IS_EQT(frame, midfra, BEZT_BINARYSEARCH_THRESH)) {
 412                         *replace = 1;
 413                         return mid;
 414                 }
 415
 416                 /* repeat in upper/lower half */
 417                 if (frame > midfra)
 418                         start= mid + 1;
 419                 else if (frame < midfra)
 420                         end= mid - 1;
 421         }
 422
 423         /* print error if loop-limit exceeded */
 424         if (loopbreaker == (maxloop-1)) {
 425                 printf("Error: binarysearch_bezt_index() was taking too long \n");
 426
 427                 // include debug info
 428                 printf("\tround = %d: start = %d, end = %d, arraylen = %d \n", loopbreaker, start, end, arraylen);
 429         }
 430
 431         /* not found, so return where to place it */
 432         return start;
 433 }
 434
 435 /* ...................................... */
 436
 437 /* helper for calc_fcurve_* functions -> find first and last BezTriple to be used */
 438 static void get_fcurve_end_keyframes (FCurve *fcu, BezTriple **first, BezTriple **last, const short selOnly)
 439 {
 440         /* init outputs */
 441         *first = NULL;
 442         *last = NULL;
 443
 444         /* sanity checks */
 445         if (fcu->bezt == NULL)
 446                 return;
 447
 448         /* only include selected items? */
 449         if (selOnly) {
 450                 BezTriple *bezt;
 451                 unsigned int i;
 452
 453                 /* find first selected */
 454                 bezt = fcu->bezt;
 455                 for (i=0; i < fcu->totvert; bezt++, i++) {
 456                         if (BEZSELECTED(bezt)) {
 457                                 *first= bezt;
 458                                 break;
 459                         }
 460                 }
 461
 462                 /* find last selected */
 463                 bezt = ARRAY_LAST_ITEM(fcu->bezt, BezTriple, sizeof(BezTriple), fcu->totvert);
 464                 for (i=0; i < fcu->totvert; bezt--, i++) {
 465                         if (BEZSELECTED(bezt)) {
 466                                 *last= bezt;
 467                                 break;
 468                         }
 469                 }
 470         }
 471         else {
 472                 /* just full array */
 473                 *first = fcu->bezt;
 474                 *last = ARRAY_LAST_ITEM(fcu->bezt, BezTriple, sizeof(BezTriple), fcu->totvert);
 475         }
 476 }
 477
 478
 479 /* Calculate the extents of F-Curve's data */
 480 void calc_fcurve_bounds (FCurve *fcu, float *xmin, float *xmax, float *ymin, float *ymax, const short selOnly)
 481 {
 482         float xminv=999999999.0f, xmaxv=-999999999.0f;
 483         float yminv=999999999.0f, ymaxv=-999999999.0f;
 484         short foundvert=0;
 485         unsigned int i;
 486
 487         if (fcu->totvert) {
 488                 if (fcu->bezt) {
 489                         BezTriple *bezt_first= NULL, *bezt_last= NULL;
 490
 491                         if (xmin || xmax) {
 492                                 /* get endpoint keyframes */
 493                                 get_fcurve_end_keyframes(fcu, &bezt_first, &bezt_last, selOnly);
 494
 495                                 if (bezt_first) {
 496                                         BLI_assert(bezt_last != NULL);
 497
 498                                         xminv= MIN2(xminv, bezt_first->vec[1][0]);
 499                                         xmaxv= MAX2(xmaxv, bezt_last->vec[1][0]);
 500                                 }
 501                         }
 502
 503                         /* only loop over keyframes to find extents for values if needed */
 504                         if (ymin || ymax) {
 505                                 BezTriple *bezt;
 506
 507                                 for (bezt=fcu->bezt, i=0; i < fcu->totvert; bezt++, i++) {
 508                                         if ((selOnly == 0) || BEZSELECTED(bezt)) {
 509                                                 if (bezt->vec[1][1] < yminv)
 510                                                         yminv= bezt->vec[1][1];
 511                                                 if (bezt->vec[1][1] > ymaxv)
 512                                                         ymaxv= bezt->vec[1][1];
 513                                         }
 514                                 }
 515                         }
 516                 }
 517                 else if (fcu->fpt) {
 518                         /* frame range can be directly calculated from end verts */
 519                         if (xmin || xmax) {
 520                                 xminv= MIN2(xminv, fcu->fpt[0].vec[0]);
 521                                 xmaxv= MAX2(xmaxv, fcu->fpt[fcu->totvert-1].vec[0]);
 522                         }
 523
 524                         /* only loop over keyframes to find extents for values if needed */
 525                         if (ymin || ymax) {
 526                                 FPoint *fpt;
 527
 528                                 for (fpt=fcu->fpt, i=0; i < fcu->totvert; fpt++, i++) {
 529                                         if (fpt->vec[1] < yminv)
 530                                                 yminv= fpt->vec[1];
 531                                         if (fpt->vec[1] > ymaxv)
 532                                                 ymaxv= fpt->vec[1];
 533                                 }
 534                         }
 535                 }
 536
 537                 foundvert=1;
 538         }
 539
 540         if (foundvert) {
 541                 if (xmin) *xmin= xminv;
 542                 if (xmax) *xmax= xmaxv;
 543
 544                 if (ymin) *ymin= yminv;
 545                 if (ymax) *ymax= ymaxv;
 546         }
 547         else {
 548                 if (G.f & G_DEBUG)
 549                         printf("F-Curve calc bounds didn't find anything, so assuming minimum bounds of 1.0\n");
 550
 551                 if (xmin) *xmin= 0.0f;
 552                 if (xmax) *xmax= 1.0f;
 553
 554                 if (ymin) *ymin= 0.0f;
 555                 if (ymax) *ymax= 1.0f;
 556         }
 557 }
 558
 559 /* Calculate the extents of F-Curve's keyframes */
 560 void calc_fcurve_range (FCurve *fcu, float *start, float *end, const short selOnly)
 561 {
 562         float min=999999999.0f, max=-999999999.0f;
 563         short foundvert=0;
 564
 565         if (fcu->totvert) {
 566                 if (fcu->bezt) {
 567                         BezTriple *bezt_first= NULL, *bezt_last= NULL;
 568
 569                         /* get endpoint keyframes */
 570                         get_fcurve_end_keyframes(fcu, &bezt_first, &bezt_last, selOnly);
 571
 572                         if (bezt_first) {
 573                                 BLI_assert(bezt_last != NULL);
 574
 575                                 min= MIN2(min, bezt_first->vec[1][0]);
 576                                 max= MAX2(max, bezt_last->vec[1][0]);
 577                         }
 578                 }
 579                 else if (fcu->fpt) {
 580                         min= MIN2(min, fcu->fpt[0].vec[0]);
 581                         max= MAX2(max, fcu->fpt[fcu->totvert-1].vec[0]);
 582                 }
 583
 584                 foundvert=1;
 585         }
 586
 587         /* minimum length is 1 frame */
 588         if (foundvert) {
 589                 if (min == max) max += 1.0f;
 590                 *start= min;
 591                 *end= max;
 592         }
 593         else {
 594                 *start= 0.0f;
 595                 *end= 1.0f;
 596         }
 597 }
 598
 599 /* ----------------- Status Checks -------------------------- */
 600
 601 /* Are keyframes on F-Curve of any use?
 602  * Usability of keyframes refers to whether they should be displayed,
 603  * and also whether they will have any influence on the final result.
 604  */
 605 short fcurve_are_keyframes_usable (FCurve *fcu)
 606 {
 607         /* F-Curve must exist */
 608         if (fcu == NULL)
 609                 return 0;
 610
 611         /* F-Curve must not have samples - samples are mutually exclusive of keyframes */
 612         if (fcu->fpt)
 613                 return 0;
 614
 615         /* if it has modifiers, none of these should "drastically" alter the curve */
 616         if (fcu->modifiers.first) {
 617                 FModifier *fcm;
 618
 619                 /* check modifiers from last to first, as last will be more influential */
 620                 // TODO: optionally, only check modifier if it is the active one...
 621                 for (fcm = fcu->modifiers.last; fcm; fcm = fcm->prev) {
 622                         /* ignore if muted/disabled */
 623                         if (fcm->flag & (FMODIFIER_FLAG_DISABLED|FMODIFIER_FLAG_MUTED))
 624                                 continue;
 625
 626                         /* type checks */
 627                         switch (fcm->type) {
 628                                 /* clearly harmless - do nothing */
 629                                 case FMODIFIER_TYPE_CYCLES:
 630                                 case FMODIFIER_TYPE_STEPPED:
 631                                 case FMODIFIER_TYPE_NOISE:
 632                                         break;
 633
 634                                 /* sometimes harmful - depending on whether they're "additive" or not */
 635                                 case FMODIFIER_TYPE_GENERATOR:
 636                                 {
 637                                         FMod_Generator *data = (FMod_Generator *)fcm->data;
 638
 639                                         if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0)
 640                                                 return 0;
 641                                 }
 642                                         break;
 643                                 case FMODIFIER_TYPE_FN_GENERATOR:
 644                                 {
 645                                         FMod_FunctionGenerator *data = (FMod_FunctionGenerator *)fcm->data;
 646
 647                                         if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0)
 648                                                 return 0;
 649                                 }
 650                                         break;
 651
 652                                 /* always harmful - cannot allow */
 653                                 default:
 654                                         return 0;
 655                         }
 656                 }
 657         }
 658
 659         /* keyframes are usable */
 660         return 1;
 661 }
 662
 663 /* Can keyframes be added to F-Curve?
 664  * Keyframes can only be added if they are already visible
 665  */
 666 short fcurve_is_keyframable (FCurve *fcu)
 667 {
 668         /* F-Curve's keyframes must be "usable" (i.e. visible + have an effect on final result) */
 669         if (fcurve_are_keyframes_usable(fcu) == 0)
 670                 return 0;
 671
 672         /* F-Curve must currently be editable too */
 673         if ( (fcu->flag & FCURVE_PROTECTED) || ((fcu->grp) && (fcu->grp->flag & AGRP_PROTECTED)) )
 674                 return 0;
 675
 676         /* F-Curve is keyframable */
 677         return 1;
 678 }
 679
 680 /* ***************************** Keyframe Column Tools ********************************* */
 681
 682 /* add a BezTriple to a column */
 683 void bezt_add_to_cfra_elem (ListBase *lb, BezTriple *bezt)
 684 {
 685         CfraElem *ce, *cen;
 686
 687         for (ce= lb->first; ce; ce= ce->next) {
 688                 /* double key? */
 689                 if (ce->cfra == bezt->vec[1][0]) {
 690                         if (bezt->f2 & SELECT) ce->sel= bezt->f2;
 691                         return;
 692                 }
 693                 /* should key be inserted before this column? */
 694                 else if (ce->cfra > bezt->vec[1][0]) break;
 695         }
 696
 697         /* create a new column */
 698         cen= MEM_callocN(sizeof(CfraElem), "add_to_cfra_elem");
 699         if (ce) BLI_insertlinkbefore(lb, ce, cen);
 700         else BLI_addtail(lb, cen);
 701
 702         cen->cfra= bezt->vec[1][0];
 703         cen->sel= bezt->f2;
 704 }
 705
 706 /* ***************************** Samples Utilities ******************************* */
 707 /* Some utilities for working with FPoints (i.e. 'sampled' animation curve data, such as
 708  * data imported from BVH/Mocap files), which are specialised for use with high density datasets,
 709  * which BezTriples/Keyframe data are ill equipped to do.
 710  */
 711
 712
 713 /* Basic sampling callback which acts as a wrapper for evaluate_fcurve()
 714  *      'data' arg here is unneeded here...
 715  */
 716 float fcurve_samplingcb_evalcurve (FCurve *fcu, void *UNUSED(data), float evaltime)
 717 {
 718         /* assume any interference from drivers on the curve is intended... */
 719         return evaluate_fcurve(fcu, evaltime);
 720 }
 721
 722
 723 /* Main API function for creating a set of sampled curve data, given some callback function
 724  * used to retrieve the values to store.
 725  */
 726 void fcurve_store_samples (FCurve *fcu, void *data, int start, int end, FcuSampleFunc sample_cb)
 727 {
 728         FPoint *fpt, *new_fpt;
 729         int cfra;
 730
 731         /* sanity checks */
 732         // TODO: make these tests report errors using reports not printf's
 733         if ELEM(NULL, fcu, sample_cb) {
 734                 printf("Error: No F-Curve with F-Curve Modifiers to Bake\n");
 735                 return;
 736         }
 737         if (start >= end) {
 738                 printf("Error: Frame range for Sampled F-Curve creation is inappropriate \n");
 739                 return;
 740         }
 741
 742         /* set up sample data */
 743         fpt= new_fpt= MEM_callocN(sizeof(FPoint)*(end-start+1), "FPoint Samples");
 744
 745         /* use the sampling callback at 1-frame intervals from start to end frames */
 746         for (cfra= start; cfra <= end; cfra++, fpt++) {
 747                 fpt->vec[0]= (float)cfra;
 748                 fpt->vec[1]= sample_cb(fcu, data, (float)cfra);
 749         }
 750
 751         /* free any existing sample/keyframe data on curve  */
 752         if (fcu->bezt) MEM_freeN(fcu->bezt);
 753         if (fcu->fpt) MEM_freeN(fcu->fpt);
 754
 755         /* store the samples */
 756         fcu->bezt= NULL;
 757         fcu->fpt= new_fpt;
 758         fcu->totvert= end - start + 1;
 759 }
 760
 761 /* ***************************** F-Curve Sanity ********************************* */
 762 /* The functions here are used in various parts of Blender, usually after some editing
 763  * of keyframe data has occurred. They ensure that keyframe data is properly ordered and
 764  * that the handles are correctly
 765  */
 766
 767 /* This function recalculates the handles of an F-Curve
 768  * If the BezTriples have been rearranged, sort them first before using this.
 769  */
 770 void calchandles_fcurve (FCurve *fcu)
 771 {
 772         BezTriple *bezt, *prev, *next;
 773         int a= fcu->totvert;
 774
 775         /* Error checking:
 776          *      - need at least two points
 777          *      - need bezier keys
 778          *      - only bezier-interpolation has handles (for now)
 779          */
 780         if (ELEM(NULL, fcu, fcu->bezt) || (a < 2) /*|| ELEM(fcu->ipo, BEZT_IPO_CONST, BEZT_IPO_LIN)*/)
 781                 return;
 782
 783         /* get initial pointers */
 784         bezt= fcu->bezt;
 785         prev= NULL;
 786         next= (bezt + 1);
 787
 788         /* loop over all beztriples, adjusting handles */
 789         while (a--) {
 790                 /* clamp timing of handles to be on either side of beztriple */
 791                 if (bezt->vec[0][0] > bezt->vec[1][0]) bezt->vec[0][0]= bezt->vec[1][0];
 792                 if (bezt->vec[2][0] < bezt->vec[1][0]) bezt->vec[2][0]= bezt->vec[1][0];
 793
 794                 /* calculate auto-handles */
 795                 if (fcu->flag & FCURVE_AUTO_HANDLES)
 796                         calchandleNurb(bezt, prev, next, 2);    /* 2==special autohandle && keep extrema horizontal */
 797                 else
 798                         calchandleNurb(bezt, prev, next, 1);    /* 1==special autohandle */
 799
 800                 /* for automatic ease in and out */
 801                 if ((bezt->h1==HD_AUTO) && (bezt->h2==HD_AUTO)) {
 802                         /* only do this on first or last beztriple */
 803                         if ((a == 0) || (a == fcu->totvert-1)) {
 804                                 /* set both handles to have same horizontal value as keyframe */
 805                                 if (fcu->extend == FCURVE_EXTRAPOLATE_CONSTANT) {
 806                                         bezt->vec[0][1]= bezt->vec[2][1]= bezt->vec[1][1];
 807                                 }
 808                         }
 809                 }
 810
 811                 /* advance pointers for next iteration */
 812                 prev= bezt;
 813                 if (a == 1) next= NULL;
 814                 else next++;
 815                 bezt++;
 816         }
 817 }
 818
 819 /* Use when F-Curve with handles has changed
 820  * It treats all BezTriples with the following rules:
 821  *  - PHASE 1: do types have to be altered?
 822  *              -> Auto handles: become aligned when selection status is NOT(000 || 111)
 823  *              -> Vector handles: become 'nothing' when (one half selected AND other not)
 824  *  - PHASE 2: recalculate handles
 825 */
 826 void testhandles_fcurve (FCurve *fcu)
 827 {
 828         BezTriple *bezt;
 829         unsigned int a;
 830
 831         /* only beztriples have handles (bpoints don't though) */
 832         if ELEM(NULL, fcu, fcu->bezt)
 833                 return;
 834
 835         /* loop over beztriples */
 836         for (a=0, bezt=fcu->bezt; a < fcu->totvert; a++, bezt++) {
 837                 short flag= 0;
 838
 839                 /* flag is initialised as selection status
 840                  * of beztriple control-points (labelled 0,1,2)
 841                  */
 842                 if (bezt->f1 & SELECT) flag |= (1<<0); // == 1
 843                 if (bezt->f2 & SELECT) flag |= (1<<1); // == 2
 844                 if (bezt->f3 & SELECT) flag |= (1<<2); // == 4
 845
 846                 /* one or two handles selected only */
 847                 if (ELEM(flag, 0, 7)==0) {
 848                         /* auto handles become aligned */
 849                         if (bezt->h1==HD_AUTO)
 850                                 bezt->h1= HD_ALIGN;
 851                         if (bezt->h2==HD_AUTO)
 852                                 bezt->h2= HD_ALIGN;
 853
 854                         /* vector handles become 'free' when only one half selected */
 855                         if (bezt->h1==HD_VECT) {
 856                                 /* only left half (1 or 2 or 1+2) */
 857                                 if (flag < 4)
 858                                         bezt->h1= 0;
 859                         }
 860                         if (bezt->h2==HD_VECT) {
 861                                 /* only right half (4 or 2+4) */
 862                                 if (flag > 3)
 863                                         bezt->h2= 0;
 864                         }
 865                 }
 866         }
 867
 868         /* recalculate handles */
 869         calchandles_fcurve(fcu);
 870 }
 871
 872 /* This function sorts BezTriples so that they are arranged in chronological order,
 873  * as tools working on F-Curves expect that the BezTriples are in order.
 874  */
 875 void sort_time_fcurve (FCurve *fcu)
 876 {
 877         short ok= 1;
 878
 879         /* keep adjusting order of beztriples until nothing moves (bubble-sort) */
 880         while (ok) {
 881                 ok= 0;
 882
 883                 /* currently, will only be needed when there are beztriples */
 884                 if (fcu->bezt) {
 885                         BezTriple *bezt;
 886                         unsigned int a;
 887
 888                         /* loop over ALL points to adjust position in array and recalculate handles */
 889                         for (a=0, bezt=fcu->bezt; a < fcu->totvert; a++, bezt++) {
 890                                 /* check if thee's a next beztriple which we could try to swap with current */
 891                                 if (a < (fcu->totvert-1)) {
 892                                         /* swap if one is after the other (and indicate that order has changed) */
 893                                         if (bezt->vec[1][0] > (bezt+1)->vec[1][0]) {
 894                                                 SWAP(BezTriple, *bezt, *(bezt+1));
 895                                                 ok= 1;
 896                                         }
 897
 898                                         /* if either one of both of the points exceeds crosses over the keyframe time... */
 899                                         if ( (bezt->vec[0][0] > bezt->vec[1][0]) && (bezt->vec[2][0] < bezt->vec[1][0]) ) {
 900                                                 /* swap handles if they have switched sides for some reason */
 901                                                 SWAP(float, bezt->vec[0][0], bezt->vec[2][0]);
 902                                                 SWAP(float, bezt->vec[0][1], bezt->vec[2][1]);
 903                                         }
 904                                         else {
 905                                                 /* clamp handles */
 906                                                 if (bezt->vec[0][0] > bezt->vec[1][0])
 907                                                         bezt->vec[0][0]= bezt->vec[1][0];
 908                                                 if (bezt->vec[2][0] < bezt->vec[1][0])
 909                                                         bezt->vec[2][0]= bezt->vec[1][0];
 910                                         }
 911                                 }
 912                         }
 913                 }
 914         }
 915 }
 916
 917 /* This function tests if any BezTriples are out of order, thus requiring a sort */
 918 short test_time_fcurve (FCurve *fcu)
 919 {
 920         unsigned int a;
 921
 922         /* sanity checks */
 923         if (fcu == NULL)
 924                 return 0;
 925
 926         /* currently, only need to test beztriples */
 927         if (fcu->bezt) {
 928                 BezTriple *bezt;
 929
 930                 /* loop through all BezTriples, stopping when one exceeds the one after it */
 931                 for (a=0, bezt= fcu->bezt; a < (fcu->totvert - 1); a++, bezt++) {
 932                         if (bezt->vec[1][0] > (bezt+1)->vec[1][0])
 933                                 return 1;
 934                 }
 935         }
 936         else if (fcu->fpt) {
 937                 FPoint *fpt;
 938
 939                 /* loop through all FPoints, stopping when one exceeds the one after it */
 940                 for (a=0, fpt= fcu->fpt; a < (fcu->totvert - 1); a++, fpt++) {
 941                         if (fpt->vec[0] > (fpt+1)->vec[0])
 942                                 return 1;
 943                 }
 944         }
 945
 946         /* none need any swapping */
 947         return 0;
 948 }
 949
 950 /* ***************************** Drivers ********************************* */
 951
 952 /* Driver Variables --------------------------- */
 953
 954 /* TypeInfo for Driver Variables (dvti) */
 955 typedef struct DriverVarTypeInfo {
 956         /* evaluation callback */
 957         float (*get_value)(ChannelDriver *driver, DriverVar *dvar);
 958
 959         /* allocation of target slots */
 960         int num_targets;                                                /* number of target slots required */
 961         const char *target_names[MAX_DRIVER_TARGETS];   /* UI names that should be given to the slots */
 962         int target_flags[MAX_DRIVER_TARGETS];   /* flags defining the requirements for each slot */
 963 } DriverVarTypeInfo;
 964
 965 /* Macro to begin definitions */
 966 #define BEGIN_DVAR_TYPEDEF(type) \
 967         {
 968
 969 /* Macro to end definitions */
 970 #define END_DVAR_TYPEDEF \
 971         }
 972
 973 /* ......... */
 974
 975 static ID *dtar_id_ensure_proxy_from(ID *id)
 976 {
 977         if (id && GS(id->name)==ID_OB && ((Object *)id)->proxy_from)
 978                 return (ID *)(((Object *)id)->proxy_from);
 979         return id;
 980 }
 981
 982 /* Helper function to obtain a value using RNA from the specified source (for evaluating drivers) */
 983 static float dtar_get_prop_val (ChannelDriver *driver, DriverTarget *dtar)
 984 {
 985         PointerRNA id_ptr, ptr;
 986         PropertyRNA *prop;
 987         ID *id;
 988         int index;
 989         float value= 0.0f;
 990
 991         /* sanity check */
 992         if ELEM(NULL, driver, dtar)
 993                 return 0.0f;
 994
 995         id= dtar_id_ensure_proxy_from(dtar->id);
 996
 997         /* error check for missing pointer... */
 998         // TODO: tag the specific target too as having issues
 999         if (id == NULL) {
1000                 printf("Error: driver has an invalid target to use \n");
1001                 if (G.f & G_DEBUG) printf("\tpath = %s\n", dtar->rna_path);
1002                 driver->flag |= DRIVER_FLAG_INVALID;
1003                 return 0.0f;
1004         }
1005
1006         /* get RNA-pointer for the ID-block given in target */
1007         RNA_id_pointer_create(id, &id_ptr);
1008
1009         /* get property to read from, and get value as appropriate */
1010         if (RNA_path_resolve_full(&id_ptr, dtar->rna_path, &ptr, &prop, &index)) {
1011                 if(RNA_property_array_check(&ptr, prop)) {
1012                         /* array */
1013                         if (index < RNA_property_array_length(&ptr, prop)) {
1014                                 switch (RNA_property_type(prop)) {
1015                                 case PROP_BOOLEAN:
1016                                         value= (float)RNA_property_boolean_get_index(&ptr, prop, index);
1017                                         break;
1018                                 case PROP_INT:
1019                                         value= (float)RNA_property_int_get_index(&ptr, prop, index);
1020                                         break;
1021                                 case PROP_FLOAT:
1022                                         value= RNA_property_float_get_index(&ptr, prop, index);
1023                                         break;
1024                                 default:
1025                                         break;
1026                                 }
1027                         }
1028                 }
1029                 else {
1030                         /* not an array */
1031                         switch (RNA_property_type(prop)) {
1032                         case PROP_BOOLEAN:
1033                                 value= (float)RNA_property_boolean_get(&ptr, prop);
1034                                 break;
1035                         case PROP_INT:
1036                                 value= (float)RNA_property_int_get(&ptr, prop);
1037                                 break;
1038                         case PROP_FLOAT:
1039                                 value= RNA_property_float_get(&ptr, prop);
1040                                 break;
1041                         case PROP_ENUM:
1042                                 value= (float)RNA_property_enum_get(&ptr, prop);
1043                                 break;
1044                         default:
1045                                 break;
1046                         }
1047                 }
1048
1049         }
1050         else {
1051                 if (G.f & G_DEBUG)
1052                         printf("Driver Evaluation Error: cannot resolve target for %s -> %s \n", id->name, dtar->rna_path);
1053
1054                 driver->flag |= DRIVER_FLAG_INVALID;
1055                 return 0.0f;
1056         }
1057
1058         return value;
1059 }
1060
1061 /* Helper function to obtain a pointer to a Pose Channel (for evaluating drivers) */
1062 static bPoseChannel *dtar_get_pchan_ptr (ChannelDriver *driver, DriverTarget *dtar)
1063 {
1064         ID *id;
1065         /* sanity check */
1066         if ELEM(NULL, driver, dtar)
1067                 return NULL;
1068
1069         id= dtar_id_ensure_proxy_from(dtar->id);
1070
1071         /* check if the ID here is a valid object */
1072         if (id && GS(id->name)) {
1073                 Object *ob= (Object *)id;
1074
1075                 /* get pose, and subsequently, posechannel */
1076                 return get_pose_channel(ob->pose, dtar->pchan_name);
1077         }
1078         else {
1079                 /* cannot find a posechannel this way */
1080                 return NULL;
1081         }
1082 }
1083
1084 /* ......... */
1085
1086 /* evaluate 'single prop' driver variable */
1087 static float dvar_eval_singleProp (ChannelDriver *driver, DriverVar *dvar)
1088 {
1089         /* just evaluate the first target slot */
1090         return dtar_get_prop_val(driver, &dvar->targets[0]);
1091 }
1092
1093 /* evaluate 'rotation difference' driver variable */
1094 static float dvar_eval_rotDiff (ChannelDriver *driver, DriverVar *dvar)
1095 {
1096         bPoseChannel *pchan, *pchan2;
1097         float q1[4], q2[4], quat[4], angle;
1098
1099         /* get pose channels, and check if we've got two */
1100         pchan= dtar_get_pchan_ptr(driver, &dvar->targets[0]);
1101         pchan2= dtar_get_pchan_ptr(driver, &dvar->targets[1]);
1102
1103         if (ELEM(NULL, pchan, pchan2)) {
1104                 /* disable this driver, since it doesn't work correctly... */
1105                 driver->flag |= DRIVER_FLAG_INVALID;
1106
1107                 /* check what the error was */
1108                 if ((pchan == NULL) && (pchan2 == NULL))
1109                         printf("Driver Evaluation Error: Rotational difference failed - first 2 targets invalid \n");
1110                 else if (pchan == NULL)
1111                         printf("Driver Evaluation Error: Rotational difference failed - first target not valid PoseChannel \n");
1112                 else if (pchan2 == NULL)
1113                         printf("Driver Evaluation Error: Rotational difference failed - second target not valid PoseChannel \n");
1114
1115                 /* stop here... */
1116                 return 0.0f;
1117         }
1118
1119         /* use the final posed locations */
1120         mat4_to_quat(q1, pchan->pose_mat);
1121         mat4_to_quat(q2, pchan2->pose_mat);
1122
1123         invert_qt(q1);
1124         mul_qt_qtqt(quat, q1, q2);
1125         angle = 2.0f * (saacos(quat[0]));
1126         angle= ABS(angle);
1127
1128         return (angle > (float)M_PI) ? (float)((2.0f * (float)M_PI) - angle) : (float)(angle);
1129 }
1130
1131 /* evaluate 'location difference' driver variable */
1132 // TODO: this needs to take into account space conversions...
1133 static float dvar_eval_locDiff (ChannelDriver *driver, DriverVar *dvar)
1134 {
1135         float loc1[3] = {0.0f,0.0f,0.0f};
1136         float loc2[3] = {0.0f,0.0f,0.0f};
1137
1138         /* get two location values */
1139         // NOTE: for now, these are all just worldspace
1140         DRIVER_TARGETS_USED_LOOPER(dvar)
1141         {
1142                 /* get pointer to loc values to store in */
1143                 Object *ob= (Object *)dtar_id_ensure_proxy_from(dtar->id);
1144                 bPoseChannel *pchan;
1145                 float tmp_loc[3];
1146
1147                 /* check if this target has valid data */
1148                 if ((ob == NULL) || (GS(ob->id.name) != ID_OB)) {
1149                         /* invalid target, so will not have enough targets */
1150                         driver->flag |= DRIVER_FLAG_INVALID;
1151                         return 0.0f;
1152                 }
1153
1154                 /* try to get posechannel */
1155                 pchan= get_pose_channel(ob->pose, dtar->pchan_name);
1156
1157                 /* check if object or bone */
1158                 if (pchan) {
1159                         /* bone */
1160                         if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1161                                 if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1162                                         float mat[4][4];
1163
1164                                         /* extract transform just like how the constraints do it! */
1165                                         copy_m4_m4(mat, pchan->pose_mat);
1166                                         constraint_mat_convertspace(ob, pchan, mat, CONSTRAINT_SPACE_POSE, CONSTRAINT_SPACE_LOCAL);
1167
1168                                         /* ... and from that, we get our transform */
1169                                         VECCOPY(tmp_loc, mat[3]);
1170                                 }
1171                                 else {
1172                                         /* transform space (use transform values directly) */
1173                                         VECCOPY(tmp_loc, pchan->loc);
1174                                 }
1175                         }
1176                         else {
1177                                 /* convert to worldspace */
1178                                 VECCOPY(tmp_loc, pchan->pose_head);
1179                                 mul_m4_v3(ob->obmat, tmp_loc);
1180                         }
1181                 }
1182                 else {
1183                         /* object */
1184                         if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1185                                 if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1186                                         // XXX: this should practically be the same as transform space...
1187                                         float mat[4][4];
1188
1189                                         /* extract transform just like how the constraints do it! */
1190                                         copy_m4_m4(mat, ob->obmat);
1191                                         constraint_mat_convertspace(ob, NULL, mat, CONSTRAINT_SPACE_WORLD, CONSTRAINT_SPACE_LOCAL);
1192
1193                                         /* ... and from that, we get our transform */
1194                                         VECCOPY(tmp_loc, mat[3]);
1195                                 }
1196                                 else {
1197                                         /* transform space (use transform values directly) */
1198                                         VECCOPY(tmp_loc, ob->loc);
1199                                 }
1200                         }
1201                         else {
1202                                 /* worldspace */
1203                                 VECCOPY(tmp_loc, ob->obmat[3]);
1204                         }
1205                 }
1206
1207                 /* copy the location to the right place */
1208                 if (tarIndex) {
1209                         VECCOPY(loc2, tmp_loc);
1210                 }
1211                 else {
1212                         VECCOPY(loc1, tmp_loc);
1213                 }
1214         }
1215         DRIVER_TARGETS_LOOPER_END
1216
1217
1218         /* if we're still here, there should now be two targets to use,
1219          * so just take the length of the vector between these points
1220          */
1221         return len_v3v3(loc1, loc2);
1222 }
1223
1224 /* evaluate 'transform channel' driver variable */
1225 static float dvar_eval_transChan (ChannelDriver *driver, DriverVar *dvar)
1226 {
1227         DriverTarget *dtar= &dvar->targets[0];
1228         Object *ob= (Object *)dtar_id_ensure_proxy_from(dtar->id);
1229         bPoseChannel *pchan;
1230         float mat[4][4];
1231         float oldEul[3] = {0.0f,0.0f,0.0f};
1232         short useEulers=0, rotOrder=ROT_MODE_EUL;
1233
1234         /* check if this target has valid data */
1235         if ((ob == NULL) || (GS(ob->id.name) != ID_OB)) {
1236                 /* invalid target, so will not have enough targets */
1237                 driver->flag |= DRIVER_FLAG_INVALID;
1238                 return 0.0f;
1239         }
1240
1241         /* try to get posechannel */
1242         pchan= get_pose_channel(ob->pose, dtar->pchan_name);
1243
1244         /* check if object or bone, and get transform matrix accordingly
1245          *      - "useEulers" code is used to prevent the problems associated with non-uniqueness
1246          *        of euler decomposition from matrices [#20870]
1247          *      - localspace is for [#21384], where parent results are not wanted
1248          *        but local-consts is for all the common "corrective-shapes-for-limbs" situations
1249          */
1250         if (pchan) {
1251                 /* bone */
1252                 if (pchan->rotmode > 0) {
1253                         VECCOPY(oldEul, pchan->eul);
1254                         rotOrder= pchan->rotmode;
1255                         useEulers = 1;
1256                 }
1257
1258                 if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1259                         if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1260                                 /* just like how the constraints do it! */
1261                                 copy_m4_m4(mat, pchan->pose_mat);
1262                                 constraint_mat_convertspace(ob, pchan, mat, CONSTRAINT_SPACE_POSE, CONSTRAINT_SPACE_LOCAL);
1263                         }
1264                         else {
1265                                 /* specially calculate local matrix, since chan_mat is not valid
1266                                  * since it stores delta transform of pose_mat so that deforms work
1267                                  * so it cannot be used here for "transform" space
1268                                  */
1269                                 pchan_to_mat4(pchan, mat);
1270                         }
1271                 }
1272                 else {
1273                         /* worldspace matrix */
1274                         mul_m4_m4m4(mat, pchan->pose_mat, ob->obmat);
1275                 }
1276         }
1277         else {
1278                 /* object */
1279                 if (ob->rotmode > 0) {
1280                         VECCOPY(oldEul, ob->rot);
1281                         rotOrder= ob->rotmode;
1282                         useEulers = 1;
1283                 }
1284
1285                 if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1286                         if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1287                                 /* just like how the constraints do it! */
1288                                 copy_m4_m4(mat, ob->obmat);
1289                                 constraint_mat_convertspace(ob, NULL, mat, CONSTRAINT_SPACE_WORLD, CONSTRAINT_SPACE_LOCAL);
1290                         }
1291                         else {
1292                                 /* transforms to matrix */
1293                                 object_to_mat4(ob, mat);
1294                         }
1295                 }
1296                 else {
1297                         /* worldspace matrix - just the good-old one */
1298                         copy_m4_m4(mat, ob->obmat);
1299                 }
1300         }
1301
1302         /* check which transform */
1303         if (dtar->transChan >= MAX_DTAR_TRANSCHAN_TYPES) {
1304                 /* not valid channel */
1305                 return 0.0f;
1306         }
1307         else if (dtar->transChan >= DTAR_TRANSCHAN_SCALEX) {
1308                 /* extract scale, and choose the right axis */
1309                 float scale[3];
1310
1311                 mat4_to_size(scale, mat);
1312                 return scale[dtar->transChan - DTAR_TRANSCHAN_SCALEX];
1313         }
1314         else if (dtar->transChan >= DTAR_TRANSCHAN_ROTX) {
1315                 /* extract rotation as eulers (if needed)
1316                  *      - definitely if rotation order isn't eulers already
1317                  *      - if eulers, then we have 2 options:
1318                  *              a) decompose transform matrix as required, then try to make eulers from
1319                  *                 there compatible with original values
1320                  *              b) [NOT USED] directly use the original values (no decomposition)
1321                  *                      - only an option for "transform space", if quality is really bad with a)
1322                  */
1323                 float eul[3];
1324
1325                 mat4_to_eulO(eul, rotOrder, mat);
1326
1327                 if (useEulers) {
1328                         compatible_eul(eul, oldEul);
1329                 }
1330
1331                 return eul[dtar->transChan - DTAR_TRANSCHAN_ROTX];
1332         }
1333         else {
1334                 /* extract location and choose right axis */
1335                 return mat[3][dtar->transChan];
1336         }
1337 }
1338
1339 /* ......... */
1340
1341 /* Table of Driver Varaiable Type Info Data */
1342 static DriverVarTypeInfo dvar_types[MAX_DVAR_TYPES] = {
1343         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_SINGLE_PROP)
1344                 dvar_eval_singleProp, /* eval callback */
1345                 1, /* number of targets used */
1346                 {"Property"}, /* UI names for targets */
1347                 {0} /* flags */
1348         END_DVAR_TYPEDEF,
1349
1350         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_ROT_DIFF)
1351                 dvar_eval_rotDiff, /* eval callback */
1352                 2, /* number of targets used */
1353                 {"Bone 1", "Bone 2"}, /* UI names for targets */
1354                 {DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY, DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY} /* flags */
1355         END_DVAR_TYPEDEF,
1356
1357         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_LOC_DIFF)
1358                 dvar_eval_locDiff, /* eval callback */
1359                 2, /* number of targets used */
1360                 {"Object/Bone 1", "Object/Bone 2"}, /* UI names for targets */
1361                 {DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY, DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY} /* flags */
1362         END_DVAR_TYPEDEF,
1363
1364         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_TRANSFORM_CHAN)
1365                 dvar_eval_transChan, /* eval callback */
1366                 1, /* number of targets used */
1367                 {"Object/Bone"}, /* UI names for targets */
1368                 {DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY} /* flags */
1369         END_DVAR_TYPEDEF,
1370 };
1371
1372 /* Get driver variable typeinfo */
1373 static DriverVarTypeInfo *get_dvar_typeinfo (int type)
1374 {
1375         /* check if valid type */
1376         if ((type >= 0) && (type < MAX_DVAR_TYPES))
1377                 return &dvar_types[type];
1378         else
1379                 return NULL;
1380 }
1381
1382 /* Driver API --------------------------------- */
1383
1384 /* This frees the driver variable itself */
1385 void driver_free_variable (ChannelDriver *driver, DriverVar *dvar)
1386 {
1387         /* sanity checks */
1388         if (dvar == NULL)
1389                 return;
1390
1391         /* free target vars
1392          *      - need to go over all of them, not just up to the ones that are used
1393          *        currently, since there may be some lingering RNA paths from
1394          *        previous users needing freeing
1395          */
1396         DRIVER_TARGETS_LOOPER(dvar)
1397         {
1398                 /* free RNA path if applicable */
1399                 if (dtar->rna_path)
1400                         MEM_freeN(dtar->rna_path);
1401         }
1402         DRIVER_TARGETS_LOOPER_END
1403
1404         /* remove the variable from the driver */
1405         if (driver)
1406                 BLI_freelinkN(&driver->variables, dvar);
1407         else
1408                 MEM_freeN(dvar);
1409
1410 #ifdef WITH_PYTHON
1411         /* since driver variables are cached, the expression needs re-compiling too */
1412         if(driver->type==DRIVER_TYPE_PYTHON)
1413                 driver->flag |= DRIVER_FLAG_RENAMEVAR;
1414 #endif
1415 }
1416
1417 /* Change the type of driver variable */
1418 void driver_change_variable_type (DriverVar *dvar, int type)
1419 {
1420         DriverVarTypeInfo *dvti= get_dvar_typeinfo(type);
1421
1422         /* sanity check */
1423         if (ELEM(NULL, dvar, dvti))
1424                 return;
1425
1426         /* set the new settings */
1427         dvar->type= type;
1428         dvar->num_targets= dvti->num_targets;
1429
1430         /* make changes to the targets based on the defines for these types
1431          * NOTE: only need to make sure the ones we're using here are valid...
1432          */
1433         DRIVER_TARGETS_USED_LOOPER(dvar)
1434         {
1435                 int flags = dvti->target_flags[tarIndex];
1436
1437                 /* store the flags */
1438                 dtar->flag = flags;
1439
1440                 /* object ID types only, or idtype not yet initialised*/
1441                 if ((flags & DTAR_FLAG_ID_OB_ONLY) || (dtar->idtype == 0))
1442                         dtar->idtype= ID_OB;
1443         }
1444         DRIVER_TARGETS_LOOPER_END
1445 }
1446
1447 /* Add a new driver variable */
1448 DriverVar *driver_add_new_variable (ChannelDriver *driver)
1449 {
1450         DriverVar *dvar;
1451
1452         /* sanity checks */
1453         if (driver == NULL)
1454                 return NULL;
1455
1456         /* make a new variable */
1457         dvar= MEM_callocN(sizeof(DriverVar), "DriverVar");
1458         BLI_addtail(&driver->variables, dvar);
1459
1460         /* give the variable a 'unique' name */
1461         strcpy(dvar->name, "var");
1462         BLI_uniquename(&driver->variables, dvar, "var", '_', offsetof(DriverVar, name), sizeof(dvar->name));
1463
1464         /* set the default type to 'single prop' */
1465         driver_change_variable_type(dvar, DVAR_TYPE_SINGLE_PROP);
1466
1467 #ifdef WITH_PYTHON
1468         /* since driver variables are cached, the expression needs re-compiling too */
1469         if (driver->type==DRIVER_TYPE_PYTHON)
1470                 driver->flag |= DRIVER_FLAG_RENAMEVAR;
1471 #endif
1472
1473         /* return the target */
1474         return dvar;
1475 }
1476
1477 /* This frees the driver itself */
1478 void fcurve_free_driver(FCurve *fcu)
1479 {
1480         ChannelDriver *driver;
1481         DriverVar *dvar, *dvarn;
1482
1483         /* sanity checks */
1484         if ELEM(NULL, fcu, fcu->driver)
1485                 return;
1486         driver= fcu->driver;
1487
1488         /* free driver targets */
1489         for (dvar= driver->variables.first; dvar; dvar= dvarn) {
1490                 dvarn= dvar->next;
1491                 driver_free_variable(driver, dvar);
1492         }
1493
1494 #ifdef WITH_PYTHON
1495         /* free compiled driver expression */
1496         if (driver->expr_comp)
1497                 BPY_DECREF(driver->expr_comp);
1498 #endif
1499
1500         /* free driver itself, then set F-Curve's point to this to NULL (as the curve may still be used) */
1501         MEM_freeN(driver);
1502         fcu->driver= NULL;
1503 }
1504
1505 /* This makes a copy of the given driver */
1506 ChannelDriver *fcurve_copy_driver (ChannelDriver *driver)
1507 {
1508         ChannelDriver *ndriver;
1509         DriverVar *dvar;
1510
1511         /* sanity checks */
1512         if (driver == NULL)
1513                 return NULL;
1514
1515         /* copy all data */
1516         ndriver= MEM_dupallocN(driver);
1517         ndriver->expr_comp= NULL;
1518
1519         /* copy variables */
1520         ndriver->variables.first= ndriver->variables.last= NULL;
1521         BLI_duplicatelist(&ndriver->variables, &driver->variables);
1522
1523         for (dvar= ndriver->variables.first; dvar; dvar= dvar->next) {
1524                 /* need to go over all targets so that we don't leave any dangling paths */
1525                 DRIVER_TARGETS_LOOPER(dvar)
1526                 {
1527                         /* make a copy of target's rna path if available */
1528                         if (dtar->rna_path)
1529                                 dtar->rna_path = MEM_dupallocN(dtar->rna_path);
1530                 }
1531                 DRIVER_TARGETS_LOOPER_END
1532         }
1533
1534         /* return the new driver */
1535         return ndriver;
1536 }
1537
1538 /* Driver Evaluation -------------------------- */
1539
1540 /* Evaluate a Driver Variable to get a value that contributes to the final */
1541 float driver_get_variable_value (ChannelDriver *driver, DriverVar *dvar)
1542 {
1543         DriverVarTypeInfo *dvti;
1544
1545         /* sanity check */
1546         if (ELEM(NULL, driver, dvar))
1547                 return 0.0f;
1548
1549         /* call the relevant callbacks to get the variable value
1550          * using the variable type info, storing the obtained value
1551          * in dvar->curval so that drivers can be debugged
1552          */
1553         dvti= get_dvar_typeinfo(dvar->type);
1554
1555         if (dvti && dvti->get_value)
1556                 dvar->curval= dvti->get_value(driver, dvar);
1557         else
1558                 dvar->curval= 0.0f;
1559
1560         return dvar->curval;
1561 }
1562
1563 /* Evaluate an Channel-Driver to get a 'time' value to use instead of "evaltime"
1564  *      - "evaltime" is the frame at which F-Curve is being evaluated
1565  *      - has to return a float value
1566  */
1567 static float evaluate_driver (ChannelDriver *driver, float UNUSED(evaltime))
1568 {
1569         DriverVar *dvar;
1570
1571         /* check if driver can be evaluated */
1572         if (driver->flag & DRIVER_FLAG_INVALID)
1573                 return 0.0f;
1574
1575         switch (driver->type) {
1576                 case DRIVER_TYPE_AVERAGE: /* average values of driver targets */
1577                 case DRIVER_TYPE_SUM: /* sum values of driver targets */
1578                 {
1579                         /* check how many variables there are first (i.e. just one?) */
1580                         if (driver->variables.first == driver->variables.last) {
1581                                 /* just one target, so just use that */
1582                                 dvar= driver->variables.first;
1583                                 driver->curval= driver_get_variable_value(driver, dvar);
1584                         }
1585                         else {
1586                                 /* more than one target, so average the values of the targets */
1587                                 float value = 0.0f;
1588                                 int tot = 0;
1589
1590                                 /* loop through targets, adding (hopefully we don't get any overflow!) */
1591                                 for (dvar= driver->variables.first; dvar; dvar=dvar->next) {
1592                                         value += driver_get_variable_value(driver, dvar);
1593                                         tot++;
1594                                 }
1595
1596                                 /* perform operations on the total if appropriate */
1597                                 if (driver->type == DRIVER_TYPE_AVERAGE)
1598                                         driver->curval= (value / (float)tot);
1599                                 else
1600                                         driver->curval= value;
1601                         }
1602                 }
1603                         break;
1604
1605                 case DRIVER_TYPE_MIN: /* smallest value */
1606                 case DRIVER_TYPE_MAX: /* largest value */
1607                 {
1608                         float value = 0.0f;
1609
1610                         /* loop through the variables, getting the values and comparing them to existing ones */
1611                         for (dvar= driver->variables.first; dvar; dvar= dvar->next) {
1612                                 /* get value */
1613                                 float tmp_val= driver_get_variable_value(driver, dvar);
1614
1615                                 /* store this value if appropriate */
1616                                 if (dvar->prev) {
1617                                         /* check if greater/smaller than the baseline */
1618                                         if (driver->type == DRIVER_TYPE_MAX) {
1619                                                 /* max? */
1620                                                 if (tmp_val > value)
1621                                                         value= tmp_val;
1622                                         }
1623                                         else {
1624                                                 /* min? */
1625                                                 if (tmp_val < value)
1626                                                         value= tmp_val;
1627                                         }
1628                                 }
1629                                 else {
1630                                         /* first item - make this the baseline for comparisons */
1631                                         value= tmp_val;
1632                                 }
1633                         }
1634
1635                         /* store value in driver */
1636                         driver->curval= value;
1637                 }
1638                         break;
1639
1640                 case DRIVER_TYPE_PYTHON: /* expression */
1641                 {
1642 #ifdef WITH_PYTHON
1643                         /* check for empty or invalid expression */
1644                         if ( (driver->expression[0] == '\0') ||
1645                                  (driver->flag & DRIVER_FLAG_INVALID) )
1646                         {
1647                                 driver->curval= 0.0f;
1648                         }
1649                         else
1650                         {
1651                                 /* this evaluates the expression using Python,and returns its result:
1652                                  *      - on errors it reports, then returns 0.0f
1653                                  */
1654                                 driver->curval= BPY_driver_exec(driver);
1655                         }
1656 #endif /* WITH_PYTHON*/
1657                 }
1658                         break;
1659
1660                 default:
1661                 {
1662                         /* special 'hack' - just use stored value
1663                          *      This is currently used as the mechanism which allows animated settings to be able
1664                          *      to be changed via the UI.
1665                          */
1666                 }
1667         }
1668
1669         /* return value for driver */
1670         return driver->curval;
1671 }
1672
1673 /* ***************************** Curve Calculations ********************************* */
1674
1675 /* The total length of the handles is not allowed to be more
1676  * than the horizontal distance between (v1-v4).
1677  * This is to prevent curve loops.
1678 */
1679 void correct_bezpart (float *v1, float *v2, float *v3, float *v4)
1680 {
1681         float h1[2], h2[2], len1, len2, len, fac;
1682
1683         /* calculate handle deltas */
1684         h1[0]= v1[0] - v2[0];
1685         h1[1]= v1[1] - v2[1];
1686
1687         h2[0]= v4[0] - v3[0];
1688         h2[1]= v4[1] - v3[1];
1689
1690         /* calculate distances:
1691          *      - len   = span of time between keyframes
1692          *      - len1  = length of handle of start key
1693          *      - len2  = length of handle of end key
1694          */
1695         len= v4[0]- v1[0];
1696         len1= (float)fabs(h1[0]);
1697         len2= (float)fabs(h2[0]);
1698
1699         /* if the handles have no length, no need to do any corrections */
1700         if ((len1+len2) == 0.0f)
1701                 return;
1702
1703         /* the two handles cross over each other, so force them
1704          * apart using the proportion they overlap
1705          */
1706         if ((len1+len2) > len) {
1707                 fac= len / (len1+len2);
1708
1709                 v2[0]= (v1[0] - fac*h1[0]);
1710                 v2[1]= (v1[1] - fac*h1[1]);
1711
1712                 v3[0]= (v4[0] - fac*h2[0]);
1713                 v3[1]= (v4[1] - fac*h2[1]);
1714         }
1715 }
1716
1717 /* find root ('zero') */
1718 static int findzero (float x, float q0, float q1, float q2, float q3, float *o)
1719 {
1720         double c0, c1, c2, c3, a, b, c, p, q, d, t, phi;
1721         int nr= 0;
1722
1723         c0= q0 - x;
1724         c1= 3.0f * (q1 - q0);
1725         c2= 3.0f * (q0 - 2.0f*q1 + q2);
1726         c3= q3 - q0 + 3.0f * (q1 - q2);
1727
1728         if (c3 != 0.0) {
1729                 a= c2/c3;
1730                 b= c1/c3;
1731                 c= c0/c3;
1732                 a= a/3;
1733
1734                 p= b/3 - a*a;
1735                 q= (2*a*a*a - a*b + c) / 2;
1736                 d= q*q + p*p*p;
1737
1738                 if (d > 0.0) {
1739                         t= sqrt(d);
1740                         o[0]= (float)(sqrt3d(-q+t) + sqrt3d(-q-t) - a);
1741
1742                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
1743                         else return 0;
1744                 }
1745                 else if (d == 0.0) {
1746                         t= sqrt3d(-q);
1747                         o[0]= (float)(2*t - a);
1748
1749                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
1750                         o[nr]= (float)(-t-a);
1751
1752                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr+1;
1753                         else return nr;
1754                 }
1755                 else {
1756                         phi= acos(-q / sqrt(-(p*p*p)));
1757                         t= sqrt(-p);
1758                         p= cos(phi/3);
1759                         q= sqrt(3 - 3*p*p);
1760                         o[0]= (float)(2*t*p - a);
1761
1762                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
1763                         o[nr]= (float)(-t * (p + q) - a);
1764
1765                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) nr++;
1766                         o[nr]= (float)(-t * (p - q) - a);
1767
1768                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr+1;
1769                         else return nr;
1770                 }
1771         }
1772         else {
1773                 a=c2;
1774                 b=c1;
1775                 c=c0;
1776
1777                 if (a != 0.0) {
1778                         // discriminant
1779                         p= b*b - 4*a*c;
1780
1781                         if (p > 0) {
1782                                 p= sqrt(p);
1783                                 o[0]= (float)((-b-p) / (2 * a));
1784
1785                                 if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
1786                                 o[nr]= (float)((-b+p)/(2*a));
1787
1788                                 if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr+1;
1789                                 else return nr;
1790                         }
1791                         else if (p == 0) {
1792                                 o[0]= (float)(-b / (2 * a));
1793                                 if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
1794                                 else return 0;
1795                         }
1796                 }
1797                 else if (b != 0.0) {
1798                         o[0]= (float)(-c/b);
1799
1800                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
1801                         else return 0;
1802                 }
1803                 else if (c == 0.0) {
1804                         o[0]= 0.0;
1805                         return 1;
1806                 }
1807
1808                 return 0;
1809         }
1810 }
1811
1812 static void berekeny (float f1, float f2, float f3, float f4, float *o, int b)
1813 {
1814         float t, c0, c1, c2, c3;
1815         int a;
1816
1817         c0= f1;
1818         c1= 3.0f * (f2 - f1);
1819         c2= 3.0f * (f1 - 2.0f*f2 + f3);
1820         c3= f4 - f1 + 3.0f * (f2 - f3);
1821
1822         for (a=0; a < b; a++) {
1823                 t= o[a];
1824                 o[a]= c0 + t*c1 + t*t*c2 + t*t*t*c3;
1825         }
1826 }
1827
1828 #if 0
1829 static void berekenx (float *f, float *o, int b)
1830 {
1831         float t, c0, c1, c2, c3;
1832         int a;
1833
1834         c0= f[0];
1835         c1= 3.0f * (f[3] - f[0]);
1836         c2= 3.0f * (f[0] - 2.0f*f[3] + f[6]);
1837         c3= f[9] - f[0] + 3.0f * (f[3] - f[6]);
1838
1839         for (a=0; a < b; a++) {
1840                 t= o[a];
1841                 o[a]= c0 + t*c1 + t*t*c2 + t*t*t*c3;
1842         }
1843 }
1844 #endif
1845
1846
1847 /* -------------------------- */
1848
1849 /* Calculate F-Curve value for 'evaltime' using BezTriple keyframes */
1850 static float fcurve_eval_keyframes (FCurve *fcu, BezTriple *bezts, float evaltime)
1851 {
1852         BezTriple *bezt, *prevbezt, *lastbezt;
1853         float v1[2], v2[2], v3[2], v4[2], opl[32], dx, fac;
1854         unsigned int a;
1855         int b;
1856         float cvalue = 0.0f;
1857
1858         /* get pointers */
1859         a= fcu->totvert-1;
1860         prevbezt= bezts;
1861         bezt= prevbezt+1;
1862         lastbezt= prevbezt + a;
1863
1864         /* evaluation time at or past endpoints? */
1865         if (prevbezt->vec[1][0] >= evaltime)
1866         {
1867                 /* before or on first keyframe */
1868                 if ( (fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (prevbezt->ipo != BEZT_IPO_CONST) &&
1869                         !(fcu->flag & FCURVE_DISCRETE_VALUES) )
1870                 {
1871                         /* linear or bezier interpolation */
1872                         if (prevbezt->ipo==BEZT_IPO_LIN)
1873                         {
1874                                 /* Use the next center point instead of our own handle for
1875                                  * linear interpolated extrapolate
1876                                  */
1877                                 if (fcu->totvert == 1)
1878                                         cvalue= prevbezt->vec[1][1];
1879                                 else
1880                                 {
1881                                         bezt = prevbezt+1;
1882                                         dx= prevbezt->vec[1][0] - evaltime;
1883                                         fac= bezt->vec[1][0] - prevbezt->vec[1][0];
1884
1885                                         /* prevent division by zero */
1886                                         if (fac) {
1887                                                 fac= (bezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
1888                                                 cvalue= prevbezt->vec[1][1] - (fac * dx);
1889                                         }
1890                                         else
1891                                                 cvalue= prevbezt->vec[1][1];
1892                                 }
1893                         }
1894                         else
1895                         {
1896                                 /* Use the first handle (earlier) of first BezTriple to calculate the
1897                                  * gradient and thus the value of the curve at evaltime
1898                                  */
1899                                 dx= prevbezt->vec[1][0] - evaltime;
1900                                 fac= prevbezt->vec[1][0] - prevbezt->vec[0][0];
1901
1902                                 /* prevent division by zero */
1903                                 if (fac) {
1904                                         fac= (prevbezt->vec[1][1] - prevbezt->vec[0][1]) / fac;
1905                                         cvalue= prevbezt->vec[1][1] - (fac * dx);
1906                                 }
1907                                 else
1908                                         cvalue= prevbezt->vec[1][1];
1909                         }
1910                 }
1911                 else
1912                 {
1913                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation,
1914                          * so just extend first keyframe's value
1915                          */
1916                         cvalue= prevbezt->vec[1][1];
1917                 }
1918         }
1919         else if (lastbezt->vec[1][0] <= evaltime)
1920         {
1921                 /* after or on last keyframe */
1922                 if ( (fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (lastbezt->ipo != BEZT_IPO_CONST) &&
1923                         !(fcu->flag & FCURVE_DISCRETE_VALUES) )
1924                 {
1925                         /* linear or bezier interpolation */
1926                         if (lastbezt->ipo==BEZT_IPO_LIN)
1927                         {
1928                                 /* Use the next center point instead of our own handle for
1929                                  * linear interpolated extrapolate
1930                                  */
1931                                 if (fcu->totvert == 1)
1932                                         cvalue= lastbezt->vec[1][1];
1933                                 else
1934                                 {
1935                                         prevbezt = lastbezt - 1;
1936                                         dx= evaltime - lastbezt->vec[1][0];
1937                                         fac= lastbezt->vec[1][0] - prevbezt->vec[1][0];
1938
1939                                         /* prevent division by zero */
1940                                         if (fac) {
1941                                                 fac= (lastbezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
1942                                                 cvalue= lastbezt->vec[1][1] + (fac * dx);
1943                                         }
1944                                         else
1945                                                 cvalue= lastbezt->vec[1][1];
1946                                 }
1947                         }
1948                         else
1949                         {
1950                                 /* Use the gradient of the second handle (later) of last BezTriple to calculate the
1951                                  * gradient and thus the value of the curve at evaltime
1952                                  */
1953                                 dx= evaltime - lastbezt->vec[1][0];
1954                                 fac= lastbezt->vec[2][0] - lastbezt->vec[1][0];
1955
1956                                 /* prevent division by zero */
1957                                 if (fac) {
1958                                         fac= (lastbezt->vec[2][1] - lastbezt->vec[1][1]) / fac;
1959                                         cvalue= lastbezt->vec[1][1] + (fac * dx);
1960                                 }
1961                                 else
1962                                         cvalue= lastbezt->vec[1][1];
1963                         }
1964                 }
1965                 else
1966                 {
1967                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation,
1968                          * so just extend last keyframe's value
1969                          */
1970                         cvalue= lastbezt->vec[1][1];
1971                 }
1972         }
1973         else
1974         {
1975                 /* evaltime occurs somewhere in the middle of the curve */
1976                 for (a=0; prevbezt && bezt && (a < fcu->totvert-1); a++, prevbezt=bezt, bezt++)
1977                 {
1978                         /* use if the key is directly on the frame, rare cases this is needed else we get 0.0 instead. */
1979                         if(fabs(bezt->vec[1][0] - evaltime) < SMALL_NUMBER) {
1980                                 cvalue= bezt->vec[1][1];
1981                         }
1982                         /* evaltime occurs within the interval defined by these two keyframes */
1983                         else if ((prevbezt->vec[1][0] <= evaltime) && (bezt->vec[1][0] >= evaltime))
1984                         {
1985                                 /* value depends on interpolation mode */
1986                                 if ((prevbezt->ipo == BEZT_IPO_CONST) || (fcu->flag & FCURVE_DISCRETE_VALUES))
1987                                 {
1988                                         /* constant (evaltime not relevant, so no interpolation needed) */
1989                                         cvalue= prevbezt->vec[1][1];
1990                                 }
1991                                 else if (prevbezt->ipo == BEZT_IPO_LIN)
1992                                 {
1993                                         /* linear - interpolate between values of the two keyframes */
1994                                         fac= bezt->vec[1][0] - prevbezt->vec[1][0];
1995
1996                                         /* prevent division by zero */
1997                                         if (fac) {
1998                                                 fac= (evaltime - prevbezt->vec[1][0]) / fac;
1999                                                 cvalue= prevbezt->vec[1][1] + (fac * (bezt->vec[1][1] - prevbezt->vec[1][1]));
2000                                         }
2001                                         else
2002                                                 cvalue= prevbezt->vec[1][1];
2003                                 }
2004                                 else
2005                                 {
2006                                         /* bezier interpolation */
2007                                                 /* v1,v2 are the first keyframe and its 2nd handle */
2008                                         v1[0]= prevbezt->vec[1][0];
2009                                         v1[1]= prevbezt->vec[1][1];
2010                                         v2[0]= prevbezt->vec[2][0];
2011                                         v2[1]= prevbezt->vec[2][1];
2012                                                 /* v3,v4 are the last keyframe's 1st handle + the last keyframe */
2013                                         v3[0]= bezt->vec[0][0];
2014                                         v3[1]= bezt->vec[0][1];
2015                                         v4[0]= bezt->vec[1][0];
2016                                         v4[1]= bezt->vec[1][1];
2017
2018                                         /* adjust handles so that they don't overlap (forming a loop) */
2019                                         correct_bezpart(v1, v2, v3, v4);
2020
2021                                         /* try to get a value for this position - if failure, try another set of points */
2022                                         b= findzero(evaltime, v1[0], v2[0], v3[0], v4[0], opl);
2023                                         if (b) {
2024                                                 berekeny(v1[1], v2[1], v3[1], v4[1], opl, 1);
2025                                                 cvalue= opl[0];
2026                                                 break;
2027                                         }
2028                                 }
2029                         }
2030                 }
2031         }
2032
2033         /* return value */
2034         return cvalue;
2035 }
2036
2037 /* Calculate F-Curve value for 'evaltime' using FPoint samples */
2038 static float fcurve_eval_samples (FCurve *fcu, FPoint *fpts, float evaltime)
2039 {
2040         FPoint *prevfpt, *lastfpt, *fpt;
2041         float cvalue= 0.0f;
2042
2043         /* get pointers */
2044         prevfpt= fpts;
2045         lastfpt= prevfpt + fcu->totvert-1;
2046
2047         /* evaluation time at or past endpoints? */
2048         if (prevfpt->vec[0] >= evaltime) {
2049                 /* before or on first sample, so just extend value */
2050                 cvalue= prevfpt->vec[1];
2051         }
2052         else if (lastfpt->vec[0] <= evaltime) {
2053                 /* after or on last sample, so just extend value */
2054                 cvalue= lastfpt->vec[1];
2055         }
2056         else {
2057                 float t= (float)abs(evaltime - (int)evaltime);
2058
2059                 /* find the one on the right frame (assume that these are spaced on 1-frame intervals) */
2060                 fpt= prevfpt + (int)(evaltime - prevfpt->vec[0]);
2061
2062                 /* if not exactly on the frame, perform linear interpolation with the next one */
2063                 if (t != 0.0f)
2064                         cvalue= interpf(fpt->vec[1], (fpt+1)->vec[1], t);
2065                 else
2066                         cvalue= fpt->vec[1];
2067         }
2068
2069         /* return value */
2070         return cvalue;
2071 }
2072
2073 /* ***************************** F-Curve - Evaluation ********************************* */
2074
2075 /* Evaluate and return the value of the given F-Curve at the specified frame ("evaltime")
2076  * Note: this is also used for drivers
2077  */
2078 float evaluate_fcurve (FCurve *fcu, float evaltime)
2079 {
2080         float cvalue= 0.0f;
2081         float devaltime;
2082
2083         /* if there is a driver (only if this F-Curve is acting as 'driver'), evaluate it to find value to use as "evaltime"
2084          * since drivers essentially act as alternative input (i.e. in place of 'time') for F-Curves
2085          *      - this value will also be returned as the value of the 'curve', if there are no keyframes
2086          */
2087         if (fcu->driver) {
2088                 /* evaltime now serves as input for the curve */
2089                 evaltime= cvalue= evaluate_driver(fcu->driver, evaltime);
2090         }
2091
2092         /* evaluate modifiers which modify time to evaluate the base curve at */
2093         devaltime= evaluate_time_fmodifiers(&fcu->modifiers, fcu, cvalue, evaltime);
2094
2095         /* evaluate curve-data
2096          *      - 'devaltime' instead of 'evaltime', as this is the time that the last time-modifying
2097          *        F-Curve modifier on the stack requested the curve to be evaluated at
2098          */
2099         if (fcu->bezt)
2100                 cvalue= fcurve_eval_keyframes(fcu, fcu->bezt, devaltime);
2101         else if (fcu->fpt)
2102                 cvalue= fcurve_eval_samples(fcu, fcu->fpt, devaltime);
2103
2104         /* evaluate modifiers */
2105         evaluate_value_fmodifiers(&fcu->modifiers, fcu, &cvalue, evaltime);
2106
2107         /* if curve can only have integral values, perform truncation (i.e. drop the decimal part)
2108          * here so that the curve can be sampled correctly
2109          */
2110         if (fcu->flag & FCURVE_INT_VALUES)
2111                 cvalue= floorf(cvalue + 0.5f);
2112
2113         /* return evaluated value */
2114         return cvalue;
2115 }
2116
2117 /* Calculate the value of the given F-Curve at the given frame, and set its curval */
2118 void calculate_fcurve (FCurve *fcu, float ctime)
2119 {
2120         /* only calculate + set curval (overriding the existing value) if curve has
2121          * any data which warrants this...
2122          */
2123         if ( (fcu->totvert) || (fcu->driver && !(fcu->driver->flag & DRIVER_FLAG_INVALID)) ||
2124                  list_has_suitable_fmodifier(&fcu->modifiers, 0, FMI_TYPE_GENERATE_CURVE) )
2125         {
2126                 /* calculate and set curval (evaluates driver too if necessary) */
2127                 fcu->curval= evaluate_fcurve(fcu, ctime);
2128         }
2129 }
2130