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