Blender  V3.3
curve_bezier.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
7 #include <algorithm>
8 
9 #include "BKE_attribute_math.hh"
10 #include "BKE_curves.hh"
11 
13 
14 bool segment_is_vector(const Span<int8_t> handle_types_left,
15  const Span<int8_t> handle_types_right,
16  const int segment_index)
17 {
18  BLI_assert(handle_types_left.index_range().drop_back(1).contains(segment_index));
19  return segment_is_vector(handle_types_right[segment_index],
20  handle_types_left[segment_index + 1]);
21 }
22 
23 bool last_cyclic_segment_is_vector(const Span<int8_t> handle_types_left,
24  const Span<int8_t> handle_types_right)
25 {
26  return segment_is_vector(handle_types_right.last(), handle_types_left.first());
27 }
28 
29 void calculate_evaluated_offsets(const Span<int8_t> handle_types_left,
30  const Span<int8_t> handle_types_right,
31  const bool cyclic,
32  const int resolution,
33  MutableSpan<int> evaluated_offsets)
34 {
35  const int size = handle_types_left.size();
36  BLI_assert(evaluated_offsets.size() == size);
37 
38  if (size == 1) {
39  evaluated_offsets.first() = 1;
40  return;
41  }
42 
43  int offset = 0;
44 
45  for (const int i : IndexRange(size - 1)) {
46  offset += segment_is_vector(handle_types_left, handle_types_right, i) ? 1 : resolution;
47  evaluated_offsets[i] = offset;
48  }
49 
50  if (cyclic) {
51  offset += last_cyclic_segment_is_vector(handle_types_left, handle_types_right) ? 1 :
52  resolution;
53  }
54  else {
55  offset++;
56  }
57 
58  evaluated_offsets.last() = offset;
59 }
60 
61 Insertion insert(const float3 &point_prev,
62  const float3 &handle_prev,
63  const float3 &handle_next,
64  const float3 &point_next,
65  float parameter)
66 {
67  /* De Casteljau Bezier subdivision. */
68  BLI_assert(parameter <= 1.0f && parameter >= 0.0f);
69 
70  const float3 center_point = math::interpolate(handle_prev, handle_next, parameter);
71 
73  result.handle_prev = math::interpolate(point_prev, handle_prev, parameter);
74  result.handle_next = math::interpolate(handle_next, point_next, parameter);
75  result.left_handle = math::interpolate(result.handle_prev, center_point, parameter);
76  result.right_handle = math::interpolate(center_point, result.handle_next, parameter);
77  result.position = math::interpolate(result.left_handle, result.right_handle, parameter);
78  return result;
79 }
80 
81 static float3 calculate_aligned_handle(const float3 &position,
82  const float3 &other_handle,
83  const float3 &aligned_handle)
84 {
85  /* Keep track of the old length of the opposite handle. */
86  const float length = math::distance(aligned_handle, position);
87  /* Set the other handle to directly opposite from the current handle. */
88  const float3 dir = math::normalize(other_handle - position);
89  return position - dir * length;
90 }
91 
92 static void calculate_point_handles(const HandleType type_left,
93  const HandleType type_right,
94  const float3 position,
95  const float3 prev_position,
96  const float3 next_position,
97  float3 &left,
98  float3 &right)
99 {
100  if (ELEM(BEZIER_HANDLE_AUTO, type_left, type_right)) {
101  const float3 prev_diff = position - prev_position;
102  const float3 next_diff = next_position - position;
103  float prev_len = math::length(prev_diff);
104  float next_len = math::length(next_diff);
105  if (prev_len == 0.0f) {
106  prev_len = 1.0f;
107  }
108  if (next_len == 0.0f) {
109  next_len = 1.0f;
110  }
111  const float3 dir = next_diff / next_len + prev_diff / prev_len;
112 
113  /* This magic number is unfortunate, but comes from elsewhere in Blender. */
114  const float len = math::length(dir) * 2.5614f;
115  if (len != 0.0f) {
116  if (type_left == BEZIER_HANDLE_AUTO) {
117  const float prev_len_clamped = std::min(prev_len, next_len * 5.0f);
118  left = position + dir * -(prev_len_clamped / len);
119  }
120  if (type_right == BEZIER_HANDLE_AUTO) {
121  const float next_len_clamped = std::min(next_len, prev_len * 5.0f);
122  right = position + dir * (next_len_clamped / len);
123  }
124  }
125  }
126 
127  if (type_left == BEZIER_HANDLE_VECTOR) {
128  left = calculate_vector_handle(position, prev_position);
129  }
130 
131  if (type_right == BEZIER_HANDLE_VECTOR) {
133  }
134 
135  /* When one of the handles is "aligned" handle, it must be aligned with the other, i.e. point in
136  * the opposite direction. Don't handle the case of two aligned handles, because code elsewhere
137  * should keep the pair consistent, and the relative locations aren't affected by other points
138  * anyway. */
139  if (type_left == BEZIER_HANDLE_ALIGN && type_right != BEZIER_HANDLE_ALIGN) {
140  left = calculate_aligned_handle(position, right, left);
141  }
142  else if (type_left != BEZIER_HANDLE_ALIGN && type_right == BEZIER_HANDLE_ALIGN) {
144  }
145 }
146 
147 void set_handle_position(const float3 &position,
148  const HandleType type,
149  const HandleType type_other,
150  const float3 &new_handle,
151  float3 &handle,
152  float3 &handle_other)
153 {
154  /* Don't bother when the handle positions are calculated automatically anyway. */
156  return;
157  }
158 
159  handle = new_handle;
160  if (type_other == BEZIER_HANDLE_ALIGN) {
161  handle_other = calculate_aligned_handle(position, handle, handle_other);
162  }
163 }
164 
165 void calculate_auto_handles(const bool cyclic,
166  const Span<int8_t> types_left,
167  const Span<int8_t> types_right,
168  const Span<float3> positions,
169  MutableSpan<float3> positions_left,
170  MutableSpan<float3> positions_right)
171 {
172  const int points_num = positions.size();
173  if (points_num == 1) {
174  return;
175  }
176 
178  HandleType(types_right.first()),
179  positions.first(),
180  cyclic ? positions.last() : 2.0f * positions.first() - positions[1],
181  positions[1],
182  positions_left.first(),
183  positions_right.first());
184 
185  threading::parallel_for(IndexRange(1, points_num - 2), 1024, [&](IndexRange range) {
186  for (const int i : range) {
187  calculate_point_handles(HandleType(types_left[i]),
188  HandleType(types_right[i]),
189  positions[i],
190  positions[i - 1],
191  positions[i + 1],
192  positions_left[i],
193  positions_right[i]);
194  }
195  });
196 
198  HandleType(types_right.last()),
199  positions.last(),
200  positions.last(1),
201  cyclic ? positions.first() : 2.0f * positions.last() - positions.last(1),
202  positions_left.last(),
203  positions_right.last());
204 }
205 
206 void evaluate_segment(const float3 &point_0,
207  const float3 &point_1,
208  const float3 &point_2,
209  const float3 &point_3,
211 {
212  BLI_assert(result.size() > 0);
213  const float inv_len = 1.0f / static_cast<float>(result.size());
214  const float inv_len_squared = inv_len * inv_len;
215  const float inv_len_cubed = inv_len_squared * inv_len;
216 
217  const float3 rt1 = 3.0f * (point_1 - point_0) * inv_len;
218  const float3 rt2 = 3.0f * (point_0 - 2.0f * point_1 + point_2) * inv_len_squared;
219  const float3 rt3 = (point_3 - point_0 + 3.0f * (point_1 - point_2)) * inv_len_cubed;
220 
221  float3 q0 = point_0;
222  float3 q1 = rt1 + rt2 + rt3;
223  float3 q2 = 2.0f * rt2 + 6.0f * rt3;
224  float3 q3 = 6.0f * rt3;
225  for (const int i : result.index_range()) {
226  result[i] = q0;
227  q0 += q1;
228  q1 += q2;
229  q2 += q3;
230  }
231 }
232 
234  const Span<float3> handles_left,
235  const Span<float3> handles_right,
236  const Span<int> evaluated_offsets,
237  MutableSpan<float3> evaluated_positions)
238 {
239  BLI_assert(evaluated_offsets.last() == evaluated_positions.size());
240  BLI_assert(evaluated_offsets.size() == positions.size());
241  if (evaluated_offsets.last() == 1) {
242  evaluated_positions.first() = positions.first();
243  return;
244  }
245 
246  /* Evaluate the first segment. */
247  evaluate_segment(positions.first(),
248  handles_right.first(),
249  handles_left[1],
250  positions[1],
251  evaluated_positions.take_front(evaluated_offsets.first()));
252 
253  /* Give each task fewer segments as the resolution gets larger. */
254  const int grain_size = std::max<int>(evaluated_positions.size() / positions.size() * 32, 1);
256  positions.index_range().drop_back(1).drop_front(1), grain_size, [&](IndexRange range) {
257  for (const int i : range) {
258  const IndexRange evaluated_range = offsets_to_range(evaluated_offsets, i - 1);
259  if (evaluated_range.size() == 1) {
260  evaluated_positions[evaluated_range.first()] = positions[i];
261  }
262  else {
263  evaluate_segment(positions[i],
264  handles_right[i],
265  handles_left[i + 1],
266  positions[i + 1],
267  evaluated_positions.slice(evaluated_range));
268  }
269  }
270  });
271 
272  /* Evaluate the final cyclic segment if necessary. */
273  const IndexRange last_segment_points = offsets_to_range(evaluated_offsets, positions.size() - 2);
274  if (last_segment_points.size() == 1) {
275  evaluated_positions.last() = positions.last();
276  }
277  else {
279  handles_right.last(),
280  handles_left.first(),
281  positions.first(),
282  evaluated_positions.slice(last_segment_points));
283  }
284 }
285 
286 template<typename T>
287 static inline void linear_interpolation(const T &a, const T &b, MutableSpan<T> dst)
288 {
289  dst.first() = a;
290  const float step = 1.0f / dst.size();
291  for (const int i : dst.index_range().drop_front(1)) {
292  dst[i] = attribute_math::mix2(i * step, a, b);
293  }
294 }
295 
296 template<typename T>
298  const Span<int> evaluated_offsets,
299  MutableSpan<T> dst)
300 {
301  BLI_assert(!src.is_empty());
302  BLI_assert(evaluated_offsets.size() == src.size());
303  BLI_assert(evaluated_offsets.last() == dst.size());
304  if (src.size() == 1) {
305  BLI_assert(dst.size() == 1);
306  dst.first() = src.first();
307  return;
308  }
309 
310  linear_interpolation(src.first(), src[1], dst.take_front(evaluated_offsets.first()));
311 
313  src.index_range().drop_back(1).drop_front(1), 512, [&](IndexRange range) {
314  for (const int i : range) {
315  const IndexRange segment_points = offsets_to_range(evaluated_offsets, i - 1);
316  linear_interpolation(src[i], src[i + 1], dst.slice(segment_points));
317  }
318  });
319 
320  const IndexRange last_segment_points(evaluated_offsets.last(1),
321  evaluated_offsets.last() - evaluated_offsets.last(1));
322  linear_interpolation(src.last(), src.first(), dst.slice(last_segment_points));
323 }
324 
325 void interpolate_to_evaluated(const GSpan src, const Span<int> evaluated_offsets, GMutableSpan dst)
326 {
327  attribute_math::convert_to_static_type(src.type(), [&](auto dummy) {
328  using T = decltype(dummy);
329  if constexpr (!std::is_void_v<attribute_math::DefaultMixer<T>>) {
330  interpolate_to_evaluated(src.typed<T>(), evaluated_offsets, dst.typed<T>());
331  }
332  });
333 }
334 
335 } // namespace blender::bke::curves::bezier
Low-level operations for curves.
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define ELEM(...)
HandleType
@ BEZIER_HANDLE_ALIGN
@ BEZIER_HANDLE_VECTOR
@ BEZIER_HANDLE_AUTO
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum type
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble right
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
constexpr IndexRange drop_back(int64_t n) const
constexpr bool contains(int64_t value) const
constexpr IndexRange drop_front(int64_t n) const
constexpr int64_t size() const
Definition: BLI_span.hh:511
constexpr T & last(const int64_t n=0) const
Definition: BLI_span.hh:680
constexpr IndexRange index_range() const
Definition: BLI_span.hh:661
constexpr T & first() const
Definition: BLI_span.hh:670
constexpr MutableSpan take_front(const int64_t n) const
Definition: BLI_span.hh:620
constexpr const T & first() const
Definition: BLI_span.hh:303
constexpr const T & last(const int64_t n=0) const
Definition: BLI_span.hh:313
constexpr int64_t size() const
Definition: BLI_span.hh:240
constexpr IndexRange index_range() const
Definition: BLI_span.hh:401
SyclQueue void void * src
int len
Definition: draw_manager.c:108
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
static int left
#define T
static unsigned a[3]
Definition: RandGen.cpp:78
void convert_to_static_type(const CPPType &cpp_type, const Func &func)
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)
Definition: curve_bezier.cc:61
bool segment_is_vector(const HandleType left, const HandleType right)
Definition: BKE_curves.hh:912
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)
Definition: curve_bezier.cc:29
float3 calculate_vector_handle(const float3 &point, const float3 &next_point)
Definition: BKE_curves.hh:922
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)
Definition: curve_bezier.cc:92
static void interpolate_to_evaluated(const Span< T > src, const Span< int > evaluated_offsets, MutableSpan< T > dst)
void evaluate_segment(const float3 &point_0, const float3 &point_1, const float3 &point_2, const float3 &point_3, MutableSpan< float3 > result)
bool last_cyclic_segment_is_vector(Span< int8_t > handle_types_left, Span< int8_t > handle_types_right)
Definition: curve_bezier.cc:23
void calculate_evaluated_positions(Span< float3 > positions, Span< float3 > handles_left, Span< float3 > handles_right, Span< int > evaluated_offsets, MutableSpan< float3 > evaluated_positions)
static float3 calculate_aligned_handle(const float3 &position, const float3 &other_handle, const float3 &aligned_handle)
Definition: curve_bezier.cc:81
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 IndexRange offsets_to_range(Span< T > offsets, int64_t index)
Definition: BKE_curves.hh:29
T length(const vec_base< T, Size > &a)
T distance(const T &a, const T &b)
vec_base< T, Size > normalize(const vec_base< T, Size > &v)
T interpolate(const T &a, const T &b, const FactorT &t)
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
Definition: BLI_task.hh:51
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
MutableSpan< float3 > positions
#define min(a, b)
Definition: sort.c:35
static float3 next_position(Span< float3 > positions, const bool cyclic, const int i)