doxygen: add newline after \file
[blender.git] / source / blender / bmesh / intern / bmesh_walkers_impl.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 /** \file
18  * \ingroup bmesh
19  *
20  * BMesh Walker Code.
21  */
22
23 #include <string.h>
24
25 #include "BLI_utildefines.h"
26
27 #include "BKE_customdata.h"
28
29 #include "bmesh.h"
30 #include "intern/bmesh_walkers_private.h"
31
32 /* pop into stack memory (common operation) */
33 #define BMW_state_remove_r(walker, owalk) { \
34         memcpy(owalk, BMW_current_state(walker), sizeof(*(owalk))); \
35         BMW_state_remove(walker); \
36 } (void)0
37
38 /** \name Mask Flag Checks
39  * \{ */
40
41 static bool bmw_mask_check_vert(BMWalker *walker, BMVert *v)
42 {
43         if ((walker->flag & BMW_FLAG_TEST_HIDDEN) && BM_elem_flag_test(v, BM_ELEM_HIDDEN)) {
44                 return false;
45         }
46         else if (walker->mask_vert && !BMO_vert_flag_test(walker->bm, v, walker->mask_vert)) {
47                 return false;
48         }
49         else {
50                 return true;
51         }
52 }
53
54 static bool bmw_mask_check_edge(BMWalker *walker, BMEdge *e)
55 {
56         if ((walker->flag & BMW_FLAG_TEST_HIDDEN) && BM_elem_flag_test(e, BM_ELEM_HIDDEN)) {
57                 return false;
58         }
59         else if (walker->mask_edge && !BMO_edge_flag_test(walker->bm, e, walker->mask_edge)) {
60                 return false;
61         }
62         else {
63                 return true;
64         }
65 }
66
67 static bool bmw_mask_check_face(BMWalker *walker, BMFace *f)
68 {
69         if ((walker->flag & BMW_FLAG_TEST_HIDDEN) && BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
70                 return false;
71         }
72         else if (walker->mask_face && !BMO_face_flag_test(walker->bm, f, walker->mask_face)) {
73                 return false;
74         }
75         else {
76                 return true;
77         }
78 }
79
80 /** \} */
81
82
83 /** \name BMesh Queries (modified to check walker flags)
84  * \{ */
85
86 /**
87  * Check for a wire edge, taking ignoring hidden.
88  */
89 static bool bmw_edge_is_wire(const BMWalker *walker, const BMEdge *e)
90 {
91         if (walker->flag & BMW_FLAG_TEST_HIDDEN) {
92                 /* check if this is a wire edge, ignoring hidden faces */
93                 if (BM_edge_is_wire(e)) {
94                         return true;
95                 }
96                 else {
97                         return BM_edge_is_all_face_flag_test(e, BM_ELEM_HIDDEN, false);
98                 }
99         }
100         else {
101                 return BM_edge_is_wire(e);
102         }
103 }
104 /** \} */
105
106
107 /** \name Shell Walker
108  * \{
109  *
110  * Starts at a vertex on the mesh and walks over the 'shell' it belongs
111  * to via visiting connected edges.
112  *
113  * takes an edge or vertex as an argument, and spits out edges,
114  * restrict flag acts on the edges as well.
115  *
116  * \todo Add restriction flag/callback for wire edges.
117  */
118 static void bmw_VertShellWalker_visitEdge(BMWalker *walker, BMEdge *e)
119 {
120         BMwShellWalker *shellWalk = NULL;
121
122         if (BLI_gset_haskey(walker->visit_set, e)) {
123                 return;
124         }
125
126         if (!bmw_mask_check_edge(walker, e)) {
127                 return;
128         }
129
130         shellWalk = BMW_state_add(walker);
131         shellWalk->curedge = e;
132         BLI_gset_insert(walker->visit_set, e);
133 }
134
135 static void bmw_VertShellWalker_begin(BMWalker *walker, void *data)
136 {
137         BMIter eiter;
138         BMHeader *h = data;
139         BMEdge *e;
140         BMVert *v;
141
142         if (UNLIKELY(h == NULL)) {
143                 return;
144         }
145
146         switch (h->htype) {
147                 case BM_VERT:
148                 {
149                         /* starting the walk at a vert, add all the edges
150                          * to the worklist */
151                         v = (BMVert *)h;
152                         BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
153                                 bmw_VertShellWalker_visitEdge(walker, e);
154                         }
155                         break;
156                 }
157
158                 case BM_EDGE:
159                 {
160                         /* starting the walk at an edge, add the single edge
161                          * to the worklist */
162                         e = (BMEdge *)h;
163                         bmw_VertShellWalker_visitEdge(walker, e);
164                         break;
165                 }
166                 default:
167                         BLI_assert(0);
168         }
169 }
170
171 static void *bmw_VertShellWalker_yield(BMWalker *walker)
172 {
173         BMwShellWalker *shellWalk = BMW_current_state(walker);
174         return shellWalk->curedge;
175 }
176
177 static void *bmw_VertShellWalker_step(BMWalker *walker)
178 {
179         BMwShellWalker *swalk, owalk;
180         BMEdge *e, *e2;
181         BMVert *v;
182         BMIter iter;
183         int i;
184
185         BMW_state_remove_r(walker, &owalk);
186         swalk = &owalk;
187
188         e = swalk->curedge;
189
190         for (i = 0; i < 2; i++) {
191                 v = i ? e->v2 : e->v1;
192                 BM_ITER_ELEM (e2, &iter, v, BM_EDGES_OF_VERT) {
193                         bmw_VertShellWalker_visitEdge(walker, e2);
194                 }
195         }
196
197         return e;
198 }
199
200 #if 0
201 static void *bmw_VertShellWalker_step(BMWalker *walker)
202 {
203         BMEdge *curedge, *next = NULL;
204         BMVert *v_old = NULL;
205         bool restrictpass = true;
206         BMwShellWalker shellWalk = *((BMwShellWalker *)BMW_current_state(walker));
207
208         if (!BLI_gset_haskey(walker->visit_set, shellWalk.base)) {
209                 BLI_gset_insert(walker->visit_set, shellWalk.base);
210         }
211
212         BMW_state_remove(walker);
213
214
215         /* find the next edge whose other vertex has not been visite */
216         curedge = shellWalk.curedge;
217         do {
218                 if (!BLI_gset_haskey(walker->visit_set, curedge)) {
219                         if (!walker->restrictflag ||
220                             (walker->restrictflag && BMO_edge_flag_test(walker->bm, curedge, walker->restrictflag)))
221                         {
222                                 BMwShellWalker *newstate;
223
224                                 v_old = BM_edge_other_vert(curedge, shellWalk.base);
225
226                                 /* push a new state onto the stac */
227                                 newState = BMW_state_add(walker);
228                                 BLI_gset_insert(walker->visit_set, curedge);
229
230                                 /* populate the new stat */
231
232                                 newState->base = v_old;
233                                 newState->curedge = curedge;
234                         }
235                 }
236         } while ((curedge = bmesh_disk_edge_next(curedge, shellWalk.base)) != shellWalk.curedge);
237
238         return shellWalk.curedge;
239 }
240 #endif
241
242 /** \} */
243
244 /** \name LoopShell Walker
245  * \{
246  *
247  * Starts at any element on the mesh and walks over the 'shell' it belongs
248  * to via visiting connected loops.
249  *
250  * \note this is mainly useful to loop over a shell delimited by edges.
251  */
252 static void bmw_LoopShellWalker_visitLoop(BMWalker *walker, BMLoop *l)
253 {
254         BMwLoopShellWalker *shellWalk = NULL;
255
256         if (BLI_gset_haskey(walker->visit_set, l)) {
257                 return;
258         }
259
260         if (!bmw_mask_check_face(walker, l->f)) {
261                 return;
262         }
263
264         shellWalk = BMW_state_add(walker);
265         shellWalk->curloop = l;
266         BLI_gset_insert(walker->visit_set, l);
267 }
268
269 static void bmw_LoopShellWalker_begin(BMWalker *walker, void *data)
270 {
271         BMIter iter;
272         BMHeader *h = data;
273
274         if (UNLIKELY(h == NULL)) {
275                 return;
276         }
277
278         switch (h->htype) {
279                 case BM_LOOP:
280                 {
281                         /* starting the walk at a vert, add all the edges
282                          * to the worklist */
283                         BMLoop *l = (BMLoop *)h;
284                         bmw_LoopShellWalker_visitLoop(walker, l);
285                         break;
286                 }
287
288                 case BM_VERT:
289                 {
290                         BMVert *v = (BMVert *)h;
291                         BMLoop *l;
292                         BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
293                                 bmw_LoopShellWalker_visitLoop(walker, l);
294                         }
295                         break;
296                 }
297                 case BM_EDGE:
298                 {
299                         BMEdge *e = (BMEdge *)h;
300                         BMLoop *l;
301                         BM_ITER_ELEM (l, &iter, e, BM_LOOPS_OF_EDGE) {
302                                 bmw_LoopShellWalker_visitLoop(walker, l);
303                         }
304                         break;
305                 }
306                 case BM_FACE:
307                 {
308                         BMFace *f = (BMFace *)h;
309                         BMLoop *l = BM_FACE_FIRST_LOOP(f);
310                         /* walker will handle other loops within the face */
311                         bmw_LoopShellWalker_visitLoop(walker, l);
312                         break;
313                 }
314                 default:
315                         BLI_assert(0);
316         }
317 }
318
319 static void *bmw_LoopShellWalker_yield(BMWalker *walker)
320 {
321         BMwLoopShellWalker *shellWalk = BMW_current_state(walker);
322         return shellWalk->curloop;
323 }
324
325 static void bmw_LoopShellWalker_step_impl(BMWalker *walker, BMLoop *l)
326 {
327         BMEdge *e_edj_pair[2];
328         int i;
329
330         /* seems paranoid, but one caller also walks edges */
331         BLI_assert(l->head.htype == BM_LOOP);
332
333         bmw_LoopShellWalker_visitLoop(walker, l->next);
334         bmw_LoopShellWalker_visitLoop(walker, l->prev);
335
336         e_edj_pair[0] = l->e;
337         e_edj_pair[1] = l->prev->e;
338
339         for (i = 0; i < 2; i++) {
340                 BMEdge *e = e_edj_pair[i];
341                 if (bmw_mask_check_edge(walker, e)) {
342                         BMLoop *l_iter, *l_first;
343
344                         l_iter = l_first = e->l;
345                         do {
346                                 BMLoop *l_radial = (l_iter->v == l->v) ? l_iter : l_iter->next;
347                                 BLI_assert(l_radial->v == l->v);
348                                 if (l != l_radial) {
349                                         bmw_LoopShellWalker_visitLoop(walker, l_radial);
350                                 }
351                         } while ((l_iter = l_iter->radial_next) != l_first);
352                 }
353         }
354 }
355
356 static void *bmw_LoopShellWalker_step(BMWalker *walker)
357 {
358         BMwLoopShellWalker *swalk, owalk;
359         BMLoop *l;
360
361         BMW_state_remove_r(walker, &owalk);
362         swalk = &owalk;
363
364         l = swalk->curloop;
365         bmw_LoopShellWalker_step_impl(walker, l);
366
367         return l;
368 }
369
370 /** \} */
371
372 /** \name LoopShell & 'Wire' Walker
373  * \{
374  *
375  * Piggyback ontop of #BMwLoopShellWalker, but also walk over wire edges
376  * This isn't elegant but users expect it when selecting linked,
377  * so we can support delimiters _and_ walking over wire edges.
378  *
379  * Details:
380  * - can yield edges (as well as loops)
381  * - only step over wire edges.
382  * - verts and edges are stored in `visit_set_alt`.
383  */
384
385 static void bmw_LoopShellWalker_visitEdgeWire(BMWalker *walker, BMEdge *e)
386 {
387         BMwLoopShellWireWalker *shellWalk = NULL;
388
389         BLI_assert(bmw_edge_is_wire(walker, e));
390
391         if (BLI_gset_haskey(walker->visit_set_alt, e)) {
392                 return;
393         }
394
395         if (!bmw_mask_check_edge(walker, e)) {
396                 return;
397         }
398
399         shellWalk = BMW_state_add(walker);
400         shellWalk->curelem = (BMElem *)e;
401         BLI_gset_insert(walker->visit_set_alt, e);
402 }
403
404 static void bmw_LoopShellWireWalker_visitVert(BMWalker *walker, BMVert *v, const BMEdge *e_from)
405 {
406         BMEdge *e;
407
408         BLI_assert(v->head.htype == BM_VERT);
409
410         if (BLI_gset_haskey(walker->visit_set_alt, v)) {
411                 return;
412         }
413
414         if (!bmw_mask_check_vert(walker, v)) {
415                 return;
416         }
417
418         e = v->e;
419         do {
420                 if (bmw_edge_is_wire(walker, e) && (e != e_from)) {
421                         BMVert *v_other;
422                         BMIter iter;
423                         BMLoop *l;
424
425                         bmw_LoopShellWalker_visitEdgeWire(walker, e);
426
427                         /* check if we step onto a non-wire vertex */
428                         v_other = BM_edge_other_vert(e, v);
429                         BM_ITER_ELEM (l, &iter, v_other, BM_LOOPS_OF_VERT) {
430
431                                 bmw_LoopShellWalker_visitLoop(walker, l);
432                         }
433                 }
434         } while ((e = BM_DISK_EDGE_NEXT(e, v)) != v->e);
435
436         BLI_gset_insert(walker->visit_set_alt, v);
437 }
438
439 static void bmw_LoopShellWireWalker_begin(BMWalker *walker, void *data)
440 {
441         BMHeader *h = data;
442
443         if (UNLIKELY(h == NULL)) {
444                 return;
445         }
446
447         bmw_LoopShellWalker_begin(walker, data);
448
449         switch (h->htype) {
450                 case BM_LOOP:
451                 {
452                         BMLoop *l = (BMLoop *)h;
453                         bmw_LoopShellWireWalker_visitVert(walker, l->v, NULL);
454                         break;
455                 }
456
457                 case BM_VERT:
458                 {
459                         BMVert *v = (BMVert *)h;
460                         if (v->e) {
461                                 bmw_LoopShellWireWalker_visitVert(walker, v, NULL);
462                         }
463                         break;
464                 }
465                 case BM_EDGE:
466                 {
467                         BMEdge *e = (BMEdge *)h;
468                         if (bmw_mask_check_edge(walker, e)) {
469                                 bmw_LoopShellWireWalker_visitVert(walker, e->v1, NULL);
470                                 bmw_LoopShellWireWalker_visitVert(walker, e->v2, NULL);
471                         }
472                         else if (e->l) {
473                                 BMLoop *l_iter, *l_first;
474
475                                 l_iter = l_first = e->l;
476                                 do {
477                                         bmw_LoopShellWalker_visitLoop(walker, l_iter);
478                                         bmw_LoopShellWalker_visitLoop(walker, l_iter->next);
479                                 } while ((l_iter = l_iter->radial_next) != l_first);
480                         }
481                         break;
482                 }
483                 case BM_FACE:
484                 {
485                         /* wire verts will be walked over */
486                         break;
487                 }
488                 default:
489                         BLI_assert(0);
490         }
491 }
492
493 static void *bmw_LoopShellWireWalker_yield(BMWalker *walker)
494 {
495         BMwLoopShellWireWalker *shellWalk = BMW_current_state(walker);
496         return shellWalk->curelem;
497 }
498
499 static void *bmw_LoopShellWireWalker_step(BMWalker *walker)
500 {
501         BMwLoopShellWireWalker *swalk, owalk;
502
503         BMW_state_remove_r(walker, &owalk);
504         swalk = &owalk;
505
506         if (swalk->curelem->head.htype == BM_LOOP) {
507                 BMLoop *l = (BMLoop *)swalk->curelem;
508
509                 bmw_LoopShellWalker_step_impl(walker, l);
510
511                 bmw_LoopShellWireWalker_visitVert(walker, l->v, NULL);
512
513                 return l;
514         }
515         else {
516                 BMEdge *e = (BMEdge *)swalk->curelem;
517
518                 BLI_assert(e->head.htype == BM_EDGE);
519
520                 bmw_LoopShellWireWalker_visitVert(walker, e->v1, e);
521                 bmw_LoopShellWireWalker_visitVert(walker, e->v2, e);
522
523                 return e;
524         }
525 }
526
527 /** \} */
528
529
530 /** \name FaceShell Walker
531  * \{
532  *
533  * Starts at an edge on the mesh and walks over the 'shell' it belongs
534  * to via visiting connected faces.
535  */
536 static void bmw_FaceShellWalker_visitEdge(BMWalker *walker, BMEdge *e)
537 {
538         BMwShellWalker *shellWalk = NULL;
539
540         if (BLI_gset_haskey(walker->visit_set, e)) {
541                 return;
542         }
543
544         if (!bmw_mask_check_edge(walker, e)) {
545                 return;
546         }
547
548         shellWalk = BMW_state_add(walker);
549         shellWalk->curedge = e;
550         BLI_gset_insert(walker->visit_set, e);
551 }
552
553 static void bmw_FaceShellWalker_begin(BMWalker *walker, void *data)
554 {
555         BMEdge *e = data;
556         bmw_FaceShellWalker_visitEdge(walker, e);
557 }
558
559 static void *bmw_FaceShellWalker_yield(BMWalker *walker)
560 {
561         BMwShellWalker *shellWalk = BMW_current_state(walker);
562         return shellWalk->curedge;
563 }
564
565 static void *bmw_FaceShellWalker_step(BMWalker *walker)
566 {
567         BMwShellWalker *swalk, owalk;
568         BMEdge *e, *e2;
569         BMIter iter;
570
571         BMW_state_remove_r(walker, &owalk);
572         swalk = &owalk;
573
574         e = swalk->curedge;
575
576         if (e->l) {
577                 BMLoop *l_iter, *l_first;
578
579                 l_iter = l_first = e->l;
580                 do {
581                         BM_ITER_ELEM (e2, &iter, l_iter->f, BM_EDGES_OF_FACE) {
582                                 if (e2 != e) {
583                                         bmw_FaceShellWalker_visitEdge(walker, e2);
584                                 }
585                         }
586                 } while ((l_iter = l_iter->radial_next) != l_first);
587         }
588
589         return e;
590 }
591 /** \} */
592
593
594 /** \name Connected Vertex Walker
595  * \{
596  *
597  * Similar to shell walker, but visits vertices instead of edges.
598  *
599  * Walk from a vertex to all connected vertices.
600  */
601 static void bmw_ConnectedVertexWalker_visitVertex(BMWalker *walker, BMVert *v)
602 {
603         BMwConnectedVertexWalker *vwalk;
604
605         if (BLI_gset_haskey(walker->visit_set, v)) {
606                 /* already visited */
607                 return;
608         }
609
610         if (!bmw_mask_check_vert(walker, v)) {
611                 /* not flagged for walk */
612                 return;
613         }
614
615         vwalk = BMW_state_add(walker);
616         vwalk->curvert = v;
617         BLI_gset_insert(walker->visit_set, v);
618 }
619
620 static void bmw_ConnectedVertexWalker_begin(BMWalker *walker, void *data)
621 {
622         BMVert *v = data;
623         bmw_ConnectedVertexWalker_visitVertex(walker, v);
624 }
625
626 static void *bmw_ConnectedVertexWalker_yield(BMWalker *walker)
627 {
628         BMwConnectedVertexWalker *vwalk = BMW_current_state(walker);
629         return vwalk->curvert;
630 }
631
632 static void *bmw_ConnectedVertexWalker_step(BMWalker *walker)
633 {
634         BMwConnectedVertexWalker *vwalk, owalk;
635         BMVert *v, *v2;
636         BMEdge *e;
637         BMIter iter;
638
639         BMW_state_remove_r(walker, &owalk);
640         vwalk = &owalk;
641
642         v = vwalk->curvert;
643
644         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
645                 v2 = BM_edge_other_vert(e, v);
646                 if (!BLI_gset_haskey(walker->visit_set, v2)) {
647                         bmw_ConnectedVertexWalker_visitVertex(walker, v2);
648                 }
649         }
650
651         return v;
652 }
653
654 /** \} */
655
656
657 /** \name Island Boundary Walker
658  * \{
659  *
660  * Starts at a edge on the mesh and walks over the boundary of an island it belongs to.
661  *
662  * \note that this doesn't work on non-manifold geometry.
663  * it might be better to rewrite this to extract
664  * boundary info from the island walker, rather then directly walking
665  * over the boundary.  raises an error if it encounters nonmanifold geometry.
666  *
667  * \todo Add restriction flag/callback for wire edges.
668  */
669 static void bmw_IslandboundWalker_begin(BMWalker *walker, void *data)
670 {
671         BMLoop *l = data;
672         BMwIslandboundWalker *iwalk = NULL;
673
674         iwalk = BMW_state_add(walker);
675
676         iwalk->base = iwalk->curloop = l;
677         iwalk->lastv = l->v;
678
679         BLI_gset_insert(walker->visit_set, data);
680
681 }
682
683 static void *bmw_IslandboundWalker_yield(BMWalker *walker)
684 {
685         BMwIslandboundWalker *iwalk = BMW_current_state(walker);
686
687         return iwalk->curloop;
688 }
689
690 static void *bmw_IslandboundWalker_step(BMWalker *walker)
691 {
692         BMwIslandboundWalker *iwalk, owalk;
693         BMVert *v;
694         BMEdge *e;
695         BMFace *f;
696         BMLoop *l;
697         /* int found = 0; */
698
699         memcpy(&owalk, BMW_current_state(walker), sizeof(owalk));
700         /* normally we'd remove here, but delay until after error checking */
701         iwalk = &owalk;
702
703         l = iwalk->curloop;
704         e = l->e;
705
706         v = BM_edge_other_vert(e, iwalk->lastv);
707
708         /* pop off current state */
709         BMW_state_remove(walker);
710
711         f = l->f;
712
713         while (1) {
714                 l = BM_loop_other_edge_loop(l, v);
715                 if (BM_loop_is_manifold(l)) {
716                         l = l->radial_next;
717                         f = l->f;
718                         e = l->e;
719
720                         if (!bmw_mask_check_face(walker, f)) {
721                                 l = l->radial_next;
722                                 break;
723                         }
724                 }
725                 else {
726                         /* treat non-manifold edges as boundaries */
727                         f = l->f;
728                         e = l->e;
729                         break;
730                 }
731         }
732
733         if (l == owalk.curloop) {
734                 return NULL;
735         }
736         else if (BLI_gset_haskey(walker->visit_set, l)) {
737                 return owalk.curloop;
738         }
739
740         BLI_gset_insert(walker->visit_set, l);
741         iwalk = BMW_state_add(walker);
742         iwalk->base = owalk.base;
743
744         //if (!BMO_face_flag_test(walker->bm, l->f, walker->restrictflag))
745         //      iwalk->curloop = l->radial_next;
746         iwalk->curloop = l; //else iwalk->curloop = l;
747         iwalk->lastv = v;
748
749         return owalk.curloop;
750 }
751
752
753 /** \name Island Walker
754  * \{
755  *
756  * Starts at a tool flagged-face and walks over the face region
757  *
758  * \todo Add restriction flag/callback for wire edges.
759  */
760 static void bmw_IslandWalker_begin(BMWalker *walker, void *data)
761 {
762         BMwIslandWalker *iwalk = NULL;
763
764         if (!bmw_mask_check_face(walker, data)) {
765                 return;
766         }
767
768         iwalk = BMW_state_add(walker);
769         BLI_gset_insert(walker->visit_set, data);
770
771         iwalk->cur = data;
772 }
773
774 static void *bmw_IslandWalker_yield(BMWalker *walker)
775 {
776         BMwIslandWalker *iwalk = BMW_current_state(walker);
777
778         return iwalk->cur;
779 }
780
781 static void *bmw_IslandWalker_step_ex(BMWalker *walker, bool only_manifold)
782 {
783         BMwIslandWalker *iwalk, owalk;
784         BMLoop *l_iter, *l_first;
785
786         BMW_state_remove_r(walker, &owalk);
787         iwalk = &owalk;
788
789         l_iter = l_first = BM_FACE_FIRST_LOOP(iwalk->cur);
790         do {
791                 /* could skip loop here too, but don't add unless we need it */
792                 if (!bmw_mask_check_edge(walker, l_iter->e)) {
793                         continue;
794                 }
795
796                 BMLoop *l_radial_iter;
797
798                 if (only_manifold && (l_iter->radial_next != l_iter)) {
799                         int face_count = 1;
800                         /* check other faces (not this one), ensure only one other can be walked onto. */
801                         l_radial_iter = l_iter->radial_next;
802                         do {
803                                 if (bmw_mask_check_face(walker, l_radial_iter->f)) {
804                                         face_count++;
805                                         if (face_count == 3) {
806                                                 break;
807                                         }
808                                 }
809                         } while ((l_radial_iter = l_radial_iter->radial_next) != l_iter);
810
811                         if (face_count != 2) {
812                                 continue;
813                         }
814                 }
815
816                 l_radial_iter = l_iter;
817                 while ((l_radial_iter = l_radial_iter->radial_next) != l_iter) {
818                         BMFace *f = l_radial_iter->f;
819
820                         if (!bmw_mask_check_face(walker, f)) {
821                                 continue;
822                         }
823
824                         /* saves checking BLI_gset_haskey below (manifold edges theres a 50% chance) */
825                         if (f == iwalk->cur) {
826                                 continue;
827                         }
828
829                         if (BLI_gset_haskey(walker->visit_set, f)) {
830                                 continue;
831                         }
832
833                         iwalk = BMW_state_add(walker);
834                         iwalk->cur = f;
835                         BLI_gset_insert(walker->visit_set, f);
836                         break;
837                 }
838         } while ((l_iter = l_iter->next) != l_first);
839
840         return owalk.cur;
841 }
842
843 static void *bmw_IslandWalker_step(BMWalker *walker)
844 {
845         return bmw_IslandWalker_step_ex(walker, false);
846 }
847
848 /**
849  * Ignore edges that don't have 2x usable faces.
850  */
851 static void *bmw_IslandManifoldWalker_step(BMWalker *walker)
852 {
853         return bmw_IslandWalker_step_ex(walker, true);
854 }
855
856 /** \} */
857
858
859 /** \name Edge Loop Walker
860  * \{
861  *
862  * Starts at a tool-flagged edge and walks over the edge loop
863  */
864
865 /* utility function to see if an edge is apart of an ngon boundary */
866 static bool bm_edge_is_single(BMEdge *e)
867 {
868         return ((BM_edge_is_boundary(e)) &&
869                 (e->l->f->len > 4) &&
870                 (BM_edge_is_boundary(e->l->next->e) || BM_edge_is_boundary(e->l->prev->e)));
871 }
872
873 static void bmw_EdgeLoopWalker_begin(BMWalker *walker, void *data)
874 {
875         BMwEdgeLoopWalker *lwalk = NULL, owalk, *owalk_pt;
876         BMEdge *e = data;
877         BMVert *v;
878         const int vert_edge_count[2] = {
879             BM_vert_edge_count_nonwire(e->v1),
880             BM_vert_edge_count_nonwire(e->v2),
881         };
882
883         v = e->v1;
884
885         lwalk = BMW_state_add(walker);
886         BLI_gset_insert(walker->visit_set, e);
887
888         lwalk->cur = lwalk->start = e;
889         lwalk->lastv = lwalk->startv = v;
890         lwalk->is_boundary = BM_edge_is_boundary(e);
891         lwalk->is_single = (lwalk->is_boundary && bm_edge_is_single(e));
892
893         /* could also check that vertex*/
894         if ((lwalk->is_boundary == false) &&
895             (vert_edge_count[0] == 3 || vert_edge_count[1] == 3))
896         {
897                 BMIter iter;
898                 BMFace *f_iter;
899                 BMFace *f_best = NULL;
900
901                 BM_ITER_ELEM (f_iter, &iter, e, BM_FACES_OF_EDGE) {
902                         if (f_best == NULL || f_best->len < f_iter->len) {
903                                 f_best = f_iter;
904                         }
905                 }
906
907                 if (f_best) {
908                         /* only use hub selection for 5+ sides else this could
909                          * conflict with normal edge loop selection. */
910                         lwalk->f_hub = f_best->len > 4 ? f_best : NULL;
911                 }
912                 else {
913                         /* edge doesn't have any faces connected to it */
914                         lwalk->f_hub = NULL;
915                 }
916         }
917         else {
918                 lwalk->f_hub = NULL;
919         }
920
921         /* rewind */
922         while ((owalk_pt = BMW_current_state(walker))) {
923                 owalk = *((BMwEdgeLoopWalker *)owalk_pt);
924                 BMW_walk(walker);
925         }
926
927         lwalk = BMW_state_add(walker);
928         *lwalk = owalk;
929
930         lwalk->lastv = lwalk->startv = BM_edge_other_vert(owalk.cur, lwalk->lastv);
931
932         BLI_gset_clear(walker->visit_set, NULL);
933         BLI_gset_insert(walker->visit_set, owalk.cur);
934 }
935
936 static void *bmw_EdgeLoopWalker_yield(BMWalker *walker)
937 {
938         BMwEdgeLoopWalker *lwalk = BMW_current_state(walker);
939
940         return lwalk->cur;
941 }
942
943 static void *bmw_EdgeLoopWalker_step(BMWalker *walker)
944 {
945         BMwEdgeLoopWalker *lwalk, owalk;
946         BMEdge *e, *nexte = NULL;
947         BMLoop *l;
948         BMVert *v;
949
950         BMW_state_remove_r(walker, &owalk);
951         lwalk = &owalk;
952
953         e = lwalk->cur;
954         l = e->l;
955
956         if (owalk.f_hub) { /* NGON EDGE */
957                 int vert_edge_tot;
958
959                 v = BM_edge_other_vert(e, lwalk->lastv);
960
961                 vert_edge_tot = BM_vert_edge_count_nonwire(v);
962
963                 if (vert_edge_tot == 3) {
964                         l = BM_face_other_vert_loop(owalk.f_hub, lwalk->lastv, v);
965                         nexte = BM_edge_exists(v, l->v);
966
967                         if (bmw_mask_check_edge(walker, nexte) &&
968                             !BLI_gset_haskey(walker->visit_set, nexte) &&
969                             /* never step onto a boundary edge, this gives odd-results */
970                             (BM_edge_is_boundary(nexte) == false))
971                         {
972                                 lwalk = BMW_state_add(walker);
973                                 lwalk->cur = nexte;
974                                 lwalk->lastv = v;
975
976                                 lwalk->is_boundary = owalk.is_boundary;
977                                 lwalk->is_single = owalk.is_single;
978                                 lwalk->f_hub = owalk.f_hub;
979
980                                 BLI_gset_insert(walker->visit_set, nexte);
981                         }
982                 }
983         }
984         else if (l == NULL) {  /* WIRE EDGE */
985                 BMIter eiter;
986
987                 /* match trunk: mark all connected wire edges */
988                 for (int i = 0; i < 2; i++) {
989                         v = i ? e->v2 : e->v1;
990
991                         BM_ITER_ELEM (nexte, &eiter, v, BM_EDGES_OF_VERT) {
992                                 if ((nexte->l == NULL) &&
993                                     bmw_mask_check_edge(walker, nexte) &&
994                                     !BLI_gset_haskey(walker->visit_set, nexte))
995                                 {
996                                         lwalk = BMW_state_add(walker);
997                                         lwalk->cur = nexte;
998                                         lwalk->lastv = v;
999
1000                                         lwalk->is_boundary = owalk.is_boundary;
1001                                         lwalk->is_single = owalk.is_single;
1002                                         lwalk->f_hub = owalk.f_hub;
1003
1004                                         BLI_gset_insert(walker->visit_set, nexte);
1005                                 }
1006                         }
1007                 }
1008         }
1009         else if (owalk.is_boundary == false) {  /* NORMAL EDGE WITH FACES */
1010                 int vert_edge_tot;
1011
1012                 v = BM_edge_other_vert(e, lwalk->lastv);
1013
1014                 vert_edge_tot = BM_vert_edge_count_nonwire(v);
1015
1016                 /* typical loopiong over edges in the middle of a mesh */
1017                 /* however, why use 2 here at all? I guess for internal ngon loops it can be useful. Antony R. */
1018                 if (vert_edge_tot == 4 || vert_edge_tot == 2) {
1019                         int i_opposite = vert_edge_tot / 2;
1020                         int i = 0;
1021                         do {
1022                                 l = BM_loop_other_edge_loop(l, v);
1023                                 if (BM_edge_is_manifold(l->e)) {
1024                                         l = l->radial_next;
1025                                 }
1026                                 else {
1027                                         l = NULL;
1028                                         break;
1029                                 }
1030                         } while ((++i != i_opposite));
1031                 }
1032                 else {
1033                         l = NULL;
1034                 }
1035
1036                 if (l != NULL) {
1037                         if (l != e->l &&
1038                             bmw_mask_check_edge(walker, l->e) &&
1039                             !BLI_gset_haskey(walker->visit_set, l->e))
1040                         {
1041                                 lwalk = BMW_state_add(walker);
1042                                 lwalk->cur = l->e;
1043                                 lwalk->lastv = v;
1044
1045                                 lwalk->is_boundary = owalk.is_boundary;
1046                                 lwalk->is_single = owalk.is_single;
1047                                 lwalk->f_hub = owalk.f_hub;
1048
1049                                 BLI_gset_insert(walker->visit_set, l->e);
1050                         }
1051                 }
1052         }
1053         else if (owalk.is_boundary == true) {  /* BOUNDARY EDGE WITH FACES */
1054                 int vert_edge_tot;
1055
1056                 v = BM_edge_other_vert(e, lwalk->lastv);
1057
1058                 vert_edge_tot = BM_vert_edge_count_nonwire(v);
1059
1060                 /* check if we should step, this is fairly involved */
1061                 if (
1062                     /* walk over boundary of faces but stop at corners */
1063                     (owalk.is_single == false && vert_edge_tot > 2) ||
1064
1065                     /* initial edge was a boundary, so is this edge and vertex is only apart of this face
1066                      * this lets us walk over the boundary of an ngon which is handy */
1067                     (owalk.is_single == true && vert_edge_tot == 2 && BM_edge_is_boundary(e)))
1068                 {
1069                         /* find next boundary edge in the fan */
1070                         do {
1071                                 l = BM_loop_other_edge_loop(l, v);
1072                                 if (BM_edge_is_manifold(l->e)) {
1073                                         l = l->radial_next;
1074                                 }
1075                                 else if (BM_edge_is_boundary(l->e)) {
1076                                         break;
1077                                 }
1078                                 else {
1079                                         l = NULL;
1080                                         break;
1081                                 }
1082                         } while (true);
1083                 }
1084
1085                 if (owalk.is_single == false && l && bm_edge_is_single(l->e)) {
1086                         l = NULL;
1087                 }
1088
1089                 if (l != NULL) {
1090                         if (l != e->l &&
1091                             bmw_mask_check_edge(walker, l->e) &&
1092                             !BLI_gset_haskey(walker->visit_set, l->e))
1093                         {
1094                                 lwalk = BMW_state_add(walker);
1095                                 lwalk->cur = l->e;
1096                                 lwalk->lastv = v;
1097
1098                                 lwalk->is_boundary = owalk.is_boundary;
1099                                 lwalk->is_single = owalk.is_single;
1100                                 lwalk->f_hub = owalk.f_hub;
1101
1102                                 BLI_gset_insert(walker->visit_set, l->e);
1103                         }
1104                 }
1105         }
1106
1107         return owalk.cur;
1108 }
1109
1110 /** \} */
1111
1112
1113 /** \name Face Loop Walker
1114  * \{
1115  *
1116  * Starts at a tool-flagged face and walks over the face loop
1117  * Conditions for starting and stepping the face loop have been
1118  * tuned in an attempt to match the face loops built by EditMesh
1119  */
1120
1121 /* Check whether the face loop should includes the face specified
1122  * by the given BMLoop */
1123 static bool bmw_FaceLoopWalker_include_face(BMWalker *walker, BMLoop *l)
1124 {
1125         /* face must have degree 4 */
1126         if (l->f->len != 4) {
1127                 return false;
1128         }
1129
1130         if (!bmw_mask_check_face(walker, l->f)) {
1131                 return false;
1132         }
1133
1134         /* the face must not have been already visited */
1135         if (BLI_gset_haskey(walker->visit_set, l->f) && BLI_gset_haskey(walker->visit_set_alt, l->e)) {
1136                 return false;
1137         }
1138
1139         return true;
1140 }
1141
1142 /* Check whether the face loop can start from the given edge */
1143 static bool bmw_FaceLoopWalker_edge_begins_loop(BMWalker *walker, BMEdge *e)
1144 {
1145         /* There is no face loop starting from a wire edge */
1146         if (BM_edge_is_wire(e)) {
1147                 return false;
1148         }
1149
1150         /* Don't start a loop from a boundary edge if it cannot
1151          * be extended to cover any faces */
1152         if (BM_edge_is_boundary(e)) {
1153                 if (!bmw_FaceLoopWalker_include_face(walker, e->l)) {
1154                         return false;
1155                 }
1156         }
1157
1158         /* Don't start a face loop from non-manifold edges */
1159         if (!BM_edge_is_manifold(e)) {
1160                 return false;
1161         }
1162
1163         return true;
1164 }
1165
1166 static void bmw_FaceLoopWalker_begin(BMWalker *walker, void *data)
1167 {
1168         BMwFaceLoopWalker *lwalk, owalk, *owalk_pt;
1169         BMEdge *e = data;
1170         /* BMesh *bm = walker->bm; */ /* UNUSED */
1171         /* int fcount = BM_edge_face_count(e); */ /* UNUSED */
1172
1173         if (!bmw_FaceLoopWalker_edge_begins_loop(walker, e))
1174                 return;
1175
1176         lwalk = BMW_state_add(walker);
1177         lwalk->l = e->l;
1178         lwalk->no_calc = false;
1179         BLI_gset_insert(walker->visit_set, lwalk->l->f);
1180
1181         /* rewind */
1182         while ((owalk_pt = BMW_current_state(walker))) {
1183                 owalk = *((BMwFaceLoopWalker *)owalk_pt);
1184                 BMW_walk(walker);
1185         }
1186
1187         lwalk = BMW_state_add(walker);
1188         *lwalk = owalk;
1189         lwalk->no_calc = false;
1190
1191         BLI_gset_clear(walker->visit_set_alt, NULL);
1192         BLI_gset_insert(walker->visit_set_alt, lwalk->l->e);
1193
1194         BLI_gset_clear(walker->visit_set, NULL);
1195         BLI_gset_insert(walker->visit_set, lwalk->l->f);
1196 }
1197
1198 static void *bmw_FaceLoopWalker_yield(BMWalker *walker)
1199 {
1200         BMwFaceLoopWalker *lwalk = BMW_current_state(walker);
1201
1202         if (!lwalk) {
1203                 return NULL;
1204         }
1205
1206         return lwalk->l->f;
1207 }
1208
1209 static void *bmw_FaceLoopWalker_step(BMWalker *walker)
1210 {
1211         BMwFaceLoopWalker *lwalk, owalk;
1212         BMFace *f;
1213         BMLoop *l;
1214
1215         BMW_state_remove_r(walker, &owalk);
1216         lwalk = &owalk;
1217
1218         f = lwalk->l->f;
1219         l = lwalk->l->radial_next;
1220
1221         if (lwalk->no_calc) {
1222                 return f;
1223         }
1224
1225         if (!bmw_FaceLoopWalker_include_face(walker, l)) {
1226                 l = lwalk->l;
1227                 l = l->next->next;
1228                 if (!BM_edge_is_manifold(l->e)) {
1229                         l = l->prev->prev;
1230                 }
1231                 l = l->radial_next;
1232         }
1233
1234         if (bmw_FaceLoopWalker_include_face(walker, l)) {
1235                 lwalk = BMW_state_add(walker);
1236                 lwalk->l = l;
1237
1238                 if (l->f->len != 4) {
1239                         lwalk->no_calc = true;
1240                         lwalk->l = owalk.l;
1241                 }
1242                 else {
1243                         lwalk->no_calc = false;
1244                 }
1245
1246                 /* both may already exist */
1247                 BLI_gset_add(walker->visit_set_alt, l->e);
1248                 BLI_gset_add(walker->visit_set, l->f);
1249         }
1250
1251         return f;
1252 }
1253
1254 /** \} */
1255
1256
1257 // #define BMW_EDGERING_NGON
1258
1259 /** \name Edge Ring Walker
1260  * \{
1261  *
1262  * Starts at a tool-flagged edge and walks over the edge ring
1263  * Conditions for starting and stepping the edge ring have been
1264  * tuned to match behavior users expect (dating back to v2.4x).
1265  */
1266 static void bmw_EdgeringWalker_begin(BMWalker *walker, void *data)
1267 {
1268         BMwEdgeringWalker *lwalk, owalk, *owalk_pt;
1269         BMEdge *e = data;
1270
1271         lwalk = BMW_state_add(walker);
1272         lwalk->l = e->l;
1273
1274         if (!lwalk->l) {
1275                 lwalk->wireedge = e;
1276                 return;
1277         }
1278         else {
1279                 lwalk->wireedge = NULL;
1280         }
1281
1282         BLI_gset_insert(walker->visit_set, lwalk->l->e);
1283
1284         /* rewind */
1285         while ((owalk_pt = BMW_current_state(walker))) {
1286                 owalk = *((BMwEdgeringWalker *)owalk_pt);
1287                 BMW_walk(walker);
1288         }
1289
1290         lwalk = BMW_state_add(walker);
1291         *lwalk = owalk;
1292
1293 #ifdef BMW_EDGERING_NGON
1294         if (lwalk->l->f->len % 2 != 0)
1295 #else
1296         if (lwalk->l->f->len != 4)
1297 #endif
1298         {
1299                 lwalk->l = lwalk->l->radial_next;
1300         }
1301
1302         BLI_gset_clear(walker->visit_set, NULL);
1303         BLI_gset_insert(walker->visit_set, lwalk->l->e);
1304 }
1305
1306 static void *bmw_EdgeringWalker_yield(BMWalker *walker)
1307 {
1308         BMwEdgeringWalker *lwalk = BMW_current_state(walker);
1309
1310         if (!lwalk) {
1311                 return NULL;
1312         }
1313
1314         if (lwalk->l) {
1315                 return lwalk->l->e;
1316         }
1317         else {
1318                 return lwalk->wireedge;
1319         }
1320 }
1321
1322 static void *bmw_EdgeringWalker_step(BMWalker *walker)
1323 {
1324         BMwEdgeringWalker *lwalk, owalk;
1325         BMEdge *e;
1326         BMLoop *l;
1327 #ifdef BMW_EDGERING_NGON
1328         int i, len;
1329 #endif
1330
1331 #define EDGE_CHECK(e) (bmw_mask_check_edge(walker, e) && (BM_edge_is_boundary(e) || BM_edge_is_manifold(e)))
1332
1333         BMW_state_remove_r(walker, &owalk);
1334         lwalk = &owalk;
1335
1336         l = lwalk->l;
1337         if (!l)
1338                 return lwalk->wireedge;
1339
1340         e = l->e;
1341         if (!EDGE_CHECK(e)) {
1342                 /* walker won't traverse to a non-manifold edge, but may
1343                  * be started on one, and should not traverse *away* from
1344                  * a non-manifold edge (non-manifold edges are never in an
1345                  * edge ring with manifold edges */
1346                 return e;
1347         }
1348
1349 #ifdef BMW_EDGERING_NGON
1350         l = l->radial_next;
1351
1352         i = len = l->f->len;
1353         while (i > 0) {
1354                 l = l->next;
1355                 i -= 2;
1356         }
1357
1358         if ((len <= 0) || (len % 2 != 0) || !EDGE_CHECK(l->e) ||
1359             !bmw_mask_check_face(walker, l->f))
1360         {
1361                 l = owalk.l;
1362                 i = len;
1363                 while (i > 0) {
1364                         l = l->next;
1365                         i -= 2;
1366                 }
1367         }
1368         /* only walk to manifold edge */
1369         if ((l->f->len % 2 == 0) && EDGE_CHECK(l->e) &&
1370             !BLI_gset_haskey(walker->visit_set, l->e))
1371
1372 #else
1373
1374         l = l->radial_next;
1375         l = l->next->next;
1376
1377         if ((l->f->len != 4) || !EDGE_CHECK(l->e) || !bmw_mask_check_face(walker, l->f)) {
1378                 l = owalk.l->next->next;
1379         }
1380         /* only walk to manifold edge */
1381         if ((l->f->len == 4) && EDGE_CHECK(l->e) &&
1382             !BLI_gset_haskey(walker->visit_set, l->e))
1383 #endif
1384         {
1385                 lwalk = BMW_state_add(walker);
1386                 lwalk->l = l;
1387                 lwalk->wireedge = NULL;
1388
1389                 BLI_gset_insert(walker->visit_set, l->e);
1390         }
1391
1392         return e;
1393
1394 #undef EDGE_CHECK
1395 }
1396
1397 /** \} */
1398
1399
1400 /** \name Boundary Edge Walker
1401  * \{ */
1402
1403 static void bmw_EdgeboundaryWalker_begin(BMWalker *walker, void *data)
1404 {
1405         BMwEdgeboundaryWalker *lwalk;
1406         BMEdge *e = data;
1407
1408         BLI_assert(BM_edge_is_boundary(e));
1409
1410         if (BLI_gset_haskey(walker->visit_set, e))
1411                 return;
1412
1413         lwalk = BMW_state_add(walker);
1414         lwalk->e = e;
1415         BLI_gset_insert(walker->visit_set, e);
1416 }
1417
1418 static void *bmw_EdgeboundaryWalker_yield(BMWalker *walker)
1419 {
1420         BMwEdgeboundaryWalker *lwalk = BMW_current_state(walker);
1421
1422         if (!lwalk) {
1423                 return NULL;
1424         }
1425
1426         return lwalk->e;
1427 }
1428
1429 static void *bmw_EdgeboundaryWalker_step(BMWalker *walker)
1430 {
1431         BMwEdgeboundaryWalker *lwalk, owalk;
1432         BMEdge *e, *e_other;
1433         BMVert *v;
1434         BMIter eiter;
1435         BMIter viter;
1436
1437         BMW_state_remove_r(walker, &owalk);
1438         lwalk = &owalk;
1439
1440         e = lwalk->e;
1441
1442         if (!bmw_mask_check_edge(walker, e)) {
1443                 return e;
1444         }
1445
1446         BM_ITER_ELEM (v, &viter, e, BM_VERTS_OF_EDGE) {
1447                 BM_ITER_ELEM (e_other, &eiter, v, BM_EDGES_OF_VERT) {
1448                         if (e != e_other && BM_edge_is_boundary(e_other)) {
1449                                 if (BLI_gset_haskey(walker->visit_set, e_other)) {
1450                                         continue;
1451                                 }
1452
1453                                 if (!bmw_mask_check_edge(walker, e_other)) {
1454                                         continue;
1455                                 }
1456
1457                                 lwalk = BMW_state_add(walker);
1458                                 BLI_gset_insert(walker->visit_set, e_other);
1459
1460                                 lwalk->e = e_other;
1461                         }
1462                 }
1463         }
1464
1465         return e;
1466 }
1467
1468 /** \} */
1469
1470
1471 /** \name UV Edge Walker
1472  *
1473  * walk over uv islands; takes a loop as input.  restrict flag
1474  * restricts the walking to loops whose vert has restrict flag set as a
1475  * tool flag.
1476  *
1477  * the flag parameter to BMW_init maps to a loop customdata layer index.
1478  *
1479  * \{ */
1480
1481 static void bmw_UVEdgeWalker_begin(BMWalker *walker, void *data)
1482 {
1483         BMwUVEdgeWalker *lwalk;
1484         BMLoop *l = data;
1485
1486         if (BLI_gset_haskey(walker->visit_set, l))
1487                 return;
1488
1489         lwalk = BMW_state_add(walker);
1490         lwalk->l = l;
1491         BLI_gset_insert(walker->visit_set, l);
1492 }
1493
1494 static void *bmw_UVEdgeWalker_yield(BMWalker *walker)
1495 {
1496         BMwUVEdgeWalker *lwalk = BMW_current_state(walker);
1497
1498         if (!lwalk) {
1499                 return NULL;
1500         }
1501
1502         return lwalk->l;
1503 }
1504
1505 static void *bmw_UVEdgeWalker_step(BMWalker *walker)
1506 {
1507         const int type = walker->bm->ldata.layers[walker->layer].type;
1508         const int offset = walker->bm->ldata.layers[walker->layer].offset;
1509
1510         BMwUVEdgeWalker *lwalk, owalk;
1511         BMLoop *l;
1512         int i;
1513
1514         BMW_state_remove_r(walker, &owalk);
1515         lwalk = &owalk;
1516
1517         l = lwalk->l;
1518
1519         if (!bmw_mask_check_edge(walker, l->e)) {
1520                 return l;
1521         }
1522
1523         /* go over loops around l->v and nl->v and see which ones share l and nl's
1524          * mloopuv's coordinates. in addition, push on l->next if necessary */
1525         for (i = 0; i < 2; i++) {
1526                 BMIter liter;
1527                 BMLoop *l_pivot, *l_radial;
1528
1529                 l_pivot = i ? l->next : l;
1530                 BM_ITER_ELEM (l_radial, &liter, l_pivot->v, BM_LOOPS_OF_VERT) {
1531                         BMLoop *l_radial_first = l_radial;
1532                         void *data_pivot = BM_ELEM_CD_GET_VOID_P(l_pivot, offset);
1533
1534                         do {
1535                                 BMLoop *l_other;
1536                                 void *data_other;
1537
1538                                 if (BLI_gset_haskey(walker->visit_set, l_radial)) {
1539                                         continue;
1540                                 }
1541
1542                                 if (l_radial->v != l_pivot->v) {
1543                                         if (!bmw_mask_check_edge(walker, l_radial->e)) {
1544                                                 continue;
1545                                         }
1546                                 }
1547
1548                                 l_other = (l_radial->v != l_pivot->v) ? l_radial->next : l_radial;
1549                                 data_other = BM_ELEM_CD_GET_VOID_P(l_other, offset);
1550
1551                                 if (!CustomData_data_equals(type, data_pivot, data_other))
1552                                         continue;
1553
1554                                 lwalk = BMW_state_add(walker);
1555                                 BLI_gset_insert(walker->visit_set, l_radial);
1556
1557                                 lwalk->l = l_radial;
1558
1559                         } while ((l_radial = l_radial->radial_next) != l_radial_first);
1560                 }
1561         }
1562
1563         return l;
1564 }
1565
1566 /** \} */
1567
1568
1569 static BMWalker bmw_VertShellWalker_Type = {
1570         BM_VERT | BM_EDGE,
1571         bmw_VertShellWalker_begin,
1572         bmw_VertShellWalker_step,
1573         bmw_VertShellWalker_yield,
1574         sizeof(BMwShellWalker),
1575         BMW_BREADTH_FIRST,
1576         BM_EDGE, /* valid restrict masks */
1577 };
1578
1579 static BMWalker bmw_LoopShellWalker_Type = {
1580         BM_FACE | BM_LOOP | BM_EDGE | BM_VERT,
1581         bmw_LoopShellWalker_begin,
1582         bmw_LoopShellWalker_step,
1583         bmw_LoopShellWalker_yield,
1584         sizeof(BMwLoopShellWalker),
1585         BMW_BREADTH_FIRST,
1586         BM_EDGE, /* valid restrict masks */
1587 };
1588
1589 static BMWalker bmw_LoopShellWireWalker_Type = {
1590         BM_FACE | BM_LOOP | BM_EDGE | BM_VERT,
1591         bmw_LoopShellWireWalker_begin,
1592         bmw_LoopShellWireWalker_step,
1593         bmw_LoopShellWireWalker_yield,
1594         sizeof(BMwLoopShellWireWalker),
1595         BMW_BREADTH_FIRST,
1596         BM_EDGE, /* valid restrict masks */
1597 };
1598
1599 static BMWalker bmw_FaceShellWalker_Type = {
1600         BM_EDGE,
1601         bmw_FaceShellWalker_begin,
1602         bmw_FaceShellWalker_step,
1603         bmw_FaceShellWalker_yield,
1604         sizeof(BMwShellWalker),
1605         BMW_BREADTH_FIRST,
1606         BM_EDGE, /* valid restrict masks */
1607 };
1608
1609 static BMWalker bmw_IslandboundWalker_Type = {
1610         BM_LOOP,
1611         bmw_IslandboundWalker_begin,
1612         bmw_IslandboundWalker_step,
1613         bmw_IslandboundWalker_yield,
1614         sizeof(BMwIslandboundWalker),
1615         BMW_DEPTH_FIRST,
1616         BM_FACE, /* valid restrict masks */
1617 };
1618
1619 static BMWalker bmw_IslandWalker_Type = {
1620         BM_FACE,
1621         bmw_IslandWalker_begin,
1622         bmw_IslandWalker_step,
1623         bmw_IslandWalker_yield,
1624         sizeof(BMwIslandWalker),
1625         BMW_BREADTH_FIRST,
1626         BM_EDGE | BM_FACE, /* valid restrict masks */
1627 };
1628
1629 static BMWalker bmw_IslandManifoldWalker_Type = {
1630         BM_FACE,
1631         bmw_IslandWalker_begin,
1632         bmw_IslandManifoldWalker_step,  /* only difference with BMW_ISLAND */
1633         bmw_IslandWalker_yield,
1634         sizeof(BMwIslandWalker),
1635         BMW_BREADTH_FIRST,
1636         BM_EDGE | BM_FACE, /* valid restrict masks */
1637 };
1638
1639 static BMWalker bmw_EdgeLoopWalker_Type = {
1640         BM_EDGE,
1641         bmw_EdgeLoopWalker_begin,
1642         bmw_EdgeLoopWalker_step,
1643         bmw_EdgeLoopWalker_yield,
1644         sizeof(BMwEdgeLoopWalker),
1645         BMW_DEPTH_FIRST,
1646         0, /* valid restrict masks */ /* could add flags here but so far none are used */
1647 };
1648
1649 static BMWalker bmw_FaceLoopWalker_Type = {
1650         BM_EDGE,
1651         bmw_FaceLoopWalker_begin,
1652         bmw_FaceLoopWalker_step,
1653         bmw_FaceLoopWalker_yield,
1654         sizeof(BMwFaceLoopWalker),
1655         BMW_DEPTH_FIRST,
1656         0, /* valid restrict masks */ /* could add flags here but so far none are used */
1657 };
1658
1659 static BMWalker bmw_EdgeringWalker_Type = {
1660         BM_EDGE,
1661         bmw_EdgeringWalker_begin,
1662         bmw_EdgeringWalker_step,
1663         bmw_EdgeringWalker_yield,
1664         sizeof(BMwEdgeringWalker),
1665         BMW_DEPTH_FIRST,
1666         BM_EDGE, /* valid restrict masks */
1667 };
1668
1669 static BMWalker bmw_EdgeboundaryWalker_Type = {
1670         BM_EDGE,
1671         bmw_EdgeboundaryWalker_begin,
1672         bmw_EdgeboundaryWalker_step,
1673         bmw_EdgeboundaryWalker_yield,
1674         sizeof(BMwEdgeboundaryWalker),
1675         BMW_DEPTH_FIRST,
1676         0,
1677 };
1678
1679 static BMWalker bmw_UVEdgeWalker_Type = {
1680         BM_LOOP,
1681         bmw_UVEdgeWalker_begin,
1682         bmw_UVEdgeWalker_step,
1683         bmw_UVEdgeWalker_yield,
1684         sizeof(BMwUVEdgeWalker),
1685         BMW_DEPTH_FIRST,
1686         BM_EDGE, /* valid restrict masks */
1687 };
1688
1689 static BMWalker bmw_ConnectedVertexWalker_Type = {
1690         BM_VERT,
1691         bmw_ConnectedVertexWalker_begin,
1692         bmw_ConnectedVertexWalker_step,
1693         bmw_ConnectedVertexWalker_yield,
1694         sizeof(BMwConnectedVertexWalker),
1695         BMW_BREADTH_FIRST,
1696         BM_VERT, /* valid restrict masks */
1697 };
1698
1699 BMWalker *bm_walker_types[] = {
1700         &bmw_VertShellWalker_Type,          /* BMW_VERT_SHELL */
1701         &bmw_LoopShellWalker_Type,          /* BMW_LOOP_SHELL */
1702         &bmw_LoopShellWireWalker_Type,      /* BMW_LOOP_SHELL_WIRE */
1703         &bmw_FaceShellWalker_Type,          /* BMW_FACE_SHELL */
1704         &bmw_EdgeLoopWalker_Type,           /* BMW_EDGELOOP */
1705         &bmw_FaceLoopWalker_Type,           /* BMW_FACELOOP */
1706         &bmw_EdgeringWalker_Type,           /* BMW_EDGERING */
1707         &bmw_EdgeboundaryWalker_Type,       /* BMW_EDGEBOUNDARY */
1708         &bmw_UVEdgeWalker_Type,             /* BMW_LOOPDATA_ISLAND */
1709         &bmw_IslandboundWalker_Type,        /* BMW_ISLANDBOUND */
1710         &bmw_IslandWalker_Type,             /* BMW_ISLAND */
1711         &bmw_IslandManifoldWalker_Type,     /* BMW_ISLAND_MANIFOLD */
1712         &bmw_ConnectedVertexWalker_Type,    /* BMW_CONNECTED_VERTEX */
1713 };
1714
1715 const int bm_totwalkers = ARRAY_SIZE(bm_walker_types);