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