Blender  V3.3
anim_path.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2001-2002 NaN Holding BV. All rights reserved. */
3 
8 #include "MEM_guardedalloc.h"
9 
10 #include <float.h>
11 
12 #include "DNA_curve_types.h"
13 #include "DNA_key_types.h"
14 #include "DNA_object_types.h"
15 
16 #include "BLI_math_vector.h"
17 
18 #include "BKE_anim_path.h"
19 #include "BKE_curve.h"
20 #include "BKE_key.h"
21 
22 #include "CLG_log.h"
23 
24 static CLG_LogRef LOG = {"bke.anim"};
25 
26 /* ******************************************************************** */
27 /* Curve Paths - for curve deforms and/or curve following */
28 
29 static int get_bevlist_seg_array_size(const BevList *bl)
30 {
31  if (bl->poly >= 0) {
32  /* Cyclic curve. */
33  return bl->nr;
34  }
35 
36  return bl->nr - 1;
37 }
38 
40 {
41  BLI_assert(curve_cache != NULL);
42 
43  BevList *bl = curve_cache->bev.first;
44 
45  BLI_assert(bl != NULL && bl->nr > 1);
46 
47  return get_bevlist_seg_array_size(bl);
48 }
49 
50 float BKE_anim_path_get_length(const CurveCache *curve_cache)
51 {
52  const int seg_size = BKE_anim_path_get_array_size(curve_cache);
53  return curve_cache->anim_path_accum_length[seg_size - 1];
54 }
55 
57 {
58  if (ob == NULL || ob->type != OB_CURVES_LEGACY) {
59  return;
60  }
61  if (ob->runtime.curve_cache == NULL) {
62  CLOG_WARN(&LOG, "No curve cache!");
63  return;
64  }
65  /* We only use the first curve. */
66  BevList *bl = ob->runtime.curve_cache->bev.first;
67  if (bl == NULL || !bl->nr) {
68  CLOG_WARN(&LOG, "No bev list data!");
69  return;
70  }
71 
72  /* Free old data. */
75  }
76 
77  /* We assume that we have at least two points.
78  * If there is less than two points in the curve,
79  * no BevList should have been generated.
80  */
81  BLI_assert(bl->nr > 1);
82 
83  const int seg_size = get_bevlist_seg_array_size(bl);
84  float *len_data = (float *)MEM_mallocN(sizeof(float) * seg_size, "calcpathdist");
86 
87  BevPoint *bp_arr = bl->bevpoints;
88  float prev_len = 0.0f;
89  for (int i = 0; i < bl->nr - 1; i++) {
90  prev_len += len_v3v3(bp_arr[i].vec, bp_arr[i + 1].vec);
91  len_data[i] = prev_len;
92  }
93 
94  if (bl->poly >= 0) {
95  /* Cyclic curve. */
96  len_data[seg_size - 1] = prev_len + len_v3v3(bp_arr[0].vec, bp_arr[bl->nr - 1].vec);
97  }
98 }
99 
100 static void get_curve_points_from_idx(const int idx,
101  const BevList *bl,
102  const bool is_cyclic,
103  BevPoint const **r_p0,
104  BevPoint const **r_p1,
105  BevPoint const **r_p2,
106  BevPoint const **r_p3)
107 {
108  BLI_assert(idx >= 0);
109  BLI_assert(idx < bl->nr - 1 || (is_cyclic && idx < bl->nr));
110  BLI_assert(bl->nr > 1);
111 
112  const BevPoint *bp_arr = bl->bevpoints;
113 
114  /* First segment. */
115  if (idx == 0) {
116  *r_p1 = &bp_arr[0];
117  if (is_cyclic) {
118  *r_p0 = &bp_arr[bl->nr - 1];
119  }
120  else {
121  *r_p0 = *r_p1;
122  }
123 
124  *r_p2 = &bp_arr[1];
125 
126  if (bl->nr > 2) {
127  *r_p3 = &bp_arr[2];
128  }
129  else {
130  *r_p3 = *r_p2;
131  }
132  return;
133  }
134 
135  /* Last segment (or next to last in a cyclic curve). */
136  if (idx == bl->nr - 2) {
137  /* The case when the bl->nr == 2 falls in to the "first segment" check above.
138  * So here we can assume that bl->nr > 2.
139  */
140  *r_p0 = &bp_arr[idx - 1];
141  *r_p1 = &bp_arr[idx];
142  *r_p2 = &bp_arr[idx + 1];
143 
144  if (is_cyclic) {
145  *r_p3 = &bp_arr[0];
146  }
147  else {
148  *r_p3 = *r_p2;
149  }
150  return;
151  }
152 
153  if (idx == bl->nr - 1) {
154  /* Last segment in a cyclic curve. This should only trigger if the curve is cyclic
155  * as it gets an extra segment between the end and the start point. */
156  *r_p0 = &bp_arr[idx - 1];
157  *r_p1 = &bp_arr[idx];
158  *r_p2 = &bp_arr[0];
159  *r_p3 = &bp_arr[1];
160  return;
161  }
162 
163  /* To get here the curve has to have four curve points or more and idx can't
164  * be the first or the last segment.
165  * So we can assume that we can get four points without any special checks.
166  */
167  *r_p0 = &bp_arr[idx - 1];
168  *r_p1 = &bp_arr[idx];
169  *r_p2 = &bp_arr[idx + 1];
170  *r_p3 = &bp_arr[idx + 2];
171 }
172 
173 static bool binary_search_anim_path(const float *accum_len_arr,
174  const int seg_size,
175  const float goal_len,
176  int *r_idx,
177  float *r_frac)
178 {
179  float left_len, right_len;
180  int cur_idx = 0, cur_base = 0;
181  int cur_step = seg_size - 1;
182 
183  while (true) {
184  cur_idx = cur_base + cur_step / 2;
185  left_len = accum_len_arr[cur_idx];
186  right_len = accum_len_arr[cur_idx + 1];
187 
188  if (left_len <= goal_len && right_len > goal_len) {
189  *r_idx = cur_idx + 1;
190  *r_frac = (goal_len - left_len) / (right_len - left_len);
191  return true;
192  }
193  if (cur_idx == 0) {
194  /* We ended up at the first segment. The point must be in here. */
195  *r_idx = 0;
196  *r_frac = goal_len / accum_len_arr[0];
197  return true;
198  }
199 
200  if (UNLIKELY(cur_step == 0)) {
201  /* This should never happen unless there is something horribly wrong. */
202  CLOG_ERROR(&LOG, "Couldn't find any valid point on the animation path!");
203  BLI_assert_msg(0, "Couldn't find any valid point on the animation path!");
204  return false;
205  }
206 
207  if (left_len < goal_len) {
208  /* Go to the right. */
209  cur_base = cur_idx + 1;
210  cur_step--;
211  } /* Else, go to the left. */
212 
213  cur_step /= 2;
214  }
215 }
216 
217 bool BKE_where_on_path(const Object *ob,
218  float ctime,
219  float r_vec[4],
220  float r_dir[3],
221  float r_quat[4],
222  float *r_radius,
223  float *r_weight)
224 {
225  if (ob == NULL || ob->type != OB_CURVES_LEGACY) {
226  return false;
227  }
228  Curve *cu = ob->data;
229  if (ob->runtime.curve_cache == NULL) {
230  CLOG_WARN(&LOG, "No curve cache!");
231  return false;
232  }
234  CLOG_WARN(&LOG, "No anim path!");
235  return false;
236  }
237  /* We only use the first curve. */
238  BevList *bl = ob->runtime.curve_cache->bev.first;
239  if (bl == NULL || !bl->nr) {
240  CLOG_WARN(&LOG, "No bev list data!");
241  return false;
242  }
243 
244  /* Test for cyclic curve. */
245  const bool is_cyclic = bl->poly >= 0;
246 
247  if (is_cyclic) {
248  /* Wrap the time into a 0.0 - 1.0 range. */
249  if (ctime < 0.0f || ctime > 1.0f) {
250  ctime -= floorf(ctime);
251  }
252  }
253 
254  /* The curve points for this ctime value. */
255  const BevPoint *p0, *p1, *p2, *p3;
256 
257  float frac;
258  const int seg_size = get_bevlist_seg_array_size(bl);
259  const float *accum_len_arr = ob->runtime.curve_cache->anim_path_accum_length;
260  const float goal_len = ctime * accum_len_arr[seg_size - 1];
261 
262  /* Are we simply trying to get the start/end point? */
263  if (ctime <= 0.0f || ctime >= 1.0f) {
264  const float clamp_time = clamp_f(ctime, 0.0f, 1.0f);
265  const int idx = clamp_time * (seg_size - 1);
266  get_curve_points_from_idx(idx, bl, is_cyclic, &p0, &p1, &p2, &p3);
267 
268  if (idx == 0) {
269  frac = goal_len / accum_len_arr[0];
270  }
271  else {
272  frac = (goal_len - accum_len_arr[idx - 1]) / (accum_len_arr[idx] - accum_len_arr[idx - 1]);
273  }
274  }
275  else {
276  /* Do binary search to get the correct segment. */
277  int idx;
278  const bool found_idx = binary_search_anim_path(accum_len_arr, seg_size, goal_len, &idx, &frac);
279 
280  if (UNLIKELY(!found_idx)) {
281  return false;
282  }
283  get_curve_points_from_idx(idx, bl, is_cyclic, &p0, &p1, &p2, &p3);
284  }
285 
286  /* NOTE: commented out for follow constraint
287  *
288  * If it's ever be uncommented watch out for BKE_curve_deform_coords()
289  * which used to temporary set CU_FOLLOW flag for the curve and no
290  * longer does it (because of threading issues of such a thing.
291  */
292  // if (cu->flag & CU_FOLLOW) {
293 
294  float w[4];
295 
297 
298  if (r_dir) {
299  interp_v3_v3v3v3v3(r_dir, p0->vec, p1->vec, p2->vec, p3->vec, w);
300 
301  /* Make compatible with #vec_to_quat. */
302  negate_v3(r_dir);
303  }
304  //}
305 
306  const ListBase *nurbs = BKE_curve_editNurbs_get(cu);
307  if (!nurbs) {
308  nurbs = &cu->nurb;
309  }
310  const Nurb *nu = nurbs->first;
311 
312  /* Make sure that first and last frame are included in the vectors here. */
313  if (ELEM(nu->type, CU_POLY, CU_BEZIER, CU_NURBS)) {
315  }
316  else if (p2 == p3) {
318  }
319  else {
321  }
322 
323  if (r_vec) {
324  r_vec[0] = /* X */
325  w[0] * p0->vec[0] + w[1] * p1->vec[0] + w[2] * p2->vec[0] + w[3] * p3->vec[0];
326  r_vec[1] = /* Y */
327  w[0] * p0->vec[1] + w[1] * p1->vec[1] + w[2] * p2->vec[1] + w[3] * p3->vec[1];
328  r_vec[2] = /* Z */
329  w[0] * p0->vec[2] + w[1] * p1->vec[2] + w[2] * p2->vec[2] + w[3] * p3->vec[2];
330  }
331 
332  /* Clamp weights to 0-1 as we don't want to extrapolate other values than position. */
333  clamp_v4(w, 0.0f, 1.0f);
334 
335  if (r_vec) {
336  /* Tilt, should not be needed since we have quat still used. */
337  r_vec[3] = w[0] * p0->tilt + w[1] * p1->tilt + w[2] * p2->tilt + w[3] * p3->tilt;
338  }
339 
340  if (r_quat) {
341  float totfac, q1[4], q2[4];
342 
343  totfac = w[0] + w[3];
344  if (totfac > FLT_EPSILON) {
345  interp_qt_qtqt(q1, p0->quat, p3->quat, w[3] / totfac);
346  }
347  else {
348  copy_qt_qt(q1, p1->quat);
349  }
350 
351  totfac = w[1] + w[2];
352  if (totfac > FLT_EPSILON) {
353  interp_qt_qtqt(q2, p1->quat, p2->quat, w[2] / totfac);
354  }
355  else {
356  copy_qt_qt(q2, p3->quat);
357  }
358 
359  totfac = w[0] + w[1] + w[2] + w[3];
360  if (totfac > FLT_EPSILON) {
361  interp_qt_qtqt(r_quat, q1, q2, (w[1] + w[2]) / totfac);
362  }
363  else {
364  copy_qt_qt(r_quat, q2);
365  }
366  }
367 
368  if (r_radius) {
369  *r_radius = w[0] * p0->radius + w[1] * p1->radius + w[2] * p2->radius + w[3] * p3->radius;
370  }
371 
372  if (r_weight) {
373  *r_weight = w[0] * p0->weight + w[1] * p1->weight + w[2] * p2->weight + w[3] * p3->weight;
374  }
375 
376  return true;
377 }
struct ListBase * BKE_curve_editNurbs_get(struct Curve *cu)
Definition: curve.cc:426
void key_curve_tangent_weights(float t, float data[4], int type)
Definition: key.c:377
void key_curve_position_weights(float t, float data[4], int type)
Definition: key.c:336
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_assert_msg(a, msg)
Definition: BLI_assert.h:53
MINLINE float clamp_f(float value, float min, float max)
void interp_qt_qtqt(float q[4], const float a[4], const float b[4], float t)
void copy_qt_qt(float q[4], const float a[4])
Definition: math_rotation.c:33
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void clamp_v4(float vec[4], float min, float max)
MINLINE void negate_v3(float r[3])
void interp_v3_v3v3v3v3(float p[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3], const float w[4])
Definition: math_vector.c:168
#define UNLIKELY(x)
#define ELEM(...)
#define CLOG_ERROR(clg_ref,...)
Definition: CLG_log.h:190
#define CLOG_WARN(clg_ref,...)
Definition: CLG_log.h:189
@ CU_BEZIER
@ CU_POLY
@ CU_NURBS
@ KEY_LINEAR
@ KEY_CARDINAL
@ KEY_BSPLINE
Object is a sort of wrapper for general info.
@ OB_CURVES_LEGACY
Read Guarded memory(de)allocation.
int BKE_anim_path_get_array_size(const CurveCache *curve_cache)
Definition: anim_path.c:39
bool BKE_where_on_path(const Object *ob, float ctime, float r_vec[4], float r_dir[3], float r_quat[4], float *r_radius, float *r_weight)
Definition: anim_path.c:217
static bool binary_search_anim_path(const float *accum_len_arr, const int seg_size, const float goal_len, int *r_idx, float *r_frac)
Definition: anim_path.c:173
static void get_curve_points_from_idx(const int idx, const BevList *bl, const bool is_cyclic, BevPoint const **r_p0, BevPoint const **r_p1, BevPoint const **r_p2, BevPoint const **r_p3)
Definition: anim_path.c:100
float BKE_anim_path_get_length(const CurveCache *curve_cache)
Definition: anim_path.c:50
static CLG_LogRef LOG
Definition: anim_path.c:24
void BKE_anim_path_calc_data(Object *ob)
Definition: anim_path.c:56
static int get_bevlist_seg_array_size(const BevList *bl)
Definition: anim_path.c:29
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition: btQuadWord.h:119
static bool is_cyclic(const Nurb *nu)
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
#define floorf(x)
Definition: metal/compat.h:224
ccl_device_inline float frac(float x, int *ix)
BevPoint * bevpoints
float radius
float quat[4]
float weight
float vec[3]
ListBase bev
Definition: BKE_curve.h:34
const float * anim_path_accum_length
Definition: BKE_curve.h:42
ListBase nurb
void * first
Definition: DNA_listBase.h:31
short type
struct CurveCache * curve_cache
Object_Runtime runtime
void * data