Blender V5.3
curve_bezier.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <algorithm>
10
11#include "BLI_task.hh"
12
13#include "BKE_attribute_math.hh"
14#include "BKE_curves.hh"
15
17
18bool segment_is_vector(const Span<int8_t> handle_types_left,
19 const Span<int8_t> handle_types_right,
20 const int segment_index)
21{
22 BLI_assert(handle_types_left.index_range().drop_back(1).contains(segment_index));
23 return segment_is_vector(handle_types_right[segment_index],
24 handle_types_left[segment_index + 1]);
25}
26
27bool last_cyclic_segment_is_vector(const Span<int8_t> handle_types_left,
28 const Span<int8_t> handle_types_right)
29{
30 return segment_is_vector(handle_types_right.last(), handle_types_left.first());
31}
32
33void calculate_evaluated_offsets(const Span<int8_t> handle_types_left,
34 const Span<int8_t> handle_types_right,
35 const bool cyclic,
36 const int resolution,
37 MutableSpan<int> evaluated_offsets)
38{
39 const int size = handle_types_left.size();
40 BLI_assert(evaluated_offsets.size() == size + 1);
41
42 evaluated_offsets.first() = 0;
43 if (size == 1) {
44 evaluated_offsets.last() = 1;
45 return;
46 }
47
48 const int points_per_segment = std::max(1, resolution);
49
50 int offset = 0;
51 for (const int i : IndexRange(size - 1)) {
52 evaluated_offsets[i] = offset;
53 offset += segment_is_vector(handle_types_left, handle_types_right, i) ? 1 : points_per_segment;
54 }
55
56 evaluated_offsets.last(1) = offset;
57 if (cyclic) {
58 offset += last_cyclic_segment_is_vector(handle_types_left, handle_types_right) ?
59 1 :
60 points_per_segment;
61 }
62 else {
63 offset++;
64 }
65
66 evaluated_offsets.last() = offset;
67}
68
69Insertion insert(const float3 &point_prev,
70 const float3 &handle_prev,
71 const float3 &handle_next,
72 const float3 &point_next,
73 float parameter)
74{
75 /* De Casteljau Bezier subdivision. */
76 BLI_assert(parameter <= 1.0f && parameter >= 0.0f);
77
78 const float3 center_point = math::interpolate(handle_prev, handle_next, parameter);
79
81 result.handle_prev = math::interpolate(point_prev, handle_prev, parameter);
82 result.handle_next = math::interpolate(handle_next, point_next, parameter);
83 result.left_handle = math::interpolate(result.handle_prev, center_point, parameter);
84 result.right_handle = math::interpolate(center_point, result.handle_next, parameter);
85 result.position = math::interpolate(result.left_handle, result.right_handle, parameter);
86 return result;
87}
88
90 const float3 &other_handle,
91 const float3 &aligned_handle)
92{
93 /* Keep track of the old length of the opposite handle. */
94 const float length = math::distance(aligned_handle, position);
95 /* Set the other handle to directly opposite from the current handle. */
96 const float3 dir = math::normalize(other_handle - position);
97 if (math::is_zero(dir)) {
98 /* There is no direction to align against when the opposite handle coincides with the
99 * control point, so preserve the existing aligned handle. */
100 return aligned_handle;
101 }
102 return position - dir * length;
103}
104
105/* Align handles to each other, length will be preserved (unless zero). The new handles will be on
106 * the same plane as the old ones.*/
107static std::pair<float3, float3> calculate_align_both_handles(const float3 &position,
108 const float3 &left_handle,
109 const float3 &right_handle)
110{
111 const float3 left_dir = left_handle - position;
112 const float3 right_dir = right_handle - position;
113
114 /* Keep track of the lengths of both handles. */
115 const float left_length = math::length(left_dir);
116 const float right_length = math::length(right_dir);
117
118 if (left_length == 0.0f && right_length == 0.0f) {
119 /* All three points are the same, no clear way to fixed it. */
120 return {left_handle, right_handle};
121 }
122 /* If one handle has zero length, use the other as the length and direction. */
123 if (left_length == 0.0f) {
124 return {position - right_dir, right_handle};
125 }
126 if (right_length == 0.0f) {
127 return {left_handle, position - left_dir};
128 }
129
130 /* Use the direction halfway between the two directions. */
131 float3 align_dir = math::normalize(left_dir) + math::normalize(right_dir);
132
133 const float align_length = math::length(align_dir);
134 if (align_length <= 0.0001f * (left_length + right_length)) {
135 /* The handles are already aligned. */
136 return {left_handle, right_handle};
137 }
138
139 /* Normalize. */
140 align_dir = align_dir / align_length;
141
142 /* Project the directions onto the plane formed by `align_dir`. */
143 const float3 new_left_dir = left_dir - math::dot(left_dir, align_dir) * align_dir;
144 const float3 new_right_dir = right_dir - math::dot(right_dir, align_dir) * align_dir;
145
146 /* Use the new directions with the old lengths. */
147 return {position + left_length * math::normalize(new_left_dir),
148 position + right_length * math::normalize(new_right_dir)};
149}
150
151static void calculate_point_handles(const HandleType type_left,
152 const HandleType type_right,
153 const float3 position,
154 const float3 prev_position,
155 const float3 next_position,
156 float3 &left,
157 float3 &right)
158{
159 if (ELEM(BEZIER_HANDLE_AUTO, type_left, type_right)) {
160 const float3 prev_diff = position - prev_position;
161 const float3 next_diff = next_position - position;
162 float prev_len = math::length(prev_diff);
163 float next_len = math::length(next_diff);
164 if (prev_len == 0.0f) {
165 prev_len = 1.0f;
166 }
167 if (next_len == 0.0f) {
168 next_len = 1.0f;
169 }
170 const float3 dir = next_diff / next_len + prev_diff / prev_len;
171
172 /* The magic number 2.5614 is derived from approximating a circular arc at the control point.
173 * Given the constraints:
174 *
175 * - `P0=(0,1),P1=(c,1),P2=(1,c),P3=(1,0)`.
176 * - The first derivative of the curve must agree with the circular arc derivative at the
177 * endpoints.
178 * - Minimize the maximum radial drift.
179 * one can compute `c ≈ 0.5519150244935105707435627`.
180 * The distance from P0 to P3 is `sqrt(2)`.
181 *
182 * The magic factor for `len` is `(sqrt(2) / 0.5519150244935105707435627) ≈ 2.562375546255352`.
183 * In older code of blender a slightly worse approximation of 2.5614 is used. It's kept
184 * for compatibility.
185 *
186 * See https://spencermortensen.com/articles/bezier-circle/. */
187 const float len = math::length(dir) * 2.5614f;
188 if (len != 0.0f) {
189 if (type_left == BEZIER_HANDLE_AUTO) {
190 const float prev_len_clamped = std::min(prev_len, next_len * 5.0f);
191 left = position + dir * -(prev_len_clamped / len);
192 }
193 if (type_right == BEZIER_HANDLE_AUTO) {
194 const float next_len_clamped = std::min(next_len, prev_len * 5.0f);
195 right = position + dir * (next_len_clamped / len);
196 }
197 }
198 }
199
200 if (type_left == BEZIER_HANDLE_VECTOR) {
201 left = calculate_vector_handle(position, prev_position);
202 }
203
204 if (type_right == BEZIER_HANDLE_VECTOR) {
205 right = calculate_vector_handle(position, next_position);
206 }
207
208 /* When one of the handles is "aligned" handle, it must be aligned with the other, i.e. point in
209 * the opposite direction. Don't handle the case of two aligned handles, because code elsewhere
210 * should keep the pair consistent, and the relative locations aren't affected by other points
211 * anyway. */
212 if (type_left == BEZIER_HANDLE_ALIGN && type_right != BEZIER_HANDLE_ALIGN) {
213 left = calculate_aligned_handle(position, right, left);
214 }
215 else if (type_left != BEZIER_HANDLE_ALIGN && type_right == BEZIER_HANDLE_ALIGN) {
216 right = calculate_aligned_handle(position, left, right);
217 }
218}
219
221 const HandleType type,
222 const HandleType type_other,
223 const float3 &new_handle,
224 float3 &handle,
225 float3 &handle_other)
226{
227 /* Don't bother when the handle positions are calculated automatically anyway. */
229 return;
230 }
231
232 handle = new_handle;
233 if (type_other == BEZIER_HANDLE_ALIGN) {
234 handle_other = calculate_aligned_handle(position, handle, handle_other);
235 }
236}
237
239 const Span<float3> positions,
240 const Span<float3> align_with,
241 MutableSpan<float3> align_handles)
242{
243 selection.foreach_index_optimized<int>(
244 [&](const int point) {
245 align_handles[point] = calculate_aligned_handle(
246 positions[point], align_with[point], align_handles[point]);
247 },
249}
250
252 const Span<float3> positions,
253 const Span<float3> handles_left,
254 const Span<float3> handles_right,
255 MutableSpan<float3> align_handles_left,
256 MutableSpan<float3> align_handles_right)
257{
258 selection.foreach_index_optimized<int>(
259 [&](const int point) {
260 const auto [new_left, new_right] = calculate_align_both_handles(
261 positions[point], handles_left[point], handles_right[point]);
262 align_handles_left[point] = new_left;
263 align_handles_right[point] = new_right;
264 },
266}
267
268void calculate_auto_handles(const bool cyclic,
269 const Span<int8_t> types_left,
270 const Span<int8_t> types_right,
271 const Span<float3> positions,
272 MutableSpan<float3> positions_left,
273 MutableSpan<float3> positions_right)
274{
275 const int points_num = positions.size();
276 if (points_num == 1) {
277 return;
278 }
279
281 HandleType(types_right.first()),
282 positions.first(),
283 cyclic ? positions.last() : 2.0f * positions.first() - positions[1],
284 positions[1],
285 positions_left.first(),
286 positions_right.first());
287
288 threading::parallel_for(IndexRange(1, points_num - 2), 1024, [&](IndexRange range) {
289 for (const int i : range) {
290 calculate_point_handles(HandleType(types_left[i]),
291 HandleType(types_right[i]),
292 positions[i],
293 positions[i - 1],
294 positions[i + 1],
295 positions_left[i],
296 positions_right[i]);
297 }
298 });
299
301 HandleType(types_right.last()),
302 positions.last(),
303 positions.last(1),
304 cyclic ? positions.first() : 2.0f * positions.last() - positions.last(1),
305 positions_left.last(),
306 positions_right.last());
307}
308
309template<typename T>
311 const T &point_0, const T &point_1, const T &point_2, const T &point_3, MutableSpan<T> result)
312{
313 BLI_assert(result.size() > 0);
314 const float inv_len = 1.0f / float(result.size());
315 const float inv_len_squared = inv_len * inv_len;
316 const float inv_len_cubed = inv_len_squared * inv_len;
317
318 const T rt1 = 3.0f * (point_1 - point_0) * inv_len;
319 const T rt2 = 3.0f * (point_0 - 2.0f * point_1 + point_2) * inv_len_squared;
320 const T rt3 = (point_3 - point_0 + 3.0f * (point_1 - point_2)) * inv_len_cubed;
321
322 T q0 = point_0;
323 T q1 = rt1 + rt2 + rt3;
324 T q2 = 2.0f * rt2 + 6.0f * rt3;
325 T q3 = 6.0f * rt3;
326 for (const int i : result.index_range()) {
327 result[i] = q0;
328 q0 += q1;
329 q1 += q2;
330 q2 += q3;
331 }
332}
333template<>
334void evaluate_segment(const float3 &point_0,
335 const float3 &point_1,
336 const float3 &point_2,
337 const float3 &point_3,
339{
340 evaluate_segment_ex<float3>(point_0, point_1, point_2, point_3, result);
341}
342template<>
343void evaluate_segment(const float2 &point_0,
344 const float2 &point_1,
345 const float2 &point_2,
346 const float2 &point_3,
348{
349 evaluate_segment_ex<float2>(point_0, point_1, point_2, point_3, result);
350}
351
353 const Span<float3> handles_left,
354 const Span<float3> handles_right,
355 const OffsetIndices<int> evaluated_offsets,
356 MutableSpan<float3> evaluated_positions)
357{
358 BLI_assert(evaluated_offsets.total_size() == evaluated_positions.size());
359 if (evaluated_offsets.total_size() == 1) {
360 evaluated_positions.first() = positions.first();
361 return;
362 }
363
364 /* Evaluate the first segment. */
365 evaluate_segment(positions.first(),
366 handles_right.first(),
367 handles_left[1],
368 positions[1],
369 evaluated_positions.slice(evaluated_offsets[0]));
370
371 /* Give each task fewer segments as the resolution gets larger. */
372 const int grain_size = std::max<int>(evaluated_positions.size() / positions.size() * 32, 1);
373 const IndexRange inner_segments = positions.index_range().drop_back(1).drop_front(1);
374 threading::parallel_for(inner_segments, grain_size, [&](IndexRange range) {
375 for (const int i : range) {
376 const IndexRange evaluated_range = evaluated_offsets[i];
377 if (evaluated_range.size() == 1) {
378 evaluated_positions[evaluated_range.first()] = positions[i];
379 }
380 else {
381 evaluate_segment(positions[i],
382 handles_right[i],
383 handles_left[i + 1],
384 positions[i + 1],
385 evaluated_positions.slice(evaluated_range));
386 }
387 }
388 });
389
390 /* Evaluate the final cyclic segment if necessary. */
391 const IndexRange last_segment_points = evaluated_offsets[positions.index_range().last()];
392 if (last_segment_points.size() == 1) {
393 evaluated_positions.last() = positions.last();
394 }
395 else {
396 evaluate_segment(positions.last(),
397 handles_right.last(),
398 handles_left.first(),
399 positions.first(),
400 evaluated_positions.slice(last_segment_points));
401 }
402}
403
404template<typename T>
405static inline void linear_interpolation(const T &a, const T &b, MutableSpan<T> dst)
406{
407 dst.first() = a;
408 const float step = 1.0f / dst.size();
409 for (const int i : dst.index_range().drop_front(1)) {
410 dst[i] = attribute_math::mix2(i * step, a, b);
411 }
412}
413
414template<typename T>
415static void interpolate_to_evaluated(const Span<T> src,
416 const OffsetIndices<int> evaluated_offsets,
417 MutableSpan<T> dst)
418{
419 BLI_assert(!src.is_empty());
420 BLI_assert(evaluated_offsets.total_size() == dst.size());
421 if (src.size() == 1) {
422 BLI_assert(dst.size() == 1);
423 dst.first() = src.first();
424 return;
425 }
426
427 linear_interpolation(src.first(), src[1], dst.slice(evaluated_offsets[0]));
428
430 src.index_range().drop_back(1).drop_front(1), 512, [&](IndexRange range) {
431 for (const int i : range) {
432 const IndexRange segment = evaluated_offsets[i];
433 linear_interpolation(src[i], src[i + 1], dst.slice(segment));
434 }
435 });
436
437 const IndexRange last_segment = evaluated_offsets[src.index_range().last()];
438 linear_interpolation(src.last(), src.first(), dst.slice(last_segment));
439}
440
442 const OffsetIndices<int> evaluated_offsets,
443 GMutableSpan dst)
444{
445 attribute_math::to_static_type(src.type(), [&]<typename T>() {
446 if constexpr (!std::is_void_v<attribute_math::DefaultMixer<T>>) {
447 interpolate_to_evaluated(src.typed<T>(), evaluated_offsets, dst.typed<T>());
448 }
449 });
450}
451
452} // namespace blender::bke::curves::bezier
Low-level operations for curves.
#define ELEM(...)
const CPPType & type() const
constexpr int64_t first() const
constexpr IndexRange drop_back(int64_t n) const
constexpr int64_t last(const int64_t n=0) const
constexpr int64_t size() const
constexpr IndexRange()=default
constexpr bool contains(int64_t value) const
constexpr IndexRange drop_front(int64_t n) const
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition BLI_span.hh:579
constexpr T & first() const
Definition BLI_span.hh:685
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr T & last(const int64_t n=0) const
Definition BLI_span.hh:695
constexpr const T & first() const
Definition BLI_span.hh:319
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr const T & last(const int64_t n=0) const
Definition BLI_span.hh:329
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr bool is_empty() const
Definition BLI_span.hh:264
void foreach_index_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
#define position
VecBase< float, D > step(VecOp< float, D >, VecOp< float, D >) RET
float length(VecOp< float, D >) RET
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
#define T
void to_static_type(const CPPType &cpp_type, Fn &&fn)
T mix2(float factor, const T &a, const T &b)
Insertion insert(const float3 &point_prev, const float3 &handle_prev, const float3 &handle_next, const float3 &point_next, float parameter)
void calculate_aligned_handles(const IndexMask &selection, Span< float3 > positions, Span< float3 > handles_left, Span< float3 > handles_right, MutableSpan< float3 > align_handles_left, MutableSpan< float3 > align_handles_right)
bool segment_is_vector(const HandleType left, const HandleType right)
void calculate_auto_handles(bool cyclic, Span< int8_t > types_left, Span< int8_t > types_right, Span< float3 > positions, MutableSpan< float3 > positions_left, MutableSpan< float3 > positions_right)
void calculate_evaluated_offsets(Span< int8_t > handle_types_left, Span< int8_t > handle_types_right, bool cyclic, int resolution, MutableSpan< int > evaluated_offsets)
static std::pair< float3, float3 > calculate_align_both_handles(const float3 &position, const float3 &left_handle, const float3 &right_handle)
float3 calculate_vector_handle(const float3 &point, const float3 &next_point)
static void calculate_point_handles(const HandleType type_left, const HandleType type_right, const float3 position, const float3 prev_position, const float3 next_position, float3 &left, float3 &right)
bool last_cyclic_segment_is_vector(Span< int8_t > handle_types_left, Span< int8_t > handle_types_right)
static float3 calculate_aligned_handle(const float3 &position, const float3 &other_handle, const float3 &aligned_handle)
void evaluate_segment(const T &point_0, const T &point_1, const T &point_2, const T &point_3, MutableSpan< T > result)
void calculate_single_aligned_handles(const IndexMask &selection, Span< float3 > positions, Span< float3 > align_with, MutableSpan< float3 > align_handles)
void calculate_evaluated_positions(Span< float3 > positions, Span< float3 > handles_left, Span< float3 > handles_right, OffsetIndices< int > evaluated_offsets, MutableSpan< float3 > evaluated_positions)
void interpolate_to_evaluated(GSpan src, OffsetIndices< int > evaluated_offsets, GMutableSpan dst)
void evaluate_segment_ex(const T &point_0, const T &point_1, const T &point_2, const T &point_3, MutableSpan< T > result)
void set_handle_position(const float3 &position, HandleType type, HandleType type_other, const float3 &new_handle, float3 &handle, float3 &handle_other)
static void linear_interpolation(const T &a, const T &b, MutableSpan< T > dst)
constexpr ParallelGrainSize grain_size(int grain_size)
T distance(const T &a, const T &b)
T length(const VecBase< T, Size > &a)
T dot(const QuaternionBase< T > &a, const QuaternionBase< T > &b)
bool is_zero(const T &a)
T interpolate(const T &a, const T &b, const FactorT &t)
MatBase< T, NumCol, NumRow > normalize(const MatBase< T, NumCol, NumRow > &a)
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Definition BLI_task.hh:69
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
VecBase< float, 2 > float2
VecBase< float, 3 > float3
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float