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