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