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