Blender V5.3
smooth_curves.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2024 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
13#include "BLI_array.hh"
14#include "BLI_generic_span.hh"
15#include "BLI_index_mask.hh"
16#include "BLI_index_range.hh"
17#include "BLI_vector.hh"
18#include "BLI_virtual_array.hh"
19
20#include "GEO_smooth_curves.hh"
21
22namespace blender::geometry {
23
24template<typename T>
25static void gaussian_blur_1D(const Span<T> src,
26 const int iterations,
27 const VArray<float> &influence_by_point,
28 const bool smooth_ends,
29 const bool keep_shape,
30 const bool is_cyclic,
32{
57
58 BLI_assert(!src.is_empty());
59 BLI_assert(src.size() == dst.size());
60
61 /* Avoid computation if there is just one point. */
62 if (src.size() == 1) {
63 return;
64 }
65
66 /* Weight Initialization. */
67 const int n_half = keep_shape ? (iterations * iterations) / 8 + iterations :
68 (iterations * iterations) / 4 + 2 * iterations + 12;
69 double w = keep_shape ? 2.0 : 1.0;
70 double w2 = keep_shape ?
71 (1.0 / M_SQRT3) * exp((2 * iterations * iterations) / double(n_half * 3)) :
72 0.0;
73 Array<double> total_weight(src.size(), 0.0);
74
75 const int64_t total_points = src.size();
76 const int64_t last_pt = total_points - 1;
77
78 auto is_end_and_fixed = [smooth_ends, is_cyclic, last_pt](int index) {
79 return !smooth_ends && !is_cyclic && ELEM(index, 0, last_pt);
80 };
81
82 /* Initialize at zero. */
83 threading::parallel_for(dst.index_range(), 1024, [&](const IndexRange range) {
84 for (const int64_t index : range) {
85 if (!is_end_and_fixed(index)) {
86 dst[index] = T(0);
87 }
88 }
89 });
90
91 /* Compute weights. */
92 for (const int64_t step : IndexRange(iterations)) {
93 const int64_t offset = iterations - step;
94 threading::parallel_for(dst.index_range(), 1024, [&](const IndexRange range) {
95 for (const int64_t index : range) {
96 /* Filter out endpoints. */
97 if (is_end_and_fixed(index)) {
98 continue;
99 }
100
101 double w_before = w - w2;
102 double w_after = w - w2;
103
104 /* Compute the neighboring points. */
105 int64_t before = index - offset;
106 int64_t after = index + offset;
107 if (is_cyclic) {
108 before = (before % total_points + total_points) % total_points;
109 after = after % total_points;
110 }
111 else {
112 if (!smooth_ends && (before < 0)) {
113 w_before *= -before / float(index);
114 }
115 before = math::max(before, int64_t(0));
116
117 if (!smooth_ends && (after > last_pt)) {
118 w_after *= (after - (total_points - 1)) / float(total_points - 1 - index);
119 }
120 after = math::min(after, last_pt);
121 }
122
123 /* Add the neighboring values. */
124 const T bval = src[before];
125 const T aval = src[after];
126 const T cval = src[index];
127
128 dst[index] += (bval - cval) * w_before;
129 dst[index] += (aval - cval) * w_after;
130
131 /* Update the weight values. */
132 total_weight[index] += w_before;
133 total_weight[index] += w_after;
134 }
135 });
136
137 w *= (n_half + offset) / double(n_half + 1 - offset);
138 w2 *= (n_half * 3 + offset) / double(n_half * 3 + 1 - offset);
139 }
140
141 /* Normalize the weights. */
142 devirtualize_varray(influence_by_point, [&](const auto influence_by_point) {
143 threading::parallel_for(dst.index_range(), 1024, [&](const IndexRange range) {
144 for (const int64_t index : range) {
145 if (!is_end_and_fixed(index)) {
146 total_weight[index] += w - w2;
147 dst[index] = src[index] + influence_by_point[index] * dst[index] / total_weight[index];
148 }
149 }
150 });
151 });
152}
153
154void gaussian_blur_1D(const GSpan src,
155 const int iterations,
156 const VArray<float> &influence_by_point,
157 const bool smooth_ends,
158 const bool keep_shape,
159 const bool is_cyclic,
160 GMutableSpan dst)
161{
162 bke::attribute_math::to_static_type(src.type(), [&]<typename T>() {
163 /* Only allow smoothing of float, float2, or float3. */
164 /* Reduces unnecessary code generation. */
165 if constexpr (is_same_any_v<T, float, float2, float3>) {
166 gaussian_blur_1D(src.typed<T>(),
167 iterations,
168 influence_by_point,
169 smooth_ends,
170 keep_shape,
171 is_cyclic,
172 dst.typed<T>());
173 }
174 });
175}
176
177void smooth_curve_attribute(const IndexMask &curves_to_smooth,
178 const OffsetIndices<int> points_by_curve,
179 const VArray<bool> &point_selection,
180 const VArray<bool> &cyclic,
181 const int iterations,
182 const VArray<float> &influence_by_point,
183 const bool smooth_ends,
184 const bool keep_shape,
185 GMutableSpan attribute_data)
186{
187 VArraySpan<float> influences(influence_by_point);
188
189 auto smooth_points_range =
190 [&](const IndexRange range, const bool cyclic, Vector<std::byte> &orig_data) {
191 GMutableSpan dst_data = attribute_data.slice(range);
192 orig_data.resize(dst_data.size_in_bytes());
193 dst_data.type().copy_assign_n(dst_data.data(), orig_data.data(), range.size());
194 const GSpan src_data(dst_data.type(), orig_data.data(), range.size());
195
196 gaussian_blur_1D(src_data,
197 iterations,
198 VArray<float>::from_span(influences.slice(range)),
199 smooth_ends,
200 keep_shape,
201 cyclic,
202 dst_data);
203 };
204
205 curves_to_smooth.foreach_index(
206 [&](const int curve_i) {
207 Vector<std::byte> orig_data;
208 const IndexRange points = points_by_curve[curve_i];
209
210 IndexMaskMemory memory;
211 const IndexMask selection_mask = IndexMask::from_bools(points, point_selection, memory);
212 if (selection_mask.is_empty()) {
213 return;
214 }
215
216 const std::optional<IndexRange> selection_range = selection_mask.to_range();
217 if (selection_range && *selection_range == points) {
218 smooth_points_range(points, cyclic[curve_i], orig_data);
219 }
220 else {
221 selection_mask.foreach_range([&](const IndexRange range) {
222 /* Individual ranges should be treated as non-cyclic. */
223 smooth_points_range(range, false, orig_data);
224 });
225 }
226 },
228}
229
230void smooth_curve_attribute(const IndexMask &curves_to_smooth,
231 const OffsetIndices<int> points_by_curve,
232 const VArray<bool> &point_selection,
233 const VArray<bool> &cyclic,
234 const int iterations,
235 const float influence,
236 const bool smooth_ends,
237 const bool keep_shape,
238 GMutableSpan attribute_data)
239{
240 smooth_curve_attribute(curves_to_smooth,
241 points_by_curve,
242 point_selection,
243 cyclic,
244 iterations,
245 VArray<float>::from_single(influence, points_by_curve.total_size()),
246 smooth_ends,
247 keep_shape,
248 attribute_data);
249}
250
252 const IndexMask &curves_to_smooth,
253 const VArray<bool> &point_selection,
254 const int iterations,
255 const VArray<float> &influence_by_point,
256 const bool smooth_ends,
257 const bool keep_shape)
258{
259 bke::MutableAttributeAccessor attributes = curves.attributes_for_write();
260 const OffsetIndices points_by_curve = curves.points_by_curve();
261 const VArray<bool> cyclic = curves.cyclic();
262 if (!curves.has_curve_with_type(CURVE_TYPE_BEZIER)) {
263 bke::GSpanAttributeWriter positions = attributes.lookup_for_write_span("position");
264 smooth_curve_attribute(curves_to_smooth,
265 points_by_curve,
266 point_selection,
267 cyclic,
268 iterations,
269 influence_by_point,
270 smooth_ends,
271 keep_shape,
272 positions.span);
273 positions.finish();
274 }
275 else {
276 IndexMaskMemory memory;
277 const IndexMask bezier_curves_to_smooth = curves.indices_for_curve_type(
278 CURVE_TYPE_BEZIER, curves_to_smooth, memory);
279
280 /* Write the positions of the handles and the control points into a flat array.
281 * This will smooth the handle positions together with the control point positions, because the
282 * smoothing algorithm takes neighboring values to apply the gaussian smoothing to. */
284 curves, bezier_curves_to_smooth);
285
286 VArraySpan<float> influences(influence_by_point);
287 bezier_curves_to_smooth.foreach_index(
288 [&](const int curve) {
289 Vector<float3> orig_data;
290 const IndexRange points = points_by_curve[curve];
291
292 IndexMaskMemory memory;
293 const IndexMask selection_mask = IndexMask::from_bools(points, point_selection, memory);
294 if (selection_mask.is_empty()) {
295 return;
296 }
297
298 selection_mask.foreach_range([&](const IndexRange range) {
299 IndexRange positions_range(range.start() * 3, range.size() * 3);
300 /* Ignore the left handle of the first point and the right handle of the last point. */
301 if (!smooth_ends && !cyclic[curve]) {
302 positions_range = positions_range.drop_front(1).drop_back(1);
303 }
304 MutableSpan<float3> dst_data = all_positions.as_mutable_span().slice(positions_range);
305
306 orig_data.resize(dst_data.size());
307 orig_data.as_mutable_span().copy_from(dst_data);
308
309 /* The influence is mapped from handle+control point index to only control point index.
310 */
311 Array<float> point_influences(positions_range.size());
312 if (!smooth_ends && !cyclic[curve]) {
314 positions_range.index_range(), 4096, [&](const IndexRange influences_range) {
315 for (const int index : influences_range) {
316 /* Account for the left handle of the first
317 * point being ignored. */
318 point_influences[index] = influences.slice(range)[(index + 1) / 3];
319 }
320 });
321 }
322 else {
324 positions_range.index_range(), 4096, [&](const IndexRange influences_range) {
325 for (const int index : influences_range) {
326 point_influences[index] = influences.slice(range)[index / 3];
327 }
328 });
329 }
330
331 gaussian_blur_1D(orig_data.as_span(),
332 iterations,
333 VArray<float>::from_span(point_influences.as_span()),
334 smooth_ends,
335 keep_shape,
336 cyclic[curve],
337 dst_data);
338 });
339 },
341
342 /* Copy the resulting values from the flat array back into the three position attributes for
343 * the left and right handles as well as the control points. */
344 bke::curves::bezier::write_all_positions(curves, bezier_curves_to_smooth, all_positions);
345
346 /* Smooth the other curve positions. */
347 const IndexMask other_curves_to_smooth = bezier_curves_to_smooth.complement(
348 curves.curves_range(), memory);
349 if (!other_curves_to_smooth.is_empty()) {
350 bke::GSpanAttributeWriter positions = attributes.lookup_for_write_span("position");
351 smooth_curve_attribute(other_curves_to_smooth,
352 points_by_curve,
353 point_selection,
354 cyclic,
355 iterations,
356 influence_by_point,
357 smooth_ends,
358 keep_shape,
359 positions.span);
360 positions.finish();
361 }
362
363 curves.calculate_bezier_auto_handles();
364 curves.calculate_bezier_aligned_handles();
365 }
366
367 curves.tag_positions_changed();
368}
369
371 const IndexMask &curves_to_smooth,
372 const VArray<bool> &point_selection,
373 const int iterations,
374 const float influence,
375 const bool smooth_ends,
376 const bool keep_shape)
377{
379 curves_to_smooth,
380 point_selection,
381 iterations,
382 VArray<float>::from_single(influence, curves.points_num()),
383 smooth_ends,
384 keep_shape);
385}
386
387} // namespace blender::geometry
Low-level operations for curves.
Low-level operations for curves.
#define M_SQRT3
#define ELEM(...)
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition btQuadWord.h:119
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
void copy_assign_n(const void *src, void *dst, int64_t n) const
int64_t size_in_bytes() const
GMutableSpan slice(const int64_t start, int64_t size) const
const CPPType & type() const
const CPPType & type() const
static IndexMask from_bools(Span< bool > bools, LinearAllocator<> &memory)
constexpr IndexRange drop_back(int64_t n) const
constexpr int64_t size() const
constexpr IndexRange()=default
constexpr int64_t start() const
constexpr IndexRange index_range() const
constexpr IndexRange drop_front(int64_t n) const
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr bool is_empty() const
Definition BLI_span.hh:264
static VArray from_single(T value, const int64_t size)
static VArray from_span(Span< T > values)
void resize(const int64_t new_size)
MutableSpan< T > as_mutable_span()
GSpanAttributeWriter lookup_for_write_span(StringRef name)
constexpr Span slice(int64_t start, int64_t size) const
void foreach_range(ForeachRangeFn auto &&fn) const
std::optional< IndexRange > to_range() const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
IndexMask complement(const IndexMask &universe, LinearAllocator<> &memory) const
#define exp
VecBase< float, D > step(VecOp< float, D >, VecOp< float, D >) RET
#define T
void to_static_type(const CPPType &cpp_type, Fn &&fn)
Array< float3 > retrieve_all_positions(const bke::CurvesGeometry &curves, const IndexMask &curves_selection)
void write_all_positions(bke::CurvesGeometry &curves, const IndexMask &curves_selection, Span< float3 > all_positions)
constexpr ParallelGrainSize grain_size(int grain_size)
void smooth_curve_positions(bke::CurvesGeometry &curves, const IndexMask &curves_to_smooth, const VArray< bool > &point_selection, int iterations, const VArray< float > &influence_by_point, bool smooth_ends, bool keep_shape)
void smooth_curve_attribute(const IndexMask &curves_to_smooth, const OffsetIndices< int > points_by_curve, const VArray< bool > &point_selection, const VArray< bool > &cyclic, int iterations, float influence, bool smooth_ends, bool keep_shape, GMutableSpan attribute_data)
void gaussian_blur_1D(const GSpan src, int iterations, const VArray< float > &influence_by_point, const bool smooth_ends, const bool keep_shape, const bool is_cyclic, GMutableSpan dst)
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
void devirtualize_varray(const VArray< T > &varray, const Func &func, bool enable=true)