Blender V5.3
curve_nurbs.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 "BLI_task.hh"
10
11#include "BKE_attribute_math.hh"
12#include "BKE_curves.hh"
13
15
16bool check_valid_eval_params(const int points_num,
17 const int8_t order,
18 const bool cyclic,
19 const KnotsMode knots_mode,
20 const int resolution)
21{
22 if (points_num < order) {
23 return false;
24 }
25
26 if (order < 2) {
27 return false;
28 }
29
30 if (resolution < 1) {
31 return false;
32 }
33
35 if (knots_mode == NURBS_KNOT_MODE_BEZIER && points_num <= order) {
36 return false;
37 }
38 return (!cyclic || points_num % (order - 1) == 0);
39 }
40
41 return true;
42}
43
44static int calc_nonzero_knot_spans(const int points_num,
45 const KnotsMode mode,
46 const int8_t order,
47 const bool cyclic)
48{
49 BLI_assert(order >= 2);
50 const bool is_bezier = ELEM(mode, NURBS_KNOT_MODE_BEZIER, NURBS_KNOT_MODE_ENDPOINT_BEZIER);
51 const bool is_end_point = ELEM(mode, NURBS_KNOT_MODE_ENDPOINT, NURBS_KNOT_MODE_ENDPOINT_BEZIER);
52 /* Inner knots are always repeated once except on Bezier case. */
53 const int repeat_inner = is_bezier ? order - 1 : 1;
54 /* For non endpoint Bezier repeated knots are shifted by one. */
55 const int knots_before_geometry = order + int(is_bezier && !is_end_point && order > 2);
56 const int knots_after_geometry = order - 1 +
57 (cyclic && mode == NURBS_KNOT_MODE_ENDPOINT ? order - 2 : 0);
58
59 const int knots_total = knots_num(points_num, order, cyclic);
60 /* On these knots as parameters actual geometry is generated. */
61 const int geometry_knots = knots_total - knots_before_geometry - knots_after_geometry;
62 /* `repeat_inner - 1` is added to `ceil`. */
63 const int non_zero_knots = (geometry_knots + repeat_inner - 1) / repeat_inner;
64 return non_zero_knots;
65}
66
67static bool is_breakpoint(const Span<float> knots, const int knot_span)
68{
69 return (knots[knot_span + 1] - knots[knot_span]) > 0.0f;
70}
71
72static int count_nonzero_knot_spans(const int points_num,
73 const int order,
74 const bool cyclic,
75 const Span<float> knots)
76{
77 BLI_assert(points_num > 0);
78 const int degree = order - 1;
79 int span_num = 0;
80
81 const int wrapped_points_num = control_points_num(points_num, order, cyclic);
82 for (const int knot_span : IndexRange::from_begin_end(degree, wrapped_points_num)) {
83 span_num += is_breakpoint(knots, knot_span);
84 }
85 return span_num;
86}
87
88int calculate_evaluated_num(const int points_num,
89 const int8_t order,
90 const bool cyclic,
91 const int resolution,
92 const KnotsMode knots_mode,
93 const Span<float> knots)
94{
95 if (!check_valid_eval_params(points_num, order, cyclic, knots_mode, resolution)) {
96 return points_num;
97 }
98 const int nonzero_span_num = knots_mode == KnotsMode::NURBS_KNOT_MODE_CUSTOM &&
99 !knots.is_empty() ?
100 count_nonzero_knot_spans(points_num, order, cyclic, knots) :
101 calc_nonzero_knot_spans(points_num, knots_mode, order, cyclic);
102 return resolution * nonzero_span_num + int(!cyclic);
103}
104
105static void copy_custom_knots(const int8_t order,
106 const bool cyclic,
107 const Span<float> custom_knots,
108 MutableSpan<float> knots)
109{
110 knots.slice(0, custom_knots.size()).copy_from(custom_knots);
111 if (cyclic) {
112 const float last_knot = custom_knots.last();
113 const float shift = last_knot - knots[order - 1];
114 const MutableSpan<float> tail = knots.take_back(order - 1);
115 for (const int knot : tail.index_range()) {
116 tail[knot] = knots[order + knot] + shift;
117 }
118 }
119}
120
121void calculate_knots(const int points_num,
122 const KnotsMode mode,
123 const int8_t order,
124 const bool cyclic,
125 MutableSpan<float> knots)
126{
127 BLI_assert(knots.size() == knots_num(points_num, order, cyclic));
128 UNUSED_VARS_NDEBUG(points_num);
129
130 const bool is_bezier = ELEM(mode, NURBS_KNOT_MODE_BEZIER, NURBS_KNOT_MODE_ENDPOINT_BEZIER);
131 const bool is_end_point = ELEM(mode, NURBS_KNOT_MODE_ENDPOINT, NURBS_KNOT_MODE_ENDPOINT_BEZIER);
132 /* Inner knots are always repeated once except on Bezier case. */
133 const int repeat_inner = is_bezier ? order - 1 : 1;
134 /* How many times to repeat 0.0 at the beginning of knot. */
135 const int head = is_end_point ? (order - (cyclic ? 1 : 0)) :
136 (is_bezier ? min_ii(2, repeat_inner) : 1);
137 /* Number of knots replicating widths of the starting knots.
138 * Covers both Cyclic and EndPoint cases. */
139 const int tail = cyclic ? 2 * order - 1 : (is_end_point ? order : 0);
140
141 int r = head;
142 float current = 0.0f;
143
144 const int offset = is_end_point && cyclic ? 1 : 0;
145 if (offset) {
146 knots[0] = current;
147 current += 1.0f;
148 }
149
150 for (const int i : IndexRange(offset, knots.size() - offset - tail)) {
151 knots[i] = current;
152 r--;
153 if (r == 0) {
154 current += 1.0;
155 r = repeat_inner;
156 }
157 }
158
159 const int tail_index = knots.size() - tail;
160 for (const int i : IndexRange(tail)) {
161 knots[tail_index + i] = current + (knots[i] - knots[0]);
162 }
163}
164
166 const int points_num,
167 const int8_t order,
168 const bool cyclic,
169 const IndexRange curve_knots,
170 const Span<float> custom_knots,
171 MutableSpan<float> knots)
172{
173 if (mode == NURBS_KNOT_MODE_CUSTOM) {
174 BLI_assert(!custom_knots.is_empty());
175 BLI_assert(!curve_knots.is_empty());
176 copy_custom_knots(order, cyclic, custom_knots.slice(curve_knots), knots);
177 }
178 else {
179 calculate_knots(points_num, mode, order, cyclic, knots);
180 }
181}
182
184{
185 Vector<int> multiplicity;
186 multiplicity.reserve(knots.size());
187
188 int m = 1;
189 for (const int64_t i : knots.index_range().drop_front(1)) {
190 /* Only consider multiplicity for exact matching values. */
191 if (knots[i - 1] == knots[i]) {
192 m++;
193 }
194 else {
195 multiplicity.append(m);
196 m = 1;
197 }
198 }
199 multiplicity.append(m);
200 return multiplicity;
201}
202
203/* Basis function calculation, implementation based on 'The NURBS Book' p. 70, ISBN: 3540615458.
204 */
206 const int degree,
207 const float parameter,
208 const int span_index,
209 MutableSpan<float> r_weights,
210 int &r_start_index)
211{
212 BLI_assert(degree >= 1);
213 BLI_assert(span_index >= degree);
214 BLI_assert(span_index + degree < knots.size());
215 BLI_assert(knots[span_index + 1] > knots[span_index]);
216 const int order = degree + 1;
217
218 r_start_index = span_index - degree;
219
220 Array<float, 12> left(order);
221 Array<float, 12> right(order);
222 r_weights[0] = 1.0f;
223
224 for (const int j : IndexRange(1, degree)) {
225 left[j] = parameter - knots[span_index + 1 - j];
226 right[j] = knots[span_index + j] - parameter;
227 float saved = 0.0f;
228 for (const int r : IndexRange(j)) {
229 const float temp = r_weights[r] / (right[r + 1] + left[j - r]);
230 r_weights[r] = saved + right[r + 1] * temp;
231 saved = left[j - r] * temp;
232 }
233 r_weights[j] = saved;
234 }
235}
236
237void calculate_basis_cache(const int points_num,
238 const int evaluated_num,
239 const int8_t order,
240 const int resolution,
241 const bool cyclic,
242 const KnotsMode knots_mode,
243 const Span<float> knots,
244 BasisCache &basis_cache)
245{
246 BLI_assert(points_num > 0);
247
248 const int8_t degree = order - 1;
249 const int wrapped_points_num = control_points_num(points_num, order, cyclic);
250
251 basis_cache.weights.resize(evaluated_num * order);
252 basis_cache.start_indices.resize(evaluated_num);
253
254 if (evaluated_num == 0) {
255 return;
256 }
257
258 if (!check_valid_eval_params(points_num, order, cyclic, knots_mode, resolution)) {
259 return;
260 }
261
262 MutableSpan<float> basis_weights(basis_cache.weights);
263 MutableSpan<int> basis_start_indices(basis_cache.start_indices);
264
265 /* Find the 'span index' for each breakpoint that defines the 'evaluated spans'.
266 * An evaluated span (or 'segment') in this context is the parameter interval
267 * between two consecutive knots [i, i + 1], where the knot at index `i` is a
268 * breakpoint and is strictly less than the value of following knot. For repeated
269 * knots, with multiplicity > 1, only the rightmost is considered a breakpoint
270 * as the spans between repeated knot values are zero length!
271 */
272 const int breakpoint_num = (evaluated_num - !cyclic) / resolution;
273 Array<int, 20> span_offsets(breakpoint_num);
274
275 int breakpoint_count = 0;
276 for (const int span_index : IndexRange::from_begin_end(degree, wrapped_points_num)) {
277 if (is_breakpoint(knots, span_index)) {
278 span_offsets[breakpoint_count++] = span_index;
279 }
280 }
281 BLI_assert(breakpoint_count == breakpoint_num);
282
283 /* Build the basis cache, sampling each evaluated span at intervals. */
284 threading::parallel_for(span_offsets.index_range(), 4096, [&](const IndexRange range) {
285 for (const int index : range) {
286 const int span_index = span_offsets[index];
287 int eval_point = index * resolution;
288
289 const float knot_delta = knots[span_index + 1] - knots[span_index];
290 const float knot_step = knot_delta / resolution;
291 BLI_assert(knot_delta > 0.0f);
292
293 for (const int step : IndexRange::from_begin_size(0, resolution)) {
294 const float parameter = knots[span_index] + step * knot_step;
295 calculate_basis_for_point(knots,
296 degree,
297 parameter,
298 span_index,
299 basis_weights.slice(eval_point * order, order),
300 basis_start_indices[eval_point]);
301 eval_point++;
302 }
303 }
304 });
305 if (!cyclic) {
307 degree,
308 knots[wrapped_points_num],
309 span_offsets.last(),
310 basis_weights.slice(basis_weights.size() - order, order),
311 basis_start_indices.last());
312 }
313}
314
315template<typename T>
316static void interpolate_to_evaluated(const BasisCache &basis_cache,
317 const int8_t order,
318 const Span<T> src,
319 MutableSpan<T> dst)
320{
322
323 threading::parallel_for(dst.index_range(), 128, [&](const IndexRange range) {
324 for (const int i : range) {
325 Span<float> point_weights = basis_cache.weights.as_span().slice(i * order, order);
326 for (const int j : point_weights.index_range()) {
327 const int point_index = (basis_cache.start_indices[i] + j) % src.size();
328 mixer.mix_in(i, src[point_index], point_weights[j]);
329 }
330 }
331 mixer.finalize(range);
332 });
333}
334
335template<typename T>
336static void interpolate_to_evaluated_rational(const BasisCache &basis_cache,
337 const int8_t order,
338 const Span<float> control_weights,
339 const Span<T> src,
340 MutableSpan<T> dst)
341{
343
344 threading::parallel_for(dst.index_range(), 128, [&](const IndexRange range) {
345 for (const int i : range) {
346 Span<float> point_weights = basis_cache.weights.as_span().slice(i * order, order);
347
348 for (const int j : point_weights.index_range()) {
349 const int point_index = (basis_cache.start_indices[i] + j) % src.size();
350 const float weight = point_weights[j] * control_weights[point_index];
351 mixer.mix_in(i, src[point_index], weight);
352 }
353 }
354 mixer.finalize(range);
355 });
356}
357
358void interpolate_to_evaluated(const BasisCache &basis_cache,
359 const int8_t order,
360 const Span<float> control_weights,
361 const GSpan src,
362 GMutableSpan dst)
363{
364 if (basis_cache.invalid) {
365 dst.copy_from(src);
366 return;
367 }
368
369 BLI_assert(dst.size() == basis_cache.start_indices.size());
370 attribute_math::to_static_type(src.type(), [&]<typename T>() {
371 if constexpr (!std::is_void_v<attribute_math::DefaultMixer<T>>) {
372 if (control_weights.is_empty()) {
373 interpolate_to_evaluated(basis_cache, order, src.typed<T>(), dst.typed<T>());
374 }
375 else {
376 interpolate_to_evaluated_rational(
377 basis_cache, order, control_weights, src.typed<T>(), dst.typed<T>());
378 }
379 }
380 });
381}
382
383} // namespace blender::bke::curves::nurbs
Low-level operations for curves.
#define UNUSED_VARS_NDEBUG(...)
#define ELEM(...)
IndexRange index_range() const
Definition BLI_array.hh:371
void copy_from(GSpan values)
const CPPType & type() const
constexpr bool is_empty() const
static constexpr IndexRange from_begin_end(const int64_t begin, const int64_t end)
constexpr IndexRange()=default
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 MutableSpan take_back(const int64_t n) const
Definition BLI_span.hh:646
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr void copy_from(Span< T > values) const
Definition BLI_span.hh:745
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
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
int64_t size() const
void append(const T &value)
void resize(const int64_t new_size)
void reserve(const int64_t min_capacity)
#define T
typename DefaultMixerStruct< T >::type DefaultMixer
void to_static_type(const CPPType &cpp_type, Fn &&fn)
Vector< int > calculate_multiplicity_sequence(Span< float > knots)
int calculate_evaluated_num(int points_num, int8_t order, bool cyclic, int resolution, KnotsMode knots_mode, Span< float > knots)
void calculate_knots(int points_num, KnotsMode mode, int8_t order, bool cyclic, MutableSpan< float > knots)
void calculate_basis_cache(int points_num, int evaluated_num, int8_t order, int resolution, bool cyclic, KnotsMode knots_mode, Span< float > knots, BasisCache &basis_cache)
static void calculate_basis_for_point(const Span< float > knots, const int degree, const float parameter, const int span_index, MutableSpan< float > r_weights, int &r_start_index)
bool check_valid_eval_params(int points_num, int8_t order, bool cyclic, KnotsMode knots_mode, int resolution)
int knots_num(int points_num, int8_t order, bool cyclic)
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)
static bool is_breakpoint(const Span< float > knots, const int knot_span)
void load_curve_knots(KnotsMode mode, int points_num, int8_t order, bool cyclic, IndexRange curve_knots, Span< float > custom_knots, MutableSpan< float > knots)
int control_points_num(int points_num, int8_t order, bool cyclic)
static int count_nonzero_knot_spans(const int points_num, const int order, const bool cyclic, const Span< float > knots)
void copy_custom_knots(const bke::CurvesGeometry &src_curves, const IndexMask &exclude_curves, bke::CurvesGeometry &dst_curves)
void interpolate_to_evaluated(const BasisCache &basis_cache, int8_t order, Span< float > control_weights, GSpan src, GMutableSpan dst)
static int calc_nonzero_knot_spans(const int points_num, const KnotsMode mode, const int8_t order, const bool cyclic)
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)
__int64 int64_t
Definition BKE_text.h:90
@ NURBS_KNOT_MODE_ENDPOINT_BEZIER
@ NURBS_KNOT_MODE_BEZIER
@ NURBS_KNOT_MODE_ENDPOINT
@ NURBS_KNOT_MODE_CUSTOM
MINLINE int min_ii(int a, int b)
signed char int8_t
Definition BKE_text.h:76
void resize(int new_size)
Definition vector.hh:94