Patch #34204: [Render Animation] Fails with "Error: Specified sample_fmt is not suppo...
[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 = min_fff(xminv, bezt_first->vec[0][0], bezt_first->vec[1][0]);
504                                                 xmaxv = max_fff(xmaxv, bezt_last->vec[1][0],  bezt_last->vec[2][0]);
505                                         }
506                                         else {
507                                                 xminv = min_ff(xminv, bezt_first->vec[1][0]);
508                                                 xmaxv = max_ff(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 = min_ffff(yminv, bezt->vec[1][1], bezt->vec[0][1], bezt->vec[2][1]);
521                                                         ymaxv = max_ffff(ymaxv, bezt->vec[1][1], bezt->vec[0][1], bezt->vec[2][1]);
522                                                 }
523                                                 else {
524                                                         yminv = min_ff(yminv, bezt->vec[1][1]);
525                                                         ymaxv = max_ff(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 = min_ff(xminv, fcu->fpt[0].vec[0]);
537                                 xmaxv = max_ff(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 = min_ff(min, bezt_first->vec[1][0]);
595                                 max = max_ff(max, bezt_last->vec[1][0]);
596                                 
597                                 foundvert = TRUE;
598                         }
599                 }
600                 else if (fcu->fpt) {
601                         min = min_ff(min, fcu->fpt[0].vec[0]);
602                         max = max_ff(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         short 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 = -1;
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                 dtar->flag   |= DTAR_FLAG_INVALID;
1033                 return 0.0f;
1034         }
1035         
1036         /* get RNA-pointer for the ID-block given in target */
1037         RNA_id_pointer_create(id, &id_ptr);
1038         
1039         /* get property to read from, and get value as appropriate */
1040         if (RNA_path_resolve_full(&id_ptr, dtar->rna_path, &ptr, &prop, &index)) {
1041                 if (RNA_property_array_check(prop)) {
1042                         /* array */
1043                         if ((index >= 0) && (index < RNA_property_array_length(&ptr, prop))) {
1044                                 switch (RNA_property_type(prop)) {
1045                                         case PROP_BOOLEAN:
1046                                                 value = (float)RNA_property_boolean_get_index(&ptr, prop, index);
1047                                                 break;
1048                                         case PROP_INT:
1049                                                 value = (float)RNA_property_int_get_index(&ptr, prop, index);
1050                                                 break;
1051                                         case PROP_FLOAT:
1052                                                 value = RNA_property_float_get_index(&ptr, prop, index);
1053                                                 break;
1054                                         default:
1055                                                 break;
1056                                 }
1057                         }
1058                         else {
1059                                 /* out of bounds */
1060                                 if (G.debug & G_DEBUG) {
1061                                         printf("Driver Evaluation Error: array index is out of bounds for %s -> %s (%d)", 
1062                                                id->name, dtar->rna_path, index);
1063                                 }
1064                                 
1065                                 driver->flag |= DRIVER_FLAG_INVALID;
1066                                 dtar->flag   |= DTAR_FLAG_INVALID;
1067                                 return 0.0f;
1068                         }
1069                 }
1070                 else {
1071                         /* not an array */
1072                         switch (RNA_property_type(prop)) {
1073                                 case PROP_BOOLEAN:
1074                                         value = (float)RNA_property_boolean_get(&ptr, prop);
1075                                         break;
1076                                 case PROP_INT:
1077                                         value = (float)RNA_property_int_get(&ptr, prop);
1078                                         break;
1079                                 case PROP_FLOAT:
1080                                         value = RNA_property_float_get(&ptr, prop);
1081                                         break;
1082                                 case PROP_ENUM:
1083                                         value = (float)RNA_property_enum_get(&ptr, prop);
1084                                         break;
1085                                 default:
1086                                         break;
1087                         }
1088                 }
1089         }
1090         else {
1091                 /* path couldn't be resolved */
1092                 if (G.debug & G_DEBUG)
1093                         printf("Driver Evaluation Error: cannot resolve target for %s -> %s\n", id->name, dtar->rna_path);
1094                 
1095                 driver->flag |= DRIVER_FLAG_INVALID;
1096                 dtar->flag   |= DTAR_FLAG_INVALID;
1097                 return 0.0f;
1098         }
1099         
1100         /* if we're still here, we should be ok... */
1101         dtar->flag &= ~DTAR_FLAG_INVALID;
1102         return value;
1103 }
1104
1105 /* Helper function to obtain a pointer to a Pose Channel (for evaluating drivers) */
1106 static bPoseChannel *dtar_get_pchan_ptr(ChannelDriver *driver, DriverTarget *dtar)
1107 {
1108         ID *id;
1109         /* sanity check */
1110         if (ELEM(NULL, driver, dtar))
1111                 return NULL;
1112
1113         id = dtar_id_ensure_proxy_from(dtar->id);
1114
1115         /* check if the ID here is a valid object */
1116         if (id && GS(id->name)) {
1117                 Object *ob = (Object *)id;
1118                 
1119                 /* get pose, and subsequently, posechannel */
1120                 return BKE_pose_channel_find_name(ob->pose, dtar->pchan_name);
1121         }
1122         else {
1123                 /* cannot find a posechannel this way */
1124                 return NULL;
1125         }
1126 }
1127
1128 /* ......... */
1129
1130 /* evaluate 'single prop' driver variable */
1131 static float dvar_eval_singleProp(ChannelDriver *driver, DriverVar *dvar)
1132 {
1133         /* just evaluate the first target slot */
1134         return dtar_get_prop_val(driver, &dvar->targets[0]);
1135 }
1136
1137 /* evaluate 'rotation difference' driver variable */
1138 static float dvar_eval_rotDiff(ChannelDriver *driver, DriverVar *dvar)
1139 {
1140         DriverTarget *dtar1 = &dvar->targets[0];
1141         DriverTarget *dtar2 = &dvar->targets[1];
1142         bPoseChannel *pchan, *pchan2;
1143         float q1[4], q2[4], quat[4], angle;
1144         
1145         /* get pose channels, and check if we've got two */
1146         pchan  = dtar_get_pchan_ptr(driver, dtar1);
1147         pchan2 = dtar_get_pchan_ptr(driver, dtar2);
1148         
1149         if (ELEM(NULL, pchan, pchan2)) {
1150                 /* disable this driver, since it doesn't work correctly... */
1151                 driver->flag |= DRIVER_FLAG_INVALID;
1152                 
1153                 /* check what the error was */
1154                 if ((pchan == NULL) && (pchan2 == NULL)) {
1155                         printf("Driver Evaluation Error: Rotational difference failed - first 2 targets invalid\n");
1156                         
1157                         dtar1->flag |= DTAR_FLAG_INVALID;
1158                         dtar2->flag |= DTAR_FLAG_INVALID;
1159                 }
1160                 else if (pchan == NULL) {
1161                         printf("Driver Evaluation Error: Rotational difference failed - first target not valid PoseChannel\n");
1162                         
1163                         dtar1->flag |=  DTAR_FLAG_INVALID;
1164                         dtar2->flag &= ~DTAR_FLAG_INVALID;
1165                 }
1166                 else if (pchan2 == NULL) {
1167                         printf("Driver Evaluation Error: Rotational difference failed - second target not valid PoseChannel\n");
1168                         
1169                         dtar1->flag &= ~DTAR_FLAG_INVALID;
1170                         dtar2->flag |=  DTAR_FLAG_INVALID;
1171                 }
1172                 
1173                 /* stop here... */
1174                 return 0.0f;
1175         }
1176         
1177         /* use the final posed locations */
1178         mat4_to_quat(q1, pchan->pose_mat);
1179         mat4_to_quat(q2, pchan2->pose_mat);
1180         
1181         invert_qt(q1);
1182         mul_qt_qtqt(quat, q1, q2);
1183         angle = 2.0f * (saacos(quat[0]));
1184         angle = ABS(angle);
1185         
1186         return (angle > (float)M_PI) ? (float)((2.0f * (float)M_PI) - angle) : (float)(angle);
1187 }
1188
1189 /* evaluate 'location difference' driver variable */
1190 /* TODO: this needs to take into account space conversions... */
1191 static float dvar_eval_locDiff(ChannelDriver *driver, DriverVar *dvar)
1192 {
1193         float loc1[3] = {0.0f, 0.0f, 0.0f};
1194         float loc2[3] = {0.0f, 0.0f, 0.0f};
1195         short valid_targets = 0;
1196         
1197         /* Perform two passes
1198          *
1199          * FIRST PASS - to just check that everything works... 
1200          * NOTE: we use loops here to reduce code duplication, though in practice, 
1201          *       there can only be 2 items or else we run into some problems later
1202          */
1203         DRIVER_TARGETS_USED_LOOPER(dvar)
1204         {
1205                 Object *ob = (Object *)dtar_id_ensure_proxy_from(dtar->id);
1206                 
1207                 /* check if this target has valid data */
1208                 if ((ob == NULL) || (GS(ob->id.name) != ID_OB)) {
1209                         /* invalid target, so will not have enough targets */
1210                         driver->flag |= DRIVER_FLAG_INVALID;
1211                         dtar->flag   |= DTAR_FLAG_INVALID;
1212                 }
1213                 else {
1214                         /* target seems to be OK now... */
1215                         dtar->flag &= ~DTAR_FLAG_INVALID;
1216                         valid_targets++;
1217                 }
1218         }
1219         DRIVER_TARGETS_LOOPER_END
1220         
1221         /* make sure we have enough valid targets to use - all or nothing for now... */
1222         if (valid_targets < dvar->num_targets) {
1223                 if (G.debug & G_DEBUG) {
1224                         printf("LocDiff DVar: not enough valid targets (n = %d) (a = %p, b = %p)\n",
1225                                 valid_targets, dvar->targets[0].id, dvar->targets[1].id);
1226                 }
1227                 return 0.0f;
1228         }
1229         
1230         
1231         /* SECOND PASS: get two location values */
1232         /* NOTE: for now, these are all just worldspace */
1233         DRIVER_TARGETS_USED_LOOPER(dvar)
1234         {
1235                 /* get pointer to loc values to store in */
1236                 Object *ob = (Object *)dtar_id_ensure_proxy_from(dtar->id);
1237                 bPoseChannel *pchan;
1238                 float tmp_loc[3];
1239                 
1240                 /* after the checks above, the targets should be valid here... */
1241                 BLI_assert((ob != NULL) && (GS(ob->id.name) != ID_OB));
1242                 
1243                 /* try to get posechannel */
1244                 pchan = BKE_pose_channel_find_name(ob->pose, dtar->pchan_name);
1245                 
1246                 /* check if object or bone */
1247                 if (pchan) {
1248                         /* bone */
1249                         if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1250                                 if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1251                                         float mat[4][4];
1252                                         
1253                                         /* extract transform just like how the constraints do it! */
1254                                         copy_m4_m4(mat, pchan->pose_mat);
1255                                         BKE_constraint_mat_convertspace(ob, pchan, mat, CONSTRAINT_SPACE_POSE, CONSTRAINT_SPACE_LOCAL);
1256                                         
1257                                         /* ... and from that, we get our transform */
1258                                         copy_v3_v3(tmp_loc, mat[3]);
1259                                 }
1260                                 else {
1261                                         /* transform space (use transform values directly) */
1262                                         copy_v3_v3(tmp_loc, pchan->loc);
1263                                 }
1264                         }
1265                         else {
1266                                 /* convert to worldspace */
1267                                 copy_v3_v3(tmp_loc, pchan->pose_head);
1268                                 mul_m4_v3(ob->obmat, tmp_loc);
1269                         }
1270                 }
1271                 else {
1272                         /* object */
1273                         if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1274                                 if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1275                                         /* XXX: this should practically be the same as transform space... */
1276                                         float mat[4][4];
1277                                         
1278                                         /* extract transform just like how the constraints do it! */
1279                                         copy_m4_m4(mat, ob->obmat);
1280                                         BKE_constraint_mat_convertspace(ob, NULL, mat, CONSTRAINT_SPACE_WORLD, CONSTRAINT_SPACE_LOCAL);
1281                                         
1282                                         /* ... and from that, we get our transform */
1283                                         copy_v3_v3(tmp_loc, mat[3]);
1284                                 }
1285                                 else {
1286                                         /* transform space (use transform values directly) */
1287                                         copy_v3_v3(tmp_loc, ob->loc);
1288                                 }
1289                         }
1290                         else {
1291                                 /* worldspace */
1292                                 copy_v3_v3(tmp_loc, ob->obmat[3]);
1293                         }
1294                 }
1295                 
1296                 /* copy the location to the right place */
1297                 if (tarIndex) {
1298                         copy_v3_v3(loc2, tmp_loc);
1299                 }
1300                 else {
1301                         copy_v3_v3(loc1, tmp_loc);
1302                 }
1303         }
1304         DRIVER_TARGETS_LOOPER_END
1305         
1306         
1307         /* if we're still here, there should now be two targets to use,
1308          * so just take the length of the vector between these points 
1309          */
1310         return len_v3v3(loc1, loc2);
1311 }
1312
1313 /* evaluate 'transform channel' driver variable */
1314 static float dvar_eval_transChan(ChannelDriver *driver, DriverVar *dvar)
1315 {
1316         DriverTarget *dtar = &dvar->targets[0];
1317         Object *ob = (Object *)dtar_id_ensure_proxy_from(dtar->id);
1318         bPoseChannel *pchan;
1319         float mat[4][4];
1320         float oldEul[3] = {0.0f, 0.0f, 0.0f};
1321         short use_eulers = FALSE, rot_order = ROT_MODE_EUL;
1322         
1323         /* check if this target has valid data */
1324         if ((ob == NULL) || (GS(ob->id.name) != ID_OB)) {
1325                 /* invalid target, so will not have enough targets */
1326                 driver->flag |= DRIVER_FLAG_INVALID;
1327                 dtar->flag   |= DTAR_FLAG_INVALID;
1328                 return 0.0f;
1329         }
1330         else {
1331                 /* target should be valid now */
1332                 dtar->flag &= ~DTAR_FLAG_INVALID;
1333         }
1334         
1335         /* try to get posechannel */
1336         pchan = BKE_pose_channel_find_name(ob->pose, dtar->pchan_name);
1337         
1338         /* check if object or bone, and get transform matrix accordingly 
1339          *      - "useEulers" code is used to prevent the problems associated with non-uniqueness
1340          *        of euler decomposition from matrices [#20870]
1341          *      - localspace is for [#21384], where parent results are not wanted
1342          *        but local-consts is for all the common "corrective-shapes-for-limbs" situations
1343          */
1344         if (pchan) {
1345                 /* bone */
1346                 if (pchan->rotmode > 0) {
1347                         copy_v3_v3(oldEul, pchan->eul);
1348                         rot_order = pchan->rotmode;
1349                         use_eulers = TRUE;
1350                 }
1351                 
1352                 if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1353                         if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1354                                 /* just like how the constraints do it! */
1355                                 copy_m4_m4(mat, pchan->pose_mat);
1356                                 BKE_constraint_mat_convertspace(ob, pchan, mat, CONSTRAINT_SPACE_POSE, CONSTRAINT_SPACE_LOCAL);
1357                         }
1358                         else {
1359                                 /* specially calculate local matrix, since chan_mat is not valid 
1360                                  * since it stores delta transform of pose_mat so that deforms work
1361                                  * so it cannot be used here for "transform" space
1362                                  */
1363                                 BKE_pchan_to_mat4(pchan, mat);
1364                         }
1365                 }
1366                 else {
1367                         /* worldspace matrix */
1368                         mult_m4_m4m4(mat, ob->obmat, pchan->pose_mat);
1369                 }
1370         }
1371         else {
1372                 /* object */
1373                 if (ob->rotmode > 0) {
1374                         copy_v3_v3(oldEul, ob->rot);
1375                         rot_order = ob->rotmode;
1376                         use_eulers = TRUE;
1377                 }
1378                 
1379                 if (dtar->flag & DTAR_FLAG_LOCALSPACE) {
1380                         if (dtar->flag & DTAR_FLAG_LOCAL_CONSTS) {
1381                                 /* just like how the constraints do it! */
1382                                 copy_m4_m4(mat, ob->obmat);
1383                                 BKE_constraint_mat_convertspace(ob, NULL, mat, CONSTRAINT_SPACE_WORLD, CONSTRAINT_SPACE_LOCAL);
1384                         }
1385                         else {
1386                                 /* transforms to matrix */
1387                                 BKE_object_to_mat4(ob, mat);
1388                         }
1389                 }
1390                 else {
1391                         /* worldspace matrix - just the good-old one */
1392                         copy_m4_m4(mat, ob->obmat);
1393                 }
1394         }
1395         
1396         /* check which transform */
1397         if (dtar->transChan >= MAX_DTAR_TRANSCHAN_TYPES) {
1398                 /* not valid channel */
1399                 return 0.0f;
1400         }
1401         else if (dtar->transChan >= DTAR_TRANSCHAN_SCALEX) {
1402                 /* extract scale, and choose the right axis */
1403                 float scale[3];
1404                 
1405                 mat4_to_size(scale, mat);
1406                 return scale[dtar->transChan - DTAR_TRANSCHAN_SCALEX];
1407         }
1408         else if (dtar->transChan >= DTAR_TRANSCHAN_ROTX) {
1409                 /* extract rotation as eulers (if needed) 
1410                  *      - definitely if rotation order isn't eulers already
1411                  *      - if eulers, then we have 2 options:
1412                  *              a) decompose transform matrix as required, then try to make eulers from
1413                  *                 there compatible with original values
1414                  *              b) [NOT USED] directly use the original values (no decomposition) 
1415                  *                      - only an option for "transform space", if quality is really bad with a)
1416                  */
1417                 float eul[3];
1418                 
1419                 mat4_to_eulO(eul, rot_order, mat);
1420                 
1421                 if (use_eulers) {
1422                         compatible_eul(eul, oldEul);
1423                 }
1424                 
1425                 return eul[dtar->transChan - DTAR_TRANSCHAN_ROTX];
1426         }
1427         else {
1428                 /* extract location and choose right axis */
1429                 return mat[3][dtar->transChan];
1430         }
1431 }
1432
1433 /* ......... */
1434
1435 /* Table of Driver Varaiable Type Info Data */
1436 static DriverVarTypeInfo dvar_types[MAX_DVAR_TYPES] = {
1437         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_SINGLE_PROP)
1438                 dvar_eval_singleProp,     /* eval callback */
1439                 1,     /* number of targets used */
1440                 {"Property"},     /* UI names for targets */
1441                 {0}     /* flags */
1442         END_DVAR_TYPEDEF,
1443         
1444         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_ROT_DIFF)
1445                 dvar_eval_rotDiff,     /* eval callback */
1446                 2,     /* number of targets used */
1447                 {"Bone 1", "Bone 2"},     /* UI names for targets */
1448                 {DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY, DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY} /* flags */
1449         END_DVAR_TYPEDEF,
1450         
1451         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_LOC_DIFF)
1452                 dvar_eval_locDiff,     /* eval callback */
1453                 2,     /* number of targets used */
1454                 {"Object/Bone 1", "Object/Bone 2"},     /* UI names for targets */
1455                 {DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY, DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY} /* flags */
1456         END_DVAR_TYPEDEF,
1457         
1458         BEGIN_DVAR_TYPEDEF(DVAR_TYPE_TRANSFORM_CHAN)
1459                 dvar_eval_transChan,     /* eval callback */
1460                 1,     /* number of targets used */
1461                 {"Object/Bone"},     /* UI names for targets */
1462                 {DTAR_FLAG_STRUCT_REF | DTAR_FLAG_ID_OB_ONLY}   /* flags */
1463         END_DVAR_TYPEDEF,
1464 };
1465
1466 /* Get driver variable typeinfo */
1467 static DriverVarTypeInfo *get_dvar_typeinfo(int type)
1468 {
1469         /* check if valid type */
1470         if ((type >= 0) && (type < MAX_DVAR_TYPES))
1471                 return &dvar_types[type];
1472         else
1473                 return NULL;
1474 }
1475
1476 /* Driver API --------------------------------- */
1477
1478 /* This frees the driver variable itself */
1479 void driver_free_variable(ChannelDriver *driver, DriverVar *dvar)
1480 {
1481         /* sanity checks */
1482         if (dvar == NULL)
1483                 return;
1484                 
1485         /* free target vars 
1486          *      - need to go over all of them, not just up to the ones that are used
1487          *        currently, since there may be some lingering RNA paths from 
1488          *    previous users needing freeing
1489          */
1490         DRIVER_TARGETS_LOOPER(dvar) 
1491         {
1492                 /* free RNA path if applicable */
1493                 if (dtar->rna_path)
1494                         MEM_freeN(dtar->rna_path);
1495         }
1496         DRIVER_TARGETS_LOOPER_END
1497         
1498         /* remove the variable from the driver */
1499         BLI_freelinkN(&driver->variables, dvar);
1500
1501 #ifdef WITH_PYTHON
1502         /* since driver variables are cached, the expression needs re-compiling too */
1503         if (driver->type == DRIVER_TYPE_PYTHON)
1504                 driver->flag |= DRIVER_FLAG_RENAMEVAR;
1505 #endif
1506 }
1507
1508 /* Change the type of driver variable */
1509 void driver_change_variable_type(DriverVar *dvar, int type)
1510 {
1511         DriverVarTypeInfo *dvti = get_dvar_typeinfo(type);
1512         
1513         /* sanity check */
1514         if (ELEM(NULL, dvar, dvti))
1515                 return;
1516                 
1517         /* set the new settings */
1518         dvar->type = type;
1519         dvar->num_targets = dvti->num_targets;
1520         
1521         /* make changes to the targets based on the defines for these types 
1522          * NOTE: only need to make sure the ones we're using here are valid...
1523          */
1524         DRIVER_TARGETS_USED_LOOPER(dvar)
1525         {
1526                 short flags = dvti->target_flags[tarIndex];
1527                 
1528                 /* store the flags */
1529                 dtar->flag = flags;
1530                 
1531                 /* object ID types only, or idtype not yet initialized */
1532                 if ((flags & DTAR_FLAG_ID_OB_ONLY) || (dtar->idtype == 0))
1533                         dtar->idtype = ID_OB;
1534         }
1535         DRIVER_TARGETS_LOOPER_END
1536 }
1537
1538 /* Add a new driver variable */
1539 DriverVar *driver_add_new_variable(ChannelDriver *driver)
1540 {
1541         DriverVar *dvar;
1542         
1543         /* sanity checks */
1544         if (driver == NULL)
1545                 return NULL;
1546                 
1547         /* make a new variable */
1548         dvar = MEM_callocN(sizeof(DriverVar), "DriverVar");
1549         BLI_addtail(&driver->variables, dvar);
1550         
1551         /* give the variable a 'unique' name */
1552         strcpy(dvar->name, "var");
1553         BLI_uniquename(&driver->variables, dvar, "var", '_', offsetof(DriverVar, name), sizeof(dvar->name));
1554         
1555         /* set the default type to 'single prop' */
1556         driver_change_variable_type(dvar, DVAR_TYPE_SINGLE_PROP);
1557         
1558 #ifdef WITH_PYTHON
1559         /* since driver variables are cached, the expression needs re-compiling too */
1560         if (driver->type == DRIVER_TYPE_PYTHON)
1561                 driver->flag |= DRIVER_FLAG_RENAMEVAR;
1562 #endif
1563
1564         /* return the target */
1565         return dvar;
1566 }
1567
1568 /* This frees the driver itself */
1569 void fcurve_free_driver(FCurve *fcu)
1570 {
1571         ChannelDriver *driver;
1572         DriverVar *dvar, *dvarn;
1573         
1574         /* sanity checks */
1575         if (ELEM(NULL, fcu, fcu->driver))
1576                 return;
1577         driver = fcu->driver;
1578         
1579         /* free driver targets */
1580         for (dvar = driver->variables.first; dvar; dvar = dvarn) {
1581                 dvarn = dvar->next;
1582                 driver_free_variable(driver, dvar);
1583         }
1584
1585 #ifdef WITH_PYTHON
1586         /* free compiled driver expression */
1587         if (driver->expr_comp)
1588                 BPY_DECREF(driver->expr_comp);
1589 #endif
1590
1591         /* free driver itself, then set F-Curve's point to this to NULL (as the curve may still be used) */
1592         MEM_freeN(driver);
1593         fcu->driver = NULL;
1594 }
1595
1596 /* This makes a copy of the given driver */
1597 ChannelDriver *fcurve_copy_driver(ChannelDriver *driver)
1598 {
1599         ChannelDriver *ndriver;
1600         DriverVar *dvar;
1601         
1602         /* sanity checks */
1603         if (driver == NULL)
1604                 return NULL;
1605                 
1606         /* copy all data */
1607         ndriver = MEM_dupallocN(driver);
1608         ndriver->expr_comp = NULL;
1609         
1610         /* copy variables */
1611         ndriver->variables.first = ndriver->variables.last = NULL;
1612         BLI_duplicatelist(&ndriver->variables, &driver->variables);
1613         
1614         for (dvar = ndriver->variables.first; dvar; dvar = dvar->next) {
1615                 /* need to go over all targets so that we don't leave any dangling paths */
1616                 DRIVER_TARGETS_LOOPER(dvar) 
1617                 {
1618                         /* make a copy of target's rna path if available */
1619                         if (dtar->rna_path)
1620                                 dtar->rna_path = MEM_dupallocN(dtar->rna_path);
1621                 }
1622                 DRIVER_TARGETS_LOOPER_END
1623         }
1624         
1625         /* return the new driver */
1626         return ndriver;
1627 }
1628
1629 /* Driver Evaluation -------------------------- */
1630
1631 /* Evaluate a Driver Variable to get a value that contributes to the final */
1632 float driver_get_variable_value(ChannelDriver *driver, DriverVar *dvar)
1633 {
1634         DriverVarTypeInfo *dvti;
1635
1636         /* sanity check */
1637         if (ELEM(NULL, driver, dvar))
1638                 return 0.0f;
1639         
1640         /* call the relevant callbacks to get the variable value 
1641          * using the variable type info, storing the obtained value
1642          * in dvar->curval so that drivers can be debugged
1643          */
1644         dvti = get_dvar_typeinfo(dvar->type);
1645         
1646         if (dvti && dvti->get_value)
1647                 dvar->curval = dvti->get_value(driver, dvar);
1648         else
1649                 dvar->curval = 0.0f;
1650         
1651         return dvar->curval;
1652 }
1653
1654 /* Evaluate an Channel-Driver to get a 'time' value to use instead of "evaltime"
1655  *      - "evaltime" is the frame at which F-Curve is being evaluated
1656  *  - has to return a float value
1657  */
1658 static float evaluate_driver(ChannelDriver *driver, const float evaltime)
1659 {
1660         DriverVar *dvar;
1661         
1662         /* check if driver can be evaluated */
1663         if (driver->flag & DRIVER_FLAG_INVALID)
1664                 return 0.0f;
1665         
1666         switch (driver->type) {
1667                 case DRIVER_TYPE_AVERAGE: /* average values of driver targets */
1668                 case DRIVER_TYPE_SUM: /* sum values of driver targets */
1669                 {
1670                         /* check how many variables there are first (i.e. just one?) */
1671                         if (driver->variables.first == driver->variables.last) {
1672                                 /* just one target, so just use that */
1673                                 dvar = driver->variables.first;
1674                                 driver->curval = driver_get_variable_value(driver, dvar);
1675                         }
1676                         else {
1677                                 /* more than one target, so average the values of the targets */
1678                                 float value = 0.0f;
1679                                 int tot = 0;
1680                                 
1681                                 /* loop through targets, adding (hopefully we don't get any overflow!) */
1682                                 for (dvar = driver->variables.first; dvar; dvar = dvar->next) {
1683                                         value += driver_get_variable_value(driver, dvar);
1684                                         tot++;
1685                                 }
1686                                 
1687                                 /* perform operations on the total if appropriate */
1688                                 if (driver->type == DRIVER_TYPE_AVERAGE)
1689                                         driver->curval = (value / (float)tot);
1690                                 else
1691                                         driver->curval = value;
1692                         }
1693                 }
1694                 break;
1695                         
1696                 case DRIVER_TYPE_MIN: /* smallest value */
1697                 case DRIVER_TYPE_MAX: /* largest value */
1698                 {
1699                         float value = 0.0f;
1700                         
1701                         /* loop through the variables, getting the values and comparing them to existing ones */
1702                         for (dvar = driver->variables.first; dvar; dvar = dvar->next) {
1703                                 /* get value */
1704                                 float tmp_val = driver_get_variable_value(driver, dvar);
1705                                 
1706                                 /* store this value if appropriate */
1707                                 if (dvar->prev) {
1708                                         /* check if greater/smaller than the baseline */
1709                                         if (driver->type == DRIVER_TYPE_MAX) {
1710                                                 /* max? */
1711                                                 if (tmp_val > value) 
1712                                                         value = tmp_val;
1713                                         }
1714                                         else {
1715                                                 /* min? */
1716                                                 if (tmp_val < value) 
1717                                                         value = tmp_val;
1718                                         }
1719                                 }
1720                                 else {
1721                                         /* first item - make this the baseline for comparisons */
1722                                         value = tmp_val;
1723                                 }
1724                         }
1725                         
1726                         /* store value in driver */
1727                         driver->curval = value;
1728                 }
1729                 break;
1730                         
1731                 case DRIVER_TYPE_PYTHON: /* expression */
1732                 {
1733 #ifdef WITH_PYTHON
1734                         /* check for empty or invalid expression */
1735                         if ( (driver->expression[0] == '\0') ||
1736                              (driver->flag & DRIVER_FLAG_INVALID) )
1737                         {
1738                                 driver->curval = 0.0f;
1739                         }
1740                         else {
1741                                 /* this evaluates the expression using Python, and returns its result:
1742                                  *  - on errors it reports, then returns 0.0f
1743                                  */
1744                                 driver->curval = BPY_driver_exec(driver, evaltime);
1745                         }
1746 #else /* WITH_PYTHON*/
1747                         (void)evaltime;
1748 #endif /* WITH_PYTHON*/
1749                 }
1750                 break;
1751                 
1752                 default:
1753                 {
1754                         /* special 'hack' - just use stored value 
1755                          *      This is currently used as the mechanism which allows animated settings to be able
1756                          *  to be changed via the UI.
1757                          */
1758                 }
1759         }
1760         
1761         /* return value for driver */
1762         return driver->curval;
1763 }
1764
1765 /* ***************************** Curve Calculations ********************************* */
1766
1767 /* The total length of the handles is not allowed to be more
1768  * than the horizontal distance between (v1-v4).
1769  * This is to prevent curve loops.
1770  */
1771 void correct_bezpart(float v1[2], float v2[2], float v3[2], float v4[2])
1772 {
1773         float h1[2], h2[2], len1, len2, len, fac;
1774         
1775         /* calculate handle deltas */
1776         h1[0] = v1[0] - v2[0];
1777         h1[1] = v1[1] - v2[1];
1778         
1779         h2[0] = v4[0] - v3[0];
1780         h2[1] = v4[1] - v3[1];
1781         
1782         /* calculate distances: 
1783          *  - len       = span of time between keyframes
1784          *      - len1  = length of handle of start key
1785          *      - len2  = length of handle of end key
1786          */
1787         len = v4[0] - v1[0];
1788         len1 = fabsf(h1[0]);
1789         len2 = fabsf(h2[0]);
1790         
1791         /* if the handles have no length, no need to do any corrections */
1792         if ((len1 + len2) == 0.0f)
1793                 return;
1794                 
1795         /* the two handles cross over each other, so force them
1796          * apart using the proportion they overlap 
1797          */
1798         if ((len1 + len2) > len) {
1799                 fac = len / (len1 + len2);
1800                 
1801                 v2[0] = (v1[0] - fac * h1[0]);
1802                 v2[1] = (v1[1] - fac * h1[1]);
1803                 
1804                 v3[0] = (v4[0] - fac * h2[0]);
1805                 v3[1] = (v4[1] - fac * h2[1]);
1806         }
1807 }
1808
1809 /* find root ('zero') */
1810 static int findzero(float x, float q0, float q1, float q2, float q3, float *o)
1811 {
1812         double c0, c1, c2, c3, a, b, c, p, q, d, t, phi;
1813         int nr = 0;
1814
1815         c0 = q0 - x;
1816         c1 = 3.0f * (q1 - q0);
1817         c2 = 3.0f * (q0 - 2.0f * q1 + q2);
1818         c3 = q3 - q0 + 3.0f * (q1 - q2);
1819         
1820         if (c3 != 0.0) {
1821                 a = c2 / c3;
1822                 b = c1 / c3;
1823                 c = c0 / c3;
1824                 a = a / 3;
1825
1826                 p = b / 3 - a * a;
1827                 q = (2 * a * a * a - a * b + c) / 2;
1828                 d = q * q + p * p * p;
1829                 
1830                 if (d > 0.0) {
1831                         t = sqrt(d);
1832                         o[0] = (float)(sqrt3d(-q + t) + sqrt3d(-q - t) - a);
1833                         
1834                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
1835                         else return 0;
1836                 }
1837                 else if (d == 0.0) {
1838                         t = sqrt3d(-q);
1839                         o[0] = (float)(2 * t - a);
1840                         
1841                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
1842                         o[nr] = (float)(-t - a);
1843                         
1844                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr + 1;
1845                         else return nr;
1846                 }
1847                 else {
1848                         phi = acos(-q / sqrt(-(p * p * p)));
1849                         t = sqrt(-p);
1850                         p = cos(phi / 3);
1851                         q = sqrt(3 - 3 * p * p);
1852                         o[0] = (float)(2 * t * p - a);
1853                         
1854                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
1855                         o[nr] = (float)(-t * (p + q) - a);
1856                         
1857                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) nr++;
1858                         o[nr] = (float)(-t * (p - q) - a);
1859                         
1860                         if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr + 1;
1861                         else return nr;
1862                 }
1863         }
1864         else {
1865                 a = c2;
1866                 b = c1;
1867                 c = c0;
1868                 
1869                 if (a != 0.0) {
1870                         /* discriminant */
1871                         p = b * b - 4 * a * c;
1872                         
1873                         if (p > 0) {
1874                                 p = sqrt(p);
1875                                 o[0] = (float)((-b - p) / (2 * a));
1876                                 
1877                                 if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) nr++;
1878                                 o[nr] = (float)((-b + p) / (2 * a));
1879                                 
1880                                 if ((o[nr] >= (float)SMALL) && (o[nr] <= 1.000001f)) return nr + 1;
1881                                 else return nr;
1882                         }
1883                         else if (p == 0) {
1884                                 o[0] = (float)(-b / (2 * a));
1885                                 if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
1886                                 else return 0;
1887                         }
1888                 }
1889                 else if (b != 0.0) {
1890                         o[0] = (float)(-c / b);
1891                         
1892                         if ((o[0] >= (float)SMALL) && (o[0] <= 1.000001f)) return 1;
1893                         else return 0;
1894                 }
1895                 else if (c == 0.0) {
1896                         o[0] = 0.0;
1897                         return 1;
1898                 }
1899                 
1900                 return 0;
1901         }
1902 }
1903
1904 static void berekeny(float f1, float f2, float f3, float f4, float *o, int b)
1905 {
1906         float t, c0, c1, c2, c3;
1907         int a;
1908
1909         c0 = f1;
1910         c1 = 3.0f * (f2 - f1);
1911         c2 = 3.0f * (f1 - 2.0f * f2 + f3);
1912         c3 = f4 - f1 + 3.0f * (f2 - f3);
1913
1914         for (a = 0; a < b; a++) {
1915                 t = o[a];
1916                 o[a] = c0 + t * c1 + t * t * c2 + t * t * t * c3;
1917         }
1918 }
1919
1920 #if 0
1921 static void berekenx(float *f, float *o, int b)
1922 {
1923         float t, c0, c1, c2, c3;
1924         int a;
1925
1926         c0 = f[0];
1927         c1 = 3.0f * (f[3] - f[0]);
1928         c2 = 3.0f * (f[0] - 2.0f * f[3] + f[6]);
1929         c3 = f[9] - f[0] + 3.0f * (f[3] - f[6]);
1930
1931         for (a = 0; a < b; a++) {
1932                 t = o[a];
1933                 o[a] = c0 + t * c1 + t * t * c2 + t * t * t * c3;
1934         }
1935 }
1936 #endif
1937
1938
1939 /* -------------------------- */
1940
1941 /* Calculate F-Curve value for 'evaltime' using BezTriple keyframes */
1942 static float fcurve_eval_keyframes(FCurve *fcu, BezTriple *bezts, float evaltime)
1943 {
1944         BezTriple *bezt, *prevbezt, *lastbezt;
1945         float v1[2], v2[2], v3[2], v4[2], opl[32], dx, fac;
1946         unsigned int a;
1947         int b;
1948         float cvalue = 0.0f;
1949         
1950         /* get pointers */
1951         a = fcu->totvert - 1;
1952         prevbezt = bezts;
1953         bezt = prevbezt + 1;
1954         lastbezt = prevbezt + a;
1955         
1956         /* evaluation time at or past endpoints? */
1957         if (prevbezt->vec[1][0] >= evaltime) {
1958                 /* before or on first keyframe */
1959                 if ( (fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (prevbezt->ipo != BEZT_IPO_CONST) &&
1960                      !(fcu->flag & FCURVE_DISCRETE_VALUES) )
1961                 {
1962                         /* linear or bezier interpolation */
1963                         if (prevbezt->ipo == BEZT_IPO_LIN) {
1964                                 /* Use the next center point instead of our own handle for
1965                                  * linear interpolated extrapolate 
1966                                  */
1967                                 if (fcu->totvert == 1) {
1968                                         cvalue = prevbezt->vec[1][1];
1969                                 }
1970                                 else {
1971                                         bezt = prevbezt + 1;
1972                                         dx = prevbezt->vec[1][0] - evaltime;
1973                                         fac = bezt->vec[1][0] - prevbezt->vec[1][0];
1974                                         
1975                                         /* prevent division by zero */
1976                                         if (fac) {
1977                                                 fac = (bezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
1978                                                 cvalue = prevbezt->vec[1][1] - (fac * dx);
1979                                         }
1980                                         else {
1981                                                 cvalue = prevbezt->vec[1][1];
1982                                         }
1983                                 }
1984                         }
1985                         else {
1986                                 /* Use the first handle (earlier) of first BezTriple to calculate the
1987                                  * gradient and thus the value of the curve at evaltime
1988                                  */
1989                                 dx = prevbezt->vec[1][0] - evaltime;
1990                                 fac = prevbezt->vec[1][0] - prevbezt->vec[0][0];
1991                                 
1992                                 /* prevent division by zero */
1993                                 if (fac) {
1994                                         fac = (prevbezt->vec[1][1] - prevbezt->vec[0][1]) / fac;
1995                                         cvalue = prevbezt->vec[1][1] - (fac * dx);
1996                                 }
1997                                 else {
1998                                         cvalue = prevbezt->vec[1][1];
1999                                 }
2000                         }
2001                 }
2002                 else {
2003                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation, 
2004                          * so just extend first keyframe's value 
2005                          */
2006                         cvalue = prevbezt->vec[1][1];
2007                 }
2008         }
2009         else if (lastbezt->vec[1][0] <= evaltime) {
2010                 /* after or on last keyframe */
2011                 if ( (fcu->extend == FCURVE_EXTRAPOLATE_LINEAR) && (lastbezt->ipo != BEZT_IPO_CONST) &&
2012                      !(fcu->flag & FCURVE_DISCRETE_VALUES) )
2013                 {
2014                         /* linear or bezier interpolation */
2015                         if (lastbezt->ipo == BEZT_IPO_LIN) {
2016                                 /* Use the next center point instead of our own handle for
2017                                  * linear interpolated extrapolate 
2018                                  */
2019                                 if (fcu->totvert == 1) {
2020                                         cvalue = lastbezt->vec[1][1];
2021                                 }
2022                                 else {
2023                                         prevbezt = lastbezt - 1;
2024                                         dx = evaltime - lastbezt->vec[1][0];
2025                                         fac = lastbezt->vec[1][0] - prevbezt->vec[1][0];
2026                                         
2027                                         /* prevent division by zero */
2028                                         if (fac) {
2029                                                 fac = (lastbezt->vec[1][1] - prevbezt->vec[1][1]) / fac;
2030                                                 cvalue = lastbezt->vec[1][1] + (fac * dx);
2031                                         }
2032                                         else {
2033                                                 cvalue = lastbezt->vec[1][1];
2034                                         }
2035                                 }
2036                         }
2037                         else {
2038                                 /* Use the gradient of the second handle (later) of last BezTriple to calculate the
2039                                  * gradient and thus the value of the curve at evaltime
2040                                  */
2041                                 dx = evaltime - lastbezt->vec[1][0];
2042                                 fac = lastbezt->vec[2][0] - lastbezt->vec[1][0];
2043                                 
2044                                 /* prevent division by zero */
2045                                 if (fac) {
2046                                         fac = (lastbezt->vec[2][1] - lastbezt->vec[1][1]) / fac;
2047                                         cvalue = lastbezt->vec[1][1] + (fac * dx);
2048                                 }
2049                                 else {
2050                                         cvalue = lastbezt->vec[1][1];
2051                                 }
2052                         }
2053                 }
2054                 else {
2055                         /* constant (BEZT_IPO_HORIZ) extrapolation or constant interpolation, 
2056                          * so just extend last keyframe's value 
2057                          */
2058                         cvalue = lastbezt->vec[1][1];
2059                 }
2060         }
2061         else {
2062                 /* evaltime occurs somewhere in the middle of the curve */
2063                 for (a = 0; prevbezt && bezt && (a < fcu->totvert - 1); a++, prevbezt = bezt, bezt++) {
2064                         /* use if the key is directly on the frame, rare cases this is needed else we get 0.0 instead. */
2065                         if (fabsf(bezt->vec[1][0] - evaltime) < SMALL_NUMBER) {
2066                                 cvalue = bezt->vec[1][1];
2067                         }
2068                         /* evaltime occurs within the interval defined by these two keyframes */
2069                         else if ((prevbezt->vec[1][0] <= evaltime) && (bezt->vec[1][0] >= evaltime)) {
2070                                 /* value depends on interpolation mode */
2071                                 if ((prevbezt->ipo == BEZT_IPO_CONST) || (fcu->flag & FCURVE_DISCRETE_VALUES)) {
2072                                         /* constant (evaltime not relevant, so no interpolation needed) */
2073                                         cvalue = prevbezt->vec[1][1];
2074                                 }
2075                                 else if (prevbezt->ipo == BEZT_IPO_LIN) {
2076                                         /* linear - interpolate between values of the two keyframes */
2077                                         fac = bezt->vec[1][0] - prevbezt->vec[1][0];
2078                                         
2079                                         /* prevent division by zero */
2080                                         if (fac) {
2081                                                 fac = (evaltime - prevbezt->vec[1][0]) / fac;
2082                                                 cvalue = prevbezt->vec[1][1] + (fac * (bezt->vec[1][1] - prevbezt->vec[1][1]));
2083                                         }
2084                                         else {
2085                                                 cvalue = prevbezt->vec[1][1];
2086                                         }
2087                                 }
2088                                 else {
2089                                         /* bezier interpolation */
2090                                         /* (v1, v2) are the first keyframe and its 2nd handle */
2091                                         v1[0] = prevbezt->vec[1][0];
2092                                         v1[1] = prevbezt->vec[1][1];
2093                                         v2[0] = prevbezt->vec[2][0];
2094                                         v2[1] = prevbezt->vec[2][1];
2095                                         /* (v3, v4) are the last keyframe's 1st handle + the last keyframe */
2096                                         v3[0] = bezt->vec[0][0];
2097                                         v3[1] = bezt->vec[0][1];
2098                                         v4[0] = bezt->vec[1][0];
2099                                         v4[1] = bezt->vec[1][1];
2100                                         
2101                                         /* adjust handles so that they don't overlap (forming a loop) */
2102                                         correct_bezpart(v1, v2, v3, v4);
2103                                         
2104                                         /* try to get a value for this position - if failure, try another set of points */
2105                                         b = findzero(evaltime, v1[0], v2[0], v3[0], v4[0], opl);
2106                                         if (b) {
2107                                                 berekeny(v1[1], v2[1], v3[1], v4[1], opl, 1);
2108                                                 cvalue = opl[0];
2109                                                 break;
2110                                         }
2111                                 }
2112                         }
2113                 }
2114         }
2115         
2116         /* return value */
2117         return cvalue;
2118 }
2119
2120 /* Calculate F-Curve value for 'evaltime' using FPoint samples */
2121 static float fcurve_eval_samples(FCurve *fcu, FPoint *fpts, float evaltime)
2122 {
2123         FPoint *prevfpt, *lastfpt, *fpt;
2124         float cvalue = 0.0f;
2125         
2126         /* get pointers */
2127         prevfpt = fpts;
2128         lastfpt = prevfpt + fcu->totvert - 1;
2129         
2130         /* evaluation time at or past endpoints? */
2131         if (prevfpt->vec[0] >= evaltime) {
2132                 /* before or on first sample, so just extend value */
2133                 cvalue = prevfpt->vec[1];
2134         }
2135         else if (lastfpt->vec[0] <= evaltime) {
2136                 /* after or on last sample, so just extend value */
2137                 cvalue = lastfpt->vec[1];
2138         }
2139         else {
2140                 float t = (float)abs(evaltime - (int)evaltime);
2141                 
2142                 /* find the one on the right frame (assume that these are spaced on 1-frame intervals) */
2143                 fpt = prevfpt + (int)(evaltime - prevfpt->vec[0]);
2144                 
2145                 /* if not exactly on the frame, perform linear interpolation with the next one */
2146                 if (t != 0.0f) 
2147                         cvalue = interpf(fpt->vec[1], (fpt + 1)->vec[1], t);
2148                 else
2149                         cvalue = fpt->vec[1];
2150         }
2151         
2152         /* return value */
2153         return cvalue;
2154 }
2155
2156 /* ***************************** F-Curve - Evaluation ********************************* */
2157
2158 /* Evaluate and return the value of the given F-Curve at the specified frame ("evaltime") 
2159  * Note: this is also used for drivers
2160  */
2161 float evaluate_fcurve(FCurve *fcu, float evaltime)
2162 {
2163         float cvalue = 0.0f;
2164         float devaltime;
2165         
2166         /* if there is a driver (only if this F-Curve is acting as 'driver'), evaluate it to find value to use as "evaltime" 
2167          * since drivers essentially act as alternative input (i.e. in place of 'time') for F-Curves
2168          *      - this value will also be returned as the value of the 'curve', if there are no keyframes
2169          */
2170         if (fcu->driver) {
2171                 /* evaltime now serves as input for the curve */
2172                 evaltime = cvalue = evaluate_driver(fcu->driver, evaltime);
2173         }
2174         
2175         /* evaluate modifiers which modify time to evaluate the base curve at */
2176         devaltime = evaluate_time_fmodifiers(&fcu->modifiers, fcu, cvalue, evaltime);
2177         
2178         /* evaluate curve-data 
2179          *      - 'devaltime' instead of 'evaltime', as this is the time that the last time-modifying 
2180          *        F-Curve modifier on the stack requested the curve to be evaluated at
2181          */
2182         if (fcu->bezt)
2183                 cvalue = fcurve_eval_keyframes(fcu, fcu->bezt, devaltime);
2184         else if (fcu->fpt)
2185                 cvalue = fcurve_eval_samples(fcu, fcu->fpt, devaltime);
2186         
2187         /* evaluate modifiers */
2188         evaluate_value_fmodifiers(&fcu->modifiers, fcu, &cvalue, evaltime);
2189         
2190         /* if curve can only have integral values, perform truncation (i.e. drop the decimal part)
2191          * here so that the curve can be sampled correctly
2192          */
2193         if (fcu->flag & FCURVE_INT_VALUES)
2194                 cvalue = floorf(cvalue + 0.5f);
2195         
2196         /* return evaluated value */
2197         return cvalue;
2198 }
2199
2200 /* Calculate the value of the given F-Curve at the given frame, and set its curval */
2201 void calculate_fcurve(FCurve *fcu, float ctime)
2202 {
2203         /* only calculate + set curval (overriding the existing value) if curve has 
2204          * any data which warrants this...
2205          */
2206         if ((fcu->totvert) || (fcu->driver && !(fcu->driver->flag & DRIVER_FLAG_INVALID)) ||
2207             list_has_suitable_fmodifier(&fcu->modifiers, 0, FMI_TYPE_GENERATE_CURVE))
2208         {
2209                 /* calculate and set curval (evaluates driver too if necessary) */
2210                 fcu->curval = evaluate_fcurve(fcu, ctime);
2211         }
2212 }
2213