Blender  V3.3
curve_nurbs.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
7 #include "BKE_attribute_math.hh"
8 
9 #include "BKE_curves.hh"
10 
12 
13 bool check_valid_num_and_order(const int points_num,
14  const int8_t order,
15  const bool cyclic,
16  const KnotsMode knots_mode)
17 {
18  if (points_num < order) {
19  return false;
20  }
21 
23  if (knots_mode == NURBS_KNOT_MODE_BEZIER && points_num <= order) {
24  return false;
25  }
26  return (!cyclic || points_num % (order - 1) == 0);
27  }
28 
29  return true;
30 }
31 
32 int calculate_evaluated_num(const int points_num,
33  const int8_t order,
34  const bool cyclic,
35  const int resolution,
36  const KnotsMode knots_mode)
37 {
38  if (!check_valid_num_and_order(points_num, order, cyclic, knots_mode)) {
39  return points_num;
40  }
41  return resolution * segments_num(points_num, cyclic);
42 }
43 
44 int knots_num(const int points_num, const int8_t order, const bool cyclic)
45 {
46  if (cyclic) {
47  return points_num + order * 2 - 1;
48  }
49  return points_num + order;
50 }
51 
52 void calculate_knots(const int points_num,
53  const KnotsMode mode,
54  const int8_t order,
55  const bool cyclic,
56  MutableSpan<float> knots)
57 {
58  BLI_assert(knots.size() == knots_num(points_num, order, cyclic));
59  UNUSED_VARS_NDEBUG(points_num);
60 
61  const bool is_bezier = ELEM(mode, NURBS_KNOT_MODE_BEZIER, NURBS_KNOT_MODE_ENDPOINT_BEZIER);
62  const bool is_end_point = ELEM(mode, NURBS_KNOT_MODE_ENDPOINT, NURBS_KNOT_MODE_ENDPOINT_BEZIER);
63  /* Inner knots are always repeated once except on Bezier case. */
64  const int repeat_inner = is_bezier ? order - 1 : 1;
65  /* How many times to repeat 0.0 at the beginning of knot. */
66  const int head = is_end_point ? (order - (cyclic ? 1 : 0)) :
67  (is_bezier ? min_ii(2, repeat_inner) : 1);
68  /* Number of knots replicating widths of the starting knots.
69  * Covers both Cyclic and EndPoint cases. */
70  const int tail = cyclic ? 2 * order - 1 : (is_end_point ? order : 0);
71 
72  int r = head;
73  float current = 0.0f;
74 
75  const int offset = is_end_point && cyclic ? 1 : 0;
76  if (offset) {
77  knots[0] = current;
78  current += 1.0f;
79  }
80 
81  for (const int i : IndexRange(offset, knots.size() - offset - tail)) {
82  knots[i] = current;
83  r--;
84  if (r == 0) {
85  current += 1.0;
86  r = repeat_inner;
87  }
88  }
89 
90  const int tail_index = knots.size() - tail;
91  for (const int i : IndexRange(tail)) {
92  knots[tail_index + i] = current + (knots[i] - knots[0]);
93  }
94 }
95 
96 static void calculate_basis_for_point(const float parameter,
97  const int points_num,
98  const int degree,
99  const Span<float> knots,
100  MutableSpan<float> r_weights,
101  int &r_start_index)
102 {
103  const int order = degree + 1;
104 
105  int start = 0;
106  int end = 0;
107  for (const int i : IndexRange(points_num + degree)) {
108  const bool knots_equal = knots[i] == knots[i + 1];
109  if (knots_equal || parameter < knots[i] || parameter > knots[i + 1]) {
110  continue;
111  }
112 
113  start = std::max(i - degree, 0);
114  end = i;
115  break;
116  }
117 
118  Array<float, 12> buffer(order * 2, 0.0f);
119 
120  buffer[end - start] = 1.0f;
121 
122  for (const int i_order : IndexRange(2, degree)) {
123  if (end + i_order >= knots.size()) {
124  end = points_num + degree - i_order;
125  }
126  for (const int i : IndexRange(end - start + 1)) {
127  const int knot_index = start + i;
128 
129  float new_basis = 0.0f;
130  if (buffer[i] != 0.0f) {
131  new_basis += ((parameter - knots[knot_index]) * buffer[i]) /
132  (knots[knot_index + i_order - 1] - knots[knot_index]);
133  }
134 
135  if (buffer[i + 1] != 0.0f) {
136  new_basis += ((knots[knot_index + i_order] - parameter) * buffer[i + 1]) /
137  (knots[knot_index + i_order] - knots[knot_index + 1]);
138  }
139 
140  buffer[i] = new_basis;
141  }
142  }
143 
144  buffer.as_mutable_span().drop_front(end - start + 1).fill(0.0f);
145  r_weights.copy_from(buffer.as_span().take_front(order));
146  r_start_index = start;
147 }
148 
149 void calculate_basis_cache(const int points_num,
150  const int evaluated_num,
151  const int8_t order,
152  const bool cyclic,
153  const Span<float> knots,
154  BasisCache &basis_cache)
155 {
156  BLI_assert(points_num > 0);
157 
158  const int8_t degree = order - 1;
159 
160  basis_cache.weights.resize(evaluated_num * order);
161  basis_cache.start_indices.resize(evaluated_num);
162 
163  if (evaluated_num == 0) {
164  return;
165  }
166 
167  MutableSpan<float> basis_weights(basis_cache.weights);
168  MutableSpan<int> basis_start_indices(basis_cache.start_indices);
169 
170  const int last_control_point_index = cyclic ? points_num + degree : points_num;
171  const int evaluated_segment_num = segments_num(evaluated_num, cyclic);
172 
173  const float start = knots[degree];
174  const float end = knots[last_control_point_index];
175  const float step = (end - start) / evaluated_segment_num;
176  for (const int i : IndexRange(evaluated_num)) {
177  /* Clamp parameter due to floating point inaccuracy. */
178  const float parameter = std::clamp(start + step * i, knots[0], knots[points_num + degree]);
179 
180  MutableSpan<float> point_weights = basis_weights.slice(i * order, order);
181 
183  parameter, last_control_point_index, degree, knots, point_weights, basis_start_indices[i]);
184  }
185 }
186 
187 template<typename T>
188 static void interpolate_to_evaluated(const BasisCache &basis_cache,
189  const int8_t order,
190  const Span<T> src,
191  MutableSpan<T> dst)
192 {
194 
195  for (const int i : dst.index_range()) {
196  Span<float> point_weights = basis_cache.weights.as_span().slice(i * order, order);
197 
198  for (const int j : point_weights.index_range()) {
199  const int point_index = (basis_cache.start_indices[i] + j) % src.size();
200  mixer.mix_in(i, src[point_index], point_weights[j]);
201  }
202  }
203 
204  mixer.finalize();
205 }
206 
207 template<typename T>
208 static void interpolate_to_evaluated_rational(const BasisCache &basis_cache,
209  const int8_t order,
210  const Span<float> control_weights,
211  const Span<T> src,
212  MutableSpan<T> dst)
213 {
215 
216  for (const int i : dst.index_range()) {
217  Span<float> point_weights = basis_cache.weights.as_span().slice(i * order, order);
218 
219  for (const int j : point_weights.index_range()) {
220  const int point_index = (basis_cache.start_indices[i] + j) % src.size();
221  const float weight = point_weights[j] * control_weights[point_index];
222  mixer.mix_in(i, src[point_index], weight);
223  }
224  }
225 
226  mixer.finalize();
227 }
228 
229 void interpolate_to_evaluated(const BasisCache &basis_cache,
230  const int8_t order,
231  const Span<float> control_weights,
232  const GSpan src,
233  GMutableSpan dst)
234 {
235  if (basis_cache.invalid) {
236  dst.copy_from(src);
237  return;
238  }
239 
240  BLI_assert(dst.size() == basis_cache.start_indices.size());
241  attribute_math::convert_to_static_type(src.type(), [&](auto dummy) {
242  using T = decltype(dummy);
243  if constexpr (!std::is_void_v<attribute_math::DefaultMixer<T>>) {
244  if (control_weights.is_empty()) {
245  interpolate_to_evaluated(basis_cache, order, src.typed<T>(), dst.typed<T>());
246  }
247  else {
248  interpolate_to_evaluated_rational(
249  basis_cache, order, control_weights, src.typed<T>(), dst.typed<T>());
250  }
251  }
252  });
253 }
254 
255 } // namespace blender::bke::curves::nurbs
Low-level operations for curves.
#define BLI_assert(a)
Definition: BLI_assert.h:46
MINLINE int min_ii(int a, int b)
#define UNUSED_VARS_NDEBUG(...)
#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
void copy_from(GSpan values)
constexpr int64_t size() const
Definition: BLI_span.hh:511
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
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)
int calculate_evaluated_num(int points_num, int8_t order, bool cyclic, int resolution, KnotsMode knots_mode)
Definition: curve_nurbs.cc:32
bool check_valid_num_and_order(int points_num, int8_t order, bool cyclic, KnotsMode knots_mode)
Definition: curve_nurbs.cc:13
void calculate_knots(int points_num, KnotsMode mode, int8_t order, bool cyclic, MutableSpan< float > knots)
Definition: curve_nurbs.cc:52
void calculate_basis_cache(int points_num, int evaluated_num, int8_t order, bool cyclic, Span< float > knots, BasisCache &basis_cache)
Definition: curve_nurbs.cc:149
static void calculate_basis_for_point(const float parameter, const int points_num, const int degree, const Span< float > knots, MutableSpan< float > r_weights, int &r_start_index)
Definition: curve_nurbs.cc:96
int knots_num(int points_num, int8_t order, bool cyclic)
Definition: curve_nurbs.cc:44
static void interpolate_to_evaluated_rational(const BasisCache &basis_cache, const int8_t order, const Span< float > control_weights, const Span< T > src, MutableSpan< T > dst)
Definition: curve_nurbs.cc:208
void interpolate_to_evaluated(const BasisCache &basis_cache, int8_t order, Span< float > control_weights, GSpan src, GMutableSpan dst)
Definition: curve_nurbs.cc:229
int segments_num(const int points_num, const bool cyclic)
Definition: BKE_curves.hh:462
T clamp(const T &a, const T &min, const T &max)
signed char int8_t
Definition: stdint.h:75
float max