Blender  V3.3
spline_nurbs.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_virtual_array.hh"
6 
7 #include "BKE_attribute_math.hh"
8 #include "BKE_spline.hh"
9 
10 using blender::Array;
11 using blender::float3;
12 using blender::GVArray;
15 using blender::Span;
16 using blender::VArray;
17 
19 {
20  NURBSpline &nurbs = static_cast<NURBSpline &>(dst);
21  nurbs.knots_mode = knots_mode;
22  nurbs.resolution_ = resolution_;
23  nurbs.order_ = order_;
24 }
25 
26 void NURBSpline::copy_data(Spline &dst) const
27 {
28  NURBSpline &nurbs = static_cast<NURBSpline &>(dst);
29  nurbs.positions_ = positions_;
30  nurbs.weights_ = weights_;
31  nurbs.knots_ = knots_;
32  nurbs.knots_dirty_ = knots_dirty_;
33  nurbs.radii_ = radii_;
34  nurbs.tilts_ = tilts_;
35 }
36 
37 int NURBSpline::size() const
38 {
39  const int size = positions_.size();
40  BLI_assert(size == radii_.size());
41  BLI_assert(size == tilts_.size());
42  BLI_assert(size == weights_.size());
43  return size;
44 }
45 
47 {
48  return resolution_;
49 }
50 
51 void NURBSpline::set_resolution(const int value)
52 {
53  BLI_assert(value > 0);
54  resolution_ = value;
55  this->mark_cache_invalid();
56 }
57 
59 {
60  return order_;
61 }
62 
63 void NURBSpline::set_order(const uint8_t value)
64 {
65  BLI_assert(value >= 2 && value <= 6);
66  order_ = value;
67  this->mark_cache_invalid();
68 }
69 
70 void NURBSpline::resize(const int size)
71 {
72  positions_.resize(size);
73  radii_.resize(size);
74  tilts_.resize(size);
75  weights_.resize(size);
76  this->mark_cache_invalid();
77  attributes.reallocate(size);
78 }
79 
81 {
82  return positions_;
83 }
85 {
86  return positions_;
87 }
89 {
90  return radii_;
91 }
93 {
94  return radii_;
95 }
97 {
98  return tilts_;
99 }
101 {
102  return tilts_;
103 }
105 {
106  return weights_;
107 }
109 {
110  return weights_;
111 }
112 
114 {
115  this->weights().reverse();
116 }
117 
119 {
120  basis_cache_dirty_ = true;
121  position_cache_dirty_ = true;
122  tangent_cache_dirty_ = true;
123  normal_cache_dirty_ = true;
124  length_cache_dirty_ = true;
125 }
126 
128 {
129  if (!this->check_valid_num_and_order()) {
130  return 0;
131  }
132  return resolution_ * this->segments_num();
133 }
134 
136 {
137 }
138 
140 {
141  if (this->size() < order_) {
142  return false;
143  }
144 
146  if (this->knots_mode == NURBS_KNOT_MODE_BEZIER && this->size() <= order_) {
147  return false;
148  }
149  return (!is_cyclic_ || this->size() % (order_ - 1) == 0);
150  }
151 
152  return true;
153 }
154 
156 {
157  const int num = this->size() + order_;
158  return is_cyclic_ ? num + order_ - 1 : num;
159 }
160 
162 {
163  const KnotsMode mode = this->knots_mode;
164  const int order = order_;
165  const bool is_bezier = ELEM(mode, NURBS_KNOT_MODE_BEZIER, NURBS_KNOT_MODE_ENDPOINT_BEZIER);
166  const bool is_end_point = ELEM(mode, NURBS_KNOT_MODE_ENDPOINT, NURBS_KNOT_MODE_ENDPOINT_BEZIER);
167  /* Inner knots are always repeated once except on Bezier case. */
168  const int repeat_inner = is_bezier ? order - 1 : 1;
169  /* How many times to repeat 0.0 at the beginning of knot. */
170  const int head = is_end_point ? (order - (is_cyclic_ ? 1 : 0)) :
171  (is_bezier ? min_ii(2, repeat_inner) : 1);
172  /* Number of knots replicating widths of the starting knots.
173  * Covers both Cyclic and EndPoint cases. */
174  const int tail = is_cyclic_ ? 2 * order - 1 : (is_end_point ? order : 0);
175 
176  knots_.resize(this->knots_num());
177  MutableSpan<float> knots = knots_;
178 
179  int r = head;
180  float current = 0.0f;
181 
182  const int offset = is_end_point && is_cyclic_ ? 1 : 0;
183  if (offset) {
184  knots[0] = current;
185  current += 1.0f;
186  }
187 
188  for (const int i : IndexRange(offset, knots.size() - offset - tail)) {
189  knots[i] = current;
190  r--;
191  if (r == 0) {
192  current += 1.0;
193  r = repeat_inner;
194  }
195  }
196 
197  const int tail_index = knots.size() - tail;
198  for (const int i : IndexRange(tail)) {
199  knots[tail_index + i] = current + (knots[i] - knots[0]);
200  }
201 }
202 
204 {
205  if (!knots_dirty_) {
206  BLI_assert(knots_.size() == this->knots_num());
207  return knots_;
208  }
209 
210  std::lock_guard lock{knots_mutex_};
211  if (!knots_dirty_) {
212  BLI_assert(knots_.size() == this->knots_num());
213  return knots_;
214  }
215 
216  this->calculate_knots();
217 
218  knots_dirty_ = false;
219 
220  return knots_;
221 }
222 
223 static void calculate_basis_for_point(const float parameter,
224  const int num,
225  const int degree,
226  const Span<float> knots,
227  MutableSpan<float> r_weights,
228  int &r_start_index)
229 {
230  const int order = degree + 1;
231 
232  int start = 0;
233  int end = 0;
234  for (const int i : IndexRange(num + degree)) {
235  const bool knots_equal = knots[i] == knots[i + 1];
236  if (knots_equal || parameter < knots[i] || parameter > knots[i + 1]) {
237  continue;
238  }
239 
240  start = std::max(i - degree, 0);
241  end = i;
242  break;
243  }
244 
245  Array<float, 12> buffer(order * 2, 0.0f);
246 
247  buffer[end - start] = 1.0f;
248 
249  for (const int i_order : IndexRange(2, degree)) {
250  if (end + i_order >= knots.size()) {
251  end = num + degree - i_order;
252  }
253  for (const int i : IndexRange(end - start + 1)) {
254  const int knot_index = start + i;
255 
256  float new_basis = 0.0f;
257  if (buffer[i] != 0.0f) {
258  new_basis += ((parameter - knots[knot_index]) * buffer[i]) /
259  (knots[knot_index + i_order - 1] - knots[knot_index]);
260  }
261 
262  if (buffer[i + 1] != 0.0f) {
263  new_basis += ((knots[knot_index + i_order] - parameter) * buffer[i + 1]) /
264  (knots[knot_index + i_order] - knots[knot_index + 1]);
265  }
266 
267  buffer[i] = new_basis;
268  }
269  }
270 
271  buffer.as_mutable_span().drop_front(end - start + 1).fill(0.0f);
272  r_weights.copy_from(buffer.as_span().take_front(order));
273  r_start_index = start;
274 }
275 
277 {
278  if (!basis_cache_dirty_) {
279  return basis_cache_;
280  }
281 
282  std::lock_guard lock{basis_cache_mutex_};
283  if (!basis_cache_dirty_) {
284  return basis_cache_;
285  }
286 
287  const int num = this->size();
288  const int eval_num = this->evaluated_points_num();
289 
290  const int order = this->order();
291  const int degree = order - 1;
292 
293  basis_cache_.weights.resize(eval_num * order);
294  basis_cache_.start_indices.resize(eval_num);
295 
296  if (eval_num == 0) {
297  return basis_cache_;
298  }
299 
300  MutableSpan<float> basis_weights(basis_cache_.weights);
301  MutableSpan<int> basis_start_indices(basis_cache_.start_indices);
302 
303  const Span<float> control_weights = this->weights();
304  const Span<float> knots = this->knots();
305 
306  const int last_control_point_index = is_cyclic_ ? num + degree : num;
307 
308  const float start = knots[degree];
309  const float end = knots[last_control_point_index];
310  const float step = (end - start) / this->evaluated_edges_num();
311  for (const int i : IndexRange(eval_num)) {
312  /* Clamp parameter due to floating point inaccuracy. */
313  const float parameter = std::clamp(start + step * i, knots[0], knots[num + degree]);
314 
315  MutableSpan<float> point_weights = basis_weights.slice(i * order, order);
316 
318  parameter, last_control_point_index, degree, knots, point_weights, basis_start_indices[i]);
319 
320  for (const int j : point_weights.index_range()) {
321  const int point_index = (basis_start_indices[i] + j) % num;
322  point_weights[j] *= control_weights[point_index];
323  }
324  }
325 
326  basis_cache_dirty_ = false;
327  return basis_cache_;
328 }
329 
330 template<typename T>
332  const int order,
333  const blender::VArray<T> &src,
334  MutableSpan<T> dst)
335 {
336  const int num = src.size();
338 
339  for (const int i : dst.index_range()) {
340  Span<float> point_weights = basis_cache.weights.as_span().slice(i * order, order);
341  const int start_index = basis_cache.start_indices[i];
342 
343  for (const int j : point_weights.index_range()) {
344  const int point_index = (start_index + j) % num;
345  mixer.mix_in(i, src[point_index], point_weights[j]);
346  }
347  }
348 
349  mixer.finalize();
350 }
351 
353 {
354  BLI_assert(src.size() == this->size());
355 
356  if (src.is_single()) {
357  return src;
358  }
359 
360  const BasisCache &basis_cache = this->calculate_basis_cache();
361 
362  GVArray new_varray;
363  blender::attribute_math::convert_to_static_type(src.type(), [&](auto dummy) {
364  using T = decltype(dummy);
365  if constexpr (!std::is_void_v<blender::attribute_math::DefaultMixer<T>>) {
366  Array<T> values(this->evaluated_points_num());
367  interpolate_to_evaluated_impl<T>(basis_cache, this->order(), src.typed<T>(), values);
368  new_varray = VArray<T>::ForContainer(std::move(values));
369  }
370  });
371 
372  return new_varray;
373 }
374 
376 {
377  if (!position_cache_dirty_) {
378  return evaluated_position_cache_;
379  }
380 
381  std::lock_guard lock{position_cache_mutex_};
382  if (!position_cache_dirty_) {
383  return evaluated_position_cache_;
384  }
385 
386  const int eval_num = this->evaluated_points_num();
387  evaluated_position_cache_.resize(eval_num);
388 
389  /* TODO: Avoid copying the evaluated data from the temporary array. */
390  VArray<float3> evaluated = Spline::interpolate_to_evaluated(positions_.as_span());
391  evaluated.materialize(evaluated_position_cache_);
392 
393  position_cache_dirty_ = false;
394  return evaluated_position_cache_;
395 }
#define BLI_assert(a)
Definition: BLI_assert.h:46
MINLINE int min_ii(int a, int b)
#define ELEM(...)
KnotsMode
@ NURBS_KNOT_MODE_ENDPOINT
@ NURBS_KNOT_MODE_BEZIER
@ NURBS_KNOT_MODE_ENDPOINT_BEZIER
_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 GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble GLdouble r _GL_VOID_RET _GL_VOID GLfloat GLfloat r _GL_VOID_RET _GL_VOID GLint GLint r _GL_VOID_RET _GL_VOID GLshort GLshort r _GL_VOID_RET _GL_VOID GLdouble GLdouble r
_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 GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint order
volatile int lock
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
void reverse_impl() override
int knots_num() const
void calculate_knots() const
void resize(int size) final
Definition: spline_nurbs.cc:70
int size() const final
Definition: spline_nurbs.cc:37
blender::MutableSpan< float > weights()
int resolution() const
Definition: spline_nurbs.cc:46
bool check_valid_num_and_order() const
KnotsMode knots_mode
Definition: BKE_spline.hh:446
void copy_data(Spline &dst) const final
Definition: spline_nurbs.cc:26
blender::MutableSpan< float > tilts() final
Definition: spline_nurbs.cc:96
blender::MutableSpan< blender::float3 > positions() final
Definition: spline_nurbs.cc:80
void set_order(uint8_t value)
Definition: spline_nurbs.cc:63
uint8_t order() const
Definition: spline_nurbs.cc:58
void mark_cache_invalid() final
blender::Span< float > knots() const
void correct_end_tangents() const final
const BasisCache & calculate_basis_cache() const
blender::MutableSpan< float > radii() final
Definition: spline_nurbs.cc:88
void set_resolution(int value)
Definition: spline_nurbs.cc:51
blender::Span< blender::float3 > evaluated_positions() const final
void copy_settings(Spline &dst) const final
Definition: spline_nurbs.cc:18
blender::GVArray interpolate_to_evaluated(const blender::GVArray &src) const final
int evaluated_points_num() const final
int evaluated_edges_num() const
Definition: spline_base.cc:119
bool tangent_cache_dirty_
Definition: BKE_spline.hh:65
bool is_cyclic_
Definition: BKE_spline.hh:60
blender::bke::CustomDataAttributes attributes
Definition: BKE_spline.hh:56
virtual blender::GVArray interpolate_to_evaluated(const blender::GVArray &src) const =0
bool normal_cache_dirty_
Definition: BKE_spline.hh:70
bool length_cache_dirty_
Definition: BKE_spline.hh:75
int segments_num() const
Definition: spline_base.cc:136
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition: BLI_span.hh:581
constexpr void copy_from(Span< T > values)
Definition: BLI_span.hh:707
constexpr IndexRange index_range() const
Definition: BLI_span.hh:661
constexpr Span slice(int64_t start, int64_t size) const
Definition: BLI_span.hh:142
constexpr int64_t size() const
Definition: BLI_span.hh:240
constexpr IndexRange index_range() const
Definition: BLI_span.hh:401
void materialize(MutableSpan< T > r_span) const
int64_t size() const
Definition: BLI_vector.hh:694
Span< T > as_span() const
Definition: BLI_vector.hh:325
void resize(const int64_t new_size)
Definition: BLI_vector.hh:353
SyclQueue void void * src
ccl_global float * buffer
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
typename DefaultMixerStruct< T >::type DefaultMixer
void convert_to_static_type(const CPPType &cpp_type, const Func &func)
T clamp(const T &a, const T &min, const T &max)
vec_base< float, 3 > float3
void interpolate_to_evaluated_impl(const NURBSpline::BasisCache &basis_cache, const int order, const blender::VArray< T > &src, MutableSpan< T > dst)
static void calculate_basis_for_point(const float parameter, const int num, const int degree, const Span< float > knots, MutableSpan< float > r_weights, int &r_start_index)
unsigned char uint8_t
Definition: stdint.h:78
blender::Vector< int > start_indices
Definition: BKE_spline.hh:457
blender::Vector< float > weights
Definition: BKE_spline.hh:453
float max