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