Blender V5.3
fit_curves.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2025 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include "BLI_array_utils.hh"
10#include "BLI_task.hh"
11
12#include "BKE_curves_utils.hh"
13#include "BKE_deform.hh"
14
15#include "GEO_fit_curves.hh"
16
17namespace blender {
18
19extern "C" {
20#include "curve_fit_nd.h"
21}
22
23namespace geometry {
24
26 const IndexMask &curve_selection,
27 const VArray<float> &thresholds,
28 const VArray<bool> &corners,
29 const FitMethod method,
30 const bke::AttributeFilter &attribute_filter)
31{
32 if (curve_selection.is_empty()) {
33 return src_curves;
34 }
35
36 BLI_assert(thresholds.size() == src_curves.curves_num());
37 BLI_assert(corners.size() == src_curves.points_num());
38
39 const OffsetIndices src_points_by_curve = src_curves.offsets();
40 const Span<float3> src_positions = src_curves.positions();
41 const VArray<bool> src_cyclic = src_curves.cyclic();
42
45
46 IndexMaskMemory memory;
47 const IndexMask unselected_curves = curve_selection.complement(src_curves.curves_range(),
48 memory);
49
50 /* Write the new sizes to the dst_curve_sizes, they will be accumulated later to offsets. */
51 MutableSpan<int> dst_curve_sizes = dst_curves.offsets_for_write();
52 offset_indices::copy_group_sizes(src_points_by_curve, unselected_curves, dst_curve_sizes);
53 MutableSpan<int8_t> dst_curve_types = dst_curves.curve_types_for_write();
54
55 /* NOTE: These spans own the data from the curve fit C-API. */
56 Array<MutableSpan<float3>> cubic_array_per_curve(curve_selection.size());
57 Array<MutableSpan<int>> corner_indices_per_curve(curve_selection.size());
58 Array<MutableSpan<int>> original_indices_per_curve(curve_selection.size());
59
60 std::atomic<bool> success = false;
61 curve_selection.foreach_index(
62 [&](const int64_t curve_i, const int64_t pos) {
63 const IndexRange points = src_points_by_curve[curve_i];
64 if (points.size() < 2) {
65 dst_curve_sizes[curve_i] = points.size();
66 dst_curve_types[curve_i] = CURVE_TYPE_POLY;
67 return;
68 }
69 const Span<float3> curve_positions = src_positions.slice(points);
70 const bool is_cyclic = src_cyclic[curve_i];
71 const float epsilon = thresholds[curve_i];
72
73 /* Both curve fitting algorithms expect the first and last points for non-cyclic curves to
74 * be treated as if they were corners. */
75 const bool use_first_as_corner = !is_cyclic && !corners[points.first()];
76 const bool use_last_as_corner = !is_cyclic && !corners[points.last()];
77 Vector<int, 32> src_corners;
78 if (use_first_as_corner) {
79 src_corners.append(0);
80 }
81 if (points.size() > 2) {
82 for (const int i : IndexRange::from_begin_end(1, points.size() - 1)) {
83 if (corners[points[i]]) {
84 src_corners.append(i);
85 }
86 }
87 }
88 if (use_last_as_corner) {
89 src_corners.append(points.last());
90 }
91 const uint *src_corners_ptr = src_corners.is_empty() ?
92 nullptr :
93 reinterpret_cast<uint *>(src_corners.data());
94
95 const uint8_t flag = CURVE_FIT_CALC_HIGH_QUALITY |
96 ((is_cyclic) ? CURVE_FIT_CALC_CYCLIC : 0);
97
98 float *cubic_array = nullptr;
99 uint32_t *orig_index_map = nullptr;
100 uint32_t cubic_array_size = 0;
101 uint32_t *corner_index_array = nullptr;
102 uint32_t corner_index_array_size = 0;
103 int error = 1;
104 if (method == FitMethod::Split) {
105 error = curve_fit_cubic_to_points_fl(curve_positions.cast<float>().data(),
106 curve_positions.size(),
107 3,
108 epsilon,
109 flag,
110 src_corners_ptr,
111 src_corners.size(),
112 &cubic_array,
113 &cubic_array_size,
114 &orig_index_map,
115 &corner_index_array,
116 &corner_index_array_size);
117 }
118 else if (method == FitMethod::Refit) {
119 error = curve_fit_cubic_to_points_refit_fl(curve_positions.cast<float>().data(),
120 curve_positions.size(),
121 3,
122 epsilon,
123 flag,
124 src_corners_ptr,
125 src_corners.size(),
126 /* Don't use automatic corner detection. */
127 FLT_MAX,
128 &cubic_array,
129 &cubic_array_size,
130 &orig_index_map,
131 &corner_index_array,
132 &corner_index_array_size);
133 }
134
135 if (error) {
136 /* Some error occurred. Fall back to using the input positions as the (poly) curve. */
137 dst_curve_sizes[curve_i] = points.size();
138 dst_curve_types[curve_i] = CURVE_TYPE_POLY;
139 return;
140 }
141
142 success.store(true, std::memory_order_relaxed);
143
144 const int dst_points_num = cubic_array_size;
145 BLI_assert(dst_points_num > 0);
146
147 dst_curve_sizes[curve_i] = dst_points_num;
148 dst_curve_types[curve_i] = CURVE_TYPE_BEZIER;
149
150 cubic_array_per_curve[pos] = MutableSpan<float3>(reinterpret_cast<float3 *>(cubic_array),
151 dst_points_num * 3);
152 corner_indices_per_curve[pos] = MutableSpan<int>(
153 reinterpret_cast<int *>(corner_index_array), corner_index_array_size);
154 original_indices_per_curve[pos] = MutableSpan<int>(reinterpret_cast<int *>(orig_index_map),
155 dst_points_num);
156 },
158
159 if (!success) {
160 /* None of the curve fittings succeeded. */
161 return src_curves;
162 }
163
165 dst_curve_sizes);
166 dst_curves.resize(dst_curves.offsets().last(), dst_curves.curves_num());
167
168 const std::optional<Span<float3>> src_handles_left = src_curves.handle_positions_left();
169 const std::optional<Span<float3>> src_handles_right = src_curves.handle_positions_right();
170 const VArraySpan<int8_t> src_handle_types_left = src_curves.handle_types_left();
171 const VArraySpan<int8_t> src_handle_types_right = src_curves.handle_types_right();
172
173 MutableSpan<float3> dst_positions = dst_curves.positions_for_write();
174 MutableSpan<float3> dst_handles_left = dst_curves.handle_positions_left_for_write();
175 MutableSpan<float3> dst_handles_right = dst_curves.handle_positions_right_for_write();
176 MutableSpan<int8_t> dst_handle_types_left = dst_curves.handle_types_left_for_write();
177 MutableSpan<int8_t> dst_handle_types_right = dst_curves.handle_types_right_for_write();
178
179 /* First handle the unselected curves. */
180 if (src_handles_left) {
181 array_utils::copy_group_to_group(src_points_by_curve,
182 dst_points_by_curve,
183 unselected_curves,
184 *src_handles_left,
185 dst_handles_left);
186 }
188 src_points_by_curve, dst_points_by_curve, unselected_curves, src_positions, dst_positions);
189 if (src_handles_right) {
190 array_utils::copy_group_to_group(src_points_by_curve,
191 dst_points_by_curve,
192 unselected_curves,
193 *src_handles_right,
194 dst_handles_right);
195 }
196 if (!src_handle_types_left.is_empty()) {
197 array_utils::copy_group_to_group(src_points_by_curve,
198 dst_points_by_curve,
199 unselected_curves,
200 src_handle_types_left,
201 dst_handle_types_left);
202 }
203 if (!src_handle_types_right.is_empty()) {
204 array_utils::copy_group_to_group(src_points_by_curve,
205 dst_points_by_curve,
206 unselected_curves,
207 src_handle_types_right,
208 dst_handle_types_right);
209 }
210
211 Array<int> old_by_new_map(dst_curves.points_num());
212 unselected_curves.foreach_index(
213 [&](const int64_t curve_i) {
214 const IndexRange src_points = src_points_by_curve[curve_i];
215 const IndexRange dst_points = dst_points_by_curve[curve_i];
216 array_utils::fill_index_range<int>(old_by_new_map.as_mutable_span().slice(dst_points),
217 src_points.start());
218 },
220
221 /* Now copy the data of the newly fitted curves. */
222 curve_selection.foreach_index(
223 [&](const int64_t curve_i, const int64_t pos) {
224 const IndexRange src_points = src_points_by_curve[curve_i];
225 const IndexRange dst_points = dst_points_by_curve[curve_i];
226 MutableSpan<float3> positions = dst_positions.slice(dst_points);
227 MutableSpan<int> old_by_new = old_by_new_map.as_mutable_span().slice(dst_points);
228
229 if (dst_curve_types[curve_i] == CURVE_TYPE_POLY) {
230 /* Handle the curves for which the curve fitting has failed. */
231 BLI_assert(src_points.size() == dst_points.size());
232 positions.copy_from(src_positions.slice(src_points));
233 dst_handles_left.slice(dst_points).copy_from(src_positions.slice(src_points));
234 dst_handles_right.slice(dst_points).copy_from(src_positions.slice(src_points));
235 dst_handle_types_left.slice(dst_points).fill(BEZIER_HANDLE_FREE);
236 dst_handle_types_right.slice(dst_points).fill(BEZIER_HANDLE_FREE);
237 array_utils::fill_index_range<int>(old_by_new, src_points.start());
238 return;
239 }
240
241 const Span<float3> cubic_array = cubic_array_per_curve[pos];
242 BLI_assert(dst_points.size() * 3 == cubic_array.size());
243 MutableSpan<float3> left_handles = dst_handles_left.slice(dst_points);
244 MutableSpan<float3> right_handles = dst_handles_right.slice(dst_points);
245 threading::parallel_for(dst_points.index_range(), 8192, [&](const IndexRange range) {
246 for (const int i : range) {
247 const int index = i * 3;
248 positions[i] = cubic_array[index + 1];
249 left_handles[i] = cubic_array[index];
250 right_handles[i] = cubic_array[index + 2];
251 }
252 });
253
254 const Span<int> corner_indices = corner_indices_per_curve[pos];
255 dst_handle_types_left.slice(dst_points).fill(BEZIER_HANDLE_ALIGN);
256 dst_handle_types_right.slice(dst_points).fill(BEZIER_HANDLE_ALIGN);
257 dst_handle_types_left.slice(dst_points).fill_indices(corner_indices, BEZIER_HANDLE_FREE);
258 dst_handle_types_right.slice(dst_points).fill_indices(corner_indices, BEZIER_HANDLE_FREE);
259
260 const Span<int> original_indices = original_indices_per_curve[pos];
261 threading::parallel_for(dst_points.index_range(), 8192, [&](const IndexRange range) {
262 for (const int i : range) {
263 old_by_new[i] = src_points[original_indices[i]];
264 }
265 });
266 },
268
269 dst_curves.update_curve_types();
270
272 src_curves.attributes(),
276 attribute_filter,
277 {"position", "handle_left", "handle_right", "handle_type_left", "handle_type_right"}),
278 old_by_new_map,
279 dst_curves.attributes_for_write());
280
281 /* Free all the data from the C-API. */
282 for (MutableSpan<float3> cubic_array : cubic_array_per_curve) {
283 free(cubic_array.data());
284 }
285 for (MutableSpan<int> corner_indices : corner_indices_per_curve) {
286 free(corner_indices.data());
287 }
288 for (MutableSpan<int> original_indices : original_indices_per_curve) {
289 free(original_indices.data());
290 }
291
292 return dst_curves;
293}
294
295} // namespace geometry
296} // namespace blender
Low-level operations for curves.
support for deformation groups and hooks.
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
constexpr int64_t first() const
constexpr int64_t last(const int64_t n=0) const
constexpr int64_t size() const
static constexpr IndexRange from_begin_end(const int64_t begin, const int64_t end)
constexpr int64_t start() const
constexpr IndexRange index_range() const
constexpr MutableSpan()=default
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition BLI_span.hh:579
constexpr void fill(const T &value) const
Definition BLI_span.hh:523
constexpr void copy_from(Span< T > values) const
Definition BLI_span.hh:745
constexpr void fill_indices(Span< IndexT > indices, const T &value) const
Definition BLI_span.hh:532
Span< NewT > constexpr cast() const
Definition BLI_span.hh:422
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
int64_t size() const
void append(const T &value)
bool is_empty() const
MutableSpan< int8_t > handle_types_left_for_write()
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
Span< float3 > positions() const
MutableSpan< float3 > handle_positions_right_for_write()
std::optional< Span< float3 > > handle_positions_left() const
IndexRange curves_range() const
MutableSpan< int8_t > curve_types_for_write()
VArray< int8_t > handle_types_left() const
MutableSpan< float3 > handle_positions_left_for_write()
MutableSpan< int > offsets_for_write()
VArray< int8_t > handle_types_right() const
constexpr bool is_empty() const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
IndexMask complement(const IndexMask &universe, LinearAllocator<> &memory) const
#define FLT_MAX
void copy_group_to_group(OffsetIndices< int > src_offsets, OffsetIndices< int > dst_offsets, const IndexMask &selection, GSpan src, GMutableSpan dst)
void fill_index_range(MutableSpan< T > span, const T start=0)
bke::CurvesGeometry copy_only_curve_domain(const bke::CurvesGeometry &src_curves)
void free(Subdiv *subdiv)
Definition subdiv.cc:192
auto attribute_filter_with_skip_ref(const AttributeFilter &filter, const Span< StringRef > skip)
void gather_attributes(AttributeAccessor src_attributes, AttrDomain src_domain, AttrDomain dst_domain, const AttributeFilter &attribute_filter, const IndexMask &selection, MutableAttributeAccessor dst_attributes)
constexpr ParallelGrainSize grain_size(int grain_size)
bke::CurvesGeometry fit_poly_to_bezier_curves(const bke::CurvesGeometry &src_curves, const IndexMask &curve_selection, const VArray< float > &thresholds, const VArray< bool > &corners, FitMethod method, const bke::AttributeFilter &attribute_filter)
Definition fit_curves.cc:25
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
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90
unsigned int uint
Definition BKE_text.h:55
unsigned int uint32_t
Definition BKE_text.h:81
unsigned char uint8_t
Definition BKE_text.h:79
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