Blender V5.3
bmo_relax_edge_loops.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
10
11#include "BLI_math_vector.hh"
12#include "BLI_math_vector_c.hh"
13
14#include "BLI_array_utils.hh"
16#include "BLI_listbase.hh"
17#include "BLI_math_solvers.hh"
18#include "BLI_vector.hh"
19#include <array>
20
21#include "bmesh.hh"
22#include "intern/bmesh_operators_private.hh" /* own include */
23
24namespace blender {
25
36
48
52struct SplineCoeffs {
54 float a;
56 float b;
58 float c;
60 float d;
62 float x;
63};
64
66constexpr float RELAX_EPSILON = 1e-8f;
67
73static void calculate_splines_axis(Span<float> distances,
74 Span<float> coords,
75 const bool is_closed,
76 Vector<SplineCoeffs> &r_coeffs)
77{
78 const int verts_num = coords.size();
79 if (verts_num < 2) {
80 return;
81 }
82 const int segments_num = is_closed ? verts_num : verts_num - 1;
83 Array<float> segment_length(segments_num);
84
85 for (const int i : IndexRange(segments_num)) {
86 segment_length[i] = distances[i + 1] - distances[i];
87 if (!(segment_length[i] > 0.0f)) {
88 segment_length[i] = RELAX_EPSILON;
89 }
90 }
91
92 /* Stores second derivative coefficients. For a natural cubic spline, the boundary
93 * condition defines the first and last points as zero. */
94 Array<float> c_vals(verts_num, 0.0f);
95
96 /* The Thomas algorithm used in `BLI_tridiagonal_solve` can't properly solve
97 * a cyclic tridiagonal system so in this case, we use the Sherman-Morrison formula
98 * via `BLI_tridiagonal_solve_cyclic`. */
99 if (is_closed) {
100 Array<float> lower_diag(verts_num);
101 Array<float> diag(verts_num);
102 Array<float> upper_diag(verts_num);
103 Array<float> rhs(verts_num);
104 for (const int i : IndexRange(verts_num)) {
105 const int i_prev = math::mod_periodic(i - 1, verts_num);
106 const int i_next = math::mod_periodic(i + 1, verts_num);
107 lower_diag[i] = segment_length[i_prev];
108 diag[i] = 2.0f * (segment_length[i_prev] + segment_length[i]);
109 upper_diag[i] = segment_length[i];
110 rhs[i] = 3.0f * (((coords[i_next] - coords[i]) / segment_length[i]) -
111 ((coords[i] - coords[i_prev]) / segment_length[i_prev]));
112 }
114 lower_diag.data(), diag.data(), upper_diag.data(), rhs.data(), c_vals.data(), verts_num);
115 }
116 else {
117 /* For a natural cubic spline the curvature at the first and last point
118 * is 0, so for n given points, we only have n-2 unknown interior points. */
119 const int interior = verts_num - 2;
120 Array<float> lower_diag(interior);
121 Array<float> diag(interior);
122 Array<float> upper_diag(interior);
123 Array<float> rhs(interior);
124
125 for (const int i_curr : IndexRange(interior)) {
126 const int i_next = i_curr + 1;
127 lower_diag[i_curr] = segment_length[i_curr];
128 diag[i_curr] = 2.0f * (segment_length[i_curr] + segment_length[i_next]);
129 upper_diag[i_curr] = segment_length[i_next];
130 rhs[i_curr] = 3.0f * (((coords[i_next + 1] - coords[i_next]) / segment_length[i_next]) -
131 ((coords[i_next] - coords[i_curr]) / segment_length[i_curr]));
132 }
133 BLI_tridiagonal_solve(lower_diag.data(),
134 diag.data(),
135 upper_diag.data(),
136 rhs.data(),
137 c_vals.data() + 1,
138 interior);
139 }
140
141 /* Build polynomial coefficients for each segment. */
142 for (const int i : IndexRange(segments_num)) {
143 const int i_next = is_closed ? math::mod_periodic(i + 1, verts_num) : i + 1;
144
145 const float coeff_a = coords[i];
146 const float coeff_b = ((coords[i_next] - coords[i]) / segment_length[i]) -
147 (segment_length[i] * (c_vals[i_next] + 2.0f * c_vals[i])) / 3.0f;
148 const float coeff_c = c_vals[i];
149 const float coeff_d = (c_vals[i_next] - c_vals[i]) / (3.0f * segment_length[i]);
150 r_coeffs.append({coeff_a, coeff_b, coeff_c, coeff_d, distances[i]});
151 }
152}
153
154static void build_relax_phases(int verts_num, bool is_closed, Vector<RelaxPhase> &r_phases)
155{
156 if (!is_closed) {
157 /* There are two relax phases, in the first phase, odd vertices are relaxed
158 * and even ones are not(they're knots in this case), in second phase, even vertices
159 * are relaxed and odd ones are not. The first and last vertices are not included to
160 * be moved. */
161 for (const int phase_index : IndexRange(2)) {
162 RelaxPhase phase;
163 for (const int i : IndexRange(verts_num)) {
164 if (i % 2 == phase_index) {
165 phase.knot_indices.append(i);
166 }
167 else if (i > 0 && i < verts_num - 1) {
168 phase.point_indices.append(i);
169 }
170 }
171 r_phases.append(std::move(phase));
172 }
173 return;
174 }
175
176 Vector<int> vert_indices(verts_num);
178
179 for (const int j : IndexRange(2)) {
180 const bool extend = verts_num % 2 == 1 ? j == 1 : j == 0;
181 const int knot_start = !extend && j == 1 ? 1 : 0;
182 const int point_start = !extend && j == 1 ? 2 : 1;
183
184 if (extend) {
185 const int last_vert = vert_indices.last();
186 const int first_vert = vert_indices.first();
187 vert_indices.insert(0, last_vert);
188 vert_indices.append(first_vert);
189 }
190
191 RelaxPhase phase;
192 for (int i = knot_start; i < vert_indices.size(); i += 2) {
193 phase.knot_indices.append(vert_indices[i]);
194 }
195 for (int i = point_start; i < vert_indices.size(); i += 2) {
196 const int val = vert_indices[i];
197 if (phase.point_indices.is_empty() || val != phase.point_indices.first()) {
198 phase.point_indices.append(val);
199 }
200 }
201 if (phase.knot_indices.first() != phase.knot_indices.last()) {
202 const int first_knot = phase.knot_indices.first();
203 phase.knot_indices.append(first_knot);
204 }
205
206 if (!phase.point_indices.is_empty()) {
207 r_phases.append(std::move(phase));
208 }
209 }
210}
211
213{
214 ListBaseT<BMEdgeLoopStore> eloops = {nullptr};
215 const BMEdgeLoopFind_Params params = {
216 .use_vert_junction = true,
217 };
219 bm, &eloops, [](BMEdge *e) { return BM_elem_flag_test(e, BM_ELEM_TAG); }, &params);
220
221 for (BMEdgeLoopStore &el_store : eloops) {
222 RelaxChainData chain;
223 chain.is_closed = BM_edgeloop_is_closed(&el_store);
224 for (LinkData &node : *BM_edgeloop_verts_get(&el_store)) {
225 chain.verts.append(static_cast<BMVert *>(node.data));
226 }
227 if (chain.verts.size() >= 3) {
228 r_chains.append(std::move(chain));
229 }
230 }
231
232 BM_mesh_edgeloops_free(&eloops);
233}
234
236 const RelaxPhase &phase,
237 const bool regular,
238 Vector<float> &r_knot_distances,
239 Vector<float> &r_point_distances)
240{
241 const int knots_num = phase.knot_indices.size();
242 const int points_num = phase.point_indices.size();
243 const int total = knots_num + points_num;
244
245 Array<float3> positions(total);
246 for (const int i : IndexRange(total)) {
247 int vert_index;
248 if (i % 2 == 0) {
249 vert_index = phase.knot_indices[i / 2];
250 }
251 else if (i == total - 1) {
252 vert_index = phase.knot_indices.last();
253 }
254 else {
255 vert_index = phase.point_indices[i / 2];
256 }
257 positions[i] = verts[vert_index]->co;
258 }
259
260 Array<float> cumulative(total);
261 cumulative[0] = 0.0f;
263 positions, false, cumulative.as_mutable_span().drop_front(1));
264
265 for (const int i : IndexRange(total)) {
266 if (i % 2 == 0 || i == total - 1) {
267 r_knot_distances.append(cumulative[i]);
268 }
269 else {
270 r_point_distances.append(cumulative[i]);
271 }
272 }
273
274 /* Place a point halfway between two knots if regular is enabled. */
275 if (regular) {
276 r_point_distances.clear();
277 for (const int p : IndexRange(points_num)) {
278 r_point_distances.append((r_knot_distances[p] + r_knot_distances[p + 1]) / 2.0f);
279 }
280 }
281}
282
284 Span<int> knot_indices,
285 Span<float> t_params,
286 bool is_closed,
287 std::array<Vector<SplineCoeffs>, 3> &r_coeffs)
288{
289 const int knots_num = knot_indices.size();
290 const int coords_num = is_closed ? knots_num - 1 : knots_num;
291 Array<float> coords_x(coords_num);
292 Array<float> coords_y(coords_num);
293 Array<float> coords_z(coords_num);
294
295 for (const int i : IndexRange(coords_num)) {
296 const float *co = verts[knot_indices[i]]->co;
297 coords_x[i] = co[0];
298 coords_y[i] = co[1];
299 coords_z[i] = co[2];
300 }
301
302 calculate_splines_axis(t_params, coords_x, is_closed, r_coeffs[0]);
303 calculate_splines_axis(t_params, coords_y, is_closed, r_coeffs[1]);
304 calculate_splines_axis(t_params, coords_z, is_closed, r_coeffs[2]);
305}
306
308 Span<BMVert *> verts, const RelaxPhase &phase, bool is_closed, int interpolation, bool regular)
309{
310 if (phase.point_indices.is_empty()) {
311 return;
312 }
313
314 Vector<float> knot_distances;
315 Vector<float> point_distances;
316 calculate_phase_distances(verts, phase, regular, knot_distances, point_distances);
317
318 const Span<float> accumulated_lengths = Span<float>(knot_distances).drop_front(1);
319
320 const int points_num = phase.point_indices.size();
321 Array<int> segment_indices(points_num);
322 Array<float> factors(points_num);
324 accumulated_lengths, point_distances, segment_indices, factors);
325
326 Array<float3> sampled_positions(points_num);
327
328 if (interpolation == RELAX_EDGE_LOOPS_INTERP_LINEAR) {
329 Array<float3> knot_positions(phase.knot_indices.size());
330 for (const int i : phase.knot_indices.index_range()) {
331 knot_positions[i] = verts[phase.knot_indices[i]]->co;
332 }
333
335 knot_positions, segment_indices, factors, sampled_positions);
336 }
337 else {
338 std::array<Vector<SplineCoeffs>, 3> axis_coeffs;
339 calculate_relax_splines(verts, phase.knot_indices, knot_distances, is_closed, axis_coeffs);
340
341 for (const int i : IndexRange(points_num)) {
342 const int seg = segment_indices[i];
343 const float dt = point_distances[i] - axis_coeffs[0][seg].x;
344
345 const SplineCoeffs &cx = axis_coeffs[0][seg];
346 const SplineCoeffs &cy = axis_coeffs[1][seg];
347 const SplineCoeffs &cz = axis_coeffs[2][seg];
348
349 sampled_positions[i] = float3(cx.a + dt * (cx.b + dt * (cx.c + dt * cx.d)),
350 cy.a + dt * (cy.b + dt * (cy.c + dt * cy.d)),
351 cz.a + dt * (cz.b + dt * (cz.c + dt * cz.d)));
352 }
353 }
354
355 for (const int i : IndexRange(points_num)) {
356 const int v_index = phase.point_indices[i];
357 const float3 current_pos(verts[v_index]->co);
358 const float3 final_pos = (current_pos + sampled_positions[i]) / 2.0f;
359 copy_v3_v3(verts[v_index]->co, final_pos);
360 }
361}
362
364{
365 const int iterations = BMO_slot_int_get(op->slots_in, "iterations");
366 const int interpolation = BMO_slot_int_get(op->slots_in, "interpolation");
367 const bool even_spacing = BMO_slot_bool_get(op->slots_in, "even_spacing");
368
371
373 get_relax_input_chains(bm, chains);
374
375 for (RelaxChainData &chain : chains) {
376 build_relax_phases(chain.verts.size(), chain.is_closed, chain.phases);
377 }
378
379 for (const int it : IndexRange(iterations)) {
380 UNUSED_VARS(it);
381
382 for (RelaxChainData &chain : chains) {
383 for (const RelaxPhase &phase : chain.phases) {
384 execute_relax_phase(chain.verts, phase, chain.is_closed, interpolation, even_spacing);
385 }
386 }
387 }
388}
389
390} // namespace blender
#define UNUSED_VARS(...)
#define BM_elem_flag_test(ele, hflag)
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
const T * data() const
Definition BLI_array.hh:323
constexpr IndexRange()=default
constexpr Span drop_front(int64_t n) const
Definition BLI_span.hh:175
constexpr int64_t size() const
Definition BLI_span.hh:256
int64_t size() const
void append(const T &value)
void insert(const int64_t insert_index, const T &value)
const T & last(const int64_t n=0) const
MutableSpan< T > as_mutable_span()
const T & first() const
void append(const T &value)
const T & last(const int64_t n=0) const
IndexRange index_range() const
const T & first() const
int64_t size() const
void fill_index_range(MutableSpan< T > span, const T start=0)
void accumulate_lengths(const Span< T > values, const bool cyclic, MutableSpan< float > lengths)
void sample_at_lengths(Span< float > accumulated_segment_lengths, Span< float > sample_lengths, MutableSpan< int > r_segment_indices, MutableSpan< float > r_factors)
void interpolate(const Span< T > src, const Span< int > indices, const Span< float > factors, MutableSpan< T > dst)
T mod_periodic(const T &a, const T &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)
static void get_relax_input_chains(BMesh *bm, Vector< RelaxChainData > &r_chains)
int BMO_slot_int_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
static void calculate_phase_distances(Span< BMVert * > verts, const RelaxPhase &phase, const bool regular, Vector< float > &r_knot_distances, Vector< float > &r_point_distances)
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:
void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
@ RELAX_EDGE_LOOPS_INTERP_LINEAR
bool BM_edgeloop_is_closed(BMEdgeLoopStore *el_store)
void bmo_relax_edge_loops_exec(BMesh *bm, BMOperator *op)
constexpr float RELAX_EPSILON
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)
static void build_relax_phases(int verts_num, bool is_closed, Vector< RelaxPhase > &r_phases)
VecBase< float, 3 > float3
static void execute_relax_phase(Span< BMVert * > verts, const RelaxPhase &phase, bool is_closed, int interpolation, bool regular)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
static void calculate_relax_splines(Span< BMVert * > verts, Span< int > knot_indices, Span< float > t_params, bool is_closed, std::array< Vector< SplineCoeffs >, 3 > &r_coeffs)
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
Vector< RelaxPhase > phases