Blender  V3.3
bmesh_edgeloop.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2013 by Campbell Barton. All rights reserved. */
3 
10 #include "MEM_guardedalloc.h"
11 
12 #include "BLI_listbase.h"
13 #include "BLI_math_vector.h"
14 #include "BLI_mempool.h"
15 #include "BLI_stack.h"
16 #include "BLI_utildefines_iter.h"
17 
18 #include "bmesh.h"
19 
20 #include "bmesh_edgeloop.h" /* own include */
21 
22 typedef struct BMEdgeLoopStore {
25  int flag;
26  int len;
27  /* optional values to calc */
28  float co[3], no[3];
30 
31 #define BM_EDGELOOP_IS_CLOSED (1 << 0)
32 
33 /* Use a small value since we need normals even for very small loops. */
34 #define EDGELOOP_EPS 1e-10f
35 
36 /* -------------------------------------------------------------------- */
37 /* BM_mesh_edgeloops_find & Util Functions. */
38 
39 static int bm_vert_other_tag(BMVert *v, BMVert *v_prev, BMEdge **r_e)
40 {
41  BMIter iter;
42  BMEdge *e, *e_next = NULL;
43  uint count = 0;
44 
45  BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
47  BMVert *v_other = BM_edge_other_vert(e, v);
48  if (v_other != v_prev) {
49  e_next = e;
50  count++;
51  }
52  }
53  }
54 
55  *r_e = e_next;
56  return count;
57 }
58 
62 static bool bm_loop_build(BMEdgeLoopStore *el_store, BMVert *v_prev, BMVert *v, int dir)
63 {
64  void (*add_fn)(ListBase *, void *) = dir == 1 ? BLI_addhead : BLI_addtail;
65  BMEdge *e_next;
66  BMVert *v_next;
67  BMVert *v_first = v;
68 
69  BLI_assert(abs(dir) == 1);
70 
72  return true;
73  }
74 
75  while (v) {
76  LinkData *node = MEM_callocN(sizeof(*node), __func__);
77  int count;
78  node->data = v;
79  add_fn(&el_store->verts, node);
80  el_store->len++;
82 
83  count = bm_vert_other_tag(v, v_prev, &e_next);
84  if (count == 1) {
85  v_next = BM_edge_other_vert(e_next, v);
87  if (UNLIKELY(v_next == v_first)) {
88  el_store->flag |= BM_EDGELOOP_IS_CLOSED;
89  v_next = NULL;
90  }
91  }
92  else if (count == 0) {
93  /* pass */
94  v_next = NULL;
95  }
96  else {
97  v_next = NULL;
98  return false;
99  }
100 
101  v_prev = v;
102  v = v_next;
103  }
104 
105  return true;
106 }
107 
109  ListBase *r_eloops,
110  bool (*test_fn)(BMEdge *, void *user_data),
111  void *user_data)
112 {
113  BMIter iter;
114  BMEdge *e;
115  BMVert *v;
116  int count = 0;
117 
118  BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
120  }
121 
122  /* first flush edges to tags, and tag verts */
123  BLI_Stack *edge_stack = BLI_stack_new(sizeof(BMEdge *), __func__);
124  BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
126  if (test_fn(e, user_data)) {
130  BLI_stack_push(edge_stack, (void *)&e);
131  }
132  else {
134  }
135  }
136 
137  const uint edges_len = BLI_stack_count(edge_stack);
138  BMEdge **edges = MEM_mallocN(sizeof(*edges) * edges_len, __func__);
139  BLI_stack_pop_n_reverse(edge_stack, edges, BLI_stack_count(edge_stack));
140  BLI_stack_free(edge_stack);
141 
142  for (uint i = 0; i < edges_len; i += 1) {
143  e = edges[i];
145  BMEdgeLoopStore *el_store = MEM_callocN(sizeof(BMEdgeLoopStore), __func__);
146 
147  /* add both directions */
148  if (bm_loop_build(el_store, e->v1, e->v2, 1) && bm_loop_build(el_store, e->v2, e->v1, -1) &&
149  el_store->len > 1) {
150  BLI_addtail(r_eloops, el_store);
151  count++;
152  }
153  else {
154  BM_edgeloop_free(el_store);
155  }
156  }
157  }
158 
159  for (uint i = 0; i < edges_len; i += 1) {
160  e = edges[i];
164  }
165 
166  MEM_freeN(edges);
167  return count;
168 }
169 
170 /* -------------------------------------------------------------------- */
171 /* BM_mesh_edgeloops_find_path & Util Functions. */
172 
177 struct VertStep {
178  struct VertStep *next, *prev;
180 };
181 
182 static void vs_add(
183  BLI_mempool *vs_pool, ListBase *lb, BMVert *v, BMEdge *e_prev, const int iter_tot)
184 {
185  struct VertStep *vs_new = BLI_mempool_alloc(vs_pool);
186  vs_new->v = v;
187 
188  BM_elem_index_set(v, iter_tot); /* set_dirty */
189 
190  /* This edge stores a direct path back to the original vertex so we can
191  * backtrack without having to store an array of previous verts. */
192 
193  /* WARNING: Setting the edge is not common practice but currently harmless, take care. */
194  BLI_assert(BM_vert_in_edge(e_prev, v));
195  v->e = e_prev;
196 
197  BLI_addtail(lb, vs_new);
198 }
199 
201  ListBase *lb,
202  const int dir,
203  BMVert *v_match[2])
204 {
205  ListBase lb_tmp = {NULL, NULL};
206  struct VertStep *vs, *vs_next;
207  BLI_assert(abs(dir) == 1);
208 
209  for (vs = lb->first; vs; vs = vs_next) {
210  BMIter iter;
211  BMEdge *e;
212  /* these values will be the same every iteration */
213  const int vs_iter_tot = BM_elem_index_get(vs->v);
214  const int vs_iter_next = vs_iter_tot + dir;
215 
216  vs_next = vs->next;
217 
218  BM_ITER_ELEM (e, &iter, vs->v, BM_EDGES_OF_VERT) {
220  BMVert *v_next = BM_edge_other_vert(e, vs->v);
221  const int v_next_index = BM_elem_index_get(v_next);
222  /* not essential to clear flag but prevents more checking next time round */
224  if (v_next_index == 0) {
225  vs_add(vs_pool, &lb_tmp, v_next, e, vs_iter_next);
226  }
227  else if ((dir < 0) == (v_next_index < 0)) {
228  /* on the same side - do nothing */
229  }
230  else {
231  /* we have met out match! (vertices from different sides meet) */
232  if (dir == 1) {
233  v_match[0] = vs->v;
234  v_match[1] = v_next;
235  }
236  else {
237  v_match[0] = v_next;
238  v_match[1] = vs->v;
239  }
240  /* normally we would manage memory of remaining items in (lb, lb_tmp),
241  * but search is done, vs_pool will get destroyed immediately */
242  return true;
243  }
244  }
245  }
246 
247  BLI_mempool_free(vs_pool, vs);
248  }
249 
250  /* Commented because used in a loop, and this flag has already been set. */
251  /* bm->elem_index_dirty |= BM_VERT; */
252 
253  /* lb is now full of free'd items, overwrite */
254  *lb = lb_tmp;
255 
256  return (BLI_listbase_is_empty(lb) == false);
257 }
258 
260  ListBase *r_eloops,
261  bool (*test_fn)(BMEdge *, void *user_data),
262  void *user_data,
263  BMVert *v_src,
264  BMVert *v_dst)
265 {
266  BMIter iter;
267  BMEdge *e;
268  bool found = false;
269 
270  BLI_assert(v_src != v_dst);
271 
272  {
273  BMVert *v;
274  BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
275  BM_elem_index_set(v, 0);
277  }
278  }
280 
281  /* first flush edges to tags, and tag verts */
282  int edges_len;
283  BMEdge **edges;
284 
285  if (test_fn) {
286  BLI_Stack *edge_stack = BLI_stack_new(sizeof(BMEdge *), __func__);
287  BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
288  if (test_fn(e, user_data)) {
292  BLI_stack_push(edge_stack, (void *)&e);
293  }
294  else {
296  }
297  }
298  edges_len = BLI_stack_count(edge_stack);
299  edges = MEM_mallocN(sizeof(*edges) * edges_len, __func__);
300  BLI_stack_pop_n_reverse(edge_stack, edges, BLI_stack_count(edge_stack));
301  BLI_stack_free(edge_stack);
302  }
303  else {
304  int i = 0;
305  edges_len = bm->totedge;
306  edges = MEM_mallocN(sizeof(*edges) * edges_len, __func__);
307 
308  BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
312  edges[i] = e;
313  }
314  }
315 
316  /* prime the lists and begin search */
317  {
318  BMVert *v_match[2] = {NULL, NULL};
319  ListBase lb_src = {NULL, NULL};
320  ListBase lb_dst = {NULL, NULL};
321  BLI_mempool *vs_pool = BLI_mempool_create(sizeof(struct VertStep), 0, 512, BLI_MEMPOOL_NOP);
322 
323  /* edge args are dummy */
324  vs_add(vs_pool, &lb_src, v_src, v_src->e, 1);
325  vs_add(vs_pool, &lb_dst, v_dst, v_dst->e, -1);
327 
328  do {
329  if ((bm_loop_path_build_step(vs_pool, &lb_src, 1, v_match) == false) || v_match[0]) {
330  break;
331  }
332  if ((bm_loop_path_build_step(vs_pool, &lb_dst, -1, v_match) == false) || v_match[0]) {
333  break;
334  }
335  } while (true);
336 
337  BLI_mempool_destroy(vs_pool);
338 
339  if (v_match[0]) {
340  BMEdgeLoopStore *el_store = MEM_callocN(sizeof(BMEdgeLoopStore), __func__);
341  BMVert *v;
342 
343  /* build loop from edge pointers */
344  v = v_match[0];
345  while (true) {
346  LinkData *node = MEM_callocN(sizeof(*node), __func__);
347  node->data = v;
348  BLI_addhead(&el_store->verts, node);
349  el_store->len++;
350  if (v == v_src) {
351  break;
352  }
353  v = BM_edge_other_vert(v->e, v);
354  }
355 
356  v = v_match[1];
357  while (true) {
358  LinkData *node = MEM_callocN(sizeof(*node), __func__);
359  node->data = v;
360  BLI_addtail(&el_store->verts, node);
361  el_store->len++;
362  if (v == v_dst) {
363  break;
364  }
365  v = BM_edge_other_vert(v->e, v);
366  }
367 
368  BLI_addtail(r_eloops, el_store);
369 
370  found = true;
371  }
372  }
373 
374  for (uint i = 0; i < edges_len; i += 1) {
375  e = edges[i];
379  }
380  MEM_freeN(edges);
381 
382  return found;
383 }
384 
385 /* -------------------------------------------------------------------- */
386 /* BM_mesh_edgeloops_xxx utility function */
387 
389 {
390  BMEdgeLoopStore *el_store;
391  while ((el_store = BLI_pophead(eloops))) {
392  BM_edgeloop_free(el_store);
393  }
394 }
395 
397 {
398  BMEdgeLoopStore *el_store;
399  for (el_store = eloops->first; el_store; el_store = el_store->next) {
400  BM_edgeloop_calc_center(bm, el_store);
401  }
402 }
403 
405 {
406  BMEdgeLoopStore *el_store;
407  for (el_store = eloops->first; el_store; el_store = el_store->next) {
408  BM_edgeloop_calc_normal(bm, el_store);
409  }
410 }
411 
412 void BM_mesh_edgeloops_calc_normal_aligned(BMesh *bm, ListBase *eloops, const float no_align[3])
413 {
414  BMEdgeLoopStore *el_store;
415  for (el_store = eloops->first; el_store; el_store = el_store->next) {
416  BM_edgeloop_calc_normal_aligned(bm, el_store, no_align);
417  }
418 }
419 
420 void BM_mesh_edgeloops_calc_order(BMesh *UNUSED(bm), ListBase *eloops, const bool use_normals)
421 {
422  ListBase eloops_ordered = {NULL};
423  BMEdgeLoopStore *el_store;
424  float cent[3];
425  int tot = 0;
426  zero_v3(cent);
427  /* assumes we calculated centers already */
428  for (el_store = eloops->first; el_store; el_store = el_store->next, tot++) {
429  add_v3_v3(cent, el_store->co);
430  }
431  mul_v3_fl(cent, 1.0f / (float)tot);
432 
433  /* Find the furthest out loop. */
434  {
435  BMEdgeLoopStore *el_store_best = NULL;
436  float len_best_sq = -1.0f;
437  for (el_store = eloops->first; el_store; el_store = el_store->next) {
438  const float len_sq = len_squared_v3v3(cent, el_store->co);
439  if (len_sq > len_best_sq) {
440  len_best_sq = len_sq;
441  el_store_best = el_store;
442  }
443  }
444 
445  BLI_remlink(eloops, el_store_best);
446  BLI_addtail(&eloops_ordered, el_store_best);
447  }
448 
449  /* not so efficient re-ordering */
450  while (eloops->first) {
451  BMEdgeLoopStore *el_store_best = NULL;
452  const float *co = ((BMEdgeLoopStore *)eloops_ordered.last)->co;
453  const float *no = ((BMEdgeLoopStore *)eloops_ordered.last)->no;
454  float len_best_sq = FLT_MAX;
455 
456  if (use_normals) {
457  BLI_ASSERT_UNIT_V3(no);
458  }
459 
460  for (el_store = eloops->first; el_store; el_store = el_store->next) {
461  float len_sq;
462  if (use_normals) {
463  /* Scale the length by how close the loops are to pointing at each other. */
464  float dir[3];
465  sub_v3_v3v3(dir, co, el_store->co);
466  len_sq = normalize_v3(dir);
467  len_sq = len_sq *
468  ((1.0f - fabsf(dot_v3v3(dir, no))) + (1.0f - fabsf(dot_v3v3(dir, el_store->no))));
469  }
470  else {
471  len_sq = len_squared_v3v3(co, el_store->co);
472  }
473 
474  if (len_sq < len_best_sq) {
475  len_best_sq = len_sq;
476  el_store_best = el_store;
477  }
478  }
479 
480  BLI_remlink(eloops, el_store_best);
481  BLI_addtail(&eloops_ordered, el_store_best);
482  }
483 
484  *eloops = eloops_ordered;
485 }
486 
487 /* -------------------------------------------------------------------- */
488 /* BM_edgeloop_*** functions */
489 
491 {
492  BMEdgeLoopStore *el_store_copy = MEM_mallocN(sizeof(*el_store), __func__);
493  *el_store_copy = *el_store;
494  BLI_duplicatelist(&el_store_copy->verts, &el_store->verts);
495  return el_store_copy;
496 }
497 
498 BMEdgeLoopStore *BM_edgeloop_from_verts(BMVert **v_arr, const int v_arr_tot, bool is_closed)
499 {
500  BMEdgeLoopStore *el_store = MEM_callocN(sizeof(*el_store), __func__);
501  int i;
502  for (i = 0; i < v_arr_tot; i++) {
503  LinkData *node = MEM_callocN(sizeof(*node), __func__);
504  node->data = v_arr[i];
505  BLI_addtail(&el_store->verts, node);
506  }
507  el_store->len = v_arr_tot;
508  if (is_closed) {
509  el_store->flag |= BM_EDGELOOP_IS_CLOSED;
510  }
511  return el_store;
512 }
513 
515 {
516  BLI_freelistN(&el_store->verts);
517  MEM_freeN(el_store);
518 }
519 
521 {
522  return (el_store->flag & BM_EDGELOOP_IS_CLOSED) != 0;
523 }
524 
526 {
527  return &el_store->verts;
528 }
529 
531 {
532  return el_store->len;
533 }
534 
535 const float *BM_edgeloop_normal_get(struct BMEdgeLoopStore *el_store)
536 {
537  return el_store->no;
538 }
539 
540 const float *BM_edgeloop_center_get(struct BMEdgeLoopStore *el_store)
541 {
542  return el_store->co;
543 }
544 
545 #define NODE_AS_V(n) ((BMVert *)((LinkData *)n)->data)
546 #define NODE_AS_CO(n) ((BMVert *)((LinkData *)n)->data)->co
547 
548 void BM_edgeloop_edges_get(struct BMEdgeLoopStore *el_store, BMEdge **e_arr)
549 {
550  LinkData *node;
551  int i = 0;
552  for (node = el_store->verts.first; node && node->next; node = node->next) {
553  e_arr[i++] = BM_edge_exists(NODE_AS_V(node), NODE_AS_V(node->next));
554  BLI_assert(e_arr[i - 1] != NULL);
555  }
556 
557  if (el_store->flag & BM_EDGELOOP_IS_CLOSED) {
558  e_arr[i] = BM_edge_exists(NODE_AS_V(el_store->verts.first), NODE_AS_V(el_store->verts.last));
559  BLI_assert(e_arr[i] != NULL);
560  }
561  BLI_assert(el_store->len == i + 1);
562 }
563 
565 {
566  LinkData *node_curr = el_store->verts.last;
567  LinkData *node_prev = ((LinkData *)el_store->verts.last)->prev;
568  LinkData *node_first = el_store->verts.first;
569  LinkData *node_next = node_first;
570 
571  const float *v_prev = NODE_AS_CO(node_prev);
572  const float *v_curr = NODE_AS_CO(node_curr);
573  const float *v_next = NODE_AS_CO(node_next);
574 
575  float totw = 0.0f;
576  float w_prev;
577 
578  zero_v3(el_store->co);
579 
580  w_prev = len_v3v3(v_prev, v_curr);
581  do {
582  const float w_curr = len_v3v3(v_curr, v_next);
583  const float w = (w_curr + w_prev);
584  madd_v3_v3fl(el_store->co, v_curr, w);
585  totw += w;
586  w_prev = w_curr;
587 
588  node_prev = node_curr;
589  node_curr = node_next;
590  node_next = node_next->next;
591 
592  if (node_next == NULL) {
593  break;
594  }
595  v_prev = v_curr;
596  v_curr = v_next;
597  v_next = NODE_AS_CO(node_next);
598  } while (1);
599 
600  if (totw != 0.0f) {
601  mul_v3_fl(el_store->co, 1.0f / (float)totw);
602  }
603 }
604 
606 {
607  LinkData *node_curr = el_store->verts.first;
608  const float *v_prev = NODE_AS_CO(el_store->verts.last);
609  const float *v_curr = NODE_AS_CO(node_curr);
610 
611  zero_v3(el_store->no);
612 
613  /* Newell's Method */
614  do {
615  add_newell_cross_v3_v3v3(el_store->no, v_prev, v_curr);
616 
617  if ((node_curr = node_curr->next)) {
618  v_prev = v_curr;
619  v_curr = NODE_AS_CO(node_curr);
620  }
621  else {
622  break;
623  }
624  } while (true);
625 
626  if (UNLIKELY(normalize_v3(el_store->no) < EDGELOOP_EPS)) {
627  el_store->no[2] = 1.0f; /* other axis set to 0.0 */
628  return false;
629  }
630  return true;
631 }
632 
634  BMEdgeLoopStore *el_store,
635  const float no_align[3])
636 {
637  LinkData *node_curr = el_store->verts.first;
638  const float *v_prev = NODE_AS_CO(el_store->verts.last);
639  const float *v_curr = NODE_AS_CO(node_curr);
640 
641  zero_v3(el_store->no);
642 
643  /* Own Method */
644  do {
645  float cross[3], no[3], dir[3];
646  sub_v3_v3v3(dir, v_curr, v_prev);
647  cross_v3_v3v3(cross, no_align, dir);
648  cross_v3_v3v3(no, dir, cross);
649  add_v3_v3(el_store->no, no);
650 
651  if ((node_curr = node_curr->next)) {
652  v_prev = v_curr;
653  v_curr = NODE_AS_CO(node_curr);
654  }
655  else {
656  break;
657  }
658  } while (true);
659 
660  if (UNLIKELY(normalize_v3(el_store->no) < EDGELOOP_EPS)) {
661  el_store->no[2] = 1.0f; /* other axis set to 0.0 */
662  return false;
663  }
664  return true;
665 }
666 
668 {
669  negate_v3(el_store->no);
670  BLI_listbase_reverse(&el_store->verts);
671 }
672 
674  BMesh *bm, BMEdgeLoopStore *el_store, int el_store_len, bool split, GSet *split_edges)
675 {
676  bool split_swap = true;
677 
678 #define EDGE_SPLIT(node_copy, node_other) \
679  { \
680  BMVert *v_split, *v_other = (node_other)->data; \
681  BMEdge *e_split, *e_other = BM_edge_exists((node_copy)->data, v_other); \
682  v_split = BM_edge_split( \
683  bm, e_other, split_swap ? (node_copy)->data : v_other, &e_split, 0.0f); \
684  v_split->e = e_split; \
685  BLI_assert(v_split == e_split->v2); \
686  BLI_gset_insert(split_edges, e_split); \
687  (node_copy)->data = v_split; \
688  } \
689  ((void)0)
690 
691  /* first double until we are more than half as big */
692  while ((el_store->len * 2) < el_store_len) {
693  LinkData *node_curr = el_store->verts.first;
694  while (node_curr) {
695  LinkData *node_curr_copy = MEM_dupallocN(node_curr);
696  if (split == false) {
697  BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
698  node_curr = node_curr_copy->next;
699  }
700  else {
701  if (node_curr->next || (el_store->flag & BM_EDGELOOP_IS_CLOSED)) {
702  EDGE_SPLIT(node_curr_copy,
703  node_curr->next ? node_curr->next : (LinkData *)el_store->verts.first);
704  BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
705  node_curr = node_curr_copy->next;
706  }
707  else {
708  EDGE_SPLIT(node_curr_copy, node_curr->prev);
709  BLI_insertlinkbefore(&el_store->verts, node_curr, node_curr_copy);
710  node_curr = node_curr->next;
711  }
712  split_swap = !split_swap;
713  }
714  el_store->len++;
715  }
716  split_swap = !split_swap;
717  }
718 
719  if (el_store->len < el_store_len) {
720  LinkData *node_curr = el_store->verts.first;
721 
722  int iter_prev = 0;
723  BLI_FOREACH_SPARSE_RANGE (el_store->len, (el_store_len - el_store->len), iter) {
724  while (iter_prev < iter) {
725  node_curr = node_curr->next;
726  iter_prev += 1;
727  }
728 
729  LinkData *node_curr_copy;
730  node_curr_copy = MEM_dupallocN(node_curr);
731  if (split == false) {
732  BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
733  node_curr = node_curr_copy->next;
734  }
735  else {
736  if (node_curr->next || (el_store->flag & BM_EDGELOOP_IS_CLOSED)) {
737  EDGE_SPLIT(node_curr_copy,
738  node_curr->next ? node_curr->next : (LinkData *)el_store->verts.first);
739  BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
740  node_curr = node_curr_copy->next;
741  }
742  else {
743  EDGE_SPLIT(node_curr_copy, node_curr->prev);
744  BLI_insertlinkbefore(&el_store->verts, node_curr, node_curr_copy);
745  node_curr = node_curr->next;
746  }
747  split_swap = !split_swap;
748  }
749  el_store->len++;
750  iter_prev += 1;
751  }
752  }
753 
754 #undef BKE_FOREACH_SUBSET_OF_RANGE
755 #undef EDGE_SPLIT
756 
757  BLI_assert(el_store->len == el_store_len);
758 }
759 
761  struct BMEdgeLoopStore *el_store_b)
762 {
763  LinkData *node;
764 
765  /* A little more efficient if 'a' as smaller. */
766  if (el_store_a->len > el_store_b->len) {
767  SWAP(BMEdgeLoopStore *, el_store_a, el_store_b);
768  }
769 
770  /* init */
771  for (node = el_store_a->verts.first; node; node = node->next) {
773  }
774  for (node = el_store_b->verts.first; node; node = node->next) {
776  }
777 
778  /* Check 'a' (clear as we go). */
779  for (node = el_store_a->verts.first; node; node = node->next) {
781  /* Finish clearing 'a', leave tag clean. */
782  while ((node = node->next)) {
784  }
785  return true;
786  }
788  }
789  return false;
790 }
#define BLI_assert(a)
Definition: BLI_assert.h:46
struct GSet GSet
Definition: BLI_ghash.h:340
BLI_INLINE bool BLI_listbase_is_empty(const struct ListBase *lb)
Definition: BLI_listbase.h:269
void * BLI_pophead(ListBase *listbase) ATTR_NONNULL(1)
Definition: listbase.c:221
void BLI_addhead(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:60
void void void void void BLI_duplicatelist(struct ListBase *dst, const struct ListBase *src) ATTR_NONNULL(1
void BLI_insertlinkafter(struct ListBase *listbase, void *vprevlink, void *vnewlink) ATTR_NONNULL(1)
Definition: listbase.c:301
void void BLI_freelistN(struct ListBase *listbase) ATTR_NONNULL(1)
Definition: listbase.c:466
void BLI_addtail(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:80
void BLI_remlink(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:100
void BLI_insertlinkbefore(struct ListBase *listbase, void *vnextlink, void *vnewlink) ATTR_NONNULL(1)
Definition: listbase.c:340
void void void void void void BLI_listbase_reverse(struct ListBase *lb) ATTR_NONNULL(1)
Definition: listbase.c:797
#define BLI_ASSERT_UNIT_V3(v)
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void madd_v3_v3fl(float r[3], const float a[3], float f)
MINLINE float normalize_v3(float r[3])
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void mul_v3_fl(float r[3], float f)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void negate_v3(float r[3])
MINLINE void zero_v3(float r[3])
MINLINE void add_v3_v3(float r[3], const float a[3])
@ BLI_MEMPOOL_NOP
Definition: BLI_mempool.h:99
void BLI_mempool_free(BLI_mempool *pool, void *addr) ATTR_NONNULL(1
BLI_mempool * BLI_mempool_create(unsigned int esize, unsigned int elem_num, unsigned int pchunk, unsigned int flag) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL
Definition: BLI_mempool.c:253
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
Definition: BLI_mempool.c:319
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
Definition: BLI_mempool.c:707
void BLI_stack_pop_n_reverse(BLI_Stack *stack, void *dst, unsigned int n) ATTR_NONNULL()
Definition: stack.c:154
size_t BLI_stack_count(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition: stack.c:225
void BLI_stack_push(BLI_Stack *stack, const void *src) ATTR_NONNULL()
Definition: stack.c:129
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
Definition: stack.c:94
#define BLI_stack_new(esize, descr)
unsigned int uint
Definition: BLI_sys_types.h:67
#define SWAP(type, a, b)
#define UNUSED(x)
#define UNLIKELY(x)
#define BLI_FOREACH_SPARSE_RANGE(src, dst, i)
Read Guarded memory(de)allocation.
@ BM_VERT
Definition: bmesh_class.h:383
@ BM_ELEM_INTERNAL_TAG
Definition: bmesh_class.h:496
#define BM_EDGELOOP_IS_CLOSED
BMEdgeLoopStore * BM_edgeloop_copy(BMEdgeLoopStore *el_store)
struct BMEdgeLoopStore BMEdgeLoopStore
const float * BM_edgeloop_center_get(struct BMEdgeLoopStore *el_store)
static bool bm_loop_path_build_step(BLI_mempool *vs_pool, ListBase *lb, const int dir, BMVert *v_match[2])
#define NODE_AS_CO(n)
void BM_edgeloop_expand(BMesh *bm, BMEdgeLoopStore *el_store, int el_store_len, bool split, GSet *split_edges)
void BM_mesh_edgeloops_free(ListBase *eloops)
void BM_edgeloop_free(BMEdgeLoopStore *el_store)
BMEdgeLoopStore * BM_edgeloop_from_verts(BMVert **v_arr, const int v_arr_tot, bool is_closed)
int BM_mesh_edgeloops_find(BMesh *bm, ListBase *r_eloops, bool(*test_fn)(BMEdge *, void *user_data), void *user_data)
#define NODE_AS_V(n)
bool BM_mesh_edgeloops_find_path(BMesh *bm, ListBase *r_eloops, bool(*test_fn)(BMEdge *, void *user_data), void *user_data, BMVert *v_src, BMVert *v_dst)
#define EDGELOOP_EPS
int BM_edgeloop_length_get(BMEdgeLoopStore *el_store)
void BM_mesh_edgeloops_calc_order(BMesh *UNUSED(bm), ListBase *eloops, const bool use_normals)
static bool bm_loop_build(BMEdgeLoopStore *el_store, BMVert *v_prev, BMVert *v, int dir)
bool BM_edgeloop_is_closed(BMEdgeLoopStore *el_store)
void BM_edgeloop_edges_get(struct BMEdgeLoopStore *el_store, BMEdge **e_arr)
ListBase * BM_edgeloop_verts_get(BMEdgeLoopStore *el_store)
void BM_mesh_edgeloops_calc_normal_aligned(BMesh *bm, ListBase *eloops, const float no_align[3])
static int bm_vert_other_tag(BMVert *v, BMVert *v_prev, BMEdge **r_e)
bool BM_edgeloop_calc_normal(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store)
bool BM_edgeloop_overlap_check(struct BMEdgeLoopStore *el_store_a, struct BMEdgeLoopStore *el_store_b)
bool BM_edgeloop_calc_normal_aligned(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store, const float no_align[3])
const float * BM_edgeloop_normal_get(struct BMEdgeLoopStore *el_store)
void BM_edgeloop_flip(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store)
static void vs_add(BLI_mempool *vs_pool, ListBase *lb, BMVert *v, BMEdge *e_prev, const int iter_tot)
void BM_mesh_edgeloops_calc_normal(BMesh *bm, ListBase *eloops)
#define EDGE_SPLIT(node_copy, node_other)
void BM_edgeloop_calc_center(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store)
void BM_mesh_edgeloops_calc_center(BMesh *bm, ListBase *eloops)
#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_index_set(ele, index)
Definition: bmesh_inline.h:111
#define BM_elem_flag_test(ele, hflag)
Definition: bmesh_inline.h:12
#define BM_elem_flag_enable(ele, hflag)
Definition: bmesh_inline.h:14
#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_EDGES_OF_MESH
@ BM_VERTS_OF_MESH
@ BM_EDGES_OF_VERT
ATTR_WARN_UNUSED_RESULT BMesh * bm
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
Definition: bmesh_query.c:1553
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE bool BM_vert_in_edge(const 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
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition: btQuadWord.h:119
OperationNode * node
void * user_data
SyclQueue void void size_t num_bytes void
int count
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_dupallocN)(const void *vmemh)
Definition: mallocn.c:28
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
#define fabsf(x)
Definition: metal/compat.h:219
void split(const std::string &s, const char delim, std::vector< std::string > &tokens)
Definition: abc_util.cc:92
vec_base< T, 3 > cross(const vec_base< T, 3 > &a, const vec_base< T, 3 > &b)
T abs(const T &a)
struct BMEdgeLoopStore * next
struct BMEdgeLoopStore * prev
struct BMEdge * e
Definition: bmesh_class.h:97
char elem_index_dirty
Definition: bmesh_class.h:305
int totedge
Definition: bmesh_class.h:297
struct LinkData * next
Definition: DNA_listBase.h:25
struct LinkData * prev
Definition: DNA_listBase.h:25
void * last
Definition: DNA_listBase.h:31
void * first
Definition: DNA_listBase.h:31
struct VertStep * next
struct VertStep * prev
BMVert * v