Blender V5.3
bmo_fit_edge_loops_to_annotation.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_listbase.hh"
12#include "BLI_math_geom.hh"
13#include "BLI_math_vector.hh"
14
16
17#include "bmesh.hh"
18#include "intern/bmesh_operators_private.hh" /* own include */
19
20namespace blender {
21
22constexpr float ray_length = 1000.0f;
23constexpr float max_ray_distance = 0.01f;
24constexpr float segment_epsilon = 1e-4f;
25constexpr float normal_length_epsilon = 1e-3f;
26
35
46
48{
49 ListBaseT<BMEdgeLoopStore> eloops = {nullptr};
50 const BMEdgeLoopFind_Params params = {
51 .use_vert_junction = true,
52 };
54 bm, &eloops, [](BMEdge *e) { return BM_elem_flag_test(e, BM_ELEM_TAG); }, &params);
55
56 for (BMEdgeLoopStore &el_store : eloops) {
58 for (LinkData &node : *BM_edgeloop_verts_get(&el_store)) {
59 chain.verts.append(static_cast<BMVert *>(node.data));
60 }
61
62 r_chains.append(std::move(chain));
63 }
64
66}
67
68static void measure_positions(const Span<float3> positions,
69 float3 &r_center,
70 Vector<float> &r_accumulated_lengths)
71{
72 const int points_num = positions.size();
73
74 r_center = float3(0.0f);
75 for (const int i : IndexRange(points_num)) {
76 r_center += positions[i];
77 }
78 r_center /= float(points_num);
79
80 r_accumulated_lengths.resize(points_num - 1);
82 positions, false, r_accumulated_lengths.as_mutable_span());
83}
84
85static bool is_total_length_valid(const Span<float> accumulated_lengths)
86{
87 return accumulated_lengths.last() > 0.0f;
88}
89
91{
92 const int verts_num = chain.verts.size();
93
94 Array<float3> positions(verts_num);
95 for (const int i : IndexRange(verts_num)) {
96 positions[i] = float3(chain.verts[i]->co);
97 }
98
99 measure_positions(positions, chain.center, chain.accumulated_lengths);
100}
101
102static void calculate_stroke_lengths(StrokeData &stroke_data)
103{
104 measure_positions(stroke_data.points, stroke_data.center, stroke_data.accumulated_lengths);
105}
106
107static void sample_stroke_positions(const StrokeData &stroke_data,
108 const ToAnnotationChain &chain,
109 const int method,
110 MutableSpan<float3> r_positions)
111{
112 const int verts_num = chain.verts.size();
113 Array<int> segment_indices(verts_num);
114 Array<float> factors(verts_num);
115
116 if (method == TO_ANNOTATION_SPREAD_EVENLY) {
118 stroke_data.accumulated_lengths, true, segment_indices, factors);
119 }
120 else {
121 const float chain_length_total = chain.accumulated_lengths.last();
122 const float stroke_length_total = stroke_data.accumulated_lengths.last();
123
124 Array<float> sample_lengths(verts_num);
125 for (const int i : IndexRange(verts_num)) {
126 float sample_factor = (i == 0) ? 0.0f :
127 chain.accumulated_lengths[i - 1] / chain_length_total;
128 sample_lengths[i] = sample_factor * stroke_length_total;
129 }
130
132 stroke_data.accumulated_lengths, sample_lengths, segment_indices, factors);
133 }
134
136 stroke_data.points, segment_indices.as_span(), factors.as_span(), r_positions);
137}
138
148 const StrokeData &stroke_data,
149 const int method)
150{
151 const int verts_num = chain.verts.size();
152 Array<float3> stroke_positions(verts_num);
153 sample_stroke_positions(stroke_data, chain, method, stroke_positions);
154
155 float total_distance = 0.0f;
156 for (const int i : IndexRange(verts_num)) {
157 total_distance += math::distance(float3(chain.verts[i]->co), stroke_positions[i]);
158 }
159 return total_distance;
160}
161
163{
164 BMLoop *l;
165 BMIter liter;
166
167 BM_ITER_ELEM (l, &liter, e, BM_LOOPS_OF_EDGE) {
168 BMLoop *l_other = BM_loop_other_edge_loop(l, v);
169 BMEdge *e_other = l_other->e;
170 if (BM_elem_flag_test(e_other, BM_ELEM_TAG)) {
171 return true;
172 }
173 }
174 return false;
175}
176
177static void calculate_verts(const StrokeData &stroke_data,
178 const int method,
179 const float factor,
180 const bool lock_x,
181 const bool lock_y,
182 const bool lock_z,
183 ToAnnotationChain &r_chain)
184{
185 const int verts_num = r_chain.verts.size();
186
187 if (method == TO_ANNOTATION_PROJECT) {
188 for (const int i : IndexRange(verts_num)) {
189 BMVert *v = r_chain.verts[i];
190 const float3 v_co = float3(v->co);
191 float3 v_co_best = v_co;
192 float dist_sq_best = FLT_MAX;
193 bool has_best = false;
194
195 auto check_intersection_fn = [&](const float3 &ray_dir) {
196 float3 ray_end = v_co + ray_dir * ray_length;
197 float3 ray_start = v_co - ray_dir * ray_length;
198
199 for (const int j : IndexRange(stroke_data.points.size() - 1)) {
200 float3 stroke_seg_start = stroke_data.points[j];
201 float3 stroke_seg_end = stroke_data.points[j + 1];
202
203 float3 closest_on_ray;
204 float3 closest_on_stroke;
205 if (math::isect_line_line(ray_start,
206 ray_end,
207 stroke_seg_start,
208 stroke_seg_end,
209 closest_on_ray,
210 closest_on_stroke) != 0)
211 {
212 if (math::distance_squared(closest_on_ray, closest_on_stroke) <
214 {
215 float dist_seg = math::distance(stroke_seg_start, stroke_seg_end);
216 float dist_to_start = math::distance(stroke_seg_start, closest_on_stroke);
217 float dist_to_end = math::distance(stroke_seg_end, closest_on_stroke);
218
219 if (dist_to_start <= dist_seg + segment_epsilon &&
220 dist_to_end <= dist_seg + segment_epsilon)
221 {
222 float dist_sq_test = math::distance_squared(v_co, closest_on_stroke);
223 if (dist_sq_test < dist_sq_best) {
224 dist_sq_best = dist_sq_test;
225 v_co_best = closest_on_stroke;
226 has_best = true;
227 }
228 }
229 }
230 }
231 }
232 };
233
234 /* In order to project the selected vertices unto the annotation stroke, we need
235 * to shoot rays forwards and backwards from those vertices along the direction of
236 * their connected unselected vertices to find where those rays intersect with the
237 * stroke, with the exception of unselected vertices connected to selected vertices
238 * on the same edge loop of the selection which can cause the selected vertices to
239 * project oddly unto the annotation stroke if the stroke curves around the selection.
240 *
241 * In the case that doesn't yield any results, we fallback to shooting rays from the
242 * vertex normals.
243 */
244 BMIter iter;
245 BMEdge *e;
246 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
249 BMVert *v_other = BM_edge_other_vert(e, v);
250 float3 ray_dir = math::normalize(float3(v_other->co) - float3(v->co));
251 check_intersection_fn(ray_dir);
252 }
253 }
254 }
255
256 if (!has_best) {
257 float3 ray_dir = float3(v->no);
259 ray_dir = math::normalize(ray_dir);
260 check_intersection_fn(ray_dir);
261 }
262 }
263
264 if (has_best) {
265 float3 new_co = math::interpolate(v_co, v_co_best, factor);
266 if (lock_x) {
267 new_co.x = v_co.x;
268 }
269 if (lock_y) {
270 new_co.y = v_co.y;
271 }
272 if (lock_z) {
273 new_co.z = v_co.z;
274 }
275 copy_v3_v3(v->co, new_co);
276 }
277 }
278 }
279 else {
280 Array<float3> stroke_positions(verts_num);
281 sample_stroke_positions(stroke_data, r_chain, method, stroke_positions);
282
283 for (const int i : IndexRange(verts_num)) {
284 BMVert *v = r_chain.verts[i];
285 const float3 v_co = float3(v->co);
286 float3 new_co = math::interpolate(v_co, stroke_positions[i], factor);
287 if (lock_x) {
288 new_co.x = v_co.x;
289 }
290 if (lock_y) {
291 new_co.y = v_co.y;
292 }
293 if (lock_z) {
294 new_co.z = v_co.z;
295 }
296 copy_v3_v3(v->co, new_co);
297 }
298 }
299}
300
302{
303 const float factor = BMO_slot_float_get(op->slots_in, "factor");
304 const int method = BMO_slot_int_get(op->slots_in, "method");
305 const bool lock_x = BMO_slot_bool_get(op->slots_in, "lock_x");
306 const bool lock_y = BMO_slot_bool_get(op->slots_in, "lock_y");
307 const bool lock_z = BMO_slot_bool_get(op->slots_in, "lock_z");
308 Vector<Span<float3>> *stroke_data_in = static_cast<Vector<Span<float3>> *>(
309 BMO_slot_ptr_get(op->slots_in, "strokes"));
310
313
316 Vector<StrokeData> strokes;
317
318 if (stroke_data_in) {
319 for (const Span<float3> &points : *stroke_data_in) {
320 StrokeData stroke_data;
321 stroke_data.points = points;
322 calculate_stroke_lengths(stroke_data);
323 strokes.append(stroke_data);
324 }
325 }
326
327 for (ToAnnotationChain &chain : chains) {
329 if (!is_total_length_valid(chain.accumulated_lengths)) {
330 continue;
331 }
332
333 StrokeData *stroke_best = nullptr;
334 float3 points_fallback[2];
335 StrokeData stroke_fallback;
336
337 /* If there are no annotation strokes drawn, the vertices are moved
338 * onto a line between the first and last vertex. */
339 if (strokes.is_empty()) {
340 float3 chain_start_co = float3(chain.verts.first()->co);
341 float3 chain_end_co = float3(chain.verts.last()->co);
342
343 points_fallback[0] = chain_start_co;
344 points_fallback[1] = chain_end_co;
345 stroke_fallback.points = Span<float3>(points_fallback, 2);
346 stroke_fallback.accumulated_lengths = {math::distance(chain_start_co, chain_end_co)};
347
348 stroke_best = &stroke_fallback;
349 }
350 else {
351 int index_best = -1;
352 int use_count_best = INT_MAX;
353 float dist_sq_best = FLT_MAX;
354
355 for (const int i : strokes.index_range()) {
356 const int use_count = strokes[i].use_count;
357 const float dist_sq_test = math::distance_squared(chain.center, strokes[i].center);
358
359 if (use_count < use_count_best ||
360 (use_count == use_count_best && dist_sq_test < dist_sq_best))
361 {
362 use_count_best = use_count;
363 dist_sq_best = dist_sq_test;
364 index_best = i;
365 }
366 }
367
368 strokes[index_best].use_count++;
369 stroke_best = &strokes[index_best];
370 }
371
372 float forward_dist = calculate_alignment_distance(chain, *stroke_best, method);
373
374 ToAnnotationChain reversed_chain = chain;
375 std::reverse(reversed_chain.verts.begin(), reversed_chain.verts.end());
376 reversed_chain.center = float3(0.0f);
377 reversed_chain.accumulated_lengths.clear();
378 calculate_chain_lengths(reversed_chain);
379
380 float reversed_dist = calculate_alignment_distance(reversed_chain, *stroke_best, method);
381 if (reversed_dist < forward_dist) {
382 chain = std::move(reversed_chain);
383 }
384 calculate_verts(*stroke_best, method, factor, lock_x, lock_y, lock_z, chain);
385 }
386}
387
388} // namespace blender
#define BM_elem_flag_test(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
Span< T > as_span() const
Definition BLI_array.hh:254
constexpr IndexRange()=default
constexpr Span()=default
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr const T & last(const int64_t n=0) const
Definition BLI_span.hh:329
void append(const T &value)
bool is_empty() const
IndexRange index_range() const
void resize(const int64_t new_size)
MutableSpan< T > as_mutable_span()
const T & last(const int64_t n=0) const
#define FLT_MAX
#define INT_MAX
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)
void sample_uniform(Span< float > accumulated_segment_lengths, bool include_last_point, MutableSpan< int > r_segment_indices, MutableSpan< float > r_factors)
T length_squared(const VecBase< T, Size > &a)
T distance(const T &a, const T &b)
T interpolate(const T &a, const T &b, const FactorT &t)
MatBase< T, NumCol, NumRow > normalize(const MatBase< T, NumCol, NumRow > &a)
T square(const T &a)
T distance_squared(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
int isect_line_line(const float3 &v1, const float3 &v2, const float3 &v3, const float3 &v4, float3 &r_i1, float3 &r_i2)
BMesh Iterators.
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 void sample_stroke_positions(const StrokeData &stroke_data, const ToAnnotationChain &chain, const int method, MutableSpan< float3 > r_positions)
constexpr float max_ray_distance
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.
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void BM_mesh_edgeloops_free(ListBaseT< BMEdgeLoopStore > *eloops)
float BMO_slot_float_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
static void measure_positions(const Span< float3 > positions, float3 &r_center, Vector< float > &r_accumulated_lengths)
void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
ATTR_WARN_UNUSED_RESULT const BMVert * v
static void calculate_verts(const StrokeData &stroke_data, const int method, const float factor, const bool lock_x, const bool lock_y, const bool lock_z, ToAnnotationChain &r_chain)
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void * BMO_slot_ptr_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
static bool is_total_length_valid(const Span< float > accumulated_lengths)
constexpr float segment_epsilon
static bool edge_shares_face_with_tagged_edge(BMEdge *e, BMVert *v)
static void calc_annotation_input_chains_from_bm(BMesh *bm, Vector< ToAnnotationChain > &r_chains)
bool BMO_slot_bool_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
@ TO_ANNOTATION_SPREAD_EVENLY
constexpr float normal_length_epsilon
static float calculate_alignment_distance(const ToAnnotationChain &chain, const StrokeData &stroke_data, const int method)
void bmo_fit_edge_loops_to_annotation_exec(BMesh *bm, BMOperator *op)
VecBase< float, 3 > float3
static void calculate_chain_lengths(ToAnnotationChain &chain)
static void calculate_stroke_lengths(StrokeData &stroke_data)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
BMLoop * BM_loop_other_edge_loop(BMLoop *l, BMVert *v)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
struct BMEdge * e
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]