Blender V5.3
subdivide_curves.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
10#include "BKE_curves.hh"
11#include "BKE_curves_utils.hh"
12#include "BKE_deform.hh"
13
14#include "BLI_array_utils.hh"
15#include "BLI_task.hh"
16
18
19namespace blender::geometry {
20
21static void calculate_result_offsets(const bke::CurvesGeometry &src_curves,
22 const IndexMask &selection,
23 const IndexMask &unselected,
24 const VArray<int> &cuts,
25 const Span<bool> cyclic,
26 MutableSpan<int> dst_curve_offsets,
27 MutableSpan<int> dst_point_offsets)
28{
29 /* Fill the array with each curve's point count, then accumulate them to the offsets. */
30 const OffsetIndices src_points_by_curve = src_curves.points_by_curve();
31 offset_indices::copy_group_sizes(src_points_by_curve, unselected, dst_curve_offsets);
32 selection.foreach_index(
33 [&](const int curve_i) {
34 const IndexRange src_points = src_points_by_curve[curve_i];
35 const IndexRange src_segments = bke::curves::per_curve_point_offsets_range(src_points,
36 curve_i);
37
38 MutableSpan<int> point_offsets = dst_point_offsets.slice(src_segments);
39 MutableSpan<int> point_counts = point_offsets.drop_back(1);
40
41 if (src_points.size() == 1) {
42 point_counts.first() = 1;
43 }
44 else {
45 cuts.materialize_compressed(src_points, point_counts);
46 for (int &count : point_counts) {
47 /* Make sure there at least one cut, and add one for the existing point. */
48 count = std::max(count, 0) + 1;
49 }
50 if (!cyclic[curve_i]) {
51 /* The last point only has a segment to be subdivided if the curve isn't cyclic. */
52 point_counts.last() = 1;
53 }
54 }
55
57 dst_curve_offsets[curve_i] = point_offsets.last();
58 },
61}
62
63template<typename T>
64static inline void linear_interpolation(const T &a, const T &b, MutableSpan<T> dst)
65{
66 dst.first() = a;
67 const float step = 1.0f / dst.size();
68 for (const int i : dst.index_range().drop_front(1)) {
69 dst[i] = bke::attribute_math::mix2(i * step, a, b);
70 }
71}
72
73template<typename T>
74static void subdivide_attribute_linear(const OffsetIndices<int> src_points_by_curve,
75 const OffsetIndices<int> dst_points_by_curve,
76 const IndexMask &selection,
77 const Span<int> all_point_offsets,
78 const Span<T> src,
80{
81 selection.foreach_index(
82 [&](const int curve_i) {
83 const IndexRange src_points = src_points_by_curve[curve_i];
84 const IndexRange src_segments = bke::curves::per_curve_point_offsets_range(src_points,
85 curve_i);
86 const OffsetIndices<int> curve_offsets = all_point_offsets.slice(src_segments);
87 const IndexRange dst_points = dst_points_by_curve[curve_i];
88 const Span<T> curve_src = src.slice(src_points);
89 MutableSpan<T> curve_dst = dst.slice(dst_points);
90
91 threading::parallel_for(curve_src.index_range().drop_back(1), 1024, [&](IndexRange range) {
92 for (const int i : range) {
93 const IndexRange segment_points = curve_offsets[i];
94 linear_interpolation(curve_src[i], curve_src[i + 1], curve_dst.slice(segment_points));
95 }
96 });
97
98 const IndexRange dst_last_segment = dst_points.slice(curve_offsets[src_points.size() - 1]);
99 linear_interpolation(curve_src.last(), curve_src.first(), dst.slice(dst_last_segment));
100 },
102}
103
104static void subdivide_attribute_linear(const OffsetIndices<int> src_points_by_curve,
105 const OffsetIndices<int> dst_points_by_curve,
106 const IndexMask &selection,
107 const Span<int> all_point_offsets,
108 const GSpan src,
109 GMutableSpan dst)
110{
111 bke::attribute_math::to_static_type(dst.type(), [&]<typename T>() {
112 if constexpr (!std::is_same_v<T, std::string>) {
113 subdivide_attribute_linear(src_points_by_curve,
114 dst_points_by_curve,
115 selection,
116 all_point_offsets,
117 src.typed<T>(),
118 dst.typed<T>());
119 }
120 });
121}
122
123static void subdivide_attribute_catmull_rom(const OffsetIndices<int> src_points_by_curve,
124 const OffsetIndices<int> dst_points_by_curve,
125 const IndexMask &selection,
126 const Span<int> all_point_offsets,
127 const Span<bool> cyclic,
128 const GSpan src,
129 GMutableSpan dst)
130{
131 selection.foreach_index(
132 [&](const int curve_i) {
133 const IndexRange src_points = src_points_by_curve[curve_i];
134 const IndexRange src_segments = bke::curves::per_curve_point_offsets_range(src_points,
135 curve_i);
136 const IndexRange dst_points = dst_points_by_curve[curve_i];
138 cyclic[curve_i],
139 all_point_offsets.slice(src_segments),
140 dst.slice(dst_points));
141 },
143}
144
146{
147 switch (type) {
149 return BEZIER_HANDLE_FREE;
151 return BEZIER_HANDLE_ALIGN;
153 return BEZIER_HANDLE_FREE;
155 return BEZIER_HANDLE_ALIGN;
156 }
158 return BEZIER_HANDLE_FREE;
159}
160
161static void subdivide_bezier_segment(const float3 &position_prev,
162 const float3 &handle_prev,
163 const float3 &handle_next,
164 const float3 &position_next,
165 const HandleType type_prev,
166 const HandleType type_next,
167 const IndexRange segment_points,
168 const int dst_next_segment_start,
169 MutableSpan<float3> dst_positions,
170 MutableSpan<float3> dst_handles_l,
171 MutableSpan<float3> dst_handles_r,
172 MutableSpan<int8_t> dst_types_l,
173 MutableSpan<int8_t> dst_types_r)
174{
175 if (bke::curves::bezier::segment_is_vector(type_prev, type_next)) {
176 linear_interpolation(position_prev, position_next, dst_positions.slice(segment_points));
177 /* All of the segment handles should be vector handles. */
178 dst_types_r[segment_points.first()] = BEZIER_HANDLE_VECTOR;
179 dst_types_l[dst_next_segment_start] = BEZIER_HANDLE_VECTOR;
180 dst_types_l.slice(segment_points.drop_front(1)).fill(BEZIER_HANDLE_VECTOR);
181 dst_types_r.slice(segment_points.drop_front(1)).fill(BEZIER_HANDLE_VECTOR);
182 }
183 else {
184 /* The first point in the segment is always copied. */
185 dst_positions[segment_points.first()] = position_prev;
186
187 /* In order to generate a Bezier curve with the same shape as the input curve, apply the
188 * De Casteljau algorithm iteratively for the provided number of cuts, constantly updating the
189 * previous result point's right handle and the left handle at the end of the segment. */
190 float3 segment_start = position_prev;
191 float3 segment_handle_prev = handle_prev;
192 float3 segment_handle_next = handle_next;
193 const float3 segment_end = position_next;
194
195 for (const int i : IndexRange(segment_points.size() - 1)) {
196 const float parameter = 1.0f / (segment_points.size() - i);
197 const int point_i = segment_points[i];
199 segment_start, segment_handle_prev, segment_handle_next, segment_end, parameter);
200
201 /* Copy relevant temporary data to the result. */
202 dst_handles_r[point_i] = insert.handle_prev;
203 dst_handles_l[point_i + 1] = insert.left_handle;
204 dst_positions[point_i + 1] = insert.position;
205
206 /* Update the segment to prepare it for the next subdivision. */
207 segment_start = insert.position;
208 segment_handle_prev = insert.right_handle;
209 segment_handle_next = insert.handle_next;
210 }
211
212 /* Copy the handles for the last segment from the working variables. */
213 dst_handles_r[segment_points.last()] = segment_handle_prev;
214 dst_handles_l[dst_next_segment_start] = segment_handle_next;
215
216 /* First and last handles at the ends of the segment are aligned if possible. */
217 dst_types_r[segment_points.first()] = aligned_or_free_handle_type(type_prev);
218 dst_types_l[dst_next_segment_start] = aligned_or_free_handle_type(type_next);
219
220 /* Handles inside the segment are aligned. */
221 dst_types_l.slice(segment_points.drop_front(1)).fill(BEZIER_HANDLE_ALIGN);
222 dst_types_r.slice(segment_points.drop_front(1)).fill(BEZIER_HANDLE_ALIGN);
223 }
224}
225
226static void subdivide_bezier_positions(const Span<float3> src_positions,
227 const Span<int8_t> src_types_l,
228 const Span<int8_t> src_types_r,
229 const Span<float3> src_handles_l,
230 const Span<float3> src_handles_r,
231 const OffsetIndices<int> evaluated_offsets,
232 const bool cyclic,
233 MutableSpan<float3> dst_positions,
234 MutableSpan<int8_t> dst_types_l,
235 MutableSpan<int8_t> dst_types_r,
236 MutableSpan<float3> dst_handles_l,
237 MutableSpan<float3> dst_handles_r)
238{
239 threading::parallel_for(src_positions.index_range().drop_back(1), 512, [&](IndexRange range) {
240 for (const int segment_i : range) {
241 const IndexRange segment = evaluated_offsets[segment_i];
242 subdivide_bezier_segment(src_positions[segment_i],
243 src_handles_r[segment_i],
244 src_handles_l[segment_i + 1],
245 src_positions[segment_i + 1],
246 HandleType(src_types_r[segment_i]),
247 HandleType(src_types_l[segment_i + 1]),
248 segment,
249 segment.one_after_last(),
250 dst_positions,
251 dst_handles_l,
252 dst_handles_r,
253 dst_types_l,
254 dst_types_r);
255 }
256 });
257
258 if (cyclic) {
259 const int last_index = src_positions.index_range().last();
260 const IndexRange segment = evaluated_offsets[last_index];
261 subdivide_bezier_segment(src_positions.last(),
262 src_handles_r.last(),
263 src_handles_l.first(),
264 src_positions.first(),
265 HandleType(src_types_r.last()),
266 HandleType(src_types_l.first()),
267 segment,
268 0,
269 dst_positions,
270 dst_handles_l,
271 dst_handles_r,
272 dst_types_l,
273 dst_types_r);
274 }
275 else {
276 dst_positions.last() = src_positions.last();
277 dst_types_l.first() = src_types_l.first();
278 dst_types_r.last() = src_types_r.last();
279 dst_handles_l.first() = src_handles_l.first();
280 dst_handles_r.last() = src_handles_r.last();
281 }
282
283 /* TODO: It would be possible to avoid calling this for all segments besides vector segments. */
284 bke::curves::bezier::calculate_auto_handles(
285 cyclic, dst_types_l, dst_types_r, dst_positions, dst_handles_l, dst_handles_r);
286}
287
289 const IndexMask &selection,
290 const VArray<int> &cuts,
291 const bke::AttributeFilter &attribute_filter)
292{
293 if (src_curves.is_empty()) {
294 return src_curves;
295 }
296
297 const OffsetIndices src_points_by_curve = src_curves.points_by_curve();
298 /* Cyclic is accessed a lot, it's probably worth it to make sure it's a span. */
299 const VArraySpan<bool> cyclic{src_curves.cyclic()};
300 IndexMaskMemory memory;
301 const IndexMask unselected = selection.complement(src_curves.curves_range(), memory);
302
304 /* Copy vertex groups from source curves to allow copying vertex group attributes. */
306
307 /* For each point, this contains the point offset in the corresponding result curve,
308 * starting at zero. For example for two curves with four points each, the values might
309 * look like this:
310 *
311 * | | Curve 0 | Curve 1 |
312 * | ------------------- |---|---|---|---|---|---|---|---|---|----|
313 * | Cuts | 0 | 3 | 0 | 0 | - | 2 | 0 | 0 | 4 | - |
314 * | New Point Count | 1 | 4 | 1 | 1 | - | 3 | 1 | 1 | 5 | - |
315 * | Accumulated Offsets | 0 | 1 | 5 | 6 | 7 | 0 | 3 | 4 | 5 | 10 |
316 *
317 * Storing the leading zero is unnecessary but makes the array a bit simpler to use by avoiding
318 * a check for the first segment, and because some existing utilities also use leading zeros. */
319 Array<int> all_point_offset_data(src_curves.points_num() + src_curves.curves_num());
320#ifndef NDEBUG
321 all_point_offset_data.fill(-1);
322#endif
323 calculate_result_offsets(src_curves,
324 selection,
325 unselected,
326 cuts,
327 cyclic,
328 dst_curves.offsets_for_write(),
329 all_point_offset_data);
330 const OffsetIndices dst_points_by_curve = dst_curves.points_by_curve();
331
332 const Span<int> all_point_offsets(all_point_offset_data);
333
334 dst_curves.resize(dst_curves.offsets().last(), dst_curves.curves_num());
335
336 const bke::AttributeAccessor src_attributes = src_curves.attributes();
337 bke::MutableAttributeAccessor dst_attributes = dst_curves.attributes_for_write();
338
339 Vector<bke::AttributeTransferData> attributes_to_transfer =
341 src_attributes, dst_attributes, {bke::AttrDomain::Point}, attribute_filter);
342
343 auto subdivide_catmull_rom = [&](const IndexMask &selection) {
344 for (auto &attribute : attributes_to_transfer) {
345 subdivide_attribute_catmull_rom(src_points_by_curve,
346 dst_points_by_curve,
347 selection,
348 all_point_offsets,
349 cyclic,
350 attribute.src,
351 attribute.dst.span);
352 }
353 };
354
355 auto subdivide_poly = [&](const IndexMask &selection) {
356 for (auto &attribute : attributes_to_transfer) {
357 subdivide_attribute_linear(src_points_by_curve,
358 dst_points_by_curve,
359 selection,
360 all_point_offsets,
361 attribute.src,
362 attribute.dst.span);
363 }
364 };
365
366 auto subdivide_bezier = [&](const IndexMask &selection) {
367 const Span<float3> src_positions = src_curves.positions();
368 const VArraySpan<int8_t> src_types_l{src_curves.handle_types_left()};
369 const VArraySpan<int8_t> src_types_r{src_curves.handle_types_right()};
370 const Span<float3> src_handles_l = *src_curves.handle_positions_left();
371 const Span<float3> src_handles_r = *src_curves.handle_positions_right();
372
373 MutableSpan<float3> dst_positions = dst_curves.positions_for_write();
374 MutableSpan<int8_t> dst_types_l = dst_curves.handle_types_left_for_write();
375 MutableSpan<int8_t> dst_types_r = dst_curves.handle_types_right_for_write();
376 MutableSpan<float3> dst_handles_l = dst_curves.handle_positions_left_for_write();
377 MutableSpan<float3> dst_handles_r = dst_curves.handle_positions_right_for_write();
378 const OffsetIndices<int> dst_points_by_curve = dst_curves.points_by_curve();
379
380 selection.foreach_index(
381 [&](const int curve_i) {
382 const IndexRange src_points = src_points_by_curve[curve_i];
383 const IndexRange src_segments = bke::curves::per_curve_point_offsets_range(src_points,
384 curve_i);
385 const IndexRange dst_points = dst_points_by_curve[curve_i];
386 subdivide_bezier_positions(src_positions.slice(src_points),
387 src_types_l.slice(src_points),
388 src_types_r.slice(src_points),
389 src_handles_l.slice(src_points),
390 src_handles_r.slice(src_points),
391 all_point_offsets.slice(src_segments),
392 cyclic[curve_i],
393 dst_positions.slice(dst_points),
394 dst_types_l.slice(dst_points),
395 dst_types_r.slice(dst_points),
396 dst_handles_l.slice(dst_points),
397 dst_handles_r.slice(dst_points));
398 },
400
401 /* Filter out positions and handles that are already interpolated. */
402 const Set<StringRef> attributes_to_skip = {
403 "position", "handle_type_left", "handle_type_right", "handle_right", "handle_left"};
404 for (auto &attribute : attributes_to_transfer) {
405 if (attributes_to_skip.contains(attribute.name)) {
406 continue;
407 }
408 subdivide_attribute_linear(src_points_by_curve,
409 dst_points_by_curve,
410 selection,
411 all_point_offsets,
412 attribute.src,
413 attribute.dst.span);
414 }
415 };
416
417 /* NURBS curves are just treated as poly curves. NURBS subdivision that maintains
418 * their shape may be possible, but probably wouldn't work with the "cuts" input. */
419 auto subdivide_nurbs = subdivide_poly;
420
422 src_curves.curve_type_counts(),
423 selection,
424 subdivide_catmull_rom,
425 subdivide_poly,
426 subdivide_bezier,
427 subdivide_nurbs);
428
429 for (auto &attribute : attributes_to_transfer) {
431 src_points_by_curve, dst_points_by_curve, unselected, attribute.src, attribute.dst.span);
432 attribute.dst.finish();
433 }
434
435 bke::curves::nurbs::copy_custom_knots(src_curves, selection, dst_curves);
436 return dst_curves;
437}
438
439} // namespace blender::geometry
Low-level operations for curves.
Low-level operations for curves.
support for deformation groups and hooks.
__forceinline const float4 insert(const float4 &a, const float b)
Definition binning.cpp:31
#define BLI_assert_unreachable()
void fill(const T &value) const
Definition BLI_array.hh:283
GMutableSpan slice(const int64_t start, int64_t size) const
const CPPType & type() const
GSpan slice(const int64_t start, int64_t size) const
constexpr int64_t first() const
constexpr IndexRange drop_back(int64_t n) const
constexpr int64_t last(const int64_t n=0) const
constexpr int64_t size() const
constexpr IndexRange slice(int64_t start, int64_t size) const
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 drop_back(const int64_t n) const
Definition BLI_span.hh:624
constexpr void fill(const T &value) const
Definition BLI_span.hh:523
constexpr T & first() const
Definition BLI_span.hh:685
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr T & last(const int64_t n=0) const
Definition BLI_span.hh:695
bool contains(const Key &key) const
Definition BLI_set.hh:310
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
void materialize_compressed(const IndexMask &mask, MutableSpan< T > r_span) const
MutableSpan< int8_t > handle_types_left_for_write()
VArray< int8_t > curve_types() const
MutableSpan< float3 > positions_for_write()
MutableSpan< int8_t > handle_types_right_for_write()
std::optional< Span< float3 > > handle_positions_right() const
void resize(int points_num, int curves_num)
VArray< bool > cyclic() const
AttributeAccessor attributes() const
Span< float3 > positions() const
MutableSpan< float3 > handle_positions_right_for_write()
std::optional< Span< float3 > > handle_positions_left() const
IndexRange curves_range() const
VArray< int8_t > handle_types_left() const
MutableSpan< float3 > handle_positions_left_for_write()
MutableSpan< int > offsets_for_write()
const std::array< int, CURVE_TYPES_NUM > & curve_type_counts() const
VArray< int8_t > handle_types_right() const
OffsetIndices< int > points_by_curve() const
MutableAttributeAccessor attributes_for_write()
constexpr Span slice(int64_t start, int64_t size) const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
IndexMask complement(const IndexMask &universe, LinearAllocator<> &memory) const
#define attribute(slot)
VecBase< float, D > step(VecOp< float, D >, VecOp< float, D >) RET
#define T
void copy_group_to_group(OffsetIndices< int > src_offsets, OffsetIndices< int > dst_offsets, const IndexMask &selection, GSpan src, GMutableSpan dst)
void to_static_type(const CPPType &cpp_type, Fn &&fn)
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)
bool segment_is_vector(const HandleType left, const HandleType right)
void interpolate_to_evaluated(GSpan src, bool cyclic, int resolution, GMutableSpan dst)
void copy_custom_knots(const bke::CurvesGeometry &src_curves, const IndexMask &exclude_curves, bke::CurvesGeometry &dst_curves)
bke::CurvesGeometry copy_only_curve_domain(const bke::CurvesGeometry &src_curves)
IndexRange per_curve_point_offsets_range(const IndexRange points, const int curve_index)
void foreach_curve_by_type(const VArray< int8_t > &types, const std::array< int, CURVE_TYPES_NUM > &type_counts, const IndexMask &selection, FunctionRef< void(IndexMask)> catmull_rom_fn, FunctionRef< void(IndexMask)> poly_fn, FunctionRef< void(IndexMask)> bezier_fn, FunctionRef< void(IndexMask)> nurbs_fn)
Vector< AttributeTransferData > retrieve_attributes_for_transfer(const AttributeAccessor src_attributes, MutableAttributeAccessor dst_attributes, Span< AttrDomain > domains, const AttributeFilter &attribute_filter={})
constexpr ParallelGrainSize grain_size(int grain_size)
static HandleType aligned_or_free_handle_type(const HandleType type)
static void calculate_result_offsets(const OffsetIndices< int > src_points_by_curve, const IndexMask &selection, const IndexMask &unselected, const VArray< float > &radii, const VArray< int > &counts, const Span< bool > cyclic, MutableSpan< int > dst_curve_offsets, MutableSpan< int > dst_point_offsets)
static void subdivide_bezier_positions(const Span< float3 > src_positions, const Span< int8_t > src_types_l, const Span< int8_t > src_types_r, const Span< float3 > src_handles_l, const Span< float3 > src_handles_r, const OffsetIndices< int > evaluated_offsets, const bool cyclic, MutableSpan< float3 > dst_positions, MutableSpan< int8_t > dst_types_l, MutableSpan< int8_t > dst_types_r, MutableSpan< float3 > dst_handles_l, MutableSpan< float3 > dst_handles_r)
static void linear_interpolation(const T &a, const T &b, MutableSpan< T > dst)
bke::CurvesGeometry subdivide_curves(const bke::CurvesGeometry &src_curves, const IndexMask &selection, const VArray< int > &cuts, const bke::AttributeFilter &attribute_filter={})
static void subdivide_attribute_catmull_rom(const OffsetIndices< int > src_points_by_curve, const OffsetIndices< int > dst_points_by_curve, const IndexMask &selection, const Span< int > all_point_offsets, const Span< bool > cyclic, const GSpan src, GMutableSpan dst)
static void subdivide_bezier_segment(const float3 &position_prev, const float3 &handle_prev, const float3 &handle_next, const float3 &position_next, const HandleType type_prev, const HandleType type_next, const IndexRange segment_points, const int dst_next_segment_start, MutableSpan< float3 > dst_positions, MutableSpan< float3 > dst_handles_l, MutableSpan< float3 > dst_handles_r, MutableSpan< int8_t > dst_types_l, MutableSpan< int8_t > dst_types_r)
static void subdivide_attribute_linear(const OffsetIndices< int > src_points_by_curve, const OffsetIndices< int > dst_points_by_curve, const IndexMask &selection, const Span< int > all_point_offsets, const Span< T > src, MutableSpan< T > dst)
void copy_group_sizes(OffsetIndices< int > offsets, const IndexMask &mask, MutableSpan< int > sizes)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
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
void BKE_defgroup_copy_list(ListBaseT< bDeformGroup > *outbase, const ListBaseT< bDeformGroup > *inbase)
Definition deform.cc:75
VecBase< float, 3 > float3
ListBaseT< struct bDeformGroup > vertex_group_names