Blender V5.3
bmesh_walkers_impl.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include <cstring>
12
13#include "BLI_utildefines.hh"
14
15#include "BKE_customdata.hh"
16
17#include "bmesh.hh"
19
20namespace blender {
21
22/* Pop into stack memory (common operation). */
23#define BMW_state_remove_r(walker, owalk) \
24 { \
25 memcpy(owalk, BMW_current_state(walker), sizeof(*(owalk))); \
26 BMW_state_remove(walker); \
27 } \
28 (void)0
29
30/* -------------------------------------------------------------------- */
33
34static bool bmw_mask_check_vert(BMWalker *walker, BMVert *v)
35{
37 return false;
38 }
39 if (walker->mask_vert && !BMO_vert_flag_test(walker->bm, v, walker->mask_vert)) {
40 return false;
41 }
42 return true;
43}
44
45static bool bmw_mask_check_edge(BMWalker *walker, BMEdge *e)
46{
48 return false;
49 }
50 if (walker->mask_edge && !BMO_edge_flag_test(walker->bm, e, walker->mask_edge)) {
51 return false;
52 }
53 return true;
54}
55
56static bool bmw_mask_check_face(BMWalker *walker, BMFace *f)
57{
59 return false;
60 }
61 if (walker->mask_face && !BMO_face_flag_test(walker->bm, f, walker->mask_face)) {
62 return false;
63 }
64 return true;
65}
66
68
69/* -------------------------------------------------------------------- */
72
76static bool bmw_edge_is_wire(const BMWalker *walker, const BMEdge *e)
77{
78 if (walker->flag & BMW_FLAG_TEST_HIDDEN) {
79 /* Check if this is a wire edge, ignoring hidden faces. */
80 if (BM_edge_is_wire(e)) {
81 return true;
82 }
84 }
85 return BM_edge_is_wire(e);
86}
87
89
90/* -------------------------------------------------------------------- */
101
103{
104 BMwShellWalker *shellWalk = nullptr;
105
106 if (walker->visit_set->contains(e)) {
107 return;
108 }
109
110 if (!bmw_mask_check_edge(walker, e)) {
111 return;
112 }
113
114 shellWalk = static_cast<BMwShellWalker *>(BMW_state_add(walker));
115 shellWalk->curedge = e;
116 walker->visit_set->add(e);
117}
118
119static void bmw_VertShellWalker_begin(BMWalker *walker, void *data)
120{
121 BMIter eiter;
122 BMHeader *h = static_cast<BMHeader *>(data);
123 BMEdge *e;
124 BMVert *v;
125
126 if (h == nullptr) [[unlikely]] {
127 return;
128 }
129
130 switch (h->htype) {
131 case BM_VERT: {
132 /* Starting the walk at a vert, add all the edges to the work-list. */
133 v = reinterpret_cast<BMVert *>(h);
134 BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
136 }
137 break;
138 }
139
140 case BM_EDGE: {
141 /* Starting the walk at an edge, add the single edge to the work-list. */
142 e = reinterpret_cast<BMEdge *>(h);
144 break;
145 }
146 default:
147 BLI_assert(0);
148 }
149}
150
152{
153 BMwShellWalker *shellWalk = static_cast<BMwShellWalker *>(BMW_current_state(walker));
154 return shellWalk->curedge;
155}
156
158{
159 BMwShellWalker *swalk, owalk;
160 BMEdge *e, *e2;
161 BMVert *v;
162 BMIter iter;
163 int i;
164
165 BMW_state_remove_r(walker, &owalk);
166 swalk = &owalk;
167
168 e = swalk->curedge;
169
170 for (i = 0; i < 2; i++) {
171 v = i ? e->v2 : e->v1;
172 BM_ITER_ELEM (e2, &iter, v, BM_EDGES_OF_VERT) {
174 }
175 }
176
177 return e;
178}
179
180#if 0
181static void *bmw_VertShellWalker_step(BMWalker *walker)
182{
183 BMEdge *curedge, *next = nullptr;
184 BMVert *v_old = nullptr;
185 bool restrictpass = true;
186 BMwShellWalker shellWalk = *((BMwShellWalker *)BMW_current_state(walker));
187
188 if (!walker->visit_set->contains(shellWalk.base)) {
189 walker->visit_set->add(shellWalk.base);
190 }
191
192 BMW_state_remove(walker);
193
194 /* Find the next edge whose other vertex has not been visited. */
195 curedge = shellWalk.curedge;
196 do {
197 if (!walker->visit_set->contains(curedge)) {
198 if (!walker->visibility_flag ||
199 (walker->visibility_flag &&
200 BMO_edge_flag_test(walker->bm, curedge, walker->visibility_flag)))
201 {
202 BMwShellWalker *newstate;
203
204 v_old = BM_edge_other_vert(curedge, shellWalk.base);
205
206 /* Push a new state onto the stack. */
207 newState = BMW_state_add(walker);
208 walker->visit_set->add(curedge);
209
210 /* Populate the new state. */
211
212 newState->base = v_old;
213 newState->curedge = curedge;
214 }
215 }
216 } while ((curedge = bmesh_disk_edge_next(curedge, shellWalk.base)) != shellWalk.curedge);
217
218 return shellWalk.curedge;
219}
220#endif
221
223
224/* -------------------------------------------------------------------- */
232
234{
235 BMwLoopShellWalker *shellWalk = nullptr;
236
237 if (walker->visit_set->contains(l)) {
238 return;
239 }
240
241 if (!bmw_mask_check_face(walker, l->f)) {
242 return;
243 }
244
245 shellWalk = static_cast<BMwLoopShellWalker *>(BMW_state_add(walker));
246 shellWalk->curloop = l;
247 walker->visit_set->add(l);
248}
249
250static void bmw_LoopShellWalker_begin(BMWalker *walker, void *data)
251{
252 BMIter iter;
253 BMHeader *h = static_cast<BMHeader *>(data);
254
255 if (h == nullptr) [[unlikely]] {
256 return;
257 }
258
259 switch (h->htype) {
260 case BM_LOOP: {
261 /* Starting the walk at a vert, add all the edges to the work-list. */
262 BMLoop *l = reinterpret_cast<BMLoop *>(h);
264 break;
265 }
266
267 case BM_VERT: {
268 BMVert *v = reinterpret_cast<BMVert *>(h);
269 BMLoop *l;
270 BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
272 }
273 break;
274 }
275 case BM_EDGE: {
276 BMEdge *e = reinterpret_cast<BMEdge *>(h);
277 BMLoop *l;
278 BM_ITER_ELEM (l, &iter, e, BM_LOOPS_OF_EDGE) {
280 }
281 break;
282 }
283 case BM_FACE: {
284 BMFace *f = reinterpret_cast<BMFace *>(h);
286 /* Walker will handle other loops within the face. */
288 break;
289 }
290 default:
291 BLI_assert(0);
292 }
293}
294
296{
297 BMwLoopShellWalker *shellWalk = static_cast<BMwLoopShellWalker *>(BMW_current_state(walker));
298 return shellWalk->curloop;
299}
300
302{
303 BMEdge *e_edj_pair[2];
304 int i;
305
306 /* Seems paranoid, but one caller also walks edges. */
308
311
312 e_edj_pair[0] = l->e;
313 e_edj_pair[1] = l->prev->e;
314
315 for (i = 0; i < 2; i++) {
316 BMEdge *e = e_edj_pair[i];
317 if (bmw_mask_check_edge(walker, e)) {
318 BMLoop *l_iter, *l_first;
319
320 l_iter = l_first = e->l;
321 do {
322 BMLoop *l_radial = (l_iter->v == l->v) ? l_iter : l_iter->next;
323 BLI_assert(l_radial->v == l->v);
324 if (l != l_radial) {
325 bmw_LoopShellWalker_visitLoop(walker, l_radial);
326 }
327 } while ((l_iter = l_iter->radial_next) != l_first);
328 }
329 }
330}
331
333{
334 BMwLoopShellWalker *swalk, owalk;
335 BMLoop *l;
336
337 BMW_state_remove_r(walker, &owalk);
338 swalk = &owalk;
339
340 l = swalk->curloop;
342
343 return l;
344}
345
347
348/* -------------------------------------------------------------------- */
360
362{
363 BMwLoopShellWireWalker *shellWalk = nullptr;
364
365 BLI_assert(bmw_edge_is_wire(walker, e));
366
367 if (walker->visit_set_alt->contains(e)) {
368 return;
369 }
370
371 if (!bmw_mask_check_edge(walker, e)) {
372 return;
373 }
374
375 shellWalk = static_cast<BMwLoopShellWireWalker *>(BMW_state_add(walker));
376 shellWalk->curelem = reinterpret_cast<BMElem *>(e);
377 walker->visit_set_alt->add(e);
378}
379
380static void bmw_LoopShellWireWalker_visitVert(BMWalker *walker, BMVert *v, const BMEdge *e_from)
381{
382 BMEdge *e;
383
385
386 if (walker->visit_set_alt->contains(v)) {
387 return;
388 }
389
390 if (!bmw_mask_check_vert(walker, v)) {
391 return;
392 }
393
394 e = v->e;
395 do {
396 if (bmw_edge_is_wire(walker, e) && (e != e_from)) {
397 BMVert *v_other;
398 BMIter iter;
399 BMLoop *l;
400
402
403 /* Check if we step onto a non-wire vertex. */
404 v_other = BM_edge_other_vert(e, v);
405 BM_ITER_ELEM (l, &iter, v_other, BM_LOOPS_OF_VERT) {
406
408 }
409 }
410 } while ((e = BM_DISK_EDGE_NEXT(e, v)) != v->e);
411
412 walker->visit_set_alt->add(v);
413}
414
415static void bmw_LoopShellWireWalker_begin(BMWalker *walker, void *data)
416{
417 BMHeader *h = static_cast<BMHeader *>(data);
418
419 if (h == nullptr) [[unlikely]] {
420 return;
421 }
422
424
425 switch (h->htype) {
426 case BM_LOOP: {
427 BMLoop *l = reinterpret_cast<BMLoop *>(h);
428 bmw_LoopShellWireWalker_visitVert(walker, l->v, nullptr);
429 break;
430 }
431
432 case BM_VERT: {
433 BMVert *v = reinterpret_cast<BMVert *>(h);
434 if (v->e) {
435 bmw_LoopShellWireWalker_visitVert(walker, v, nullptr);
436 }
437 break;
438 }
439 case BM_EDGE: {
440 BMEdge *e = reinterpret_cast<BMEdge *>(h);
441 if (bmw_mask_check_edge(walker, e)) {
442 bmw_LoopShellWireWalker_visitVert(walker, e->v1, nullptr);
443 bmw_LoopShellWireWalker_visitVert(walker, e->v2, nullptr);
444 }
445 else if (e->l) {
446 BMLoop *l_iter, *l_first;
447
448 l_iter = l_first = e->l;
449 do {
450 bmw_LoopShellWalker_visitLoop(walker, l_iter);
451 bmw_LoopShellWalker_visitLoop(walker, l_iter->next);
452 } while ((l_iter = l_iter->radial_next) != l_first);
453 }
454 break;
455 }
456 case BM_FACE: {
457 /* Wire verts will be walked over. */
458 break;
459 }
460 default:
461 BLI_assert(0);
462 }
463}
464
466{
467 BMwLoopShellWireWalker *shellWalk = static_cast<BMwLoopShellWireWalker *>(
468 BMW_current_state(walker));
469 return shellWalk->curelem;
470}
471
473{
474 BMwLoopShellWireWalker *swalk, owalk;
475
476 BMW_state_remove_r(walker, &owalk);
477 swalk = &owalk;
478
479 if (swalk->curelem->head.htype == BM_LOOP) {
480 BMLoop *l = reinterpret_cast<BMLoop *>(swalk->curelem);
481
483
484 bmw_LoopShellWireWalker_visitVert(walker, l->v, nullptr);
485
486 return l;
487 }
488
489 BMEdge *e = reinterpret_cast<BMEdge *>(swalk->curelem);
490
492
495
496 return e;
497}
498
500
501/* -------------------------------------------------------------------- */
507
509{
510 BMwShellWalker *shellWalk = nullptr;
511
512 if (walker->visit_set->contains(e)) {
513 return;
514 }
515
516 if (!bmw_mask_check_edge(walker, e)) {
517 return;
518 }
519
520 shellWalk = static_cast<BMwShellWalker *>(BMW_state_add(walker));
521 shellWalk->curedge = e;
522 walker->visit_set->add(e);
523}
524
525static void bmw_FaceShellWalker_begin(BMWalker *walker, void *data)
526{
527 BMEdge *e = static_cast<BMEdge *>(data);
529}
530
532{
533 BMwShellWalker *shellWalk = static_cast<BMwShellWalker *>(BMW_current_state(walker));
534 return shellWalk->curedge;
535}
536
538{
539 BMwShellWalker *swalk, owalk;
540 BMEdge *e, *e2;
541 BMIter iter;
542
543 BMW_state_remove_r(walker, &owalk);
544 swalk = &owalk;
545
546 e = swalk->curedge;
547
548 if (e->l) {
549 BMLoop *l_iter, *l_first;
550
551 l_iter = l_first = e->l;
552 do {
553 BM_ITER_ELEM (e2, &iter, l_iter->f, BM_EDGES_OF_FACE) {
554 if (e2 != e) {
556 }
557 }
558 } while ((l_iter = l_iter->radial_next) != l_first);
559 }
560
561 return e;
562}
563
565
566/* -------------------------------------------------------------------- */
573
575{
577
578 if (walker->visit_set->contains(v)) {
579 /* Already visited. */
580 return;
581 }
582
583 if (!bmw_mask_check_vert(walker, v)) {
584 /* Not flagged for walk. */
585 return;
586 }
587
588 vwalk = static_cast<BMwConnectedVertexWalker *>(BMW_state_add(walker));
589 vwalk->curvert = v;
590 walker->visit_set->add(v);
591}
592
594{
595 BMVert *v = static_cast<BMVert *>(data);
597}
598
600{
602 BMW_current_state(walker));
603 return vwalk->curvert;
604}
605
607{
608 BMwConnectedVertexWalker *vwalk, owalk;
609 BMVert *v, *v2;
610 BMEdge *e;
611 BMIter iter;
612
613 BMW_state_remove_r(walker, &owalk);
614 vwalk = &owalk;
615
616 v = vwalk->curvert;
617
618 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
620 if (!walker->visit_set->contains(v2)) {
622 }
623 }
624
625 return v;
626}
627
629
630/* -------------------------------------------------------------------- */
642
643static void bmw_IslandboundWalker_begin(BMWalker *walker, void *data)
644{
645 BMLoop *l = static_cast<BMLoop *>(data);
646 BMwIslandboundWalker *iwalk = nullptr;
647
648 iwalk = static_cast<BMwIslandboundWalker *>(BMW_state_add(walker));
649
650 iwalk->base = iwalk->curloop = l;
651 iwalk->lastv = l->v;
652
653 walker->visit_set->add(data);
654}
655
657{
658 BMwIslandboundWalker *iwalk = static_cast<BMwIslandboundWalker *>(BMW_current_state(walker));
659
660 return iwalk->curloop;
661}
662
664{
665 BMwIslandboundWalker *iwalk, owalk;
666 BMVert *v;
667 BMEdge *e;
668 BMFace *f;
669 BMLoop *l;
670
671 memcpy(&owalk, BMW_current_state(walker), sizeof(owalk));
672 /* Normally we'd remove here, but delay until after error checking. */
673 iwalk = &owalk;
674
675 l = iwalk->curloop;
676 e = l->e;
677
678 v = BM_edge_other_vert(e, iwalk->lastv);
679
680 /* Pop off current state. */
681 BMW_state_remove(walker);
682
683 f = l->f;
684
685 while (true) {
687 if (BM_loop_is_manifold(l)) {
688 l = l->radial_next;
689 f = l->f;
690 e = l->e;
691
692 if (!bmw_mask_check_face(walker, f)) {
693 l = l->radial_next;
694 break;
695 }
696 }
697 else {
698 /* Treat non-manifold edges as boundaries. */
699 f = l->f;
700 e = l->e;
701 break;
702 }
703 }
704
705 if (l == owalk.curloop) {
706 return nullptr;
707 }
708 if (walker->visit_set->contains(l)) {
709 return owalk.curloop;
710 }
711
712 walker->visit_set->add(l);
713 iwalk = static_cast<BMwIslandboundWalker *>(BMW_state_add(walker));
714 iwalk->base = owalk.base;
715
716#if 0
717 if (!BMO_face_flag_test(walker->bm, l->f, walker->visibility_flag)) {
718 iwalk->curloop = l->radial_next;
719 }
720 else {
721 iwalk->curloop = l;
722 }
723#else
724 iwalk->curloop = l;
725#endif
726 iwalk->lastv = v;
727
728 return owalk.curloop;
729}
730
732
733/* -------------------------------------------------------------------- */
740
741static void bmw_IslandWalker_begin(BMWalker *walker, void *data)
742{
743 BMwIslandWalker *iwalk = nullptr;
744
745 if (!bmw_mask_check_face(walker, static_cast<BMFace *>(data))) {
746 return;
747 }
748
749 iwalk = static_cast<BMwIslandWalker *>(BMW_state_add(walker));
750 walker->visit_set->add(data);
751
752 iwalk->cur = static_cast<BMFace *>(data);
753}
754
755static void *bmw_IslandWalker_yield(BMWalker *walker)
756{
757 BMwIslandWalker *iwalk = static_cast<BMwIslandWalker *>(BMW_current_state(walker));
758
759 return iwalk->cur;
760}
761
762static void *bmw_IslandWalker_step_ex(BMWalker *walker, bool only_manifold)
763{
764 BMwIslandWalker *iwalk, owalk;
765 BMLoop *l_iter, *l_first;
766
767 BMW_state_remove_r(walker, &owalk);
768 iwalk = &owalk;
769
770 l_iter = l_first = BM_FACE_FIRST_LOOP(iwalk->cur);
771 do {
772 /* Could skip loop here too, but don't add unless we need it. */
773 if (!bmw_mask_check_edge(walker, l_iter->e)) {
774 continue;
775 }
776
777 BMLoop *l_radial_iter;
778
779 if (only_manifold && (l_iter->radial_next != l_iter)) {
780 int face_count = 1;
781 /* Check other faces (not this one), ensure only one other Can be walked onto. */
782 l_radial_iter = l_iter->radial_next;
783 do {
784 if (bmw_mask_check_face(walker, l_radial_iter->f)) {
785 face_count++;
786 if (face_count == 3) {
787 break;
788 }
789 }
790 } while ((l_radial_iter = l_radial_iter->radial_next) != l_iter);
791
792 if (face_count != 2) {
793 continue;
794 }
795 }
796
797 l_radial_iter = l_iter;
798 while ((l_radial_iter = l_radial_iter->radial_next) != l_iter) {
799 BMFace *f = l_radial_iter->f;
800
801 if (!bmw_mask_check_face(walker, f)) {
802 continue;
803 }
804
805 /* Saves checking #BLI_gset_haskey below (manifold edges there's a 50% chance). */
806 if (f == iwalk->cur) {
807 continue;
808 }
809
810 if (walker->visit_set->contains(f)) {
811 continue;
812 }
813
814 iwalk = static_cast<BMwIslandWalker *>(BMW_state_add(walker));
815 iwalk->cur = f;
816 walker->visit_set->add(f);
817 break;
818 }
819 } while ((l_iter = l_iter->next) != l_first);
820
821 return owalk.cur;
822}
823
824static void *bmw_IslandWalker_step(BMWalker *walker)
825{
826 return bmw_IslandWalker_step_ex(walker, false);
827}
828
833{
834 return bmw_IslandWalker_step_ex(walker, true);
835}
836
838
839/* -------------------------------------------------------------------- */
844
845/* utility function to see if an edge is a part of an ngon boundary */
847{
848 return (BM_edge_is_boundary(e) && (e->l->f->len > 4) &&
849 (BM_edge_is_boundary(e->l->next->e) || BM_edge_is_boundary(e->l->prev->e)));
850}
851
853 BMWalker *walker, BMVert *v, BMEdge *e, BMLoop *l, bool (*edge_mark_check_fn)(const BMEdge *))
854{
855 /* When starting on a mark, stop when the next edge does not have the mark.
856 * Otherwise, stop when any edge connected to the next vert has the mark. */
857 if (edge_mark_check_fn(e)) {
858 if (!edge_mark_check_fn(l->e) &&
861 {
862 return true;
863 }
864 }
865 else {
866 BMIter eiter;
867 BMEdge *e_other;
868 BM_ITER_ELEM (e_other, &eiter, v, BM_EDGES_OF_VERT) {
869 if (edge_mark_check_fn(e_other) &&
870 !((walker->flag & BMW_FLAG_TEST_HIDDEN) && BM_elem_flag_test(e_other, BM_ELEM_HIDDEN)) &&
871 !BM_edge_is_wire(e_other))
872 {
873 return true;
874 }
875 }
876 }
877 return false;
878}
879
881 BMVert *v,
882 BMEdge *e,
883 BMLoop *l)
884{
885 if ((walker->delimit & BMW_DELIMIT_EDGE_MARK_SEAM) &&
887 walker,
888 v,
889 e,
890 l,
891 [](const BMEdge *e) -> bool { return BM_elem_flag_test(e, BM_ELEM_SEAM); }))
892 {
893 return true;
894 }
895 if ((walker->delimit & BMW_DELIMIT_EDGE_MARK_SHARP) &&
897 walker,
898 v,
899 e,
900 l,
901 [](const BMEdge *e) -> bool { return !BM_elem_flag_test(e, BM_ELEM_SMOOTH); }))
902 {
903 return true;
904 }
905 return false;
906}
907
908static void bmw_EdgeLoopWalker_begin(BMWalker *walker, void *data)
909{
910 BMwEdgeLoopWalker *lwalk = nullptr, owalk, *owalk_pt;
911 BMEdge *e = static_cast<BMEdge *>(data);
912 BMVert *v;
913 const int vert_edge_count[2] = {
916 };
917 const int vert_face_count[2] = {
920 };
921
922 v = e->v1;
923
924 lwalk = static_cast<BMwEdgeLoopWalker *>(BMW_state_add(walker));
925 walker->visit_set->add(e);
926
927 lwalk->cur = lwalk->start = e;
928 lwalk->lastv = lwalk->startv = v;
930 lwalk->is_single = (lwalk->is_boundary && bm_edge_is_single(e));
931
996 if ((lwalk->is_boundary == false) &&
997 /* Without checking the face count, the 3 edges could be this edge
998 * plus two boundary edges (which would not be stepped over), see #84906. */
999 ((vert_edge_count[0] == 3 && vert_face_count[0] == 3) ||
1000 (vert_edge_count[1] == 3 && vert_face_count[1] == 3)))
1001 {
1002 BMIter iter;
1003 BMFace *f_iter;
1004 BMFace *f_best = nullptr;
1005
1006 BM_ITER_ELEM (f_iter, &iter, e, BM_FACES_OF_EDGE) {
1007 if (f_best == nullptr || f_best->len < f_iter->len) {
1008 f_best = f_iter;
1009 }
1010 }
1011
1012 if (f_best) {
1013 /* Only use hub selection for 5+ sides else this could
1014 * conflict with normal edge loop selection. */
1015 lwalk->f_hub = f_best->len > 4 ? f_best : nullptr;
1016 }
1017 else {
1018 /* Edge doesn't have any faces connected to it. */
1019 lwalk->f_hub = nullptr;
1020 }
1021 }
1022 else {
1023 lwalk->f_hub = nullptr;
1024 }
1025
1026 /* Rewind. */
1027 while ((owalk_pt = static_cast<BMwEdgeLoopWalker *>(BMW_current_state(walker)))) {
1028 owalk = *(owalk_pt);
1029 BMW_walk(walker);
1030 }
1031
1032 lwalk = static_cast<BMwEdgeLoopWalker *>(BMW_state_add(walker));
1033 *lwalk = owalk;
1034
1035 lwalk->lastv = lwalk->startv = BM_edge_other_vert(owalk.cur, lwalk->lastv);
1036
1037 walker->visit_set->clear();
1038 walker->visit_set->add(owalk.cur);
1039}
1040
1042{
1043 BMwEdgeLoopWalker *lwalk = static_cast<BMwEdgeLoopWalker *>(BMW_current_state(walker));
1044
1045 return lwalk->cur;
1046}
1047
1049{
1050 BMwEdgeLoopWalker *lwalk, owalk;
1051 BMEdge *e, *nexte = nullptr;
1052 BMLoop *l;
1053 BMVert *v;
1054
1055 BMW_state_remove_r(walker, &owalk);
1056 lwalk = &owalk;
1057
1058 e = lwalk->cur;
1059 l = e->l;
1060
1061 if (owalk.f_hub) { /* INTERIOR NGON EDGE */
1062 int vert_edge_tot;
1063
1064 v = BM_edge_other_vert(e, lwalk->lastv);
1065
1066 vert_edge_tot = BM_vert_edge_count_nonwire(v);
1067
1068 if (vert_edge_tot == 3) {
1069 l = BM_face_other_vert_loop(owalk.f_hub, lwalk->lastv, v);
1070 nexte = BM_edge_exists(v, l->v);
1071
1072 if (bmw_mask_check_edge(walker, nexte) && !walker->visit_set->contains(nexte) &&
1073 /* Never step onto a boundary edge, this gives odd-results. */
1074 (BM_edge_is_boundary(nexte) == false))
1075 {
1076 lwalk = static_cast<BMwEdgeLoopWalker *>(BMW_state_add(walker));
1077 lwalk->cur = nexte;
1078 lwalk->lastv = v;
1079
1080 lwalk->is_boundary = owalk.is_boundary;
1081 lwalk->is_single = owalk.is_single;
1082 lwalk->f_hub = owalk.f_hub;
1083
1084 walker->visit_set->add(nexte);
1085 }
1086 }
1087 }
1088 else if (l == nullptr) { /* WIRE EDGE */
1089 BMIter eiter;
1090
1091 /* Match trunk: mark all connected wire edges. */
1092 for (int i = 0; i < 2; i++) {
1093 v = i ? e->v2 : e->v1;
1094
1095 BM_ITER_ELEM (nexte, &eiter, v, BM_EDGES_OF_VERT) {
1096 if ((nexte->l == nullptr) && bmw_mask_check_edge(walker, nexte) &&
1097 !walker->visit_set->contains(nexte))
1098 {
1099 lwalk = static_cast<BMwEdgeLoopWalker *>(BMW_state_add(walker));
1100 lwalk->cur = nexte;
1101 lwalk->lastv = v;
1102
1103 lwalk->is_boundary = owalk.is_boundary;
1104 lwalk->is_single = owalk.is_single;
1105 lwalk->f_hub = owalk.f_hub;
1106
1107 walker->visit_set->add(nexte);
1108 }
1109 }
1110 }
1111 }
1112 else if (owalk.is_boundary == false) { /* NORMAL EDGE WITH FACES */
1113 int vert_edge_tot;
1114
1115 v = BM_edge_other_vert(e, lwalk->lastv);
1116
1117 vert_edge_tot = BM_vert_edge_count_nonwire(v);
1118
1119 /* Typical looping over edges in the middle of a mesh.
1120 * Why use 2 here at all? - for internal ngon loops it can be useful. */
1121 if (ELEM(vert_edge_tot, 4, 2)) {
1122 int i_opposite = vert_edge_tot / 2;
1123 int i = 0;
1124 do {
1126 if (BM_edge_is_manifold(l->e)) {
1127 l = l->radial_next;
1128 }
1129 else {
1130 l = nullptr;
1131 break;
1132 }
1133 } while (++i != i_opposite);
1134 }
1135 else {
1136 l = nullptr;
1137 }
1138
1139 if (l && bmw_EdgeLoopWalker_delimit_mark_check(walker, v, e, l)) {
1140 l = nullptr;
1141 }
1142
1143 if (l != nullptr) {
1144 if (l != e->l && bmw_mask_check_edge(walker, l->e) && !walker->visit_set->contains(l->e)) {
1145 lwalk = static_cast<BMwEdgeLoopWalker *>(BMW_state_add(walker));
1146 lwalk->cur = l->e;
1147 lwalk->lastv = v;
1148
1149 lwalk->is_boundary = owalk.is_boundary;
1150 lwalk->is_single = owalk.is_single;
1151 lwalk->f_hub = owalk.f_hub;
1152
1153 walker->visit_set->add(l->e);
1154 }
1155 }
1156 }
1157 else if (owalk.is_boundary == true) { /* BOUNDARY EDGE WITH FACES */
1158 int vert_edge_tot;
1159
1160 v = BM_edge_other_vert(e, lwalk->lastv);
1161
1162 vert_edge_tot = BM_vert_edge_count_nonwire(v);
1163
1164 /* Check if any corner delimits should stop the step. */
1165 bool has_corner_delimit = false;
1166 if ((walker->delimit & BMW_DELIMIT_EDGE_LOOP_INNER_CORNERS) != 0) {
1167 if (vert_edge_tot > 3) {
1168 has_corner_delimit = true;
1169 }
1170 }
1171 if ((walker->delimit & BMW_DELIMIT_EDGE_LOOP_OUTER_CORNERS) != 0 &&
1172 has_corner_delimit == false)
1173 {
1174 if (vert_edge_tot == 2 && bm_edge_is_single(e) == false) {
1175 has_corner_delimit = true;
1176 }
1177 }
1178
1179 /* Find next boundary edge in the fan. */
1180 if (has_corner_delimit == false) {
1181 do {
1183 if (BM_edge_is_manifold(l->e)) {
1184 l = l->radial_next;
1185 }
1186 else if (BM_edge_is_boundary(l->e)) {
1187 break;
1188 }
1189 else {
1190 l = nullptr;
1191 break;
1192 }
1193 } while (true);
1194 }
1195
1196 if (l && bmw_EdgeLoopWalker_delimit_mark_check(walker, v, e, l)) {
1197 l = nullptr;
1198 }
1199
1200 /* Stop at delimiting n-gons here so that Rewind picks the correct edge to start from. */
1201 if (l && (walker->delimit & BMW_DELIMIT_EDGE_LOOP_NGONS) != 0) {
1202 if (owalk.is_single != bm_edge_is_single(l->e)) {
1203 l = nullptr;
1204 }
1205 }
1206
1207 if (l != nullptr) {
1208 if (l != e->l && bmw_mask_check_edge(walker, l->e) && !walker->visit_set->contains(l->e)) {
1209 lwalk = static_cast<BMwEdgeLoopWalker *>(BMW_state_add(walker));
1210 lwalk->cur = l->e;
1211 lwalk->lastv = v;
1212
1213 lwalk->is_boundary = owalk.is_boundary;
1214 lwalk->is_single = owalk.is_single;
1215 lwalk->f_hub = owalk.f_hub;
1216
1217 walker->visit_set->add(l->e);
1218 }
1219 }
1220 }
1221
1222 return owalk.cur;
1223}
1224
1226
1227/* -------------------------------------------------------------------- */
1234
1240{
1241 /* Face must have degree 4. */
1242 if (l->f->len != 4) {
1243 return false;
1244 }
1245
1246 if (!bmw_mask_check_face(walker, l->f)) {
1247 return false;
1248 }
1249
1250 /* The face must not have been already visited. */
1251 if (walker->visit_set->contains(l->f) && walker->visit_set_alt->contains(l->e)) {
1252 return false;
1253 }
1254
1255 return true;
1256}
1257
1258/* Check whether the face loop can start from the given edge. */
1260{
1261 /* There is no face loop starting from a wire edge. */
1262 if (BM_edge_is_wire(e)) {
1263 return false;
1264 }
1265
1266 /* Don't start a loop from a boundary edge if it cannot be extended to cover any faces. */
1267 if (BM_edge_is_boundary(e)) {
1268 if (!bmw_FaceLoopWalker_include_face(walker, e->l)) {
1269 return false;
1270 }
1271 }
1272
1273 /* Don't start a face loop from non-manifold edges. */
1274 if (!BM_edge_is_manifold(e)) {
1275 return false;
1276 }
1277
1278 return true;
1279}
1280
1282 BMEdge *e,
1283 BMFace *f_b,
1284 const BMWDelimitFlag delimit)
1285{
1288 return true;
1289 }
1291 return true;
1292 }
1293 }
1294
1295 if (delimit & BMW_DELIMIT_FACE_MARK_MATERIAL) {
1296 if (f_a->mat_nr != f_b->mat_nr) {
1297 return true;
1298 }
1299 }
1300
1301 return false;
1302}
1303
1304static void bmw_FaceLoopWalker_begin(BMWalker *walker, void *data)
1305{
1306 BMwFaceLoopWalker *lwalk, owalk, *owalk_pt;
1307 BMEdge *e = static_cast<BMEdge *>(data);
1308 // BMesh *bm = walker->bm; /* UNUSED */
1309 // int fcount = BM_edge_face_count(e); /* UNUSED */
1310
1311 if (!bmw_FaceLoopWalker_edge_begins_loop(walker, e)) {
1312 return;
1313 }
1314
1315 lwalk = static_cast<BMwFaceLoopWalker *>(BMW_state_add(walker));
1316 lwalk->l = e->l;
1317 lwalk->no_calc = false;
1318 walker->visit_set->add(lwalk->l->f);
1319
1320 /* Rewind. */
1321 while ((owalk_pt = static_cast<BMwFaceLoopWalker *>(BMW_current_state(walker)))) {
1322 owalk = *(owalk_pt);
1323 BMW_walk(walker);
1324 }
1325
1326 lwalk = static_cast<BMwFaceLoopWalker *>(BMW_state_add(walker));
1327 *lwalk = owalk;
1328 lwalk->no_calc = false;
1329
1330 walker->visit_set_alt->clear();
1331 walker->visit_set_alt->add(lwalk->l->e);
1332
1333 walker->visit_set->clear();
1334 walker->visit_set->add(lwalk->l->f);
1335
1336 /* When starting on a delimiting edge, add both sides so both directions are walked. */
1338 lwalk->l->f, lwalk->l->e, lwalk->l->radial_next->f, walker->delimit))
1339 {
1340 BMwFaceLoopWalker *lwalk_alt = static_cast<BMwFaceLoopWalker *>(BMW_state_add(walker));
1341 lwalk_alt->l = lwalk->l->radial_next;
1342 lwalk_alt->no_calc = false;
1343 walker->visit_set->add(lwalk_alt->l->f);
1344 }
1345}
1346
1348{
1349 BMwFaceLoopWalker *lwalk = static_cast<BMwFaceLoopWalker *>(BMW_current_state(walker));
1350
1351 if (!lwalk) {
1352 return nullptr;
1353 }
1354
1355 return lwalk->l->f;
1356}
1357
1359{
1360 BMwFaceLoopWalker *lwalk, owalk;
1361 BMFace *f;
1362 BMLoop *l;
1363
1364 BMW_state_remove_r(walker, &owalk);
1365 lwalk = &owalk;
1366
1367 f = lwalk->l->f;
1368 l = lwalk->l->radial_next;
1369
1370 if (lwalk->no_calc) {
1371 return f;
1372 }
1373
1374 if (!bmw_FaceLoopWalker_include_face(walker, l)) {
1375 l = lwalk->l;
1376 l = l->next->next;
1377 if (!BM_edge_is_manifold(l->e)) {
1378 l = l->prev->prev;
1379 }
1380 l = l->radial_next;
1381 }
1382
1383 if (bmw_FaceLoopWalker_include_face(walker, l)) {
1384 lwalk = static_cast<BMwFaceLoopWalker *>(BMW_state_add(walker));
1385 lwalk->l = l;
1386
1387 if (l->f->len != 4 || bmw_FaceLoopWalker_delimit_check(f, l->e, l->f, walker->delimit)) {
1388 lwalk->no_calc = true;
1389 lwalk->l = owalk.l;
1390 }
1391 else {
1392 lwalk->no_calc = false;
1393 }
1394
1395 /* Both may already exist. */
1396 walker->visit_set_alt->add(l->e);
1397 walker->visit_set->add(l->f);
1398 }
1399
1400 return f;
1401}
1402
1404
1405/* -------------------------------------------------------------------- */
1412
1414{
1415 if (!BM_edge_is_manifold(e)) {
1416 return false;
1417 }
1418 if (delimit & BMW_DELIMIT_EDGE_MARK_SEAM) {
1420 return true;
1421 }
1422 }
1423 if (delimit & BMW_DELIMIT_EDGE_MARK_SHARP) {
1425 return true;
1426 }
1427 }
1428 if (delimit & BMW_DELIMIT_FACE_MARK_MATERIAL) {
1429 BMLoop *l = e->l;
1430 if (l->f->mat_nr != l->radial_next->f->mat_nr) {
1431 return true;
1432 }
1433 }
1434 return false;
1435}
1436
1437static void bmw_EdgeringWalker_begin(BMWalker *walker, void *data)
1438{
1439 BMwEdgeringWalker *lwalk, owalk, *owalk_pt;
1440 BMEdge *e = static_cast<BMEdge *>(data);
1441
1442 lwalk = static_cast<BMwEdgeringWalker *>(BMW_state_add(walker));
1443 lwalk->l = e->l;
1444 lwalk->no_calc = false;
1445
1446 if (!lwalk->l) {
1447 lwalk->wireedge = e;
1448 return;
1449 }
1450
1451 /* Treat delimiting edge as wire edge (select only this edge).
1452 * NOTE(@ideasman42): Ideally starting from a delimiting edge would scan in both directions,
1453 * but supporting that with the current walker logic is quite involved,
1454 * especially for a corner case. */
1456 lwalk->l = nullptr;
1457 lwalk->wireedge = e;
1458 return;
1459 }
1460
1461 lwalk->wireedge = nullptr;
1462
1463 walker->visit_set->add(lwalk->l->e);
1464
1465 /* Rewind. */
1466 while ((owalk_pt = static_cast<BMwEdgeringWalker *>(BMW_current_state(walker)))) {
1467 owalk = *(owalk_pt);
1468 BMW_walk(walker);
1469 }
1470
1471 lwalk = static_cast<BMwEdgeringWalker *>(BMW_state_add(walker));
1472 *lwalk = owalk;
1473
1474 const bool delimit_ngon = (walker->delimit & BMW_DELIMIT_EDGE_RING_NGONS) != 0;
1475 if (delimit_ngon ? (lwalk->l->f->len != 4) : (lwalk->l->f->len % 2 != 0)) {
1476 lwalk->l = lwalk->l->radial_next;
1477 }
1478
1479 walker->visit_set->clear();
1480 walker->visit_set->add(lwalk->l->e);
1481
1482 /* Add both sides so both directions are walked. */
1483 if (lwalk->l->radial_next != lwalk->l) {
1484 /* When `no_calc` is true, the walker hit a delimiting edge and can't step further,
1485 * so add the alt walker to traverse the ring in the opposite direction. See #157860. */
1486 if (lwalk->no_calc || (delimit_ngon ? (lwalk->l->f->len != 4) : (lwalk->l->f->len % 2 != 0))) {
1487 BMwEdgeringWalker *lwalk_alt = static_cast<BMwEdgeringWalker *>(BMW_state_add(walker));
1488 lwalk_alt->l = lwalk->l->radial_next;
1489 lwalk_alt->wireedge = nullptr;
1490 lwalk_alt->no_calc = false;
1491 }
1492 }
1493}
1494
1496{
1497 BMwEdgeringWalker *lwalk = static_cast<BMwEdgeringWalker *>(BMW_current_state(walker));
1498
1499 if (!lwalk) {
1500 return nullptr;
1501 }
1502
1503 if (lwalk->l) {
1504 return lwalk->l->e;
1505 }
1506 return lwalk->wireedge;
1507}
1508
1510{
1511 BMwEdgeringWalker *lwalk, owalk;
1512 BMEdge *e;
1513 BMLoop *l;
1514
1515#define EDGE_CHECK(e) \
1516 (bmw_mask_check_edge(walker, e) && (BM_edge_is_boundary(e) || BM_edge_is_manifold(e)))
1517
1518 BMW_state_remove_r(walker, &owalk);
1519 lwalk = &owalk;
1520
1521 l = lwalk->l;
1522 if (!l) {
1523 return lwalk->wireedge;
1524 }
1525
1526 e = l->e;
1527 if (!EDGE_CHECK(e) || lwalk->no_calc) {
1528 /* Walker won't traverse to a non-manifold edge, but may
1529 * be started on one, and should not traverse *away* from
1530 * a non-manifold edge (non-manifold edges are never in an
1531 * edge ring with manifold edges). */
1532 return e;
1533 }
1534
1535 const bool delimit_ngon = (walker->delimit & BMW_DELIMIT_EDGE_RING_NGONS) != 0;
1536 bool step_ok = false;
1537
1538 if (delimit_ngon) {
1539 /* Only quads. */
1540 l = l->radial_next;
1541 l = l->next->next;
1542
1543 if ((l->f->len != 4) || !EDGE_CHECK(l->e) || !bmw_mask_check_face(walker, l->f)) {
1544 l = owalk.l->next->next;
1545 }
1546 /* Only walk to manifold edge. */
1547 step_ok = (l->f->len == 4) && EDGE_CHECK(l->e) && !walker->visit_set->contains(l->e);
1548 }
1549 else {
1550 /* Only N-gons with an even number of sides. */
1551 l = l->radial_next;
1552
1553 int i, len;
1554 i = len = l->f->len;
1555 while (i > 0) {
1556 l = l->next;
1557 i -= 2;
1558 }
1559
1560 if ((len <= 0) || (len % 2 != 0) || !EDGE_CHECK(l->e) || !bmw_mask_check_face(walker, l->f)) {
1561 l = owalk.l;
1562 i = len;
1563 while (i > 0) {
1564 l = l->next;
1565 i -= 2;
1566 }
1567 }
1568 /* Only walk to manifold edge. */
1569 step_ok = (l->f->len % 2 == 0) && EDGE_CHECK(l->e) && !walker->visit_set->contains(l->e);
1570 }
1571
1572 if (step_ok) {
1573 lwalk = static_cast<BMwEdgeringWalker *>(BMW_state_add(walker));
1574 lwalk->l = l;
1575 lwalk->wireedge = nullptr;
1577
1578 walker->visit_set->add(l->e);
1579 }
1580
1581 return e;
1582
1583#undef EDGE_CHECK
1584}
1585
1587
1588/* -------------------------------------------------------------------- */
1591
1592static void bmw_EdgeboundaryWalker_begin(BMWalker *walker, void *data)
1593{
1594 BMwEdgeboundaryWalker *lwalk;
1595 BMEdge *e = static_cast<BMEdge *>(data);
1596
1598
1599 if (walker->visit_set->contains(e)) {
1600 return;
1601 }
1602
1603 lwalk = static_cast<BMwEdgeboundaryWalker *>(BMW_state_add(walker));
1604 lwalk->e = e;
1605 walker->visit_set->add(e);
1606}
1607
1609{
1610 BMwEdgeboundaryWalker *lwalk = static_cast<BMwEdgeboundaryWalker *>(BMW_current_state(walker));
1611
1612 if (!lwalk) {
1613 return nullptr;
1614 }
1615
1616 return lwalk->e;
1617}
1618
1620{
1621 BMwEdgeboundaryWalker *lwalk, owalk;
1622 BMEdge *e, *e_other;
1623 BMVert *v;
1624 BMIter eiter;
1625 BMIter viter;
1626
1627 BMW_state_remove_r(walker, &owalk);
1628 lwalk = &owalk;
1629
1630 e = lwalk->e;
1631
1632 if (!bmw_mask_check_edge(walker, e)) {
1633 return e;
1634 }
1635
1636 BM_ITER_ELEM (v, &viter, e, BM_VERTS_OF_EDGE) {
1637 BM_ITER_ELEM (e_other, &eiter, v, BM_EDGES_OF_VERT) {
1638 if (e != e_other && BM_edge_is_boundary(e_other)) {
1639 if (walker->visit_set->contains(e_other)) {
1640 continue;
1641 }
1642
1643 if (!bmw_mask_check_edge(walker, e_other)) {
1644 continue;
1645 }
1646
1647 lwalk = static_cast<BMwEdgeboundaryWalker *>(BMW_state_add(walker));
1648 walker->visit_set->add(e_other);
1649
1650 lwalk->e = e_other;
1651 }
1652 }
1653 }
1654
1655 return e;
1656}
1657
1659
1660/* -------------------------------------------------------------------- */
1679
1680static void bmw_UVEdgeWalker_begin(BMWalker *walker, void *data)
1681{
1682 BMwUVEdgeWalker *lwalk;
1683 BMLoop *l = static_cast<BMLoop *>(data);
1684
1685 if (walker->visit_set->contains(l)) {
1686 return;
1687 }
1688
1689 lwalk = static_cast<BMwUVEdgeWalker *>(BMW_state_add(walker));
1690 lwalk->l = l;
1691 walker->visit_set->add(l);
1692}
1693
1695{
1696 BMwUVEdgeWalker *lwalk = static_cast<BMwUVEdgeWalker *>(BMW_current_state(walker));
1697
1698 if (!lwalk) {
1699 return nullptr;
1700 }
1701
1702 return lwalk->l;
1703}
1704
1705static void *bmw_UVEdgeWalker_step(BMWalker *walker)
1706{
1707 const int type = walker->bm->ldata.layers[walker->layer].type;
1708 const int offset = walker->bm->ldata.layers[walker->layer].offset;
1709
1710 BMwUVEdgeWalker *lwalk, owalk;
1711 BMLoop *l;
1712 int i;
1713
1714 BMW_state_remove_r(walker, &owalk);
1715 lwalk = &owalk;
1716
1717 l = lwalk->l;
1718
1719 if (!bmw_mask_check_edge(walker, l->e)) {
1720 return l;
1721 }
1722
1723 /* Go over loops around `l->v` and `l->next->v` and see which ones share `l` and `l->next`
1724 * UV coordinates. in addition, push on `l->next` if necessary. */
1725 for (i = 0; i < 2; i++) {
1726 BMIter liter;
1727 BMLoop *l_pivot, *l_radial;
1728
1729 l_pivot = i ? l->next : l;
1730 BM_ITER_ELEM (l_radial, &liter, l_pivot->v, BM_LOOPS_OF_VERT) {
1731 BMLoop *l_radial_first = l_radial;
1732 void *data_pivot = BM_ELEM_CD_GET_VOID_P(l_pivot, offset);
1733
1734 do {
1735 BMLoop *l_other;
1736 void *data_other;
1737
1738 if (walker->visit_set->contains(l_radial)) {
1739 continue;
1740 }
1741
1742 if (l_radial->v != l_pivot->v) {
1743 if (!bmw_mask_check_edge(walker, l_radial->e)) {
1744 continue;
1745 }
1746 }
1747
1748 l_other = (l_radial->v != l_pivot->v) ? l_radial->next : l_radial;
1749 data_other = BM_ELEM_CD_GET_VOID_P(l_other, offset);
1750
1751 if (!CustomData_data_equals(eCustomDataType(type), data_pivot, data_other)) {
1752 continue;
1753 }
1754
1755 lwalk = static_cast<BMwUVEdgeWalker *>(BMW_state_add(walker));
1756 walker->visit_set->add(l_radial);
1757
1758 lwalk->l = l_radial;
1759
1760 } while ((l_radial = l_radial->radial_next) != l_radial_first);
1761
1762 /* Also traverse the previous loop's edge `l_radial_first->prev->e` for masked walks.
1763 * This handles boundary edges where face winding places the loop at the opposite
1764 * end of the edge from the pivot vertex, see: #152249. */
1765 if (walker->mask_edge) {
1766 BMLoop *l_boundary = l_radial_first->prev;
1767 if (BM_edge_is_boundary(l_boundary->e) && bmw_mask_check_edge(walker, l_boundary->e) &&
1768 walker->visit_set->add(l_boundary))
1769 {
1770 lwalk = static_cast<BMwUVEdgeWalker *>(BMW_state_add(walker));
1771 lwalk->l = l_boundary;
1772 }
1773 }
1774 }
1775 }
1776
1777 return l;
1778}
1779
1781
1782/* -------------------------------------------------------------------- */
1785
1787{
1789 BMEdge *e = static_cast<BMEdge *>(data);
1790
1791 if (walker->visit_set->contains(e)) {
1792 return;
1793 }
1794
1795 lwalk = static_cast<BMwNonManifoldEdgeLoopWalker *>(BMW_state_add(walker));
1796 lwalk->start = e;
1797 lwalk->cur = e;
1798 lwalk->startv = e->v1;
1799 lwalk->lastv = e->v1;
1801 walker->visit_set->add(e);
1802}
1803
1805{
1807 BMW_current_state(walker));
1808
1809 if (!lwalk) {
1810 return nullptr;
1811 }
1812 return lwalk->cur;
1813}
1814
1820{
1821 BLI_assert(!BM_loop_is_manifold(l));
1822 do {
1824 if (BM_loop_is_manifold(l)) {
1825 l = l->radial_next;
1826 }
1827 else if (BM_edge_face_count_is_equal(l->e, face_count)) {
1828 return l;
1829 }
1830 else {
1831 break;
1832 }
1833 } while (true);
1834 return nullptr;
1835}
1836
1838{
1839 BMwNonManifoldEdgeLoopWalker *lwalk, owalk;
1840 BMW_state_remove_r(walker, &owalk);
1841 lwalk = &owalk;
1842 BMLoop *l_cur = nullptr;
1843 const int face_count = lwalk->face_count;
1844
1845 BMVert *v = nullptr;
1846
1847 /* Use the second pass is unlikely, only needed to walk back in the opposite direction. */
1848 for (int pass = 0; pass < 2; pass++) {
1849
1850 BMEdge *e = lwalk->cur;
1851 v = BM_edge_other_vert(e, lwalk->lastv);
1852
1853 /* If `lwalk.lastv` can't be walked along, start walking in the opposite direction
1854 * on the initial edge, do this at most one time during this walk operation. */
1855 if (pass == 1) [[unlikely]] {
1856 e = lwalk->start;
1857 v = lwalk->startv;
1858 }
1859
1860 BMLoop *l = e->l;
1861 do {
1862 BMLoop *l_next = bmw_NonManifoldLoop_find_next_around_vertex(l, v, face_count);
1863 if ((l_next != nullptr) && !walker->visit_set->contains(l_next->e)) {
1864 if (l_cur == nullptr) {
1865 l_cur = l_next;
1866 }
1867 else if (l_cur->e != l_next->e) {
1868 /* If there are more than one possible edge to step onto (unlikely but possible),
1869 * treat as a junction and stop walking as there is no correct answer in this case. */
1870 l_cur = nullptr;
1871 break;
1872 }
1873 }
1874 } while ((l = l->radial_next) != e->l);
1875
1876 if (l_cur != nullptr) {
1877 break;
1878 }
1879 }
1880
1881 if (l_cur != nullptr) {
1882 BLI_assert(!walker->visit_set->contains(l_cur->e));
1883 BLI_assert(BM_edge_face_count(l_cur->e) == face_count);
1884 lwalk = static_cast<BMwNonManifoldEdgeLoopWalker *>(BMW_state_add(walker));
1885 lwalk->lastv = v;
1886 lwalk->cur = l_cur->e;
1887 lwalk->face_count = face_count;
1888 walker->visit_set->add(l_cur->e);
1889 }
1890 return owalk.cur;
1891}
1892
1894
1895/* -------------------------------------------------------------------- */
1898
1900 /*begin_htype*/ BM_VERT | BM_EDGE,
1901 /*begin*/ bmw_VertShellWalker_begin,
1902 /*step*/ bmw_VertShellWalker_step,
1903 /*yield*/ bmw_VertShellWalker_yield,
1904 /*structsize*/ sizeof(BMwShellWalker),
1905 /*order*/ BMW_BREADTH_FIRST,
1906 /*valid_mask*/ BM_EDGE, /* Valid restrict masks. */
1907 /*delimit_supported*/ BMW_DELIMIT_NONE,
1908};
1909
1911 /*begin_htype*/ BM_FACE | BM_LOOP | BM_EDGE | BM_VERT,
1912 /*begin*/ bmw_LoopShellWalker_begin,
1913 /*step*/ bmw_LoopShellWalker_step,
1914 /*yield*/ bmw_LoopShellWalker_yield,
1915 /*structsize*/ sizeof(BMwLoopShellWalker),
1916 /*order*/ BMW_BREADTH_FIRST,
1917 /*valid_mask*/ BM_EDGE,
1918 /*delimit_supported*/ BMW_DELIMIT_NONE,
1919};
1920
1922 /*begin_htype*/ BM_FACE | BM_LOOP | BM_EDGE | BM_VERT,
1926 /*structsize*/ sizeof(BMwLoopShellWireWalker),
1927 /*order*/ BMW_BREADTH_FIRST,
1928 /*valid_mask*/ BM_EDGE,
1929 /*delimit_supported*/ BMW_DELIMIT_NONE,
1930};
1931
1933 /*begin_htype*/ BM_EDGE,
1934 /*begin*/ bmw_FaceShellWalker_begin,
1935 /*step*/ bmw_FaceShellWalker_step,
1936 /*yield*/ bmw_FaceShellWalker_yield,
1937 /*structsize*/ sizeof(BMwShellWalker),
1938 /*order*/ BMW_BREADTH_FIRST,
1939 /*valid_mask*/ BM_EDGE,
1940 /*delimit_supported*/ BMW_DELIMIT_NONE,
1941};
1942
1944 /*begin_htype*/ BM_LOOP,
1948 /*structsize*/ sizeof(BMwIslandboundWalker),
1949 /*order*/ BMW_DEPTH_FIRST,
1950 /*valid_mask*/ BM_FACE,
1951 /*delimit_supported*/ BMW_DELIMIT_NONE,
1952};
1953
1955 /*begin_htype*/ BM_FACE,
1956 /*begin*/ bmw_IslandWalker_begin,
1957 /*step*/ bmw_IslandWalker_step,
1958 /*yield*/ bmw_IslandWalker_yield,
1959 /*structsize*/ sizeof(BMwIslandWalker),
1960 /*order*/ BMW_BREADTH_FIRST,
1961 /*valid_mask*/ BM_EDGE | BM_FACE,
1962 /*delimit_supported*/ BMW_DELIMIT_NONE,
1963};
1964
1966 /*begin_htype*/ BM_FACE,
1967 /*begin*/ bmw_IslandWalker_begin,
1968 /*step*/ bmw_IslandManifoldWalker_step, /* Only difference with #BMW_ISLAND. */
1969 /*yield*/ bmw_IslandWalker_yield,
1970 /*structsize*/ sizeof(BMwIslandWalker),
1971 /*order*/ BMW_BREADTH_FIRST,
1972 /*valid_mask*/ BM_EDGE | BM_FACE,
1973 /*delimit_supported*/ BMW_DELIMIT_NONE,
1974};
1975
1977 /*begin_htype*/ BM_EDGE,
1978 /*begin*/ bmw_EdgeLoopWalker_begin,
1979 /*step*/ bmw_EdgeLoopWalker_step,
1980 /*yield*/ bmw_EdgeLoopWalker_yield,
1981 /*structsize*/ sizeof(BMwEdgeLoopWalker),
1982 /*order*/ BMW_DEPTH_FIRST,
1983 /*valid_mask*/ 0, /* Could add flags here but so far none are used. */
1984 /*delimit_supported*/
1987};
1988
1990 /*begin_htype*/ BM_EDGE,
1991 /*begin*/ bmw_FaceLoopWalker_begin,
1992 /*step*/ bmw_FaceLoopWalker_step,
1993 /*yield*/ bmw_FaceLoopWalker_yield,
1994 /*structsize*/ sizeof(BMwFaceLoopWalker),
1995 /*order*/ BMW_DEPTH_FIRST,
1996 /*valid_mask*/ 0, /* Could add flags here but so far none are used. */
1997 /*delimit_supported*/
1999};
2000
2002 /*begin_htype*/ BM_EDGE,
2003 /*begin*/ bmw_EdgeringWalker_begin,
2004 /*step*/ bmw_EdgeringWalker_step,
2005 /*yield*/ bmw_EdgeringWalker_yield,
2006 /*structsize*/ sizeof(BMwEdgeringWalker),
2007 /*order*/ BMW_DEPTH_FIRST,
2008 /*valid_mask*/ BM_EDGE,
2009 /*delimit_supported*/
2012};
2013
2015 /*begin_htype*/ BM_EDGE,
2019 /*structsize*/ sizeof(BMwEdgeboundaryWalker),
2020 /*order*/ BMW_DEPTH_FIRST,
2021 /*valid_mask*/ 0,
2022 /*delimit_supported*/ BMW_DELIMIT_NONE,
2023};
2024
2026 /*begin_htype*/ BM_EDGE,
2030 /*structsize*/ sizeof(BMwNonManifoldEdgeLoopWalker),
2031 /*order*/ BMW_DEPTH_FIRST,
2032 /*valid_mask*/ 0,
2033 /*delimit_supported*/ BMW_DELIMIT_NONE,
2034};
2035
2037 /*begin_htype*/ BM_LOOP,
2038 /*begin*/ bmw_UVEdgeWalker_begin,
2039 /*step*/ bmw_UVEdgeWalker_step,
2040 /*yield*/ bmw_UVEdgeWalker_yield,
2041 /*structsize*/ sizeof(BMwUVEdgeWalker),
2042 /*order*/ BMW_DEPTH_FIRST,
2043 /*valid_mask*/ BM_EDGE,
2044 /*delimit_supported*/ BMW_DELIMIT_NONE,
2045};
2046
2048 /*begin_htype*/ BM_VERT,
2052 /*structsize*/ sizeof(BMwConnectedVertexWalker),
2053 /*order*/ BMW_BREADTH_FIRST,
2054 /*valid_mask*/ BM_VERT,
2055 /*delimit_supported*/ BMW_DELIMIT_NONE,
2056};
2057
2059
2060/* -------------------------------------------------------------------- */
2063
2065 &bmw_VertShellWalker_Type, /* #BMW_VERT_SHELL */
2066 &bmw_LoopShellWalker_Type, /* #BMW_LOOP_SHELL */
2067 &bmw_LoopShellWireWalker_Type, /* #BMW_LOOP_SHELL_WIRE */
2068 &bmw_FaceShellWalker_Type, /* #BMW_FACE_SHELL */
2069 &bmw_EdgeLoopWalker_Type, /* #BMW_EDGELOOP */
2070 &bmw_FaceLoopWalker_Type, /* #BMW_FACELOOP */
2071 &bmw_EdgeringWalker_Type, /* #BMW_EDGERING */
2072 &bmw_EdgeboundaryWalker_Type, /* #BMW_EDGEBOUNDARY */
2073 &bmw_NonManifoldedgeWalker_type, /* #BMW_EDGELOOP_NONMANIFOLD */
2074 &bmw_UVEdgeWalker_Type, /* #BMW_LOOPDATA_ISLAND */
2075 &bmw_IslandboundWalker_Type, /* #BMW_ISLANDBOUND */
2076 &bmw_IslandWalker_Type, /* #BMW_ISLAND */
2077 &bmw_IslandManifoldWalker_Type, /* #BMW_ISLAND_MANIFOLD */
2078 &bmw_ConnectedVertexWalker_Type, /* #BMW_CONNECTED_VERTEX */
2079};
2080
2082
2084
2085} // namespace blender
CustomData interface, see also DNA_customdata_types.h.
#define ELEM(...)
#define BM_DISK_EDGE_NEXT(e, v)
#define BM_FACE_FIRST_LOOP(p)
#define BM_ELEM_CD_GET_VOID_P(ele, offset)
#define BM_elem_flag_test(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BMO_edge_flag_test(bm, e, oflag)
#define BMO_vert_flag_test(bm, e, oflag)
#define BMO_face_flag_test(bm, e, oflag)
#define BM_edge_face_count_is_equal(e, n)
#define EDGE_CHECK(e)
#define BMW_state_remove_r(walker, owalk)
bool contains(const Key &key) const
Definition BLI_set.hh:310
bool add(const Key &key)
Definition BLI_set.hh:248
void clear()
Definition BLI_set.hh:570
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
BMesh Iterators.
static const BMWalker bmw_UVEdgeWalker_Type
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
static bool bmw_FaceLoopWalker_delimit_check(BMFace *f_a, BMEdge *e, BMFace *f_b, const BMWDelimitFlag delimit)
static void * bmw_IslandManifoldWalker_step(BMWalker *walker)
static void * bmw_FaceLoopWalker_step(BMWalker *walker)
int BM_edge_face_count(const BMEdge *e)
const int bm_totwalkers
static void * bmw_EdgeLoopWalker_yield(BMWalker *walker)
BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
@ BMW_FLAG_TEST_HIDDEN
static void * bmw_FaceShellWalker_yield(BMWalker *walker)
static void * bmw_NonManifoldedgeWalker_step(BMWalker *walker)
static const BMWalker bmw_NonManifoldedgeWalker_type
static void bmw_EdgeringWalker_begin(BMWalker *walker, void *data)
static bool bmw_mask_check_vert(BMWalker *walker, BMVert *v)
static void bmw_EdgeLoopWalker_begin(BMWalker *walker, void *data)
void BMW_state_remove(BMWalker *walker)
Remove Current Walker State.
ATTR_WARN_UNUSED_RESULT const BMLoop * l
static void bmw_UVEdgeWalker_begin(BMWalker *walker, void *data)
static bool bmw_EdgeLoopWalker_delimit_mark_check(BMWalker *walker, BMVert *v, BMEdge *e, BMLoop *l)
static const BMWalker bmw_FaceShellWalker_Type
static void * bmw_VertShellWalker_step(BMWalker *walker)
static void * bmw_LoopShellWireWalker_step(BMWalker *walker)
static void bmw_VertShellWalker_visitEdge(BMWalker *walker, BMEdge *e)
static void bmw_NonManifoldedgeWalker_begin(BMWalker *walker, void *data)
static void bmw_EdgeboundaryWalker_begin(BMWalker *walker, void *data)
@ BMW_BREADTH_FIRST
static const BMWalker bmw_FaceLoopWalker_Type
bool CustomData_data_equals(eCustomDataType type, const void *data1, const void *data2)
static void * bmw_IslandWalker_yield(BMWalker *walker)
void * BMW_state_add(BMWalker *walker)
Add a new Walker State.
static void * bmw_ConnectedVertexWalker_step(BMWalker *walker)
static void bmw_ConnectedVertexWalker_begin(BMWalker *walker, void *data)
static bool bmw_EdgeringWalker_delimit_check(BMEdge *e, const BMWDelimitFlag delimit)
BMLoop * BM_face_other_vert_loop(BMFace *f, BMVert *v_prev, BMVert *v)
Other Loop in Face Sharing a Vertex.
ATTR_WARN_UNUSED_RESULT const BMVert * v
static void bmw_LoopShellWalker_step_impl(BMWalker *walker, BMLoop *l)
static void * bmw_IslandWalker_step(BMWalker *walker)
static void bmw_LoopShellWireWalker_visitVert(BMWalker *walker, BMVert *v, const BMEdge *e_from)
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static void * bmw_LoopShellWireWalker_yield(BMWalker *walker)
static void bmw_LoopShellWireWalker_begin(BMWalker *walker, void *data)
static void bmw_IslandboundWalker_begin(BMWalker *walker, void *data)
static const BMWalker bmw_ConnectedVertexWalker_Type
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static void * bmw_VertShellWalker_yield(BMWalker *walker)
static const BMWalker bmw_IslandWalker_Type
static void bmw_FaceLoopWalker_begin(BMWalker *walker, void *data)
static void * bmw_EdgeLoopWalker_step(BMWalker *walker)
static void * bmw_UVEdgeWalker_step(BMWalker *walker)
static BMLoop * bmw_NonManifoldLoop_find_next_around_vertex(BMLoop *l, BMVert *v, int face_count)
static bool bmw_FaceLoopWalker_include_face(BMWalker *walker, BMLoop *l)
static void * bmw_EdgeboundaryWalker_yield(BMWalker *walker)
void * BMW_current_state(BMWalker *walker)
Current Walker State.
int BM_vert_face_count(const BMVert *v)
static void bmw_FaceShellWalker_visitEdge(BMWalker *walker, BMEdge *e)
static const BMWalker bmw_IslandboundWalker_Type
BMesh const char void * data
static bool bmw_mask_check_edge(BMWalker *walker, BMEdge *e)
static bool bmw_mask_check_face(BMWalker *walker, BMFace *f)
static void * bmw_EdgeringWalker_step(BMWalker *walker)
static bool bmw_EdgeLoopWalker_delimit_by_mark(BMWalker *walker, BMVert *v, BMEdge *e, BMLoop *l, bool(*edge_mark_check_fn)(const BMEdge *))
static void * bmw_LoopShellWalker_step(BMWalker *walker)
static void bmw_FaceShellWalker_begin(BMWalker *walker, void *data)
int BM_vert_edge_count_nonwire(const BMVert *v)
static void * bmw_EdgeringWalker_yield(BMWalker *walker)
static const BMWalker bmw_EdgeboundaryWalker_Type
static void * bmw_ConnectedVertexWalker_yield(BMWalker *walker)
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
BLI_INLINE bool BM_edge_is_boundary(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static const BMWalker bmw_IslandManifoldWalker_Type
static const BMWalker bmw_VertShellWalker_Type
static void * bmw_IslandboundWalker_step(BMWalker *walker)
static void bmw_LoopShellWalker_begin(BMWalker *walker, void *data)
static const BMWalker bmw_LoopShellWalker_Type
static void * bmw_FaceShellWalker_step(BMWalker *walker)
static void * bmw_UVEdgeWalker_yield(BMWalker *walker)
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
static void bmw_LoopShellWalker_visitEdgeWire(BMWalker *walker, BMEdge *e)
static bool bm_edge_is_single(BMEdge *e)
bool BM_edge_is_all_face_flag_test(const BMEdge *e, const char hflag, const bool respect_hide)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
const BMWalker * bm_walker_types[]
static void * bmw_NonManifoldedgeWalker_yield(BMWalker *walker)
static void * bmw_IslandWalker_step_ex(BMWalker *walker, bool only_manifold)
BLI_INLINE BMEdge * bmesh_disk_edge_next(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static void * bmw_EdgeboundaryWalker_step(BMWalker *walker)
static void bmw_IslandWalker_begin(BMWalker *walker, void *data)
static void bmw_LoopShellWalker_visitLoop(BMWalker *walker, BMLoop *l)
static const BMWalker bmw_LoopShellWireWalker_Type
static bool bmw_edge_is_wire(const BMWalker *walker, const BMEdge *e)
static bool bmw_FaceLoopWalker_edge_begins_loop(BMWalker *walker, BMEdge *e)
static void bmw_VertShellWalker_begin(BMWalker *walker, void *data)
static void * bmw_IslandboundWalker_yield(BMWalker *walker)
static const BMWalker bmw_EdgeringWalker_Type
static void * bmw_FaceLoopWalker_yield(BMWalker *walker)
static void bmw_ConnectedVertexWalker_visitVertex(BMWalker *walker, BMVert *v)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
@ BMW_DELIMIT_EDGE_LOOP_OUTER_CORNERS
@ BMW_DELIMIT_EDGE_MARK_SHARP
@ BMW_DELIMIT_EDGE_LOOP_INNER_CORNERS
@ BMW_DELIMIT_EDGE_LOOP_NGONS
@ BMW_DELIMIT_FACE_MARK_MATERIAL
@ BMW_DELIMIT_EDGE_MARK_SEAM
@ BMW_DELIMIT_EDGE_RING_NGONS
static const BMWalker bmw_EdgeLoopWalker_Type
static void * bmw_LoopShellWalker_yield(BMWalker *walker)
BMLoop * BM_loop_other_edge_loop(BMLoop *l, BMVert *v)
void * BMW_walk(BMWalker *walker)
Main Walking Function.
struct BMLoop * l
struct BMLoop * next
struct BMLoop * prev
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
Set< const void * > * visit_set
BMWDelimitFlag delimit
Set< const void * > * visit_set_alt
struct BMLoop * radial_next