dee50151c61e6a3c35eb0590e80549b2e7e483ab
[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_private.h"
37 #include "intern/bmesh_walkers_private.h"
38
39 /* pop into stack memory (common operation) */
40 #define BMW_state_remove_r(walker, owalk) { \
41         memcpy(owalk, BMW_current_state(walker), sizeof(*(owalk))); \
42         BMW_state_remove(walker); \
43 } (void)0
44
45 /** \name Mask Flag Checks
46  * \{ */
47
48 static bool bmw_mask_check_vert(BMWalker *walker, BMVert *v)
49 {
50         if ((walker->flag & BMW_FLAG_TEST_HIDDEN) && BM_elem_flag_test(v, BM_ELEM_HIDDEN)) {
51                 return false;
52         }
53         else if (walker->mask_vert && !BMO_elem_flag_test(walker->bm, v, walker->mask_vert)) {
54                 return false;
55         }
56         else {
57                 return true;
58         }
59 }
60
61 static bool bmw_mask_check_edge(BMWalker *walker, BMEdge *e)
62 {
63         if ((walker->flag & BMW_FLAG_TEST_HIDDEN) && BM_elem_flag_test(e, BM_ELEM_HIDDEN)) {
64                 return false;
65         }
66         else if (walker->mask_edge && !BMO_elem_flag_test(walker->bm, e, walker->mask_edge)) {
67                 return false;
68         }
69         else {
70                 return true;
71         }
72 }
73
74 static bool bmw_mask_check_face(BMWalker *walker, BMFace *f)
75 {
76         if ((walker->flag & BMW_FLAG_TEST_HIDDEN) && BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
77                 return false;
78         }
79         else if (walker->mask_face && !BMO_elem_flag_test(walker->bm, f, walker->mask_face)) {
80                 return false;
81         }
82         else {
83                 return true;
84         }
85 }
86
87 /** \} */
88
89
90 /** \name Shell Walker
91  * \{
92  *
93  * Starts at a vertex on the mesh and walks over the 'shell' it belongs
94  * to via visiting connected edges.
95  *
96  * \todo Add restriction flag/callback for wire edges.
97  */
98 static void bmw_ShellWalker_visitEdge(BMWalker *walker, BMEdge *e)
99 {
100         BMwShellWalker *shellWalk = NULL;
101
102         if (BLI_gset_haskey(walker->visit_set, e)) {
103                 return;
104         }
105
106         if (!bmw_mask_check_edge(walker, e)) {
107                 return;
108         }
109
110         shellWalk = BMW_state_add(walker);
111         shellWalk->curedge = e;
112         BLI_gset_insert(walker->visit_set, e);
113 }
114
115 static void bmw_ShellWalker_begin(BMWalker *walker, void *data)
116 {
117         BMIter eiter;
118         BMHeader *h = data;
119         BMEdge *e;
120         BMVert *v;
121
122         if (UNLIKELY(h == NULL)) {
123                 return;
124         }
125
126         switch (h->htype) {
127                 case BM_VERT:
128                 {
129                         /* starting the walk at a vert, add all the edges
130                          * to the worklist */
131                         v = (BMVert *)h;
132                         BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
133                                 bmw_ShellWalker_visitEdge(walker, e);
134                         }
135                         break;
136                 }
137
138                 case BM_EDGE:
139                 {
140                         /* starting the walk at an edge, add the single edge
141                          * to the worklist */
142                         e = (BMEdge *)h;
143                         bmw_ShellWalker_visitEdge(walker, e);
144                         break;
145                 }
146         }
147 }
148
149 static void *bmw_ShellWalker_yield(BMWalker *walker)
150 {
151         BMwShellWalker *shellWalk = BMW_current_state(walker);
152         return shellWalk->curedge;
153 }
154
155 static void *bmw_ShellWalker_step(BMWalker *walker)
156 {
157         BMwShellWalker *swalk, owalk;
158         BMEdge *e, *e2;
159         BMVert *v;
160         BMIter iter;
161         int i;
162
163         BMW_state_remove_r(walker, &owalk);
164         swalk = &owalk;
165
166         e = swalk->curedge;
167
168         for (i = 0; i < 2; i++) {
169                 v = i ? e->v2 : e->v1;
170                 BM_ITER_ELEM (e2, &iter, v, BM_EDGES_OF_VERT) {
171                         bmw_ShellWalker_visitEdge(walker, e2);
172                 }
173         }
174
175         return e;
176 }
177
178 #if 0
179 static void *bmw_ShellWalker_step(BMWalker *walker)
180 {
181         BMEdge *curedge, *next = NULL;
182         BMVert *v_old = NULL;
183         bool restrictpass = true;
184         BMwShellWalker shellWalk = *((BMwShellWalker *)BMW_current_state(walker));
185         
186         if (!BLI_gset_haskey(walker->visit_set, shellWalk.base)) {
187                 BLI_gset_insert(walker->visit_set, shellWalk.base);
188         }
189
190         BMW_state_remove(walker);
191
192
193         /* find the next edge whose other vertex has not been visite */
194         curedge = shellWalk.curedge;
195         do {
196                 if (!BLI_gset_haskey(walker->visit_set, curedge)) {
197                         if (!walker->restrictflag ||
198                             (walker->restrictflag && BMO_elem_flag_test(walker->bm, curedge, walker->restrictflag)))
199                         {
200                                 BMwShellWalker *newstate;
201
202                                 v_old = BM_edge_other_vert(curedge, shellWalk.base);
203                                 
204                                 /* push a new state onto the stac */
205                                 newState = BMW_state_add(walker);
206                                 BLI_gset_insert(walker->visit_set, curedge);
207                                 
208                                 /* populate the new stat */
209
210                                 newState->base = v_old;
211                                 newState->curedge = curedge;
212                         }
213                 }
214                 curedge = bmesh_disk_edge_next(curedge, shellWalk.base);
215         } while (curedge != shellWalk.curedge);
216         
217         return shellWalk.curedge;
218 }
219 #endif
220
221 /** \} */
222
223
224 /** \name Connected Vertex Walker
225  * \{
226  *
227  * Similar to shell walker, but visits vertices instead of edges.
228  */
229 static void bmw_ConnectedVertexWalker_visitVertex(BMWalker *walker, BMVert *v)
230 {
231         BMwConnectedVertexWalker *vwalk;
232
233         if (BLI_gset_haskey(walker->visit_set, v)) {
234                 /* already visited */
235                 return;
236         }
237
238         if (!bmw_mask_check_vert(walker, v)) {
239                 /* not flagged for walk */
240                 return;
241         }
242
243         vwalk = BMW_state_add(walker);
244         vwalk->curvert = v;
245         BLI_gset_insert(walker->visit_set, v);
246 }
247
248 static void bmw_ConnectedVertexWalker_begin(BMWalker *walker, void *data)
249 {
250         BMVert *v = data;
251         bmw_ConnectedVertexWalker_visitVertex(walker, v);
252 }
253
254 static void *bmw_ConnectedVertexWalker_yield(BMWalker *walker)
255 {
256         BMwConnectedVertexWalker *vwalk = BMW_current_state(walker);
257         return vwalk->curvert;
258 }
259
260 static void *bmw_ConnectedVertexWalker_step(BMWalker *walker)
261 {
262         BMwConnectedVertexWalker *vwalk, owalk;
263         BMVert *v, *v2;
264         BMEdge *e;
265         BMIter iter;
266
267         BMW_state_remove_r(walker, &owalk);
268         vwalk = &owalk;
269
270         v = vwalk->curvert;
271
272         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
273                 v2 = BM_edge_other_vert(e, v);
274                 if (!BLI_gset_haskey(walker->visit_set, v2)) {
275                         bmw_ConnectedVertexWalker_visitVertex(walker, v2);
276                 }
277         }
278
279         return v;
280 }
281
282 /** \} */
283
284
285 /** \name Island Boundary Walker
286  * \{
287  *
288  * Starts at a edge on the mesh and walks over the boundary of an island it belongs to.
289  *
290  * \todo Add restriction flag/callback for wire edges.
291  */
292 static void bmw_IslandboundWalker_begin(BMWalker *walker, void *data)
293 {
294         BMLoop *l = data;
295         BMwIslandboundWalker *iwalk = NULL;
296
297         iwalk = BMW_state_add(walker);
298
299         iwalk->base = iwalk->curloop = l;
300         iwalk->lastv = l->v;
301
302         BLI_gset_insert(walker->visit_set, data);
303
304 }
305
306 static void *bmw_IslandboundWalker_yield(BMWalker *walker)
307 {
308         BMwIslandboundWalker *iwalk = BMW_current_state(walker);
309
310         return iwalk->curloop;
311 }
312
313 static void *bmw_IslandboundWalker_step(BMWalker *walker)
314 {
315         BMwIslandboundWalker *iwalk, owalk;
316         BMVert *v;
317         BMEdge *e;
318         BMFace *f;
319         BMLoop *l;
320         /* int found = 0; */
321
322         memcpy(&owalk, BMW_current_state(walker), sizeof(owalk));
323         /* normally we'd remove here, but delay until after error checking */
324         iwalk = &owalk;
325
326         l = iwalk->curloop;
327         e = l->e;
328
329         v = BM_edge_other_vert(e, iwalk->lastv);
330
331         if (!BM_vert_is_manifold(v)) {
332                 BMW_reset(walker);
333                 BMO_error_raise(walker->bm, NULL, BMERR_WALKER_FAILED,
334                                 "Non-manifold vert while searching region boundary");
335                 return NULL;
336         }
337         
338         /* pop off current state */
339         BMW_state_remove(walker);
340         
341         f = l->f;
342         
343         while (1) {
344                 l = BM_loop_other_edge_loop(l, v);
345                 if (l != l->radial_next) {
346                         l = l->radial_next;
347                         f = l->f;
348                         e = l->e;
349
350                         if (!bmw_mask_check_face(walker, f)) {
351                                 l = l->radial_next;
352                                 break;
353                         }
354                 }
355                 else {
356                         f = l->f;
357                         e = l->e;
358                         break;
359                 }
360         }
361         
362         if (l == owalk.curloop) {
363                 return NULL;
364         }
365         else if (BLI_gset_haskey(walker->visit_set, l)) {
366                 return owalk.curloop;
367         }
368
369         BLI_gset_insert(walker->visit_set, l);
370         iwalk = BMW_state_add(walker);
371         iwalk->base = owalk.base;
372
373         //if (!BMO_elem_flag_test(walker->bm, l->f, walker->restrictflag))
374         //      iwalk->curloop = l->radial_next;
375         iwalk->curloop = l; //else iwalk->curloop = l;
376         iwalk->lastv = v;
377
378         return owalk.curloop;
379 }
380
381
382 /** \name Island Walker
383  * \{
384  *
385  * Starts at a tool flagged-face and walks over the face region
386  *
387  * \todo Add restriction flag/callback for wire edges.
388  */
389 static void bmw_IslandWalker_begin(BMWalker *walker, void *data)
390 {
391         BMwIslandWalker *iwalk = NULL;
392
393         if (!bmw_mask_check_face(walker, data)) {
394                 return;
395         }
396
397         iwalk = BMW_state_add(walker);
398         BLI_gset_insert(walker->visit_set, data);
399
400         iwalk->cur = data;
401 }
402
403 static void *bmw_IslandWalker_yield(BMWalker *walker)
404 {
405         BMwIslandWalker *iwalk = BMW_current_state(walker);
406
407         return iwalk->cur;
408 }
409
410 static void *bmw_IslandWalker_step(BMWalker *walker)
411 {
412         BMwIslandWalker *iwalk, owalk;
413         BMIter iter, liter;
414         BMFace *f;
415         BMLoop *l;
416         
417         BMW_state_remove_r(walker, &owalk);
418         iwalk = &owalk;
419
420         l = BM_iter_new(&liter, walker->bm, BM_LOOPS_OF_FACE, iwalk->cur);
421         for ( ; l; l = BM_iter_step(&liter)) {
422                 /* could skip loop here too, but don't add unless we need it */
423                 if (!bmw_mask_check_edge(walker, l->e)) {
424                         continue;
425                 }
426
427                 f = BM_iter_new(&iter, walker->bm, BM_FACES_OF_EDGE, l->e);
428                 for ( ; f; f = BM_iter_step(&iter)) {
429
430                         if (!bmw_mask_check_face(walker, f)) {
431                                 continue;
432                         }
433
434                         /* saves checking BLI_gset_haskey below (manifold edges theres a 50% chance) */
435                         if (f == iwalk->cur) {
436                                 continue;
437                         }
438
439                         if (BLI_gset_haskey(walker->visit_set, f)) {
440                                 continue;
441                         }
442                         
443                         iwalk = BMW_state_add(walker);
444                         iwalk->cur = f;
445                         BLI_gset_insert(walker->visit_set, f);
446                         break;
447                 }
448         }
449         
450         return owalk.cur;
451 }
452
453 /** \} */
454
455
456 /** \name Edge Loop Walker
457  * \{
458  *
459  * Starts at a tool-flagged edge and walks over the edge loop
460  */
461
462 /* utility function to see if an edge is apart of an ngon boundary */
463 static bool bm_edge_is_single(BMEdge *e)
464 {
465         return ((BM_edge_is_boundary(e)) &&
466                 (e->l->f->len > 4) &&
467                 (BM_edge_is_boundary(e->l->next->e) || BM_edge_is_boundary(e->l->prev->e)));
468 }
469
470 static void bmw_LoopWalker_begin(BMWalker *walker, void *data)
471 {
472         BMwLoopWalker *lwalk = NULL, owalk, *owalk_pt;
473         BMEdge *e = data;
474         BMVert *v;
475         int vert_edge_count[2] = {BM_vert_edge_count_nonwire(e->v1),
476                                   BM_vert_edge_count_nonwire(e->v2)};
477
478         v = e->v1;
479
480         lwalk = BMW_state_add(walker);
481         BLI_gset_insert(walker->visit_set, e);
482
483         lwalk->cur = lwalk->start = e;
484         lwalk->lastv = lwalk->startv = v;
485         lwalk->is_boundary = BM_edge_is_boundary(e);
486         lwalk->is_single = (lwalk->is_boundary && bm_edge_is_single(e));
487
488         /* could also check that vertex*/
489         if ((lwalk->is_boundary == false) &&
490             (vert_edge_count[0] == 3 || vert_edge_count[1] == 3))
491         {
492                 BMIter iter;
493                 BMFace *f_iter;
494                 BMFace *f_best = NULL;
495
496                 BM_ITER_ELEM (f_iter, &iter, e, BM_FACES_OF_EDGE) {
497                         if (f_best == NULL || f_best->len < f_iter->len) {
498                                 f_best = f_iter;
499                         }
500                 }
501
502                 if (f_best) {
503                         /* only use hub selection for 5+ sides else this could
504                          * conflict with normal edge loop selection. */
505                         lwalk->f_hub = f_best->len > 4 ? f_best : NULL;
506                 }
507                 else {
508                         /* edge doesn't have any faces connected to it */
509                         lwalk->f_hub = NULL;
510                 }
511         }
512         else {
513                 lwalk->f_hub = NULL;
514         }
515
516         /* rewind */
517         while ((owalk_pt = BMW_current_state(walker))) {
518                 owalk = *((BMwLoopWalker *)owalk_pt);
519                 BMW_walk(walker);
520         }
521
522         lwalk = BMW_state_add(walker);
523         *lwalk = owalk;
524
525         lwalk->lastv = lwalk->startv = BM_edge_other_vert(owalk.cur, lwalk->lastv);
526
527         BLI_gset_clear(walker->visit_set, NULL);
528         BLI_gset_insert(walker->visit_set, owalk.cur);
529 }
530
531 static void *bmw_LoopWalker_yield(BMWalker *walker)
532 {
533         BMwLoopWalker *lwalk = BMW_current_state(walker);
534
535         return lwalk->cur;
536 }
537
538 static void *bmw_LoopWalker_step(BMWalker *walker)
539 {
540         BMwLoopWalker *lwalk, owalk;
541         BMEdge *e, *nexte = NULL;
542         BMLoop *l;
543         BMVert *v;
544         int i = 0;
545
546         BMW_state_remove_r(walker, &owalk);
547         lwalk = &owalk;
548
549         e = lwalk->cur;
550         l = e->l;
551
552         if (owalk.f_hub) { /* NGON EDGE */
553                 int vert_edge_tot;
554
555                 v = BM_edge_other_vert(e, lwalk->lastv);
556
557                 vert_edge_tot = BM_vert_edge_count_nonwire(v);
558
559                 if (vert_edge_tot == 3) {
560                         l = BM_face_other_vert_loop(owalk.f_hub, lwalk->lastv, v);
561                         nexte = BM_edge_exists(v, l->v);
562
563                         if (bmw_mask_check_edge(walker, nexte) &&
564                             !BLI_gset_haskey(walker->visit_set, nexte) &&
565                             /* never step onto a boundary edge, this gives odd-results */
566                             (BM_edge_is_boundary(nexte) == false))
567                         {
568                                 lwalk = BMW_state_add(walker);
569                                 lwalk->cur = nexte;
570                                 lwalk->lastv = v;
571
572                                 lwalk->is_boundary = owalk.is_boundary;
573                                 lwalk->is_single = owalk.is_single;
574                                 lwalk->f_hub = owalk.f_hub;
575
576                                 BLI_gset_insert(walker->visit_set, nexte);
577                         }
578                 }
579         }
580         else if (l == NULL) {  /* WIRE EDGE */
581                 BMIter eiter;
582
583                 /* match trunk: mark all connected wire edges */
584                 for (i = 0; i < 2; i++) {
585                         v = i ? e->v2 : e->v1;
586
587                         BM_ITER_ELEM (nexte, &eiter, v, BM_EDGES_OF_VERT) {
588                                 if ((nexte->l == NULL) &&
589                                     bmw_mask_check_edge(walker, nexte) &&
590                                     !BLI_gset_haskey(walker->visit_set, nexte))
591                                 {
592                                         lwalk = BMW_state_add(walker);
593                                         lwalk->cur = nexte;
594                                         lwalk->lastv = v;
595
596                                         lwalk->is_boundary = owalk.is_boundary;
597                                         lwalk->is_single = owalk.is_single;
598                                         lwalk->f_hub = owalk.f_hub;
599
600                                         BLI_gset_insert(walker->visit_set, nexte);
601                                 }
602                         }
603                 }
604         }
605         else if (owalk.is_boundary == false) {  /* NORMAL EDGE WITH FACES */
606                 int vert_edge_tot;
607
608                 v = BM_edge_other_vert(e, lwalk->lastv);
609
610                 vert_edge_tot = BM_vert_edge_count_nonwire(v);
611
612                 /* typical loopiong over edges in the middle of a mesh */
613                 /* however, why use 2 here at all? I guess for internal ngon loops it can be useful. Antony R. */
614                 if (vert_edge_tot == 4 || vert_edge_tot == 2) {
615                         int i_opposite = vert_edge_tot / 2;
616                         int i = 0;
617                         do {
618                                 l = BM_loop_other_edge_loop(l, v);
619                                 if (BM_edge_is_manifold(l->e)) {
620                                         l = l->radial_next;
621                                 }
622                                 else {
623                                         l = NULL;
624                                         break;
625                                 }
626                         } while ((++i != i_opposite));
627                 }
628                 else {
629                         l = NULL;
630                 }
631
632                 if (l != NULL) {
633                         if (l != e->l &&
634                             bmw_mask_check_edge(walker, l->e) &&
635                             !BLI_gset_haskey(walker->visit_set, l->e))
636                         {
637                                 lwalk = BMW_state_add(walker);
638                                 lwalk->cur = l->e;
639                                 lwalk->lastv = v;
640
641                                 lwalk->is_boundary = owalk.is_boundary;
642                                 lwalk->is_single = owalk.is_single;
643                                 lwalk->f_hub = owalk.f_hub;
644
645                                 BLI_gset_insert(walker->visit_set, l->e);
646                         }
647                 }
648         }
649         else if (owalk.is_boundary == true) {  /* BOUNDARY EDGE WITH FACES */
650                 int vert_edge_tot;
651
652                 v = BM_edge_other_vert(e, lwalk->lastv);
653
654                 vert_edge_tot = BM_vert_edge_count_nonwire(v);
655
656                 /* check if we should step, this is fairly involved */
657                 if (
658                     /* walk over boundary of faces but stop at corners */
659                     (owalk.is_single == false && vert_edge_tot > 2) ||
660
661                     /* initial edge was a boundary, so is this edge and vertex is only apart of this face
662                     * this lets us walk over the the boundary of an ngon which is handy */
663                     (owalk.is_single == true && vert_edge_tot == 2 && BM_edge_is_boundary(e)))
664                 {
665                         /* find next boundary edge in the fan */
666                         do {
667                                 l = BM_loop_other_edge_loop(l, v);
668                                 if (BM_edge_is_manifold(l->e)) {
669                                         l = l->radial_next;
670                                 }
671                                 else if (BM_edge_is_boundary(l->e)) {
672                                         break;
673                                 }
674                                 else {
675                                         l = NULL;
676                                         break;
677                                 }
678                         } while (true);
679                 }
680
681                 if (owalk.is_single == false && l && bm_edge_is_single(l->e)) {
682                         l = NULL;
683                 }
684
685                 if (l != NULL) {
686                         if (l != e->l &&
687                             bmw_mask_check_edge(walker, l->e) &&
688                             !BLI_gset_haskey(walker->visit_set, l->e))
689                         {
690                                 lwalk = BMW_state_add(walker);
691                                 lwalk->cur = l->e;
692                                 lwalk->lastv = v;
693
694                                 lwalk->is_boundary = owalk.is_boundary;
695                                 lwalk->is_single = owalk.is_single;
696                                 lwalk->f_hub = owalk.f_hub;
697
698                                 BLI_gset_insert(walker->visit_set, l->e);
699                         }
700                 }
701         }
702
703         return owalk.cur;
704 }
705
706 /** \} */
707
708
709 /** \name Face Loop Walker
710  * \{
711  *
712  * Starts at a tool-flagged face and walks over the face loop
713  * Conditions for starting and stepping the face loop have been
714  * tuned in an attempt to match the face loops built by EditMesh
715  */
716
717 /* Check whether the face loop should includes the face specified
718  * by the given BMLoop */
719 static bool bmw_FaceLoopWalker_include_face(BMWalker *walker, BMLoop *l)
720 {
721         /* face must have degree 4 */
722         if (l->f->len != 4) {
723                 return false;
724         }
725
726         if (!bmw_mask_check_face(walker, l->f)) {
727                 return false;
728         }
729
730         /* the face must not have been already visited */
731         if (BLI_gset_haskey(walker->visit_set, l->f) && BLI_gset_haskey(walker->visit_set_alt, l->e)) {
732                 return false;
733         }
734
735         return true;
736 }
737
738 /* Check whether the face loop can start from the given edge */
739 static bool bmw_FaceLoopWalker_edge_begins_loop(BMWalker *walker, BMEdge *e)
740 {
741         /* There is no face loop starting from a wire edge */
742         if (BM_edge_is_wire(e)) {
743                 return false;
744         }
745         
746         /* Don't start a loop from a boundary edge if it cannot
747          * be extended to cover any faces */
748         if (BM_edge_is_boundary(e)) {
749                 if (!bmw_FaceLoopWalker_include_face(walker, e->l)) {
750                         return false;
751                 }
752         }
753         
754         /* Don't start a face loop from non-manifold edges */
755         if (!BM_edge_is_manifold(e)) {
756                 return false;
757         }
758
759         return true;
760 }
761
762 static void bmw_FaceLoopWalker_begin(BMWalker *walker, void *data)
763 {
764         BMwFaceLoopWalker *lwalk, owalk, *owalk_pt;
765         BMEdge *e = data;
766         /* BMesh *bm = walker->bm; */ /* UNUSED */
767         /* int fcount = BM_edge_face_count(e); */ /* UNUSED */
768
769         if (!bmw_FaceLoopWalker_edge_begins_loop(walker, e))
770                 return;
771
772         lwalk = BMW_state_add(walker);
773         lwalk->l = e->l;
774         lwalk->no_calc = false;
775         BLI_gset_insert(walker->visit_set, lwalk->l->f);
776
777         /* rewind */
778         while ((owalk_pt = BMW_current_state(walker))) {
779                 owalk = *((BMwFaceLoopWalker *)owalk_pt);
780                 BMW_walk(walker);
781         }
782
783         lwalk = BMW_state_add(walker);
784         *lwalk = owalk;
785         lwalk->no_calc = false;
786
787         BLI_gset_clear(walker->visit_set_alt, NULL);
788         BLI_gset_insert(walker->visit_set_alt, lwalk->l->e);
789
790         BLI_gset_clear(walker->visit_set, NULL);
791         BLI_gset_insert(walker->visit_set, lwalk->l->f);
792 }
793
794 static void *bmw_FaceLoopWalker_yield(BMWalker *walker)
795 {
796         BMwFaceLoopWalker *lwalk = BMW_current_state(walker);
797         
798         if (!lwalk) {
799                 return NULL;
800         }
801
802         return lwalk->l->f;
803 }
804
805 static void *bmw_FaceLoopWalker_step(BMWalker *walker)
806 {
807         BMwFaceLoopWalker *lwalk, owalk;
808         BMFace *f;
809         BMLoop *l;
810
811         BMW_state_remove_r(walker, &owalk);
812         lwalk = &owalk;
813
814         f = lwalk->l->f;
815         l = lwalk->l->radial_next;
816         
817         if (lwalk->no_calc) {
818                 return f;
819         }
820
821         if (!bmw_FaceLoopWalker_include_face(walker, l)) {
822                 l = lwalk->l;
823                 l = l->next->next;
824                 if (!BM_edge_is_manifold(l->e)) {
825                         l = l->prev->prev;
826                 }
827                 l = l->radial_next;
828         }
829
830         if (bmw_FaceLoopWalker_include_face(walker, l)) {
831                 lwalk = BMW_state_add(walker);
832                 lwalk->l = l;
833
834                 if (l->f->len != 4) {
835                         lwalk->no_calc = true;
836                         lwalk->l = owalk.l;
837                 }
838                 else {
839                         lwalk->no_calc = false;
840                 }
841
842                 /* both may already exist */
843                 BLI_gset_reinsert(walker->visit_set_alt, l->e, NULL);
844                 BLI_gset_reinsert(walker->visit_set, l->f, NULL);
845         }
846
847         return f;
848 }
849
850 /** \} */
851
852
853 // #define BMW_EDGERING_NGON
854
855 /** \name Edge Ring Walker
856  * \{
857  *
858  * Starts at a tool-flagged edge and walks over the edge ring
859  * Conditions for starting and stepping the edge ring have been
860  * tuned in an attempt to match the edge rings built by EditMesh
861  */
862 static void bmw_EdgeringWalker_begin(BMWalker *walker, void *data)
863 {
864         BMwEdgeringWalker *lwalk, owalk, *owalk_pt;
865         BMEdge *e = data;
866
867         lwalk = BMW_state_add(walker);
868         lwalk->l = e->l;
869
870         if (!lwalk->l) {
871                 lwalk->wireedge = e;
872                 return;
873         }
874         else {
875                 lwalk->wireedge = NULL;
876         }
877
878         BLI_gset_insert(walker->visit_set, lwalk->l->e);
879
880         /* rewind */
881         while ((owalk_pt = BMW_current_state(walker))) {
882                 owalk = *((BMwEdgeringWalker *)owalk_pt);
883                 BMW_walk(walker);
884         }
885
886         lwalk = BMW_state_add(walker);
887         *lwalk = owalk;
888
889 #ifdef BMW_EDGERING_NGON
890         if (lwalk->l->f->len % 2 != 0)
891 #else
892         if (lwalk->l->f->len != 4)
893 #endif
894         {
895                 lwalk->l = lwalk->l->radial_next;
896         }
897
898         BLI_gset_clear(walker->visit_set, NULL);
899         BLI_gset_insert(walker->visit_set, lwalk->l->e);
900 }
901
902 static void *bmw_EdgeringWalker_yield(BMWalker *walker)
903 {
904         BMwEdgeringWalker *lwalk = BMW_current_state(walker);
905         
906         if (!lwalk) {
907                 return NULL;
908         }
909
910         if (lwalk->l) {
911                 return lwalk->l->e;
912         }
913         else {
914                 return lwalk->wireedge;
915         }
916 }
917
918 static void *bmw_EdgeringWalker_step(BMWalker *walker)
919 {
920         BMwEdgeringWalker *lwalk, owalk;
921         BMEdge *e;
922         BMLoop *l;
923 #ifdef BMW_EDGERING_NGON
924         int i, len;
925 #endif
926
927 #define EDGE_CHECK(e) (bmw_mask_check_edge(walker, e) && (BM_edge_is_boundary(e) || BM_edge_is_manifold(e)))
928
929         BMW_state_remove_r(walker, &owalk);
930         lwalk = &owalk;
931
932         l = lwalk->l;
933         if (!l)
934                 return lwalk->wireedge;
935
936         e = l->e;
937         if (!EDGE_CHECK(e)) {
938                 /* walker won't traverse to a non-manifold edge, but may
939                  * be started on one, and should not traverse *away* from
940                  * a non-manifold edge (non-manifold edges are never in an
941                  * edge ring with manifold edges */
942                 return e;
943         }
944
945 #ifdef BMW_EDGERING_NGON
946         l = l->radial_next;
947
948         i = len = l->f->len;
949         while (i > 0) {
950                 l = l->next;
951                 i -= 2;
952         }
953
954         if ((len <= 0) || (len % 2 != 0) || !EDGE_CHECK(l->e) ||
955             !bmw_mask_check_face(walker, l->f))
956         {
957                 l = owalk.l;
958                 i = len;
959                 while (i > 0) {
960                         l = l->next;
961                         i -= 2;
962                 }
963         }
964         /* only walk to manifold edge */
965         if ((l->f->len % 2 == 0) && EDGE_CHECK(l->e) &&
966             !BLI_gset_haskey(walker->visit_set, l->e))
967
968 #else
969
970         l = l->radial_next;
971         l = l->next->next;
972         
973         if ((l->f->len != 4) || !EDGE_CHECK(l->e) || !bmw_mask_check_face(walker, l->f)) {
974                 l = owalk.l->next->next;
975         }
976         /* only walk to manifold edge */
977         if ((l->f->len == 4) && EDGE_CHECK(l->e) &&
978             !BLI_gset_haskey(walker->visit_set, l->e))
979 #endif
980         {
981                 lwalk = BMW_state_add(walker);
982                 lwalk->l = l;
983                 lwalk->wireedge = NULL;
984
985                 BLI_gset_insert(walker->visit_set, l->e);
986         }
987
988         return e;
989
990 #undef EDGE_CHECK
991 }
992
993 /** \} */
994
995
996 /** \name UV Edge Walker
997  * \{ */
998
999 static void bmw_UVEdgeWalker_begin(BMWalker *walker, void *data)
1000 {
1001         BMwUVEdgeWalker *lwalk;
1002         BMLoop *l = data;
1003
1004         if (BLI_gset_haskey(walker->visit_set, l))
1005                 return;
1006
1007         lwalk = BMW_state_add(walker);
1008         lwalk->l = l;
1009         BLI_gset_insert(walker->visit_set, l);
1010 }
1011
1012 static void *bmw_UVEdgeWalker_yield(BMWalker *walker)
1013 {
1014         BMwUVEdgeWalker *lwalk = BMW_current_state(walker);
1015         
1016         if (!lwalk) {
1017                 return NULL;
1018         }
1019
1020         return lwalk->l;
1021 }
1022
1023 static void *bmw_UVEdgeWalker_step(BMWalker *walker)
1024 {
1025         const int type = walker->bm->ldata.layers[walker->layer].type;
1026         BMwUVEdgeWalker *lwalk, owalk;
1027         BMLoop *l, *l2, *l3, *nl, *cl;
1028         BMIter liter;
1029         void *d1, *d2;
1030         int i, j, rlen;
1031
1032         BMW_state_remove_r(walker, &owalk);
1033         lwalk = &owalk;
1034
1035         l = lwalk->l;
1036         nl = l->next;
1037
1038         if (!bmw_mask_check_edge(walker, l->e)) {
1039                 return l;
1040         }
1041
1042         /* go over loops around l->v and nl->v and see which ones share l and nl's
1043          * mloopuv's coordinates. in addition, push on l->next if necessary */
1044         for (i = 0; i < 2; i++) {
1045                 cl = i ? nl : l;
1046                 BM_ITER_ELEM (l2, &liter, cl->v, BM_LOOPS_OF_VERT) {
1047                         d1 = CustomData_bmesh_get_layer_n(&walker->bm->ldata,
1048                                                           cl->head.data, walker->layer);
1049                         
1050                         rlen = BM_edge_face_count(l2->e);
1051                         for (j = 0; j < rlen; j++) {
1052                                 if (BLI_gset_haskey(walker->visit_set, l2)) {
1053                                         continue;
1054                                 }
1055
1056                                 if (!bmw_mask_check_edge(walker, l2->e)) {
1057                                         if (l2->v != cl->v) {
1058                                                 continue;
1059                                         }
1060                                 }
1061
1062                                 l3 = l2->v != cl->v ? l2->next : l2;
1063                                 d2 = CustomData_bmesh_get_layer_n(&walker->bm->ldata,
1064                                                                   l3->head.data, walker->layer);
1065
1066                                 if (!CustomData_data_equals(type, d1, d2))
1067                                         continue;
1068                                 
1069                                 lwalk = BMW_state_add(walker);
1070                                 BLI_gset_insert(walker->visit_set, l2);
1071
1072                                 lwalk->l = l2;
1073
1074                                 l2 = l2->radial_next;
1075                         }
1076                 }
1077         }
1078
1079         return l;
1080 }
1081
1082 /** \} */
1083
1084
1085 static BMWalker bmw_ShellWalker_Type = {
1086         bmw_ShellWalker_begin,
1087         bmw_ShellWalker_step,
1088         bmw_ShellWalker_yield,
1089         sizeof(BMwShellWalker),
1090         BMW_BREADTH_FIRST,
1091         BM_EDGE, /* valid restrict masks */
1092 };
1093
1094 static BMWalker bmw_IslandboundWalker_Type = {
1095         bmw_IslandboundWalker_begin,
1096         bmw_IslandboundWalker_step,
1097         bmw_IslandboundWalker_yield,
1098         sizeof(BMwIslandboundWalker),
1099         BMW_DEPTH_FIRST,
1100         BM_FACE, /* valid restrict masks */
1101 };
1102
1103 static BMWalker bmw_IslandWalker_Type = {
1104         bmw_IslandWalker_begin,
1105         bmw_IslandWalker_step,
1106         bmw_IslandWalker_yield,
1107         sizeof(BMwIslandWalker),
1108         BMW_BREADTH_FIRST,
1109         BM_EDGE | BM_FACE, /* valid restrict masks */
1110 };
1111
1112 static BMWalker bmw_LoopWalker_Type = {
1113         bmw_LoopWalker_begin,
1114         bmw_LoopWalker_step,
1115         bmw_LoopWalker_yield,
1116         sizeof(BMwLoopWalker),
1117         BMW_DEPTH_FIRST,
1118         0, /* valid restrict masks */ /* could add flags here but so far none are used */
1119 };
1120
1121 static BMWalker bmw_FaceLoopWalker_Type = {
1122         bmw_FaceLoopWalker_begin,
1123         bmw_FaceLoopWalker_step,
1124         bmw_FaceLoopWalker_yield,
1125         sizeof(BMwFaceLoopWalker),
1126         BMW_DEPTH_FIRST,
1127         0, /* valid restrict masks */ /* could add flags here but so far none are used */
1128 };
1129
1130 static BMWalker bmw_EdgeringWalker_Type = {
1131         bmw_EdgeringWalker_begin,
1132         bmw_EdgeringWalker_step,
1133         bmw_EdgeringWalker_yield,
1134         sizeof(BMwEdgeringWalker),
1135         BMW_DEPTH_FIRST,
1136         0, /* valid restrict masks */ /* could add flags here but so far none are used */
1137 };
1138
1139 static BMWalker bmw_UVEdgeWalker_Type = {
1140         bmw_UVEdgeWalker_begin,
1141         bmw_UVEdgeWalker_step,
1142         bmw_UVEdgeWalker_yield,
1143         sizeof(BMwUVEdgeWalker),
1144         BMW_DEPTH_FIRST,
1145         BM_EDGE, /* valid restrict masks */
1146 };
1147
1148 static BMWalker bmw_ConnectedVertexWalker_Type = {
1149         bmw_ConnectedVertexWalker_begin,
1150         bmw_ConnectedVertexWalker_step,
1151         bmw_ConnectedVertexWalker_yield,
1152         sizeof(BMwConnectedVertexWalker),
1153         BMW_BREADTH_FIRST,
1154         BM_VERT, /* valid restrict masks */
1155 };
1156
1157 BMWalker *bm_walker_types[] = {
1158         &bmw_ShellWalker_Type,              /* BMW_SHELL */
1159         &bmw_LoopWalker_Type,               /* BMW_LOOP */
1160         &bmw_FaceLoopWalker_Type,           /* BMW_FACELOOP */
1161         &bmw_EdgeringWalker_Type,           /* BMW_EDGERING */
1162         &bmw_UVEdgeWalker_Type,             /* BMW_LOOPDATA_ISLAND */
1163         &bmw_IslandboundWalker_Type,        /* BMW_ISLANDBOUND */
1164         &bmw_IslandWalker_Type,             /* BMW_ISLAND */
1165         &bmw_ConnectedVertexWalker_Type,    /* BMW_CONNECTED_VERTEX */
1166 };
1167
1168 const int bm_totwalkers = sizeof(bm_walker_types) / sizeof(*bm_walker_types);