Blender V5.3
bmesh_path_region_uv.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
15
16#include "MEM_guardedalloc.h"
17
18#include <algorithm>
19
20#include "BLI_array.hh"
21#include "BLI_linklist.hh"
22#include "BLI_math_vector_c.hh"
24
25#include "bmesh.hh"
26#include "bmesh_path_region_uv.hh" /* own include */
27
28namespace blender {
29
41#define USE_EDGE_CHAIN
42
43#ifdef USE_EDGE_CHAIN
49static bool bm_loop_pair_ends(BMLoop *l_pivot, BMLoop *l_end_pair[2])
50{
51 int j;
52 for (j = 0; j < 2; j++) {
53 BMLoop *l_other = j ? l_pivot->next : l_pivot->prev;
54 while (BM_vert_is_edge_pair_manifold(l_other->v)) {
55 l_other = j ? l_other->next : l_other->prev;
56 if (l_other == l_pivot) {
57 return false;
58 }
59 }
60 l_end_pair[j] = l_other;
61 }
62 BLI_assert(j == 2);
63 return true;
64}
65#endif /* USE_EDGE_CHAIN */
66
67/* -------------------------------------------------------------------- */
70
71static bool bm_loop_region_test(BMLoop *l, int *const depths[2], const int pass)
72{
73 const int index = BM_elem_index_get(l);
74 return (((depths[0][index] != -1) && (depths[1][index] != -1)) &&
75 ((depths[0][index] + depths[1][index]) < pass));
76}
77
78#ifdef USE_EDGE_CHAIN
79static bool bm_loop_region_test_chain(BMLoop *l, int *const depths[2], const int pass)
80{
81 BMLoop *l_end_pair[2];
82 if (bm_loop_region_test(l, depths, pass)) {
83 return true;
84 }
85 if (BM_vert_is_edge_pair_manifold(l->v) && bm_loop_pair_ends(l, l_end_pair) &&
86 bm_loop_region_test(l_end_pair[0], depths, pass) &&
87 bm_loop_region_test(l_end_pair[1], depths, pass))
88 {
89 return true;
90 }
91
92 return false;
93}
94#else
95static bool bm_loop_region_test_chain(BMLoop *l, int *const depths[2], const int pass)
96{
97 return bm_loop_region_test(l, depths, pass);
98}
99#endif
100
102
117 BMElem *ele_src,
118 BMElem *ele_dst,
119 const int cd_loop_uv_offset,
120 const char path_htype)
121{
122 BLI_assert(cd_loop_uv_offset >= 0);
123 int ele_loops_len[2];
125 BMLoop **ele_loops[2];
126
127 /* Get vertices from any `ele_src/ele_dst` elements. */
128 for (int side = 0; side < 2; side++) {
129 BMElem *ele = side ? ele_dst : ele_src;
130 int j = 0;
131
132 if (ele->head.htype == BM_FACE) {
133 BMFace *f = reinterpret_cast<BMFace *>(ele);
134 ele_loops_buf[side].resize(f->len);
135 ele_loops[side] = ele_loops_buf[side].data();
136
137 BMLoop *l_first, *l_iter;
138 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
139 do {
140 ele_loops[side][j++] = l_iter;
141 } while ((l_iter = l_iter->next) != l_first);
142 }
143 else if (ele->head.htype == BM_LOOP) {
144 if (path_htype == BM_EDGE) {
145 BMLoop *l = reinterpret_cast<BMLoop *>(ele);
146 ele_loops_buf[side].resize(2);
147 ele_loops[side] = ele_loops_buf[side].data();
148 ele_loops[side][j++] = l;
149 ele_loops[side][j++] = l->next;
150 }
151 else if (path_htype == BM_VERT) {
152 BMLoop *l = reinterpret_cast<BMLoop *>(ele);
153 ele_loops_buf[side].resize(1);
154 ele_loops[side] = ele_loops_buf[side].data();
155
156 ele_loops[side][j++] = l;
157 }
158 else {
159 BLI_assert(0);
160 }
161 }
162 else {
163 BLI_assert(0);
164 }
165 ele_loops_len[side] = j;
166 }
167
168 int *depths[2] = {nullptr};
169 int pass = 0;
170
172 BMLoop **stack_other = MEM_new_array_uninitialized<BMLoop *>(bm->totloop, __func__);
173
174 STACK_DECLARE(stack);
175 STACK_INIT(stack, bm->totloop);
176
177 STACK_DECLARE(stack_other);
178 STACK_INIT(stack_other, bm->totloop);
179
181
182 /* After exhausting all possible elements, we should have found all elements on the 'side_other'.
183 * otherwise, exit early. */
184 bool found_all = false;
185
186 for (int side = 0; side < 2; side++) {
187 const int side_other = !side;
188
189 /* initialize depths to -1 (un-touched), fill in with the depth as we walk over the edges. */
190 depths[side] = MEM_new_array_uninitialized<int>(bm->totloop, __func__);
191 std::fill_n(depths[side], bm->totloop, -1);
192
193 /* needed for second side */
194 STACK_CLEAR(stack);
195 STACK_CLEAR(stack_other);
196
197 for (int i = 0; i < ele_loops_len[side]; i++) {
198 BMLoop *l = ele_loops[side][i];
199 depths[side][BM_elem_index_get(l)] = 0;
201 STACK_PUSH(stack, l);
202 }
203 }
204
205#ifdef USE_EDGE_CHAIN
206 /* Expand initial state to end-point vertices when they only have 2x edges,
207 * this prevents odd behavior when source or destination are in the middle
208 * of a long chain of edges. */
209 if (ELEM(path_htype, BM_VERT, BM_EDGE)) {
210 for (int i = 0; i < ele_loops_len[side]; i++) {
211 BMLoop *l = ele_loops[side][i];
212 BMLoop *l_end_pair[2];
213 if (BM_vert_is_edge_pair_manifold(l->v) && bm_loop_pair_ends(l, l_end_pair)) {
214 for (int j = 0; j < 2; j++) {
215 const int l_end_index = BM_elem_index_get(l_end_pair[j]);
216 if (depths[side][l_end_index] == -1) {
217 depths[side][l_end_index] = 0;
218 if (!BM_elem_flag_test(l_end_pair[j], BM_ELEM_TAG)) {
219 STACK_PUSH(stack, l_end_pair[j]);
220 }
221 }
222 }
223 }
224 }
225 }
226#endif /* USE_EDGE_CHAIN */
227
228 /* Keep walking over connected geometry until we find all the vertices in
229 * `ele_loops[side_other]`, or exit the loop when there's no connection. */
230 found_all = false;
231 for (pass = 1; (STACK_SIZE(stack) != 0); pass++) {
232 while (STACK_SIZE(stack) != 0) {
233 BMLoop *l_a = STACK_POP(stack);
234 const int l_a_index = BM_elem_index_get(l_a);
235
236 BMIter iter;
237 BMLoop *l_iter;
238
239 BM_ITER_ELEM (l_iter, &iter, l_a->v, BM_LOOPS_OF_VERT) {
240 if (BM_elem_flag_test(l_iter, BM_ELEM_TAG)) {
241 continue;
242 }
243 if (!BM_loop_uv_share_vert_check(l_a, l_iter, cd_loop_uv_offset)) {
244 continue;
245 }
246
247 /* Flush the depth to connected loops (only needed for UVs). */
248 if (depths[side][BM_elem_index_get(l_iter)] == -1) {
249 depths[side][BM_elem_index_get(l_iter)] = depths[side][l_a_index];
250 }
251
252 for (int j = 0; j < 2; j++) {
253 BMLoop *l_b = j ? l_iter->next : l_iter->prev;
254 int l_b_index = BM_elem_index_get(l_b);
255 if (depths[side][l_b_index] == -1) {
256
257#ifdef USE_EDGE_CHAIN
258 /* Walk along the chain, fill in values until we reach a vertex with 3+ edges. */
259 {
261 ((depths[side][l_b_index] == -1) &&
262 /* Don't walk back to the beginning */
263 (l_b != (j ? l_iter->prev : l_iter->next))))
264 {
265 depths[side][l_b_index] = pass;
266
267 l_b = j ? l_b->next : l_b->prev;
268 l_b_index = BM_elem_index_get(l_b);
269 }
270 }
271#endif /* USE_EDGE_CHAIN */
272
273 /* Add the other vertex to the stack, to be traversed in the next pass. */
274 if (depths[side][l_b_index] == -1) {
275#ifdef USE_EDGE_CHAIN
277#endif
278 BLI_assert(pass == depths[side][BM_elem_index_get(l_a)] + 1);
279 depths[side][l_b_index] = pass;
281 STACK_PUSH(stack_other, l_b);
282 }
283 }
284 }
285 }
286 }
287 }
288
289 /* Stop searching once there's none left.
290 * Note that this looks in-efficient, however until the target elements reached,
291 * it will exit immediately.
292 * After that, it takes as many passes as the element has edges to finish off. */
293 found_all = true;
294 for (int i = 0; i < ele_loops_len[side_other]; i++) {
295 if (depths[side][BM_elem_index_get(ele_loops[side_other][i])] == -1) {
296 found_all = false;
297 break;
298 }
299 }
300 if (found_all == true) {
301 pass++;
302 break;
303 }
304
305 STACK_SWAP(stack, stack_other);
306 }
307
308 /* if we have nothing left, and didn't find all elements on the other side,
309 * exit early and don't continue */
310 if (found_all == false) {
311 break;
312 }
313 }
314
315 MEM_delete(stack);
316 MEM_delete(stack_other);
317
318 /* Now we have depths recorded from both sides,
319 * select elements that use tagged verts. */
320 LinkNode *path = nullptr;
321
322 if (found_all == false) {
323 /* fail! (do nothing) */
324 }
325 else if (path_htype == BM_FACE) {
326 BMIter fiter;
327 BMFace *f;
328
329 BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
331 /* check all verts in face are tagged */
332 BMLoop *l_first, *l_iter;
333 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
334 bool ok = true;
335#if 0
336 do {
337 if (!bm_loop_region_test_chain(l_iter->v, depths, pass)) {
338 ok = false;
339 break;
340 }
341 } while ((l_iter = l_iter->next) != l_first);
342#else
343 /* Allowing a single failure on a face gives fewer 'gaps'.
344 * While correct, in practice they're often part of what
345 * a user would consider the 'region'. */
346 int ok_tests = f->len > 3 ? 1 : 0; /* how many times we may fail */
347 do {
348 if (!bm_loop_region_test_chain(l_iter, depths, pass)) {
349 if (ok_tests == 0) {
350 ok = false;
351 break;
352 }
353 ok_tests--;
354 }
355 } while ((l_iter = l_iter->next) != l_first);
356#endif
357
358 if (ok) {
359 BLI_linklist_prepend(&path, f);
360 }
361 }
362 }
363 }
364 else if (path_htype == BM_EDGE) {
365 BMIter fiter;
366 BMFace *f;
367 BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
368 BMIter liter;
369 BMLoop *l;
370 /* Check the current and next loop vertices are in the region. */
371 bool l_in_chain_next = bm_loop_region_test_chain(BM_FACE_FIRST_LOOP(f), depths, pass);
372 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
373 const bool l_in_chain = l_in_chain_next;
374 l_in_chain_next = bm_loop_region_test_chain(l->next, depths, pass);
375 if (l_in_chain && l_in_chain_next) {
376 BLI_linklist_prepend(&path, l);
377 }
378 }
379 }
380 }
381 else if (path_htype == BM_VERT) {
382 BMIter fiter;
383 BMFace *f;
384 BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
385 BMIter liter;
386 BMLoop *l;
387 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
388 if (bm_loop_region_test_chain(l, depths, pass)) {
389 BLI_linklist_prepend(&path, l);
390 }
391 }
392 }
393 }
394
395 for (int side = 0; side < 2; side++) {
396 if (depths[side]) {
397 MEM_delete(depths[side]);
398 }
399 }
400
401 return path;
402}
403
404#undef USE_EDGE_CHAIN
405
406/* -------------------------------------------------------------------- */
409
411 BMElem *ele_src,
412 BMElem *ele_dst,
413 const int cd_loop_uv_offset,
414 bool (*filter_fn)(BMLoop *, void *user_data),
415 void *user_data)
416{
417 LinkNode *path = nullptr;
418 /* BM_ELEM_TAG flag is used to store visited verts */
419 BMFace *f;
420 BMIter fiter;
421 int i = 0;
422
423 BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
424 BMIter liter;
425 BMLoop *l;
426 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
427 BM_elem_flag_set(l, BM_ELEM_TAG, !filter_fn(l, user_data));
428 BM_elem_index_set(l, i); /* set_inline */
429 i += 1;
430 }
431 }
433
434 path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, cd_loop_uv_offset, BM_VERT);
435
436 return path;
437}
438
440 BMElem *ele_src,
441 BMElem *ele_dst,
442 const int cd_loop_uv_offset,
443 bool (*filter_fn)(BMLoop *, void *user_data),
444 void *user_data)
445{
446 LinkNode *path = nullptr;
447 /* BM_ELEM_TAG flag is used to store visited verts */
448 BMFace *f;
449 BMIter fiter;
450 int i = 0;
451
452 BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
453 BMIter liter;
454 BMLoop *l;
455 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
456 BM_elem_flag_set(l, BM_ELEM_TAG, !filter_fn(l, user_data));
457 BM_elem_index_set(l, i); /* set_inline */
458 i += 1;
459 }
460 }
462
463 path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, cd_loop_uv_offset, BM_EDGE);
464
465 return path;
466}
467
469 BMElem *ele_src,
470 BMElem *ele_dst,
471 const int cd_loop_uv_offset,
472 bool (*filter_fn)(BMFace *, void *user_data),
473 void *user_data)
474{
475 LinkNode *path = nullptr;
476 /* BM_ELEM_TAG flag is used to store visited verts */
477 BMFace *f;
478 BMIter fiter;
479 int i;
480
481 /* flush flag to verts */
483
484 BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
485 bool test;
486 BM_elem_flag_set(f, BM_ELEM_TAG, test = !filter_fn(f, user_data));
487
488 /* flush tag to verts */
489 if (test == false) {
490 BMLoop *l_first, *l_iter;
491 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
492 do {
494 } while ((l_iter = l_iter->next) != l_first);
495 }
496 }
497
498 path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, cd_loop_uv_offset, BM_FACE);
499
500 return path;
501}
502
504
505} // namespace blender
#define STACK_POP(stack)
#define STACK_CLEAR(stack)
#define STACK_PUSH(stack, val)
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_INIT(stack, stack_num)
#define STACK_SWAP(stack_a, stack_b)
Read Blender memory allocation and freeing.
#define ELEM(...)
#define BM_FACE_FIRST_LOOP(p)
#define BM_elem_index_get(ele)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_flag_set(ele, hflag, val)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
void resize(const int64_t new_size)
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
void BM_mesh_elem_hflag_enable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
ATTR_WARN_UNUSED_RESULT const BMLoop * l
bool BM_loop_uv_share_vert_check(const BMLoop *l_a, const BMLoop *l_b, const int cd_loop_uv_offset)
void void BLI_linklist_prepend(LinkNode **listp, void *ptr) ATTR_NONNULL(1)
bool BM_vert_is_edge_pair_manifold(const BMVert *v)
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
LinkNode * BM_mesh_calc_path_uv_region_face(BMesh *bm, BMElem *ele_src, BMElem *ele_dst, const int cd_loop_uv_offset, bool(*filter_fn)(BMFace *, void *user_data), void *user_data)
static bool bm_loop_region_test_chain(BMLoop *l, int *const depths[2], const int pass)
static bool bm_loop_region_test(BMLoop *l, int *const depths[2], const int pass)
LinkNode * BM_mesh_calc_path_uv_region_vert(BMesh *bm, BMElem *ele_src, BMElem *ele_dst, const int cd_loop_uv_offset, bool(*filter_fn)(BMLoop *, void *user_data), void *user_data)
static LinkNode * mesh_calc_path_region_elem(BMesh *bm, BMElem *ele_src, BMElem *ele_dst, const char path_htype)
static bool bm_loop_pair_ends(BMLoop *l_pivot, BMLoop *l_end_pair[2])
LinkNode * BM_mesh_calc_path_uv_region_edge(BMesh *bm, BMElem *ele_src, BMElem *ele_dst, const int cd_loop_uv_offset, bool(*filter_fn)(BMLoop *, void *user_data), void *user_data)
struct BMLoop * next
struct BMLoop * prev
struct BMVert * v