source/blender/blenkernel/intern/fcurve.c

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