fcurve.c

Go to the documentation of this file.

/*
 * $Id: fcurve.c 36779 2011-05-19 12:39:57Z campbellbarton $
 *
 * ***** BEGIN GPL LICENSE BLOCK *****
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
 * All rights reserved.
 *
 * The Original Code is: all of this file.
 *
 * Contributor(s): Joshua Leung (full recode)
 *
 * ***** END GPL LICENSE BLOCK *****
 */

#include <math.h>
#include <stdio.h>
#include <stddef.h>
#include <string.h>
#include <float.h>

#include "MEM_guardedalloc.h"

#include "DNA_anim_types.h"
#include "DNA_object_types.h"

#include "BLI_blenlib.h"
#include "BLI_math.h"
#include "BLI_utildefines.h"

#include "BKE_fcurve.h"
#include "BKE_animsys.h"
#include "BKE_action.h"
#include "BKE_armature.h"
#include "BKE_curve.h" 
#include "BKE_global.h"
#include "BKE_object.h"
#include "BKE_utildefines.h"

#include "RNA_access.h"

#ifdef WITH_PYTHON
#include "BPY_extern.h" 
#endif

#define SMALL -1.0e-10
#define SELECT 1

/* ************************** Data-Level Functions ************************* */

/* ---------------------- Freeing --------------------------- */

/* Frees the F-Curve itself too, so make sure BLI_remlink is called before calling this... */
void free_fcurve (FCurve *fcu) 
{
        if (fcu == NULL) 
                return;
        
        /* free curve data */
        if (fcu) {
                if (fcu->bezt) MEM_freeN(fcu->bezt);
                if (fcu->fpt) MEM_freeN(fcu->fpt);
        }
        
        /* free RNA-path, as this were allocated when getting the path string */
        if (fcu->rna_path)
                MEM_freeN(fcu->rna_path);
        
        /* free extra data - i.e. modifiers, and driver */
        fcurve_free_driver(fcu);
        free_fmodifiers(&fcu->modifiers);
        
        /* free f-curve itself */
        MEM_freeN(fcu);
}

/* Frees a list of F-Curves */
void free_fcurves (ListBase *list)
{
        FCurve *fcu, *fcn;
        
        /* sanity check */
        if (list == NULL)
                return;
                
        /* free data - no need to call remlink before freeing each curve, 
         * as we store reference to next, and freeing only touches the curve
         * it's given
         */
        for (fcu= list->first; fcu; fcu= fcn) {
                fcn= fcu->next;
                free_fcurve(fcu);
        }
        
        /* clear pointers just in case */
        list->first= list->last= NULL;
}       

/* ---------------------- Copy --------------------------- */

/* duplicate an F-Curve */
FCurve *copy_fcurve (FCurve *fcu)
{
        FCurve *fcu_d;
        
        /* sanity check */
        if (fcu == NULL)
                return NULL;
                
        /* make a copy */
        fcu_d= MEM_dupallocN(fcu);
        
        fcu_d->next= fcu_d->prev= NULL;
        fcu_d->grp= NULL;
        
        /* copy curve data */
        fcu_d->bezt= MEM_dupallocN(fcu_d->bezt);
        fcu_d->fpt= MEM_dupallocN(fcu_d->fpt);
        
        /* copy rna-path */
        fcu_d->rna_path= MEM_dupallocN(fcu_d->rna_path);
        
        /* copy driver */
        fcu_d->driver= fcurve_copy_driver(fcu_d->driver);
        
        /* copy modifiers */
        copy_fmodifiers(&fcu_d->modifiers, &fcu->modifiers);
        
        /* return new data */
        return fcu_d;
}

/* duplicate a list of F-Curves */
void copy_fcurves (ListBase *dst, ListBase *src)
{
        FCurve *dfcu, *sfcu;
        
        /* sanity checks */
        if ELEM(NULL, dst, src)
                return;
        
        /* clear destination list first */
        dst->first= dst->last= NULL;
        
        /* copy one-by-one */
        for (sfcu= src->first; sfcu; sfcu= sfcu->next) {
                dfcu= copy_fcurve(sfcu);
                BLI_addtail(dst, dfcu);
        }
}

/* ----------------- Finding F-Curves -------------------------- */

/* high level function to get an fcurve from C without having the rna */
FCurve *id_data_find_fcurve(ID *id, void *data, StructRNA *type, const char *prop_name, int index)
{
        /* anim vars */
        AnimData *adt= BKE_animdata_from_id(id);
        FCurve *fcu= NULL;

        /* rna vars */
        PointerRNA ptr;
        PropertyRNA *prop;
        char *path;
        
        /* only use the current action ??? */
        if (ELEM(NULL, adt, adt->action))
                return NULL;
        
        RNA_pointer_create(id, type, data, &ptr);
        prop = RNA_struct_find_property(&ptr, prop_name);
        
        if (prop) {
                path= RNA_path_from_ID_to_property(&ptr, prop);
                        
                if (path) {
                        /* animation takes priority over drivers */
                        if ((adt->action) && (adt->action->curves.first))
                                fcu= list_find_fcurve(&adt->action->curves, path, index);
                        
                        /* if not animated, check if driven */
#if 0
                        if ((fcu == NULL) && (adt->drivers.first)) {
                                fcu= list_find_fcurve(&adt->drivers, path, but->rnaindex);
                        }
#endif
                        
                        MEM_freeN(path);
                }
        }

        return fcu;
}


/* Find the F-Curve affecting the given RNA-access path + index, in the list of F-Curves provided */
FCurve *list_find_fcurve (ListBase *list, const char rna_path[], const int array_index)
{
        FCurve *fcu;
        
        /* sanity checks */
        if ( ELEM(NULL, list, rna_path) || (array_index < 0) )
                return NULL;
        
        /* check paths of curves, then array indices... */
        for (fcu= list->first; fcu; fcu= fcu->next) {
                /* simple string-compare (this assumes that they have the same root...) */
                if (fcu->rna_path && !strcmp(fcu->rna_path, rna_path)) {
                        /* now check indices */
                        if (fcu->array_index == array_index)
                                return fcu;
                }
        }
        
        /* return */
        return NULL;
}

/* quick way to loop over all fcurves of a given 'path' */
FCurve *iter_step_fcurve (FCurve *fcu_iter, const char rna_path[])
{
        FCurve *fcu;
        
        /* sanity checks */
        if (ELEM(NULL, fcu_iter, rna_path))
                return NULL;

        /* check paths of curves, then array indices... */
        for (fcu= fcu_iter; fcu; fcu= fcu->next) {
                /* simple string-compare (this assumes that they have the same root...) */
                if (fcu->rna_path && !strcmp(fcu->rna_path, rna_path)) {
                        return fcu;
                }
        }

        /* return */
        return NULL;
}

/* Get list of LinkData's containing pointers to the F-Curves which control the types of data indicated 
 * Lists...
 *      - dst: list of LinkData's matching the criteria returned. 
 *        List must be freed after use, and is assumed to be empty when passed.
 *      - src: list of F-Curves to search through
 * Filters...
 *      - dataPrefix: i.e. 'pose.bones[' or 'nodes['
 *      - dataName: name of entity within "" immediately following the prefix
 */
int list_find_data_fcurves (ListBase *dst, ListBase *src, const char *dataPrefix, const char *dataName)
{
        FCurve *fcu;
        int matches = 0;
        
        /* sanity checks */
        if (ELEM4(NULL, dst, src, dataPrefix, dataName))
                return 0;
        else if ((dataPrefix[0] == 0) || (dataName[0] == 0))
                return 0;
        
        /* search each F-Curve one by one */
        for (fcu= src->first; fcu; fcu= fcu->next) {
                /* check if quoted string matches the path */
                if ((fcu->rna_path) && strstr(fcu->rna_path, dataPrefix)) {
                        char *quotedName= BLI_getQuotedStr(fcu->rna_path, dataPrefix);
                        
                        if (quotedName) {
                                /* check if the quoted name matches the required name */
                                if (strcmp(quotedName, dataName) == 0) {
                                        LinkData *ld= MEM_callocN(sizeof(LinkData), "list_find_data_fcurves");
                                        
                                        ld->data= fcu;
                                        BLI_addtail(dst, ld);
                                        
                                        matches++;
                                }
                                
                                /* always free the quoted string, since it needs freeing */
                                MEM_freeN(quotedName);
                        }
                }
        }
        
        /* return the number of matches */
        return matches;
}

FCurve *rna_get_fcurve (PointerRNA *ptr, PropertyRNA *prop, int rnaindex, bAction **action, int *driven)
{
        FCurve *fcu= NULL;
        
        *driven= 0;
        
        /* there must be some RNA-pointer + property combon */
        if (prop && ptr->id.data && RNA_property_animateable(ptr, prop)) {
                AnimData *adt= BKE_animdata_from_id(ptr->id.data);
                char *path;
                
                if (adt) {
                        if ((adt->action && adt->action->curves.first) || (adt->drivers.first)) {
                                /* XXX this function call can become a performance bottleneck */
                                path= RNA_path_from_ID_to_property(ptr, prop);
                                
                                if (path) {
                                        /* animation takes priority over drivers */
                                        if (adt->action && adt->action->curves.first)
                                                fcu= list_find_fcurve(&adt->action->curves, path, rnaindex);
                                        
                                        /* if not animated, check if driven */
                                        if (!fcu && (adt->drivers.first)) {
                                                fcu= list_find_fcurve(&adt->drivers, path, rnaindex);
                                                
                                                if (fcu)
                                                        *driven= 1;
                                        }
                                        
                                        if (fcu && action)
                                                *action= adt->action;
                                        
                                        MEM_freeN(path);
                                }
                        }
                }
        }
        
        return fcu;
}

/* ----------------- Finding Keyframes/Extents -------------------------- */

/* threshold for binary-searching keyframes - threshold here should be good enough for now, but should become userpref */
#define BEZT_BINARYSEARCH_THRESH        0.01f /* was 0.00001, but giving errors */

/* Binary search algorithm for finding where to insert BezTriple. (for use by insert_bezt_fcurve)
 * Returns the index to insert at (data already at that index will be offset if replace is 0)
 */
int binarysearch_bezt_index (BezTriple array[], float frame, int arraylen, short *replace)
{
        int start=0, end=arraylen;
        int loopbreaker= 0, maxloop= arraylen * 2;
        
        /* initialise replace-flag first */
        *replace= 0;
        
        /* sneaky optimisations (don't go through searching process if...):
         *      - keyframe to be added is to be added out of current bounds
         *      - keyframe to be added would replace one of the existing ones on bounds
         */
        if ((arraylen <= 0) || (array == NULL)) {
                printf("Warning: binarysearch_bezt_index() encountered invalid array \n");
                return 0;
        }
        else {
                /* check whether to add before/after/on */
                float framenum;
                
                /* 'First' Keyframe (when only one keyframe, this case is used) */
                framenum= array[0].vec[1][0];
                if (IS_EQT(frame, framenum, BEZT_BINARYSEARCH_THRESH)) {
                        *replace = 1;
                        return 0;
                }
                else if (frame < framenum)
                        return 0;
                        
                /* 'Last' Keyframe */
                framenum= array[(arraylen-1)].vec[1][0];
                if (IS_EQT(frame, framenum, BEZT_BINARYSEARCH_THRESH)) {
                        *replace= 1;
                        return (arraylen - 1);
                }
                else if (frame > framenum)
                        return arraylen;
        }
        
        
        /* most of the time, this loop is just to find where to put it
         * 'loopbreaker' is just here to prevent infinite loops 
         */
        for (loopbreaker=0; (start <= end) && (loopbreaker < maxloop); loopbreaker++) {
                /* compute and get midpoint */
                int mid = start + ((end - start) / 2);  /* we calculate the midpoint this way to avoid int overflows... */
                float midfra= array[mid].vec[1][0];
                
                /* check if exactly equal to midpoint */
                if (IS_EQT(frame, midfra, BEZT_BINARYSEARCH_THRESH)) {
                        *replace = 1;
                        return mid;
                }
                
                /* repeat in upper/lower half */
                if (frame > midfra)
                        start= mid + 1;
                else if (frame < midfra)
                        end= mid - 1;
        }
        
        /* print error if loop-limit exceeded */
        if (loopbreaker == (maxloop-1)) {
                printf("Error: binarysearch_bezt_index() was taking too long \n");
                
                // include debug info 
                printf("\tround = %d: start = %d, end = %d, arraylen = %d \n", loopbreaker, start, end, arraylen);
        }
        
        /* not found, so return where to place it */
        return start;
}

/* ...................................... */

/* helper for calc_fcurve_* functions -> find first and last BezTriple to be used */
static void get_fcurve_end_keyframes (FCurve *fcu, BezTriple **first, BezTriple **last, const short selOnly)
{
        /* init outputs */
        *first = NULL;
        *last = NULL;
        
        /* sanity checks */
        if (fcu->bezt == NULL)
                return;
        
        /* only include selected items? */
        if (selOnly) {
                BezTriple *bezt;
                unsigned int i;
                
                /* find first selected */
                bezt = fcu->bezt;
                for (i=0; i < fcu->totvert; bezt++, i++) {
                        if (BEZSELECTED(bezt)) {
                                *first= bezt;
                                break;
                        }
                }
                
                /* find last selected */
                bezt = ARRAY_LAST_ITEM(fcu->bezt, BezTriple, sizeof(BezTriple), fcu->totvert);
                for (i=0; i < fcu->totvert; bezt--, i++) {
                        if (BEZSELECTED(bezt)) {
                                *last= bezt;
                                break;
                        }
                }
        }
        else {
                /* just full array */
                *first = fcu->bezt;
                *last = ARRAY_LAST_ITEM(fcu->bezt, BezTriple, sizeof(BezTriple), fcu->totvert);
        }
}


/* Calculate the extents of F-Curve's data */
void calc_fcurve_bounds (FCurve *fcu, float *xmin, float *xmax, float *ymin, float *ymax, const short selOnly)
{
        float xminv=999999999.0f, xmaxv=-999999999.0f;
        float yminv=999999999.0f, ymaxv=-999999999.0f;
        short foundvert=0;
        unsigned int i;
        
        if (fcu->totvert) {
                if (fcu->bezt) {
                        BezTriple *bezt_first= NULL, *bezt_last= NULL;
                        
                        if (xmin || xmax) {
                                /* get endpoint keyframes */
                                get_fcurve_end_keyframes(fcu, &bezt_first, &bezt_last, selOnly);
                                
                                if (bezt_first) {
                                        BLI_assert(bezt_last != NULL);
                                        
                                        xminv= MIN2(xminv, bezt_first->vec[1][0]);
                                        xmaxv= MAX2(xmaxv, bezt_last->vec[1][0]);
                                }
                        }
                        
                        /* only loop over keyframes to find extents for values if needed */
                        if (ymin || ymax) {     
                                BezTriple *bezt;
                                
                                for (bezt=fcu->bezt, i=0; i < fcu->totvert; bezt++, i++) {
                                        if ((selOnly == 0) || BEZSELECTED(bezt)) {
                                                if (bezt->vec[1][1] < yminv)
                                                        yminv= bezt->vec[1][1];
                                                if (bezt->vec[1][1] > ymaxv)
                                                        ymaxv= bezt->vec[1][1];
                                        }
                                }
                        }
                }
                else if (fcu->fpt) {
                        /* frame range can be directly calculated from end verts */
                        if (xmin || xmax) {
                                xminv= MIN2(xminv, fcu->fpt[0].vec[0]);
                                xmaxv= MAX2(xmaxv, fcu->fpt[fcu->totvert-1].vec[0]);
                        }
                        
                        /* only loop over keyframes to find extents for values if needed */
                        if (ymin || ymax) {
                                FPoint *fpt;
                                
                                for (fpt=fcu->fpt, i=0; i < fcu->totvert; fpt++, i++) {
                                        if (fpt->vec[1] < yminv)
                                                yminv= fpt->vec[1];
                                        if (fpt->vec[1] > ymaxv)
                                                ymaxv= fpt->vec[1];
                                }
                        }
                }
                
                foundvert=1;
        }
        
        if (foundvert) {
                if (xmin) *xmin= xminv;
                if (xmax) *xmax= xmaxv;
                
                if (ymin) *ymin= yminv;
                if (ymax) *ymax= ymaxv;
        }
        else {
                if (G.f & G_DEBUG)
                        printf("F-Curve calc bounds didn't find anything, so assuming minimum bounds of 1.0\n");
                        
                if (xmin) *xmin= 0.0f;
                if (xmax) *xmax= 1.0f;
                
                if (ymin) *ymin= 0.0f;
                if (ymax) *ymax= 1.0f;
        }
}

/* Calculate the extents of F-Curve's keyframes */
void calc_fcurve_range (FCurve *fcu, float *start, float *end, const short selOnly)
{
        float min=999999999.0f, max=-999999999.0f;
        short foundvert=0;

        if (fcu->totvert) {
                if (fcu->bezt) {
                        BezTriple *bezt_first= NULL, *bezt_last= NULL;
                        
                        /* get endpoint keyframes */
                        get_fcurve_end_keyframes(fcu, &bezt_first, &bezt_last, selOnly);
                        
                        if (bezt_first) {
                                BLI_assert(bezt_last != NULL);
                                
                                min= MIN2(min, bezt_first->vec[1][0]);
                                max= MAX2(max, bezt_last->vec[1][0]);
                        }
                }
                else if (fcu->fpt) {
                        min= MIN2(min, fcu->fpt[0].vec[0]);
                        max= MAX2(max, fcu->fpt[fcu->totvert-1].vec[0]);
                }
                
                foundvert=1;
        }
        
        /* minimum length is 1 frame */
        if (foundvert) {
                if (min == max) max += 1.0f;
                *start= min;
                *end= max;
        }
        else {
                *start= 0.0f;
                *end= 1.0f;
        }
}

/* ----------------- Status Checks -------------------------- */

/* Are keyframes on F-Curve of any use? 
 * Usability of keyframes refers to whether they should be displayed,
 * and also whether they will have any influence on the final result.
 */
short fcurve_are_keyframes_usable (FCurve *fcu)
{
        /* F-Curve must exist */
        if (fcu == NULL)
                return 0;
                
        /* F-Curve must not have samples - samples are mutually exclusive of keyframes */
        if (fcu->fpt)
                return 0;
        
        /* if it has modifiers, none of these should "drastically" alter the curve */
        if (fcu->modifiers.first) {
                FModifier *fcm;
                
                /* check modifiers from last to first, as last will be more influential */
                // TODO: optionally, only check modifier if it is the active one...
                for (fcm = fcu->modifiers.last; fcm; fcm = fcm->prev) {
                        /* ignore if muted/disabled */
                        if (fcm->flag & (FMODIFIER_FLAG_DISABLED|FMODIFIER_FLAG_MUTED))
                                continue;
                                
                        /* type checks */
                        switch (fcm->type) {
                                /* clearly harmless - do nothing */
                                case FMODIFIER_TYPE_CYCLES:
                                case FMODIFIER_TYPE_STEPPED:
                                case FMODIFIER_TYPE_NOISE:
                                        break;
                                        
                                /* sometimes harmful - depending on whether they're "additive" or not */
                                case FMODIFIER_TYPE_GENERATOR:
                                {
                                        FMod_Generator *data = (FMod_Generator *)fcm->data;
                                        
                                        if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0)
                                                return 0;
                                }
                                        break;
                                case FMODIFIER_TYPE_FN_GENERATOR:
                                {
                                        FMod_FunctionGenerator *data = (FMod_FunctionGenerator *)fcm->data;
                                        
                                        if ((data->flag & FCM_GENERATOR_ADDITIVE) == 0)
                                                return 0;
                                }
                                        break;
                                        
                                /* always harmful - cannot allow */
                                default:
                                        return 0;
                        }
                }
        }
        
        /* keyframes are usable */
        return 1;
}

/* Can keyframes be added to F-Curve? 
 * Keyframes can only be added if they are already visible
 */
short fcurve_is_keyframable (FCurve *fcu)
{
        /* F-Curve's keyframes must be "usable" (i.e. visible + have an effect on final result) */
        if (fcurve_are_keyframes_usable(fcu) == 0)
                return 0;
                
        /* F-Curve must currently be editable too */
        if ( (fcu->flag & FCURVE_PROTECTED) || ((fcu->grp) && (fcu->grp->flag & AGRP_PROTECTED)) )
                return 0;
        
        /* F-Curve is keyframable */
        return 1;
}

/* ***************************** Keyframe Column Tools ********************************* */

/* add a BezTriple to a column */
void bezt_add_to_cfra_elem (ListBase *lb, BezTriple *bezt)
{
        CfraElem *ce, *cen;
        
        for (ce= lb->first; ce; ce= ce->next) {
                /* double key? */
                if (ce->cfra == bezt->vec[1][0]) {
                        if (bezt->f2 & SELECT) ce->sel= bezt->f2;
                        return;
                }
                /* should key be inserted before this column? */
                else if (ce->cfra > bezt->vec[1][0]) break;
        }
        
        /* create a new column */
        cen= MEM_callocN(sizeof(CfraElem), "add_to_cfra_elem"); 
        if (ce) BLI_insertlinkbefore(lb, ce, cen);
        else BLI_addtail(lb, cen);

        cen->cfra= bezt->vec[1][0];
        cen->sel= bezt->f2;
}

/* ***************************** Samples Utilities ******************************* */
/* Some utilities for working with FPoints (i.e. 'sampled' animation curve data, such as
 * data imported from BVH/Mocap files), which are specialised for use with high density datasets,
 * which BezTriples/Keyframe data are ill equipped to do.
 */
 
 
/* Basic sampling callback which acts as a wrapper for evaluate_fcurve() 
 *      'data' arg here is unneeded here...
 */
float fcurve_samplingcb_evalcurve (FCurve *fcu, void *UNUSED(data), float evaltime)
{
        /* assume any interference from drivers on the curve is intended... */
        return evaluate_fcurve(fcu, evaltime);
} 

 
/* Main API function for creating a set of sampled curve data, given some callback function 
 * used to retrieve the values to store.
 */
void fcurve_store_samples (FCurve *fcu, void *data, int start, int end, FcuSampleFunc sample_cb)
{
        FPoint *fpt, *new_fpt;
        int cfra;
        
        /* sanity checks */
        // TODO: make these tests report errors using reports not printf's
        if ELEM(NULL, fcu, sample_cb) {
                printf("Error: No F-Curve with F-Curve Modifiers to Bake\n");
                return;
        }
        if (start >= end) {
                printf("Error: Frame range for Sampled F-Curve creation is inappropriate \n");
                return;
        }
        
        /* set up sample data */
        fpt= new_fpt= MEM_callocN(sizeof(FPoint)*(end-start+1), "FPoint Samples");
        
        /* use the sampling callback at 1-frame intervals from start to end frames */
        for (cfra= start; cfra <= end; cfra++, fpt++) {
                fpt->vec[0]= (float)cfra;
                fpt->vec[1]= sample_cb(fcu, data, (float)cfra);
        }
        
        /* free any existing sample/keyframe data on curve  */
        if (fcu->bezt) MEM_freeN(fcu->bezt);
        if (fcu->fpt) MEM_freeN(fcu->fpt);
        
        /* store the samples */
        fcu->bezt= NULL;
        fcu->fpt= new_fpt;
        fcu->totvert= end - start + 1;
}

/* ***************************** F-Curve Sanity ********************************* */
/* The functions here are used in various parts of Blender, usually after some editing
 * of keyframe data has occurred. They ensure that keyframe data is properly ordered and
 * that the handles are correctly 
 */

/* This function recalculates the handles of an F-Curve 
 * If the BezTriples have been rearranged, sort them first before using this.
 */
void calchandles_fcurve (FCurve *fcu)
{
        BezTriple *bezt, *prev, *next;
        int a= fcu->totvert;

        /* Error checking:
         *      - need at least two points
         *      - need bezier keys
         *      - only bezier-interpolation has handles (for now)
         */
        if (ELEM(NULL, fcu, fcu->bezt) || (a < 2) /*|| ELEM(fcu->ipo, BEZT_IPO_CONST, BEZT_IPO_LIN)*/) 
                return;
        
        /* get initial pointers */
        bezt= fcu->bezt;
        prev= NULL;
        next= (bezt + 1);
        
        /* loop over all beztriples, adjusting handles */
        while (a--) {
                /* clamp timing of handles to be on either side of beztriple */
                if (bezt->vec[0][0] > bezt->vec[1][0]) bezt->vec[0][0]= bezt->vec[1][0];
                if (bezt->vec[2][0] < bezt->vec[1][0]) bezt->vec[2][0]= bezt->vec[1][0];
                
                /* calculate auto-handles */
                if (fcu->flag & FCURVE_AUTO_HANDLES) 
                        calchandleNurb(bezt, prev, next, 2);    /* 2==special autohandle && keep extrema horizontal */
                else
                        calchandleNurb(bezt, prev, next, 1);    /* 1==special autohandle */
                
                /* for automatic ease in and out */
                if ((bezt->h1==HD_AUTO) && (bezt->h2==HD_AUTO)) {
                        /* only do this on first or last beztriple */
                        if ((a == 0) || (a == fcu->totvert-1)) {
                                /* set both handles to have same horizontal value as keyframe */
                                if (fcu->extend == FCURVE_EXTRAPOLATE_CONSTANT) {
                                        bezt->vec[0][1]= bezt->vec[2][1]= bezt->vec[1][1];
                                }
                        }
                }
                
                /* advance pointers for next iteration */
                prev= bezt;
                if (a == 1) next= NULL;
                else next++;
                bezt++;
        }
}

/* Use when F-Curve with handles has changed
 * It treats all BezTriples with the following rules:
 *  - PHASE 1: do types have to be altered?
 *              -> Auto handles: become aligned when selection status is NOT(000 || 111)
 *              -> Vector handles: become 'nothing' when (one half selected AND other not)
 *  - PHASE 2: recalculate handles
*/
void testhandles_fcurve (FCurve *fcu)
{
        BezTriple *bezt;
        unsigned int a;

        /* only beztriples have handles (bpoints don't though) */
        if ELEM(NULL, fcu, fcu->bezt)
                return;
        
        /* loop over beztriples */
        for (a=0, bezt=fcu->bezt; a < fcu->totvert; a++, bezt++) {
                short flag= 0;
                
                /* flag is initialised as selection status
                 * of beztriple control-points (labelled 0,1,2)
                 */
                if (bezt->f1 & SELECT) flag |= (1<<0); // == 1
                if (bezt->f2 & SELECT) flag |= (1<<1); // == 2
                if (bezt->f3 & SELECT) flag |= (1<<2); // == 4
                
                /* one or two handles selected only */
                if (ELEM(flag, 0, 7)==0) {
                        /* auto handles become aligned */
                        if (bezt->h1==HD_AUTO)
                                bezt->h1= HD_ALIGN;
                        if (bezt->h2==HD_AUTO)
                                bezt->h2= HD_ALIGN;
                        
                        /* vector handles become 'free' when only one half selected */
                        if (bezt->h1==HD_VECT) {
                                /* only left half (1 or 2 or 1+2) */
                                if (flag < 4) 
                                        bezt->h1= 0;
                        }
                        if (bezt->h2==HD_VECT) {
                                /* only right half (4 or 2+4) */
                                if (flag > 3) 
                                        bezt->h2= 0;
                        }
                }
        }

        /* recalculate handles */
        calchandles_fcurve(fcu);
}

/* This function sorts BezTriples so that they are arranged in chronological order,
 * as tools working on F-Curves expect that the BezTriples are in order.
 */
void sort_time_fcurve (FCurve *fcu)
{
        short ok= 1;
        
        /* keep adjusting order of beztriples until nothing moves (bubble-sort) */
        while (ok) {
                ok= 0;
                
                /* currently, will only be needed when there are beztriples */
                if (fcu->bezt) {
                        BezTriple *bezt;
                        unsigned int a;
                        
                        /* loop over ALL points to adjust position in array and recalculate handles */
                        for (a=0, bezt=fcu->bezt; a < fcu->totvert; a++, bezt++) {
                                /* check if thee's a next beztriple which we could try to swap with current */
                                if (a < (fcu->totvert-1)) {
                                        /* swap if one is after the other (and indicate that order has changed) */
                                        if (bezt->vec[1][0] > (bezt+1)->vec[1][0]) {
                                                SWAP(BezTriple, *bezt, *(bezt+1));
                                                ok= 1;
                                        }
                                        
                                        /* if either one of both of the points exceeds crosses over the keyframe time... */
                                        if ( (bezt->vec[0][0] > bezt->vec[1][0]) && (bezt->vec[2][0] < bezt->vec[1][0]) ) {
                                                /* swap handles if they have switched sides for some reason */
                                                SWAP(float, bezt->vec[0][0], bezt->vec[2][0]);
                                                SWAP(float, bezt->vec[0][1], bezt->vec[2][1]);
                                        }
                                        else {
                                                /* clamp handles */
                                                if (bezt->vec[0][0] > bezt->vec[1][0]) 
                                                        bezt->vec[0][0]= bezt->vec[1][0];
                                                if (bezt->vec[2][0] < bezt->vec[1][0]) 
                                                        bezt->vec[2][0]= bezt->vec[1][0];
                                        }
                                }
                        }
                }
        }
}

/* This function tests if any BezTriples are out of order, thus requiring a sort */
short test_time_fcurve (FCurve *fcu)
{
        unsigned int a;
        
        /* sanity checks */
        if (fcu == NULL)
                return 0;
        
        /* currently, only need to test beztriples */
        if (fcu->bezt) {
                BezTriple *bezt;
                
                /* loop through all BezTriples, stopping when one exceeds the one after it */
                for (a=0, bezt= fcu->bezt; a < (fcu->totvert - 1); a++, bezt++) {
                        if (bezt->vec[1][0] > (bezt+1)->vec[1][0])
                                return 1;
                }
        }
        else if (fcu->fpt) {
                FPoint *fpt;
                
                /* loop through all FPoints, stopping when one exceeds the one after it */
                for (a=0, fpt= fcu->fpt; a < (fcu->totvert - 1); a++, fpt++) {
                        if (fpt->vec[0] > (fpt+1)->vec[0])
                                return 1;
                }
        }
        
        /* none need any swapping */
        return 0;
}

/* ***************************** Drivers ********************************* */

/* Driver Variables --------------------------- */

/* TypeInfo for Driver Variables (dvti) */
typedef struct DriverVarTypeInfo {
        /* evaluation callback */
        float (*get_value)(ChannelDriver *driver, DriverVar *dvar);
        
        /* allocation of target slots */
        int num_targets;                                                /* number of target slots required */
        const char *target_names[MAX_DRIVER_TARGETS];   /* UI names that should be given to the slots */
        int target_flags[MAX_DRIVER_TARGETS];   /* flags defining the requirements for each slot */
} DriverVarTypeInfo;

/* Macro to begin definitions */
#define BEGIN_DVAR_TYPEDEF(type) \
        {
        
/* Macro to end definitions */
#define END_DVAR_TYPEDEF \
        }

/* ......... */

static ID *dtar_id_ensure_proxy_from(ID *id)
{
        if (id && GS(id->name)==ID_OB && ((Object *)id)->proxy_from)
                return (ID *)(((Object *)id)->proxy_from);
        return id;
}

/* Helper function to obtain a value using RNA from the specified source (for evaluating drivers) */
static float dtar_get_prop_val (ChannelDriver *driver, DriverTarget *dtar)
{
        PointerRNA id_ptr, ptr;
        PropertyRNA *prop;
        ID *id;
        int index;
        float value= 0.0f;
        
        /* sanity check */
        if ELEM(NULL, driver, dtar)
                return 0.0f;
        
        id= dtar_id_ensure_proxy_from(dtar->id);
        
        /* error check for missing pointer... */
        // TODO: tag the specific target too as having issues
        if (id == NULL) {
                printf("Error: driver has an invalid target to use \n");
                if (G.f & G_DEBUG) printf("\tpath = %s\n", dtar->rna_path);
                driver->flag |= DRIVER_FLAG_INVALID;
                return 0.0f;
        }
        
        /* get RNA-pointer for the ID-block given in target */
        RNA_id_pointer_create(id, &id_ptr);
        
        /* get property to read from, and get value as appropriate */
        if (RNA_path_resolve_full(&id_ptr, dtar->rna_path, &ptr, &prop, &index)) {
                if(RNA_property_array_check(&ptr, prop)) {
                        /* array */
                        if (index < RNA_property_array_length(&ptr, prop)) {    
                                switch (RNA_property_type(prop)) {
                                case PROP_BOOLEAN:
                                        value= (float)RNA_property_boolean_get_index(&ptr, prop, index);
                                        break;
                                case PROP_INT:
                                        value= (float)RNA_property_int_get_index(&ptr, prop, index);
                                        break;
                                case PROP_FLOAT:
                                        value= RNA_property_float_get_index(&ptr, prop, index);
                                        break;
                                default:
                                        break;
                                }
                        }
                }
                else {
                        /* not an array */
                        switch (RNA_property_type(prop)) {
                        case PROP_BOOLEAN:
                                value= (float)RNA_property_boolean_get(&ptr, prop);
                                break;
                        case PROP_INT:
                                value= (float)RNA_property_int_get(&ptr, prop);
                                break;
                        case PROP_FLOAT:
                                value= RNA_property_float_get(&ptr, prop);
                                break;
                        case PROP_ENUM:
                                value= (float)RNA_property_enum_get(&ptr, prop);
                                break;
                        default:
                                break;
                        }
                }

        }
        else {
                if (G.f & G_DEBUG)
                        printf("Driver Evaluation Error: cannot resolve target for %s -> %s \n", id->name, dtar->rna_path);
                
                driver->flag |= DRIVER_FLAG_INVALID;
                return 0.0f;
        }
        
        return value;
}

/* Helper function to obtain a pointer to a Pose Channel (for evaluating drivers) */
static bPoseChannel *dtar_get_pchan_ptr (ChannelDriver *driver, DriverTarget *dtar)
{
        ID *id;
        /* sanity check */
        if ELEM(NULL, driver, dtar)
                return NULL;

        id= dtar_id_ensure_proxy_from(dtar->id);

        /* check if the ID here is a valid object */
        if (id && GS(id->name)) {
                Object *ob= (Object *)id;
                
                /* get pose, and subsequently, posechannel */
                return get_pose_channel(ob->pose, dtar->pchan_name);
        }
        else {
                /* cannot find a posechannel this way */
                return NULL;
        }
}

/* ......... */

/* evaluate 'single prop' driver variable */
static float dvar_eval_singleProp (ChannelDriver *driver, DriverVar *dvar)
{
        /* just evaluate the first target slot */
        return dtar_get_prop_val(driver, &dvar->targets[0]);
}

/* evaluate 'rotation difference' driver variable */
static float dvar_eval_rotDiff (ChannelDriver *driver, DriverVar *dvar)
{
        bPoseChannel *pchan, *pchan2;
        float q1[4], q2[4], quat[4], angle;
        
        /* get pose channels, and check if we've got two */
        pchan= dtar_get_pchan_ptr(driver, &dvar->targets[0]);
        pchan2= dtar_get_pchan_ptr(driver, &dvar->targets[1]);
        
        if (ELEM(NULL, pchan, pchan2)) {
                /* disable this driver, since it doesn't work correctly... */
                driver->flag |= DRIVER_FLAG_INVALID;
                
                /* check what the error was */
                if ((pchan == NULL) && (pchan2 == NULL))
                        printf("Driver Evaluation Error: Rotational difference failed - first 2 targets invalid \n");
                else if (pchan == NULL)
                        printf("Driver Evaluation Error: Rotational difference failed - first target not valid PoseChannel \n");
                else if (pchan2 == NULL)
                        printf("Driver Evaluation Error: Rotational difference failed - second target not valid PoseChannel \n");
                        
                /* stop here... */
                return 0.0f;
        }                       
        
        /* use the final posed locations */
        mat4_to_quat(q1, pchan->pose_mat);
        mat4_to_quat(q2, pchan2->pose_mat);
        
        invert_qt(q1);
        mul_qt_qtqt(quat, q1, q2);
        angle = 2.0f * (saacos(quat[0]));
        angle= ABS(angle);
        
        return (angle > (float)M_PI) ? (float)((2.0f * (float)M_PI) - angle) : (float)(angle);
}

/* evaluate 'location difference' driver variable */
// TODO: this needs to take into account space conversions...
static float dvar_eval_locDiff (ChannelDriver *driver, DriverVar *dvar)
{
        float loc1[3] = {0.0f,0.0f,0.0f};
        float loc2[3] = {0.0f,0.0f,0.0f};
        
        /* get two location values */
        // NOTE: for now, these are all just worldspace
        DRIVER_TARGETS_USED_LOOPER(dvar)
        {
                /* get pointer to loc values to store in */
                Object *ob= (Object *)dtar_id_ensure_proxy_from(dtar->id);
                bPoseChannel *pchan;
                float tmp_loc[3];
                
                /* check if this target has valid data */
                if ((ob == NULL) || (GS(ob->id.name) != ID_OB)) {
                        /* invalid target, so will not have enough targets */
                        driver->flag |= DRIVER_FLAG_INVALID;
                        return 0.0f;
                }
                
                /* try to get posechannel */
                pchan= get_pose_channel(ob->pose, dtar->pchan_name);
                
                /* check if object or bone */
                if (pchan) {
                        /* bone */
                        if ((dtar->flag & DTAR_FLAG_LOCALSPACE) == 0) {
                                /* convert to worldspace */
                                VECCOPY(tmp_loc, pchan->pose_head);
                                mul_m4_v3(ob->obmat, tmp_loc);
                        }
                        else {
                                /* local (use transform values directly) */
                                VECCOPY(tmp_loc, pchan->loc);
                        }
                }
                else {
                        /* object */
                        if ((dtar->flag & DTAR_FLAG_LOCALSPACE) == 0) {
                                /* worldspace */
                                VECCOPY(tmp_loc, ob->obmat[3]); 
                        }
                        else {
                                /* local (use transform values directly) */
                                VECCOPY(tmp_loc, ob->loc);
                        }
                }
                
                /* copy the location to the right place */
                if (tarIndex) {
                        VECCOPY(loc2, tmp_loc);
                }
                else {
                        VECCOPY(loc1, tmp_loc);
                }
        }
        DRIVER_TARGETS_LOOPER_END
        
        
        /* if we're still here, there should now be two targets to use,
         * so just take the length of the vector between these points 
         */
        return len_v3v3(loc1, loc2);
}

/* evaluate 'transform channel' driver variable */
static float dvar_eval_transChan (ChannelDriver *driver, DriverVar *dvar)
{
        DriverTarget *dtar= &dvar->targets[0];
        Object *ob= (Object *)dtar_id_ensure_proxy_from(dtar->id);
        bPoseChannel *pchan;
        float mat[4][4];
        float eul[3] = {0.0f,0.0f,0.0f};
        short useEulers=0, rotOrder=ROT_MODE_EUL;
        
        /* check if this target has valid data */
        if ((ob == NULL) || (GS(ob->id.name) != ID_OB)) {
                /* invalid target, so will not have enough targets */
                driver->flag |= DRIVER_FLAG_INVALID;
                return 0.0f;
        }
        
        /* try to get posechannel */
        pchan= get_pose_channel(ob->pose, dtar->pchan_name);
        
        /* check if object or bone, and get transform matrix accordingly */
        if (pchan) {
                /* bone */
                if (pchan->rotmode > 0) {
                        VECCOPY(eul, pchan->eul);
                        rotOrder= pchan->rotmode;
                        useEulers = 1;
                }
                
                if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
                        /* specially calculate local matrix, since chan_mat is not valid 
                         * since it stores delta transform of pose_mat so that deforms work
                         */
                        pchan_to_mat4(pchan, mat);
                }
                else
                        mul_m4_m4m4(mat, pchan->pose_mat, ob->obmat);
        }
        else {
                /* object */
                if (ob->rotmode > 0) {
                        VECCOPY(eul, ob->rot);
                        rotOrder= ob->rotmode;
                        useEulers = 1;
                }
                
                if (dtar->flag & DTAR_FLAG_LOCALSPACE)
                        object_to_mat4(ob, mat);
                else
                        copy_m4_m4(mat, ob->obmat);
        }
        
        /* check which transform */
        if (dtar->transChan >= MAX_DTAR_TRANSCHAN_TYPES) {
                /* not valid channel */
                return 0.0f;
        }
        else if (dtar->transChan >= DTAR_TRANSCHAN_SCALEX) {
                /* extract scale, and choose the right axis */
                float scale[3];
                
                mat4_to_size(scale, mat);
                return scale[dtar->transChan - DTAR_TRANSCHAN_SCALEX];
        }
        else if (dtar->transChan >= DTAR_TRANSCHAN_ROTX) {
                /* extract euler rotation (if needed), and choose the right axis */
                if ((dtar->flag & DTAR_FLAG_LOCALSPACE)==0 || (useEulers == 0))
                        mat4_to_eulO(eul, rotOrder, mat);
                
                return eul[dtar->transChan - DTAR_TRANSCHAN_ROTX];
        }
        else {
                /* extract location and choose right axis */
                return mat[3][dtar->transChan];
        }
}

/* ......... */

/* Table of Driver Varaiable Type Info Data */
static DriverVarTypeInfo dvar_types[MAX_DVAR_TYPES] = {
        BEGIN_DVAR_TYPEDEF(DVAR_TYPE_SINGLE_PROP)
                dvar_eval_singleProp, /* eval callback */
                1, /* number of targets used */
                {"Property"}, /* UI names for targets */
                {0} /* flags */
        END_DVAR_TYPEDEF,
        
        BEGIN_DVAR_TYPEDEF(DVAR_TYPE_ROT_DIFF)
                dvar_eval_rotDiff, /* eval callback */
                2, /* number of targets used */
                {"Bone 1", "Bone 2"}, /* UI names for targets */
                {DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY, DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY} /* flags */
        END_DVAR_TYPEDEF,
        
        BEGIN_DVAR_TYPEDEF(DVAR_TYPE_LOC_DIFF)
                dvar_eval_locDiff, /* eval callback */
                2, /* number of targets used */
                {"Object/Bone 1", "Object/Bone 2"}, /* UI names for targets */
                {DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY, DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY} /* flags */
        END_DVAR_TYPEDEF,
        
        BEGIN_DVAR_TYPEDEF(DVAR_TYPE_TRANSFORM_CHAN)
                dvar_eval_transChan, /* eval callback */
                1, /* number of targets used */
                {"Object/Bone"}, /* UI names for targets */
                {DTAR_FLAG_STRUCT_REF|DTAR_FLAG_ID_OB_ONLY} /* flags */
        END_DVAR_TYPEDEF,
};

/* Get driver variable typeinfo */
static DriverVarTypeInfo *get_dvar_typeinfo (int type)
{
        /* check if valid type */
        if ((type >= 0) && (type < MAX_DVAR_TYPES))
                return &dvar_types[type];
        else
                return NULL;
}

/* Driver API --------------------------------- */

/* This frees the driver variable itself */
void driver_free_variable (ChannelDriver *driver, DriverVar *dvar)
{
        /* sanity checks */
        if (dvar == NULL)
                return;
                
        /* free target vars 
         *      - need to go over all of them, not just up to the ones that are used
         *        currently, since there may be some lingering RNA paths from 
         *        previous users needing freeing
         */
        DRIVER_TARGETS_LOOPER(dvar) 
        {
                /* free RNA path if applicable */
                if (dtar->rna_path)
                        MEM_freeN(dtar->rna_path);
        }
        DRIVER_TARGETS_LOOPER_END
        
        /* remove the variable from the driver */
        if (driver)
                BLI_freelinkN(&driver->variables, dvar);
        else
                MEM_freeN(dvar);

#ifdef WITH_PYTHON
        /* since driver variables are cached, the expression needs re-compiling too */
        if(driver->type==DRIVER_TYPE_PYTHON)
                driver->flag |= DRIVER_FLAG_RENAMEVAR;
#endif
}

/* Change the type of driver variable */
void driver_change_variable_type (DriverVar *dvar, int type)
{
        DriverVarTypeInfo *dvti= get_dvar_typeinfo(type);
        
        /* sanity check */
        if (ELEM(NULL, dvar, dvti))
                return;
                
        /* set the new settings */
        dvar->type= type;
        dvar->num_targets= dvti->num_targets;
        
        /* make changes to the targets based on the defines for these types 
         * NOTE: only need to make sure the ones we're using here are valid...
         */
        DRIVER_TARGETS_USED_LOOPER(dvar)
        {
                int flags = dvti->target_flags[tarIndex];
                
                /* store the flags */
                dtar->flag = flags;
                
                /* object ID types only, or idtype not yet initialised*/
                if ((flags & DTAR_FLAG_ID_OB_ONLY) || (dtar->idtype == 0))
                        dtar->idtype= ID_OB;
        }
        DRIVER_TARGETS_LOOPER_END
}

/* Add a new driver variable */
DriverVar *driver_add_new_variable (ChannelDriver *driver)
{
        DriverVar *dvar;
        
        /* sanity checks */
        if (driver == NULL)
                return NULL;
                
        /* make a new variable */
        dvar= MEM_callocN(sizeof(DriverVar), "DriverVar");
        BLI_addtail(&driver->variables, dvar);
        
        /* give the variable a 'unique' name */
        strcpy(dvar->name, "var");
        BLI_uniquename(&driver->variables, dvar, "var", '_', offsetof(DriverVar, name), sizeof(dvar->name));
        
        /* set the default type to 'single prop' */
        driver_change_variable_type(dvar, DVAR_TYPE_SINGLE_PROP);
        
#ifdef WITH_PYTHON
        /* since driver variables are cached, the expression needs re-compiling too */
        if (driver->type==DRIVER_TYPE_PYTHON)
                driver->flag |= DRIVER_FLAG_RENAMEVAR;
#endif

        /* return the target */
        return dvar;
}

/* This frees the driver itself */
void fcurve_free_driver(FCurve *fcu)
{
        ChannelDriver *driver;
        DriverVar *dvar, *dvarn;
        
        /* sanity checks */
        if ELEM(NULL, fcu, fcu->driver)
                return;
        driver= fcu->driver;
        
        /* free driver targets */
        for (dvar= driver->variables.first; dvar; dvar= dvarn) {
                dvarn= dvar->next;
                driver_free_variable(driver, dvar);
        }

#ifdef WITH_PYTHON
        /* free compiled driver expression */
        if (driver->expr_comp)
                BPY_DECREF(driver->expr_comp);
#endif

        /* free driver itself, then set F-Curve's point to this to NULL (as the curve may still be used) */
        MEM_freeN(driver);
        fcu->driver= NULL;
}

/* This makes a copy of the given driver */
ChannelDriver *fcurve_copy_driver (ChannelDriver *driver)
{
        ChannelDriver *ndriver;
        DriverVar *dvar;
        
        /* sanity checks */
        if (driver == NULL)
                return NULL;
                
        /* copy all data */
        ndriver= MEM_dupallocN(driver);
        ndriver->expr_comp= NULL;
        
        /* copy variables */
        ndriver->variables.first= ndriver->variables.last= NULL;
        BLI_duplicatelist(&ndriver->variables, &driver->variables);
        
        for (dvar= ndriver->variables.first; dvar; dvar= dvar->next) {  
                /* need to go over all targets so that we don't leave any dangling paths */
                DRIVER_TARGETS_LOOPER(dvar) 
                {       
                        /* make a copy of target's rna path if available */
                        if (dtar->rna_path)
                                dtar->rna_path = MEM_dupallocN(dtar->rna_path);
                }
                DRIVER_TARGETS_LOOPER_END
        }
        
        /* return the new driver */
        return ndriver;
}

/* Driver Evaluation -------------------------- */

/* Evaluate a Driver Variable to get a value that contributes to the final */
float driver_get_variable_value (ChannelDriver *driver, DriverVar *dvar)
{
        DriverVarTypeInfo *dvti;

        /* sanity check */
        if (ELEM(NULL, driver, dvar))
                return 0.0f;
        
        /* call the relevant callbacks to get the variable value 
         * using the variable type info, storing the obtained value
         * in dvar->curval so that drivers can be debugged
         */
        dvti= get_dvar_typeinfo(dvar->type);
        
        if (dvti && dvti->get_value)
                dvar->curval= dvti->get_value(driver, dvar);
        else
                dvar->curval= 0.0f;
        
        return dvar->curval;
}

/* Evaluate an Channel-Driver to get a 'time' value to use instead of "evaltime"
 *      - "evaltime" is the frame at which F-Curve is being evaluated
 *      - has to return a float value 
 */
static float evaluate_driver (ChannelDriver *driver, float UNUSED(evaltime))
{
        DriverVar *dvar;
        
        /* check if driver can be evaluated */
        if (driver->flag & DRIVER_FLAG_INVALID)
                return 0.0f;
        
        switch (driver->type) {
                case DRIVER_TYPE_AVERAGE: /* average values of driver targets */
                case DRIVER_TYPE_SUM: /* sum values of driver targets */
                {
                        /* check how many variables there are first (i.e. just one?) */
                        if (driver->variables.first == driver->variables.last) {
                                /* just one target, so just use that */
                                dvar= driver->variables.first;
                                driver->curval= driver_get_variable_value(driver, dvar);
                        }
                        else {
                                /* more than one target, so average the values of the targets */
                                float value = 0.0f;
                                int tot = 0;
                                
                                /* loop through targets, adding (hopefully we don't get any overflow!) */
                                for (dvar= driver->variables.first; dvar; dvar=dvar->next) {
                                        value += driver_get_variable_value(driver, dvar);
                                        tot++;
                                }
                                
                                /* perform operations on the total if appropriate */
                                if (driver->type == DRIVER_TYPE_AVERAGE)
                                        driver->curval= (value / (float)tot);
                                else
                                        driver->curval= value;
                        }
                }
                        break;
                        
                case DRIVER_TYPE_MIN: /* smallest value */
                case DRIVER_TYPE_MAX: /* largest value */
                {
                        float value = 0.0f;
                        
                        /* loop through the variables, getting the values and comparing them to existing ones */
                        for (dvar= driver->variables.first; dvar; dvar= dvar->next) {
                                /* get value */
                                float tmp_val= driver_get_variable_value(driver, dvar);
                                
                                /* store this value if appropriate */
                                if (dvar->prev) {
                                        /* check if greater/smaller than the baseline */
                                        if (driver->type == DRIVER_TYPE_MAX) {
                                                /* max? */
                                                if (tmp_val > value) 
                                                        value= tmp_val;
                                        }
                                        else {
                                                /* min? */
                                                if (tmp_val < value) 
                                                        value= tmp_val;
                                        }
                                }
                                else {
                                        /* first item - make this the baseline for comparisons */
                                        value= tmp_val;
                                }
                        }
                        
                        /* store value in driver */
                        driver->curval= value;
                }
                        break;
                        
                case DRIVER_TYPE_PYTHON: /* expression */
                {
#ifdef WITH_PYTHON
                        /* check for empty or invalid expression */
                        if ( (driver->expression[0] == '\0') ||
                                 (driver->flag & DRIVER_FLAG_INVALID) )
                        {
                                driver->curval= 0.0f;
                        }
                        else
                        {
                                /* this evaluates the expression using Python,and returns its result:
                                 *      - on errors it reports, then returns 0.0f
                                 */
                                driver->curval= BPY_driver_exec(driver);
                        }
#endif /* WITH_PYTHON*/
                }
                        break;
                
                default:
                {
                        /* special 'hack' - just use stored value 
                         *      This is currently used as the mechanism which allows animated settings to be able
                         *      to be changed via the UI.
                         */
                }
        }
        
        /* return value for driver */
        return driver->curval;
}

/* ***************************** Curve Calculations ********************************* */

/* The total length of the handles is not allowed to be more
 * than the horizontal distance between (v1-v4).
 * This is to prevent curve loops.
*/
void correct_bezpart (float *v1, float *v2, float *v3, float *v4)
{
        float h1[2], h2[2], len1, len2, len, fac;
        
        /* calculate handle deltas */
        h1[0]= v1[0] - v2[0];
        h1[1]= v1[1] - v2[1];
        
        h2[0]= v4[0] - v3[0];
        h2[1]= v4[1] - v3[1];
        
        /* calculate distances: 
         *      - len   = span of time between keyframes 
         *      - len1  = length of handle of start key
         *      - len2  = length of handle of end key
         */
        len= v4[0]- v1[0];
        len1= (float)fabs(h1[0]);
        len2= (float)fabs(h2[0]);
        
        /* if the handles have no length, no need to do any corrections */
        if ((len1+len2) == 0.0f) 
                return;
                
        /* the two handles cross over each other, so force them
         * apart using the proportion they overlap 
         */
        if ((len1+len2) > len) {
                fac= len / (len1+len2);
                
                v2[0]= (v1[0] - fac*h1[0]);
                v2[1]= (v1[1] - fac*h1[1]);
                
                v3[0]= (v4[0] - fac*h2[0]);
                v3[1]= (v4[1] - fac*h2[1]);
        }
}

/* find root ('zero') */
static int findzero (float x, float q0, float q1, float q2, float q3, float *o)
{
        double c0, c1, c2, c3, a, b, c, p, q, d, t, phi;
        int nr= 0;

        c0= q0 - x;
        c1= 3.0f * (q1 - q0);
        c2= 3.0f * (q0 - 2.0f*q1 + q2);
        c3= q3 - q0 + 3.0f * (q1 - q2);
        
        if (c3 != 0.0) {
                a= c2/c3;
                b= c1/c3;
                c= c0/c3;
                a= a/3;
                
                p= b/3 - a*a;
                q= (2*a*a*a - a*b + c) / 2;
                d= q*q + p*p*p;
                
                if (d > 0.0) {
                        t= sqrt(d);
                        o[0]= (float)(sqrt3d(-q+t) + sqrt3d(-q-t) - a);
                        
                        if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
                        else return 0;
                }
                else if (d == 0.0) {
                        t= sqrt3d(-q);
                        o[0]= (float)(2*t - a);
                        
                        if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
                        o[nr]= (float)(-t-a);
                        
                        if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr+1;
                        else return nr;
                }
                else {
                        phi= acos(-q / sqrt(-(p*p*p)));
                        t= sqrt(-p);
                        p= cos(phi/3);
                        q= sqrt(3 - 3*p*p);
                        o[0]= (float)(2*t*p - a);
                        
                        if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
                        o[nr]= (float)(-t * (p + q) - a);
                        
                        if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) nr++;
                        o[nr]= (float)(-t * (p - q) - a);
                        
                        if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr+1;
                        else return nr;
                }
        }
        else {
                a=c2;
                b=c1;
                c=c0;
                
                if (a != 0.0) {
                        // discriminant
                        p= b*b - 4*a*c;
                        
                        if (p > 0) {
                                p= sqrt(p);
                                o[0]= (float)((-b-p) / (2 * a));
                                
                                if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
                                o[nr]= (float)((-b+p)/(2*a));
                                
                                if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr+1;
                                else return nr;
                        }
                        else if (p == 0) {
                                o[0]= (float)(-b / (2 * a));
                                if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
                                else return 0;
                        }
                }
                else if (b != 0.0) {
                        o[0]= (float)(-c/b);
                        
                        if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
                        else return 0;
                }
                else if (c == 0.0) {
                        o[0]= 0.0;
                        return 1;
                }
                
                return 0;       
        }
}

static void berekeny (float f1, float f2, float f3, float f4, float *o, int b)
{
        float t, c0, c1, c2, c3;
        int a;

        c0= f1;
        c1= 3.0f * (f2 - f1);
        c2= 3.0f * (f1 - 2.0f*f2 + f3);
        c3= f4 - f1 + 3.0f * (f2 - f3);
        
        for (a=0; a < b; a++) {
                t= o[a];
                o[a]= c0 + t*c1 + t*t*c2 + t*t*t*c3;
        }
}

#if 0
static void berekenx (float *f, float *o, int b)
{
        float t, c0, c1, c2, c3;
        int a;

        c0= f[0];
        c1= 3.0f * (f[3] - f[0]);
        c2= 3.0f * (f[0] - 2.0f*f[3] + f[6]);
        c3= f[9] - f[0] + 3.0f * (f[3] - f[6]);
        
        for (a=0; a < b; a++) {
                t= o[a];
                o[a]= c0 + t*c1 + t*t*c2 + t*t*t*c3;
        }
}
#endif


/* -------------------------- */

/* Calculate F-Curve value for 'evaltime' using BezTriple keyframes */
static float fcurve_eval_keyframes (FCurve *fcu, BezTriple *bezts, float evaltime)
{
        BezTriple *bezt, *prevbezt, *lastbezt;
        float v1[2], v2[2], v3[2], v4[2], opl[32], dx, fac;
        unsigned int a;
        int b;
        float cvalue = 0.0f;
        
        /* get pointers */
        a= fcu->totvert-1;
        prevbezt= bezts;
        bezt= prevbezt+1;
        lastbezt= prevbezt + a;
        
        /* evaluation time at or past endpoints? */
        if (prevbezt->vec[1][0] >= evaltime) 
        {
                /* before or on first keyframe */
                if ( (fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (prevbezt->ipo != BEZT_IPO_CONST) &&
                        !(fcu->flag & FCURVE_DISCRETE_VALUES) ) 
                {
                        /* linear or bezier interpolation */
                        if (prevbezt->ipo==BEZT_IPO_LIN) 
                        {
                                /* Use the next center point instead of our own handle for
                                 * linear interpolated extrapolate 
                                 */
                                if (fcu->totvert == 1) 
                                        cvalue= prevbezt->vec[1][1];
                                else 
                                {
                                        bezt = prevbezt+1;
                                        dx= prevbezt->vec[1][0] - evaltime;
                                        fac= bezt->vec[1][0] - prevbezt->vec[1][0];
                                        
                                        /* prevent division by zero */
                                        if (fac) {
                                                fac= (bezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
                                                cvalue= prevbezt->vec[1][1] - (fac * dx);
                                        }
                                        else 
                                                cvalue= prevbezt->vec[1][1];
                                }
                        } 
                        else 
                        {
                                /* Use the first handle (earlier) of first BezTriple to calculate the
                                 * gradient and thus the value of the curve at evaltime
                                 */
                                dx= prevbezt->vec[1][0] - evaltime;
                                fac= prevbezt->vec[1][0] - prevbezt->vec[0][0];
                                
                                /* prevent division by zero */
                                if (fac) {
                                        fac= (prevbezt->vec[1][1] - prevbezt->vec[0][1]) / fac;
                                        cvalue= prevbezt->vec[1][1] - (fac * dx);
                                }
                                else 
                                        cvalue= prevbezt->vec[1][1];
                        }
                }
                else 
                {
                        /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation, 
                         * so just extend first keyframe's value 
                         */
                        cvalue= prevbezt->vec[1][1];
                }
        }
        else if (lastbezt->vec[1][0] <= evaltime) 
        {
                /* after or on last keyframe */
                if ( (fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (lastbezt->ipo != BEZT_IPO_CONST) &&
                        !(fcu->flag & FCURVE_DISCRETE_VALUES) ) 
                {
                        /* linear or bezier interpolation */
                        if (lastbezt->ipo==BEZT_IPO_LIN) 
                        {
                                /* Use the next center point instead of our own handle for
                                 * linear interpolated extrapolate 
                                 */
                                if (fcu->totvert == 1) 
                                        cvalue= lastbezt->vec[1][1];
                                else 
                                {
                                        prevbezt = lastbezt - 1;
                                        dx= evaltime - lastbezt->vec[1][0];
                                        fac= lastbezt->vec[1][0] - prevbezt->vec[1][0];
                                        
                                        /* prevent division by zero */
                                        if (fac) {
                                                fac= (lastbezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
                                                cvalue= lastbezt->vec[1][1] + (fac * dx);
                                        }
                                        else 
                                                cvalue= lastbezt->vec[1][1];
                                }
                        } 
                        else 
                        {
                                /* Use the gradient of the second handle (later) of last BezTriple to calculate the
                                 * gradient and thus the value of the curve at evaltime
                                 */
                                dx= evaltime - lastbezt->vec[1][0];
                                fac= lastbezt->vec[2][0] - lastbezt->vec[1][0];
                                
                                /* prevent division by zero */
                                if (fac) {
                                        fac= (lastbezt->vec[2][1] - lastbezt->vec[1][1]) / fac;
                                        cvalue= lastbezt->vec[1][1] + (fac * dx);
                                }
                                else 
                                        cvalue= lastbezt->vec[1][1];
                        }
                }
                else 
                {
                        /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation, 
                         * so just extend last keyframe's value 
                         */
                        cvalue= lastbezt->vec[1][1];
                }
        }
        else 
        {
                /* evaltime occurs somewhere in the middle of the curve */
                for (a=0; prevbezt && bezt && (a < fcu->totvert-1); a++, prevbezt=bezt, bezt++) 
                {
                        /* use if the key is directly on the frame, rare cases this is needed else we get 0.0 instead. */
                        if(fabs(bezt->vec[1][0] - evaltime) < SMALL_NUMBER) {
                                cvalue= bezt->vec[1][1];
                        }
                        /* evaltime occurs within the interval defined by these two keyframes */
                        else if ((prevbezt->vec[1][0] <= evaltime) && (bezt->vec[1][0] >= evaltime))
                        {
                                /* value depends on interpolation mode */
                                if ((prevbezt->ipo == BEZT_IPO_CONST) || (fcu->flag & FCURVE_DISCRETE_VALUES))
                                {
                                        /* constant (evaltime not relevant, so no interpolation needed) */
                                        cvalue= prevbezt->vec[1][1];
                                }
                                else if (prevbezt->ipo == BEZT_IPO_LIN) 
                                {
                                        /* linear - interpolate between values of the two keyframes */
                                        fac= bezt->vec[1][0] - prevbezt->vec[1][0];
                                        
                                        /* prevent division by zero */
                                        if (fac) {
                                                fac= (evaltime - prevbezt->vec[1][0]) / fac;
                                                cvalue= prevbezt->vec[1][1] + (fac * (bezt->vec[1][1] - prevbezt->vec[1][1]));
                                        }
                                        else
                                                cvalue= prevbezt->vec[1][1];
                                }
                                else 
                                {
                                        /* bezier interpolation */
                                                /* v1,v2 are the first keyframe and its 2nd handle */
                                        v1[0]= prevbezt->vec[1][0];
                                        v1[1]= prevbezt->vec[1][1];
                                        v2[0]= prevbezt->vec[2][0];
                                        v2[1]= prevbezt->vec[2][1];
                                                /* v3,v4 are the last keyframe's 1st handle + the last keyframe */
                                        v3[0]= bezt->vec[0][0];
                                        v3[1]= bezt->vec[0][1];
                                        v4[0]= bezt->vec[1][0];
                                        v4[1]= bezt->vec[1][1];
                                        
                                        /* adjust handles so that they don't overlap (forming a loop) */
                                        correct_bezpart(v1, v2, v3, v4);
                                        
                                        /* try to get a value for this position - if failure, try another set of points */
                                        b= findzero(evaltime, v1[0], v2[0], v3[0], v4[0], opl);
                                        if (b) {
                                                berekeny(v1[1], v2[1], v3[1], v4[1], opl, 1);
                                                cvalue= opl[0];
                                                break;
                                        }
                                }
                        }
                }
        }
        
        /* return value */
        return cvalue;
}

/* Calculate F-Curve value for 'evaltime' using FPoint samples */
static float fcurve_eval_samples (FCurve *fcu, FPoint *fpts, float evaltime)
{
        FPoint *prevfpt, *lastfpt, *fpt;
        float cvalue= 0.0f;
        
        /* get pointers */
        prevfpt= fpts;
        lastfpt= prevfpt + fcu->totvert-1;
        
        /* evaluation time at or past endpoints? */
        if (prevfpt->vec[0] >= evaltime) {
                /* before or on first sample, so just extend value */
                cvalue= prevfpt->vec[1];
        }
        else if (lastfpt->vec[0] <= evaltime) {
                /* after or on last sample, so just extend value */
                cvalue= lastfpt->vec[1];
        }
        else {
                float t= (float)abs(evaltime - (int)evaltime);
                
                /* find the one on the right frame (assume that these are spaced on 1-frame intervals) */
                fpt= prevfpt + (int)(evaltime - prevfpt->vec[0]);
                
                /* if not exactly on the frame, perform linear interpolation with the next one */
                if (t != 0.0f) 
                        cvalue= interpf(fpt->vec[1], (fpt+1)->vec[1], t);
                else
                        cvalue= fpt->vec[1];
        }
        
        /* return value */
        return cvalue;
}

/* ***************************** F-Curve - Evaluation ********************************* */

/* Evaluate and return the value of the given F-Curve at the specified frame ("evaltime") 
 * Note: this is also used for drivers
 */
float evaluate_fcurve (FCurve *fcu, float evaltime) 
{
        float cvalue= 0.0f;
        float devaltime;
        
        /* if there is a driver (only if this F-Curve is acting as 'driver'), evaluate it to find value to use as "evaltime" 
         * since drivers essentially act as alternative input (i.e. in place of 'time') for F-Curves
         *      - this value will also be returned as the value of the 'curve', if there are no keyframes
         */
        if (fcu->driver) {
                /* evaltime now serves as input for the curve */
                evaltime= cvalue= evaluate_driver(fcu->driver, evaltime);
        }
        
        /* evaluate modifiers which modify time to evaluate the base curve at */
        devaltime= evaluate_time_fmodifiers(&fcu->modifiers, fcu, cvalue, evaltime);
        
        /* evaluate curve-data 
         *      - 'devaltime' instead of 'evaltime', as this is the time that the last time-modifying 
         *        F-Curve modifier on the stack requested the curve to be evaluated at
         */
        if (fcu->bezt)
                cvalue= fcurve_eval_keyframes(fcu, fcu->bezt, devaltime);
        else if (fcu->fpt)
                cvalue= fcurve_eval_samples(fcu, fcu->fpt, devaltime);
        
        /* evaluate modifiers */
        evaluate_value_fmodifiers(&fcu->modifiers, fcu, &cvalue, evaltime);
        
        /* if curve can only have integral values, perform truncation (i.e. drop the decimal part)
         * here so that the curve can be sampled correctly
         */
        if (fcu->flag & FCURVE_INT_VALUES)
                cvalue= floorf(cvalue + 0.5f);
        
        /* return evaluated value */
        return cvalue;
}

/* Calculate the value of the given F-Curve at the given frame, and set its curval */
void calculate_fcurve (FCurve *fcu, float ctime)
{
        /* only calculate + set curval (overriding the existing value) if curve has 
         * any data which warrants this...
         */
        if ( (fcu->totvert) || (fcu->driver && !(fcu->driver->flag & DRIVER_FLAG_INVALID)) ||
                 list_has_suitable_fmodifier(&fcu->modifiers, 0, FMI_TYPE_GENERATE_CURVE) )
        {
                /* calculate and set curval (evaluates driver too if necessary) */
                fcu->curval= evaluate_fcurve(fcu, ctime);
        }
}