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