Blender  V3.3
spline_bezier.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #include "BLI_array.hh"
4 #include "BLI_span.hh"
5 #include "BLI_task.hh"
6 
7 #include "BKE_spline.hh"
8 
9 using blender::Array;
10 using blender::float3;
11 using blender::GVArray;
14 using blender::Span;
15 using blender::VArray;
16 
17 void BezierSpline::copy_settings(Spline &dst) const
18 {
19  BezierSpline &bezier = static_cast<BezierSpline &>(dst);
20  bezier.resolution_ = resolution_;
21 }
22 
23 void BezierSpline::copy_data(Spline &dst) const
24 {
25  BezierSpline &bezier = static_cast<BezierSpline &>(dst);
26  bezier.positions_ = positions_;
27  bezier.handle_types_left_ = handle_types_left_;
28  bezier.handle_positions_left_ = handle_positions_left_;
29  bezier.handle_types_right_ = handle_types_right_;
30  bezier.handle_positions_right_ = handle_positions_right_;
31  bezier.radii_ = radii_;
32  bezier.tilts_ = tilts_;
33 }
34 
35 int BezierSpline::size() const
36 {
37  const int size = positions_.size();
38  BLI_assert(size == handle_types_left_.size());
39  BLI_assert(size == handle_positions_left_.size());
40  BLI_assert(size == handle_types_right_.size());
41  BLI_assert(size == handle_positions_right_.size());
42  BLI_assert(size == radii_.size());
43  BLI_assert(size == tilts_.size());
44  return size;
45 }
46 
48 {
49  return resolution_;
50 }
51 
52 void BezierSpline::set_resolution(const int value)
53 {
54  BLI_assert(value > 0);
55  resolution_ = value;
56  this->mark_cache_invalid();
57 }
58 
59 void BezierSpline::resize(const int size)
60 {
61  handle_types_left_.resize(size);
62  handle_positions_left_.resize(size);
63  positions_.resize(size);
64  handle_types_right_.resize(size);
65  handle_positions_right_.resize(size);
66  radii_.resize(size);
67  tilts_.resize(size);
68  this->mark_cache_invalid();
69  attributes.reallocate(size);
70 }
71 
73 {
74  return positions_;
75 }
77 {
78  return positions_;
79 }
81 {
82  return radii_;
83 }
85 {
86  return radii_;
87 }
89 {
90  return tilts_;
91 }
93 {
94  return tilts_;
95 }
97 {
98  return handle_types_left_;
99 }
101 {
102  return handle_types_left_;
103 }
105 {
106  this->ensure_auto_handles();
107  return handle_positions_left_;
108 }
110 {
111  if (!write_only) {
112  this->ensure_auto_handles();
113  }
114  return handle_positions_left_;
115 }
116 
118 {
119  return handle_types_right_;
120 }
122 {
123  return handle_types_right_;
124 }
126 {
127  this->ensure_auto_handles();
128  return handle_positions_right_;
129 }
131 {
132  if (!write_only) {
133  this->ensure_auto_handles();
134  }
135  return handle_positions_right_;
136 }
137 
139 {
140  this->handle_positions_left().reverse();
141  this->handle_positions_right().reverse();
142  std::swap(this->handle_positions_left_, this->handle_positions_right_);
143 
144  this->handle_types_left().reverse();
145  this->handle_types_right().reverse();
146  std::swap(this->handle_types_left_, this->handle_types_right_);
147 }
148 
149 static float3 previous_position(Span<float3> positions, const bool cyclic, const int i)
150 {
151  if (i == 0) {
152  if (cyclic) {
153  return positions[positions.size() - 1];
154  }
155  return 2.0f * positions[i] - positions[i + 1];
156  }
157  return positions[i - 1];
158 }
159 
160 static float3 next_position(Span<float3> positions, const bool cyclic, const int i)
161 {
162  if (i == positions.size() - 1) {
163  if (cyclic) {
164  return positions[0];
165  }
166  return 2.0f * positions[i] - positions[i - 1];
167  }
168  return positions[i + 1];
169 }
170 
172 {
173  if (!auto_handles_dirty_) {
174  return;
175  }
176 
177  std::lock_guard lock{auto_handle_mutex_};
178  if (!auto_handles_dirty_) {
179  return;
180  }
181 
182  if (this->size() == 1) {
183  auto_handles_dirty_ = false;
184  return;
185  }
186 
187  for (const int i : IndexRange(this->size())) {
188  using namespace blender;
189 
190  if (ELEM(BEZIER_HANDLE_AUTO, handle_types_left_[i], handle_types_right_[i])) {
191  const float3 prev_diff = positions_[i] - previous_position(positions_, is_cyclic_, i);
192  const float3 next_diff = next_position(positions_, is_cyclic_, i) - positions_[i];
193  float prev_len = math::length(prev_diff);
194  float next_len = math::length(next_diff);
195  if (prev_len == 0.0f) {
196  prev_len = 1.0f;
197  }
198  if (next_len == 0.0f) {
199  next_len = 1.0f;
200  }
201  const float3 dir = next_diff / next_len + prev_diff / prev_len;
202 
203  /* This magic number is unfortunate, but comes from elsewhere in Blender. */
204  const float len = math::length(dir) * 2.5614f;
205  if (len != 0.0f) {
206  if (handle_types_left_[i] == BEZIER_HANDLE_AUTO) {
207  const float prev_len_clamped = std::min(prev_len, next_len * 5.0f);
208  handle_positions_left_[i] = positions_[i] + dir * -(prev_len_clamped / len);
209  }
210  if (handle_types_right_[i] == BEZIER_HANDLE_AUTO) {
211  const float next_len_clamped = std::min(next_len, prev_len * 5.0f);
212  handle_positions_right_[i] = positions_[i] + dir * (next_len_clamped / len);
213  }
214  }
215  }
216 
217  if (handle_types_left_[i] == BEZIER_HANDLE_VECTOR) {
218  const float3 prev = previous_position(positions_, is_cyclic_, i);
219  handle_positions_left_[i] = math::interpolate(positions_[i], prev, 1.0f / 3.0f);
220  }
221 
222  if (handle_types_right_[i] == BEZIER_HANDLE_VECTOR) {
223  const float3 next = next_position(positions_, is_cyclic_, i);
224  handle_positions_right_[i] = math::interpolate(positions_[i], next, 1.0f / 3.0f);
225  }
226  }
227 
228  auto_handles_dirty_ = false;
229 }
230 
231 void BezierSpline::translate(const blender::float3 &translation)
232 {
233  for (float3 &position : this->positions()) {
234  position += translation;
235  }
236  for (float3 &handle_position : this->handle_positions_left()) {
237  handle_position += translation;
238  }
239  for (float3 &handle_position : this->handle_positions_right()) {
240  handle_position += translation;
241  }
242  this->mark_cache_invalid();
243 }
244 
246 {
247  for (float3 &position : this->positions()) {
248  position = matrix * position;
249  }
250  for (float3 &handle_position : this->handle_positions_left()) {
251  handle_position = matrix * handle_position;
252  }
253  for (float3 &handle_position : this->handle_positions_right()) {
254  handle_position = matrix * handle_position;
255  }
256  this->mark_cache_invalid();
257 }
258 
259 static void set_handle_position(const float3 &position,
260  const HandleType type,
261  const HandleType type_other,
262  const float3 &new_value,
263  float3 &handle,
264  float3 &handle_other)
265 {
266  using namespace blender::math;
267 
268  /* Don't bother when the handle positions are calculated automatically anyway. */
270  return;
271  }
272 
273  handle = new_value;
274  if (type_other == BEZIER_HANDLE_ALIGN) {
275  /* Keep track of the old length of the opposite handle. */
276  const float length = distance(handle_other, position);
277  /* Set the other handle to directly opposite from the current handle. */
278  const float3 dir = normalize(handle - position);
279  handle_other = position - dir * length;
280  }
281 }
282 
283 void BezierSpline::set_handle_position_right(const int index, const blender::float3 &value)
284 {
285  set_handle_position(positions_[index],
286  static_cast<HandleType>(handle_types_right_[index]),
287  static_cast<HandleType>(handle_types_left_[index]),
288  value,
289  handle_positions_right_[index],
290  handle_positions_left_[index]);
291 }
292 
293 void BezierSpline::set_handle_position_left(const int index, const blender::float3 &value)
294 {
295  set_handle_position(positions_[index],
296  static_cast<HandleType>(handle_types_right_[index]),
297  static_cast<HandleType>(handle_types_left_[index]),
298  value,
299  handle_positions_left_[index],
300  handle_positions_right_[index]);
301 }
302 
303 bool BezierSpline::point_is_sharp(const int index) const
304 {
305  return ELEM(handle_types_left_[index], BEZIER_HANDLE_VECTOR, BEZIER_HANDLE_FREE) ||
306  ELEM(handle_types_right_[index], BEZIER_HANDLE_VECTOR, BEZIER_HANDLE_FREE);
307 }
308 
309 bool BezierSpline::segment_is_vector(const int index) const
310 {
311  /* Two control points are necessary to form a segment, that should be checked by the caller. */
312  BLI_assert(this->size() > 1);
313 
314  if (index == this->size() - 1) {
315  if (is_cyclic_) {
316  return handle_types_right_.last() == BEZIER_HANDLE_VECTOR &&
317  handle_types_left_.first() == BEZIER_HANDLE_VECTOR;
318  }
319  /* There is actually no segment in this case, but it's nice to avoid
320  * having a special case for the last segment in calling code. */
321  return true;
322  }
323  return handle_types_right_[index] == BEZIER_HANDLE_VECTOR &&
324  handle_types_left_[index + 1] == BEZIER_HANDLE_VECTOR;
325 }
326 
328 {
329  offset_cache_dirty_ = true;
330  position_cache_dirty_ = true;
331  mapping_cache_dirty_ = true;
332  tangent_cache_dirty_ = true;
333  normal_cache_dirty_ = true;
334  length_cache_dirty_ = true;
335  auto_handles_dirty_ = true;
336 }
337 
339 {
340  BLI_assert(this->size() > 0);
341  return this->control_point_offsets().last();
342 }
343 
344 void BezierSpline::correct_end_tangents() const
345 {
346  using namespace blender::math;
347  if (is_cyclic_) {
348  return;
349  }
350 
352 
353  if (handle_positions_right_.first() != positions_.first()) {
354  tangents.first() = normalize(handle_positions_right_.first() - positions_.first());
355  }
356  if (handle_positions_left_.last() != positions_.last()) {
357  tangents.last() = normalize(positions_.last() - handle_positions_left_.last());
358  }
359 }
360 
362  const int next_index,
363  const float parameter)
364 {
365  using namespace blender::math;
366 
367  BLI_assert(parameter <= 1.0f && parameter >= 0.0f);
368  BLI_assert(ELEM(next_index, 0, index + 1));
369  const float3 &point_prev = positions_[index];
370  const float3 &handle_prev = handle_positions_right_[index];
371  const float3 &handle_next = handle_positions_left_[next_index];
372  const float3 &point_next = positions_[next_index];
373  const float3 center_point = interpolate(handle_prev, handle_next, parameter);
374 
376  result.handle_prev = interpolate(point_prev, handle_prev, parameter);
377  result.handle_next = interpolate(handle_next, point_next, parameter);
378  result.left_handle = interpolate(result.handle_prev, center_point, parameter);
379  result.right_handle = interpolate(center_point, result.handle_next, parameter);
380  result.position = interpolate(result.left_handle, result.right_handle, parameter);
381  return result;
382 }
383 
384 static void bezier_forward_difference_3d(const float3 &point_0,
385  const float3 &point_1,
386  const float3 &point_2,
387  const float3 &point_3,
389 {
390  BLI_assert(result.size() > 0);
391  const float inv_len = 1.0f / static_cast<float>(result.size());
392  const float inv_len_squared = inv_len * inv_len;
393  const float inv_len_cubed = inv_len_squared * inv_len;
394 
395  const float3 rt1 = 3.0f * (point_1 - point_0) * inv_len;
396  const float3 rt2 = 3.0f * (point_0 - 2.0f * point_1 + point_2) * inv_len_squared;
397  const float3 rt3 = (point_3 - point_0 + 3.0f * (point_1 - point_2)) * inv_len_cubed;
398 
399  float3 q0 = point_0;
400  float3 q1 = rt1 + rt2 + rt3;
401  float3 q2 = 2.0f * rt2 + 6.0f * rt3;
402  float3 q3 = 6.0f * rt3;
403  for (const int i : result.index_range()) {
404  result[i] = q0;
405  q0 += q1;
406  q1 += q2;
407  q2 += q3;
408  }
409 }
410 
411 void BezierSpline::evaluate_segment(const int index,
412  const int next_index,
414 {
415  if (this->segment_is_vector(index)) {
416  BLI_assert(positions.size() == 1);
417  positions.first() = positions_[index];
418  }
419  else {
420  bezier_forward_difference_3d(positions_[index],
421  handle_positions_right_[index],
422  handle_positions_left_[next_index],
423  positions_[next_index],
424  positions);
425  }
426 }
427 
429 {
430  if (!offset_cache_dirty_) {
431  return offset_cache_;
432  }
433 
434  std::lock_guard lock{offset_cache_mutex_};
435  if (!offset_cache_dirty_) {
436  return offset_cache_;
437  }
438 
439  const int size = this->size();
440  offset_cache_.resize(size + 1);
441 
442  MutableSpan<int> offsets = offset_cache_;
443  if (size == 1) {
444  offsets.first() = 0;
445  offsets.last() = 1;
446  }
447  else {
448  int offset = 0;
449  for (const int i : IndexRange(size)) {
450  offsets[i] = offset;
451  offset += this->segment_is_vector(i) ? 1 : resolution_;
452  }
453  offsets.last() = offset;
454  }
455 
456  offset_cache_dirty_ = false;
457  return offsets;
458 }
459 
461  const int size,
462  const int resolution,
463  const bool is_cyclic,
464  MutableSpan<float> r_mappings)
465 {
466  const float first_segment_len_inv = 1.0f / offsets[1];
467  for (const int i : IndexRange(0, offsets[1])) {
468  r_mappings[i] = i * first_segment_len_inv;
469  }
470 
471  const int grain_size = std::max(2048 / resolution, 1);
472  blender::threading::parallel_for(IndexRange(1, size - 2), grain_size, [&](IndexRange range) {
473  for (const int i_control_point : range) {
474  const int segment_len = offsets[i_control_point + 1] - offsets[i_control_point];
475  const float segment_len_inv = 1.0f / segment_len;
476  for (const int i : IndexRange(segment_len)) {
477  r_mappings[offsets[i_control_point] + i] = i_control_point + i * segment_len_inv;
478  }
479  }
480  });
481 
482  if (is_cyclic) {
483  const int last_segment_len = offsets[size] - offsets[size - 1];
484  const float last_segment_len_inv = 1.0f / last_segment_len;
485  for (const int i : IndexRange(last_segment_len)) {
486  r_mappings[offsets[size - 1] + i] = size - 1 + i * last_segment_len_inv;
487  }
488  }
489  else {
490  r_mappings.last() = size - 1;
491  }
492 }
493 
495 {
496  if (!mapping_cache_dirty_) {
497  return evaluated_mapping_cache_;
498  }
499 
500  std::lock_guard lock{mapping_cache_mutex_};
501  if (!mapping_cache_dirty_) {
502  return evaluated_mapping_cache_;
503  }
504 
505  const int num = this->size();
506  const int eval_num = this->evaluated_points_num();
507  evaluated_mapping_cache_.resize(eval_num);
508  MutableSpan<float> mappings = evaluated_mapping_cache_;
509 
510  if (eval_num == 1) {
511  mappings.first() = 0.0f;
512  mapping_cache_dirty_ = false;
513  return mappings;
514  }
515 
516  Span<int> offsets = this->control_point_offsets();
517 
519  /* Isolate the task, since this is function is multi-threaded and holds a lock. */
520  calculate_mappings_linear_resolution(offsets, num, resolution_, is_cyclic_, mappings);
521  });
522 
523  mapping_cache_dirty_ = false;
524  return mappings;
525 }
526 
528 {
529  if (!position_cache_dirty_) {
530  return evaluated_position_cache_;
531  }
532 
533  std::lock_guard lock{position_cache_mutex_};
534  if (!position_cache_dirty_) {
535  return evaluated_position_cache_;
536  }
537 
538  const int num = this->size();
539  const int eval_num = this->evaluated_points_num();
540  evaluated_position_cache_.resize(eval_num);
541 
542  MutableSpan<float3> positions = evaluated_position_cache_;
543 
544  if (num == 1) {
545  /* Use a special case for single point splines to avoid checking in #evaluate_segment. */
546  BLI_assert(eval_num == 1);
547  positions.first() = positions_.first();
548  position_cache_dirty_ = false;
549  return positions;
550  }
551 
552  this->ensure_auto_handles();
553 
554  Span<int> offsets = this->control_point_offsets();
555 
556  const int grain_size = std::max(512 / resolution_, 1);
558  /* Isolate the task, since this is function is multi-threaded and holds a lock. */
559  blender::threading::parallel_for(IndexRange(num - 1), grain_size, [&](IndexRange range) {
560  for (const int i : range) {
561  this->evaluate_segment(i, i + 1, positions.slice(offsets[i], offsets[i + 1] - offsets[i]));
562  }
563  });
564  });
565  if (is_cyclic_) {
566  this->evaluate_segment(
567  num - 1, 0, positions.slice(offsets[num - 1], offsets[num] - offsets[num - 1]));
568  }
569  else {
570  /* Since evaluating the bezier segment doesn't add the final point,
571  * it must be added manually in the non-cyclic case. */
572  positions.last() = positions_.last();
573  }
574 
575  position_cache_dirty_ = false;
576  return positions;
577 }
578 
580  const float index_factor) const
581 {
582  const int num = this->size();
583 
584  if (is_cyclic_) {
585  if (index_factor < num) {
586  const int index = std::floor(index_factor);
587  const int next_index = (index < num - 1) ? index + 1 : 0;
588  return InterpolationData{index, next_index, index_factor - index};
589  }
590  return InterpolationData{num - 1, 0, 1.0f};
591  }
592 
593  if (index_factor < num - 1) {
594  const int index = std::floor(index_factor);
595  const int next_index = index + 1;
596  return InterpolationData{index, next_index, index_factor - index};
597  }
598  return InterpolationData{num - 2, num - 1, 1.0f};
599 }
600 
601 /* Use a spline argument to avoid adding this to the header. */
602 template<typename T>
603 static void interpolate_to_evaluated_impl(const BezierSpline &spline,
604  const blender::VArray<T> &src,
605  MutableSpan<T> dst)
606 {
607  BLI_assert(src.size() == spline.size());
608  BLI_assert(dst.size() == spline.evaluated_points_num());
609  Span<float> mappings = spline.evaluated_mappings();
610 
611  for (const int i : dst.index_range()) {
613  mappings[i]);
614 
615  const T &value = src[interp.control_point_index];
616  const T &next_value = src[interp.next_control_point_index];
617 
618  dst[i] = blender::attribute_math::mix2(interp.factor, value, next_value);
619  }
620 }
621 
623 {
624  BLI_assert(src.size() == this->size());
625 
626  if (src.is_single()) {
627  return src;
628  }
629 
630  const int eval_num = this->evaluated_points_num();
631  if (eval_num == 1) {
632  return src;
633  }
634 
635  GVArray new_varray;
636  blender::attribute_math::convert_to_static_type(src.type(), [&](auto dummy) {
637  using T = decltype(dummy);
638  if constexpr (!std::is_void_v<blender::attribute_math::DefaultMixer<T>>) {
639  Array<T> values(eval_num);
640  interpolate_to_evaluated_impl<T>(*this, src.typed<T>(), values);
641  new_varray = VArray<T>::ForContainer(std::move(values));
642  }
643  });
644 
645  return new_varray;
646 }
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define ELEM(...)
void swap(T &a, T &b)
Definition: Common.h:19
HandleType
@ BEZIER_HANDLE_FREE
@ BEZIER_HANDLE_ALIGN
@ BEZIER_HANDLE_VECTOR
@ BEZIER_HANDLE_AUTO
volatile int lock
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
int size() const final
blender::MutableSpan< float > tilts() final
blender::Span< blender::float3 > handle_positions_right() const
bool segment_is_vector(int start_index) const
blender::Span< float > evaluated_mappings() const
void resize(int size) final
blender::Span< blender::float3 > handle_positions_left() const
void set_handle_position_left(int index, const blender::float3 &value)
void transform(const blender::float4x4 &matrix) override
void evaluate_segment(int index, int next_index, blender::MutableSpan< blender::float3 > positions) const
InsertResult calculate_segment_insertion(int index, int next_index, float parameter)
int evaluated_points_num() const final
blender::Span< int8_t > handle_types_left() const
void ensure_auto_handles() const
InterpolationData interpolation_data_from_index_factor(float index_factor) const
blender::Span< int > control_point_offsets() const
void translate(const blender::float3 &translation) override
int resolution() const
virtual blender::GVArray interpolate_to_evaluated(const blender::GVArray &src) const override
bool point_is_sharp(int index) const
void mark_cache_invalid() final
void set_resolution(int value)
blender::Span< int8_t > handle_types_right() const
blender::Span< blender::float3 > evaluated_positions() const final
void set_handle_position_right(int index, const blender::float3 &value)
void reverse_impl() override
blender::MutableSpan< blender::float3 > positions() final
blender::MutableSpan< float > radii() final
CurveType type() const
Definition: spline_base.cc:25
bool tangent_cache_dirty_
Definition: BKE_spline.hh:65
blender::Vector< blender::float3 > evaluated_tangents_cache_
Definition: BKE_spline.hh:63
bool is_cyclic_
Definition: BKE_spline.hh:60
float length() const
Definition: spline_base.cc:130
blender::bke::CustomDataAttributes attributes
Definition: BKE_spline.hh:56
bool is_cyclic() const
Definition: spline_base.cc:143
bool normal_cache_dirty_
Definition: BKE_spline.hh:70
bool length_cache_dirty_
Definition: BKE_spline.hh:75
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 const T & last(const int64_t n=0) const
Definition: BLI_span.hh:313
int64_t size() const
Definition: BLI_vector.hh:694
const T & last(const int64_t n=0) const
Definition: BLI_vector.hh:663
void resize(const int64_t new_size)
Definition: BLI_vector.hh:353
const T & first() const
Definition: BLI_vector.hh:680
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
ccl_device_inline float2 interp(const float2 &a, const float2 &b, float t)
Definition: math_float2.h:232
static ulong * next
#define T
void convert_to_static_type(const CPPType &cpp_type, const Func &func)
T mix2(float factor, const T &a, const T &b)
void interpolate(const Span< T > src, const Span< int > indices, const Span< float > factors, MutableSpan< T > dst)
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 floor(const T &a)
SymEdge< T > * prev(const SymEdge< T > *se)
Definition: delaunay_2d.cc:105
void isolate_task(const Function &function)
Definition: BLI_task.hh:125
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
Definition: BLI_task.hh:51
vec_base< float, 3 > float3
MutableSpan< float3 > positions
MutableSpan< float3 > tangents
#define min(a, b)
Definition: sort.c:35
static void calculate_mappings_linear_resolution(Span< int > offsets, const int size, const int resolution, const bool is_cyclic, MutableSpan< float > r_mappings)
static void bezier_forward_difference_3d(const float3 &point_0, const float3 &point_1, const float3 &point_2, const float3 &point_3, MutableSpan< float3 > result)
static float3 next_position(Span< float3 > positions, const bool cyclic, const int i)
static void set_handle_position(const float3 &position, const HandleType type, const HandleType type_other, const float3 &new_value, float3 &handle, float3 &handle_other)
static float3 previous_position(Span< float3 > positions, const bool cyclic, const int i)
static void interpolate_to_evaluated_impl(const BezierSpline &spline, const blender::VArray< T > &src, MutableSpan< T > dst)
float max