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