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
17 /** \file
18 * \ingroup bke
19 */
20
21 #include "MEM_guardedalloc.h"
22
23 #include <stdlib.h>
24
25 #include "BLI_dlrbTree.h"
26 #include "BLI_listbase.h"
27 #include "BLI_math.h"
28
29 #include "DNA_anim_types.h"
30 #include "DNA_armature_types.h"
31 #include "DNA_scene_types.h"
32
33 #include "BKE_action.h"
34 #include "BKE_anim_data.h"
35 #include "BKE_main.h"
36 #include "BKE_scene.h"
37
38 #include "DEG_depsgraph.h"
39 #include "DEG_depsgraph_build.h"
40 #include "DEG_depsgraph_query.h"
41
42 #include "GPU_batch.h"
43 #include "GPU_vertex_buffer.h"
44
45 #include "ED_anim_api.h"
46 #include "ED_keyframes_draw.h"
47
48 #include "CLG_log.h"
49
50 static CLG_LogRef LOG = {"ed.anim.motion_paths"};
51
52 /* Motion path needing to be baked (mpt) */
53 typedef struct MPathTarget {
54 struct MPathTarget *next, *prev;
55
56 bMotionPath *mpath; /* motion path in question */
57
58 DLRBT_Tree keys; /* temp, to know where the keyframes are */
59
60 /* Original (Source Objects) */
61 Object *ob; /* source object */
62 bPoseChannel *pchan; /* source posechannel (if applicable) */
63
64 /* "Evaluated" Copies (these come from the background COW copy
65 * that provide all the coordinates we want to save off). */
66 Object *ob_eval; /* evaluated object */
67 } MPathTarget;
68
69 /* ........ */
70
71 /* update scene for current frame */
motionpaths_calc_update_scene(struct Depsgraph * depsgraph)72 static void motionpaths_calc_update_scene(struct Depsgraph *depsgraph)
73 {
74 BKE_scene_graph_update_for_newframe(depsgraph);
75 }
76
animviz_depsgraph_build(Main * bmain,Scene * scene,ViewLayer * view_layer,ListBase * targets)77 Depsgraph *animviz_depsgraph_build(Main *bmain,
78 Scene *scene,
79 ViewLayer *view_layer,
80 ListBase *targets)
81 {
82 /* Allocate dependency graph. */
83 Depsgraph *depsgraph = DEG_graph_new(bmain, scene, view_layer, DAG_EVAL_VIEWPORT);
84
85 /* Make a flat array of IDs for the DEG API. */
86 const int num_ids = BLI_listbase_count(targets);
87 ID **ids = MEM_malloc_arrayN(sizeof(ID *), num_ids, "animviz IDS");
88 int current_id_index = 0;
89 for (MPathTarget *mpt = targets->first; mpt != NULL; mpt = mpt->next) {
90 ids[current_id_index++] = &mpt->ob->id;
91 }
92
93 /* Build graph from all requested IDs. */
94 DEG_graph_build_from_ids(depsgraph, ids, num_ids);
95 MEM_freeN(ids);
96
97 /* Update once so we can access pointers of evaluated animation data. */
98 motionpaths_calc_update_scene(depsgraph);
99 return depsgraph;
100 }
101
102 /* get list of motion paths to be baked for the given object
103 * - assumes the given list is ready to be used
104 */
105 /* TODO: it would be nice in future to be able to update objects dependent on these bones too? */
animviz_get_object_motionpaths(Object * ob,ListBase * targets)106 void animviz_get_object_motionpaths(Object *ob, ListBase *targets)
107 {
108 MPathTarget *mpt;
109
110 /* object itself first */
111 if ((ob->avs.recalc & ANIMVIZ_RECALC_PATHS) && (ob->mpath)) {
112 /* new target for object */
113 mpt = MEM_callocN(sizeof(MPathTarget), "MPathTarget Ob");
114 BLI_addtail(targets, mpt);
115
116 mpt->mpath = ob->mpath;
117 mpt->ob = ob;
118 }
119
120 /* bones */
121 if ((ob->pose) && (ob->pose->avs.recalc & ANIMVIZ_RECALC_PATHS)) {
122 bArmature *arm = ob->data;
123 bPoseChannel *pchan;
124
125 for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next) {
126 if ((pchan->bone) && (arm->layer & pchan->bone->layer) && (pchan->mpath)) {
127 /* new target for bone */
128 mpt = MEM_callocN(sizeof(MPathTarget), "MPathTarget PoseBone");
129 BLI_addtail(targets, mpt);
130
131 mpt->mpath = pchan->mpath;
132 mpt->ob = ob;
133 mpt->pchan = pchan;
134 }
135 }
136 }
137 }
138
139 /* ........ */
140
141 /* perform baking for the targets on the current frame */
motionpaths_calc_bake_targets(ListBase * targets,int cframe)142 static void motionpaths_calc_bake_targets(ListBase *targets, int cframe)
143 {
144 MPathTarget *mpt;
145
146 /* for each target, check if it can be baked on the current frame */
147 for (mpt = targets->first; mpt; mpt = mpt->next) {
148 bMotionPath *mpath = mpt->mpath;
149
150 /* current frame must be within the range the cache works for
151 * - is inclusive of the first frame, but not the last otherwise we get buffer overruns
152 */
153 if ((cframe < mpath->start_frame) || (cframe >= mpath->end_frame)) {
154 continue;
155 }
156
157 /* get the relevant cache vert to write to */
158 bMotionPathVert *mpv = mpath->points + (cframe - mpath->start_frame);
159
160 Object *ob_eval = mpt->ob_eval;
161
162 /* Lookup evaluated pose channel, here because the depsgraph
163 * evaluation can change them so they are not cached in mpt. */
164 bPoseChannel *pchan_eval = NULL;
165 if (mpt->pchan) {
166 pchan_eval = BKE_pose_channel_find_name(ob_eval->pose, mpt->pchan->name);
167 }
168
169 /* pose-channel or object path baking? */
170 if (pchan_eval) {
171 /* heads or tails */
172 if (mpath->flag & MOTIONPATH_FLAG_BHEAD) {
173 copy_v3_v3(mpv->co, pchan_eval->pose_head);
174 }
175 else {
176 copy_v3_v3(mpv->co, pchan_eval->pose_tail);
177 }
178
179 /* result must be in worldspace */
180 mul_m4_v3(ob_eval->obmat, mpv->co);
181 }
182 else {
183 /* worldspace object location */
184 copy_v3_v3(mpv->co, ob_eval->obmat[3]);
185 }
186
187 float mframe = (float)(cframe);
188
189 /* Tag if it's a keyframe */
190 if (BLI_dlrbTree_search_exact(&mpt->keys, compare_ak_cfraPtr, &mframe)) {
191 mpv->flag |= MOTIONPATH_VERT_KEY;
192 }
193 else {
194 mpv->flag &= ~MOTIONPATH_VERT_KEY;
195 }
196
197 /* Incremental update on evaluated object if possible, for fast updating
198 * while dragging in transform. */
199 bMotionPath *mpath_eval = NULL;
200 if (mpt->pchan) {
201 mpath_eval = (pchan_eval) ? pchan_eval->mpath : NULL;
202 }
203 else {
204 mpath_eval = ob_eval->mpath;
205 }
206
207 if (mpath_eval && mpath_eval->length == mpath->length) {
208 bMotionPathVert *mpv_eval = mpath_eval->points + (cframe - mpath_eval->start_frame);
209 *mpv_eval = *mpv;
210
211 GPU_VERTBUF_DISCARD_SAFE(mpath_eval->points_vbo);
212 GPU_BATCH_DISCARD_SAFE(mpath_eval->batch_line);
213 GPU_BATCH_DISCARD_SAFE(mpath_eval->batch_points);
214 }
215 }
216 }
217
218 /* Get pointer to animviz settings for the given target. */
animviz_target_settings_get(MPathTarget * mpt)219 static bAnimVizSettings *animviz_target_settings_get(MPathTarget *mpt)
220 {
221 if (mpt->pchan != NULL) {
222 return &mpt->ob->pose->avs;
223 }
224 return &mpt->ob->avs;
225 }
226
motionpath_get_global_framerange(ListBase * targets,int * r_sfra,int * r_efra)227 static void motionpath_get_global_framerange(ListBase *targets, int *r_sfra, int *r_efra)
228 {
229 *r_sfra = INT_MAX;
230 *r_efra = INT_MIN;
231 LISTBASE_FOREACH (MPathTarget *, mpt, targets) {
232 *r_sfra = min_ii(*r_sfra, mpt->mpath->start_frame);
233 *r_efra = max_ii(*r_efra, mpt->mpath->end_frame);
234 }
235 }
236
motionpath_get_prev_keyframe(MPathTarget * mpt,DLRBT_Tree * fcu_keys,int current_frame)237 static int motionpath_get_prev_keyframe(MPathTarget *mpt, DLRBT_Tree *fcu_keys, int current_frame)
238 {
239 if (current_frame <= mpt->mpath->start_frame) {
240 return mpt->mpath->start_frame;
241 }
242
243 float current_frame_float = current_frame;
244 DLRBT_Node *node = BLI_dlrbTree_search_prev(fcu_keys, compare_ak_cfraPtr, ¤t_frame_float);
245 if (node == NULL) {
246 return mpt->mpath->start_frame;
247 }
248
249 ActKeyColumn *key_data = (ActKeyColumn *)node;
250 return key_data->cfra;
251 }
252
motionpath_get_prev_prev_keyframe(MPathTarget * mpt,DLRBT_Tree * fcu_keys,int current_frame)253 static int motionpath_get_prev_prev_keyframe(MPathTarget *mpt,
254 DLRBT_Tree *fcu_keys,
255 int current_frame)
256 {
257 int frame = motionpath_get_prev_keyframe(mpt, fcu_keys, current_frame);
258 return motionpath_get_prev_keyframe(mpt, fcu_keys, frame);
259 }
260
motionpath_get_next_keyframe(MPathTarget * mpt,DLRBT_Tree * fcu_keys,int current_frame)261 static int motionpath_get_next_keyframe(MPathTarget *mpt, DLRBT_Tree *fcu_keys, int current_frame)
262 {
263 if (current_frame >= mpt->mpath->end_frame) {
264 return mpt->mpath->end_frame;
265 }
266
267 float current_frame_float = current_frame;
268 DLRBT_Node *node = BLI_dlrbTree_search_next(fcu_keys, compare_ak_cfraPtr, ¤t_frame_float);
269 if (node == NULL) {
270 return mpt->mpath->end_frame;
271 }
272
273 ActKeyColumn *key_data = (ActKeyColumn *)node;
274 return key_data->cfra;
275 }
276
motionpath_get_next_next_keyframe(MPathTarget * mpt,DLRBT_Tree * fcu_keys,int current_frame)277 static int motionpath_get_next_next_keyframe(MPathTarget *mpt,
278 DLRBT_Tree *fcu_keys,
279 int current_frame)
280 {
281 int frame = motionpath_get_next_keyframe(mpt, fcu_keys, current_frame);
282 return motionpath_get_next_keyframe(mpt, fcu_keys, frame);
283 }
284
motionpath_check_can_use_keyframe_range(MPathTarget * UNUSED (mpt),AnimData * adt,ListBase * fcurve_list)285 static bool motionpath_check_can_use_keyframe_range(MPathTarget *UNUSED(mpt),
286 AnimData *adt,
287 ListBase *fcurve_list)
288 {
289 if (adt == NULL || fcurve_list == NULL) {
290 return false;
291 }
292 /* NOTE: We might needed to do a full frame range update if there is a specific setup of NLA
293 * or drivers or modifiers on the f-curves. */
294 return true;
295 }
296
motionpath_calculate_update_range(MPathTarget * mpt,AnimData * adt,ListBase * fcurve_list,int current_frame,int * r_sfra,int * r_efra)297 static void motionpath_calculate_update_range(MPathTarget *mpt,
298 AnimData *adt,
299 ListBase *fcurve_list,
300 int current_frame,
301 int *r_sfra,
302 int *r_efra)
303 {
304 *r_sfra = INT_MAX;
305 *r_efra = INT_MIN;
306
307 /* If the current frame is outside of the configured motion path range we ignore update of this
308 * motion path by using invalid frame range where start frame is above the end frame. */
309 if (current_frame < mpt->mpath->start_frame || current_frame > mpt->mpath->end_frame) {
310 return;
311 }
312
313 /* Similar to the case when there is only a single keyframe: need to update en entire range to
314 * a constant value. */
315 if (!motionpath_check_can_use_keyframe_range(mpt, adt, fcurve_list)) {
316 *r_sfra = mpt->mpath->start_frame;
317 *r_efra = mpt->mpath->end_frame;
318 return;
319 }
320
321 /* NOTE: Iterate over individual f-curves, and check their keyframes individually and pick a
322 * widest range from them. This is because it's possible to have more narrow keyframe on a
323 * channel which wasn't edited.
324 * Could be optimized further by storing some flags about which channels has been modified so
325 * we ignore all others (which can potentially make an update range unnecessary wide). */
326 for (FCurve *fcu = fcurve_list->first; fcu != NULL; fcu = fcu->next) {
327 DLRBT_Tree fcu_keys;
328 BLI_dlrbTree_init(&fcu_keys);
329 fcurve_to_keylist(adt, fcu, &fcu_keys, 0);
330
331 int fcu_sfra = motionpath_get_prev_prev_keyframe(mpt, &fcu_keys, current_frame);
332 int fcu_efra = motionpath_get_next_next_keyframe(mpt, &fcu_keys, current_frame);
333
334 /* Extend range furher, since accelleration compensation propagates even further away. */
335 if (fcu->auto_smoothing != FCURVE_SMOOTH_NONE) {
336 fcu_sfra = motionpath_get_prev_prev_keyframe(mpt, &fcu_keys, fcu_sfra);
337 fcu_efra = motionpath_get_next_next_keyframe(mpt, &fcu_keys, fcu_efra);
338 }
339
340 if (fcu_sfra <= fcu_efra) {
341 *r_sfra = min_ii(*r_sfra, fcu_sfra);
342 *r_efra = max_ii(*r_efra, fcu_efra);
343 }
344
345 BLI_dlrbTree_free(&fcu_keys);
346 }
347 }
348
motionpath_free_free_tree_data(ListBase * targets)349 static void motionpath_free_free_tree_data(ListBase *targets)
350 {
351 LISTBASE_FOREACH (MPathTarget *, mpt, targets) {
352 BLI_dlrbTree_free(&mpt->keys);
353 }
354 }
355
356 /* Perform baking of the given object's and/or its bones' transforms to motion paths
357 * - scene: current scene
358 * - ob: object whose flagged motionpaths should get calculated
359 * - recalc: whether we need to
360 */
361 /* TODO: include reports pointer? */
animviz_calc_motionpaths(Depsgraph * depsgraph,Main * bmain,Scene * scene,ListBase * targets,eAnimvizCalcRange range,bool restore)362 void animviz_calc_motionpaths(Depsgraph *depsgraph,
363 Main *bmain,
364 Scene *scene,
365 ListBase *targets,
366 eAnimvizCalcRange range,
367 bool restore)
368 {
369 /* Sanity check. */
370 if (ELEM(NULL, targets, targets->first)) {
371 return;
372 }
373
374 const int cfra = CFRA;
375 int sfra = INT_MAX, efra = INT_MIN;
376 switch (range) {
377 case ANIMVIZ_CALC_RANGE_CURRENT_FRAME:
378 motionpath_get_global_framerange(targets, &sfra, &efra);
379 if (sfra > efra) {
380 return;
381 }
382 if (cfra < sfra || cfra > efra) {
383 return;
384 }
385 sfra = efra = cfra;
386 break;
387 case ANIMVIZ_CALC_RANGE_CHANGED:
388 /* Nothing to do here, will be handled later when iterating through the targets. */
389 break;
390 case ANIMVIZ_CALC_RANGE_FULL:
391 motionpath_get_global_framerange(targets, &sfra, &efra);
392 if (sfra > efra) {
393 return;
394 }
395 break;
396 }
397
398 /* get copies of objects/bones to get the calculated results from
399 * (for copy-on-write evaluation), so that we actually get some results
400 */
401
402 /* TODO: Create a copy of background depsgraph that only contain these entities,
403 * and only evaluates them.
404 *
405 * For until that is done we force dependency graph to not be active, so we don't lose unkeyed
406 * changes during updating the motion path.
407 * This still doesn't include unkeyed changes to the path itself, but allows to have updates in
408 * an environment when auto-keying and pose paste is used. */
409
410 const bool is_active_depsgraph = DEG_is_active(depsgraph);
411 if (is_active_depsgraph) {
412 DEG_make_inactive(depsgraph);
413 }
414
415 LISTBASE_FOREACH (MPathTarget *, mpt, targets) {
416 mpt->ob_eval = DEG_get_evaluated_object(depsgraph, mpt->ob);
417
418 AnimData *adt = BKE_animdata_from_id(&mpt->ob_eval->id);
419
420 /* build list of all keyframes in active action for object or pchan */
421 BLI_dlrbTree_init(&mpt->keys);
422
423 ListBase *fcurve_list = NULL;
424 if (adt) {
425 /* get pointer to animviz settings for each target */
426 bAnimVizSettings *avs = animviz_target_settings_get(mpt);
427
428 /* it is assumed that keyframes for bones are all grouped in a single group
429 * unless an option is set to always use the whole action
430 */
431 if ((mpt->pchan) && (avs->path_viewflag & MOTIONPATH_VIEW_KFACT) == 0) {
432 bActionGroup *agrp = BKE_action_group_find_name(adt->action, mpt->pchan->name);
433
434 if (agrp) {
435 fcurve_list = &agrp->channels;
436 agroup_to_keylist(adt, agrp, &mpt->keys, 0);
437 }
438 }
439 else {
440 fcurve_list = &adt->action->curves;
441 action_to_keylist(adt, adt->action, &mpt->keys, 0);
442 }
443 }
444
445 if (range == ANIMVIZ_CALC_RANGE_CHANGED) {
446 int mpt_sfra, mpt_efra;
447 motionpath_calculate_update_range(mpt, adt, fcurve_list, cfra, &mpt_sfra, &mpt_efra);
448 if (mpt_sfra <= mpt_efra) {
449 sfra = min_ii(sfra, mpt_sfra);
450 efra = max_ii(efra, mpt_efra);
451 }
452 }
453 }
454
455 if (sfra > efra) {
456 motionpath_free_free_tree_data(targets);
457 return;
458 }
459
460 /* calculate path over requested range */
461 CLOG_INFO(&LOG,
462 1,
463 "Calculating MotionPaths between frames %d - %d (%d frames)",
464 sfra,
465 efra,
466 efra - sfra + 1);
467 for (CFRA = sfra; CFRA <= efra; CFRA++) {
468 if (range == ANIMVIZ_CALC_RANGE_CURRENT_FRAME) {
469 /* For current frame, only update tagged. */
470 BKE_scene_graph_update_tagged(depsgraph, bmain);
471 }
472 else {
473 /* Update relevant data for new frame. */
474 motionpaths_calc_update_scene(depsgraph);
475 }
476
477 /* perform baking for targets */
478 motionpaths_calc_bake_targets(targets, CFRA);
479 }
480
481 /* reset original environment */
482 /* NOTE: We don't always need to reevaluate the main scene, as the depsgraph
483 * may be a temporary one that works on a subset of the data.
484 * We always have to restore the current frame though. */
485 CFRA = cfra;
486 if (range != ANIMVIZ_CALC_RANGE_CURRENT_FRAME && restore) {
487 motionpaths_calc_update_scene(depsgraph);
488 }
489
490 if (is_active_depsgraph) {
491 DEG_make_active(depsgraph);
492 }
493
494 /* clear recalc flags from targets */
495 LISTBASE_FOREACH (MPathTarget *, mpt, targets) {
496 bMotionPath *mpath = mpt->mpath;
497
498 /* get pointer to animviz settings for each target */
499 bAnimVizSettings *avs = animviz_target_settings_get(mpt);
500
501 /* clear the flag requesting recalculation of targets */
502 avs->recalc &= ~ANIMVIZ_RECALC_PATHS;
503
504 /* Clean temp data */
505 BLI_dlrbTree_free(&mpt->keys);
506
507 /* Free previous batches to force update. */
508 GPU_VERTBUF_DISCARD_SAFE(mpath->points_vbo);
509 GPU_BATCH_DISCARD_SAFE(mpath->batch_line);
510 GPU_BATCH_DISCARD_SAFE(mpath->batch_points);
511 }
512 }
513