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