Blender V5.3
bmesh_path_region.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
11
12#include "MEM_guardedalloc.h"
13
14#include <algorithm>
15
16#include "BLI_array.hh"
17#include "BLI_linklist.hh"
18#include "BLI_math_vector_c.hh"
20
21#include "bmesh.hh"
22#include "bmesh_path_region.hh" /* own include */
23
24namespace blender {
25
37#define USE_EDGE_CHAIN
38
39#ifdef USE_EDGE_CHAIN
45static bool bm_vert_pair_ends(BMVert *v_pivot, BMVert *v_end_pair[2])
46{
47 BMEdge *e = v_pivot->e;
48 int j = 0;
49 do {
50 BMEdge *e_chain = e;
51 BMVert *v_other = BM_edge_other_vert(e_chain, v_pivot);
52 while (BM_vert_is_edge_pair_manifold(v_other)) {
53 BMEdge *e_chain_next = BM_DISK_EDGE_NEXT(e_chain, v_other);
54 BLI_assert(BM_DISK_EDGE_NEXT(e_chain_next, v_other) == e_chain);
55 v_other = BM_edge_other_vert(e_chain_next, v_other);
56 if (v_other == v_pivot) {
57 return false;
58 }
59 e_chain = e_chain_next;
60 }
61 v_end_pair[j++] = v_other;
62 } while ((e = BM_DISK_EDGE_NEXT(e, v_pivot)) != v_pivot->e);
63
64 BLI_assert(j == 2);
65 return true;
66}
67#endif /* USE_EDGE_CHAIN */
68
69/* -------------------------------------------------------------------- */
72
73static bool bm_vert_region_test(BMVert *v, int *const depths[2], const int pass)
74{
75 const int index = BM_elem_index_get(v);
76 return (((depths[0][index] != -1) && (depths[1][index] != -1)) &&
77 ((depths[0][index] + depths[1][index]) < pass));
78}
79
80#ifdef USE_EDGE_CHAIN
81static bool bm_vert_region_test_chain(BMVert *v, int *const depths[2], const int pass)
82{
83 BMVert *v_end_pair[2];
84 if (bm_vert_region_test(v, depths, pass)) {
85 return true;
86 }
88 bm_vert_region_test(v_end_pair[0], depths, pass) &&
89 bm_vert_region_test(v_end_pair[1], depths, pass))
90 {
91 return true;
92 }
93
94 return false;
95}
96#else
97static bool bm_vert_region_test_chain(BMVert *v, int *const depths[2], const int pass)
98{
99 return bm_vert_region_test(v, depths, pass);
100}
101#endif
102
104
119 BMElem *ele_src,
120 BMElem *ele_dst,
121 const char path_htype)
122{
123 int ele_verts_len[2];
125 BMVert **ele_verts[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_verts_buf[side].resize(f->len);
135 ele_verts[side] = ele_verts_buf[side].data();
136
137 BMLoop *l_first, *l_iter;
138 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
139 do {
140 ele_verts[side][j++] = l_iter->v;
141 } while ((l_iter = l_iter->next) != l_first);
142 }
143 else if (ele->head.htype == BM_EDGE) {
144 BMEdge *e = reinterpret_cast<BMEdge *>(ele);
145 ele_verts_buf[side].resize(2);
146 ele_verts[side] = ele_verts_buf[side].data();
147
148 ele_verts[side][j++] = e->v1;
149 ele_verts[side][j++] = e->v2;
150 }
151 else if (ele->head.htype == BM_VERT) {
152 BMVert *v = reinterpret_cast<BMVert *>(ele);
153 ele_verts_buf[side].resize(1);
154 ele_verts[side] = ele_verts_buf[side].data();
155
156 ele_verts[side][j++] = v;
157 }
158 else {
159 BLI_assert(0);
160 }
161 ele_verts_len[side] = j;
162 }
163
164 int *depths[2] = {nullptr};
165 int pass = 0;
166
168 BMVert **stack_other = MEM_new_array_uninitialized<BMVert *>(bm->totvert, __func__);
169
170 STACK_DECLARE(stack);
171 STACK_INIT(stack, bm->totvert);
172
173 STACK_DECLARE(stack_other);
174 STACK_INIT(stack_other, bm->totvert);
175
177
178 /* After exhausting all possible elements, we should have found all elements on the 'side_other'.
179 * otherwise, exit early. */
180 bool found_all = false;
181
182 for (int side = 0; side < 2; side++) {
183 const int side_other = !side;
184
185 /* initialize depths to -1 (un-touched), fill in with the depth as we walk over the edges. */
186 depths[side] = MEM_new_array_uninitialized<int>(bm->totvert, __func__);
187 std::fill_n(depths[side], bm->totvert, -1);
188
189 /* needed for second side */
190 STACK_CLEAR(stack);
191 STACK_CLEAR(stack_other);
192
193 for (int i = 0; i < ele_verts_len[side]; i++) {
194 BMVert *v = ele_verts[side][i];
195 depths[side][BM_elem_index_get(v)] = 0;
196 if (v->e && !BM_elem_flag_test(v, BM_ELEM_TAG)) {
197 STACK_PUSH(stack, v);
198 }
199 }
200
201#ifdef USE_EDGE_CHAIN
202 /* Expand initial state to end-point vertices when they only have 2x edges,
203 * this prevents odd behavior when source or destination are in the middle
204 * of a long chain of edges. */
205 if (ELEM(path_htype, BM_VERT, BM_EDGE)) {
206 for (int i = 0; i < ele_verts_len[side]; i++) {
207 BMVert *v = ele_verts[side][i];
208 BMVert *v_end_pair[2];
209 if (BM_vert_is_edge_pair_manifold(v) && bm_vert_pair_ends(v, v_end_pair)) {
210 for (int j = 0; j < 2; j++) {
211 const int v_end_index = BM_elem_index_get(v_end_pair[j]);
212 if (depths[side][v_end_index] == -1) {
213 depths[side][v_end_index] = 0;
214 if (!BM_elem_flag_test(v_end_pair[j], BM_ELEM_TAG)) {
215 STACK_PUSH(stack, v_end_pair[j]);
216 }
217 }
218 }
219 }
220 }
221 }
222#endif /* USE_EDGE_CHAIN */
223
224 /* Keep walking over connected geometry until we find all the vertices in
225 * `ele_verts[side_other]`, or exit the loop when there's no connection. */
226 found_all = false;
227 for (pass = 1; (STACK_SIZE(stack) != 0); pass++) {
228 while (STACK_SIZE(stack) != 0) {
229 BMVert *v_a = STACK_POP(stack);
230 // const int v_a_index = BM_elem_index_get(v_a); /* only for assert */
231 BMEdge *e = v_a->e;
232
233 do {
234 BMVert *v_b = BM_edge_other_vert(e, v_a);
235 int v_b_index = BM_elem_index_get(v_b);
236 if (depths[side][v_b_index] == -1) {
237
238#ifdef USE_EDGE_CHAIN
239 /* Walk along the chain, fill in values until we reach a vertex with 3+ edges. */
240 {
241 BMEdge *e_chain = e;
242 while (BM_vert_is_edge_pair_manifold(v_b) && (depths[side][v_b_index] == -1)) {
243 depths[side][v_b_index] = pass;
244
245 BMEdge *e_chain_next = BM_DISK_EDGE_NEXT(e_chain, v_b);
246 BLI_assert(BM_DISK_EDGE_NEXT(e_chain_next, v_b) == e_chain);
247 v_b = BM_edge_other_vert(e_chain_next, v_b);
248 v_b_index = BM_elem_index_get(v_b);
249 e_chain = e_chain_next;
250 }
251 }
252#endif /* USE_EDGE_CHAIN */
253
254 /* Add the other vertex to the stack, to be traversed in the next pass. */
255 if (depths[side][v_b_index] == -1) {
256#ifdef USE_EDGE_CHAIN
258#endif
259 BLI_assert(pass == depths[side][BM_elem_index_get(v_a)] + 1);
260 depths[side][v_b_index] = pass;
261 if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
262 STACK_PUSH(stack_other, v_b);
263 }
264 }
265 }
266 } while ((e = BM_DISK_EDGE_NEXT(e, v_a)) != v_a->e);
267 }
268
269 /* Stop searching once there's none left.
270 * Note that this looks in-efficient, however until the target elements reached,
271 * it will exit immediately.
272 * After that, it takes as many passes as the element has edges to finish off. */
273 found_all = true;
274 for (int i = 0; i < ele_verts_len[side_other]; i++) {
275 if (depths[side][BM_elem_index_get(ele_verts[side_other][i])] == -1) {
276 found_all = false;
277 break;
278 }
279 }
280 if (found_all == true) {
281 pass++;
282 break;
283 }
284
285 STACK_SWAP(stack, stack_other);
286 }
287
288 /* if we have nothing left, and didn't find all elements on the other side,
289 * exit early and don't continue */
290 if (found_all == false) {
291 break;
292 }
293 }
294
295 MEM_delete(stack);
296 MEM_delete(stack_other);
297
298 /* Now we have depths recorded from both sides,
299 * select elements that use tagged verts. */
300 LinkNode *path = nullptr;
301
302 if (found_all == false) {
303 /* fail! (do nothing) */
304 }
305 else if (path_htype == BM_FACE) {
306 BMIter fiter;
307 BMFace *f;
308
309 BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
311 /* check all verts in face are tagged */
312 BMLoop *l_first, *l_iter;
313 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
314 bool ok = true;
315#if 0
316 do {
317 if (!bm_vert_region_test_chain(l_iter->v, depths, pass)) {
318 ok = false;
319 break;
320 }
321 } while ((l_iter = l_iter->next) != l_first);
322#else
323 /* Allowing a single failure on a face gives fewer 'gaps'.
324 * While correct, in practice they're often part of what
325 * a user would consider the 'region'. */
326 int ok_tests = f->len > 3 ? 1 : 0; /* how many times we may fail */
327 do {
328 if (!bm_vert_region_test_chain(l_iter->v, depths, pass)) {
329 if (ok_tests == 0) {
330 ok = false;
331 break;
332 }
333 ok_tests--;
334 }
335 } while ((l_iter = l_iter->next) != l_first);
336#endif
337
338 if (ok) {
339 BLI_linklist_prepend(&path, f);
340 }
341 }
342 }
343 }
344 else if (path_htype == BM_EDGE) {
345 BMIter eiter;
346 BMEdge *e;
347
348 BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
350 /* check all verts in edge are tagged */
351 bool ok = true;
352 for (int j = 0; j < 2; j++) {
353 if (!bm_vert_region_test_chain(*((&e->v1) + j), depths, pass)) {
354 ok = false;
355 break;
356 }
357 }
358
359 if (ok) {
360 BLI_linklist_prepend(&path, e);
361 }
362 }
363 }
364 }
365 else if (path_htype == BM_VERT) {
366 BMIter viter;
367 BMVert *v;
368
369 BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
370 if (bm_vert_region_test_chain(v, depths, pass)) {
371 BLI_linklist_prepend(&path, v);
372 }
373 }
374 }
375
376 for (int side = 0; side < 2; side++) {
377 if (depths[side]) {
378 MEM_delete(depths[side]);
379 }
380 }
381
382 return path;
383}
384
385#undef USE_EDGE_CHAIN
386
387/* -------------------------------------------------------------------- */
390
392 BMElem *ele_src,
393 BMElem *ele_dst,
394 bool (*filter_fn)(BMVert *, void *user_data),
395 void *user_data)
396{
397 LinkNode *path = nullptr;
398 /* BM_ELEM_TAG flag is used to store visited verts */
399 BMVert *v;
400 BMIter viter;
401 int i;
402
403 BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
404 BM_elem_flag_set(v, BM_ELEM_TAG, !filter_fn(v, user_data));
405 BM_elem_index_set(v, i); /* set_inline */
406 }
408
409 path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_VERT);
410
411 return path;
412}
413
415 BMElem *ele_src,
416 BMElem *ele_dst,
417 bool (*filter_fn)(BMEdge *, void *user_data),
418 void *user_data)
419{
420 LinkNode *path = nullptr;
421 /* BM_ELEM_TAG flag is used to store visited verts */
422 BMEdge *e;
423 BMIter eiter;
424 int i;
425
426 /* flush flag to verts */
428
429 BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
430 bool test;
431 BM_elem_flag_set(e, BM_ELEM_TAG, test = !filter_fn(e, user_data));
432
433 /* flush tag to verts */
434 if (test == false) {
435 for (int j = 0; j < 2; j++) {
436 BM_elem_flag_disable(*((&e->v1) + j), BM_ELEM_TAG);
437 }
438 }
439 }
440
441 path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_EDGE);
442
443 return path;
444}
445
447 BMElem *ele_src,
448 BMElem *ele_dst,
449 bool (*filter_fn)(BMFace *, void *user_data),
450 void *user_data)
451{
452 LinkNode *path = nullptr;
453 /* BM_ELEM_TAG flag is used to store visited verts */
454 BMFace *f;
455 BMIter fiter;
456 int i;
457
458 /* flush flag to verts */
460
461 BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
462 bool test;
463 BM_elem_flag_set(f, BM_ELEM_TAG, test = !filter_fn(f, user_data));
464
465 /* flush tag to verts */
466 if (test == false) {
467 BMLoop *l_first, *l_iter;
468 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
469 do {
471 } while ((l_iter = l_iter->next) != l_first);
472 }
473 }
474
475 path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_FACE);
476
477 return path;
478}
479
481
482} // 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_DISK_EDGE_NEXT(e, v)
#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_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 BMVert * v
LinkNode * BM_mesh_calc_path_region_edge(BMesh *bm, BMElem *ele_src, BMElem *ele_dst, bool(*filter_fn)(BMEdge *, void *user_data), void *user_data)
static bool bm_vert_region_test_chain(BMVert *v, int *const depths[2], const int pass)
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void void BLI_linklist_prepend(LinkNode **listp, void *ptr) ATTR_NONNULL(1)
bool BM_vert_is_edge_pair_manifold(const BMVert *v)
static bool bm_vert_region_test(BMVert *v, int *const depths[2], const int pass)
static bool bm_vert_pair_ends(BMVert *v_pivot, BMVert *v_end_pair[2])
static LinkNode * mesh_calc_path_region_elem(BMesh *bm, BMElem *ele_src, BMElem *ele_dst, const char path_htype)
LinkNode * BM_mesh_calc_path_region_face(BMesh *bm, BMElem *ele_src, BMElem *ele_dst, bool(*filter_fn)(BMFace *, void *user_data), void *user_data)
LinkNode * BM_mesh_calc_path_region_vert(BMesh *bm, BMElem *ele_src, BMElem *ele_dst, bool(*filter_fn)(BMVert *, void *user_data), void *user_data)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
struct BMLoop * next
struct BMVert * v
struct BMEdge * e