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