Blender V5.3
curves_extrude.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 "BKE_attribute.hh"
10#include "BKE_curves_utils.hh"
11
12#include "WM_api.hh"
13#include "WM_types.hh"
14
15#include "ED_curves.hh"
16
17#include "DEG_depsgraph.hh"
18
19namespace blender::ed::curves {
20
26static Span<int> compress_intervals(const OffsetIndices<int> intervals_by_curve,
27 MutableSpan<int> intervals)
28{
29 const int *src = intervals.data();
30 /* Skip the first curve, as all the data stays in the same place.
31 * -1 to drop index denoting curve's right endpoint.
32 */
33 int *dst = intervals.data() + intervals_by_curve[0].size() - 1;
34
35 for (const int curve : intervals_by_curve.index_range().drop_front(1)) {
36 const IndexRange range = intervals_by_curve[curve];
37 /* -2 one to drop index denoting curve's beginning, second one for ending. */
38 const int width = range.size() - 2;
39 std::copy_n(src + range.first() + 1, width, dst);
40 dst += width;
41 }
42 (*dst) = src[intervals_by_curve[intervals_by_curve.size() - 1].last()];
43 return {intervals.data(), dst - intervals.data() + 1};
44}
45
46static void calc_curves_extrusion(const IndexMask &selection,
47 const OffsetIndices<int> points_by_curve,
48 MutableSpan<int> copy_intervals,
49 MutableSpan<int> curves_intervals_offsets,
50 MutableSpan<bool> is_first_selected)
51{
52 int current_endpoint_index = 0;
53 curves_intervals_offsets.first() = 0;
54
56 selection,
57 points_by_curve,
58 [&](const int curve,
59 const IndexRange curve_points,
60 const Span<IndexRange> selected_point_ranges) {
61 const IndexRange first_range = selected_point_ranges.first();
62 is_first_selected[curve] = first_range.first() == curve_points.start() &&
63 first_range.size() == 1 &&
64 /* If single point curve is extruded we want the newly created
65 * point to get selected. */
66 curve_points.size() != 1;
67 current_endpoint_index += !is_first_selected[curve];
68 copy_intervals[curves_intervals_offsets[curve]] = curve_points.start();
69
70 for (const IndexRange range : selected_point_ranges) {
71 copy_intervals[current_endpoint_index++] = range.first();
72 copy_intervals[current_endpoint_index++] = range.last();
73 }
74
75 const int last_interval_index = current_endpoint_index - 1;
76 if (copy_intervals[last_interval_index] != curve_points.last() ||
77 copy_intervals[last_interval_index - 1] != copy_intervals[last_interval_index])
78 {
79 /* Append last point of the current curve if it is not extruded or extruded together with
80 * preceding points. */
81 copy_intervals[current_endpoint_index++] = curve_points.last();
82 }
83
84 curves_intervals_offsets[curve + 1] = current_endpoint_index;
85 },
86 [&](const IndexRange curves, [[maybe_unused]] const IndexRange unselected_points) {
87 for (const int curve : curves) {
88 const IndexRange curve_points = points_by_curve[curve];
89 /* Setup interval to copy full curve. */
90 is_first_selected[curve] = false;
91 copy_intervals[current_endpoint_index++] = curve_points.first();
92 copy_intervals[current_endpoint_index++] = curve_points.last();
93 curves_intervals_offsets[curve + 1] = current_endpoint_index;
94 }
95 });
96}
97
98static void calc_new_offsets(const Span<int> old_offsets,
99 const Span<int> curves_intervals_offsets,
100 MutableSpan<int> new_offsets)
101{
102 new_offsets.first() = 0;
103 const IndexRange range = old_offsets.index_range().drop_back(1).shift(1);
104 threading::parallel_for(range, 256, [&](IndexRange index_range) {
105 for (const int i : index_range) {
106 /* -1 subtracts last interval endpoint and gives number of intervals.
107 * Another -1 from number of intervals gives number of new points created for curve.
108 * Multiplied by i because -2 are accumulated for each curve.
109 */
110 new_offsets[i] = old_offsets[i] + curves_intervals_offsets[i] - 2 * i;
111 }
112 });
113}
114
118static IndexRange shift_end_by(const IndexRange &range, const int n)
119{
120 return IndexRange::from_begin_size(range.start(), range.size() + n);
121}
122
123static float clamp_to_zero(const float value)
124{
125 return math::abs(value) < 0.00001 ? 0.0 : value;
126}
127
129 const OffsetIndices<int> intervals_by_curve,
130 const OffsetIndices<int> copy_intervals,
131 const Span<bool> is_first_selected,
132 bke::CurvesGeometry &dst_curves)
133{
134 IndexMaskMemory memory;
135 const IndexMask custom_knot_curves = curves.nurbs_custom_knot_curves(memory);
136 const Span<float> src_knots = curves.nurbs_custom_knots();
137 const VArray<int8_t> orders = curves.nurbs_orders();
138 const OffsetIndices<int> src_knots_by_curve = curves.nurbs_custom_knots_by_curve();
139
141 MutableSpan<float> dst_knots = dst_curves.nurbs_custom_knots_for_write();
142
143 custom_knot_curves.foreach_index(
144 [&](const int64_t curve) {
145 const int order = orders[curve];
146 const bool is_first_interval_selected = is_first_selected[curve];
147 Span<float> src_curve_knots = src_knots.slice(src_knots_by_curve[curve]);
148
149 Array<float> curve_span_data(src_curve_knots.size() - 1);
150 Array<int> span_multiplicity(curve_span_data.size(), 0);
151
152 int span = 0;
153 curve_span_data[span] = clamp_to_zero(src_curve_knots[1] - src_curve_knots[0]);
154 span_multiplicity[span] = 1;
155
156 for (const int i : src_curve_knots.index_range().drop_back(1).drop_front(1)) {
157 const float span_value = clamp_to_zero(src_curve_knots[i + 1] - src_curve_knots[i]);
158 const bool is_new = abs(curve_span_data[span] - span_value) >= 0.00001;
159 span += is_new;
160 curve_span_data[span] = span_value;
161 span_multiplicity[span]++;
162 }
163
164 MutableSpan<float> curve_spans = curve_span_data.as_mutable_span().slice(0, span + 1);
165
166 const IndexRange curve_intervals = intervals_by_curve[curve];
167 const Span<int> duplicated_points =
168 copy_intervals.data().slice(curve_intervals).drop_front(1).drop_back(1);
169 const int first_curve_point = copy_intervals.data()[curve_intervals.first()];
170 Vector<int> increase_span_multiplicity;
171 increase_span_multiplicity.reserve(duplicated_points.size());
172 int first_span_knot = 0;
173 span = 0;
174
175 for (const int i : duplicated_points.index_range()) {
176 const bool is_selected = bool(i % 2) != is_first_interval_selected;
177 const int point = duplicated_points[i] - first_curve_point;
178 while (first_span_knot + span_multiplicity[span] <= point) {
179 first_span_knot += span_multiplicity[span];
180 span++;
181 }
182
183 int multiplicity = point - first_span_knot;
184 int point_span = span;
185 std::array<int, 2> side_spans{point_span, point_span};
186 int side = 0;
187 for ([[maybe_unused]] const int i : IndexRange(order)) {
188 multiplicity++;
189 if (multiplicity > span_multiplicity[point_span]) {
190 point_span++;
191 multiplicity = 1;
192 }
193 if (curve_spans[point_span] == 0.0) {
194 continue;
195 }
196 side_spans[side] = point_span;
197 side = 1;
198 side_spans[side] = point_span;
199 }
200 increase_span_multiplicity.append(side_spans[is_selected]);
201 }
202 for (const int span : increase_span_multiplicity) {
203 span_multiplicity[span]++;
204 }
205
206 const OffsetIndices<int> dst_knots_by_curve = dst_curves.nurbs_custom_knots_by_curve();
207 MutableSpan<float> dst_curve_knots = dst_knots.slice(dst_knots_by_curve[curve]);
208 int knot = 0;
209 float knot_value = src_curve_knots[knot];
210 dst_curve_knots[knot++] = knot_value;
211 for (const int span : curve_spans.index_range()) {
212 for ([[maybe_unused]] const int k : IndexRange(span_multiplicity[span])) {
213 knot_value += curve_spans[span];
214 dst_curve_knots[knot++] = knot_value;
215 }
216 }
217 },
219}
220
222 const IndexMask &extruded_points)
223{
224
226
227 const int curves_num = curves.curves_num();
228
229 /* Buffer for intervals of all curves. Beginning and end of a curve can be determined only by
230 * #curve_interval_ranges. For ex. [0, 3, 4, 4, 4] indicates one copy interval for first curve
231 * [0, 3] and two for second [4, 4][4, 4]. The first curve will be copied as is without changes,
232 * in the second one (consisting only one point - 4) first point will be duplicated (extruded).
233 */
234 Array<int> copy_interval_offsets(extruded_points.size() * 2 + curves_num * 2);
235
236 /* Points to intervals for each curve in the copy_intervals array.
237 * For example above value would be [0, 3, 5]. Meaning that [0 .. 2] are indices for curve 0 in
238 * copy_intervals array, [3 .. 4] for curve 1. */
239 Array<int> curves_intervals_offsets(curves_num + 1);
240
241 /* Per curve boolean indicating if first interval in a curve is selected.
242 * Other can be calculated as in a curve two adjacent intervals can not have same selection
243 * state. */
244 Array<bool> is_first_selected(curves_num);
245
246 calc_curves_extrusion(extruded_points,
247 curves.points_by_curve(),
248 copy_interval_offsets,
249 curves_intervals_offsets,
250 is_first_selected);
251
252 MutableSpan<int> new_offsets = new_curves.offsets_for_write();
253 calc_new_offsets(curves.offsets(), curves_intervals_offsets, new_offsets);
254 new_curves.resize(new_offsets.last(), new_curves.curves_num());
255
256 const bke::AttributeAccessor src_attributes = curves.attributes();
257
258 std::array<GVArraySpan, 3> src_selection;
259 std::array<bke::GSpanAttributeWriter, 3> dst_selections;
260
261 const Span<StringRef> selection_attr_names = get_curves_selection_attribute_names(curves);
262 for (const int selection_i : selection_attr_names.index_range()) {
263 const StringRef selection_name = selection_attr_names[selection_i];
264
265 GVArray src_selection_array = *src_attributes.lookup(selection_name, bke::AttrDomain::Point);
266 if (!src_selection_array) {
267 src_selection_array = VArray<bool>::from_single(true, curves.points_num());
268 }
269
270 src_selection[selection_i] = src_selection_array;
271 dst_selections[selection_i] = ensure_selection_attribute(
272 new_curves,
274 src_selection_array.type().is<bool>() ? bke::AttrType::Bool : bke::AttrType::Float,
275 selection_name);
276 }
277
278 const OffsetIndices<int> intervals_by_curve = curves_intervals_offsets.as_span();
279 const OffsetIndices<int> copy_intervals = copy_interval_offsets.as_span().slice(
280 0, curves_intervals_offsets.last());
281
282 threading::parallel_for(curves.curves_range(), 256, [&](IndexRange curves_range) {
283 for (const int curve : curves_range) {
284 const int first_index = intervals_by_curve[curve].start();
285 const int first_value = copy_intervals[first_index].start();
286 const bool first_selected = is_first_selected[curve];
287
288 for (const int i : intervals_by_curve[curve].drop_back(1)) {
289 const bool is_selected = bool((i - first_index) % 2) != first_selected;
290 const IndexRange src = shift_end_by(copy_intervals[i], 1);
291 const IndexRange dst = src.shift(new_offsets[curve] - first_value + i - first_index);
292
293 for (const int selection_i : selection_attr_names.index_range()) {
294 GMutableSpan dst_span = dst_selections[selection_i].span.slice(dst);
295 if (is_selected) {
296 GSpan src_span = src_selection[selection_i].slice(src);
297 src_selection[selection_i].type().copy_assign_n(
298 src_span.data(), dst_span.data(), src.size());
299 }
300 else {
301 fill_selection(dst_span, false);
302 }
303 }
304 }
305 }
306 });
307
308 for (const int selection_i : selection_attr_names.index_range()) {
309 dst_selections[selection_i].finish();
310 }
311
312 if (curves.nurbs_has_custom_knots()) {
313 extrude_knots(curves, intervals_by_curve, copy_intervals, is_first_selected, new_curves);
314 }
315
316 const OffsetIndices<int> compact_intervals = compress_intervals(intervals_by_curve,
317 copy_interval_offsets);
318
319 bke::MutableAttributeAccessor dst_attributes = new_curves.attributes_for_write();
320
322 src_attributes,
323 dst_attributes,
325 bke::attribute_filter_from_skip_ref(selection_attr_names)))
326 {
327 const CPPType &type = attribute.src.type();
328 threading::parallel_for(compact_intervals.index_range(), 512, [&](IndexRange range) {
329 for (const int i : range) {
330 const IndexRange src = shift_end_by(compact_intervals[i], 1);
331 const IndexRange dst = src.shift(i);
332 type.copy_assign_n(
333 attribute.src.slice(src).data(), attribute.dst.span.slice(dst).data(), src.size());
334 }
335 });
336 attribute.dst.finish();
337 }
338 return new_curves;
339}
340
342{
343 bool extruded = false;
344 for (Curves *curves_id : get_unique_editable_curves(*C)) {
345 const bke::AttrDomain selection_domain = bke::AttrDomain(curves_id->selection_domain);
346 if (selection_domain != bke::AttrDomain::Point) {
347 continue;
348 }
349
350 const bke::CurvesGeometry &curves = curves_id->geometry.wrap();
351 IndexMaskMemory memory;
352 const IndexMask extruded_points = retrieve_selected_points(curves, memory);
353 if (extruded_points.is_empty()) {
354 continue;
355 }
356
357 curves_id->geometry.wrap() = extrude_curves(curves, extruded_points);
358 DEG_id_tag_update(&curves_id->id, ID_RECALC_GEOMETRY);
359 extruded = true;
360 }
361 return extruded ? OPERATOR_FINISHED : OPERATOR_CANCELLED;
362}
363
365{
366 ot->name = "Extrude";
367 ot->description = "Extrude selected control point(s)";
368 ot->idname = "CURVES_OT_extrude";
369
372
374}
375
376} // namespace blender::ed::curves
Low-level operations for curves.
#define C
Definition RandGen.cpp:29
int64_t size() const
Definition BLI_array.hh:267
Span< T > as_span() const
Definition BLI_array.hh:254
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
const T & last(const int64_t n=0) const
Definition BLI_array.hh:307
bool is() const
constexpr int64_t first() const
constexpr IndexRange shift(int64_t n) 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()=default
static constexpr IndexRange from_begin_size(const int64_t begin, const int64_t size)
constexpr int64_t start() const
constexpr IndexRange drop_front(int64_t n) const
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition BLI_span.hh:579
constexpr T * data() const
Definition BLI_span.hh:545
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
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr const T & first() const
Definition BLI_span.hh:319
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
static VArray from_single(T value, const int64_t size)
void append(const T &value)
void reserve(const int64_t min_capacity)
GAttributeReader lookup(const StringRef name) const
void resize(int points_num, int curves_num)
OffsetIndices< int > nurbs_custom_knots_by_curve() const
MutableSpan< float > nurbs_custom_knots_for_write()
MutableSpan< int > offsets_for_write()
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
#define attribute(slot)
#define abs
void foreach_selected_point_ranges_per_curve(const IndexMask &mask, OffsetIndices< int > points_by_curve, SelectedCallback selected_fn)
bke::CurvesGeometry copy_only_curve_domain(const bke::CurvesGeometry &src_curves)
auto attribute_filter_from_skip_ref(const Span< StringRef > skip)
Vector< AttributeTransferData > retrieve_attributes_for_transfer(const AttributeAccessor src_attributes, MutableAttributeAccessor dst_attributes, Span< AttrDomain > domains, const AttributeFilter &attribute_filter={})
static bke::CurvesGeometry extrude_curves(const bke::CurvesGeometry &curves, const IndexMask &extruded_points)
IndexMask retrieve_selected_points(const bke::CurvesGeometry &curves, LinearAllocator<> &memory)
static void calc_new_offsets(const Span< int > old_offsets, const Span< int > curves_intervals_offsets, MutableSpan< int > new_offsets)
VectorSet< Curves * > get_unique_editable_curves(const bContext &C)
static void calc_curves_extrusion(const IndexMask &selection, const OffsetIndices< int > points_by_curve, MutableSpan< int > copy_intervals, MutableSpan< int > curves_intervals_offsets, MutableSpan< bool > is_first_selected)
static float clamp_to_zero(const float value)
bool editable_curves_in_edit_mode_poll(bContext *C)
static void extrude_knots(const bke::CurvesGeometry &curves, const OffsetIndices< int > intervals_by_curve, const OffsetIndices< int > copy_intervals, const Span< bool > is_first_selected, bke::CurvesGeometry &dst_curves)
Span< StringRef > get_curves_selection_attribute_names(const bke::CurvesGeometry &curves)
static Span< int > compress_intervals(const OffsetIndices< int > intervals_by_curve, MutableSpan< int > intervals)
static wmOperatorStatus curves_extrude_exec(bContext *C, wmOperator *)
static IndexRange shift_end_by(const IndexRange &range, const int n)
bke::GSpanAttributeWriter ensure_selection_attribute(bke::CurvesGeometry &curves, bke::AttrDomain selection_domain, bke::AttrType create_type, StringRef attribute_name)
void CURVES_OT_extrude(wmOperatorType *ot)
constexpr ParallelGrainSize grain_size(int grain_size)
T abs(const T &a)
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
__int64 int64_t
Definition BKE_text.h:90
void DEG_id_tag_update(ID *id, unsigned int flags)
@ ID_RECALC_GEOMETRY
Definition DNA_ID.h:1074
@ OPTYPE_REGISTER
Definition WM_types.hh:188
@ OPTYPE_UNDO
Definition WM_types.hh:190
wmOperatorStatus(*) exec(bContext *C, wmOperator *op) ATTR_WARN_UNUSED_RESULT
Definition WM_types.hh:1125
const char * description
Definition WM_types.hh:1115
bool(*) poll(bContext *C) ATTR_WARN_UNUSED_RESULT
Definition WM_types.hh:1165