Blender V5.3
bmo_space_edge_loops_evenly.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
16#include "BLI_math_vector.hh"
17
18#include "BLI_binary_search.hh"
20#include "BLI_listbase.hh"
21#include "BLI_math_geom_c.hh"
22#include "BLI_math_solvers.hh"
23#include "BLI_span.hh"
24#include "BLI_vector.hh"
25
26#include "bmesh.hh"
27#include "intern/bmesh_operators_private.hh" /* own include */
28
29namespace blender {
30
32constexpr float DUPLICATE_POSITION_THRESHOLD = 1e-6f;
34constexpr float SPACE_EPSILON = 1e-8f;
35
45
59
63struct SplineCoeffs {
65 float a;
67 float b;
69 float c;
71 float d;
73 float x;
74};
75
80{
81 ListBaseT<BMEdgeLoopStore> eloops = {nullptr};
82 const BMEdgeLoopFind_Params params = {
83 .use_vert_junction = true,
84 };
86 bm, &eloops, [](BMEdge *e) { return BM_elem_flag_test(e, BM_ELEM_TAG); }, &params);
87
88 for (BMEdgeLoopStore &el_store : eloops) {
89 SpaceChainData chain;
90 chain.is_closed = BM_edgeloop_is_closed(&el_store);
91 for (LinkData &node : *BM_edgeloop_verts_get(&el_store)) {
92 chain.verts.append(static_cast<BMVert *>(node.data));
93 }
94
95 /* Skip chains where all vertices are at the same location. */
96 bool all_duplicate = true;
97 for (const int i : chain.verts.index_range().drop_back(1)) {
98 if (math::distance_squared(float3(chain.verts[i]->co), float3(chain.verts[i + 1]->co)) >
100 {
101 all_duplicate = false;
102 break;
103 }
104 }
105
106 if (!all_duplicate) {
107 r_chains.append(std::move(chain));
108 }
109 }
110
111 BM_mesh_edgeloops_free(&eloops);
112}
113
118{
119 SpaceMeasurements measure;
120 const int verts_num = chain.verts.size();
121
122 measure.positions.reinitialize(verts_num);
123 for (const int i : IndexRange(verts_num)) {
124 measure.positions[i] = float3(chain.verts[i]->co);
125 }
126 measure.knot_distances.reinitialize(verts_num + (chain.is_closed ? 1 : 0));
127 measure.knot_distances[0] = 0.0f;
129 measure.positions, chain.is_closed, measure.knot_distances.as_mutable_span().drop_front(1));
130
131 return measure;
132}
133
138 Span<float> coords,
139 const bool is_closed,
140 Vector<SplineCoeffs> &r_coeffs)
141{
142 const int verts_num = coords.size();
143 if (verts_num < 2) {
144 return;
145 }
146 const int num_segments = is_closed ? verts_num : verts_num - 1;
147 Array<float> segment_length(num_segments);
148
149 for (const int i : IndexRange(num_segments)) {
150 segment_length[i] = distances[i + 1] - distances[i];
151 if (!(segment_length[i] > 0.0f)) {
152 segment_length[i] = SPACE_EPSILON;
153 }
154 }
155
156 /* Stores second derivative coefficients. For a natural cubic spline, the boundary
157 * condition defines the first and last points as zero. */
158 Array<float> c_vals(verts_num, 0.0f);
159
160 /* The Thomas algorithm used in `BLI_tridiagonal_solve` can't properly solve
161 * a cyclic tridiagonal system so in this case, we use the Sherman-Morrison formula
162 * via `BLI_tridiagonal_solve_cyclic`. */
163 if (is_closed) {
164 Array<float> lower_diag(verts_num);
165 Array<float> diag(verts_num);
166 Array<float> upper_diag(verts_num);
167 Array<float> rhs(verts_num);
168 for (const int i : IndexRange(verts_num)) {
169 const int i_prev = math::mod_periodic(i - 1, verts_num);
170 const int i_next = math::mod_periodic(i + 1, verts_num);
171 lower_diag[i] = segment_length[i_prev];
172 diag[i] = 2.0f * (segment_length[i_prev] + segment_length[i]);
173 upper_diag[i] = segment_length[i];
174 rhs[i] = 3.0f * (((coords[i_next] - coords[i]) / segment_length[i]) -
175 ((coords[i] - coords[i_prev]) / segment_length[i_prev]));
176 }
178 lower_diag.data(), diag.data(), upper_diag.data(), rhs.data(), c_vals.data(), verts_num);
179 }
180 else {
181 /* For a natural cubic spline the curvature at the first and last point
182 * is 0, so for n given points, we only have n-2 unknown interior points. */
183 const int interior = verts_num - 2;
184 Array<float> lower_diag(interior);
185 Array<float> diag(interior);
186 Array<float> upper_diag(interior);
187 Array<float> rhs(interior);
188
189 for (const int i_curr : IndexRange(interior)) {
190 const int i_next = i_curr + 1;
191 lower_diag[i_curr] = segment_length[i_curr];
192 diag[i_curr] = 2.0f * (segment_length[i_curr] + segment_length[i_next]);
193 upper_diag[i_curr] = segment_length[i_next];
194 rhs[i_curr] = 3.0f * (((coords[i_next + 1] - coords[i_next]) / segment_length[i_next]) -
195 ((coords[i_next] - coords[i_curr]) / segment_length[i_curr]));
196 }
197 BLI_tridiagonal_solve(lower_diag.data(),
198 diag.data(),
199 upper_diag.data(),
200 rhs.data(),
201 c_vals.data() + 1,
202 interior);
203 }
204
205 /* Build polynomial coefficients for each segment. */
206 for (const int i : IndexRange(num_segments)) {
207 const int i_next = is_closed ? math::mod_periodic(i + 1, verts_num) : i + 1;
208
209 const float coeff_a = coords[i];
210 const float coeff_b = ((coords[i_next] - coords[i]) / segment_length[i]) -
211 (segment_length[i] * (c_vals[i_next] + 2.0f * c_vals[i])) / 3.0f;
212 const float coeff_c = c_vals[i];
213 const float coeff_d = (c_vals[i_next] - c_vals[i]) / (3.0f * segment_length[i]);
214 r_coeffs.append({coeff_a, coeff_b, coeff_c, coeff_d, distances[i]});
215 }
216}
217
219static int calc_spline_segment(Span<float> knot_distances, const float target_distance)
220{
221 const int segment_index = binary_search::last_if(
222 knot_distances, [&](const float value) { return value <= target_distance; });
223 return std::clamp(segment_index, 0, int(knot_distances.size()) - 2);
224}
225
228 Span<SplineCoeffs> coeffs_x,
229 Span<SplineCoeffs> coeffs_y,
230 Span<SplineCoeffs> coeffs_z,
231 const float target_distance)
232{
233 const int segment = calc_spline_segment(tknots, target_distance);
234 const float dt = target_distance - coeffs_x[segment].x;
235
236 const SplineCoeffs &cx = coeffs_x[segment];
237 const SplineCoeffs &cy = coeffs_y[segment];
238 const SplineCoeffs &cz = coeffs_z[segment];
239
240 return float3(cx.a + dt * (cx.b + dt * (cx.c + dt * cx.d)),
241 cy.a + dt * (cy.b + dt * (cy.c + dt * cy.d)),
242 cz.a + dt * (cz.b + dt * (cz.c + dt * cz.d)));
243}
244
246{
247 const float factor = BMO_slot_float_get(op->slots_in, "factor");
248 const SpaceInterpolationMethod interpolation = static_cast<SpaceInterpolationMethod>(
249 BMO_slot_int_get(op->slots_in, "interpolation"));
250 const bool lock_x = BMO_slot_bool_get(op->slots_in, "lock_x");
251 const bool lock_y = BMO_slot_bool_get(op->slots_in, "lock_y");
252 const bool lock_z = BMO_slot_bool_get(op->slots_in, "lock_z");
253
256
258 get_space_input_chains(bm, chains);
259
260 for (SpaceChainData &chain : chains) {
261 const int verts_num = chain.verts.size();
262 SpaceMeasurements measure = measure_chain(chain);
263
264 Array<int> sample_indices(verts_num);
265 Array<float> sample_factors(verts_num);
267 !chain.is_closed,
268 sample_indices,
269 sample_factors);
270
271 Array<float3> new_positions(verts_num);
272
273 if (interpolation == SPACE_EDGE_LOOPS_EVENLY_INTERP_LINEAR) {
275 measure.positions, sample_indices, sample_factors, new_positions);
276 }
277 else {
278 Array<float> coords_x(verts_num);
279 Array<float> coords_y(verts_num);
280 Array<float> coords_z(verts_num);
281 for (const int i : IndexRange(verts_num)) {
282 coords_x[i] = measure.positions[i].x;
283 coords_y[i] = measure.positions[i].y;
284 coords_z[i] = measure.positions[i].z;
285 }
286
287 Vector<SplineCoeffs> coeffs_x;
288 Vector<SplineCoeffs> coeffs_y;
289 Vector<SplineCoeffs> coeffs_z;
290 calculate_splines_axis(measure.knot_distances, coords_x, chain.is_closed, coeffs_x);
291 calculate_splines_axis(measure.knot_distances, coords_y, chain.is_closed, coeffs_y);
292 calculate_splines_axis(measure.knot_distances, coords_z, chain.is_closed, coeffs_z);
293
294 for (const int i : IndexRange(verts_num)) {
295 const int seg = sample_indices[i];
296 const float target_dist = math::interpolate(
297 measure.knot_distances[seg], measure.knot_distances[seg + 1], sample_factors[i]);
298
299 new_positions[i] = evaluate_cubic(
300 measure.knot_distances, coeffs_x, coeffs_y, coeffs_z, target_dist);
301 }
302 }
303
304 for (const int i : IndexRange(verts_num)) {
305 /* The first and last vertices of an open chain are anchor points so they are skipped. */
306 if (!chain.is_closed && ELEM(i, 0, verts_num - 1)) {
307 continue;
308 }
309
310 float3 new_pos = new_positions[i];
311
312 if (lock_x) {
313 new_pos.x = measure.positions[i].x;
314 }
315 if (lock_y) {
316 new_pos.y = measure.positions[i].y;
317 }
318 if (lock_z) {
319 new_pos.z = measure.positions[i].z;
320 }
321
322 float3 final_pos = math::interpolate(measure.positions[i], new_pos, factor);
323 copy_v3_v3(chain.verts[i]->co, final_pos);
324 }
325 }
326}
327
328} // namespace blender
#define ELEM(...)
#define BM_elem_flag_test(ele, hflag)
Span< T > as_span() const
Definition BLI_array.hh:254
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
const T * data() const
Definition BLI_array.hh:323
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
constexpr IndexRange()=default
constexpr int64_t size() const
Definition BLI_span.hh:256
void append(const T &value)
constexpr MutableSpan drop_front(const int64_t n) const
constexpr Span drop_front(int64_t n) const
int64_t last_if(const Range &range, Predicate &&predicate)
void accumulate_lengths(const Span< T > values, const bool cyclic, MutableSpan< float > lengths)
void interpolate(const Span< T > src, const Span< int > indices, const Span< float > factors, MutableSpan< T > dst)
void sample_uniform(Span< float > accumulated_segment_lengths, bool include_last_point, MutableSpan< int > r_segment_indices, MutableSpan< float > r_factors)
T interpolate(const T &a, const T &b, const FactorT &t)
T square(const T &a)
T mod_periodic(const T &a, const T &b)
T distance_squared(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
BMesh Iterators.
bool BLI_tridiagonal_solve_cyclic(const float *a, const float *b, const float *c, const float *d, float *r_x, int count)
Solve a possibly cyclic tridiagonal system using the Sherman-Morrison formula.
ListBaseT< LinkData > * BM_edgeloop_verts_get(BMEdgeLoopStore *el_store)
int BM_mesh_edgeloops_find(BMesh *bm, ListBaseT< BMEdgeLoopStore > *r_eloops, FunctionRef< bool(BMEdge *)> test_fn, const BMEdgeLoopFind_Params *params)
int BMO_slot_int_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
static SpaceMeasurements measure_chain(const SpaceChainData &chain)
MINLINE void copy_v3_v3(float r[3], const float a[3])
void BMO_slot_buffer_hflag_enable(BMesh *bm, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, char hflag, bool do_flush)
BMO_FLAG_BUFFER.
void BM_mesh_edgeloops_free(ListBaseT< BMEdgeLoopStore > *eloops)
bool BLI_tridiagonal_solve(const float *a, const float *b, const float *c, const float *d, float *r_x, int count)
Solve a tridiagonal system of equations:
float BMO_slot_float_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
static int calc_spline_segment(Span< float > knot_distances, const float target_distance)
constexpr float SPACE_EPSILON
void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
@ SPACE_EDGE_LOOPS_EVENLY_INTERP_LINEAR
bool BM_edgeloop_is_closed(BMEdgeLoopStore *el_store)
static void get_space_input_chains(BMesh *bm, Vector< SpaceChainData > &r_chains)
static void calculate_splines_axis(const Span< float > distances, const Span< float > coords, const bool is_closed, Array< SplineCoeffs > &r_coeffs)
bool BMO_slot_bool_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
void bmo_space_edge_loops_evenly_exec(BMesh *bm, BMOperator *op)
static float3 evaluate_cubic(Span< float > tknots, Span< SplineCoeffs > coeffs_x, Span< SplineCoeffs > coeffs_y, Span< SplineCoeffs > coeffs_z, const float target_distance)
VecBase< float, 3 > float3
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
constexpr float DUPLICATE_POSITION_THRESHOLD
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]