doxygen: add newline after \file
[blender.git] / source / blender / blenkernel / intern / anim.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup bke
22  */
23
24 #include "MEM_guardedalloc.h"
25
26 #include <stdlib.h>
27
28 #include "BLI_listbase.h"
29 #include "BLI_math.h"
30 #include "BLI_dlrbTree.h"
31
32 #include "BLT_translation.h"
33
34 #include "DNA_anim_types.h"
35 #include "DNA_armature_types.h"
36 #include "DNA_key_types.h"
37 #include "DNA_scene_types.h"
38
39 #include "BKE_anim.h"
40 #include "BKE_animsys.h"
41 #include "BKE_action.h"
42 #include "BKE_curve.h"
43 #include "BKE_key.h"
44 #include "BKE_main.h"
45 #include "BKE_object.h"
46 #include "BKE_particle.h"
47 #include "BKE_scene.h"
48 #include "BKE_report.h"
49
50 #include "DEG_depsgraph.h"
51 #include "DEG_depsgraph_query.h"
52 #include "DEG_depsgraph_build.h"
53
54 #include "GPU_batch.h"
55
56 #include "CLG_log.h"
57
58 static CLG_LogRef LOG = {"bke.anim"};
59
60 // XXX bad level call...
61 extern short compare_ak_cfraPtr(void *node, void *data);
62 extern void agroup_to_keylist(struct AnimData *adt, struct bActionGroup *agrp, struct DLRBT_Tree *keys, int saction_flag);
63 extern void action_to_keylist(struct AnimData *adt, struct bAction *act, struct DLRBT_Tree *keys, int saction_flag);
64
65 /* --------------------- */
66 /* forward declarations */
67
68 /* ******************************************************************** */
69 /* Animation Visualization */
70
71 /* Initialize the default settings for animation visualization */
72 void animviz_settings_init(bAnimVizSettings *avs)
73 {
74         /* sanity check */
75         if (avs == NULL)
76                 return;
77
78         /* path settings */
79         avs->path_bc = avs->path_ac = 10;
80
81         avs->path_sf = 1; /* xxx - take from scene instead? */
82         avs->path_ef = 250; /* xxx - take from scene instead? */
83
84         avs->path_viewflag = (MOTIONPATH_VIEW_KFRAS | MOTIONPATH_VIEW_KFNOS);
85
86         avs->path_step = 1;
87
88         avs->path_bakeflag |= MOTIONPATH_BAKE_HEADS;
89 }
90
91 /* ------------------- */
92
93 /* Free the given motion path's cache */
94 void animviz_free_motionpath_cache(bMotionPath *mpath)
95 {
96         /* sanity check */
97         if (mpath == NULL)
98                 return;
99
100         /* free the path if necessary */
101         if (mpath->points)
102                 MEM_freeN(mpath->points);
103
104         GPU_VERTBUF_DISCARD_SAFE(mpath->points_vbo);
105         GPU_BATCH_DISCARD_SAFE(mpath->batch_line);
106         GPU_BATCH_DISCARD_SAFE(mpath->batch_points);
107
108         /* reset the relevant parameters */
109         mpath->points = NULL;
110         mpath->length = 0;
111 }
112
113 /* Free the given motion path instance and its data
114  * NOTE: this frees the motion path given!
115  */
116 void animviz_free_motionpath(bMotionPath *mpath)
117 {
118         /* sanity check */
119         if (mpath == NULL)
120                 return;
121
122         /* free the cache first */
123         animviz_free_motionpath_cache(mpath);
124
125         /* now the instance itself */
126         MEM_freeN(mpath);
127 }
128
129 /* ------------------- */
130
131 /* Make a copy of motionpath data, so that viewing with copy on write works */
132 bMotionPath *animviz_copy_motionpath(const bMotionPath *mpath_src)
133 {
134         bMotionPath *mpath_dst;
135
136         if (mpath_src == NULL)
137                 return NULL;
138
139         mpath_dst = MEM_dupallocN(mpath_src);
140         mpath_dst->points = MEM_dupallocN(mpath_src->points);
141
142         /* should get recreated on draw... */
143         mpath_dst->points_vbo = NULL;
144         mpath_dst->batch_line = NULL;
145         mpath_dst->batch_points = NULL;
146
147         return mpath_dst;
148 }
149
150 /* ------------------- */
151
152 /**
153  * Setup motion paths for the given data.
154  * \note Only used when explicitly calculating paths on bones which may/may not be consider already
155  *
156  * \param scene: Current scene (for frame ranges, etc.)
157  * \param ob: Object to add paths for (must be provided)
158  * \param pchan: Posechannel to add paths for (optional; if not provided, object-paths are assumed)
159  */
160 bMotionPath *animviz_verify_motionpaths(ReportList *reports, Scene *scene, Object *ob, bPoseChannel *pchan)
161 {
162         bAnimVizSettings *avs;
163         bMotionPath *mpath, **dst;
164
165         /* sanity checks */
166         if (ELEM(NULL, scene, ob))
167                 return NULL;
168
169         /* get destination data */
170         if (pchan) {
171                 /* paths for posechannel - assume that posechannel belongs to the object */
172                 avs = &ob->pose->avs;
173                 dst = &pchan->mpath;
174         }
175         else {
176                 /* paths for object */
177                 avs = &ob->avs;
178                 dst = &ob->mpath;
179         }
180
181         /* avoid 0 size allocs */
182         if (avs->path_sf >= avs->path_ef) {
183                 BKE_reportf(reports, RPT_ERROR,
184                             "Motion path frame extents invalid for %s (%d to %d)%s",
185                             (pchan) ? pchan->name : ob->id.name,
186                             avs->path_sf, avs->path_ef,
187                             (avs->path_sf == avs->path_ef) ? TIP_(", cannot have single-frame paths") : "");
188                 return NULL;
189         }
190
191         /* if there is already a motionpath, just return that,
192          * provided it's settings are ok (saves extra free+alloc)
193          */
194         if (*dst != NULL) {
195                 int expected_length = avs->path_ef - avs->path_sf;
196
197                 mpath = *dst;
198
199                 /* path is "valid" if length is valid, but must also be of the same length as is being requested */
200                 if ((mpath->start_frame != mpath->end_frame) && (mpath->length > 0)) {
201                         /* outer check ensures that we have some curve data for this path */
202                         if (mpath->length == expected_length) {
203                                 /* return/use this as it is already valid length */
204                                 return mpath;
205                         }
206                         else {
207                                 /* clear the existing path (as the range has changed), and reallocate below */
208                                 animviz_free_motionpath_cache(mpath);
209                         }
210                 }
211         }
212         else {
213                 /* create a new motionpath, and assign it */
214                 mpath = MEM_callocN(sizeof(bMotionPath), "bMotionPath");
215                 *dst = mpath;
216         }
217
218         /* set settings from the viz settings */
219         mpath->start_frame = avs->path_sf;
220         mpath->end_frame = avs->path_ef;
221
222         mpath->length = mpath->end_frame - mpath->start_frame;
223
224         if (avs->path_bakeflag & MOTIONPATH_BAKE_HEADS)
225                 mpath->flag |= MOTIONPATH_FLAG_BHEAD;
226         else
227                 mpath->flag &= ~MOTIONPATH_FLAG_BHEAD;
228
229         /* set default custom values */
230         mpath->color[0] = 1.0;    /* Red */
231         mpath->color[1] = 0.0;
232         mpath->color[2] = 0.0;
233
234         mpath->line_thickness = 2;
235         mpath->flag |= MOTIONPATH_FLAG_LINES;  /* draw lines by default */
236
237         /* allocate a cache */
238         mpath->points = MEM_callocN(sizeof(bMotionPathVert) * mpath->length, "bMotionPathVerts");
239
240         /* tag viz settings as currently having some path(s) which use it */
241         avs->path_bakeflag |= MOTIONPATH_BAKE_HAS_PATHS;
242
243         /* return it */
244         return mpath;
245 }
246
247 /* ------------------- */
248
249 /* Motion path needing to be baked (mpt) */
250 typedef struct MPathTarget {
251         struct MPathTarget *next, *prev;
252
253         bMotionPath *mpath;         /* motion path in question */
254
255         DLRBT_Tree keys;         /* temp, to know where the keyframes are */
256
257         /* Original (Source Objects) */
258         Object *ob;                 /* source object */
259         bPoseChannel *pchan;        /* source posechannel (if applicable) */
260
261         /* "Evaluated" Copies (these come from the background COW copie
262          * that provide all the coordinates we want to save off)
263          */
264         Object *ob_eval;             /* evaluated object */
265 } MPathTarget;
266
267 /* ........ */
268
269 /* get list of motion paths to be baked for the given object
270  * - assumes the given list is ready to be used
271  */
272 /* TODO: it would be nice in future to be able to update objects dependent on these bones too? */
273 void animviz_get_object_motionpaths(Object *ob, ListBase *targets)
274 {
275         MPathTarget *mpt;
276
277         /* object itself first */
278         if ((ob->avs.recalc & ANIMVIZ_RECALC_PATHS) && (ob->mpath)) {
279                 /* new target for object */
280                 mpt = MEM_callocN(sizeof(MPathTarget), "MPathTarget Ob");
281                 BLI_addtail(targets, mpt);
282
283                 mpt->mpath = ob->mpath;
284                 mpt->ob = ob;
285         }
286
287         /* bones */
288         if ((ob->pose) && (ob->pose->avs.recalc & ANIMVIZ_RECALC_PATHS)) {
289                 bArmature *arm = ob->data;
290                 bPoseChannel *pchan;
291
292                 for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) {
293                         if ((pchan->bone) && (arm->layer & pchan->bone->layer) && (pchan->mpath)) {
294                                 /* new target for bone */
295                                 mpt = MEM_callocN(sizeof(MPathTarget), "MPathTarget PoseBone");
296                                 BLI_addtail(targets, mpt);
297
298                                 mpt->mpath = pchan->mpath;
299                                 mpt->ob = ob;
300                                 mpt->pchan = pchan;
301                         }
302                 }
303         }
304 }
305
306 /* ........ */
307
308 /* update scene for current frame */
309 static void motionpaths_calc_update_scene(Main *bmain,
310                                           struct Depsgraph *depsgraph)
311 {
312         /* Do all updates
313          *  - if this is too slow, resort to using a more efficient way
314          *    that doesn't force complete update, but for now, this is the
315          *    most accurate way!
316          *
317          * TODO(segey): Bring back partial updates, which became impossible
318          * with the new depsgraph due to unsorted nature of bases.
319          *
320          * TODO(sergey): Use evaluation context dedicated to motion paths.
321          */
322         BKE_scene_graph_update_for_newframe(depsgraph, bmain);
323 }
324
325 /* ........ */
326
327 /* perform baking for the targets on the current frame */
328 static void motionpaths_calc_bake_targets(ListBase *targets, int cframe)
329 {
330         MPathTarget *mpt;
331
332         /* for each target, check if it can be baked on the current frame */
333         for (mpt = targets->first; mpt; mpt = mpt->next) {
334                 bMotionPath *mpath = mpt->mpath;
335
336                 /* current frame must be within the range the cache works for
337                  * - is inclusive of the first frame, but not the last otherwise we get buffer overruns
338                  */
339                 if ((cframe < mpath->start_frame) || (cframe >= mpath->end_frame)) {
340                         continue;
341                 }
342
343                 /* get the relevant cache vert to write to */
344                 bMotionPathVert *mpv = mpath->points + (cframe - mpath->start_frame);
345
346                 Object *ob_eval = mpt->ob_eval;
347
348                 /* Lookup evaluated pose channel, here because the depsgraph
349                  * evaluation can change them so they are not cached in mpt. */
350                 bPoseChannel *pchan_eval = NULL;
351                 if (mpt->pchan) {
352                         pchan_eval = BKE_pose_channel_find_name(ob_eval->pose, mpt->pchan->name);
353                 }
354
355                 /* pose-channel or object path baking? */
356                 if (pchan_eval) {
357                         /* heads or tails */
358                         if (mpath->flag & MOTIONPATH_FLAG_BHEAD) {
359                                 copy_v3_v3(mpv->co, pchan_eval->pose_head);
360                         }
361                         else {
362                                 copy_v3_v3(mpv->co, pchan_eval->pose_tail);
363                         }
364
365                         /* result must be in worldspace */
366                         mul_m4_v3(ob_eval->obmat, mpv->co);
367                 }
368                 else {
369                         /* worldspace object location */
370                         copy_v3_v3(mpv->co, ob_eval->obmat[3]);
371                 }
372
373                 float mframe = (float)(cframe);
374
375                 /* Tag if it's a keyframe */
376                 if (BLI_dlrbTree_search_exact(&mpt->keys, compare_ak_cfraPtr, &mframe)) {
377                         mpv->flag |= MOTIONPATH_VERT_KEY;
378                 }
379
380                 /* Incremental update on evaluated object if possible, for fast updating
381                  * while dragging in transform. */
382                 bMotionPath *mpath_eval = NULL;
383                 if (mpt->pchan) {
384                         mpath_eval = (pchan_eval) ? pchan_eval->mpath : NULL;
385                 }
386                 else {
387                         mpath_eval = ob_eval->mpath;
388                 }
389
390                 if (mpath_eval && mpath_eval->length == mpath->length) {
391                         bMotionPathVert *mpv_eval = mpath_eval->points + (cframe - mpath_eval->start_frame);
392                         *mpv_eval = *mpv;
393
394                         GPU_VERTBUF_DISCARD_SAFE(mpath_eval->points_vbo);
395                         GPU_BATCH_DISCARD_SAFE(mpath_eval->batch_line);
396                         GPU_BATCH_DISCARD_SAFE(mpath_eval->batch_points);
397                 }
398         }
399 }
400
401 /* Perform baking of the given object's and/or its bones' transforms to motion paths
402  * - scene: current scene
403  * - ob: object whose flagged motionpaths should get calculated
404  * - recalc: whether we need to
405  */
406 /* TODO: include reports pointer? */
407 void animviz_calc_motionpaths(Depsgraph *depsgraph,
408                               Main *bmain,
409                               Scene *scene,
410                               ListBase *targets,
411                               bool restore,
412                               bool current_frame_only)
413 {
414         /* sanity check */
415         if (ELEM(NULL, targets, targets->first))
416                 return;
417
418         /* Compute frame range to bake within.
419          * TODO: this method could be improved...
420          * 1) max range for standard baking
421          * 2) minimum range for recalc baking (i.e. between keyframes, but how?) */
422         int sfra = INT_MAX;
423         int efra = INT_MIN;
424
425         for (MPathTarget *mpt = targets->first; mpt; mpt = mpt->next) {
426                 /* try to increase area to do (only as much as needed) */
427                 sfra = MIN2(sfra, mpt->mpath->start_frame);
428                 efra = MAX2(efra, mpt->mpath->end_frame);
429         }
430
431         if (efra <= sfra) {
432                 return;
433         }
434
435         /* Limit frame range if we are updating just the current frame. */
436         /* set frame values */
437         int cfra = CFRA;
438         if (current_frame_only) {
439                 if (cfra < sfra || cfra > efra) {
440                         return;
441                 }
442                 sfra = efra = cfra;
443         }
444
445         /* get copies of objects/bones to get the calculated results from
446          * (for copy-on-write evaluation), so that we actually get some results
447          */
448         // TODO: Create a copy of background depsgraph that only contain these entities, and only evaluates them..
449         for (MPathTarget *mpt = targets->first; mpt; mpt = mpt->next) {
450                 mpt->ob_eval = DEG_get_evaluated_object(depsgraph, mpt->ob);
451
452                 AnimData *adt = BKE_animdata_from_id(&mpt->ob_eval->id);
453
454                 /* build list of all keyframes in active action for object or pchan */
455                 BLI_dlrbTree_init(&mpt->keys);
456
457                 if (adt) {
458                         bAnimVizSettings *avs;
459
460                         /* get pointer to animviz settings for each target */
461                         if (mpt->pchan)
462                                 avs = &mpt->ob->pose->avs;
463                         else
464                                 avs = &mpt->ob->avs;
465
466                         /* it is assumed that keyframes for bones are all grouped in a single group
467                          * unless an option is set to always use the whole action
468                          */
469                         if ((mpt->pchan) && (avs->path_viewflag & MOTIONPATH_VIEW_KFACT) == 0) {
470                                 bActionGroup *agrp = BKE_action_group_find_name(adt->action, mpt->pchan->name);
471
472                                 if (agrp) {
473                                         agroup_to_keylist(adt, agrp, &mpt->keys, 0);
474                                 }
475                         }
476                         else {
477                                 action_to_keylist(adt, adt->action, &mpt->keys, 0);
478                         }
479                 }
480         }
481
482         /* calculate path over requested range */
483         CLOG_INFO(&LOG, 1, "Calculating MotionPaths between frames %d - %d (%d frames)", sfra, efra, efra - sfra + 1);
484         for (CFRA = sfra; CFRA <= efra; CFRA++) {
485                 if (current_frame_only) {
486                         /* For current frame, only update tagged. */
487                         BKE_scene_graph_update_tagged(depsgraph, bmain);
488                 }
489                 else {
490                         /* Update relevant data for new frame. */
491                         motionpaths_calc_update_scene(bmain, depsgraph);
492                 }
493
494                 /* perform baking for targets */
495                 motionpaths_calc_bake_targets(targets, CFRA);
496         }
497
498         /* reset original environment */
499         /* NOTE: We don't always need to reevaluate the main scene, as the depsgraph
500          * may be a temporary one that works on a subset of the data. We always have
501          * to resoture the current frame though. */
502         CFRA = cfra;
503         if (!current_frame_only && restore) {
504                 motionpaths_calc_update_scene(bmain, depsgraph);
505         }
506
507         /* clear recalc flags from targets */
508         for (MPathTarget *mpt = targets->first; mpt; mpt = mpt->next) {
509                 bAnimVizSettings *avs;
510                 bMotionPath *mpath = mpt->mpath;
511
512                 /* get pointer to animviz settings for each target */
513                 if (mpt->pchan)
514                         avs = &mpt->ob->pose->avs;
515                 else
516                         avs = &mpt->ob->avs;
517
518                 /* clear the flag requesting recalculation of targets */
519                 avs->recalc &= ~ANIMVIZ_RECALC_PATHS;
520
521                 /* Clean temp data */
522                 BLI_dlrbTree_free(&mpt->keys);
523
524                 /* Free previous batches to force update. */
525                 GPU_VERTBUF_DISCARD_SAFE(mpath->points_vbo);
526                 GPU_BATCH_DISCARD_SAFE(mpath->batch_line);
527                 GPU_BATCH_DISCARD_SAFE(mpath->batch_points);
528         }
529 }
530
531 /* ******************************************************************** */
532 /* Curve Paths - for curve deforms and/or curve following */
533
534 /* free curve path data
535  * NOTE: frees the path itself!
536  * NOTE: this is increasingly inaccurate with non-uniform BevPoint subdivisions [#24633]
537  */
538 void free_path(Path *path)
539 {
540         if (path->data) MEM_freeN(path->data);
541         MEM_freeN(path);
542 }
543
544 /* calculate a curve-deform path for a curve
545  * - only called from displist.c -> do_makeDispListCurveTypes
546  */
547 void calc_curvepath(Object *ob, ListBase *nurbs)
548 {
549         BevList *bl;
550         BevPoint *bevp, *bevpn, *bevpfirst, *bevplast;
551         PathPoint *pp;
552         Nurb *nu;
553         Path *path;
554         float *fp, *dist, *maxdist, xyz[3];
555         float fac, d = 0, fac1, fac2;
556         int a, tot, cycl = 0;
557
558         /* in a path vertices are with equal differences: path->len = number of verts */
559         /* NOW WITH BEVELCURVE!!! */
560
561         if (ob == NULL || ob->type != OB_CURVE) {
562                 return;
563         }
564
565         if (ob->runtime.curve_cache->path) free_path(ob->runtime.curve_cache->path);
566         ob->runtime.curve_cache->path = NULL;
567
568         /* weak! can only use first curve */
569         bl = ob->runtime.curve_cache->bev.first;
570         if (bl == NULL || !bl->nr) {
571                 return;
572         }
573
574         nu = nurbs->first;
575
576         ob->runtime.curve_cache->path = path = MEM_callocN(sizeof(Path), "calc_curvepath");
577
578         /* if POLY: last vertice != first vertice */
579         cycl = (bl->poly != -1);
580
581         tot = cycl ? bl->nr : bl->nr - 1;
582
583         path->len = tot + 1;
584         /* exception: vector handle paths and polygon paths should be subdivided at least a factor resolu */
585         if (path->len < nu->resolu * SEGMENTSU(nu)) {
586                 path->len = nu->resolu * SEGMENTSU(nu);
587         }
588
589         dist = (float *)MEM_mallocN(sizeof(float) * (tot + 1), "calcpathdist");
590
591         /* all lengths in *dist */
592         bevp = bevpfirst = bl->bevpoints;
593         fp = dist;
594         *fp = 0.0f;
595         for (a = 0; a < tot; a++) {
596                 fp++;
597                 if (cycl && a == tot - 1)
598                         sub_v3_v3v3(xyz, bevpfirst->vec, bevp->vec);
599                 else
600                         sub_v3_v3v3(xyz, (bevp + 1)->vec, bevp->vec);
601
602                 *fp = *(fp - 1) + len_v3(xyz);
603                 bevp++;
604         }
605
606         path->totdist = *fp;
607
608         /* the path verts  in path->data */
609         /* now also with TILT value */
610         pp = path->data = (PathPoint *)MEM_callocN(sizeof(PathPoint) * path->len, "pathdata");
611
612         bevp = bevpfirst;
613         bevpn = bevp + 1;
614         bevplast = bevpfirst + (bl->nr - 1);
615         if (UNLIKELY(bevpn > bevplast)) {
616                 bevpn = cycl ? bevpfirst : bevplast;
617         }
618         fp = dist + 1;
619         maxdist = dist + tot;
620         fac = 1.0f / ((float)path->len - 1.0f);
621         fac = fac * path->totdist;
622
623         for (a = 0; a < path->len; a++) {
624
625                 d = ((float)a) * fac;
626
627                 /* we're looking for location (distance) 'd' in the array */
628                 if (LIKELY(tot > 0)) {
629                         while ((fp < maxdist) && (d >= *fp)) {
630                                 fp++;
631                                 if (bevp < bevplast) bevp++;
632                                 bevpn = bevp + 1;
633                                 if (UNLIKELY(bevpn > bevplast)) {
634                                         bevpn = cycl ? bevpfirst : bevplast;
635                                 }
636                         }
637
638                         fac1 = (*(fp) - d) / (*(fp) - *(fp - 1));
639                         fac2 = 1.0f - fac1;
640                 }
641                 else {
642                         fac1 = 1.0f;
643                         fac2 = 0.0f;
644                 }
645
646                 interp_v3_v3v3(pp->vec, bevp->vec, bevpn->vec, fac2);
647                 pp->vec[3] = fac1 * bevp->alfa   + fac2 * bevpn->alfa;
648                 pp->radius = fac1 * bevp->radius + fac2 * bevpn->radius;
649                 pp->weight = fac1 * bevp->weight + fac2 * bevpn->weight;
650                 interp_qt_qtqt(pp->quat, bevp->quat, bevpn->quat, fac2);
651                 normalize_qt(pp->quat);
652
653                 pp++;
654         }
655
656         MEM_freeN(dist);
657 }
658
659 static int interval_test(const int min, const int max, int p1, const int cycl)
660 {
661         if (cycl) {
662                 p1 = mod_i(p1 - min, (max - min + 1)) + min;
663         }
664         else {
665                 if      (p1 < min) p1 = min;
666                 else if (p1 > max) p1 = max;
667         }
668         return p1;
669 }
670
671
672 /* calculate the deformation implied by the curve path at a given parametric position,
673  * and returns whether this operation succeeded.
674  *
675  * note: ctime is normalized range <0-1>
676  *
677  * returns OK: 1/0
678  */
679 int where_on_path(Object *ob, float ctime, float vec[4], float dir[3], float quat[4], float *radius, float *weight)
680 {
681         Curve *cu;
682         Nurb *nu;
683         BevList *bl;
684         Path *path;
685         PathPoint *pp, *p0, *p1, *p2, *p3;
686         float fac;
687         float data[4];
688         int cycl = 0, s0, s1, s2, s3;
689         ListBase *nurbs;
690
691         if (ob == NULL || ob->type != OB_CURVE) return 0;
692         cu = ob->data;
693         if (ob->runtime.curve_cache == NULL || ob->runtime.curve_cache->path == NULL || ob->runtime.curve_cache->path->data == NULL) {
694                 CLOG_WARN(&LOG, "no path!");
695                 return 0;
696         }
697         path = ob->runtime.curve_cache->path;
698         pp = path->data;
699
700         /* test for cyclic */
701         bl = ob->runtime.curve_cache->bev.first;
702         if (!bl) return 0;
703         if (!bl->nr) return 0;
704         if (bl->poly > -1) cycl = 1;
705
706         /* values below zero for non-cyclic curves give strange results */
707         BLI_assert(cycl || ctime >= 0.0f);
708
709         ctime *= (path->len - 1);
710
711         s1 = (int)floor(ctime);
712         fac = (float)(s1 + 1) - ctime;
713
714         /* path->len is corrected for cyclic */
715         s0 = interval_test(0, path->len - 1 - cycl, s1 - 1, cycl);
716         s1 = interval_test(0, path->len - 1 - cycl, s1, cycl);
717         s2 = interval_test(0, path->len - 1 - cycl, s1 + 1, cycl);
718         s3 = interval_test(0, path->len - 1 - cycl, s1 + 2, cycl);
719
720         p0 = pp + s0;
721         p1 = pp + s1;
722         p2 = pp + s2;
723         p3 = pp + s3;
724
725         /* NOTE: commented out for follow constraint
726          *
727          *       If it's ever be uncommented watch out for curve_deform_verts()
728          *       which used to temporary set CU_FOLLOW flag for the curve and no
729          *       longer does it (because of threading issues of such a thing.
730          */
731         //if (cu->flag & CU_FOLLOW) {
732
733         key_curve_tangent_weights(1.0f - fac, data, KEY_BSPLINE);
734
735         interp_v3_v3v3v3v3(dir, p0->vec, p1->vec, p2->vec, p3->vec, data);
736
737         /* make compatible with vectoquat */
738         negate_v3(dir);
739         //}
740
741         nurbs = BKE_curve_editNurbs_get(cu);
742         if (!nurbs)
743                 nurbs = &cu->nurb;
744         nu = nurbs->first;
745
746         /* make sure that first and last frame are included in the vectors here  */
747         if (nu->type == CU_POLY) key_curve_position_weights(1.0f - fac, data, KEY_LINEAR);
748         else if (nu->type == CU_BEZIER) key_curve_position_weights(1.0f - fac, data, KEY_LINEAR);
749         else if (s0 == s1 || p2 == p3) key_curve_position_weights(1.0f - fac, data, KEY_CARDINAL);
750         else key_curve_position_weights(1.0f - fac, data, KEY_BSPLINE);
751
752         vec[0] = data[0] * p0->vec[0] + data[1] * p1->vec[0] + data[2] * p2->vec[0] + data[3] * p3->vec[0]; /* X */
753         vec[1] = data[0] * p0->vec[1] + data[1] * p1->vec[1] + data[2] * p2->vec[1] + data[3] * p3->vec[1]; /* Y */
754         vec[2] = data[0] * p0->vec[2] + data[1] * p1->vec[2] + data[2] * p2->vec[2] + data[3] * p3->vec[2]; /* Z */
755         vec[3] = data[0] * p0->vec[3] + data[1] * p1->vec[3] + data[2] * p2->vec[3] + data[3] * p3->vec[3]; /* Tilt, should not be needed since we have quat still used */
756
757         if (quat) {
758                 float totfac, q1[4], q2[4];
759
760                 totfac = data[0] + data[3];
761                 if (totfac > FLT_EPSILON) interp_qt_qtqt(q1, p0->quat, p3->quat, data[3] / totfac);
762                 else copy_qt_qt(q1, p1->quat);
763
764                 totfac = data[1] + data[2];
765                 if (totfac > FLT_EPSILON) interp_qt_qtqt(q2, p1->quat, p2->quat, data[2] / totfac);
766                 else copy_qt_qt(q2, p3->quat);
767
768                 totfac = data[0] + data[1] + data[2] + data[3];
769                 if (totfac > FLT_EPSILON) interp_qt_qtqt(quat, q1, q2, (data[1] + data[2]) / totfac);
770                 else copy_qt_qt(quat, q2);
771         }
772
773         if (radius)
774                 *radius = data[0] * p0->radius + data[1] * p1->radius + data[2] * p2->radius + data[3] * p3->radius;
775
776         if (weight)
777                 *weight = data[0] * p0->weight + data[1] * p1->weight + data[2] * p2->weight + data[3] * p3->weight;
778
779         return 1;
780 }