Blender  V3.3
bmesh_path_region.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
10 #include "MEM_guardedalloc.h"
11 
12 #include "BLI_alloca.h"
13 #include "BLI_linklist.h"
14 #include "BLI_math.h"
15 #include "BLI_utildefines_stack.h"
16 
17 #include "bmesh.h"
18 #include "bmesh_path_region.h" /* own include */
19 
31 #define USE_EDGE_CHAIN
32 
33 #ifdef USE_EDGE_CHAIN
39 static bool bm_vert_pair_ends(BMVert *v_pivot, BMVert *v_end_pair[2])
40 {
41  BMEdge *e = v_pivot->e;
42  int j = 0;
43  do {
44  BMEdge *e_chain = e;
45  BMVert *v_other = BM_edge_other_vert(e_chain, v_pivot);
46  while (BM_vert_is_edge_pair_manifold(v_other)) {
47  BMEdge *e_chain_next = BM_DISK_EDGE_NEXT(e_chain, v_other);
48  BLI_assert(BM_DISK_EDGE_NEXT(e_chain_next, v_other) == e_chain);
49  v_other = BM_edge_other_vert(e_chain_next, v_other);
50  if (v_other == v_pivot) {
51  return false;
52  }
53  e_chain = e_chain_next;
54  }
55  v_end_pair[j++] = v_other;
56  } while ((e = BM_DISK_EDGE_NEXT(e, v_pivot)) != v_pivot->e);
57 
58  BLI_assert(j == 2);
59  return true;
60 }
61 #endif /* USE_EDGE_CHAIN */
62 
63 /* -------------------------------------------------------------------- */
67 static bool bm_vert_region_test(BMVert *v, int *const depths[2], const int pass)
68 {
69  const int index = BM_elem_index_get(v);
70  return (((depths[0][index] != -1) && (depths[1][index] != -1)) &&
71  ((depths[0][index] + depths[1][index]) < pass));
72 }
73 
74 #ifdef USE_EDGE_CHAIN
75 static bool bm_vert_region_test_chain(BMVert *v, int *const depths[2], const int pass)
76 {
77  BMVert *v_end_pair[2];
78  if (bm_vert_region_test(v, depths, pass)) {
79  return true;
80  }
81  if (BM_vert_is_edge_pair_manifold(v) && bm_vert_pair_ends(v, v_end_pair) &&
82  bm_vert_region_test(v_end_pair[0], depths, pass) &&
83  bm_vert_region_test(v_end_pair[1], depths, pass)) {
84  return true;
85  }
86 
87  return false;
88 }
89 #else
90 static bool bm_vert_region_test_chain(BMVert *v, int *const depths[2], const int pass)
91 {
92  return bm_vert_region_test(v, depths, pass);
93 }
94 #endif
95 
112  BMElem *ele_src,
113  BMElem *ele_dst,
114  const char path_htype)
115 {
116  int ele_verts_len[2];
117  BMVert **ele_verts[2];
118 
119  /* Get vertices from any `ele_src/ele_dst` elements. */
120  for (int side = 0; side < 2; side++) {
121  BMElem *ele = side ? ele_dst : ele_src;
122  int j = 0;
123 
124  if (ele->head.htype == BM_FACE) {
125  BMFace *f = (BMFace *)ele;
126  ele_verts[side] = BLI_array_alloca(ele_verts[side], f->len);
127 
128  BMLoop *l_first, *l_iter;
129  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
130  do {
131  ele_verts[side][j++] = l_iter->v;
132  } while ((l_iter = l_iter->next) != l_first);
133  }
134  else if (ele->head.htype == BM_EDGE) {
135  BMEdge *e = (BMEdge *)ele;
136  ele_verts[side] = BLI_array_alloca(ele_verts[side], 2);
137 
138  ele_verts[side][j++] = e->v1;
139  ele_verts[side][j++] = e->v2;
140  }
141  else if (ele->head.htype == BM_VERT) {
142  BMVert *v = (BMVert *)ele;
143  ele_verts[side] = BLI_array_alloca(ele_verts[side], 1);
144 
145  ele_verts[side][j++] = v;
146  }
147  else {
148  BLI_assert(0);
149  }
150  ele_verts_len[side] = j;
151  }
152 
153  int *depths[2] = {NULL};
154  int pass = 0;
155 
156  BMVert **stack = MEM_mallocN(sizeof(*stack) * bm->totvert, __func__);
157  BMVert **stack_other = MEM_mallocN(sizeof(*stack_other) * bm->totvert, __func__);
158 
159  STACK_DECLARE(stack);
160  STACK_INIT(stack, bm->totvert);
161 
162  STACK_DECLARE(stack_other);
163  STACK_INIT(stack_other, bm->totvert);
164 
166 
167  /* After exhausting all possible elements, we should have found all elements on the 'side_other'.
168  * otherwise, exit early. */
169  bool found_all = false;
170 
171  for (int side = 0; side < 2; side++) {
172  const int side_other = !side;
173 
174  /* initialize depths to -1 (un-touched), fill in with the depth as we walk over the edges. */
175  depths[side] = MEM_mallocN(sizeof(*depths[side]) * bm->totvert, __func__);
176  copy_vn_i(depths[side], bm->totvert, -1);
177 
178  /* needed for second side */
179  STACK_CLEAR(stack);
180  STACK_CLEAR(stack_other);
181 
182  for (int i = 0; i < ele_verts_len[side]; i++) {
183  BMVert *v = ele_verts[side][i];
184  depths[side][BM_elem_index_get(v)] = 0;
185  if (v->e && !BM_elem_flag_test(v, BM_ELEM_TAG)) {
186  STACK_PUSH(stack, v);
187  }
188  }
189 
190 #ifdef USE_EDGE_CHAIN
191  /* Expand initial state to end-point vertices when they only have 2x edges,
192  * this prevents odd behavior when source or destination are in the middle
193  * of a long chain of edges. */
194  if (ELEM(path_htype, BM_VERT, BM_EDGE)) {
195  for (int i = 0; i < ele_verts_len[side]; i++) {
196  BMVert *v = ele_verts[side][i];
197  BMVert *v_end_pair[2];
198  if (BM_vert_is_edge_pair_manifold(v) && bm_vert_pair_ends(v, v_end_pair)) {
199  for (int j = 0; j < 2; j++) {
200  const int v_end_index = BM_elem_index_get(v_end_pair[j]);
201  if (depths[side][v_end_index] == -1) {
202  depths[side][v_end_index] = 0;
203  if (!BM_elem_flag_test(v_end_pair[j], BM_ELEM_TAG)) {
204  STACK_PUSH(stack, v_end_pair[j]);
205  }
206  }
207  }
208  }
209  }
210  }
211 #endif /* USE_EDGE_CHAIN */
212 
213  /* Keep walking over connected geometry until we find all the vertices in
214  * `ele_verts[side_other]`, or exit the loop when there's no connection. */
215  found_all = false;
216  for (pass = 1; (STACK_SIZE(stack) != 0); pass++) {
217  while (STACK_SIZE(stack) != 0) {
218  BMVert *v_a = STACK_POP(stack);
219  // const int v_a_index = BM_elem_index_get(v_a); /* only for assert */
220  BMEdge *e = v_a->e;
221 
222  do {
223  BMVert *v_b = BM_edge_other_vert(e, v_a);
224  int v_b_index = BM_elem_index_get(v_b);
225  if (depths[side][v_b_index] == -1) {
226 
227 #ifdef USE_EDGE_CHAIN
228  /* Walk along the chain, fill in values until we reach a vertex with 3+ edges. */
229  {
230  BMEdge *e_chain = e;
231  while (BM_vert_is_edge_pair_manifold(v_b) && ((depths[side][v_b_index] == -1))) {
232  depths[side][v_b_index] = pass;
233 
234  BMEdge *e_chain_next = BM_DISK_EDGE_NEXT(e_chain, v_b);
235  BLI_assert(BM_DISK_EDGE_NEXT(e_chain_next, v_b) == e_chain);
236  v_b = BM_edge_other_vert(e_chain_next, v_b);
237  v_b_index = BM_elem_index_get(v_b);
238  e_chain = e_chain_next;
239  }
240  }
241 #endif /* USE_EDGE_CHAIN */
242 
243  /* Add the other vertex to the stack, to be traversed in the next pass. */
244  if (depths[side][v_b_index] == -1) {
245 #ifdef USE_EDGE_CHAIN
247 #endif
248  BLI_assert(pass == depths[side][BM_elem_index_get(v_a)] + 1);
249  depths[side][v_b_index] = pass;
250  if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
251  STACK_PUSH(stack_other, v_b);
252  }
253  }
254  }
255  } while ((e = BM_DISK_EDGE_NEXT(e, v_a)) != v_a->e);
256  }
257 
258  /* Stop searching once there's none left.
259  * Note that this looks in-efficient, however until the target elements reached,
260  * it will exit immediately.
261  * After that, it takes as many passes as the element has edges to finish off. */
262  found_all = true;
263  for (int i = 0; i < ele_verts_len[side_other]; i++) {
264  if (depths[side][BM_elem_index_get(ele_verts[side_other][i])] == -1) {
265  found_all = false;
266  break;
267  }
268  }
269  if (found_all == true) {
270  pass++;
271  break;
272  }
273 
274  STACK_SWAP(stack, stack_other);
275  }
276 
277  /* if we have nothing left, and didn't find all elements on the other side,
278  * exit early and don't continue */
279  if (found_all == false) {
280  break;
281  }
282  }
283 
284  MEM_freeN(stack);
285  MEM_freeN(stack_other);
286 
287  /* Now we have depths recorded from both sides,
288  * select elements that use tagged verts. */
289  LinkNode *path = NULL;
290 
291  if (found_all == false) {
292  /* fail! (do nothing) */
293  }
294  else if (path_htype == BM_FACE) {
295  BMIter fiter;
296  BMFace *f;
297 
298  BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
299  if (!BM_elem_flag_test(f, BM_ELEM_TAG)) {
300  /* check all verts in face are tagged */
301  BMLoop *l_first, *l_iter;
302  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
303  bool ok = true;
304 #if 0
305  do {
306  if (!bm_vert_region_test_chain(l_iter->v, depths, pass)) {
307  ok = false;
308  break;
309  }
310  } while ((l_iter = l_iter->next) != l_first);
311 #else
312  /* Allowing a single failure on a face gives fewer 'gaps'.
313  * While correct, in practice they're often part of what
314  * a user would consider the 'region'. */
315  int ok_tests = f->len > 3 ? 1 : 0; /* how many times we may fail */
316  do {
317  if (!bm_vert_region_test_chain(l_iter->v, depths, pass)) {
318  if (ok_tests == 0) {
319  ok = false;
320  break;
321  }
322  ok_tests--;
323  }
324  } while ((l_iter = l_iter->next) != l_first);
325 #endif
326 
327  if (ok) {
328  BLI_linklist_prepend(&path, f);
329  }
330  }
331  }
332  }
333  else if (path_htype == BM_EDGE) {
334  BMIter eiter;
335  BMEdge *e;
336 
337  BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
339  /* check all verts in edge are tagged */
340  bool ok = true;
341  for (int j = 0; j < 2; j++) {
342  if (!bm_vert_region_test_chain(*((&e->v1) + j), depths, pass)) {
343  ok = false;
344  break;
345  }
346  }
347 
348  if (ok) {
349  BLI_linklist_prepend(&path, e);
350  }
351  }
352  }
353  }
354  else if (path_htype == BM_VERT) {
355  BMIter viter;
356  BMVert *v;
357 
358  BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
359  if (bm_vert_region_test_chain(v, depths, pass)) {
360  BLI_linklist_prepend(&path, v);
361  }
362  }
363  }
364 
365  for (int side = 0; side < 2; side++) {
366  if (depths[side]) {
367  MEM_freeN(depths[side]);
368  }
369  }
370 
371  return path;
372 }
373 
374 #undef USE_EDGE_CHAIN
375 
376 /* -------------------------------------------------------------------- */
381  BMElem *ele_src,
382  BMElem *ele_dst,
383  bool (*filter_fn)(BMVert *, void *user_data),
384  void *user_data)
385 {
386  LinkNode *path = NULL;
387  /* BM_ELEM_TAG flag is used to store visited verts */
388  BMVert *v;
389  BMIter viter;
390  int i;
391 
392  BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
393  BM_elem_flag_set(v, BM_ELEM_TAG, !filter_fn(v, user_data));
394  BM_elem_index_set(v, i); /* set_inline */
395  }
397 
398  path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_VERT);
399 
400  return path;
401 }
402 
404  BMElem *ele_src,
405  BMElem *ele_dst,
406  bool (*filter_fn)(BMEdge *, void *user_data),
407  void *user_data)
408 {
409  LinkNode *path = NULL;
410  /* BM_ELEM_TAG flag is used to store visited verts */
411  BMEdge *e;
412  BMIter eiter;
413  int i;
414 
415  /* flush flag to verts */
417 
418  BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
419  bool test;
420  BM_elem_flag_set(e, BM_ELEM_TAG, test = !filter_fn(e, user_data));
421 
422  /* flush tag to verts */
423  if (test == false) {
424  for (int j = 0; j < 2; j++) {
425  BM_elem_flag_disable(*((&e->v1) + j), BM_ELEM_TAG);
426  }
427  }
428  }
429 
430  path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_EDGE);
431 
432  return path;
433 }
434 
436  BMElem *ele_src,
437  BMElem *ele_dst,
438  bool (*filter_fn)(BMFace *, void *user_data),
439  void *user_data)
440 {
441  LinkNode *path = NULL;
442  /* BM_ELEM_TAG flag is used to store visited verts */
443  BMFace *f;
444  BMIter fiter;
445  int i;
446 
447  /* flush flag to verts */
449 
450  BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
451  bool test;
452  BM_elem_flag_set(f, BM_ELEM_TAG, test = !filter_fn(f, user_data));
453 
454  /* flush tag to verts */
455  if (test == false) {
456  BMLoop *l_first, *l_iter;
457  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
458  do {
460  } while ((l_iter = l_iter->next) != l_first);
461  }
462  }
463 
464  path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_FACE);
465 
466  return path;
467 }
468 
#define BLI_array_alloca(arr, realsize)
Definition: BLI_alloca.h:22
#define BLI_assert(a)
Definition: BLI_assert.h:46
void copy_vn_i(int *array_tar, int size, int val)
Definition: math_vector.c:1223
#define ELEM(...)
#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 Guarded memory(de)allocation.
#define BM_DISK_EDGE_NEXT(e, v)
Definition: bmesh_class.h:625
#define BM_FACE_FIRST_LOOP(p)
Definition: bmesh_class.h:622
@ BM_FACE
Definition: bmesh_class.h:386
@ BM_VERT
Definition: bmesh_class.h:383
@ BM_EDGE
Definition: bmesh_class.h:384
@ BM_ELEM_TAG
Definition: bmesh_class.h:484
#define BM_elem_index_get(ele)
Definition: bmesh_inline.h:110
#define BM_elem_flag_disable(ele, hflag)
Definition: bmesh_inline.h:15
#define BM_elem_flag_set(ele, hflag, val)
Definition: bmesh_inline.h:16
#define BM_elem_index_set(ele, index)
Definition: bmesh_inline.h:111
#define BM_elem_flag_test(ele, hflag)
Definition: bmesh_inline.h:12
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
@ BM_EDGES_OF_MESH
@ BM_VERTS_OF_MESH
@ BM_FACES_OF_MESH
ATTR_WARN_UNUSED_RESULT BMesh * bm
void BM_mesh_elem_hflag_enable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
Definition: bmesh_mesh.cc:446
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 bool bm_vert_region_test_chain(BMVert *v, int *const depths[2], const int pass)
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)
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)
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)
static LinkNode * mesh_calc_path_region_elem(BMesh *bm, BMElem *ele_src, BMElem *ele_dst, const char path_htype)
bool BM_vert_is_edge_pair_manifold(const BMVert *v)
Definition: bmesh_query.c:578
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
void * user_data
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
BMHeader head
Definition: bmesh_class.h:243
int len
Definition: bmesh_class.h:267
char htype
Definition: bmesh_class.h:64
struct BMVert * v
Definition: bmesh_class.h:153
struct BMLoop * next
Definition: bmesh_class.h:233
struct BMEdge * e
Definition: bmesh_class.h:97
int totvert
Definition: bmesh_class.h:297
char elem_index_dirty
Definition: bmesh_class.h:305