Blender V5.3
merge_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
9#include "BLI_array_utils.hh"
10#include "BLI_stack.hh"
11
12#include "BKE_curves_utils.hh"
13#include "BKE_deform.hh"
14
15#include "GEO_merge_curves.hh"
16
17namespace blender::geometry {
18
19enum Flag {
22};
23
24template<typename Fn>
25static void foreach_connected_curve(const Span<int> connect_to_curve,
27 const int start,
28 Fn fn)
29{
30 const IndexRange range = connect_to_curve.index_range();
31
32 Stack<int> stack;
33
34 bool has_cycle = false;
35 auto push_curve = [&](const int curve_i) -> bool {
36 if ((flags[curve_i] & Inserted) != 0) {
37 return false;
38 }
39 if ((flags[curve_i] & OnStack) != 0) {
40 has_cycle = true;
41 return false;
42 }
43 stack.push(curve_i);
44 flags[curve_i] |= OnStack;
45 fn(curve_i);
46 return true;
47 };
48
49 push_curve(start);
50
51 while (!stack.is_empty()) {
52 const int current = stack.peek();
53
54 const int next = connect_to_curve[current];
55 if (range.contains(next)) {
56 if (push_curve(next)) {
57 continue;
58 }
59 }
60
61 flags[current] |= Inserted;
62 stack.pop();
63 }
64
65 UNUSED_VARS(has_cycle);
66}
67
68/* Topological sorting that puts connected curves into contiguous ranges. */
69static Vector<int> toposort_connected_curves(const Span<int> connect_to_curve)
70{
71 const IndexRange range = connect_to_curve.index_range();
72
73 Array<uint8_t> flags(connect_to_curve.size());
74
75 /* First add all open chains by finding curves without a connection. */
76 Array<bool> is_start_curve(range.size(), true);
77 for (const int curve_i : range) {
78 const int next = connect_to_curve[curve_i];
79 if (range.contains(next)) {
80 is_start_curve[next] = false;
81 }
82 }
83 /* Mark all curves that can be reached from a start curve. These must not be added before the
84 * start curve, or it can lead to gaps in curve ranges. */
85 flags.fill(0);
86 Array<bool> is_reachable(range.size(), false);
87 for (const int curve_i : range) {
88 if (is_start_curve[curve_i]) {
90 connect_to_curve, flags, curve_i, [&](const int index) { is_reachable[index] = true; });
91 }
92 }
93
94 Vector<int> sorted_curves;
95 sorted_curves.reserve(connect_to_curve.size());
96
97 flags.fill(0);
98 for (const int curve_i : range) {
99 if (is_start_curve[curve_i] || !is_reachable[curve_i]) {
101 connect_to_curve, flags, curve_i, [&](const int index) { sorted_curves.append(index); });
102 }
103 }
104
105 BLI_assert(sorted_curves.size() == range.size());
106 return sorted_curves;
107}
108
109/* TODO Add an optimized function for reversing the order of spans. */
111{
112 const CPPType &cpptype = span.type();
113 BUFFER_FOR_CPP_TYPE_VALUE(cpptype, buffer);
114 cpptype.default_construct(buffer);
115
116 for (const int i : IndexRange(span.size() / 2)) {
117 const int mirror_i = span.size() - 1 - i;
118 /* Swap. */
119 cpptype.move_assign(span[i], buffer);
120 cpptype.move_assign(span[mirror_i], span[i]);
121 cpptype.move_assign(buffer, span[mirror_i]);
122 }
123
124 cpptype.destruct(buffer);
125}
126
128 const bke::AttributeAccessor src_attributes,
129 const bke::AttrDomain domain,
130 const OffsetIndices<int> src_offsets,
131 const OffsetIndices<int> dst_offsets,
132 const Span<int> old_by_new_map,
133 const Span<bool> flip_direction,
134 bke::MutableAttributeAccessor dst_attributes)
135{
136 src_attributes.foreach_attribute([&](const bke::AttributeIter &iter) {
137 if (iter.domain != domain) {
138 return;
139 }
140 if (iter.data_type == bke::AttrType::String) {
141 return;
142 }
143 const GVArray src = *iter.get(domain);
144 const CommonVArrayInfo info = src.common_info();
146 const bke::AttributeInitValue init(GPointer(src.type(), info.data));
147 if (dst_attributes.add(iter.name, iter.domain, iter.data_type, init)) {
148 return;
149 }
150 }
152 iter.name, domain, iter.data_type);
153 if (!dst) {
154 return;
155 }
156
157 threading::parallel_for(old_by_new_map.index_range(), 1024, [&](const IndexRange range) {
158 for (const int new_i : range) {
159 const int old_i = old_by_new_map[new_i];
160 const bool flip = flip_direction[old_i];
161
162 GMutableSpan dst_span = dst.span.slice(dst_offsets[new_i]);
163 array_utils::copy(src.slice(src_offsets[old_i]), dst_span);
164 if (flip) {
165 reverse_order(dst_span);
166 }
167 }
168 });
169
170 dst.finish();
171 });
172}
173
175 const Span<int> old_by_new_map,
176 const Span<bool> flip_direction)
177{
178 bke::CurvesGeometry dst_curves = bke::CurvesGeometry(src_curves);
179
183 {},
184 old_by_new_map,
185 dst_curves.attributes_for_write());
186
187 const Span<int> old_offsets = src_curves.offsets();
188 MutableSpan<int> new_offsets = dst_curves.offsets_for_write();
189 offset_indices::gather_group_sizes(old_offsets, old_by_new_map, new_offsets);
191
194 old_offsets,
195 new_offsets.as_span(),
196 old_by_new_map,
197 flip_direction,
198 dst_curves.attributes_for_write());
199 dst_curves.tag_topology_changed();
200 return dst_curves;
201}
202
203/* Build new offsets array for connected ranges. */
204static void find_connected_ranges(const bke::CurvesGeometry &src_curves,
205 const Span<int> old_by_new_map,
206 Span<int> connect_to_curve,
207 Span<bool> cyclic,
208 Vector<int> &r_joined_curve_offsets,
209 Vector<bool> &r_joined_cyclic)
210{
211 const IndexRange curves_range = src_curves.curves_range();
212
213 Array<int> new_by_old_map(old_by_new_map.size());
214 for (const int dst_i : old_by_new_map.index_range()) {
215 const int src_i = old_by_new_map[dst_i];
216 new_by_old_map[src_i] = dst_i;
217 }
218
219 r_joined_curve_offsets.reserve(curves_range.size() + 1);
220 r_joined_cyclic.reserve(curves_range.size());
221
222 int start_index = -1;
223 for (const int dst_i : curves_range) {
224 const int src_i = old_by_new_map[dst_i];
225 /* Strokes are cyclic if they are not connected and the original stroke is cyclic, or if the
226 * the last stroke of a chain is merged with the first stroke. */
227 const bool src_cyclic = cyclic[src_i];
228
229 if (start_index < 0) {
230 r_joined_curve_offsets.append(0);
231 r_joined_cyclic.append(src_cyclic);
232 start_index = dst_i;
233 }
234
235 ++r_joined_curve_offsets.last();
236
237 const int src_connect_to = connect_to_curve[src_i];
238 const bool is_connected = curves_range.contains(src_connect_to);
239 const int dst_connect_to = is_connected ? new_by_old_map[src_connect_to] : -1;
240
241 /* Check for end of chain. */
242 if (dst_connect_to != dst_i + 1) {
243 /* Set cyclic state for connected curves.
244 * Becomes cyclic if connected to the start. */
245 const bool is_chain = (is_connected || dst_i != start_index);
246 if (is_chain) {
247 r_joined_cyclic.last() = (dst_connect_to == start_index);
248 }
249 /* Start new curve. */
250 start_index = -1;
251 }
252 }
253 /* Offsets has one more entry for the overall size. */
254 r_joined_curve_offsets.append(0);
255
256 offset_indices::accumulate_counts_to_offsets(r_joined_curve_offsets);
257}
258
260 const OffsetIndices<int> old_curves_by_new)
261{
262 bke::CurvesGeometry dst_curves = bke::CurvesGeometry(src_curves.points_num(),
263 old_curves_by_new.size());
264 /* Copy vertex group names. */
266 dst_curves.attributes_active_index = src_curves.attributes_active_index;
267
268 /* NOTE: using the offsets as an index map means the first curve of each range is used for
269 * attributes. */
270 const Span<int> old_by_new_map = old_curves_by_new.data().drop_back(1);
275 old_by_new_map,
276 dst_curves.attributes_for_write());
277
278 const OffsetIndices old_points_by_curve = src_curves.points_by_curve();
279 MutableSpan<int> new_offsets = dst_curves.offsets_for_write();
280 new_offsets.fill(0);
281 for (const int new_i : new_offsets.index_range().drop_back(1)) {
282 const IndexRange old_curves = old_curves_by_new[new_i];
283 new_offsets[new_i] = offset_indices::sum_group_sizes(old_points_by_curve, old_curves);
284 }
286
287 /* Point attributes copied without changes. */
288 bke::copy_attributes(src_curves.attributes(),
291 {},
292 dst_curves.attributes_for_write());
293
294 dst_curves.tag_topology_changed();
295 return dst_curves;
296}
297
299 Span<int> connect_to_curve,
300 Span<bool> flip_direction,
301 const bke::AttributeFilter & /*attribute_filter*/)
302{
303 BLI_assert(connect_to_curve.size() == src_curves.curves_num());
304 const VArraySpan<bool> src_cyclic = src_curves.cyclic();
305
306 Vector<int> old_by_new_map = toposort_connected_curves(connect_to_curve);
307
308 Vector<int> joined_curve_offsets;
309 Vector<bool> cyclic;
311 src_curves, old_by_new_map, connect_to_curve, src_cyclic, joined_curve_offsets, cyclic);
312
314 src_curves, old_by_new_map, flip_direction);
315
316 OffsetIndices joined_curves_by_new = OffsetIndices<int>(joined_curve_offsets);
317 bke::CurvesGeometry merged_curves = join_curves_ranges(ordered_curves, joined_curves_by_new);
318 merged_curves.cyclic_for_write().copy_from(cyclic);
319
324 if (src_curves.nurbs_has_custom_knots()) {
328 merged_curves);
329 }
330 return merged_curves;
331}
332
333} // namespace blender::geometry
Low-level operations for curves.
support for deformation groups and hooks.
#define BUFFER_FOR_CPP_TYPE_VALUE(type, variable_name)
#define UNUSED_VARS(...)
void fill(const T &value) const
Definition BLI_array.hh:283
void move_assign(void *src, void *dst) const
void destruct(void *ptr) const
void default_construct(void *ptr) const
const CPPType & type() const
GPointer()=default
CommonVArrayInfo common_info() const
constexpr IndexRange drop_back(int64_t n) const
constexpr int64_t size() const
constexpr IndexRange()=default
constexpr bool contains(int64_t value) const
constexpr void fill(const T &value) const
Definition BLI_span.hh:523
constexpr Span< T > as_span() const
Definition BLI_span.hh:667
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
bool is_empty() const
Definition BLI_stack.hh:310
void push(const T &value)
Definition BLI_stack.hh:215
int64_t size() const
void append(const T &value)
const T & last(const int64_t n=0) const
void reserve(const int64_t min_capacity)
void foreach_attribute(const FunctionRef< void(const AttributeIter &)> fn) const
GAttributeReader get() const
VArray< bool > cyclic() const
AttributeAccessor attributes() const
IndexRange curves_range() const
MutableSpan< int > offsets_for_write()
MutableSpan< bool > cyclic_for_write()
OffsetIndices< int > points_by_curve() const
MutableAttributeAccessor attributes_for_write()
bool add(const StringRef name, const AttrDomain domain, const AttrType data_type, const AttributeInit &initializer)
GSpanAttributeWriter lookup_or_add_for_write_only_span(StringRef name, AttrDomain domain, AttrType data_type)
void update_custom_knot_modes(const IndexMask &mask, const KnotsMode mode_for_regular, const KnotsMode mode_for_cyclic, bke::CurvesGeometry &curves)
auto attribute_filter_from_skip_ref(const Span< StringRef > skip)
void copy_attributes(const AttributeAccessor src_attributes, AttrDomain src_domain, AttrDomain dst_domain, const AttributeFilter &attribute_filter, MutableAttributeAccessor dst_attributes)
void gather_attributes(AttributeAccessor src_attributes, AttrDomain src_domain, AttrDomain dst_domain, const AttributeFilter &attribute_filter, const IndexMask &selection, MutableAttributeAccessor dst_attributes)
static Vector< int > toposort_connected_curves(const Span< int > connect_to_curve)
static bke::CurvesGeometry reorder_and_flip_curves(const bke::CurvesGeometry &src_curves, const Span< int > old_by_new_map, const Span< bool > flip_direction)
static void foreach_connected_curve(const Span< int > connect_to_curve, MutableSpan< uint8_t > flags, const int start, Fn fn)
static void reorder_and_flip_attributes_group_to_group(const bke::AttributeAccessor src_attributes, const bke::AttrDomain domain, const OffsetIndices< int > src_offsets, const OffsetIndices< int > dst_offsets, const Span< int > old_by_new_map, const Span< bool > flip_direction, bke::MutableAttributeAccessor dst_attributes)
static void reverse_order(GMutableSpan span)
static bke::CurvesGeometry join_curves_ranges(const bke::CurvesGeometry &src_curves, const OffsetIndices< int > old_curves_by_new)
static void find_connected_ranges(const bke::CurvesGeometry &src_curves, const Span< int > old_by_new_map, Span< int > connect_to_curve, Span< bool > cyclic, Vector< int > &r_joined_curve_offsets, Vector< bool > &r_joined_cyclic)
bke::CurvesGeometry curves_merge_endpoints(const bke::CurvesGeometry &src_curves, Span< int > connect_to_curve, Span< bool > flip_direction, const bke::AttributeFilter &attribute_filter)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
void gather_group_sizes(OffsetIndices< int > offsets, const IndexMask &mask, MutableSpan< int > sizes)
int sum_group_sizes(OffsetIndices< int > offsets, const IndexMask &mask)
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)
@ NURBS_KNOT_MODE_NORMAL
void BKE_defgroup_copy_list(ListBaseT< bDeformGroup > *outbase, const ListBaseT< bDeformGroup > *inbase)
Definition deform.cc:75
ListBaseT< struct bDeformGroup > vertex_group_names