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