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