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_easing.h"
  49 #include "BLI_threads.h"
  50 #include "BLI_string_utils.h"
  51 #include "BLI_utildefines.h"
  52
  53 #include "BLT_translation.h"
  54
  55 #include "BKE_fcurve.h"
  56 #include "BKE_animsys.h"
  57 #include "BKE_action.h"
  58 #include "BKE_armature.h"
  59 #include "BKE_constraint.h"
  60 #include "BKE_context.h"
  61 #include "BKE_curve.h"
  62 #include "BKE_global.h"
  63 #include "BKE_object.h"
  64 #include "BKE_nla.h"
  65
  66 #include "RNA_access.h"
  67
  68 #ifdef WITH_PYTHON
  69 #include "BPY_extern.h"
  70 #endif
  71
  72 #define SMALL -1.0e-10
  73 #define SELECT 1
  74
  75 #ifdef WITH_PYTHON
  76 static ThreadMutex python_driver_lock = BLI_MUTEX_INITIALIZER;
  77 #endif
  78
  79 /* ************************** Data-Level Functions ************************* */
  80
  81 /* ---------------------- Freeing --------------------------- */
  82
  83 /* Frees the F-Curve itself too, so make sure BLI_remlink is called before calling this... */
  84 void free_fcurve(FCurve *fcu)
  85 {
  86         if (fcu == NULL)
  87                 return;
  88
  89         /* free curve data */
  90         MEM_SAFE_FREE(fcu->bezt);
  91         MEM_SAFE_FREE(fcu->fpt);
  92
  93         /* free RNA-path, as this were allocated when getting the path string */
  94         MEM_SAFE_FREE(fcu->rna_path);
  95
  96         /* free extra data - i.e. modifiers, and driver */
  97         fcurve_free_driver(fcu);
  98         free_fmodifiers(&fcu->modifiers);
  99
 100         /* free f-curve itself */
 101         MEM_freeN(fcu);
 102 }
 103
 104 /* Frees a list of F-Curves */
 105 void free_fcurves(ListBase *list)
 106 {
 107         FCurve *fcu, *fcn;
 108
 109         /* sanity check */
 110         if (list == NULL)
 111                 return;
 112
 113         /* free data - no need to call remlink before freeing each curve,
 114          * as we store reference to next, and freeing only touches the curve
 115          * it's given
 116          */
 117         for (fcu = list->first; fcu; fcu = fcn) {
 118                 fcn = fcu->next;
 119                 free_fcurve(fcu);
 120         }
 121
 122         /* clear pointers just in case */
 123         BLI_listbase_clear(list);
 124 }
 125
 126 /* ---------------------- Copy --------------------------- */
 127
 128 /* duplicate an F-Curve */
 129 FCurve *copy_fcurve(const FCurve *fcu)
 130 {
 131         FCurve *fcu_d;
 132
 133         /* sanity check */
 134         if (fcu == NULL)
 135                 return NULL;
 136
 137         /* make a copy */
 138         fcu_d = MEM_dupallocN(fcu);
 139
 140         fcu_d->next = fcu_d->prev = NULL;
 141         fcu_d->grp = NULL;
 142
 143         /* copy curve data */
 144         fcu_d->bezt = MEM_dupallocN(fcu_d->bezt);
 145         fcu_d->fpt = MEM_dupallocN(fcu_d->fpt);
 146
 147         /* copy rna-path */
 148         fcu_d->rna_path = MEM_dupallocN(fcu_d->rna_path);
 149
 150         /* copy driver */
 151         fcu_d->driver = fcurve_copy_driver(fcu_d->driver);
 152
 153         /* copy modifiers */
 154         copy_fmodifiers(&fcu_d->modifiers, &fcu->modifiers);
 155
 156         /* return new data */
 157         return fcu_d;
 158 }
 159
 160 /* duplicate a list of F-Curves */
 161 void copy_fcurves(ListBase *dst, ListBase *src)
 162 {
 163         FCurve *dfcu, *sfcu;
 164
 165         /* sanity checks */
 166         if (ELEM(NULL, dst, src))
 167                 return;
 168
 169         /* clear destination list first */
 170         BLI_listbase_clear(dst);
 171
 172         /* copy one-by-one */
 173         for (sfcu = src->first; sfcu; sfcu = sfcu->next) {
 174                 dfcu = copy_fcurve(sfcu);
 175                 BLI_addtail(dst, dfcu);
 176         }
 177 }
 178
 179 /* ----------------- Finding F-Curves -------------------------- */
 180
 181 /* high level function to get an fcurve from C without having the rna */
 182 FCurve *id_data_find_fcurve(ID *id, void *data, StructRNA *type, const char *prop_name, int index, bool *r_driven)
 183 {
 184         /* anim vars */
 185         AnimData *adt = BKE_animdata_from_id(id);
 186         FCurve *fcu = NULL;
 187
 188         /* rna vars */
 189         PointerRNA ptr;
 190         PropertyRNA *prop;
 191         char *path;
 192
 193         if (r_driven)
 194                 *r_driven = false;
 195
 196         /* only use the current action ??? */
 197         if (ELEM(NULL, adt, adt->action))
 198                 return NULL;
 199
 200         RNA_pointer_create(id, type, data, &ptr);
 201         prop = RNA_struct_find_property(&ptr, prop_name);
 202
 203         if (prop) {
 204                 path = RNA_path_from_ID_to_property(&ptr, prop);
 205
 206                 if (path) {
 207                         /* animation takes priority over drivers */
 208                         if ((adt->action) && (adt->action->curves.first))
 209                                 fcu = list_find_fcurve(&adt->action->curves, path, index);
 210
 211                         /* if not animated, check if driven */
 212                         if ((fcu == NULL) && (adt->drivers.first)) {
 213                                 fcu = list_find_fcurve(&adt->drivers, path, index);
 214                                 if (fcu && r_driven)
 215                                         *r_driven = true;
 216                                 fcu = NULL;
 217                         }
 218
 219                         MEM_freeN(path);
 220                 }
 221         }
 222
 223         return fcu;
 224 }
 225
 226
 227 /* Find the F-Curve affecting the given RNA-access path + index, in the list of F-Curves provided */
 228 FCurve *list_find_fcurve(ListBase *list, const char rna_path[], const int array_index)
 229 {
 230         FCurve *fcu;
 231
 232         /* sanity checks */
 233         if (ELEM(NULL, list, rna_path) || (array_index < 0) )
 234                 return NULL;
 235
 236         /* check paths of curves, then array indices... */
 237         for (fcu = list->first; fcu; fcu = fcu->next) {
 238                 /* simple string-compare (this assumes that they have the same root...) */
 239                 if (fcu->rna_path && STREQ(fcu->rna_path, rna_path)) {
 240                         /* now check indices */
 241                         if (fcu->array_index == array_index)
 242                                 return fcu;
 243                 }
 244         }
 245
 246         /* return */
 247         return NULL;
 248 }
 249
 250 /* quick way to loop over all fcurves of a given 'path' */
 251 FCurve *iter_step_fcurve(FCurve *fcu_iter, const char rna_path[])
 252 {
 253         FCurve *fcu;
 254
 255         /* sanity checks */
 256         if (ELEM(NULL, fcu_iter, rna_path))
 257                 return NULL;
 258
 259         /* check paths of curves, then array indices... */
 260         for (fcu = fcu_iter; fcu; fcu = fcu->next) {
 261                 /* simple string-compare (this assumes that they have the same root...) */
 262                 if (fcu->rna_path && STREQ(fcu->rna_path, rna_path)) {
 263                         return fcu;
 264                 }
 265         }
 266
 267         /* return */
 268         return NULL;
 269 }
 270
 271 /* Get list of LinkData's containing pointers to the F-Curves which control the types of data indicated
 272  * Lists...
 273  *      - dst: list of LinkData's matching the criteria returned.
 274  *        List must be freed after use, and is assumed to be empty when passed.
 275  *      - src: list of F-Curves to search through
 276  * Filters...
 277  *  - dataPrefix: i.e. 'pose.bones[' or 'nodes['
 278  *  - dataName: name of entity within "" immediately following the prefix
 279  */
 280 int list_find_data_fcurves(ListBase *dst, ListBase *src, const char *dataPrefix, const char *dataName)
 281 {
 282         FCurve *fcu;
 283         int matches = 0;
 284
 285         /* sanity checks */
 286         if (ELEM(NULL, dst, src, dataPrefix, dataName))
 287                 return 0;
 288         else if ((dataPrefix[0] == 0) || (dataName[0] == 0))
 289                 return 0;
 290
 291         /* search each F-Curve one by one */
 292         for (fcu = src->first; fcu; fcu = fcu->next) {
 293                 /* check if quoted string matches the path */
 294                 if ((fcu->rna_path) && strstr(fcu->rna_path, dataPrefix)) {
 295                         char *quotedName = BLI_str_quoted_substrN(fcu->rna_path, dataPrefix);
 296
 297                         if (quotedName) {
 298                                 /* check if the quoted name matches the required name */
 299                                 if (STREQ(quotedName, dataName)) {
 300                                         LinkData *ld = MEM_callocN(sizeof(LinkData), __func__);
 301
 302                                         ld->data = fcu;
 303                                         BLI_addtail(dst, ld);
 304
 305                                         matches++;
 306                                 }
 307
 308                                 /* always free the quoted string, since it needs freeing */
 309                                 MEM_freeN(quotedName);
 310                         }
 311                 }
 312         }
 313
 314         /* return the number of matches */
 315         return matches;
 316 }
 317
 318 FCurve *rna_get_fcurve(
 319         PointerRNA *ptr, PropertyRNA *prop, int rnaindex,
 320         AnimData **r_adt,  bAction **r_action, bool *r_driven, bool *r_special)
 321 {
 322         return rna_get_fcurve_context_ui(NULL, ptr, prop, rnaindex, r_adt, r_action, r_driven, r_special);
 323 }
 324
 325 FCurve *rna_get_fcurve_context_ui(
 326         bContext *C, PointerRNA *ptr, PropertyRNA *prop, int rnaindex,
 327         AnimData **r_animdata, bAction **r_action, bool *r_driven, bool *r_special)
 328 {
 329         FCurve *fcu = NULL;
 330         PointerRNA tptr = *ptr;
 331
 332         *r_driven = false;
 333         *r_special = false;
 334
 335         if (r_animdata) *r_animdata = NULL;
 336         if (r_action) *r_action = NULL;
 337
 338         /* Special case for NLA Control Curves... */
 339         if (BKE_nlastrip_has_curves_for_property(ptr, prop)) {
 340                 NlaStrip *strip = (NlaStrip *)ptr->data;
 341
 342                 /* Set the special flag, since it cannot be a normal action/driver
 343                  * if we've been told to start looking here...
 344                  */
 345                 *r_special = true;
 346
 347                 /* The F-Curve either exists or it doesn't here... */
 348                 fcu = list_find_fcurve(&strip->fcurves, RNA_property_identifier(prop), rnaindex);
 349                 return fcu;
 350         }
 351
 352         /* there must be some RNA-pointer + property combon */
 353         if (prop && tptr.id.data && RNA_property_animateable(&tptr, prop)) {
 354                 AnimData *adt = BKE_animdata_from_id(tptr.id.data);
 355                 int step = C ? 2 : 1;  /* Always 1 in case we have no context (can't check in 'ancestors' of given RNA ptr). */
 356                 char *path = NULL;
 357
 358                 if (!adt && C) {
 359                         path = BKE_animdata_driver_path_hack(C, &tptr, prop, NULL);
 360                         adt = BKE_animdata_from_id(tptr.id.data);
 361                         step--;
 362                 }
 363
 364                 /* Standard F-Curve - Animation (Action) or Drivers */
 365                 while (adt && step--) {
 366                         if ((adt->action && adt->action->curves.first) || (adt->drivers.first)) {
 367                                 /* XXX this function call can become a performance bottleneck */
 368                                 if (step) {
 369                                         path = RNA_path_from_ID_to_property(&tptr, prop);
 370                                 }
 371
 372                                 // XXX: the logic here is duplicated with a function up above
 373                                 if (path) {
 374                                         /* animation takes priority over drivers */
 375                                         if (adt->action && adt->action->curves.first) {
 376                                                 fcu = list_find_fcurve(&adt->action->curves, path, rnaindex);
 377
 378                                                 if (fcu && r_action)
 379                                                         *r_action = adt->action;
 380                                         }
 381
 382                                         /* if not animated, check if driven */
 383                                         if (!fcu && (adt->drivers.first)) {
 384                                                 fcu = list_find_fcurve(&adt->drivers, path, rnaindex);
 385
 386                                                 if (fcu) {
 387                                                         if (r_animdata) *r_animdata = adt;
 388                                                         *r_driven = true;
 389                                                 }
 390                                         }
 391
 392                                         if (fcu && r_action) {
 393                                                 if (r_animdata) *r_animdata = adt;
 394                                                 *r_action = adt->action;
 395                                                 break;
 396                                         }
 397                                         else if (step) {
 398                                                 char *tpath = BKE_animdata_driver_path_hack(C, &tptr, prop, path);
 399                                                 if (tpath && tpath != path) {
 400                                                         MEM_freeN(path);
 401                                                         path = tpath;
 402                                                         adt = BKE_animdata_from_id(tptr.id.data);
 403                                                 }
 404                                                 else {
 405                                                         adt = NULL;
 406                                                 }
 407                                         }
 408                                 }
 409                         }
 410                 }
 411                 MEM_SAFE_FREE(path);
 412         }
 413
 414         return fcu;
 415 }
 416
 417 /* ----------------- Finding Keyframes/Extents -------------------------- */
 418
 419 /* Binary search algorithm for finding where to insert BezTriple, with optional argument for precision required.
 420  * Returns the index to insert at (data already at that index will be offset if replace is 0)
 421  */
 422 static int binarysearch_bezt_index_ex(BezTriple array[], float frame, int arraylen, float threshold, bool *r_replace)
 423 {
 424         int start = 0, end = arraylen;
 425         int loopbreaker = 0, maxloop = arraylen * 2;
 426
 427         /* initialize replace-flag first */
 428         *r_replace = false;
 429
 430         /* sneaky optimizations (don't go through searching process if...):
 431          *      - keyframe to be added is to be added out of current bounds
 432          *      - keyframe to be added would replace one of the existing ones on bounds
 433          */
 434         if ((arraylen <= 0) || (array == NULL)) {
 435                 printf("Warning: binarysearch_bezt_index() encountered invalid array\n");
 436                 return 0;
 437         }
 438         else {
 439                 /* check whether to add before/after/on */
 440                 float framenum;
 441
 442                 /* 'First' Keyframe (when only one keyframe, this case is used) */
 443                 framenum = array[0].vec[1][0];
 444                 if (IS_EQT(frame, framenum, threshold)) {
 445                         *r_replace = true;
 446                         return 0;
 447                 }
 448                 else if (frame < framenum)
 449                         return 0;
 450
 451                 /* 'Last' Keyframe */
 452                 framenum = array[(arraylen - 1)].vec[1][0];
 453                 if (IS_EQT(frame, framenum, threshold)) {
 454                         *r_replace = true;
 455                         return (arraylen - 1);
 456                 }
 457                 else if (frame > framenum)
 458                         return arraylen;
 459         }
 460
 461
 462         /* most of the time, this loop is just to find where to put it
 463          * 'loopbreaker' is just here to prevent infinite loops
 464          */
 465         for (loopbreaker = 0; (start <= end) && (loopbreaker < maxloop); loopbreaker++) {
 466                 /* compute and get midpoint */
 467                 int mid = start + ((end - start) / 2);  /* we calculate the midpoint this way to avoid int overflows... */
 468                 float midfra = array[mid].vec[1][0];
 469
 470                 /* check if exactly equal to midpoint */
 471                 if (IS_EQT(frame, midfra, threshold)) {
 472                         *r_replace = true;
 473                         return mid;
 474                 }
 475
 476                 /* repeat in upper/lower half */
 477                 if (frame > midfra)
 478                         start = mid + 1;
 479                 else if (frame < midfra)
 480                         end = mid - 1;
 481         }
 482
 483         /* print error if loop-limit exceeded */
 484         if (loopbreaker == (maxloop - 1)) {
 485                 printf("Error: binarysearch_bezt_index() was taking too long\n");
 486
 487                 /* include debug info */
 488                 printf("\tround = %d: start = %d, end = %d, arraylen = %d\n", loopbreaker, start, end, arraylen);
 489         }
 490
 491         /* not found, so return where to place it */
 492         return start;
 493 }
 494
 495
 496 /* Binary search algorithm for finding where to insert BezTriple. (for use by insert_bezt_fcurve)
 497  * Returns the index to insert at (data already at that index will be offset if replace is 0)
 498  */
 499 int binarysearch_bezt_index(BezTriple array[], float frame, int arraylen, bool *r_replace)
 500 {
 501         /* this is just a wrapper which uses the default threshold */
 502         return binarysearch_bezt_index_ex(array, frame, arraylen, BEZT_BINARYSEARCH_THRESH, r_replace);
 503 }
 504
 505 /* ...................................... */
 506
 507 /* helper for calc_fcurve_* functions -> find first and last BezTriple to be used */
 508 static short get_fcurve_end_keyframes(FCurve *fcu, BezTriple **first, BezTriple **last,
 509                                       const bool do_sel_only)
 510 {
 511         bool found = false;
 512
 513         /* init outputs */
 514         *first = NULL;
 515         *last = NULL;
 516
 517         /* sanity checks */
 518         if (fcu->bezt == NULL)
 519                 return found;
 520
 521         /* only include selected items? */
 522         if (do_sel_only) {
 523                 BezTriple *bezt;
 524                 unsigned int i;
 525
 526                 /* find first selected */
 527                 bezt = fcu->bezt;
 528                 for (i = 0; i < fcu->totvert; bezt++, i++) {
 529                         if (BEZT_ISSEL_ANY(bezt)) {
 530                                 *first = bezt;
 531                                 found = true;
 532                                 break;
 533                         }
 534                 }
 535
 536                 /* find last selected */
 537                 bezt = ARRAY_LAST_ITEM(fcu->bezt, BezTriple, fcu->totvert);
 538                 for (i = 0; i < fcu->totvert; bezt--, i++) {
 539                         if (BEZT_ISSEL_ANY(bezt)) {
 540                                 *last = bezt;
 541                                 found = true;
 542                                 break;
 543                         }
 544                 }
 545         }
 546         else {
 547                 /* just full array */
 548                 *first = fcu->bezt;
 549                 *last = ARRAY_LAST_ITEM(fcu->bezt, BezTriple, fcu->totvert);
 550                 found = true;
 551         }
 552
 553         return found;
 554 }
 555
 556
 557 /* Calculate the extents of F-Curve's data */
 558 bool calc_fcurve_bounds(FCurve *fcu, float *xmin, float *xmax, float *ymin, float *ymax,
 559                         const bool do_sel_only, const bool include_handles)
 560 {
 561         float xminv = 999999999.0f, xmaxv = -999999999.0f;
 562         float yminv = 999999999.0f, ymaxv = -999999999.0f;
 563         bool foundvert = false;
 564         unsigned int i;
 565
 566         if (fcu->totvert) {
 567                 if (fcu->bezt) {
 568                         BezTriple *bezt_first = NULL, *bezt_last = NULL;
 569
 570                         if (xmin || xmax) {
 571                                 /* get endpoint keyframes */
 572                                 foundvert = 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                                         if (include_handles) {
 578                                                 xminv = min_fff(xminv, bezt_first->vec[0][0], bezt_first->vec[1][0]);
 579                                                 xmaxv = max_fff(xmaxv, bezt_last->vec[1][0],  bezt_last->vec[2][0]);
 580                                         }
 581                                         else {
 582                                                 xminv = min_ff(xminv, bezt_first->vec[1][0]);
 583                                                 xmaxv = max_ff(xmaxv, bezt_last->vec[1][0]);
 584                                         }
 585                                 }
 586                         }
 587
 588                         /* only loop over keyframes to find extents for values if needed */
 589                         if (ymin || ymax) {
 590                                 BezTriple *bezt, *prevbezt = NULL;
 591
 592                                 for (bezt = fcu->bezt, i = 0; i < fcu->totvert; prevbezt = bezt, bezt++, i++) {
 593                                         if ((do_sel_only == false) || BEZT_ISSEL_ANY(bezt)) {
 594                                                 /* keyframe itself */
 595                                                 yminv = min_ff(yminv, bezt->vec[1][1]);
 596                                                 ymaxv = max_ff(ymaxv, bezt->vec[1][1]);
 597
 598                                                 if (include_handles) {
 599                                                         /* left handle - only if applicable
 600                                                          * NOTE: for the very first keyframe, the left handle actually has no bearings on anything
 601                                                          */
 602                                                         if (prevbezt && (prevbezt->ipo == BEZT_IPO_BEZ)) {
 603                                                                 yminv = min_ff(yminv, bezt->vec[0][1]);
 604                                                                 ymaxv = max_ff(ymaxv, bezt->vec[0][1]);
 605                                                         }
 606
 607                                                         /* right handle - only if applicable */
 608                                                         if (bezt->ipo == BEZT_IPO_BEZ) {
 609                                                                 yminv = min_ff(yminv, bezt->vec[2][1]);
 610                                                                 ymaxv = max_ff(ymaxv, bezt->vec[2][1]);
 611                                                         }
 612                                                 }
 613
 614                                                 foundvert = true;
 615                                         }
 616                                 }
 617                         }
 618                 }
 619                 else if (fcu->fpt) {
 620                         /* frame range can be directly calculated from end verts */
 621                         if (xmin || xmax) {
 622                                 xminv = min_ff(xminv, fcu->fpt[0].vec[0]);
 623                                 xmaxv = max_ff(xmaxv, fcu->fpt[fcu->totvert - 1].vec[0]);
 624                         }
 625
 626                         /* only loop over keyframes to find extents for values if needed */
 627                         if (ymin || ymax) {
 628                                 FPoint *fpt;
 629
 630                                 for (fpt = fcu->fpt, i = 0; i < fcu->totvert; fpt++, i++) {
 631                                         if (fpt->vec[1] < yminv)
 632                                                 yminv = fpt->vec[1];
 633                                         if (fpt->vec[1] > ymaxv)
 634                                                 ymaxv = fpt->vec[1];
 635
 636                                         foundvert = true;
 637                                 }
 638                         }
 639                 }
 640         }
 641
 642         if (foundvert) {
 643                 if (xmin) *xmin = xminv;
 644                 if (xmax) *xmax = xmaxv;
 645
 646                 if (ymin) *ymin = yminv;
 647                 if (ymax) *ymax = ymaxv;
 648         }
 649         else {
 650                 if (G.debug & G_DEBUG)
 651                         printf("F-Curve calc bounds didn't find anything, so assuming minimum bounds of 1.0\n");
 652
 653                 if (xmin) *xmin = 0.0f;
 654                 if (xmax) *xmax = 1.0f;
 655
 656                 if (ymin) *ymin = 0.0f;
 657                 if (ymax) *ymax = 1.0f;
 658         }
 659
 660         return foundvert;
 661 }
 662
 663 /* Calculate the extents of F-Curve's keyframes */
 664 bool calc_fcurve_range(FCurve *fcu, float *start, float *end,
 665                        const bool do_sel_only, const bool do_min_length)
 666 {
 667         float min = 999999999.0f, max = -999999999.0f;
 668         bool foundvert = false;
 669
 670         if (fcu->totvert) {
 671                 if (fcu->bezt) {
 672                         BezTriple *bezt_first = NULL, *bezt_last = NULL;
 673
 674                         /* get endpoint keyframes */
 675                         get_fcurve_end_keyframes(fcu, &bezt_first, &bezt_last, do_sel_only);
 676
 677                         if (bezt_first) {
 678                                 BLI_assert(bezt_last != NULL);
 679
 680                                 min = min_ff(min, bezt_first->vec[1][0]);
 681                                 max = max_ff(max, bezt_last->vec[1][0]);
 682
 683                                 foundvert = true;
 684                         }
 685                 }
 686                 else if (fcu->fpt) {
 687                         min = min_ff(min, fcu->fpt[0].vec[0]);
 688                         max = max_ff(max, fcu->fpt[fcu->totvert - 1].vec[0]);
 689
 690                         foundvert = true;
 691                 }
 692
 693         }
 694
 695         if (foundvert == false) {
 696                 min = max = 0.0f;
 697         }
 698
 699         if (do_min_length) {
 700                 /* minimum length is 1 frame */
 701                 if (min == max) {
 702                         max += 1.0f;
 703                 }
 704         }
 705
 706         *start = min;
 707         *end = max;
 708
 709         return foundvert;
 710 }
 711
 712 /* ----------------- Status Checks -------------------------- */
 713
 714 /* Are keyframes on F-Curve of any use?
 715  * Usability of keyframes refers to whether they should be displayed,
 716  * and also whether they will have any influence on the final result.
 717  */
 718 bool fcurve_are_keyframes_usable(FCurve *fcu)
 719 {
 720         /* F-Curve must exist */
 721         if (fcu == NULL)
 722                 return false;
 723
 724         /* F-Curve must not have samples - samples are mutually exclusive of keyframes */
 725         if (fcu->fpt)
 726                 return false;
 727
 728         /* if it has modifiers, none of these should "drastically" alter the curve */
 729         if (fcu->modifiers.first) {
 730                 FModifier *fcm;
 731
 732                 /* check modifiers from last to first, as last will be more influential */
 733                 /* TODO: optionally, only check modifier if it is the active one... */
 734                 for (fcm = fcu->modifiers.last; fcm; fcm = fcm->prev) {
 735                         /* ignore if muted/disabled */
 736                         if (fcm->flag & (FMODIFIER_FLAG_DISABLED | FMODIFIER_FLAG_MUTED))
 737                                 continue;
 738
 739                         /* type checks */
 740                         switch (fcm->type) {
 741                                 /* clearly harmless - do nothing */
 742                                 case FMODIFIER_TYPE_CYCLES:
 743                                 case FMODIFIER_TYPE_STEPPED:
 744                                 case FMODIFIER_TYPE_NOISE:
 745                                         break;
 746
 747                                 /* sometimes harmful - depending on whether they're "additive" or not */
 748                                 case FMODIFIER_TYPE_GENERATOR:
 749                                 {
 750                                         FMod_Generator *data = (FMod_Generator *)fcm->data;
 751
 752                                         if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0)
 753                                                 return false;
 754                                         break;
 755                                 }
 756                                 case FMODIFIER_TYPE_FN_GENERATOR:
 757                                 {
 758                                         FMod_FunctionGenerator *data = (FMod_FunctionGenerator *)fcm->data;
 759
 760                                         if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0)
 761                                                 return false;
 762                                         break;
 763                                 }
 764                                 /* always harmful - cannot allow */
 765                                 default:
 766                                         return false;
 767                         }
 768                 }
 769         }
 770
 771         /* keyframes are usable */
 772         return true;
 773 }
 774
 775 bool BKE_fcurve_is_protected(FCurve *fcu)
 776 {
 777         return ((fcu->flag & FCURVE_PROTECTED) ||
 778                 ((fcu->grp) && (fcu->grp->flag & AGRP_PROTECTED)));
 779 }
 780
 781 /* Can keyframes be added to F-Curve?
 782  * Keyframes can only be added if they are already visible
 783  */
 784 bool fcurve_is_keyframable(FCurve *fcu)
 785 {
 786         /* F-Curve's keyframes must be "usable" (i.e. visible + have an effect on final result) */
 787         if (fcurve_are_keyframes_usable(fcu) == 0)
 788                 return false;
 789
 790         /* F-Curve must currently be editable too */
 791         if (BKE_fcurve_is_protected(fcu))
 792                 return false;
 793
 794         /* F-Curve is keyframable */
 795         return true;
 796 }
 797
 798 /* ***************************** Keyframe Column Tools ********************************* */
 799
 800 /* add a BezTriple to a column */
 801 void bezt_add_to_cfra_elem(ListBase *lb, BezTriple *bezt)
 802 {
 803         CfraElem *ce, *cen;
 804
 805         for (ce = lb->first; ce; ce = ce->next) {
 806                 /* double key? */
 807                 if (IS_EQT(ce->cfra, bezt->vec[1][0], BEZT_BINARYSEARCH_THRESH)) {
 808                         if (bezt->f2 & SELECT) ce->sel = bezt->f2;
 809                         return;
 810                 }
 811                 /* should key be inserted before this column? */
 812                 else if (ce->cfra > bezt->vec[1][0]) break;
 813         }
 814
 815         /* create a new column */
 816         cen = MEM_callocN(sizeof(CfraElem), "add_to_cfra_elem");
 817         if (ce) BLI_insertlinkbefore(lb, ce, cen);
 818         else BLI_addtail(lb, cen);
 819
 820         cen->cfra = bezt->vec[1][0];
 821         cen->sel = bezt->f2;
 822 }
 823
 824 /* ***************************** Samples Utilities ******************************* */
 825 /* Some utilities for working with FPoints (i.e. 'sampled' animation curve data, such as
 826  * data imported from BVH/Mocap files), which are specialized for use with high density datasets,
 827  * which BezTriples/Keyframe data are ill equipped to do.
 828  */
 829
 830
 831 /* Basic sampling callback which acts as a wrapper for evaluate_fcurve()
 832  *      'data' arg here is unneeded here...
 833  */
 834 float fcurve_samplingcb_evalcurve(FCurve *fcu, void *UNUSED(data), float evaltime)
 835 {
 836         /* assume any interference from drivers on the curve is intended... */
 837         return evaluate_fcurve(fcu, evaltime);
 838 }
 839
 840
 841 /* Main API function for creating a set of sampled curve data, given some callback function
 842  * used to retrieve the values to store.
 843  */
 844 void fcurve_store_samples(FCurve *fcu, void *data, int start, int end, FcuSampleFunc sample_cb)
 845 {
 846         FPoint *fpt, *new_fpt;
 847         int cfra;
 848
 849         /* sanity checks */
 850         /* TODO: make these tests report errors using reports not printf's */
 851         if (ELEM(NULL, fcu, sample_cb)) {
 852                 printf("Error: No F-Curve with F-Curve Modifiers to Bake\n");
 853                 return;
 854         }
 855         if (start > end) {
 856                 printf("Error: Frame range for Sampled F-Curve creation is inappropriate\n");
 857                 return;
 858         }
 859
 860         /* set up sample data */
 861         fpt = new_fpt = MEM_callocN(sizeof(FPoint) * (end - start + 1), "FPoint Samples");
 862
 863         /* use the sampling callback at 1-frame intervals from start to end frames */
 864         for (cfra = start; cfra <= end; cfra++, fpt++) {
 865                 fpt->vec[0] = (float)cfra;
 866                 fpt->vec[1] = sample_cb(fcu, data, (float)cfra);
 867         }
 868
 869         /* free any existing sample/keyframe data on curve  */
 870         if (fcu->bezt) MEM_freeN(fcu->bezt);
 871         if (fcu->fpt) MEM_freeN(fcu->fpt);
 872
 873         /* store the samples */
 874         fcu->bezt = NULL;
 875         fcu->fpt = new_fpt;
 876         fcu->totvert = end - start + 1;
 877 }
 878
 879 /* ***************************** F-Curve Sanity ********************************* */
 880 /* The functions here are used in various parts of Blender, usually after some editing
 881  * of keyframe data has occurred. They ensure that keyframe data is properly ordered and
 882  * that the handles are correctly
 883  */
 884
 885 /* Checks if the F-Curve has a Cycles modifier with simple settings that warrant transition smoothing */
 886 bool BKE_fcurve_is_cyclic(FCurve *fcu)
 887 {
 888         FModifier *fcm = fcu->modifiers.first;
 889
 890         if (!fcm || fcm->type != FMODIFIER_TYPE_CYCLES)
 891                 return false;
 892
 893         if (fcm->flag & (FMODIFIER_FLAG_DISABLED | FMODIFIER_FLAG_MUTED))
 894                 return false;
 895
 896         if (fcm->flag & (FMODIFIER_FLAG_RANGERESTRICT | FMODIFIER_FLAG_USEINFLUENCE))
 897                 return false;
 898
 899         FMod_Cycles *data = (FMod_Cycles *)fcm->data;
 900
 901         return data && data->after_cycles == 0 && data->before_cycles == 0 &&
 902             ELEM(data->before_mode, FCM_EXTRAPOLATE_CYCLIC, FCM_EXTRAPOLATE_CYCLIC_OFFSET) &&
 903             ELEM(data->after_mode, FCM_EXTRAPOLATE_CYCLIC, FCM_EXTRAPOLATE_CYCLIC_OFFSET);
 904 }
 905
 906 /* Shifts 'in' by the difference in coordinates between 'to' and 'from', using 'out' as the output buffer.
 907  * When 'to' and 'from' are end points of the loop, this moves the 'in' point one loop cycle.
 908  */
 909 static BezTriple *cycle_offset_triple(bool cycle, BezTriple *out, const BezTriple *in, const BezTriple *from, const BezTriple *to)
 910 {
 911         if (!cycle)
 912                 return NULL;
 913
 914         memcpy(out, in, sizeof(BezTriple));
 915
 916         float delta[3];
 917         sub_v3_v3v3(delta, to->vec[1], from->vec[1]);
 918
 919         for (int i = 0; i < 3; i++)
 920                 add_v3_v3(out->vec[i], delta);
 921
 922         return out;
 923 }
 924
 925 /* This function recalculates the handles of an F-Curve
 926  * If the BezTriples have been rearranged, sort them first before using this.
 927  */
 928 void calchandles_fcurve(FCurve *fcu)
 929 {
 930         BezTriple *bezt, *prev, *next;
 931         int a = fcu->totvert;
 932
 933         /* Error checking:
 934          *      - need at least two points
 935          *      - need bezier keys
 936          *      - only bezier-interpolation has handles (for now)
 937          */
 938         if (ELEM(NULL, fcu, fcu->bezt) || (a < 2) /*|| ELEM(fcu->ipo, BEZT_IPO_CONST, BEZT_IPO_LIN)*/)
 939                 return;
 940
 941         /* if the first modifier is Cycles, smooth the curve through the cycle */
 942         BezTriple *first = &fcu->bezt[0], *last = &fcu->bezt[fcu->totvert - 1];
 943         BezTriple tmp;
 944
 945         bool cycle = BKE_fcurve_is_cyclic(fcu) && BEZT_IS_AUTOH(first) && BEZT_IS_AUTOH(last);
 946
 947         /* get initial pointers */
 948         bezt = fcu->bezt;
 949         prev = cycle_offset_triple(cycle, &tmp, &fcu->bezt[fcu->totvert - 2], last, first);
 950         next = (bezt + 1);
 951
 952         /* loop over all beztriples, adjusting handles */
 953         while (a--) {
 954                 /* clamp timing of handles to be on either side of beztriple */
 955                 if (bezt->vec[0][0] > bezt->vec[1][0]) bezt->vec[0][0] = bezt->vec[1][0];
 956                 if (bezt->vec[2][0] < bezt->vec[1][0]) bezt->vec[2][0] = bezt->vec[1][0];
 957
 958                 /* calculate auto-handles */
 959                 BKE_nurb_handle_calc(bezt, prev, next, true, fcu->auto_smoothing);
 960
 961                 /* for automatic ease in and out */
 962                 if (BEZT_IS_AUTOH(bezt) && !cycle) {
 963                         /* only do this on first or last beztriple */
 964                         if ((a == 0) || (a == fcu->totvert - 1)) {
 965                                 /* set both handles to have same horizontal value as keyframe */
 966                                 if (fcu->extend == FCURVE_EXTRAPOLATE_CONSTANT) {
 967                                         bezt->vec[0][1] = bezt->vec[2][1] = bezt->vec[1][1];
 968                                         /* remember that these keyframes are special, they don't need to be adjusted */
 969                                         bezt->f5 = HD_AUTOTYPE_SPECIAL;
 970                                 }
 971                         }
 972                 }
 973
 974                 /* avoid total smoothing failure on duplicate keyframes (can happen during grab) */
 975                 if (prev && prev->vec[1][0] >= bezt->vec[1][0]) {
 976                         prev->f5 = bezt->f5 = HD_AUTOTYPE_SPECIAL;
 977                 }
 978
 979                 /* advance pointers for next iteration */
 980                 prev = bezt;
 981
 982                 if (a == 1) {
 983                         next = cycle_offset_triple(cycle, &tmp, &fcu->bezt[1], first, last);
 984                 }
 985                 else {
 986                         next++;
 987                 }
 988
 989                 bezt++;
 990         }
 991
 992         /* if cyclic extrapolation and Auto Clamp has triggered, ensure it is symmetric */
 993         if (cycle && (first->f5 != HD_AUTOTYPE_NORMAL || last->f5 != HD_AUTOTYPE_NORMAL)) {
 994                 first->vec[0][1] = first->vec[2][1] = first->vec[1][1];
 995                 last->vec[0][1] = last->vec[2][1] = last->vec[1][1];
 996                 first->f5 = last->f5 = HD_AUTOTYPE_SPECIAL;
 997         }
 998
 999         /* do a second pass for auto handle: compute the handle to have 0 accelaration step */
1000         if (fcu->auto_smoothing != FCURVE_SMOOTH_NONE) {
1001                 BKE_nurb_handle_smooth_fcurve(fcu->bezt, fcu->totvert, cycle);
1002         }
1003 }
1004
1005 void testhandles_fcurve(FCurve *fcu, const bool use_handle)
1006 {
1007         BezTriple *bezt;
1008         unsigned int a;
1009
1010         /* only beztriples have handles (bpoints don't though) */
1011         if (ELEM(NULL, fcu, fcu->bezt))
1012                 return;
1013
1014         /* loop over beztriples */
1015         for (a = 0, bezt = fcu->bezt; a < fcu->totvert; a++, bezt++) {
1016                 BKE_nurb_bezt_handle_test(bezt, use_handle);
1017         }
1018
1019         /* recalculate handles */
1020         calchandles_fcurve(fcu);
1021 }
1022
1023 /* This function sorts BezTriples so that they are arranged in chronological order,
1024  * as tools working on F-Curves expect that the BezTriples are in order.
1025  */
1026 void sort_time_fcurve(FCurve *fcu)
1027 {
1028         bool ok = true;
1029
1030         /* keep adjusting order of beztriples until nothing moves (bubble-sort) */
1031         while (ok) {
1032                 ok = 0;
1033
1034                 /* currently, will only be needed when there are beztriples */
1035                 if (fcu->bezt) {
1036                         BezTriple *bezt;
1037                         unsigned int a;
1038
1039                         /* loop over ALL points to adjust position in array and recalculate handles */
1040                         for (a = 0, bezt = fcu->bezt; a < fcu->totvert; a++, bezt++) {
1041                                 /* check if thee's a next beztriple which we could try to swap with current */
1042                                 if (a < (fcu->totvert - 1)) {
1043                                         /* swap if one is after the other (and indicate that order has changed) */
1044                                         if (bezt->vec[1][0] > (bezt + 1)->vec[1][0]) {
1045                                                 SWAP(BezTriple, *bezt, *(bezt + 1));
1046                                                 ok = 1;
1047                                         }
1048
1049                                         /* if either one of both of the points exceeds crosses over the keyframe time... */
1050                                         if ( (bezt->vec[0][0] > bezt->vec[1][0]) && (bezt->vec[2][0] < bezt->vec[1][0]) ) {
1051                                                 /* swap handles if they have switched sides for some reason */
1052                                                 swap_v2_v2(bezt->vec[0], bezt->vec[2]);
1053                                         }
1054                                         else {
1055                                                 /* clamp handles */
1056                                                 CLAMP_MAX(bezt->vec[0][0], bezt->vec[1][0]);
1057                                                 CLAMP_MIN(bezt->vec[2][0], bezt->vec[1][0]);
1058                                         }
1059                                 }
1060                         }
1061                 }
1062         }
1063 }
1064
1065 /* This function tests if any BezTriples are out of order, thus requiring a sort */
1066 short test_time_fcurve(FCurve *fcu)
1067 {
1068         unsigned int a;
1069
1070         /* sanity checks */
1071         if (fcu == NULL)
1072                 return 0;
1073
1074         /* currently, only need to test beztriples */
1075         if (fcu->bezt) {
1076                 BezTriple *bezt;
1077
1078                 /* loop through all BezTriples, stopping when one exceeds the one after it */
1079                 for (a = 0, bezt = fcu->bezt; a < (fcu->totvert - 1); a++, bezt++) {
1080                         if (bezt->vec[1][0] > (bezt + 1)->vec[1][0])
1081                                 return 1;
1082                 }
1083         }
1084         else if (fcu->fpt) {
1085                 FPoint *fpt;
1086
1087                 /* loop through all FPoints, stopping when one exceeds the one after it */
1088                 for (a = 0, fpt = fcu->fpt; a < (fcu->totvert - 1); a++, fpt++) {
1089                         if (fpt->vec[0] > (fpt + 1)->vec[0])
1090                                 return 1;
1091                 }
1092         }
1093
1094         /* none need any swapping */
1095         return 0;
1096 }
1097
1098 /* ***************************** Drivers ********************************* */
1099
1100 /* Driver Variables --------------------------- */
1101
1102 /* TypeInfo for Driver Variables (dvti) */
1103 typedef struct DriverVarTypeInfo {
1104         /* evaluation callback */
1105         float (*get_value)(ChannelDriver *driver, DriverVar *dvar);
1106
1107         /* allocation of target slots */
1108         int num_targets;                                        /* number of target slots required */
1109         const char *target_names[MAX_DRIVER_TARGETS];   /* UI names that should be given to the slots */
1110         short target_flags[MAX_DRIVER_TARGETS];                 /* flags defining the requirements for each slot */
1111 } DriverVarTypeInfo;
1112
1113 /* Macro to begin definitions */
1114 #define BEGIN_DVAR_TYPEDEF(type) \
1115         {
1116
1117 /* Macro to end definitions */
1118 #define END_DVAR_TYPEDEF \
1119         }
1120
1121 /* ......... */
1122
1123 static ID *dtar_id_ensure_proxy_from(ID *id)
1124 {
1125         if (id && GS(id->name) == ID_OB && ((Object *)id)->proxy_from)
1126                 return (ID *)(((Object *)id)->proxy_from);
1127         return id;
1128 }
1129
1130 /* Helper function to obtain a value using RNA from the specified source (for evaluating drivers) */
1131 static float dtar_get_prop_val(ChannelDriver *driver, DriverTarget *dtar)
1132 {
1133         PointerRNA id_ptr, ptr;
1134         PropertyRNA *prop;
1135         ID *id;
1136         int index = -1;
1137         float value = 0.0f;
1138
1139         /* sanity check */
1140         if (ELEM(NULL, driver, dtar))
1141                 return 0.0f;
1142
1143         id = dtar_id_ensure_proxy_from(dtar->id);
1144
1145         /* error check for missing pointer... */
1146         if (id == NULL) {
1147                 if (G.debug & G_DEBUG) {
1148                         printf("Error: driver has an invalid target to use (path = %s)\n", dtar->rna_path);
1149                 }
1150
1151                 driver->flag |= DRIVER_FLAG_INVALID;
1152                 dtar->flag   |= DTAR_FLAG_INVALID;
1153                 return 0.0f;
1154         }
1155
1156         /* get RNA-pointer for the ID-block given in target */
1157         RNA_id_pointer_create(id, &id_ptr);
1158
1159         /* get property to read from, and get value as appropriate */
1160         if (RNA_path_resolve_property_full(&id_ptr, dtar->rna_path, &ptr, &prop, &index)) {
1161                 if (RNA_property_array_check(prop)) {
1162                         /* array */
1163                         if ((index >= 0) && (index < RNA_property_array_length(&ptr, prop))) {
1164                                 switch (RNA_property_type(prop)) {
1165                                         case PROP_BOOLEAN:
1166                                                 value = (float)RNA_property_boolean_get_index(&ptr, prop, index);
1167                                                 break;
1168                                         case PROP_INT:
1169                                                 value = (float)RNA_property_int_get_index(&ptr, prop, index);
1170                                                 break;
1171                                         case PROP_FLOAT:
1172                                                 value = RNA_property_float_get_index(&ptr, prop, index);
1173                                                 break;
1174                                         default:
1175                                                 break;
1176                                 }
1177                         }
1178                         else {
1179                                 /* out of bounds */
1180                                 if (G.debug & G_DEBUG) {
1181                                         printf("Driver Evaluation Error: array index is out of bounds for %s -> %s (%d)",
1182                                                id->name, dtar->rna_path, index);
1183                                 }
1184
1185                                 driver->flag |= DRIVER_FLAG_INVALID;
1186                                 dtar->flag   |= DTAR_FLAG_INVALID;
1187                                 return 0.0f;
1188                         }
1189                 }
1190                 else {
1191                         /* not an array */
1192                         switch (RNA_property_type(prop)) {
1193                                 case PROP_BOOLEAN:
1194                                         value = (float)RNA_property_boolean_get(&ptr, prop);
1195                                         break;
1196                                 case PROP_INT:
1197                                         value = (float)RNA_property_int_get(&ptr, prop);
1198                                         break;
1199                                 case PROP_FLOAT:
1200                                         value = RNA_property_float_get(&ptr, prop);
1201                                         break;
1202                                 case PROP_ENUM:
1203                                         value = (float)RNA_property_enum_get(&ptr, prop);
1204                                         break;
1205                                 default:
1206                                         break;
1207                         }
1208                 }
1209         }
1210         else {
1211                 /* path couldn't be resolved */
1212                 if (G.debug & G_DEBUG) {
1213                         printf("Driver Evaluation Error: cannot resolve target for %s -> %s\n", id->name, dtar->rna_path);
1214                 }
1215
1216                 driver->flag |= DRIVER_FLAG_INVALID;
1217                 dtar->flag   |= DTAR_FLAG_INVALID;
1218                 return 0.0f;
1219         }
1220
1221         /* if we're still here, we should be ok... */
1222         dtar->flag &= ~DTAR_FLAG_INVALID;
1223         return value;
1224 }
1225
1226 /**
1227  * Same as 'dtar_get_prop_val'. but get the RNA property.
1228  */
1229 bool driver_get_variable_property(
1230         ChannelDriver *driver, DriverTarget *dtar,
1231         PointerRNA *r_ptr, PropertyRNA **r_prop, int *r_index)
1232 {
1233         PointerRNA id_ptr;
1234         PointerRNA ptr;
1235         PropertyRNA *prop;
1236         ID *id;
1237         int index = -1;
1238
1239         /* sanity check */
1240         if (ELEM(NULL, driver, dtar))
1241                 return false;
1242
1243         id = dtar_id_ensure_proxy_from(dtar->id);
1244
1245         /* error check for missing pointer... */
1246         if (id == NULL) {
1247                 if (G.debug & G_DEBUG) {
1248                         printf("Error: driver has an invalid target to use (path = %s)\n", dtar->rna_path);
1249                 }
1250
1251                 driver->flag |= DRIVER_FLAG_INVALID;
1252                 dtar->flag   |= DTAR_FLAG_INVALID;
1253                 return false;
1254         }
1255
1256         /* get RNA-pointer for the ID-block given in target */
1257         RNA_id_pointer_create(id, &id_ptr);
1258
1259         /* get property to read from, and get value as appropriate */
1260         if (dtar->rna_path == NULL || dtar->rna_path[0] == '\0') {
1261                 ptr = PointerRNA_NULL;
1262                 prop = NULL; /* ok */
1263         }
1264         else if (RNA_path_resolve_property_full(&id_ptr, dtar->rna_path, &ptr, &prop, &index)) {
1265                 /* ok */
1266         }
1267         else {
1268                 /* path couldn't be resolved */
1269                 if (G.debug & G_DEBUG) {
1270                         printf("Driver Evaluation Error: cannot resolve target for %s -> %s\n", id->name, dtar->rna_path);
1271                 }
1272
1273                 ptr = PointerRNA_NULL;
1274                 *r_prop = NULL;
1275                 *r_index = -1;
1276
1277                 driver->flag |= DRIVER_FLAG_INVALID;
1278                 dtar->flag   |= DTAR_FLAG_INVALID;
1279                 return false;
1280         }
1281
1282         *r_ptr = ptr;
1283         *r_prop = prop;
1284         *r_index = index;
1285
1286         /* if we're still here, we should be ok... */
1287         dtar->flag &= ~DTAR_FLAG_INVALID;
1288         return true;
1289 }
1290
1291 #if 0
1292 /* Helper function to obtain a pointer to a Pose Channel (for evaluating drivers) */
1293 static bPoseChannel *dtar_get_pchan_ptr(ChannelDriver *driver, DriverTarget *dtar)
1294 {
1295         ID *id;
1296         /* sanity check */
1297         if (ELEM(NULL, driver, dtar))
1298                 return NULL;
1299
1300         id = dtar_id_ensure_proxy_from(dtar->id);
1301
1302         /* check if the ID here is a valid object */
1303         if (id && GS(id->name)) {
1304                 Object *ob = (Object *)id;
1305
1306                 /* get pose, and subsequently, posechannel */
1307                 return BKE_pose_channel_find_name(ob->pose, dtar->pchan_name);
1308         }
1309         else {
1310                 /* cannot find a posechannel this way */
1311                 return NULL;
1312         }
1313 }
1314 #endif
1315
1316 static short driver_check_valid_targets(ChannelDriver *driver, DriverVar *dvar)
1317 {
1318         short valid_targets = 0;
1319
1320         DRIVER_TARGETS_USED_LOOPER(dvar)
1321         {
1322                 Object *ob = (Object *)dtar_id_ensure_proxy_from(dtar->id);
1323
1324                 /* check if this target has valid data */
1325                 if ((ob == NULL) || (GS(ob->id.name) != ID_OB)) {
1326                         /* invalid target, so will not have enough targets */
1327                         driver->flag |= DRIVER_FLAG_INVALID;
1328                         dtar->flag |= DTAR_FLAG_INVALID;
1329                 }
1330                 else {
1331                         /* target seems to be OK now... */
1332                         dtar->flag &= ~DTAR_FLAG_INVALID;
1333                         valid_targets++;
1334                 }
1335         }
1336         DRIVER_TARGETS_LOOPER_END
1337
1338         return valid_targets;
1339 }
1340
1341 /* ......... */
1342
1343 /* evaluate 'single prop' driver variable */
1344 static float dvar_eval_singleProp(ChannelDriver *driver, DriverVar *dvar)
1345 {
1346         /* just evaluate the first target slot */
1347         return dtar_get_prop_val(driver, &dvar->targets[0]);
1348 }
1349
1350 /* evaluate 'rotation difference' driver variable */
1351 static float dvar_eval_rotDiff(ChannelDriver *driver, DriverVar *dvar)
1352 {
1353         short valid_targets = driver_check_valid_targets(driver, dvar);
1354
1355         /* make sure we have enough valid targets to use - all or nothing for now... */
1356         if (driver_check_valid_targets(driver, dvar) != 2) {
1357                 if (G.debug & G_DEBUG) {
1358                         printf("RotDiff DVar: not enough valid targets (n = %d) (a = %p, b = %p)\n",
1359                                 valid_targets, dvar->targets[0].id, dvar->targets[1].id);
1360                 }
1361                 return 0.0f;
1362         }
1363
1364         float (*mat[2])[4];
1365
1366         /* NOTE: for now, these are all just worldspace */
1367         for (int i = 0; i < 2; i++) {
1368                 /* get pointer to loc values to store in */
1369                 DriverTarget *dtar = &dvar->targets[i];
1370                 Object *ob = (Object *)dtar_id_ensure_proxy_from(dtar->id);
1371                 bPoseChannel *pchan;
1372
1373                 /* after the checks above, the targets should be valid here... */
1374                 BLI_assert((ob != NULL) && (GS(ob->id.name) == ID_OB));
1375
1376                 /* try to get posechannel */
1377                 pchan = BKE_pose_channel_find_name(ob->pose, dtar->pchan_name);
1378
1379                 /* check if object or bone */
1380                 if (pchan) {
1381                         /* bone */
1382                         mat[i] = pchan->pose_mat;
1383                 }
1384                 else {
1385                         /* object */
1386                         mat[i] = ob->obmat;
1387                 }
1388         }
1389
1390         float q1[4], q2[4], quat[4], angle;
1391
1392         /* use the final posed locations */
1393         mat4_to_quat(q1, mat[0]);
1394         mat4_to_quat(q2, mat[1]);
1395
1396         invert_qt_normalized(q1);
1397         mul_qt_qtqt(quat, q1, q2);
1398         angle = 2.0f * (saacos(quat[0]));
1399         angle = ABS(angle);
1400
1401         return (angle > (float)M_PI) ? (float)((2.0f * (float)M_PI) - angle) : (float)(angle);
1402 }
1403
1404 /* evaluate 'location difference' driver variable */
1405 /* TODO: this needs to take into account space conversions... */
1406 static float dvar_eval_locDiff(ChannelDriver *driver, DriverVar *dvar)
1407 {
1408         float loc1[3] = {0.0f, 0.0f, 0.0f};
1409         float loc2[3] = {0.0f, 0.0f, 0.0f};
1410         short valid_targets = driver_check_valid_targets(driver, dvar);
1411
1412         /* make sure we have enough valid targets to use - all or nothing for now... */
1413         if (valid_targets < dvar->num_targets) {
1414                 if (G.debug & G_DEBUG) {
1415                         printf("LocDiff DVar: not enough valid targets (n = %d) (a = %p, b = %p)\n",
1416                                 valid_targets, dvar->targets[0].id, dvar->targets[1].id);
1417                 }
1418                 return 0.0f;
1419         }
1420
1421         /* SECOND PASS: get two location values */
1422         /* NOTE: for now, these are all just worldspace */
1423         DRIVER_TARGETS_USED_LOOPER(dvar)
1424         {
1425                 /* get pointer to loc values to store in */
1426                 Object *ob = (Object *)dtar_id_ensure_proxy_from(dtar->id);
1427                 bPoseChannel *pchan;
1428                 float tmp_loc[3];
1429
1430                 /* after the checks above, the targets should be valid here... */
1431                 BLI_assert((ob != NULL) && (GS(ob->id.name) == ID_OB));
1432
1433                 /* try to get posechannel */
1434                 pchan = BKE_pose_channel_find_name(ob->pose, dtar->pchan_name);
1435
1436                 /* check if object or bone */
1437                 if (pchan) {
1438                         /* bone */
1439                         if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1440                                 if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1441                                         float mat[4][4];
1442
1443                                         /* extract transform just like how the constraints do it! */
1444                                         copy_m4_m4(mat, pchan->pose_mat);
1445                                         BKE_constraint_mat_convertspace(ob, pchan, mat, CONSTRAINT_SPACE_POSE, CONSTRAINT_SPACE_LOCAL, false);
1446
1447                                         /* ... and from that, we get our transform */
1448                                         copy_v3_v3(tmp_loc, mat[3]);
1449                                 }
1450                                 else {
1451                                         /* transform space (use transform values directly) */
1452                                         copy_v3_v3(tmp_loc, pchan->loc);
1453                                 }
1454                         }
1455                         else {
1456                                 /* convert to worldspace */
1457                                 copy_v3_v3(tmp_loc, pchan->pose_head);
1458                                 mul_m4_v3(ob->obmat, tmp_loc);
1459                         }
1460                 }
1461                 else {
1462                         /* object */
1463                         if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1464                                 if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1465                                         /* XXX: this should practically be the same as transform space... */
1466                                         float mat[4][4];
1467
1468                                         /* extract transform just like how the constraints do it! */
1469                                         copy_m4_m4(mat, ob->obmat);
1470                                         BKE_constraint_mat_convertspace(ob, NULL, mat, CONSTRAINT_SPACE_WORLD, CONSTRAINT_SPACE_LOCAL, false);
1471
1472                                         /* ... and from that, we get our transform */
1473                                         copy_v3_v3(tmp_loc, mat[3]);
1474                                 }
1475                                 else {
1476                                         /* transform space (use transform values directly) */
1477                                         copy_v3_v3(tmp_loc, ob->loc);
1478                                 }
1479                         }
1480                         else {
1481                                 /* worldspace */
1482                                 copy_v3_v3(tmp_loc, ob->obmat[3]);
1483                         }
1484                 }
1485
1486                 /* copy the location to the right place */
1487                 if (tarIndex) {
1488                         copy_v3_v3(loc2, tmp_loc);
1489                 }
1490                 else {
1491                         copy_v3_v3(loc1, tmp_loc);
1492                 }
1493         }
1494         DRIVER_TARGETS_LOOPER_END
1495
1496
1497         /* if we're still here, there should now be two targets to use,
1498          * so just take the length of the vector between these points
1499          */
1500         return len_v3v3(loc1, loc2);
1501 }
1502
1503 /* evaluate 'transform channel' driver variable */
1504 static float dvar_eval_transChan(ChannelDriver *driver, DriverVar *dvar)
1505 {
1506         DriverTarget *dtar = &dvar->targets[0];
1507         Object *ob = (Object *)dtar_id_ensure_proxy_from(dtar->id);
1508         bPoseChannel *pchan;
1509         float mat[4][4];
1510         float oldEul[3] = {0.0f, 0.0f, 0.0f};
1511         bool use_eulers = false;
1512         short rot_order = ROT_MODE_EUL;
1513
1514         /* check if this target has valid data */
1515         if ((ob == NULL) || (GS(ob->id.name) != ID_OB)) {
1516                 /* invalid target, so will not have enough targets */
1517                 driver->flag |= DRIVER_FLAG_INVALID;
1518                 dtar->flag   |= DTAR_FLAG_INVALID;
1519                 return 0.0f;
1520         }
1521         else {
1522                 /* target should be valid now */
1523                 dtar->flag &= ~DTAR_FLAG_INVALID;
1524         }
1525
1526         /* try to get posechannel */
1527         pchan = BKE_pose_channel_find_name(ob->pose, dtar->pchan_name);
1528
1529         /* check if object or bone, and get transform matrix accordingly
1530          *      - "useEulers" code is used to prevent the problems associated with non-uniqueness
1531          *        of euler decomposition from matrices [#20870]
1532          *      - localspace is for [#21384], where parent results are not wanted
1533          *        but local-consts is for all the common "corrective-shapes-for-limbs" situations
1534          */
1535         if (pchan) {
1536                 /* bone */
1537                 if (pchan->rotmode > 0) {
1538                         copy_v3_v3(oldEul, pchan->eul);
1539                         rot_order = pchan->rotmode;
1540                         use_eulers = true;
1541                 }
1542
1543                 if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1544                         if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1545                                 /* just like how the constraints do it! */
1546                                 copy_m4_m4(mat, pchan->pose_mat);
1547                                 BKE_constraint_mat_convertspace(ob, pchan, mat, CONSTRAINT_SPACE_POSE, CONSTRAINT_SPACE_LOCAL, false);
1548                         }
1549                         else {
1550                                 /* specially calculate local matrix, since chan_mat is not valid
1551                                  * since it stores delta transform of pose_mat so that deforms work
1552                                  * so it cannot be used here for "transform" space
1553                                  */
1554                                 BKE_pchan_to_mat4(pchan, mat);
1555                         }
1556                 }
1557                 else {
1558                         /* worldspace matrix */
1559                         mul_m4_m4m4(mat, ob->obmat, pchan->pose_mat);
1560                 }
1561         }
1562         else {
1563                 /* object */
1564                 if (ob->rotmode > 0) {
1565                         copy_v3_v3(oldEul, ob->rot);
1566                         rot_order = ob->rotmode;
1567                         use_eulers = true;
1568                 }
1569
1570                 if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1571                         if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1572                                 /* just like how the constraints do it! */
1573                                 copy_m4_m4(mat, ob->obmat);
1574                                 BKE_constraint_mat_convertspace(ob, NULL, mat, CONSTRAINT_SPACE_WORLD, CONSTRAINT_SPACE_LOCAL, false);
1575                         }
1576                         else {
1577                                 /* transforms to matrix */
1578                                 BKE_object_to_mat4(ob, mat);
1579                         }
1580                 }
1581                 else {
1582                         /* worldspace matrix - just the good-old one */
1583                         copy_m4_m4(mat, ob->obmat);
1584                 }
1585         }
1586
1587         /* check which transform */
1588         if (dtar->transChan >= MAX_DTAR_TRANSCHAN_TYPES) {
1589                 /* not valid channel */
1590                 return 0.0f;
1591         }
1592         else if (dtar->transChan >= DTAR_TRANSCHAN_SCALEX) {
1593                 /* Extract scale, and choose the right axis,
1594                  * inline 'mat4_to_size'. */
1595                 return len_v3(mat[dtar->transChan - DTAR_TRANSCHAN_SCALEX]);
1596         }
1597         else if (dtar->transChan >= DTAR_TRANSCHAN_ROTX) {
1598                 /* extract rotation as eulers (if needed)
1599                  *      - definitely if rotation order isn't eulers already
1600                  *      - if eulers, then we have 2 options:
1601                  *              a) decompose transform matrix as required, then try to make eulers from
1602                  *                 there compatible with original values
1603                  *              b) [NOT USED] directly use the original values (no decomposition)
1604                  *                      - only an option for "transform space", if quality is really bad with a)
1605                  */
1606                 float eul[3];
1607
1608                 mat4_to_eulO(eul, rot_order, mat);
1609
1610                 if (use_eulers) {
1611                         compatible_eul(eul, oldEul);
1612                 }
1613
1614                 return eul[dtar->transChan - DTAR_TRANSCHAN_ROTX];
1615         }
1616         else {
1617                 /* extract location and choose right axis */
1618                 return mat[3][dtar->transChan];
1619         }
1620 }
1621
1622 /* ......... */
1623
1624 /* Table of Driver Varaiable Type Info Data */
1625 static DriverVarTypeInfo dvar_types[MAX_DVAR_TYPES] = {
1626         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_SINGLE_PROP)
1627                 dvar_eval_singleProp,     /* eval callback */
1628                 1,     /* number of targets used */
1629                 {"Property"},     /* UI names for targets */
1630                 {0}     /* flags */
1631         END_DVAR_TYPEDEF,
1632
1633         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_ROT_DIFF)
1634                 dvar_eval_rotDiff,     /* eval callback */
1635                 2,     /* number of targets used */
1636                 {"Object/Bone 1", "Object/Bone 2"},     /* UI names for targets */
1637                 {DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY, DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY} /* flags */
1638         END_DVAR_TYPEDEF,
1639
1640         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_LOC_DIFF)
1641                 dvar_eval_locDiff,     /* eval callback */
1642                 2,     /* number of targets used */
1643                 {"Object/Bone 1", "Object/Bone 2"},     /* UI names for targets */
1644                 {DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY, DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY} /* flags */
1645         END_DVAR_TYPEDEF,
1646
1647         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_TRANSFORM_CHAN)
1648                 dvar_eval_transChan,     /* eval callback */
1649                 1,     /* number of targets used */
1650                 {"Object/Bone"},     /* UI names for targets */
1651                 {DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY}   /* flags */
1652         END_DVAR_TYPEDEF,
1653 };
1654
1655 /* Get driver variable typeinfo */
1656 static const DriverVarTypeInfo *get_dvar_typeinfo(int type)
1657 {
1658         /* check if valid type */
1659         if ((type >= 0) && (type < MAX_DVAR_TYPES))
1660                 return &dvar_types[type];
1661         else
1662                 return NULL;
1663 }
1664
1665 /* Driver API --------------------------------- */
1666
1667 /* Perform actual freeing driver variable and remove it from the given list */
1668 void driver_free_variable(ListBase *variables, DriverVar *dvar)
1669 {
1670         /* sanity checks */
1671         if (dvar == NULL)
1672                 return;
1673
1674         /* free target vars
1675          *      - need to go over all of them, not just up to the ones that are used
1676          *        currently, since there may be some lingering RNA paths from
1677          *    previous users needing freeing
1678          */
1679         DRIVER_TARGETS_LOOPER(dvar)
1680         {
1681                 /* free RNA path if applicable */
1682                 if (dtar->rna_path)
1683                         MEM_freeN(dtar->rna_path);
1684         }
1685         DRIVER_TARGETS_LOOPER_END
1686
1687         /* remove the variable from the driver */
1688         BLI_freelinkN(variables, dvar);
1689 }
1690
1691 /* Free the driver variable and do extra updates */
1692 void driver_free_variable_ex(ChannelDriver *driver, DriverVar *dvar)
1693 {
1694         /* remove and free the driver variable */
1695         driver_free_variable(&driver->variables, dvar);
1696
1697 #ifdef WITH_PYTHON
1698         /* since driver variables are cached, the expression needs re-compiling too */
1699         if (driver->type == DRIVER_TYPE_PYTHON)
1700                 driver->flag |= DRIVER_FLAG_RENAMEVAR;
1701 #endif
1702 }
1703
1704 /* Copy driver variables from src_vars list to dst_vars list */
1705 void driver_variables_copy(ListBase *dst_vars, const ListBase *src_vars)
1706 {
1707         BLI_assert(BLI_listbase_is_empty(dst_vars));
1708         BLI_duplicatelist(dst_vars, src_vars);
1709
1710         for (DriverVar *dvar = dst_vars->first; dvar; dvar = dvar->next) {
1711                 /* need to go over all targets so that we don't leave any dangling paths */
1712                 DRIVER_TARGETS_LOOPER(dvar)
1713                 {
1714                         /* make a copy of target's rna path if available */
1715                         if (dtar->rna_path)
1716                                 dtar->rna_path = MEM_dupallocN(dtar->rna_path);
1717                 }
1718                 DRIVER_TARGETS_LOOPER_END
1719         }
1720 }
1721
1722 /* Change the type of driver variable */
1723 void driver_change_variable_type(DriverVar *dvar, int type)
1724 {
1725         const DriverVarTypeInfo *dvti = get_dvar_typeinfo(type);
1726
1727         /* sanity check */
1728         if (ELEM(NULL, dvar, dvti))
1729                 return;
1730
1731         /* set the new settings */
1732         dvar->type = type;
1733         dvar->num_targets = dvti->num_targets;
1734
1735         /* make changes to the targets based on the defines for these types
1736          * NOTE: only need to make sure the ones we're using here are valid...
1737          */
1738         DRIVER_TARGETS_USED_LOOPER(dvar)
1739         {
1740                 short flags = dvti->target_flags[tarIndex];
1741
1742                 /* store the flags */
1743                 dtar->flag = flags;
1744
1745                 /* object ID types only, or idtype not yet initialized */
1746                 if ((flags & DTAR_FLAG_ID_OB_ONLY) || (dtar->idtype == 0))
1747                         dtar->idtype = ID_OB;
1748         }
1749         DRIVER_TARGETS_LOOPER_END
1750 }
1751
1752 /* Validate driver name (after being renamed) */
1753 void driver_variable_name_validate(DriverVar *dvar)
1754 {
1755         /* Special character blacklist */
1756         const char special_char_blacklist[] = {
1757             '~', '`', '!', '@', '#', '$', '%', '^', '&', '*', '+', '=', '-',
1758             '/', '\\', '?', ':', ';',  '<', '>', '{', '}', '[', ']', '|',
1759             ' ', '.', '\t', '\n', '\r'
1760         };
1761
1762         /* sanity checks */
1763         if (dvar == NULL)
1764                 return;
1765
1766         /* clear all invalid-name flags */
1767         dvar->flag &= ~DVAR_ALL_INVALID_FLAGS;
1768
1769         /* 0) Zero-length identifiers are not allowed */
1770         if (dvar->name[0] == '\0') {
1771                 dvar->flag |= DVAR_FLAG_INVALID_EMPTY;
1772         }
1773
1774         /* 1) Must start with a letter */
1775         /* XXX: We assume that valid unicode letters in other languages are ok too, hence the blacklisting */
1776         if (IN_RANGE_INCL(dvar->name[0], '0', '9')) {
1777                 dvar->flag |= DVAR_FLAG_INVALID_START_NUM;
1778         }
1779         else if (dvar->name[0] == '_') {
1780                 /* NOTE: We don't allow names to start with underscores (i.e. it helps when ruling out security risks) */
1781                 dvar->flag |= DVAR_FLAG_INVALID_START_CHAR;
1782         }
1783
1784         /* 2) Must not contain invalid stuff in the middle of the string */
1785         if (strchr(dvar->name, ' ')) {
1786                 dvar->flag |= DVAR_FLAG_INVALID_HAS_SPACE;
1787         }
1788         if (strchr(dvar->name, '.')) {
1789                 dvar->flag |= DVAR_FLAG_INVALID_HAS_DOT;
1790         }
1791
1792         /* 3) Check for special characters - Either at start, or in the middle */
1793         for (int i = 0; i < sizeof(special_char_blacklist); i++) {
1794                 char *match = strchr(dvar->name, special_char_blacklist[i]);
1795
1796                 if (match == dvar->name)
1797                         dvar->flag |= DVAR_FLAG_INVALID_START_CHAR;
1798                 else if (match != NULL)
1799                         dvar->flag |= DVAR_FLAG_INVALID_HAS_SPECIAL;
1800         }
1801
1802         /* 4) Check if the name is a reserved keyword
1803          * NOTE: These won't confuse Python, but it will be impossible to use the variable
1804          *       in an expression without Python misinterpreting what these are for
1805          */
1806 #ifdef WITH_PYTHON
1807         if (BPY_string_is_keyword(dvar->name)) {
1808                 dvar->flag |= DVAR_FLAG_INVALID_PY_KEYWORD;
1809         }
1810 #endif
1811
1812         /* If any these conditions match, the name is invalid */
1813         if (dvar->flag & DVAR_ALL_INVALID_FLAGS)
1814                 dvar->flag |= DVAR_FLAG_INVALID_NAME;
1815 }
1816
1817 /* Add a new driver variable */
1818 DriverVar *driver_add_new_variable(ChannelDriver *driver)
1819 {
1820         DriverVar *dvar;
1821
1822         /* sanity checks */
1823         if (driver == NULL)
1824                 return NULL;
1825
1826         /* make a new variable */
1827         dvar = MEM_callocN(sizeof(DriverVar), "DriverVar");
1828         BLI_addtail(&driver->variables, dvar);
1829
1830         /* give the variable a 'unique' name */
1831         strcpy(dvar->name, CTX_DATA_(BLT_I18NCONTEXT_ID_ACTION, "var"));
1832         BLI_uniquename(&driver->variables, dvar, CTX_DATA_(BLT_I18NCONTEXT_ID_ACTION, "var"), '_',
1833                        offsetof(DriverVar, name), sizeof(dvar->name));
1834
1835         /* set the default type to 'single prop' */
1836         driver_change_variable_type(dvar, DVAR_TYPE_SINGLE_PROP);
1837
1838 #ifdef WITH_PYTHON
1839         /* since driver variables are cached, the expression needs re-compiling too */
1840         if (driver->type == DRIVER_TYPE_PYTHON)
1841                 driver->flag |= DRIVER_FLAG_RENAMEVAR;
1842 #endif
1843
1844         /* return the target */
1845         return dvar;
1846 }
1847
1848 /* This frees the driver itself */
1849 void fcurve_free_driver(FCurve *fcu)
1850 {
1851         ChannelDriver *driver;
1852         DriverVar *dvar, *dvarn;
1853
1854         /* sanity checks */
1855         if (ELEM(NULL, fcu, fcu->driver))
1856                 return;
1857         driver = fcu->driver;
1858
1859         /* free driver targets */
1860         for (dvar = driver->variables.first; dvar; dvar = dvarn) {
1861                 dvarn = dvar->next;
1862                 driver_free_variable_ex(driver, dvar);
1863         }
1864
1865 #ifdef WITH_PYTHON
1866         /* free compiled driver expression */
1867         if (driver->expr_comp)
1868                 BPY_DECREF(driver->expr_comp);
1869 #endif
1870
1871         /* free driver itself, then set F-Curve's point to this to NULL (as the curve may still be used) */
1872         MEM_freeN(driver);
1873         fcu->driver = NULL;
1874 }
1875
1876 /* This makes a copy of the given driver */
1877 ChannelDriver *fcurve_copy_driver(const ChannelDriver *driver)
1878 {
1879         ChannelDriver *ndriver;
1880
1881         /* sanity checks */
1882         if (driver == NULL)
1883                 return NULL;
1884
1885         /* copy all data */
1886         ndriver = MEM_dupallocN(driver);
1887         ndriver->expr_comp = NULL;
1888
1889         /* copy variables */
1890         BLI_listbase_clear(&ndriver->variables); /* to get rid of refs to non-copied data (that's still used on original) */
1891         driver_variables_copy(&ndriver->variables, &driver->variables);
1892
1893         /* return the new driver */
1894         return ndriver;
1895 }
1896
1897 /* Driver Evaluation -------------------------- */
1898
1899 /* Evaluate a Driver Variable to get a value that contributes to the final */
1900 float driver_get_variable_value(ChannelDriver *driver, DriverVar *dvar)
1901 {
1902         const DriverVarTypeInfo *dvti;
1903
1904         /* sanity check */
1905         if (ELEM(NULL, driver, dvar))
1906                 return 0.0f;
1907
1908         /* call the relevant callbacks to get the variable value
1909          * using the variable type info, storing the obtained value
1910          * in dvar->curval so that drivers can be debugged
1911          */
1912         dvti = get_dvar_typeinfo(dvar->type);
1913
1914         if (dvti && dvti->get_value)
1915                 dvar->curval = dvti->get_value(driver, dvar);
1916         else
1917                 dvar->curval = 0.0f;
1918
1919         return dvar->curval;
1920 }
1921
1922 /* Evaluate an Channel-Driver to get a 'time' value to use instead of "evaltime"
1923  *      - "evaltime" is the frame at which F-Curve is being evaluated
1924  *  - has to return a float value
1925  */
1926 float evaluate_driver(PathResolvedRNA *anim_rna, ChannelDriver *driver, const float evaltime)
1927 {
1928         DriverVar *dvar;
1929
1930         /* check if driver can be evaluated */
1931         if (driver->flag & DRIVER_FLAG_INVALID)
1932                 return 0.0f;
1933
1934         switch (driver->type) {
1935                 case DRIVER_TYPE_AVERAGE: /* average values of driver targets */
1936                 case DRIVER_TYPE_SUM: /* sum values of driver targets */
1937                 {
1938                         /* check how many variables there are first (i.e. just one?) */
1939                         if (BLI_listbase_is_single(&driver->variables)) {
1940                                 /* just one target, so just use that */
1941                                 dvar = driver->variables.first;
1942                                 driver->curval = driver_get_variable_value(driver, dvar);
1943                         }
1944                         else {
1945                                 /* more than one target, so average the values of the targets */
1946                                 float value = 0.0f;
1947                                 int tot = 0;
1948
1949                                 /* loop through targets, adding (hopefully we don't get any overflow!) */
1950                                 for (dvar = driver->variables.first; dvar; dvar = dvar->next) {
1951                                         value += driver_get_variable_value(driver, dvar);
1952                                         tot++;
1953                                 }
1954
1955                                 /* perform operations on the total if appropriate */
1956                                 if (driver->type == DRIVER_TYPE_AVERAGE)
1957                                         driver->curval = tot ? (value / (float)tot) : 0.0f;
1958                                 else
1959                                         driver->curval = value;
1960                         }
1961                         break;
1962                 }
1963                 case DRIVER_TYPE_MIN: /* smallest value */
1964                 case DRIVER_TYPE_MAX: /* largest value */
1965                 {
1966                         float value = 0.0f;
1967
1968                         /* loop through the variables, getting the values and comparing them to existing ones */
1969                         for (dvar = driver->variables.first; dvar; dvar = dvar->next) {
1970                                 /* get value */
1971                                 float tmp_val = driver_get_variable_value(driver, dvar);
1972
1973                                 /* store this value if appropriate */
1974                                 if (dvar->prev) {
1975                                         /* check if greater/smaller than the baseline */
1976                                         if (driver->type == DRIVER_TYPE_MAX) {
1977                                                 /* max? */
1978                                                 if (tmp_val > value)
1979                                                         value = tmp_val;
1980                                         }
1981                                         else {
1982                                                 /* min? */
1983                                                 if (tmp_val < value)
1984                                                         value = tmp_val;
1985                                         }
1986                                 }
1987                                 else {
1988                                         /* first item - make this the baseline for comparisons */
1989                                         value = tmp_val;
1990                                 }
1991                         }
1992
1993                         /* store value in driver */
1994                         driver->curval = value;
1995                         break;
1996                 }
1997                 case DRIVER_TYPE_PYTHON: /* expression */
1998                 {
1999 #ifdef WITH_PYTHON
2000                         /* check for empty or invalid expression */
2001                         if ( (driver->expression[0] == '\0') ||
2002                              (driver->flag & DRIVER_FLAG_INVALID) )
2003                         {
2004                                 driver->curval = 0.0f;
2005                         }
2006                         else {
2007                                 /* this evaluates the expression using Python, and returns its result:
2008                                  *  - on errors it reports, then returns 0.0f
2009                                  */
2010                                 BLI_mutex_lock(&python_driver_lock);
2011
2012                                 driver->curval = BPY_driver_exec(anim_rna, driver, evaltime);
2013
2014                                 BLI_mutex_unlock(&python_driver_lock);
2015                         }
2016 #else /* WITH_PYTHON*/
2017                         UNUSED_VARS(anim_rna, evaltime);
2018 #endif /* WITH_PYTHON*/
2019                         break;
2020                 }
2021                 default:
2022                 {
2023                         /* special 'hack' - just use stored value
2024                          *      This is currently used as the mechanism which allows animated settings to be able
2025                          *  to be changed via the UI.
2026                          */
2027                         break;
2028                 }
2029         }
2030
2031         /* return value for driver */
2032         return driver->curval;
2033 }
2034
2035 /* ***************************** Curve Calculations ********************************* */
2036
2037 /* The total length of the handles is not allowed to be more
2038  * than the horizontal distance between (v1-v4).
2039  * This is to prevent curve loops.
2040  */
2041 void correct_bezpart(float v1[2], float v2[2], float v3[2], float v4[2])
2042 {
2043         float h1[2], h2[2], len1, len2, len, fac;
2044
2045         /* calculate handle deltas */
2046         h1[0] = v1[0] - v2[0];
2047         h1[1] = v1[1] - v2[1];
2048
2049         h2[0] = v4[0] - v3[0];
2050         h2[1] = v4[1] - v3[1];
2051
2052         /* calculate distances:
2053          *  - len       = span of time between keyframes
2054          *      - len1  = length of handle of start key
2055          *      - len2  = length of handle of end key
2056          */
2057         len = v4[0] - v1[0];
2058         len1 = fabsf(h1[0]);
2059         len2 = fabsf(h2[0]);
2060
2061         /* if the handles have no length, no need to do any corrections */
2062         if ((len1 + len2) == 0.0f)
2063                 return;
2064
2065         /* the two handles cross over each other, so force them
2066          * apart using the proportion they overlap
2067          */
2068         if ((len1 + len2) > len) {
2069                 fac = len / (len1 + len2);
2070
2071                 v2[0] = (v1[0] - fac * h1[0]);
2072                 v2[1] = (v1[1] - fac * h1[1]);
2073
2074                 v3[0] = (v4[0] - fac * h2[0]);
2075                 v3[1] = (v4[1] - fac * h2[1]);
2076         }
2077 }
2078
2079 /* find root ('zero') */
2080 static int findzero(float x, float q0, float q1, float q2, float q3, float *o)
2081 {
2082         double c0, c1, c2, c3, a, b, c, p, q, d, t, phi;
2083         int nr = 0;
2084
2085         c0 = q0 - x;
2086         c1 = 3.0f * (q1 - q0);
2087         c2 = 3.0f * (q0 - 2.0f * q1 + q2);
2088         c3 = q3 - q0 + 3.0f * (q1 - q2);
2089
2090         if (c3 != 0.0) {
2091                 a = c2 / c3;
2092                 b = c1 / c3;
2093                 c = c0 / c3;
2094                 a = a / 3;
2095
2096                 p = b / 3 - a * a;
2097                 q = (2 * a * a * a - a * b + c) / 2;
2098                 d = q * q + p * p * p;
2099
2100                 if (d > 0.0) {
2101                         t = sqrt(d);
2102                         o[0] = (float)(sqrt3d(-q + t) + sqrt3d(-q - t) - a);
2103
2104                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
2105                         else return 0;
2106                 }
2107                 else if (d == 0.0) {
2108                         t = sqrt3d(-q);
2109                         o[0] = (float)(2 * t - a);
2110
2111                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
2112                         o[nr] = (float)(-t - a);
2113
2114                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr + 1;
2115                         else return nr;
2116                 }
2117                 else {
2118                         phi = acos(-q / sqrt(-(p * p * p)));
2119                         t = sqrt(-p);
2120                         p = cos(phi / 3);
2121                         q = sqrt(3 - 3 * p * p);
2122                         o[0] = (float)(2 * t * p - a);
2123
2124                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
2125                         o[nr] = (float)(-t * (p + q) - a);
2126
2127                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) nr++;
2128                         o[nr] = (float)(-t * (p - q) - a);
2129
2130                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr + 1;
2131                         else return nr;
2132                 }
2133         }
2134         else {
2135                 a = c2;
2136                 b = c1;
2137                 c = c0;
2138
2139                 if (a != 0.0) {
2140                         /* discriminant */
2141                         p = b * b - 4 * a * c;
2142
2143                         if (p > 0) {
2144                                 p = sqrt(p);
2145                                 o[0] = (float)((-b - p) / (2 * a));
2146
2147                                 if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
2148                                 o[nr] = (float)((-b + p) / (2 * a));
2149
2150                                 if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr + 1;
2151                                 else return nr;
2152                         }
2153                         else if (p == 0) {
2154                                 o[0] = (float)(-b / (2 * a));
2155                                 if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
2156                                 else return 0;
2157                         }
2158                 }
2159                 else if (b != 0.0) {
2160                         o[0] = (float)(-c / b);
2161
2162                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
2163                         else return 0;
2164                 }
2165                 else if (c == 0.0) {
2166                         o[0] = 0.0;
2167                         return 1;
2168                 }
2169
2170                 return 0;
2171         }
2172 }
2173
2174 static void berekeny(float f1, float f2, float f3, float f4, float *o, int b)
2175 {
2176         float t, c0, c1, c2, c3;
2177         int a;
2178
2179         c0 = f1;
2180         c1 = 3.0f * (f2 - f1);
2181         c2 = 3.0f * (f1 - 2.0f * f2 + f3);
2182         c3 = f4 - f1 + 3.0f * (f2 - f3);
2183
2184         for (a = 0; a < b; a++) {
2185                 t = o[a];
2186                 o[a] = c0 + t * c1 + t * t * c2 + t * t * t * c3;
2187         }
2188 }
2189
2190 #if 0
2191 static void berekenx(float *f, float *o, int b)
2192 {
2193         float t, c0, c1, c2, c3;
2194         int a;
2195
2196         c0 = f[0];
2197         c1 = 3.0f * (f[3] - f[0]);
2198         c2 = 3.0f * (f[0] - 2.0f * f[3] + f[6]);
2199         c3 = f[9] - f[0] + 3.0f * (f[3] - f[6]);
2200
2201         for (a = 0; a < b; a++) {
2202                 t = o[a];
2203                 o[a] = c0 + t * c1 + t * t * c2 + t * t * t * c3;
2204         }
2205 }
2206 #endif
2207
2208
2209 /* -------------------------- */
2210
2211 /* Calculate F-Curve value for 'evaltime' using BezTriple keyframes */
2212 static float fcurve_eval_keyframes(FCurve *fcu, BezTriple *bezts, float evaltime)
2213 {
2214         const float eps = 1.e-8f;
2215         BezTriple *bezt, *prevbezt, *lastbezt;
2216         float v1[2], v2[2], v3[2], v4[2], opl[32], dx, fac;
2217         unsigned int a;
2218         int b;
2219         float cvalue = 0.0f;
2220
2221         /* get pointers */
2222         a = fcu->totvert - 1;
2223         prevbezt = bezts;
2224         bezt = prevbezt + 1;
2225         lastbezt = prevbezt + a;
2226
2227         /* evaluation time at or past endpoints? */
2228         if (prevbezt->vec[1][0] >= evaltime) {
2229                 /* before or on first keyframe */
2230                 if ( (fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (prevbezt->ipo != BEZT_IPO_CONST) &&
2231                      !(fcu->flag & FCURVE_DISCRETE_VALUES) )
2232                 {
2233                         /* linear or bezier interpolation */
2234                         if (prevbezt->ipo == BEZT_IPO_LIN) {
2235                                 /* Use the next center point instead of our own handle for
2236                                  * linear interpolated extrapolate
2237                                  */
2238                                 if (fcu->totvert == 1) {
2239                                         cvalue = prevbezt->vec[1][1];
2240                                 }
2241                                 else {
2242                                         bezt = prevbezt + 1;
2243                                         dx = prevbezt->vec[1][0] - evaltime;
2244                                         fac = bezt->vec[1][0] - prevbezt->vec[1][0];
2245
2246                                         /* prevent division by zero */
2247                                         if (fac) {
2248                                                 fac = (bezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
2249                                                 cvalue = prevbezt->vec[1][1] - (fac * dx);
2250                                         }
2251                                         else {
2252                                                 cvalue = prevbezt->vec[1][1];
2253                                         }
2254                                 }
2255                         }
2256                         else {
2257                                 /* Use the first handle (earlier) of first BezTriple to calculate the
2258                                  * gradient and thus the value of the curve at evaltime
2259                                  */
2260                                 dx = prevbezt->vec[1][0] - evaltime;
2261                                 fac = prevbezt->vec[1][0] - prevbezt->vec[0][0];
2262
2263                                 /* prevent division by zero */
2264                                 if (fac) {
2265                                         fac = (prevbezt->vec[1][1] - prevbezt->vec[0][1]) / fac;
2266                                         cvalue = prevbezt->vec[1][1] - (fac * dx);
2267                                 }
2268                                 else {
2269                                         cvalue = prevbezt->vec[1][1];
2270                                 }
2271                         }
2272                 }
2273                 else {
2274                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation,
2275                          * so just extend first keyframe's value
2276                          */
2277                         cvalue = prevbezt->vec[1][1];
2278                 }
2279         }
2280         else if (lastbezt->vec[1][0] <= evaltime) {
2281                 /* after or on last keyframe */
2282                 if ( (fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (lastbezt->ipo != BEZT_IPO_CONST) &&
2283                      !(fcu->flag & FCURVE_DISCRETE_VALUES) )
2284                 {
2285                         /* linear or bezier interpolation */
2286                         if (lastbezt->ipo == BEZT_IPO_LIN) {
2287                                 /* Use the next center point instead of our own handle for
2288                                  * linear interpolated extrapolate
2289                                  */
2290                                 if (fcu->totvert == 1) {
2291                                         cvalue = lastbezt->vec[1][1];
2292                                 }
2293                                 else {
2294                                         prevbezt = lastbezt - 1;
2295                                         dx = evaltime - lastbezt->vec[1][0];
2296                                         fac = lastbezt->vec[1][0] - prevbezt->vec[1][0];
2297
2298                                         /* prevent division by zero */
2299                                         if (fac) {
2300                                                 fac = (lastbezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
2301                                                 cvalue = lastbezt->vec[1][1] + (fac * dx);
2302                                         }
2303                                         else {
2304                                                 cvalue = lastbezt->vec[1][1];
2305                                         }
2306                                 }
2307                         }
2308                         else {
2309                                 /* Use the gradient of the second handle (later) of last BezTriple to calculate the
2310                                  * gradient and thus the value of the curve at evaltime
2311                                  */
2312                                 dx = evaltime - lastbezt->vec[1][0];
2313                                 fac = lastbezt->vec[2][0] - lastbezt->vec[1][0];
2314
2315                                 /* prevent division by zero */
2316                                 if (fac) {
2317                                         fac = (lastbezt->vec[2][1] - lastbezt->vec[1][1]) / fac;
2318                                         cvalue = lastbezt->vec[1][1] + (fac * dx);
2319                                 }
2320                                 else {
2321                                         cvalue = lastbezt->vec[1][1];
2322                                 }
2323                         }
2324                 }
2325                 else {
2326                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation,
2327                          * so just extend last keyframe's value
2328                          */
2329                         cvalue = lastbezt->vec[1][1];
2330                 }
2331         }
2332         else {
2333                 /* evaltime occurs somewhere in the middle of the curve */
2334                 bool exact = false;
2335
2336                 /* Use binary search to find appropriate keyframes...
2337                  *
2338                  * The threshold here has the following constraints:
2339                  *    - 0.001   is too coarse   -> We get artifacts with 2cm driver movements at 1BU = 1m (see T40332)
2340                  *    - 0.00001 is too fine     -> Weird errors, like selecting the wrong keyframe range (see T39207), occur.
2341                  *                                 This lower bound was established in b888a32eee8147b028464336ad2404d8155c64dd
2342                  */
2343                 a = binarysearch_bezt_index_ex(bezts, evaltime, fcu->totvert, 0.0001, &exact);
2344                 if (G.debug & G_DEBUG) printf("eval fcurve '%s' - %f => %u/%u, %d\n", fcu->rna_path, evaltime, a, fcu->totvert, exact);
2345
2346                 if (exact) {
2347                         /* index returned must be interpreted differently when it sits on top of an existing keyframe
2348                          * - that keyframe is the start of the segment we need (see action_bug_2.blend in T39207)
2349                          */
2350                         prevbezt = bezts + a;
2351                         bezt = (a < fcu->totvert - 1) ? (prevbezt + 1) : prevbezt;
2352                 }
2353                 else {
2354                         /* index returned refers to the keyframe that the eval-time occurs *before*
2355                          * - hence, that keyframe marks the start of the segment we're dealing with
2356                          */
2357                         bezt = bezts + a;
2358                         prevbezt = (a > 0) ? (bezt - 1) : bezt;
2359                 }
2360
2361                 /* use if the key is directly on the frame, rare cases this is needed else we get 0.0 instead. */
2362                 /* XXX: consult T39207 for examples of files where failure of these checks can cause issues */
2363                 if (exact) {
2364                         cvalue = prevbezt->vec[1][1];
2365                 }
2366                 else if (fabsf(bezt->vec[1][0] - evaltime) < eps) {
2367                         cvalue = bezt->vec[1][1];
2368                 }
2369                 /* evaltime occurs within the interval defined by these two keyframes */
2370                 else if ((prevbezt->vec[1][0] <= evaltime) && (bezt->vec[1][0] >= evaltime)) {
2371                         const float begin = prevbezt->vec[1][1];
2372                         const float change = bezt->vec[1][1] - prevbezt->vec[1][1];
2373                         const float duration = bezt->vec[1][0] - prevbezt->vec[1][0];
2374                         const float time = evaltime - prevbezt->vec[1][0];
2375                         const float amplitude = prevbezt->amplitude;
2376                         const float period = prevbezt->period;
2377
2378                         /* value depends on interpolation mode */
2379                         if ((prevbezt->ipo == BEZT_IPO_CONST) || (fcu->flag & FCURVE_DISCRETE_VALUES) || (duration == 0)) {
2380                                 /* constant (evaltime not relevant, so no interpolation needed) */
2381                                 cvalue = prevbezt->vec[1][1];
2382                         }
2383                         else {
2384                                 switch (prevbezt->ipo) {
2385                                         /* interpolation ...................................... */
2386                                         case BEZT_IPO_BEZ:
2387                                                 /* bezier interpolation */
2388                                                 /* (v1, v2) are the first keyframe and its 2nd handle */
2389                                                 v1[0] = prevbezt->vec[1][0];
2390                                                 v1[1] = prevbezt->vec[1][1];
2391                                                 v2[0] = prevbezt->vec[2][0];
2392                                                 v2[1] = prevbezt->vec[2][1];
2393                                                 /* (v3, v4) are the last keyframe's 1st handle + the last keyframe */
2394                                                 v3[0] = bezt->vec[0][0];
2395                                                 v3[1] = bezt->vec[0][1];
2396                                                 v4[0] = bezt->vec[1][0];
2397                                                 v4[1] = bezt->vec[1][1];
2398
2399                                                 if (fabsf(v1[1] - v4[1]) < FLT_EPSILON &&
2400                                                     fabsf(v2[1] - v3[1]) < FLT_EPSILON &&
2401                                                     fabsf(v3[1] - v4[1]) < FLT_EPSILON)
2402                                                 {
2403                                                         /* Optimisation: If all the handles are flat/at the same values,
2404                                                          * the value is simply the shared value (see T40372 -> F91346)
2405                                                          */
2406                                                         cvalue = v1[1];
2407                                                 }
2408                                                 else {
2409                                                         /* adjust handles so that they don't overlap (forming a loop) */
2410                                                         correct_bezpart(v1, v2, v3, v4);
2411
2412                                                         /* try to get a value for this position - if failure, try another set of points */
2413                                                         b = findzero(evaltime, v1[0], v2[0], v3[0], v4[0], opl);
2414                                                         if (b) {
2415                                                                 berekeny(v1[1], v2[1], v3[1], v4[1], opl, 1);
2416                                                                 cvalue = opl[0];
2417                                                                 /* break; */
2418                                                         }
2419                                                         else {
2420                                                                 if (G.debug & G_DEBUG) printf("    ERROR: findzero() failed at %f with %f %f %f %f\n", evaltime, v1[0], v2[0], v3[0], v4[0]);
2421                                                         }
2422                                                 }
2423                                                 break;
2424
2425                                         case BEZT_IPO_LIN:
2426                                                 /* linear - simply linearly interpolate between values of the two keyframes */
2427                                                 cvalue = BLI_easing_linear_ease(time, begin, change, duration);
2428                                                 break;
2429
2430                                         /* easing ............................................ */
2431                                         case BEZT_IPO_BACK:
2432                                                 switch (prevbezt->easing) {
2433                                                         case BEZT_IPO_EASE_IN:
2434                                                                 cvalue = BLI_easing_back_ease_in(time, begin, change, duration, prevbezt->back);
2435                                                                 break;
2436                                                         case BEZT_IPO_EASE_OUT:
2437                                                                 cvalue = BLI_easing_back_ease_out(time, begin, change, duration, prevbezt->back);
2438                                                                 break;
2439                                                         case BEZT_IPO_EASE_IN_OUT:
2440                                                                 cvalue = BLI_easing_back_ease_in_out(time, begin, change, duration, prevbezt->back);
2441                                                                 break;
2442
2443                                                         default: /* default/auto: same as ease out */
2444                                                                 cvalue = BLI_easing_back_ease_out(time, begin, change, duration, prevbezt->back);
2445                                                                 break;
2446                                                 }
2447                                                 break;
2448
2449                                         case BEZT_IPO_BOUNCE:
2450                                                 switch (prevbezt->easing) {
2451                                                         case BEZT_IPO_EASE_IN:
2452                                                                 cvalue = BLI_easing_bounce_ease_in(time, begin, change, duration);
2453                                                                 break;
2454                                                         case BEZT_IPO_EASE_OUT:
2455                                                                 cvalue = BLI_easing_bounce_ease_out(time, begin, change, duration);
2456                                                                 break;
2457                                                         case BEZT_IPO_EASE_IN_OUT:
2458                                                                 cvalue = BLI_easing_bounce_ease_in_out(time, begin, change, duration);
2459                                                                 break;
2460
2461                                                         default: /* default/auto: same as ease out */
2462                                                                 cvalue = BLI_easing_bounce_ease_out(time, begin, change, duration);
2463                                                                 break;
2464                                                 }
2465                                                 break;
2466
2467                                         case BEZT_IPO_CIRC:
2468                                                 switch (prevbezt->easing) {
2469                                                         case BEZT_IPO_EASE_IN:
2470                                                                 cvalue = BLI_easing_circ_ease_in(time, begin, change, duration);
2471                                                                 break;
2472                                                         case BEZT_IPO_EASE_OUT:
2473                                                                 cvalue = BLI_easing_circ_ease_out(time, begin, change, duration);
2474                                                                 break;
2475                                                         case BEZT_IPO_EASE_IN_OUT:
2476                                                                 cvalue = BLI_easing_circ_ease_in_out(time, begin, change, duration);
2477                                                                 break;
2478
2479                                                         default: /* default/auto: same as ease in */
2480                                                                 cvalue = BLI_easing_circ_ease_in(time, begin, change, duration);
2481                                                                 break;
2482                                                 }
2483                                                 break;
2484
2485                                         case BEZT_IPO_CUBIC:
2486                                                 switch (prevbezt->easing) {
2487                                                         case BEZT_IPO_EASE_IN:
2488                                                                 cvalue = BLI_easing_cubic_ease_in(time, begin, change, duration);
2489                                                                 break;
2490                                                         case BEZT_IPO_EASE_OUT:
2491                                                                 cvalue = BLI_easing_cubic_ease_out(time, begin, change, duration);
2492                                                                 break;
2493                                                         case BEZT_IPO_EASE_IN_OUT:
2494                                                                 cvalue = BLI_easing_cubic_ease_in_out(time, begin, change, duration);
2495                                                                 break;
2496
2497                                                         default: /* default/auto: same as ease in */
2498                                                                 cvalue = BLI_easing_cubic_ease_in(time, begin, change, duration);
2499                                                                 break;
2500                                                 }
2501                                                 break;
2502
2503                                         case BEZT_IPO_ELASTIC:
2504                                                 switch (prevbezt->easing) {
2505                                                         case BEZT_IPO_EASE_IN:
2506                                                                 cvalue = BLI_easing_elastic_ease_in(time, begin, change, duration, amplitude, period);
2507                                                                 break;
2508                                                         case BEZT_IPO_EASE_OUT:
2509                                                                 cvalue = BLI_easing_elastic_ease_out(time, begin, change, duration, amplitude, period);
2510                                                                 break;
2511                                                         case BEZT_IPO_EASE_IN_OUT:
2512                                                                 cvalue = BLI_easing_elastic_ease_in_out(time, begin, change, duration, amplitude, period);
2513                                                                 break;
2514
2515                                                         default: /* default/auto: same as ease out */
2516                                                                 cvalue = BLI_easing_elastic_ease_out(time, begin, change, duration, amplitude, period);
2517                                                                 break;
2518                                                 }
2519                                                 break;
2520
2521                                         case BEZT_IPO_EXPO:
2522                                                 switch (prevbezt->easing) {
2523                                                         case BEZT_IPO_EASE_IN:
2524                                                                 cvalue = BLI_easing_expo_ease_in(time, begin, change, duration);
2525                                                                 break;
2526                                                         case BEZT_IPO_EASE_OUT:
2527                                                                 cvalue = BLI_easing_expo_ease_out(time, begin, change, duration);
2528                                                                 break;
2529                                                         case BEZT_IPO_EASE_IN_OUT:
2530                                                                 cvalue = BLI_easing_expo_ease_in_out(time, begin, change, duration);
2531                                                                 break;
2532
2533                                                         default: /* default/auto: same as ease in */
2534                                                                 cvalue = BLI_easing_expo_ease_in(time, begin, change, duration);
2535                                                                 break;
2536                                                 }
2537                                                 break;
2538
2539                                         case BEZT_IPO_QUAD:
2540                                                 switch (prevbezt->easing) {
2541                                                         case BEZT_IPO_EASE_IN:
2542                                                                 cvalue = BLI_easing_quad_ease_in(time, begin, change, duration);
2543                                                                 break;
2544                                                         case BEZT_IPO_EASE_OUT:
2545                                                                 cvalue = BLI_easing_quad_ease_out(time, begin, change, duration);
2546                                                                 break;
2547                                                         case BEZT_IPO_EASE_IN_OUT:
2548                                                                 cvalue = BLI_easing_quad_ease_in_out(time, begin, change, duration);
2549                                                                 break;
2550
2551                                                         default: /* default/auto: same as ease in */
2552                                                                 cvalue = BLI_easing_quad_ease_in(time, begin, change, duration);
2553                                                                 break;
2554                                                 }
2555                                                 break;
2556
2557                                         case BEZT_IPO_QUART:
2558                                                 switch (prevbezt->easing) {
2559                                                         case BEZT_IPO_EASE_IN:
2560                                                                 cvalue = BLI_easing_quart_ease_in(time, begin, change, duration);
2561                                                                 break;
2562                                                         case BEZT_IPO_EASE_OUT:
2563                                                                 cvalue = BLI_easing_quart_ease_out(time, begin, change, duration);
2564                                                                 break;
2565                                                         case BEZT_IPO_EASE_IN_OUT:
2566                                                                 cvalue = BLI_easing_quart_ease_in_out(time, begin, change, duration);
2567                                                                 break;
2568
2569                                                         default: /* default/auto: same as ease in */
2570                                                                 cvalue = BLI_easing_quart_ease_in(time, begin, change, duration);
2571                                                                 break;
2572                                                 }
2573                                                 break;
2574
2575                                         case BEZT_IPO_QUINT:
2576                                                 switch (prevbezt->easing) {
2577                                                         case BEZT_IPO_EASE_IN:
2578                                                                 cvalue = BLI_easing_quint_ease_in(time, begin, change, duration);
2579                                                                 break;
2580                                                         case BEZT_IPO_EASE_OUT:
2581                                                                 cvalue = BLI_easing_quint_ease_out(time, begin, change, duration);
2582                                                                 break;
2583                                                         case BEZT_IPO_EASE_IN_OUT:
2584                                                                 cvalue = BLI_easing_quint_ease_in_out(time, begin, change, duration);
2585                                                                 break;
2586
2587                                                         default: /* default/auto: same as ease in */
2588                                                                 cvalue = BLI_easing_quint_ease_in(time, begin, change, duration);
2589                                                                 break;
2590                                                 }
2591                                                 break;
2592
2593                                         case BEZT_IPO_SINE:
2594                                                 switch (prevbezt->easing) {
2595                                                         case BEZT_IPO_EASE_IN:
2596                                                                 cvalue = BLI_easing_sine_ease_in(time, begin, change, duration);
2597                                                                 break;
2598                                                         case BEZT_IPO_EASE_OUT:
2599                                                                 cvalue = BLI_easing_sine_ease_out(time, begin, change, duration);
2600                                                                 break;
2601                                                         case BEZT_IPO_EASE_IN_OUT:
2602                                                                 cvalue = BLI_easing_sine_ease_in_out(time, begin, change, duration);
2603                                                                 break;
2604
2605                                                         default: /* default/auto: same as ease in */
2606                                                                 cvalue = BLI_easing_sine_ease_in(time, begin, change, duration);
2607                                                                 break;
2608                                                 }
2609                                                 break;
2610
2611
2612                                         default:
2613                                                 cvalue = prevbezt->vec[1][1];
2614                                                 break;
2615                                 }
2616                         }
2617                 }
2618                 else {
2619                         if (G.debug & G_DEBUG) printf("   ERROR: failed eval - p=%f b=%f, t=%f (%f)\n", prevbezt->vec[1][0], bezt->vec[1][0], evaltime, fabsf(bezt->vec[1][0] - evaltime));
2620                 }
2621         }
2622
2623         /* return value */
2624         return cvalue;
2625 }
2626
2627 /* Calculate F-Curve value for 'evaltime' using FPoint samples */
2628 static float fcurve_eval_samples(FCurve *fcu, FPoint *fpts, float evaltime)
2629 {
2630         FPoint *prevfpt, *lastfpt, *fpt;
2631         float cvalue = 0.0f;
2632
2633         /* get pointers */
2634         prevfpt = fpts;
2635         lastfpt = prevfpt + fcu->totvert - 1;
2636
2637         /* evaluation time at or past endpoints? */
2638         if (prevfpt->vec[0] >= evaltime) {
2639                 /* before or on first sample, so just extend value */
2640                 cvalue = prevfpt->vec[1];
2641         }
2642         else if (lastfpt->vec[0] <= evaltime) {
2643                 /* after or on last sample, so just extend value */
2644                 cvalue = lastfpt->vec[1];
2645         }
2646         else {
2647                 float t = fabsf(evaltime - floorf(evaltime));
2648
2649                 /* find the one on the right frame (assume that these are spaced on 1-frame intervals) */
2650                 fpt = prevfpt + ((int)evaltime - (int)prevfpt->vec[0]);
2651
2652                 /* if not exactly on the frame, perform linear interpolation with the next one */
2653                 if ((t != 0.0f) && (t < 1.0f))
2654                         cvalue = interpf(fpt->vec[1], (fpt + 1)->vec[1], 1.0f - t);
2655                 else
2656                         cvalue = fpt->vec[1];
2657         }
2658
2659         /* return value */
2660         return cvalue;
2661 }
2662
2663 /* ***************************** F-Curve - Evaluation ********************************* */
2664
2665 /* Evaluate and return the value of the given F-Curve at the specified frame ("evaltime")
2666  * Note: this is also used for drivers
2667  */
2668 static float evaluate_fcurve_ex(FCurve *fcu, float evaltime, float cvalue)
2669 {
2670         FModifierStackStorage *storage;
2671         float devaltime;
2672
2673         /* evaluate modifiers which modify time to evaluate the base curve at */
2674         storage = evaluate_fmodifiers_storage_new(&fcu->modifiers);
2675         devaltime = evaluate_time_fmodifiers(storage, &fcu->modifiers, fcu, cvalue, evaltime);
2676
2677         /* evaluate curve-data
2678          *      - 'devaltime' instead of 'evaltime', as this is the time that the last time-modifying
2679          *        F-Curve modifier on the stack requested the curve to be evaluated at
2680          */
2681         if (fcu->bezt)
2682                 cvalue = fcurve_eval_keyframes(fcu, fcu->bezt, devaltime);
2683         else if (fcu->fpt)
2684                 cvalue = fcurve_eval_samples(fcu, fcu->fpt, devaltime);
2685
2686         /* evaluate modifiers */
2687         evaluate_value_fmodifiers(storage, &fcu->modifiers, fcu, &cvalue, devaltime);
2688
2689         evaluate_fmodifiers_storage_free(storage);
2690
2691         /* if curve can only have integral values, perform truncation (i.e. drop the decimal part)
2692          * here so that the curve can be sampled correctly
2693          */
2694         if (fcu->flag & FCURVE_INT_VALUES)
2695                 cvalue = floorf(cvalue + 0.5f);
2696
2697         /* return evaluated value */
2698         return cvalue;
2699 }
2700
2701 float evaluate_fcurve(FCurve *fcu, float evaltime)
2702 {
2703         BLI_assert(fcu->driver == NULL);
2704
2705         return evaluate_fcurve_ex(fcu, evaltime, 0.0);
2706 }
2707
2708 float evaluate_fcurve_driver(PathResolvedRNA *anim_rna, FCurve *fcu, float evaltime)
2709 {
2710         BLI_assert(fcu->driver != NULL);
2711         float cvalue = 0.0f;
2712
2713         /* if there is a driver (only if this F-Curve is acting as 'driver'), evaluate it to find value to use as "evaltime"
2714          * since drivers essentially act as alternative input (i.e. in place of 'time') for F-Curves
2715          */
2716         if (fcu->driver) {
2717                 /* evaltime now serves as input for the curve */
2718                 evaltime = evaluate_driver(anim_rna, fcu->driver, evaltime);
2719
2720                 /* only do a default 1-1 mapping if it's unlikely that anything else will set a value... */
2721                 if (fcu->totvert == 0) {
2722                         FModifier *fcm;
2723                         bool do_linear = true;
2724
2725                         /* out-of-range F-Modifiers will block, as will those which just plain overwrite the values
2726                          * XXX: additive is a bit more dicey; it really depends then if things are in range or not...
2727                          */
2728                         for (fcm = fcu->modifiers.first; fcm; fcm = fcm->next) {
2729                                 /* if there are range-restrictions, we must definitely block [#36950] */
2730                                 if ((fcm->flag & FMODIFIER_FLAG_RANGERESTRICT) == 0 ||
2731                                     ((fcm->sfra <= evaltime) && (fcm->efra >= evaltime)) )
2732                                 {
2733                                         /* within range: here it probably doesn't matter, though we'd want to check on additive... */
2734                                 }
2735                                 else {
2736                                         /* outside range: modifier shouldn't contribute to the curve here, though it does in other areas,
2737                                          * so neither should the driver!
2738                                          */
2739                                         do_linear = false;
2740                                 }
2741                         }
2742
2743                         /* only copy over results if none of the modifiers disagreed with this */
2744                         if (do_linear) {
2745                                 cvalue = evaltime;
2746                         }
2747                 }
2748         }
2749
2750         return evaluate_fcurve_ex(fcu, evaltime, cvalue);
2751 }
2752
2753 /* Calculate the value of the given F-Curve at the given frame, and set its curval */
2754 float calculate_fcurve(PathResolvedRNA *anim_rna, FCurve *fcu, float evaltime)
2755 {
2756         /* only calculate + set curval (overriding the existing value) if curve has
2757          * any data which warrants this...
2758          */
2759         if ((fcu->totvert) || (fcu->driver && !(fcu->driver->flag & DRIVER_FLAG_INVALID)) ||
2760             list_has_suitable_fmodifier(&fcu->modifiers, 0, FMI_TYPE_GENERATE_CURVE))
2761         {
2762                 /* calculate and set curval (evaluates driver too if necessary) */
2763                 float curval;
2764                 if (fcu->driver) {
2765                         curval = evaluate_fcurve_driver(anim_rna, fcu, evaltime);
2766                 }
2767                 else {
2768                         curval = evaluate_fcurve(fcu, evaltime);
2769                 }
2770                 fcu->curval = curval;  /* debug display only, not thread safe! */
2771                 return curval;
2772         }
2773         else {
2774                 return 0.0f;
2775         }
2776 }
2777