part 1 of cleaning up my little array macro library to be a formal API. also removed...
[blender.git] / source / blender / bmesh / intern / bmesh_walkers.c
1 #include <stdio.h>
2 #include <string.h>
3
4 #include "BKE_utildefines.h"
5 #include "BKE_customdata.h"
6
7 #include "DNA_meshdata_types.h"
8 #include "DNA_mesh_types.h"
9
10 #include "BLI_mempool.h"
11 #include "BLI_array.h"
12
13 #include "bmesh_private.h"
14 #include "bmesh_walkers.h"
15
16 #include "bmesh.h"
17
18 /*
19  - joeedh -
20  design notes:
21
22  original desing: walkers directly emulation recursive functions.
23  functions save their state onto a stack, and also push new states
24  to implement recursive or looping behaviour.  generally only one
25  state push per call with a specific state is desired.
26
27  basic design pattern: the walker step function goes through it's
28  list of possible choices for recursion, and recurses (by pushing a new state)
29  using the first non-visited one.  this choise is the flagged as visited using
30  the ghash.  each step may push multiple new states onto the stack at once.
31
32  * walkers use tool flags, not header flags
33  * walkers now use ghash for storing visited elements, 
34    rather then stealing flags.  ghash can be rewritten 
35    to be faster if necassary, in the far future :) .
36  * tools should ALWAYS have necassary error handling
37    for if walkers fail.
38 */
39
40 typedef struct shellWalker{
41         struct shellWalker *prev;
42         BMVert *base;                   
43         BMEdge *curedge, *current;
44 } shellWalker;
45
46 typedef struct islandboundWalker {
47         struct islandboundWalker *prev;
48         BMLoop *base;
49         BMVert *lastv;
50         BMLoop *curloop;
51 } islandboundWalker;
52
53 typedef struct islandWalker {
54         struct islandWalker * prev;
55         BMFace *cur;
56 } islandWalker;
57
58 typedef struct loopWalker {
59         struct loopWalker * prev;
60         BMEdge *cur, *start;
61         BMVert *lastv, *startv;
62         int startrad, stage2;
63 } loopWalker;
64
65 typedef struct faceloopWalker {
66         struct faceloopWalker * prev;
67         BMLoop *l;
68         int nocalc;
69 } faceloopWalker;
70
71 typedef struct edgeringWalker {
72         struct edgeringWalker * prev;
73         BMLoop *l;
74 } edgeringWalker;
75
76 typedef struct uvedgeWalker {
77         struct uvedgeWalker *prev;
78         BMLoop *l;
79 } uvedgeWalker;
80
81 /*  NOTE: this comment is out of date, update it - joeedh
82  *      BMWalker - change this to use the filters functions.
83  *      
84  *      A generic structure for maintaing the state and callbacks nessecary for walking over
85  *  the surface of a mesh. An example of usage:
86  *
87  *           BMEdge *edge;
88  *           BMWalker *walker = BMW_create(BM_SHELLWALKER, BM_SELECT);
89  *       walker->begin(walker, vert);
90  *       for(edge = BMW_walk(walker); edge; edge = bmeshWwalker_walk(walker)){
91  *            bmesh_select_edge(edge);
92  *       }
93  *       BMW_free(walker);
94  *
95  *      The above example creates a walker that walks over the surface a mesh by starting at
96  *  a vertex and traveling across its edges to other vertices, and repeating the process
97  *  over and over again until it has visited each vertex in the shell. An additional restriction
98  *  is passed into the BMW_create function stating that we are only interested
99  *  in walking over edges that have been flagged with the bitmask 'BM_SELECT'.
100  *
101  *
102 */
103
104 /*Forward declerations*/
105 static void *BMW_walk(struct BMWalker *walker);
106 static void BMW_popstate(struct BMWalker *walker);
107 static void BMW_pushstate(struct BMWalker *walker);
108
109 static void shellWalker_begin(struct BMWalker *walker, void *data);
110 static void *shellWalker_yield(struct BMWalker *walker);
111 static void *shellWalker_step(struct BMWalker *walker);
112
113 static void islandboundWalker_begin(BMWalker *walker, void *data);
114 static void *islandboundWalker_yield(BMWalker *walker);
115 static void *islandboundWalker_step(BMWalker *walker);
116
117 static void islandWalker_begin(BMWalker *walker, void *data);
118 static void *islandWalker_yield(BMWalker *walker);
119 static void *islandWalker_step(BMWalker *walker);
120
121 static void loopWalker_begin(BMWalker *walker, void *data);
122 static void *loopWalker_yield(BMWalker *walker);
123 static void *loopWalker_step(BMWalker *walker);
124
125 static void faceloopWalker_begin(BMWalker *walker, void *data);
126 static void *faceloopWalker_yield(BMWalker *walker);
127 static void *faceloopWalker_step(BMWalker *walker);
128
129 static void edgeringWalker_begin(BMWalker *walker, void *data);
130 static void *edgeringWalker_yield(BMWalker *walker);
131 static void *edgeringWalker_step(BMWalker *walker);
132
133 static void uvedgeWalker_begin(BMWalker *walker, void *data);
134 static void *uvedgeWalker_yield(BMWalker *walker);
135 static void *uvedgeWalker_step(BMWalker *walker);
136
137 /* Pointer hiding*/
138 typedef struct bmesh_walkerGeneric{
139         struct bmesh_walkerGeneric *prev;
140 } bmesh_walkerGeneric;
141
142
143 void *BMW_Begin(BMWalker *walker, void *start) {
144         walker->begin(walker, start);
145         
146         return walker->currentstate ? walker->step(walker) : NULL;
147 }
148
149 /*
150  * BMW_CREATE
151  * 
152  * Allocates and returns a new mesh walker of 
153  * a given type. The elements visited are filtered
154  * by the bitmask 'searchmask'.
155  *
156 */
157
158 void BMW_Init(BMWalker *walker, BMesh *bm, int type, int searchmask, int flag)
159 {
160         int size = 0;
161         
162         memset(walker, 0, sizeof(BMWalker));
163
164         walker->flag = flag;
165         walker->bm = bm;
166         walker->restrictflag = searchmask;
167         walker->visithash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
168
169         switch(type){
170                 case BMW_SHELL:
171                         walker->begin = shellWalker_begin;
172                         walker->step = shellWalker_step;
173                         walker->yield = shellWalker_yield;
174                         size = sizeof(shellWalker);             
175                         break;
176                 case BMW_ISLANDBOUND:
177                         walker->begin = islandboundWalker_begin;
178                         walker->step = islandboundWalker_step;
179                         walker->yield = islandboundWalker_yield;
180                         size = sizeof(islandboundWalker);               
181                         break;
182                 case BMW_ISLAND:
183                         walker->begin = islandWalker_begin;
184                         walker->step = islandWalker_step;
185                         walker->yield = islandWalker_yield;
186                         size = sizeof(islandWalker);            
187                         break;
188                 case BMW_LOOP:
189                         walker->begin = loopWalker_begin;
190                         walker->step = loopWalker_step;
191                         walker->yield = loopWalker_yield;
192                         size = sizeof(loopWalker);
193                         break;
194                 case BMW_FACELOOP:
195                         walker->begin = faceloopWalker_begin;
196                         walker->step = faceloopWalker_step;
197                         walker->yield = faceloopWalker_yield;
198                         size = sizeof(faceloopWalker);
199                         break;
200                 case BMW_EDGERING:
201                         walker->begin = edgeringWalker_begin;
202                         walker->step = edgeringWalker_step;
203                         walker->yield = edgeringWalker_yield;
204                         size = sizeof(edgeringWalker);
205                         break;
206                 case BMW_LOOPDATA_ISLAND:
207                         walker->begin = uvedgeWalker_begin;
208                         walker->step = uvedgeWalker_step;
209                         walker->yield = uvedgeWalker_yield;
210                         size = sizeof(uvedgeWalker);
211                         break;
212                 default:
213                         break;
214         }
215         walker->stack = BLI_mempool_create(size, 100, 100);
216         walker->currentstate = NULL;
217 }
218
219 /*
220  * BMW_End
221  *
222  * Frees a walker's stack.
223  *
224 */
225
226 void BMW_End(BMWalker *walker)
227 {
228         BLI_mempool_destroy(walker->stack);
229         BLI_ghash_free(walker->visithash, NULL, NULL);
230 }
231
232
233 /*
234  * BMW_Step
235  *
236 */
237
238 void *BMW_Step(BMWalker *walker)
239 {
240         BMHeader *head;
241
242         head = BMW_walk(walker);
243
244         return head;
245 }
246
247 /*
248  * BMW_WALK
249  *
250  * Steps a mesh walker forward by one element
251  *
252  * TODO:
253  *  -add searchmask filtering
254  *
255 */
256
257 static void *BMW_walk(BMWalker *walker)
258 {
259         void *current = NULL;
260
261         while(walker->currentstate){
262                 current = walker->step(walker);
263                 if(current) return current;
264         }
265         return NULL;
266 }
267
268 /*
269  * BMW_popstate
270  *
271  * Pops the current walker state off the stack
272  * and makes the previous state current
273  *
274 */
275
276 static void BMW_popstate(BMWalker *walker)
277 {
278         void *oldstate;
279         oldstate = walker->currentstate;
280         walker->currentstate 
281                 = ((bmesh_walkerGeneric*)walker->currentstate)->prev;
282         BLI_mempool_free(walker->stack, oldstate);
283 }
284
285 /*
286  * BMW_pushstate
287  *
288  * Pushes the current state down the stack and allocates
289  * a new one.
290  *
291 */
292
293 static void BMW_pushstate(BMWalker *walker)
294 {
295         bmesh_walkerGeneric *newstate;
296         newstate = BLI_mempool_alloc(walker->stack);
297         newstate->prev = walker->currentstate;
298         walker->currentstate = newstate;
299 }
300
301 void BMW_reset(BMWalker *walker) {
302         while (walker->currentstate) {
303                 BMW_popstate(walker);
304         }
305 }
306
307 /*      Shell Walker:
308  *
309  *      Starts at a vertex on the mesh and walks over the 'shell' it belongs 
310  *      to via visiting connected edges.
311  *
312  *      TODO:
313  *
314  *  Add restriction flag/callback for wire edges.
315  * 
316 */
317
318 static void shellWalker_begin(BMWalker *walker, void *data){
319         BMIter eiter;
320         BMEdge *e;
321         BMVert *v = data;
322         shellWalker *shellWalk = NULL;
323
324         if (!v->edge)
325                 return;
326
327         if (walker->restrictflag) {
328                 BM_ITER(e, &eiter, walker->bm, BM_EDGES_OF_VERT, v) {
329                         if (BMO_TestFlag(walker->bm, e, walker->restrictflag))
330                                 break;
331                 }
332         } else {
333                 e = v->edge;
334         }
335
336         if (!e) 
337                 return;
338
339         if (BLI_ghash_haskey(walker->visithash, e))
340                 return;
341
342         BMW_pushstate(walker);
343
344         shellWalk = walker->currentstate;
345         shellWalk->base = v;
346         shellWalk->curedge = e;
347         BLI_ghash_insert(walker->visithash, e, NULL);
348 }
349
350 static void *shellWalker_yield(BMWalker *walker)
351 {
352         shellWalker *shellWalk = walker->currentstate;
353         return shellWalk->curedge;
354 }
355
356 static void *shellWalker_step(BMWalker *walker)
357 {
358         shellWalker *swalk = walker->currentstate;
359         BMEdge *e, *e2;
360         BMVert *v;
361         BMIter iter;
362         int i;
363
364         BMW_popstate(walker);
365
366         e = swalk->curedge;
367         for (i=0; i<2; i++) {
368                 v = i ? e->v2 : e->v1;
369                 BM_ITER(e2, &iter, walker->bm, BM_EDGES_OF_VERT, v) {
370                         if (walker->restrictflag && !BMO_TestFlag(walker->bm, e2, walker->restrictflag))
371                                 continue;
372                         if (BLI_ghash_haskey(walker->visithash, e2))
373                                 continue;
374                         
375                         BMW_pushstate(walker);
376                         BLI_ghash_insert(walker->visithash, e2, NULL);
377
378                         swalk = walker->currentstate;
379                         swalk->curedge = e2;
380                 }
381         }
382
383         return e;
384 }
385
386 #if 0
387 static void *shellWalker_step(BMWalker *walker)
388 {
389         BMEdge *curedge, *next = NULL;
390         BMVert *ov = NULL;
391         int restrictpass = 1;
392         shellWalker shellWalk = *((shellWalker*)walker->currentstate);
393         
394         if (!BLI_ghash_haskey(walker->visithash, shellWalk.base))
395                 BLI_ghash_insert(walker->visithash, shellWalk.base, NULL);
396
397         BMW_popstate(walker);
398
399
400         /*find the next edge whose other vertex has not been visited*/
401         curedge = shellWalk.curedge;
402         do{
403                 if (!BLI_ghash_haskey(walker->visithash, curedge)) { 
404                         if(!walker->restrictflag || (walker->restrictflag &&
405                            BMO_TestFlag(walker->bm, curedge, walker->restrictflag)))
406                         {
407                                 ov = BM_OtherEdgeVert(curedge, shellWalk.base);
408                                 
409                                 /*push a new state onto the stack*/
410                                 BMW_pushstate(walker);
411                                 BLI_ghash_insert(walker->visithash, curedge, NULL);
412                                 
413                                 /*populate the new state*/
414
415                                 ((shellWalker*)walker->currentstate)->base = ov;
416                                 ((shellWalker*)walker->currentstate)->curedge = curedge;
417                         }
418                 }
419                 curedge = bmesh_disk_nextedge(curedge, shellWalk.base);
420         }while(curedge != shellWalk.curedge);
421         
422         return shellWalk.curedge;
423 }
424 #endif
425
426 /*      Island Boundary Walker:
427  *
428  *      Starts at a edge on the mesh and walks over the boundary of an
429  *      island it belongs to.
430  *
431  *      TODO:
432  *
433  *  Add restriction flag/callback for wire edges.
434  * 
435 */
436
437 static void islandboundWalker_begin(BMWalker *walker, void *data){
438         BMLoop *l = data;
439         islandboundWalker *iwalk = NULL;
440
441         BMW_pushstate(walker);
442
443         iwalk = walker->currentstate;
444
445         iwalk->base = iwalk->curloop = l;
446         iwalk->lastv = l->v;
447
448         BLI_ghash_insert(walker->visithash, data, NULL);
449
450 }
451
452 static void *islandboundWalker_yield(BMWalker *walker)
453 {
454         islandboundWalker *iwalk = walker->currentstate;
455
456         return iwalk->curloop;
457 }
458
459 static void *islandboundWalker_step(BMWalker *walker)
460 {
461         islandboundWalker *iwalk = walker->currentstate, owalk;
462         BMVert *v;
463         BMEdge *e = iwalk->curloop->e;
464         BMFace *f;
465         BMLoop *l = iwalk->curloop;
466         int found=0;
467
468         owalk = *iwalk;
469
470         if (iwalk->lastv == e->v1) v = e->v2;
471         else v = e->v1;
472
473         if (BM_Nonmanifold_Vert(walker->bm, v)) {
474                 BMW_reset(walker);
475                 BMO_RaiseError(walker->bm, NULL,BMERR_WALKER_FAILED,
476                         "Non-manifold vert"
477                         " while searching region boundary");
478                 return NULL;
479         }
480         
481         /*pop off current state*/
482         BMW_popstate(walker);
483         
484         f = l->f;
485         
486         while (1) {
487                 l = BM_OtherFaceLoop(e, f, v);
488                 if (bmesh_radial_nextloop(l) != l) {
489                         l = bmesh_radial_nextloop(l);
490                         f = l->f;
491                         e = l->e;
492                         if(!BMO_TestFlag(walker->bm, f, walker->restrictflag)){
493                                 l = l->radial.next->data;
494                                 break;
495                         }
496                 } else {
497                         f = l->f;
498                         e = l->e;
499                         break;
500                 }
501         }
502         
503         if (l == owalk.curloop) return NULL;
504         if (BLI_ghash_haskey(walker->visithash, l)) return owalk.curloop;
505
506         BLI_ghash_insert(walker->visithash, l, NULL);
507         BMW_pushstate(walker);
508         iwalk = walker->currentstate;
509         iwalk->base = owalk.base;
510
511         //if (!BMO_TestFlag(walker->bm, l->f, walker->restrictflag))
512         //      iwalk->curloop = l->radial.next->data;
513         iwalk->curloop = l; //else iwalk->curloop = l;
514         iwalk->lastv = v;                               
515
516         return owalk.curloop;
517 }
518
519
520 /*      Island Walker:
521  *
522  *      Starts at a tool flagged-face and walks over the face region
523  *
524  *      TODO:
525  *
526  *  Add restriction flag/callback for wire edges.
527  * 
528 */
529
530 static void islandWalker_begin(BMWalker *walker, void *data){
531         islandWalker *iwalk = NULL;
532
533         BMW_pushstate(walker);
534
535         iwalk = walker->currentstate;
536         BLI_ghash_insert(walker->visithash, data, NULL);
537
538         iwalk->cur = data;
539 }
540
541 static void *islandWalker_yield(BMWalker *walker)
542 {
543         islandWalker *iwalk = walker->currentstate;
544
545         return iwalk->cur;
546 }
547
548 static void *islandWalker_step(BMWalker *walker)
549 {
550         islandWalker *iwalk = walker->currentstate, *owalk;
551         BMIter iter, liter;
552         BMFace *f, *curf = iwalk->cur;
553         BMLoop *l;
554         owalk = iwalk;
555         
556         BMW_popstate(walker);
557
558         l = BMIter_New(&liter, walker->bm, BM_LOOPS_OF_FACE, iwalk->cur);
559         for (; l; l=BMIter_Step(&liter)) {
560                 f = BMIter_New(&iter, walker->bm, BM_FACES_OF_EDGE, l->e);
561                 for (; f; f=BMIter_Step(&iter)) {
562                         if (!BMO_TestFlag(walker->bm, f, walker->restrictflag))
563                                 continue;
564                         if (BLI_ghash_haskey(walker->visithash, f)) continue;
565                         
566                         BMW_pushstate(walker);
567                         iwalk = walker->currentstate;
568                         iwalk->cur = f;
569                         BLI_ghash_insert(walker->visithash, f, NULL);
570                         break;
571
572                 }
573         }
574         
575         return curf;
576 }
577
578
579 /*      Island Walker:
580  *
581  *      Starts at a tool flagged-face and walks over the face region
582  *
583  *      TODO:
584  *
585  *  Add restriction flag/callback for wire edges.
586  * 
587 */
588
589 static void loopWalker_begin(BMWalker *walker, void *data){
590         loopWalker *lwalk = NULL, owalk;
591         BMEdge *e = data;
592         BMVert *v;
593         int found=1, val;
594
595         v = e->v1;
596
597         val = BM_Vert_EdgeCount(v);
598
599         BMW_pushstate(walker);
600         
601         lwalk = walker->currentstate;
602         BLI_ghash_insert(walker->visithash, e, NULL);
603         
604         lwalk->cur = lwalk->start = e;
605         lwalk->lastv = lwalk->startv = v;
606         lwalk->stage2 = 0;
607         lwalk->startrad = BM_Edge_FaceCount(e);
608
609         /*rewind*/
610         while (walker->currentstate) {
611                 owalk = *((loopWalker*)walker->currentstate);
612                 BMW_walk(walker);
613         }
614
615         BMW_pushstate(walker);
616         lwalk = walker->currentstate;
617         *lwalk = owalk;
618
619         if (lwalk->lastv == owalk.cur->v1) lwalk->lastv = owalk.cur->v2;
620         else lwalk->lastv = owalk.cur->v1;
621
622         lwalk->startv = lwalk->lastv;
623
624         BLI_ghash_free(walker->visithash, NULL, NULL);
625         walker->visithash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
626         BLI_ghash_insert(walker->visithash, owalk.cur, NULL);
627 }
628
629 static void *loopWalker_yield(BMWalker *walker)
630 {
631         loopWalker *lwalk = walker->currentstate;
632
633         return lwalk->cur;
634 }
635
636 static void *loopWalker_step(BMWalker *walker)
637 {
638         loopWalker *lwalk = walker->currentstate, owalk;
639         BMEdge *e = lwalk->cur, *nexte = NULL;
640         BMLoop *l, *l2;
641         BMVert *v;
642         int val, rlen, found=0, i=0, stopi;
643
644         owalk = *lwalk;
645         
646         if (e->v1 == lwalk->lastv) v = e->v2;
647         else v = e->v1;
648
649         val = BM_Vert_EdgeCount(v);
650         
651         BMW_popstate(walker);
652         
653         rlen = owalk.startrad;
654         l = e->loop;
655         if (!l)
656                 return owalk.cur;
657
658         if (val == 4 || val == 2 || rlen == 1) {                
659                 i = 0;
660                 stopi = val / 2;
661                 while (1) {
662                         if (rlen != 1 && i == stopi) break;
663
664                         l = BM_OtherFaceLoop(l->e, l->f, v);
665
666                         if (!l)
667                                 break;
668
669                         l2 = bmesh_radial_nextloop(l);
670                         
671                         if (l2 == l) {
672                                 break;
673                         }
674
675                         l = l2;
676                         i += 1;
677                 }
678         }
679         
680         if (!l)
681                 return owalk.cur;
682
683         if (l != e->loop && !BLI_ghash_haskey(walker->visithash, l->e)) {
684                 if (!(rlen != 1 && i != stopi)) {
685                         BMW_pushstate(walker);
686                         lwalk = walker->currentstate;
687                         *lwalk = owalk;
688                         lwalk->cur = l->e;
689                         lwalk->lastv = v;
690                         BLI_ghash_insert(walker->visithash, l->e, NULL);
691                 }
692         }
693         
694         return owalk.cur;
695 }
696
697 static void faceloopWalker_begin(BMWalker *walker, void *data)
698 {
699         faceloopWalker *lwalk, owalk;
700         BMEdge *e = data;
701
702         BMW_pushstate(walker);
703
704         if (!e->loop) return;
705
706         lwalk = walker->currentstate;
707         lwalk->l = e->loop;
708         lwalk->nocalc = 0;
709         BLI_ghash_insert(walker->visithash, lwalk->l->f, NULL);
710
711         /*rewind*/
712         while (walker->currentstate) {
713                 owalk = *((faceloopWalker*)walker->currentstate);
714                 BMW_walk(walker);
715         }
716
717         BMW_pushstate(walker);
718         lwalk = walker->currentstate;
719         *lwalk = owalk;
720         lwalk->nocalc = 0;
721
722         BLI_ghash_free(walker->visithash, NULL, NULL);
723         walker->visithash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
724         BLI_ghash_insert(walker->visithash, lwalk->l->f, NULL);
725 }
726
727 static void *faceloopWalker_yield(BMWalker *walker)
728 {
729         faceloopWalker *lwalk = walker->currentstate;
730         
731         if (!lwalk) return NULL;
732
733         return lwalk->l->f;
734 }
735
736 static void *faceloopWalker_step(BMWalker *walker)
737 {
738         faceloopWalker *lwalk = walker->currentstate;
739         BMFace *f = lwalk->l->f;
740         BMLoop *l = lwalk->l, *origl = lwalk->l;
741
742         BMW_popstate(walker);
743
744         l = l->radial.next->data;
745         
746         if (lwalk->nocalc)
747                 return f;
748
749         if (BLI_ghash_haskey(walker->visithash, l->f)) {
750                 l = lwalk->l;
751                 l = l->head.next->next;
752                 if (l == l->radial.next->data) {
753                         l = l->head.prev->prev;
754                 }
755                 l = l->radial.next->data;
756         }
757
758         if (!BLI_ghash_haskey(walker->visithash, l->f)) {
759                 BMW_pushstate(walker);
760                 lwalk = walker->currentstate;
761                 lwalk->l = l;
762
763                 if (l->f->len != 4) {
764                         lwalk->nocalc = 1;
765                         lwalk->l = origl;
766                 } else
767                         lwalk->nocalc = 0;
768
769                 BLI_ghash_insert(walker->visithash, l->f, NULL);
770         }
771
772         return f;
773 }
774
775 static void edgeringWalker_begin(BMWalker *walker, void *data)
776 {
777         edgeringWalker *lwalk, owalk;
778         BMEdge *e = data;
779
780         BMW_pushstate(walker);
781
782         if (!e->loop) return;
783
784         lwalk = walker->currentstate;
785         lwalk->l = e->loop;
786         BLI_ghash_insert(walker->visithash, lwalk->l->e, NULL);
787
788         /*rewind*/
789         while (walker->currentstate) {
790                 owalk = *((edgeringWalker*)walker->currentstate);
791                 BMW_walk(walker);
792         }
793
794         BMW_pushstate(walker);
795         lwalk = walker->currentstate;
796         *lwalk = owalk;
797
798         if (lwalk->l->f->len != 4)
799                 lwalk->l = lwalk->l->radial.next->data;
800
801         BLI_ghash_free(walker->visithash, NULL, NULL);
802         walker->visithash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
803         BLI_ghash_insert(walker->visithash, lwalk->l->e, NULL);
804 }
805
806 static void *edgeringWalker_yield(BMWalker *walker)
807 {
808         edgeringWalker *lwalk = walker->currentstate;
809         
810         if (!lwalk) return NULL;
811
812         return lwalk->l->e;
813 }
814
815 static void *edgeringWalker_step(BMWalker *walker)
816 {
817         edgeringWalker *lwalk = walker->currentstate;
818         BMEdge *e = lwalk->l->e;
819         BMLoop *l = lwalk->l, *origl = lwalk->l;
820
821         BMW_popstate(walker);
822
823         l = l->radial.next->data;
824         l = l->head.next->next;
825         
826         if (l->f->len != 4) {
827                 l = lwalk->l->head.next->next;
828         }
829
830         if (l->f->len == 4 && !BLI_ghash_haskey(walker->visithash, l->e)) {
831                 BMW_pushstate(walker);
832                 lwalk = walker->currentstate;
833                 lwalk->l = l;
834
835                 BLI_ghash_insert(walker->visithash, l->e, NULL);
836         }
837
838         return e;
839 }
840
841 static void uvedgeWalker_begin(BMWalker *walker, void *data)
842 {
843         uvedgeWalker *lwalk;
844         BMLoop *l = data;
845
846         if (BLI_ghash_haskey(walker->visithash, l))
847                 return;
848
849         BMW_pushstate(walker);
850         lwalk = walker->currentstate;
851         lwalk->l = l;
852         BLI_ghash_insert(walker->visithash, l, NULL);
853 }
854
855 static void *uvedgeWalker_yield(BMWalker *walker)
856 {
857         uvedgeWalker *lwalk = walker->currentstate;
858         
859         if (!lwalk) return NULL;
860 }
861
862 static void *uvedgeWalker_step(BMWalker *walker)
863 {
864         uvedgeWalker *lwalk = walker->currentstate;
865         BMLoop *l, *l2, *l3, *nl, *cl;
866         BMIter liter;
867         void *d1, *d2;
868         int i, j, rlen, type;
869
870         l = lwalk->l;
871         nl = l->head.next;
872         type = walker->bm->ldata.layers[walker->flag].type;
873
874         BMW_popstate(walker);
875         
876         if (walker->restrictflag && !BMO_TestFlag(walker->bm, l->e, walker->restrictflag))
877                 return l;
878
879         /*go over loops around l->v and nl->v and see which ones share l and nl's 
880           mloopuv's coordinates. in addition, push on l->head.next if necassary.*/
881         for (i=0; i<2; i++) {
882                 cl = i ? nl : l;
883                 BM_ITER(l2, &liter, walker->bm, BM_LOOPS_OF_VERT, cl->v) {
884                         d1 = CustomData_bmesh_get_layer_n(&walker->bm->ldata, 
885                                      cl->head.data, walker->flag);
886                         
887                         rlen = BM_Edge_FaceCount(l2->e);
888                         for (j=0; j<rlen; j++) {
889                                 if (BLI_ghash_haskey(walker->visithash, l2))
890                                         continue;
891                                 if (walker->restrictflag && !(BMO_TestFlag(walker->bm, l2->e, walker->restrictflag)))
892                                 {
893                                         if (l2->v != cl->v)
894                                                 continue;
895                                 }
896                                 
897                                 l3 = l2->v != cl->v ? (BMLoop*)l2->head.next : l2;
898                                 d2 = CustomData_bmesh_get_layer_n(&walker->bm->ldata, 
899                                              l3->head.data, walker->flag);
900
901                                 if (!CustomData_data_equals(type, d1, d2))
902                                         continue;
903                                 
904                                 BMW_pushstate(walker);
905                                 BLI_ghash_insert(walker->visithash, l2, NULL);
906                                 lwalk = walker->currentstate;
907
908                                 lwalk->l = l2;
909
910                                 l2 = l2->radial.next->data;
911                         }
912                 }
913         }
914
915         return l;
916 }
917