Blender  V3.3
bmesh_walkers_impl.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
9 #include <string.h>
10 
11 #include "BLI_utildefines.h"
12 
13 #include "BKE_customdata.h"
14 
15 #include "bmesh.h"
17 
18 /* Pop into stack memory (common operation). */
19 #define BMW_state_remove_r(walker, owalk) \
20  { \
21  memcpy(owalk, BMW_current_state(walker), sizeof(*(owalk))); \
22  BMW_state_remove(walker); \
23  } \
24  (void)0
25 
26 /* -------------------------------------------------------------------- */
30 static bool bmw_mask_check_vert(BMWalker *walker, BMVert *v)
31 {
33  return false;
34  }
35  if (walker->mask_vert && !BMO_vert_flag_test(walker->bm, v, walker->mask_vert)) {
36  return false;
37  }
38  return true;
39 }
40 
41 static bool bmw_mask_check_edge(BMWalker *walker, BMEdge *e)
42 {
44  return false;
45  }
46  if (walker->mask_edge && !BMO_edge_flag_test(walker->bm, e, walker->mask_edge)) {
47  return false;
48  }
49  return true;
50 }
51 
52 static bool bmw_mask_check_face(BMWalker *walker, BMFace *f)
53 {
55  return false;
56  }
57  if (walker->mask_face && !BMO_face_flag_test(walker->bm, f, walker->mask_face)) {
58  return false;
59  }
60  return true;
61 }
62 
65 /* -------------------------------------------------------------------- */
72 static bool bmw_edge_is_wire(const BMWalker *walker, const BMEdge *e)
73 {
74  if (walker->flag & BMW_FLAG_TEST_HIDDEN) {
75  /* Check if this is a wire edge, ignoring hidden faces. */
76  if (BM_edge_is_wire(e)) {
77  return true;
78  }
80  }
81  return BM_edge_is_wire(e);
82 }
83 
86 /* -------------------------------------------------------------------- */
99 {
100  BMwShellWalker *shellWalk = NULL;
101 
102  if (BLI_gset_haskey(walker->visit_set, e)) {
103  return;
104  }
105 
106  if (!bmw_mask_check_edge(walker, e)) {
107  return;
108  }
109 
110  shellWalk = BMW_state_add(walker);
111  shellWalk->curedge = e;
112  BLI_gset_insert(walker->visit_set, e);
113 }
114 
115 static void bmw_VertShellWalker_begin(BMWalker *walker, void *data)
116 {
117  BMIter eiter;
118  BMHeader *h = data;
119  BMEdge *e;
120  BMVert *v;
121 
122  if (UNLIKELY(h == NULL)) {
123  return;
124  }
125 
126  switch (h->htype) {
127  case BM_VERT: {
128  /* Starting the walk at a vert, add all the edges to the work-list. */
129  v = (BMVert *)h;
130  BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
132  }
133  break;
134  }
135 
136  case BM_EDGE: {
137  /* Starting the walk at an edge, add the single edge to the work-list. */
138  e = (BMEdge *)h;
140  break;
141  }
142  default:
143  BLI_assert(0);
144  }
145 }
146 
147 static void *bmw_VertShellWalker_yield(BMWalker *walker)
148 {
149  BMwShellWalker *shellWalk = BMW_current_state(walker);
150  return shellWalk->curedge;
151 }
152 
153 static void *bmw_VertShellWalker_step(BMWalker *walker)
154 {
155  BMwShellWalker *swalk, owalk;
156  BMEdge *e, *e2;
157  BMVert *v;
158  BMIter iter;
159  int i;
160 
161  BMW_state_remove_r(walker, &owalk);
162  swalk = &owalk;
163 
164  e = swalk->curedge;
165 
166  for (i = 0; i < 2; i++) {
167  v = i ? e->v2 : e->v1;
168  BM_ITER_ELEM (e2, &iter, v, BM_EDGES_OF_VERT) {
169  bmw_VertShellWalker_visitEdge(walker, e2);
170  }
171  }
172 
173  return e;
174 }
175 
176 #if 0
177 static void *bmw_VertShellWalker_step(BMWalker *walker)
178 {
179  BMEdge *curedge, *next = NULL;
180  BMVert *v_old = NULL;
181  bool restrictpass = true;
182  BMwShellWalker shellWalk = *((BMwShellWalker *)BMW_current_state(walker));
183 
184  if (!BLI_gset_haskey(walker->visit_set, shellWalk.base)) {
185  BLI_gset_insert(walker->visit_set, shellWalk.base);
186  }
187 
188  BMW_state_remove(walker);
189 
190  /* Find the next edge whose other vertex has not been visited. */
191  curedge = shellWalk.curedge;
192  do {
193  if (!BLI_gset_haskey(walker->visit_set, curedge)) {
194  if (!walker->visibility_flag ||
195  (walker->visibility_flag &&
196  BMO_edge_flag_test(walker->bm, curedge, walker->visibility_flag))) {
197  BMwShellWalker *newstate;
198 
199  v_old = BM_edge_other_vert(curedge, shellWalk.base);
200 
201  /* Push a new state onto the stack. */
202  newState = BMW_state_add(walker);
203  BLI_gset_insert(walker->visit_set, curedge);
204 
205  /* Populate the new state. */
206 
207  newState->base = v_old;
208  newState->curedge = curedge;
209  }
210  }
211  } while ((curedge = bmesh_disk_edge_next(curedge, shellWalk.base)) != shellWalk.curedge);
212 
213  return shellWalk.curedge;
214 }
215 #endif
216 
219 /* -------------------------------------------------------------------- */
229 {
230  BMwLoopShellWalker *shellWalk = NULL;
231 
232  if (BLI_gset_haskey(walker->visit_set, l)) {
233  return;
234  }
235 
236  if (!bmw_mask_check_face(walker, l->f)) {
237  return;
238  }
239 
240  shellWalk = BMW_state_add(walker);
241  shellWalk->curloop = l;
242  BLI_gset_insert(walker->visit_set, l);
243 }
244 
245 static void bmw_LoopShellWalker_begin(BMWalker *walker, void *data)
246 {
247  BMIter iter;
248  BMHeader *h = data;
249 
250  if (UNLIKELY(h == NULL)) {
251  return;
252  }
253 
254  switch (h->htype) {
255  case BM_LOOP: {
256  /* Starting the walk at a vert, add all the edges to the work-list. */
257  BMLoop *l = (BMLoop *)h;
259  break;
260  }
261 
262  case BM_VERT: {
263  BMVert *v = (BMVert *)h;
264  BMLoop *l;
265  BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
267  }
268  break;
269  }
270  case BM_EDGE: {
271  BMEdge *e = (BMEdge *)h;
272  BMLoop *l;
273  BM_ITER_ELEM (l, &iter, e, BM_LOOPS_OF_EDGE) {
275  }
276  break;
277  }
278  case BM_FACE: {
279  BMFace *f = (BMFace *)h;
281  /* Walker will handle other loops within the face. */
283  break;
284  }
285  default:
286  BLI_assert(0);
287  }
288 }
289 
290 static void *bmw_LoopShellWalker_yield(BMWalker *walker)
291 {
292  BMwLoopShellWalker *shellWalk = BMW_current_state(walker);
293  return shellWalk->curloop;
294 }
295 
297 {
298  BMEdge *e_edj_pair[2];
299  int i;
300 
301  /* Seems paranoid, but one caller also walks edges. */
303 
306 
307  e_edj_pair[0] = l->e;
308  e_edj_pair[1] = l->prev->e;
309 
310  for (i = 0; i < 2; i++) {
311  BMEdge *e = e_edj_pair[i];
312  if (bmw_mask_check_edge(walker, e)) {
313  BMLoop *l_iter, *l_first;
314 
315  l_iter = l_first = e->l;
316  do {
317  BMLoop *l_radial = (l_iter->v == l->v) ? l_iter : l_iter->next;
318  BLI_assert(l_radial->v == l->v);
319  if (l != l_radial) {
320  bmw_LoopShellWalker_visitLoop(walker, l_radial);
321  }
322  } while ((l_iter = l_iter->radial_next) != l_first);
323  }
324  }
325 }
326 
327 static void *bmw_LoopShellWalker_step(BMWalker *walker)
328 {
329  BMwLoopShellWalker *swalk, owalk;
330  BMLoop *l;
331 
332  BMW_state_remove_r(walker, &owalk);
333  swalk = &owalk;
334 
335  l = swalk->curloop;
337 
338  return l;
339 }
340 
343 /* -------------------------------------------------------------------- */
357 {
358  BMwLoopShellWireWalker *shellWalk = NULL;
359 
360  BLI_assert(bmw_edge_is_wire(walker, e));
361 
362  if (BLI_gset_haskey(walker->visit_set_alt, e)) {
363  return;
364  }
365 
366  if (!bmw_mask_check_edge(walker, e)) {
367  return;
368  }
369 
370  shellWalk = BMW_state_add(walker);
371  shellWalk->curelem = (BMElem *)e;
372  BLI_gset_insert(walker->visit_set_alt, e);
373 }
374 
375 static void bmw_LoopShellWireWalker_visitVert(BMWalker *walker, BMVert *v, const BMEdge *e_from)
376 {
377  BMEdge *e;
378 
380 
381  if (BLI_gset_haskey(walker->visit_set_alt, v)) {
382  return;
383  }
384 
385  if (!bmw_mask_check_vert(walker, v)) {
386  return;
387  }
388 
389  e = v->e;
390  do {
391  if (bmw_edge_is_wire(walker, e) && (e != e_from)) {
392  BMVert *v_other;
393  BMIter iter;
394  BMLoop *l;
395 
397 
398  /* Check if we step onto a non-wire vertex. */
399  v_other = BM_edge_other_vert(e, v);
400  BM_ITER_ELEM (l, &iter, v_other, BM_LOOPS_OF_VERT) {
401 
403  }
404  }
405  } while ((e = BM_DISK_EDGE_NEXT(e, v)) != v->e);
406 
407  BLI_gset_insert(walker->visit_set_alt, v);
408 }
409 
410 static void bmw_LoopShellWireWalker_begin(BMWalker *walker, void *data)
411 {
412  BMHeader *h = data;
413 
414  if (UNLIKELY(h == NULL)) {
415  return;
416  }
417 
419 
420  switch (h->htype) {
421  case BM_LOOP: {
422  BMLoop *l = (BMLoop *)h;
424  break;
425  }
426 
427  case BM_VERT: {
428  BMVert *v = (BMVert *)h;
429  if (v->e) {
431  }
432  break;
433  }
434  case BM_EDGE: {
435  BMEdge *e = (BMEdge *)h;
436  if (bmw_mask_check_edge(walker, e)) {
439  }
440  else if (e->l) {
441  BMLoop *l_iter, *l_first;
442 
443  l_iter = l_first = e->l;
444  do {
445  bmw_LoopShellWalker_visitLoop(walker, l_iter);
446  bmw_LoopShellWalker_visitLoop(walker, l_iter->next);
447  } while ((l_iter = l_iter->radial_next) != l_first);
448  }
449  break;
450  }
451  case BM_FACE: {
452  /* Wire verts will be walked over. */
453  break;
454  }
455  default:
456  BLI_assert(0);
457  }
458 }
459 
461 {
462  BMwLoopShellWireWalker *shellWalk = BMW_current_state(walker);
463  return shellWalk->curelem;
464 }
465 
467 {
468  BMwLoopShellWireWalker *swalk, owalk;
469 
470  BMW_state_remove_r(walker, &owalk);
471  swalk = &owalk;
472 
473  if (swalk->curelem->head.htype == BM_LOOP) {
474  BMLoop *l = (BMLoop *)swalk->curelem;
475 
477 
479 
480  return l;
481  }
482 
483  BMEdge *e = (BMEdge *)swalk->curelem;
484 
486 
487  bmw_LoopShellWireWalker_visitVert(walker, e->v1, e);
488  bmw_LoopShellWireWalker_visitVert(walker, e->v2, e);
489 
490  return e;
491 }
492 
495 /* -------------------------------------------------------------------- */
503 {
504  BMwShellWalker *shellWalk = NULL;
505 
506  if (BLI_gset_haskey(walker->visit_set, e)) {
507  return;
508  }
509 
510  if (!bmw_mask_check_edge(walker, e)) {
511  return;
512  }
513 
514  shellWalk = BMW_state_add(walker);
515  shellWalk->curedge = e;
516  BLI_gset_insert(walker->visit_set, e);
517 }
518 
519 static void bmw_FaceShellWalker_begin(BMWalker *walker, void *data)
520 {
521  BMEdge *e = data;
523 }
524 
525 static void *bmw_FaceShellWalker_yield(BMWalker *walker)
526 {
527  BMwShellWalker *shellWalk = BMW_current_state(walker);
528  return shellWalk->curedge;
529 }
530 
531 static void *bmw_FaceShellWalker_step(BMWalker *walker)
532 {
533  BMwShellWalker *swalk, owalk;
534  BMEdge *e, *e2;
535  BMIter iter;
536 
537  BMW_state_remove_r(walker, &owalk);
538  swalk = &owalk;
539 
540  e = swalk->curedge;
541 
542  if (e->l) {
543  BMLoop *l_iter, *l_first;
544 
545  l_iter = l_first = e->l;
546  do {
547  BM_ITER_ELEM (e2, &iter, l_iter->f, BM_EDGES_OF_FACE) {
548  if (e2 != e) {
549  bmw_FaceShellWalker_visitEdge(walker, e2);
550  }
551  }
552  } while ((l_iter = l_iter->radial_next) != l_first);
553  }
554 
555  return e;
556 }
557 
560 /* -------------------------------------------------------------------- */
569 {
571 
572  if (BLI_gset_haskey(walker->visit_set, v)) {
573  /* Already visited. */
574  return;
575  }
576 
577  if (!bmw_mask_check_vert(walker, v)) {
578  /* Not flagged for walk. */
579  return;
580  }
581 
582  vwalk = BMW_state_add(walker);
583  vwalk->curvert = v;
584  BLI_gset_insert(walker->visit_set, v);
585 }
586 
587 static void bmw_ConnectedVertexWalker_begin(BMWalker *walker, void *data)
588 {
589  BMVert *v = data;
591 }
592 
594 {
596  return vwalk->curvert;
597 }
598 
600 {
601  BMwConnectedVertexWalker *vwalk, owalk;
602  BMVert *v, *v2;
603  BMEdge *e;
604  BMIter iter;
605 
606  BMW_state_remove_r(walker, &owalk);
607  vwalk = &owalk;
608 
609  v = vwalk->curvert;
610 
611  BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
612  v2 = BM_edge_other_vert(e, v);
613  if (!BLI_gset_haskey(walker->visit_set, v2)) {
615  }
616  }
617 
618  return v;
619 }
620 
623 /* -------------------------------------------------------------------- */
636 static void bmw_IslandboundWalker_begin(BMWalker *walker, void *data)
637 {
638  BMLoop *l = data;
639  BMwIslandboundWalker *iwalk = NULL;
640 
641  iwalk = BMW_state_add(walker);
642 
643  iwalk->base = iwalk->curloop = l;
644  iwalk->lastv = l->v;
645 
646  BLI_gset_insert(walker->visit_set, data);
647 }
648 
650 {
651  BMwIslandboundWalker *iwalk = BMW_current_state(walker);
652 
653  return iwalk->curloop;
654 }
655 
657 {
658  BMwIslandboundWalker *iwalk, owalk;
659  BMVert *v;
660  BMEdge *e;
661  BMFace *f;
662  BMLoop *l;
663 
664  memcpy(&owalk, BMW_current_state(walker), sizeof(owalk));
665  /* Normally we'd remove here, but delay until after error checking. */
666  iwalk = &owalk;
667 
668  l = iwalk->curloop;
669  e = l->e;
670 
671  v = BM_edge_other_vert(e, iwalk->lastv);
672 
673  /* Pop off current state. */
674  BMW_state_remove(walker);
675 
676  f = l->f;
677 
678  while (1) {
680  if (BM_loop_is_manifold(l)) {
681  l = l->radial_next;
682  f = l->f;
683  e = l->e;
684 
685  if (!bmw_mask_check_face(walker, f)) {
686  l = l->radial_next;
687  break;
688  }
689  }
690  else {
691  /* Treat non-manifold edges as boundaries. */
692  f = l->f;
693  e = l->e;
694  break;
695  }
696  }
697 
698  if (l == owalk.curloop) {
699  return NULL;
700  }
701  if (BLI_gset_haskey(walker->visit_set, l)) {
702  return owalk.curloop;
703  }
704 
705  BLI_gset_insert(walker->visit_set, l);
706  iwalk = BMW_state_add(walker);
707  iwalk->base = owalk.base;
708 
709 #if 0
710  if (!BMO_face_flag_test(walker->bm, l->f, walker->visibility_flag)) {
711  iwalk->curloop = l->radial_next;
712  }
713  else {
714  iwalk->curloop = l;
715  }
716 #else
717  iwalk->curloop = l;
718 #endif
719  iwalk->lastv = v;
720 
721  return owalk.curloop;
722 }
723 
724 /* -------------------------------------------------------------------- */
732 static void bmw_IslandWalker_begin(BMWalker *walker, void *data)
733 {
734  BMwIslandWalker *iwalk = NULL;
735 
736  if (!bmw_mask_check_face(walker, data)) {
737  return;
738  }
739 
740  iwalk = BMW_state_add(walker);
741  BLI_gset_insert(walker->visit_set, data);
742 
743  iwalk->cur = data;
744 }
745 
746 static void *bmw_IslandWalker_yield(BMWalker *walker)
747 {
748  BMwIslandWalker *iwalk = BMW_current_state(walker);
749 
750  return iwalk->cur;
751 }
752 
753 static void *bmw_IslandWalker_step_ex(BMWalker *walker, bool only_manifold)
754 {
755  BMwIslandWalker *iwalk, owalk;
756  BMLoop *l_iter, *l_first;
757 
758  BMW_state_remove_r(walker, &owalk);
759  iwalk = &owalk;
760 
761  l_iter = l_first = BM_FACE_FIRST_LOOP(iwalk->cur);
762  do {
763  /* Could skip loop here too, but don't add unless we need it. */
764  if (!bmw_mask_check_edge(walker, l_iter->e)) {
765  continue;
766  }
767 
768  BMLoop *l_radial_iter;
769 
770  if (only_manifold && (l_iter->radial_next != l_iter)) {
771  int face_count = 1;
772  /* Check other faces (not this one), ensure only one other Can be walked onto. */
773  l_radial_iter = l_iter->radial_next;
774  do {
775  if (bmw_mask_check_face(walker, l_radial_iter->f)) {
776  face_count++;
777  if (face_count == 3) {
778  break;
779  }
780  }
781  } while ((l_radial_iter = l_radial_iter->radial_next) != l_iter);
782 
783  if (face_count != 2) {
784  continue;
785  }
786  }
787 
788  l_radial_iter = l_iter;
789  while ((l_radial_iter = l_radial_iter->radial_next) != l_iter) {
790  BMFace *f = l_radial_iter->f;
791 
792  if (!bmw_mask_check_face(walker, f)) {
793  continue;
794  }
795 
796  /* Saves checking #BLI_gset_haskey below (manifold edges there's a 50% chance). */
797  if (f == iwalk->cur) {
798  continue;
799  }
800 
801  if (BLI_gset_haskey(walker->visit_set, f)) {
802  continue;
803  }
804 
805  iwalk = BMW_state_add(walker);
806  iwalk->cur = f;
807  BLI_gset_insert(walker->visit_set, f);
808  break;
809  }
810  } while ((l_iter = l_iter->next) != l_first);
811 
812  return owalk.cur;
813 }
814 
815 static void *bmw_IslandWalker_step(BMWalker *walker)
816 {
817  return bmw_IslandWalker_step_ex(walker, false);
818 }
819 
824 {
825  return bmw_IslandWalker_step_ex(walker, true);
826 }
827 
830 /* -------------------------------------------------------------------- */
836 /* utility function to see if an edge is a part of an ngon boundary */
838 {
839  return (BM_edge_is_boundary(e) && (e->l->f->len > 4) &&
840  (BM_edge_is_boundary(e->l->next->e) || BM_edge_is_boundary(e->l->prev->e)));
841 }
842 
843 static void bmw_EdgeLoopWalker_begin(BMWalker *walker, void *data)
844 {
845  BMwEdgeLoopWalker *lwalk = NULL, owalk, *owalk_pt;
846  BMEdge *e = data;
847  BMVert *v;
848  const int vert_edge_count[2] = {
851  };
852  const int vert_face_count[2] = {
853  BM_vert_face_count(e->v1),
854  BM_vert_face_count(e->v2),
855  };
856 
857  v = e->v1;
858 
859  lwalk = BMW_state_add(walker);
860  BLI_gset_insert(walker->visit_set, e);
861 
862  lwalk->cur = lwalk->start = e;
863  lwalk->lastv = lwalk->startv = v;
865  lwalk->is_single = (lwalk->is_boundary && bm_edge_is_single(e));
866 
931  if ((lwalk->is_boundary == false) &&
932  /* Without checking the face count, the 3 edges could be this edge
933  * plus two boundary edges (which would not be stepped over), see T84906. */
934  ((vert_edge_count[0] == 3 && vert_face_count[0] == 3) ||
935  (vert_edge_count[1] == 3 && vert_face_count[1] == 3))) {
936  BMIter iter;
937  BMFace *f_iter;
938  BMFace *f_best = NULL;
939 
940  BM_ITER_ELEM (f_iter, &iter, e, BM_FACES_OF_EDGE) {
941  if (f_best == NULL || f_best->len < f_iter->len) {
942  f_best = f_iter;
943  }
944  }
945 
946  if (f_best) {
947  /* Only use hub selection for 5+ sides else this could
948  * conflict with normal edge loop selection. */
949  lwalk->f_hub = f_best->len > 4 ? f_best : NULL;
950  }
951  else {
952  /* Edge doesn't have any faces connected to it. */
953  lwalk->f_hub = NULL;
954  }
955  }
956  else {
957  lwalk->f_hub = NULL;
958  }
959 
960  /* Rewind. */
961  while ((owalk_pt = BMW_current_state(walker))) {
962  owalk = *((BMwEdgeLoopWalker *)owalk_pt);
963  BMW_walk(walker);
964  }
965 
966  lwalk = BMW_state_add(walker);
967  *lwalk = owalk;
968 
969  lwalk->lastv = lwalk->startv = BM_edge_other_vert(owalk.cur, lwalk->lastv);
970 
971  BLI_gset_clear(walker->visit_set, NULL);
972  BLI_gset_insert(walker->visit_set, owalk.cur);
973 }
974 
975 static void *bmw_EdgeLoopWalker_yield(BMWalker *walker)
976 {
977  BMwEdgeLoopWalker *lwalk = BMW_current_state(walker);
978 
979  return lwalk->cur;
980 }
981 
982 static void *bmw_EdgeLoopWalker_step(BMWalker *walker)
983 {
984  BMwEdgeLoopWalker *lwalk, owalk;
985  BMEdge *e, *nexte = NULL;
986  BMLoop *l;
987  BMVert *v;
988 
989  BMW_state_remove_r(walker, &owalk);
990  lwalk = &owalk;
991 
992  e = lwalk->cur;
993  l = e->l;
994 
995  if (owalk.f_hub) { /* NGON EDGE */
996  int vert_edge_tot;
997 
998  v = BM_edge_other_vert(e, lwalk->lastv);
999 
1000  vert_edge_tot = BM_vert_edge_count_nonwire(v);
1001 
1002  if (vert_edge_tot == 3) {
1003  l = BM_face_other_vert_loop(owalk.f_hub, lwalk->lastv, v);
1004  nexte = BM_edge_exists(v, l->v);
1005 
1006  if (bmw_mask_check_edge(walker, nexte) && !BLI_gset_haskey(walker->visit_set, nexte) &&
1007  /* Never step onto a boundary edge, this gives odd-results. */
1008  (BM_edge_is_boundary(nexte) == false)) {
1009  lwalk = BMW_state_add(walker);
1010  lwalk->cur = nexte;
1011  lwalk->lastv = v;
1012 
1013  lwalk->is_boundary = owalk.is_boundary;
1014  lwalk->is_single = owalk.is_single;
1015  lwalk->f_hub = owalk.f_hub;
1016 
1017  BLI_gset_insert(walker->visit_set, nexte);
1018  }
1019  }
1020  }
1021  else if (l == NULL) { /* WIRE EDGE */
1022  BMIter eiter;
1023 
1024  /* Match trunk: mark all connected wire edges. */
1025  for (int i = 0; i < 2; i++) {
1026  v = i ? e->v2 : e->v1;
1027 
1028  BM_ITER_ELEM (nexte, &eiter, v, BM_EDGES_OF_VERT) {
1029  if ((nexte->l == NULL) && bmw_mask_check_edge(walker, nexte) &&
1030  !BLI_gset_haskey(walker->visit_set, nexte)) {
1031  lwalk = BMW_state_add(walker);
1032  lwalk->cur = nexte;
1033  lwalk->lastv = v;
1034 
1035  lwalk->is_boundary = owalk.is_boundary;
1036  lwalk->is_single = owalk.is_single;
1037  lwalk->f_hub = owalk.f_hub;
1038 
1039  BLI_gset_insert(walker->visit_set, nexte);
1040  }
1041  }
1042  }
1043  }
1044  else if (owalk.is_boundary == false) { /* NORMAL EDGE WITH FACES */
1045  int vert_edge_tot;
1046 
1047  v = BM_edge_other_vert(e, lwalk->lastv);
1048 
1049  vert_edge_tot = BM_vert_edge_count_nonwire(v);
1050 
1051  /* Typical looping over edges in the middle of a mesh.
1052  * Why use 2 here at all? - for internal ngon loops it can be useful. */
1053  if (ELEM(vert_edge_tot, 4, 2)) {
1054  int i_opposite = vert_edge_tot / 2;
1055  int i = 0;
1056  do {
1058  if (BM_edge_is_manifold(l->e)) {
1059  l = l->radial_next;
1060  }
1061  else {
1062  l = NULL;
1063  break;
1064  }
1065  } while ((++i != i_opposite));
1066  }
1067  else {
1068  l = NULL;
1069  }
1070 
1071  if (l != NULL) {
1072  if (l != e->l && bmw_mask_check_edge(walker, l->e) &&
1073  !BLI_gset_haskey(walker->visit_set, l->e)) {
1074  lwalk = BMW_state_add(walker);
1075  lwalk->cur = l->e;
1076  lwalk->lastv = v;
1077 
1078  lwalk->is_boundary = owalk.is_boundary;
1079  lwalk->is_single = owalk.is_single;
1080  lwalk->f_hub = owalk.f_hub;
1081 
1082  BLI_gset_insert(walker->visit_set, l->e);
1083  }
1084  }
1085  }
1086  else if (owalk.is_boundary == true) { /* BOUNDARY EDGE WITH FACES */
1087  int vert_edge_tot;
1088 
1089  v = BM_edge_other_vert(e, lwalk->lastv);
1090 
1091  vert_edge_tot = BM_vert_edge_count_nonwire(v);
1092 
1093  /* Check if we should step, this is fairly involved. */
1094  if (
1095  /* Walk over boundary of faces but stop at corners. */
1096  (owalk.is_single == false && vert_edge_tot > 2) ||
1097 
1098  /* Initial edge was a boundary, so is this edge and vertex is only a part of this face
1099  * this lets us walk over the boundary of an ngon which is handy. */
1100  (owalk.is_single == true && vert_edge_tot == 2 && BM_edge_is_boundary(e))) {
1101  /* Find next boundary edge in the fan. */
1102  do {
1104  if (BM_edge_is_manifold(l->e)) {
1105  l = l->radial_next;
1106  }
1107  else if (BM_edge_is_boundary(l->e)) {
1108  break;
1109  }
1110  else {
1111  l = NULL;
1112  break;
1113  }
1114  } while (true);
1115  }
1116 
1117  if (owalk.is_single == false && l && bm_edge_is_single(l->e)) {
1118  l = NULL;
1119  }
1120 
1121  if (l != NULL) {
1122  if (l != e->l && bmw_mask_check_edge(walker, l->e) &&
1123  !BLI_gset_haskey(walker->visit_set, l->e)) {
1124  lwalk = BMW_state_add(walker);
1125  lwalk->cur = l->e;
1126  lwalk->lastv = v;
1127 
1128  lwalk->is_boundary = owalk.is_boundary;
1129  lwalk->is_single = owalk.is_single;
1130  lwalk->f_hub = owalk.f_hub;
1131 
1132  BLI_gset_insert(walker->visit_set, l->e);
1133  }
1134  }
1135  }
1136 
1137  return owalk.cur;
1138 }
1139 
1142 /* -------------------------------------------------------------------- */
1155 {
1156  /* Face must have degree 4. */
1157  if (l->f->len != 4) {
1158  return false;
1159  }
1160 
1161  if (!bmw_mask_check_face(walker, l->f)) {
1162  return false;
1163  }
1164 
1165  /* The face must not have been already visited. */
1166  if (BLI_gset_haskey(walker->visit_set, l->f) && BLI_gset_haskey(walker->visit_set_alt, l->e)) {
1167  return false;
1168  }
1169 
1170  return true;
1171 }
1172 
1173 /* Check whether the face loop can start from the given edge. */
1175 {
1176  /* There is no face loop starting from a wire edge. */
1177  if (BM_edge_is_wire(e)) {
1178  return false;
1179  }
1180 
1181  /* Don't start a loop from a boundary edge if it cannot be extended to cover any faces. */
1182  if (BM_edge_is_boundary(e)) {
1183  if (!bmw_FaceLoopWalker_include_face(walker, e->l)) {
1184  return false;
1185  }
1186  }
1187 
1188  /* Don't start a face loop from non-manifold edges. */
1189  if (!BM_edge_is_manifold(e)) {
1190  return false;
1191  }
1192 
1193  return true;
1194 }
1195 
1196 static void bmw_FaceLoopWalker_begin(BMWalker *walker, void *data)
1197 {
1198  BMwFaceLoopWalker *lwalk, owalk, *owalk_pt;
1199  BMEdge *e = data;
1200  /* BMesh *bm = walker->bm; */ /* UNUSED */
1201  /* int fcount = BM_edge_face_count(e); */ /* UNUSED */
1202 
1203  if (!bmw_FaceLoopWalker_edge_begins_loop(walker, e)) {
1204  return;
1205  }
1206 
1207  lwalk = BMW_state_add(walker);
1208  lwalk->l = e->l;
1209  lwalk->no_calc = false;
1210  BLI_gset_insert(walker->visit_set, lwalk->l->f);
1211 
1212  /* Rewind. */
1213  while ((owalk_pt = BMW_current_state(walker))) {
1214  owalk = *((BMwFaceLoopWalker *)owalk_pt);
1215  BMW_walk(walker);
1216  }
1217 
1218  lwalk = BMW_state_add(walker);
1219  *lwalk = owalk;
1220  lwalk->no_calc = false;
1221 
1222  BLI_gset_clear(walker->visit_set_alt, NULL);
1223  BLI_gset_insert(walker->visit_set_alt, lwalk->l->e);
1224 
1225  BLI_gset_clear(walker->visit_set, NULL);
1226  BLI_gset_insert(walker->visit_set, lwalk->l->f);
1227 }
1228 
1229 static void *bmw_FaceLoopWalker_yield(BMWalker *walker)
1230 {
1231  BMwFaceLoopWalker *lwalk = BMW_current_state(walker);
1232 
1233  if (!lwalk) {
1234  return NULL;
1235  }
1236 
1237  return lwalk->l->f;
1238 }
1239 
1240 static void *bmw_FaceLoopWalker_step(BMWalker *walker)
1241 {
1242  BMwFaceLoopWalker *lwalk, owalk;
1243  BMFace *f;
1244  BMLoop *l;
1245 
1246  BMW_state_remove_r(walker, &owalk);
1247  lwalk = &owalk;
1248 
1249  f = lwalk->l->f;
1250  l = lwalk->l->radial_next;
1251 
1252  if (lwalk->no_calc) {
1253  return f;
1254  }
1255 
1256  if (!bmw_FaceLoopWalker_include_face(walker, l)) {
1257  l = lwalk->l;
1258  l = l->next->next;
1259  if (!BM_edge_is_manifold(l->e)) {
1260  l = l->prev->prev;
1261  }
1262  l = l->radial_next;
1263  }
1264 
1265  if (bmw_FaceLoopWalker_include_face(walker, l)) {
1266  lwalk = BMW_state_add(walker);
1267  lwalk->l = l;
1268 
1269  if (l->f->len != 4) {
1270  lwalk->no_calc = true;
1271  lwalk->l = owalk.l;
1272  }
1273  else {
1274  lwalk->no_calc = false;
1275  }
1276 
1277  /* Both may already exist. */
1278  BLI_gset_add(walker->visit_set_alt, l->e);
1279  BLI_gset_add(walker->visit_set, l->f);
1280  }
1281 
1282  return f;
1283 }
1284 
1287 // #define BMW_EDGERING_NGON
1288 
1289 /* -------------------------------------------------------------------- */
1297 static void bmw_EdgeringWalker_begin(BMWalker *walker, void *data)
1298 {
1299  BMwEdgeringWalker *lwalk, owalk, *owalk_pt;
1300  BMEdge *e = data;
1301 
1302  lwalk = BMW_state_add(walker);
1303  lwalk->l = e->l;
1304 
1305  if (!lwalk->l) {
1306  lwalk->wireedge = e;
1307  return;
1308  }
1309  lwalk->wireedge = NULL;
1310 
1311  BLI_gset_insert(walker->visit_set, lwalk->l->e);
1312 
1313  /* Rewind. */
1314  while ((owalk_pt = BMW_current_state(walker))) {
1315  owalk = *((BMwEdgeringWalker *)owalk_pt);
1316  BMW_walk(walker);
1317  }
1318 
1319  lwalk = BMW_state_add(walker);
1320  *lwalk = owalk;
1321 
1322 #ifdef BMW_EDGERING_NGON
1323  if (lwalk->l->f->len % 2 != 0)
1324 #else
1325  if (lwalk->l->f->len != 4)
1326 #endif
1327  {
1328  lwalk->l = lwalk->l->radial_next;
1329  }
1330 
1331  BLI_gset_clear(walker->visit_set, NULL);
1332  BLI_gset_insert(walker->visit_set, lwalk->l->e);
1333 }
1334 
1335 static void *bmw_EdgeringWalker_yield(BMWalker *walker)
1336 {
1337  BMwEdgeringWalker *lwalk = BMW_current_state(walker);
1338 
1339  if (!lwalk) {
1340  return NULL;
1341  }
1342 
1343  if (lwalk->l) {
1344  return lwalk->l->e;
1345  }
1346  return lwalk->wireedge;
1347 }
1348 
1349 static void *bmw_EdgeringWalker_step(BMWalker *walker)
1350 {
1351  BMwEdgeringWalker *lwalk, owalk;
1352  BMEdge *e;
1353  BMLoop *l;
1354 #ifdef BMW_EDGERING_NGON
1355  int i, len;
1356 #endif
1357 
1358 #define EDGE_CHECK(e) \
1359  (bmw_mask_check_edge(walker, e) && (BM_edge_is_boundary(e) || BM_edge_is_manifold(e)))
1360 
1361  BMW_state_remove_r(walker, &owalk);
1362  lwalk = &owalk;
1363 
1364  l = lwalk->l;
1365  if (!l) {
1366  return lwalk->wireedge;
1367  }
1368 
1369  e = l->e;
1370  if (!EDGE_CHECK(e)) {
1371  /* Walker won't traverse to a non-manifold edge, but may
1372  * be started on one, and should not traverse *away* from
1373  * a non-manifold edge (non-manifold edges are never in an
1374  * edge ring with manifold edges. */
1375  return e;
1376  }
1377 
1378 #ifdef BMW_EDGERING_NGON
1379  l = l->radial_next;
1380 
1381  i = len = l->f->len;
1382  while (i > 0) {
1383  l = l->next;
1384  i -= 2;
1385  }
1386 
1387  if ((len <= 0) || (len % 2 != 0) || !EDGE_CHECK(l->e) || !bmw_mask_check_face(walker, l->f)) {
1388  l = owalk.l;
1389  i = len;
1390  while (i > 0) {
1391  l = l->next;
1392  i -= 2;
1393  }
1394  }
1395  /* Only walk to manifold edge. */
1396  if ((l->f->len % 2 == 0) && EDGE_CHECK(l->e) && !BLI_gset_haskey(walker->visit_set, l->e))
1397 #else
1398 
1399  l = l->radial_next;
1400  l = l->next->next;
1401 
1402  if ((l->f->len != 4) || !EDGE_CHECK(l->e) || !bmw_mask_check_face(walker, l->f)) {
1403  l = owalk.l->next->next;
1404  }
1405  /* Only walk to manifold edge. */
1406  if ((l->f->len == 4) && EDGE_CHECK(l->e) && !BLI_gset_haskey(walker->visit_set, l->e))
1407 #endif
1408  {
1409  lwalk = BMW_state_add(walker);
1410  lwalk->l = l;
1411  lwalk->wireedge = NULL;
1412 
1413  BLI_gset_insert(walker->visit_set, l->e);
1414  }
1415 
1416  return e;
1417 
1418 #undef EDGE_CHECK
1419 }
1420 
1423 /* -------------------------------------------------------------------- */
1427 static void bmw_EdgeboundaryWalker_begin(BMWalker *walker, void *data)
1428 {
1429  BMwEdgeboundaryWalker *lwalk;
1430  BMEdge *e = data;
1431 
1433 
1434  if (BLI_gset_haskey(walker->visit_set, e)) {
1435  return;
1436  }
1437 
1438  lwalk = BMW_state_add(walker);
1439  lwalk->e = e;
1440  BLI_gset_insert(walker->visit_set, e);
1441 }
1442 
1444 {
1445  BMwEdgeboundaryWalker *lwalk = BMW_current_state(walker);
1446 
1447  if (!lwalk) {
1448  return NULL;
1449  }
1450 
1451  return lwalk->e;
1452 }
1453 
1455 {
1456  BMwEdgeboundaryWalker *lwalk, owalk;
1457  BMEdge *e, *e_other;
1458  BMVert *v;
1459  BMIter eiter;
1460  BMIter viter;
1461 
1462  BMW_state_remove_r(walker, &owalk);
1463  lwalk = &owalk;
1464 
1465  e = lwalk->e;
1466 
1467  if (!bmw_mask_check_edge(walker, e)) {
1468  return e;
1469  }
1470 
1471  BM_ITER_ELEM (v, &viter, e, BM_VERTS_OF_EDGE) {
1472  BM_ITER_ELEM (e_other, &eiter, v, BM_EDGES_OF_VERT) {
1473  if (e != e_other && BM_edge_is_boundary(e_other)) {
1474  if (BLI_gset_haskey(walker->visit_set, e_other)) {
1475  continue;
1476  }
1477 
1478  if (!bmw_mask_check_edge(walker, e_other)) {
1479  continue;
1480  }
1481 
1482  lwalk = BMW_state_add(walker);
1483  BLI_gset_insert(walker->visit_set, e_other);
1484 
1485  lwalk->e = e_other;
1486  }
1487  }
1488  }
1489 
1490  return e;
1491 }
1492 
1495 /* -------------------------------------------------------------------- */
1505 static void bmw_UVEdgeWalker_begin(BMWalker *walker, void *data)
1506 {
1507  BMwUVEdgeWalker *lwalk;
1508  BMLoop *l = data;
1509 
1510  if (BLI_gset_haskey(walker->visit_set, l)) {
1511  return;
1512  }
1513 
1514  lwalk = BMW_state_add(walker);
1515  lwalk->l = l;
1516  BLI_gset_insert(walker->visit_set, l);
1517 }
1518 
1519 static void *bmw_UVEdgeWalker_yield(BMWalker *walker)
1520 {
1521  BMwUVEdgeWalker *lwalk = BMW_current_state(walker);
1522 
1523  if (!lwalk) {
1524  return NULL;
1525  }
1526 
1527  return lwalk->l;
1528 }
1529 
1530 static void *bmw_UVEdgeWalker_step(BMWalker *walker)
1531 {
1532  const int type = walker->bm->ldata.layers[walker->layer].type;
1533  const int offset = walker->bm->ldata.layers[walker->layer].offset;
1534 
1535  BMwUVEdgeWalker *lwalk, owalk;
1536  BMLoop *l;
1537  int i;
1538 
1539  BMW_state_remove_r(walker, &owalk);
1540  lwalk = &owalk;
1541 
1542  l = lwalk->l;
1543 
1544  if (!bmw_mask_check_edge(walker, l->e)) {
1545  return l;
1546  }
1547 
1548  /* Go over loops around `l->v` and `l->next->v` and see which ones share `l` and `l->next`
1549  * UV's coordinates. in addition, push on `l->next` if necessary. */
1550  for (i = 0; i < 2; i++) {
1551  BMIter liter;
1552  BMLoop *l_pivot, *l_radial;
1553 
1554  l_pivot = i ? l->next : l;
1555  BM_ITER_ELEM (l_radial, &liter, l_pivot->v, BM_LOOPS_OF_VERT) {
1556  BMLoop *l_radial_first = l_radial;
1557  void *data_pivot = BM_ELEM_CD_GET_VOID_P(l_pivot, offset);
1558 
1559  do {
1560  BMLoop *l_other;
1561  void *data_other;
1562 
1563  if (BLI_gset_haskey(walker->visit_set, l_radial)) {
1564  continue;
1565  }
1566 
1567  if (l_radial->v != l_pivot->v) {
1568  if (!bmw_mask_check_edge(walker, l_radial->e)) {
1569  continue;
1570  }
1571  }
1572 
1573  l_other = (l_radial->v != l_pivot->v) ? l_radial->next : l_radial;
1574  data_other = BM_ELEM_CD_GET_VOID_P(l_other, offset);
1575 
1576  if (!CustomData_data_equals(type, data_pivot, data_other)) {
1577  continue;
1578  }
1579 
1580  lwalk = BMW_state_add(walker);
1581  BLI_gset_insert(walker->visit_set, l_radial);
1582 
1583  lwalk->l = l_radial;
1584 
1585  } while ((l_radial = l_radial->radial_next) != l_radial_first);
1586  }
1587  }
1588 
1589  return l;
1590 }
1591 
1594 /* -------------------------------------------------------------------- */
1598 static void bmw_NonManifoldedgeWalker_begin(BMWalker *walker, void *data)
1599 {
1601  BMEdge *e = data;
1602 
1603  if (BLI_gset_haskey(walker->visit_set, e)) {
1604  return;
1605  }
1606 
1607  lwalk = BMW_state_add(walker);
1608  lwalk->start = e;
1609  lwalk->cur = e;
1610  lwalk->startv = e->v1;
1611  lwalk->lastv = e->v1;
1612  lwalk->face_count = BM_edge_face_count(e);
1613  BLI_gset_insert(walker->visit_set, e);
1614 }
1615 
1617 {
1619 
1620  if (!lwalk) {
1621  return NULL;
1622  }
1623  return lwalk->cur;
1624 }
1625 
1631 {
1632  BLI_assert(!BM_loop_is_manifold(l));
1633  do {
1635  if (BM_loop_is_manifold(l)) {
1636  l = l->radial_next;
1637  }
1638  else if (BM_edge_face_count_is_equal(l->e, face_count)) {
1639  return l;
1640  }
1641  else {
1642  break;
1643  }
1644  } while (true);
1645  return NULL;
1646 }
1647 
1649 {
1650  BMwNonManifoldEdgeLoopWalker *lwalk, owalk;
1651  BMW_state_remove_r(walker, &owalk);
1652  lwalk = &owalk;
1653  BMLoop *l_cur = NULL;
1654  const int face_count = lwalk->face_count;
1655 
1656  BMVert *v = NULL;
1657 
1658  /* Use the second pass is unlikely, only needed to walk back in the opposite direction. */
1659  for (int pass = 0; pass < 2; pass++) {
1660 
1661  BMEdge *e = lwalk->cur;
1662  v = BM_edge_other_vert(e, lwalk->lastv);
1663 
1664  /* If `lwalk.lastv` can't be walked along, start walking in the opposite direction
1665  * on the initial edge, do this at most one time during this walk operation. */
1666  if (UNLIKELY(pass == 1)) {
1667  e = lwalk->start;
1668  v = lwalk->startv;
1669  }
1670 
1671  BMLoop *l = e->l;
1672  do {
1673  BMLoop *l_next = bmw_NonManifoldLoop_find_next_around_vertex(l, v, face_count);
1674  if ((l_next != NULL) && !BLI_gset_haskey(walker->visit_set, l_next->e)) {
1675  if (l_cur == NULL) {
1676  l_cur = l_next;
1677  }
1678  else if (l_cur->e != l_next->e) {
1679  /* If there are more than one possible edge to step onto (unlikely but possible),
1680  * treat as a junction and stop walking as there is no correct answer in this case. */
1681  l_cur = NULL;
1682  break;
1683  }
1684  }
1685  } while ((l = l->radial_next) != e->l);
1686 
1687  if (l_cur != NULL) {
1688  break;
1689  }
1690  }
1691 
1692  if (l_cur != NULL) {
1693  BLI_assert(!BLI_gset_haskey(walker->visit_set, l_cur->e));
1694  BLI_assert(BM_edge_face_count(l_cur->e) == face_count);
1695  lwalk = BMW_state_add(walker);
1696  lwalk->lastv = v;
1697  lwalk->cur = l_cur->e;
1698  lwalk->face_count = face_count;
1699  BLI_gset_insert(walker->visit_set, l_cur->e);
1700  }
1701  return owalk.cur;
1702 }
1703 
1707  BM_VERT | BM_EDGE,
1711  sizeof(BMwShellWalker),
1713  BM_EDGE, /* Valid restrict masks. */
1714 };
1715 
1721  sizeof(BMwLoopShellWalker),
1723  BM_EDGE, /* Valid restrict masks. */
1724 };
1725 
1731  sizeof(BMwLoopShellWireWalker),
1733  BM_EDGE, /* Valid restrict masks. */
1734 };
1735 
1737  BM_EDGE,
1741  sizeof(BMwShellWalker),
1743  BM_EDGE, /* Valid restrict masks. */
1744 };
1745 
1747  BM_LOOP,
1751  sizeof(BMwIslandboundWalker),
1753  BM_FACE, /* Valid restrict masks. */
1754 };
1755 
1757  BM_FACE,
1761  sizeof(BMwIslandWalker),
1763  BM_EDGE | BM_FACE, /* Valid restrict masks. */
1764 };
1765 
1767  BM_FACE,
1769  bmw_IslandManifoldWalker_step, /* Only difference with #BMW_ISLAND. */
1771  sizeof(BMwIslandWalker),
1773  BM_EDGE | BM_FACE, /* Valid restrict masks. */
1774 };
1775 
1777  BM_EDGE,
1781  sizeof(BMwEdgeLoopWalker),
1783  0,
1784  /* Valid restrict masks. */ /* Could add flags here but so far none are used. */
1785 };
1786 
1788  BM_EDGE,
1792  sizeof(BMwFaceLoopWalker),
1794  0,
1795  /* Valid restrict masks. */ /* Could add flags here but so far none are used. */
1796 };
1797 
1799  BM_EDGE,
1803  sizeof(BMwEdgeringWalker),
1805  BM_EDGE, /* Valid restrict masks. */
1806 };
1807 
1809  BM_EDGE,
1813  sizeof(BMwEdgeboundaryWalker),
1815  0,
1816 };
1817 
1819  BM_EDGE,
1825  0,
1826 };
1827 
1829  BM_LOOP,
1833  sizeof(BMwUVEdgeWalker),
1835  BM_EDGE, /* Valid restrict masks. */
1836 };
1837 
1839  BM_VERT,
1843  sizeof(BMwConnectedVertexWalker),
1845  BM_VERT, /* Valid restrict masks. */
1846 };
1847 
1850 /* -------------------------------------------------------------------- */
1855  &bmw_VertShellWalker_Type, /* #BMW_VERT_SHELL */
1856  &bmw_LoopShellWalker_Type, /* #BMW_LOOP_SHELL */
1857  &bmw_LoopShellWireWalker_Type, /* #BMW_LOOP_SHELL_WIRE */
1858  &bmw_FaceShellWalker_Type, /* #BMW_FACE_SHELL */
1859  &bmw_EdgeLoopWalker_Type, /* #BMW_EDGELOOP */
1860  &bmw_FaceLoopWalker_Type, /* #BMW_FACELOOP */
1861  &bmw_EdgeringWalker_Type, /* #BMW_EDGERING */
1862  &bmw_EdgeboundaryWalker_Type, /* #BMW_EDGEBOUNDARY */
1863  &bmw_NonManifoldedgeWalker_type, /* #BMW_EDGELOOP_NONMANIFOLD */
1864  &bmw_UVEdgeWalker_Type, /* #BMW_LOOPDATA_ISLAND */
1865  &bmw_IslandboundWalker_Type, /* #BMW_ISLANDBOUND */
1866  &bmw_IslandWalker_Type, /* #BMW_ISLAND */
1867  &bmw_IslandManifoldWalker_Type, /* #BMW_ISLAND_MANIFOLD */
1868  &bmw_ConnectedVertexWalker_Type, /* #BMW_CONNECTED_VERTEX */
1869 };
1870 
1872 
CustomData interface, see also DNA_customdata_types.h.
bool CustomData_data_equals(int type, const void *data1, const void *data2)
Definition: customdata.cc:3973
#define BLI_assert(a)
Definition: BLI_assert.h:46
bool BLI_gset_haskey(const GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:1007
void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp)
Definition: BLI_ghash.c:1032
void BLI_gset_insert(GSet *gs, void *key)
Definition: BLI_ghash.c:962
bool BLI_gset_add(GSet *gs, void *key)
Definition: BLI_ghash.c:969
#define ARRAY_SIZE(arr)
#define UNLIKELY(x)
#define ELEM(...)
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum type
#define BM_DISK_EDGE_NEXT(e, v)
Definition: bmesh_class.h:625
#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_HIDDEN
Definition: bmesh_class.h:472
#define BM_ELEM_CD_GET_VOID_P(ele, offset)
Definition: bmesh_class.h:541
#define BM_elem_flag_test(ele, hflag)
Definition: bmesh_inline.h:12
#define BM_ITER_ELEM(ele, iter, data, itype)
@ BM_FACES_OF_EDGE
@ BM_VERTS_OF_EDGE
@ BM_LOOPS_OF_VERT
@ BM_LOOPS_OF_EDGE
@ BM_EDGES_OF_VERT
@ BM_EDGES_OF_FACE
#define BMO_edge_flag_test(bm, e, oflag)
#define BMO_vert_flag_test(bm, e, oflag)
#define BMO_face_flag_test(bm, e, oflag)
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
Definition: bmesh_query.c:1553
bool BM_edge_is_all_face_flag_test(const BMEdge *e, const char hflag, const bool respect_hide)
Definition: bmesh_query.c:1950
BMLoop * BM_face_other_vert_loop(BMFace *f, BMVert *v_prev, BMVert *v)
Other Loop in Face Sharing a Vertex.
Definition: bmesh_query.c:39
int BM_vert_face_count(const BMVert *v)
Definition: bmesh_query.c:664
int BM_edge_face_count(const BMEdge *e)
Definition: bmesh_query.c:629
BMLoop * BM_loop_other_edge_loop(BMLoop *l, BMVert *v)
Definition: bmesh_query.c:33
int BM_vert_edge_count_nonwire(const BMVert *v)
Definition: bmesh_query.c:617
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
#define BM_edge_face_count_is_equal(e, n)
Definition: bmesh_query.h:247
BLI_INLINE bool BM_edge_is_boundary(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMLoop * l
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
BLI_INLINE BMEdge * bmesh_disk_edge_next(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void * BMW_current_state(BMWalker *walker)
Current Walker State.
void * BMW_walk(BMWalker *walker)
Main Walking Function.
void * BMW_state_add(BMWalker *walker)
Add a new Walker State.
void BMW_state_remove(BMWalker *walker)
Remove Current Walker State.
@ BMW_DEPTH_FIRST
Definition: bmesh_walkers.h:14
@ BMW_BREADTH_FIRST
Definition: bmesh_walkers.h:15
@ BMW_FLAG_TEST_HIDDEN
Definition: bmesh_walkers.h:20
static void * bmw_IslandManifoldWalker_step(BMWalker *walker)
static void bmw_FaceLoopWalker_begin(BMWalker *walker, void *data)
static void bmw_VertShellWalker_begin(BMWalker *walker, void *data)
static bool bmw_edge_is_wire(const BMWalker *walker, const BMEdge *e)
static BMWalker bmw_UVEdgeWalker_Type
static void bmw_ConnectedVertexWalker_begin(BMWalker *walker, void *data)
static void * bmw_VertShellWalker_yield(BMWalker *walker)
static bool bmw_FaceLoopWalker_edge_begins_loop(BMWalker *walker, BMEdge *e)
static void bmw_FaceShellWalker_begin(BMWalker *walker, void *data)
static bool bmw_FaceLoopWalker_include_face(BMWalker *walker, BMLoop *l)
static void * bmw_FaceLoopWalker_step(BMWalker *walker)
static void * bmw_FaceLoopWalker_yield(BMWalker *walker)
static bool bm_edge_is_single(BMEdge *e)
static BMWalker bmw_FaceLoopWalker_Type
static void * bmw_EdgeboundaryWalker_step(BMWalker *walker)
static void * bmw_LoopShellWireWalker_step(BMWalker *walker)
static void bmw_IslandboundWalker_begin(BMWalker *walker, void *data)
static void bmw_LoopShellWalker_step_impl(BMWalker *walker, BMLoop *l)
static void bmw_IslandWalker_begin(BMWalker *walker, void *data)
static void bmw_EdgeboundaryWalker_begin(BMWalker *walker, void *data)
static BMWalker bmw_ConnectedVertexWalker_Type
static void * bmw_UVEdgeWalker_step(BMWalker *walker)
static BMWalker bmw_FaceShellWalker_Type
static BMWalker bmw_EdgeboundaryWalker_Type
static void bmw_EdgeringWalker_begin(BMWalker *walker, void *data)
static void * bmw_EdgeringWalker_yield(BMWalker *walker)
static void bmw_VertShellWalker_visitEdge(BMWalker *walker, BMEdge *e)
#define EDGE_CHECK(e)
static void bmw_LoopShellWalker_visitLoop(BMWalker *walker, BMLoop *l)
static BMLoop * bmw_NonManifoldLoop_find_next_around_vertex(BMLoop *l, BMVert *v, int face_count)
static void * bmw_EdgeLoopWalker_yield(BMWalker *walker)
static void * bmw_FaceShellWalker_yield(BMWalker *walker)
#define BMW_state_remove_r(walker, owalk)
const int bm_totwalkers
static bool bmw_mask_check_edge(BMWalker *walker, BMEdge *e)
static BMWalker bmw_LoopShellWireWalker_Type
static void * bmw_ConnectedVertexWalker_yield(BMWalker *walker)
static void bmw_NonManifoldedgeWalker_begin(BMWalker *walker, void *data)
static void bmw_LoopShellWalker_visitEdgeWire(BMWalker *walker, BMEdge *e)
static void * bmw_LoopShellWalker_step(BMWalker *walker)
static void * bmw_FaceShellWalker_step(BMWalker *walker)
static void bmw_ConnectedVertexWalker_visitVertex(BMWalker *walker, BMVert *v)
static BMWalker bmw_IslandboundWalker_Type
static void * bmw_IslandWalker_step(BMWalker *walker)
static void * bmw_IslandboundWalker_step(BMWalker *walker)
static bool bmw_mask_check_face(BMWalker *walker, BMFace *f)
static void * bmw_UVEdgeWalker_yield(BMWalker *walker)
static void bmw_LoopShellWireWalker_visitVert(BMWalker *walker, BMVert *v, const BMEdge *e_from)
static void bmw_EdgeLoopWalker_begin(BMWalker *walker, void *data)
static void * bmw_NonManifoldedgeWalker_yield(BMWalker *walker)
static BMWalker bmw_EdgeringWalker_Type
static void * bmw_IslandboundWalker_yield(BMWalker *walker)
static bool bmw_mask_check_vert(BMWalker *walker, BMVert *v)
static void bmw_FaceShellWalker_visitEdge(BMWalker *walker, BMEdge *e)
static void * bmw_NonManifoldedgeWalker_step(BMWalker *walker)
static void bmw_LoopShellWireWalker_begin(BMWalker *walker, void *data)
static void * bmw_VertShellWalker_step(BMWalker *walker)
static void * bmw_LoopShellWireWalker_yield(BMWalker *walker)
static void bmw_UVEdgeWalker_begin(BMWalker *walker, void *data)
static BMWalker bmw_LoopShellWalker_Type
static void * bmw_ConnectedVertexWalker_step(BMWalker *walker)
static void * bmw_IslandWalker_step_ex(BMWalker *walker, bool only_manifold)
static void * bmw_IslandWalker_yield(BMWalker *walker)
static void * bmw_EdgeLoopWalker_step(BMWalker *walker)
static BMWalker bmw_EdgeLoopWalker_Type
static BMWalker bmw_VertShellWalker_Type
static BMWalker bmw_IslandManifoldWalker_Type
static void bmw_LoopShellWalker_begin(BMWalker *walker, void *data)
static BMWalker bmw_NonManifoldedgeWalker_type
static BMWalker bmw_IslandWalker_Type
static void * bmw_LoopShellWalker_yield(BMWalker *walker)
static void * bmw_EdgeringWalker_step(BMWalker *walker)
static void * bmw_EdgeboundaryWalker_yield(BMWalker *walker)
BMWalker * bm_walker_types[]
struct BMwNonManifoldEdgeLoopWalker BMwNonManifoldEdgeLoopWalker
struct BMwIslandWalker BMwIslandWalker
struct BMwFaceLoopWalker BMwFaceLoopWalker
struct BMwEdgeLoopWalker BMwEdgeLoopWalker
struct BMwIslandboundWalker BMwIslandboundWalker
struct BMwEdgeringWalker BMwEdgeringWalker
struct BMwConnectedVertexWalker BMwConnectedVertexWalker
struct BMwLoopShellWalker BMwLoopShellWalker
struct BMwEdgeboundaryWalker BMwEdgeboundaryWalker
struct BMwLoopShellWireWalker BMwLoopShellWireWalker
struct BMwShellWalker BMwShellWalker
struct BMwUVEdgeWalker BMwUVEdgeWalker
int len
Definition: draw_manager.c:108
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
static ulong * next
struct BMLoop * l
Definition: bmesh_class.h:128
BMHeader head
Definition: bmesh_class.h:243
int len
Definition: bmesh_class.h:267
char htype
Definition: bmesh_class.h:64
BMHeader head
Definition: bmesh_class.h:145
struct BMVert * v
Definition: bmesh_class.h:153
struct BMEdge * e
Definition: bmesh_class.h:164
struct BMLoop * radial_next
Definition: bmesh_class.h:204
struct BMLoop * prev
Definition: bmesh_class.h:233
struct BMFace * f
Definition: bmesh_class.h:171
struct BMLoop * next
Definition: bmesh_class.h:233
struct BMEdge * e
Definition: bmesh_class.h:97
BMHeader head
Definition: bmesh_class.h:85
struct GSet * visit_set_alt
Definition: bmesh_walkers.h:49
BMWFlag flag
Definition: bmesh_walkers.h:46
short mask_face
Definition: bmesh_walkers.h:44
struct GSet * visit_set
Definition: bmesh_walkers.h:48
BMesh * bm
Definition: bmesh_walkers.h:36
short mask_edge
Definition: bmesh_walkers.h:43
short mask_vert
Definition: bmesh_walkers.h:42
CustomData ldata
Definition: bmesh_class.h:337
CustomDataLayer * layers