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