bd7664673e9954484c4de35e0d867eef92816755
[blender.git] / source / blender / bmesh / intern / bmesh_newcore.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, Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/intern/bmesh_newcore.c
24  *  \ingroup bmesh
25  *
26  * TODO
27  */
28
29 #include <limits.h>
30
31 #include "BLI_math_vector.h"
32
33 #include "BKE_customdata.h"
34 #include "BKE_DerivedMesh.h"
35
36 #include "BLI_utildefines.h"
37 #include "BLI_blenlib.h"
38 #include "BLI_listbase.h"
39 #include "BLI_mempool.h"
40 #include "BLI_ghash.h"
41 #include "BLI_array.h"
42
43 #include "MEM_guardedalloc.h"
44
45 #include "DNA_listBase.h"
46
47 #include "bmesh_class.h"
48
49 #include "bmesh_iterators.h"
50 #include "bmesh_private.h"
51
52 /* use so valgrinds memcheck alerts us when undefined index is used.
53  * TESTING ONLY! */
54 // #define USE_DEBUG_INDEX_MEMCHECK
55
56 #ifdef USE_DEBUG_INDEX_MEMCHECK
57 #define DEBUG_MEMCHECK_INDEX_INVALIDATE(ele)               \
58         {                                                      \
59                 int undef_idx;                                     \
60                 BM_SetIndex(ele, undef_idx); /* set_ok_invalid */  \
61         }                                                      \
62
63 #endif
64
65 BMVert *BM_Make_Vert(BMesh *bm, const float co[3], const struct BMVert *example)
66 {
67         BMVert *v = BLI_mempool_calloc(bm->vpool);
68
69 #ifdef USE_DEBUG_INDEX_MEMCHECK
70         DEBUG_MEMCHECK_INDEX_INVALIDATE(v)
71 #else
72         BM_SetIndex(v, -1); /* set_ok_invalid */
73 #endif
74
75         bm->elem_index_dirty |= BM_VERT; /* may add to middle of the pool */
76
77         bm->totvert++;
78
79         v->head.htype = BM_VERT;
80
81         /* 'v->no' is handled by BM_Copy_Attributes */
82         if (co) copy_v3_v3(v->co, co);
83         
84         /*allocate flags*/
85         v->head.flags = BLI_mempool_calloc(bm->toolflagpool);
86
87         CustomData_bmesh_set_default(&bm->vdata, &v->head.data);
88         
89         if (example) {
90                 BM_Copy_Attributes(bm, bm, (BMVert*)example, (BMVert*)v);
91         }
92
93         BM_CHECK_ELEMENT(bm, v);
94
95         return (BMVert*) v;
96 }
97
98 /**
99  *                      BMESH EDGE EXIST
100  *
101  *  Finds out if two vertices already have an edge
102  *  connecting them. Note that multiple edges may
103  *  exist between any two vertices, and therefore
104  *  This function only returns the first one found.
105  *
106  *  Returns -
107  *      BMEdge pointer
108  */
109 BMEdge *BM_Edge_Exist(BMVert *v1, BMVert *v2)
110 {
111         BMIter iter;
112         BMEdge *e;
113
114         BM_ITER(e, &iter, NULL, BM_EDGES_OF_VERT, v1) {
115                 if (e->v1 == v2 || e->v2 == v2)
116                         return e;
117         }
118
119         return NULL;
120 }
121
122 BMEdge *BM_Make_Edge(BMesh *bm, BMVert *v1, BMVert *v2, const BMEdge *example, int nodouble)
123 {
124         BMEdge *e;
125         
126         if (nodouble && (e= BM_Edge_Exist(v1, v2)))
127                 return (BMEdge*)e;
128         
129         e = BLI_mempool_calloc(bm->epool);
130
131 #ifdef USE_DEBUG_INDEX_MEMCHECK
132         DEBUG_MEMCHECK_INDEX_INVALIDATE(e)
133 #else
134         BM_SetIndex(e, -1); /* set_ok_invalid */
135 #endif
136
137         bm->elem_index_dirty |= BM_EDGE; /* may add to middle of the pool */
138
139         bm->totedge++;
140
141         e->head.htype = BM_EDGE;
142         
143         /*allocate flags*/
144         e->head.flags = BLI_mempool_calloc(bm->toolflagpool);
145
146         e->v1 = (BMVert*) v1;
147         e->v2 = (BMVert*) v2;
148         
149         
150         CustomData_bmesh_set_default(&bm->edata, &e->head.data);
151         
152         bmesh_disk_append_edge(e, e->v1);
153         bmesh_disk_append_edge(e, e->v2);
154         
155         if (example)
156                 BM_Copy_Attributes(bm, bm, (BMEdge*)example, (BMEdge*)e);
157         
158         BM_CHECK_ELEMENT(bm, e);
159
160         return (BMEdge*) e;
161 }
162
163 static BMLoop *bmesh_create_loop(BMesh *bm, BMVert *v, BMEdge *e, BMFace *f, const BMLoop *example)
164 {
165         BMLoop *l=NULL;
166
167         l = BLI_mempool_calloc(bm->lpool);
168         l->next = l->prev = NULL;
169         l->v = v;
170         l->e = e;
171         l->f = f;
172         l->radial_next = l->radial_prev = NULL;
173         l->head.data = NULL;
174         l->head.htype = BM_LOOP;
175
176         bm->totloop++;
177
178         if(example)
179                 CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, example->head.data, &l->head.data);
180         else
181                 CustomData_bmesh_set_default(&bm->ldata, &l->head.data);
182
183         return l;
184 }
185
186 static BMLoop *BM_Add_FaceBoundary(BMesh *bm, BMFace *f, BMVert *startv, BMEdge *starte)
187 {
188         BMLoopList *lst = BLI_mempool_calloc(bm->looplistpool);
189         BMLoop *l = bmesh_create_loop(bm, startv, starte, f, NULL);
190         
191         bmesh_radial_append(starte, l);
192
193         lst->first = lst->last = l;
194         BLI_addtail(&f->loops, lst);
195         
196         l->f = f;
197         
198         return l;       
199 }
200
201 BMFace *BM_Copy_Face(BMesh *bm, BMFace *f, int copyedges, int copyverts)
202 {
203         BMEdge **edges = NULL;
204         BMVert **verts = NULL;
205         BLI_array_staticdeclare(edges, 256);
206         BLI_array_staticdeclare(verts, 256);
207         BMLoop *l, *l2;
208         BMFace *f2;
209         int i;
210
211         l = bm_firstfaceloop(f);
212         do {
213                 if (copyverts) {
214                         BMVert *v = BM_Make_Vert(bm, l->v->co, l->v);
215                         BLI_array_append(verts, v);
216                 } else {        
217                         BLI_array_append(verts, l->v);
218                 }
219                 l = l->next;
220         } while (l != bm_firstfaceloop(f));
221
222         l = bm_firstfaceloop(f);
223         i = 0;
224         do {
225                 if (copyedges) {
226                         BMEdge *e;
227                         BMVert *v1, *v2;
228                         
229                         if (l->e->v1 == verts[i]) {
230                                 v1 = verts[i];
231                                 v2 = verts[(i+1)%f->len];
232                         } else {
233                                 v2 = verts[i];
234                                 v1 = verts[(i+1)%f->len];
235                         }
236                         
237                         e = BM_Make_Edge(bm,  v1, v2, l->e, 0);
238                         BLI_array_append(edges, e);
239                 } else {
240                         BLI_array_append(edges, l->e);
241                 }
242                 
243                 i++;
244                 l = l->next;
245         } while (l != bm_firstfaceloop(f));
246         
247         f2 = BM_Make_Face(bm, verts, edges, f->len, 0);
248         
249         BM_Copy_Attributes(bm, bm, f, f2);
250         
251         l = bm_firstfaceloop(f);
252         l2 = bm_firstfaceloop(f2);
253         do {
254                 BM_Copy_Attributes(bm, bm, l, l2);
255                 l = l->next;
256                 l2 = l2->next;
257         } while (l != bm_firstfaceloop(f));
258         
259         return f2;
260 }
261
262 BMFace *BM_Make_Face(BMesh *bm, BMVert **verts, BMEdge **edges, const int len, int nodouble)
263 {
264         BMFace *f = NULL;
265         BMLoop *l, *startl, *lastl;
266         int i, overlap;
267         
268         if (len == 0) {
269                 /*just return NULL for now*/
270                 return NULL;
271         }
272
273         if (nodouble) {
274                 /* Check if face already exists */
275                 overlap = BM_Face_Exists(bm, verts, len, &f);
276                 if (overlap) {
277                         return f;
278                 }
279                 else {
280                         BLI_assert(f == NULL);
281                 }
282         }
283         
284         f = BLI_mempool_calloc(bm->fpool);
285
286 #ifdef USE_DEBUG_INDEX_MEMCHECK
287         DEBUG_MEMCHECK_INDEX_INVALIDATE(f)
288 #else
289         BM_SetIndex(f, -1); /* set_ok_invalid */
290 #endif
291
292         bm->elem_index_dirty |= BM_FACE; /* may add to middle of the pool */
293
294         bm->totface++;
295
296         f->head.htype = BM_FACE;
297
298         startl = lastl = BM_Add_FaceBoundary(bm, (BMFace*)f, verts[0], edges[0]);
299         
300         startl->v = (BMVert*) verts[0];
301         startl->e = (BMEdge*) edges[0];
302         for (i=1; i<len; i++) {
303                 l = bmesh_create_loop(bm, verts[i], edges[i], (BMFace *)f, edges[i]->l);
304                 
305                 l->f = (BMFace*) f;
306                 bmesh_radial_append(edges[i], l);
307
308                 l->prev = lastl;
309                 lastl->next = l;
310                 lastl = l;
311         }
312         
313         /*allocate flags*/
314         f->head.flags = BLI_mempool_calloc(bm->toolflagpool);
315
316         CustomData_bmesh_set_default(&bm->pdata, &f->head.data);
317         
318         startl->prev = lastl;
319         lastl->next = startl;
320         
321         f->len = len;
322         f->totbounds = 0;
323         
324         BM_CHECK_ELEMENT(bm, f);
325
326         return (BMFace*) f;
327 }
328
329 int bmesh_check_element(BMesh *UNUSED(bm), void *element, const char htype)
330 {
331         BMHeader *head = element;
332         int err = 0;
333
334         if (!element)
335                 return 1;
336
337         if (head->htype != htype)
338                 return 2;
339         
340         switch (htype) {
341         case BM_VERT: {
342                 BMVert *v = element;
343                 if (v->e && v->e->head.htype != BM_EDGE) {
344                         err |= 4;
345                 }
346                 break;
347         }
348         case BM_EDGE: {
349                 BMEdge *e = element;
350                 if (e->l && e->l->head.htype != BM_LOOP)
351                         err |= 8;
352                 if (e->l && e->l->f->head.htype != BM_FACE)
353                         err |= 16;
354                 if (e->dlink1.prev == NULL || e->dlink2.prev == NULL || e->dlink1.next == NULL || e->dlink2.next == NULL)
355                         err |= 32;
356                 if (e->l && (e->l->radial_next == NULL || e->l->radial_prev == NULL))
357                         err |= 64;
358                 if (e->l && e->l->f->len <= 0)
359                         err |= 128;
360                 break;
361         }
362         case BM_LOOP: {
363                 BMLoop *l = element, *l2;
364                 int i;
365
366                 if (l->f->head.htype != BM_FACE)
367                         err |= 256;
368                 if (l->e->head.htype != BM_EDGE)
369                         err |= 512;
370                 if (l->v->head.htype !=  BM_VERT)
371                         err |= 1024;
372                 if (!BM_Vert_In_Edge(l->e, l->v)) {
373                         fprintf(stderr, "%s: fatal bmesh error (vert not in edge)! (bmesh internal error)\n", __func__);
374                         err |= 2048;
375                 }
376
377                 if (l->radial_next == NULL || l->radial_prev == NULL)
378                         err |= (1<<12);
379                 if (l->f->len <= 0)
380                         err |= (1<<13);
381
382                 /*validate boundary loop--invalid for hole loops, of course,
383                   but we won't be allowing those for a while yet*/
384                 l2 = l;
385                 i = 0;
386                 do {
387                         if (i >= 9999999)
388                                 break;
389
390                         i++;
391                         l2 = l2->next;
392                 } while (l2 != l);
393
394                 if (i != l->f->len || l2 != l)
395                         err |= (1<<14);
396
397                 if (!bmesh_radial_validate(bmesh_radial_length(l), l))
398                         err |= (1<<15);
399
400                 break;
401         }
402         case BM_FACE: {
403                 BMFace *f = element;
404                 BMLoop *l;
405                 int len=0;
406
407                 if (!f->loops.first)
408                         err |= (1<<16);
409                 l = bm_firstfaceloop(f);
410                 do {
411                         if (l->f != f) {
412                                 fprintf(stderr, "%s: loop inside one face points to another! (bmesh internal error)\n", __func__);
413                                 err |= (1<<17);
414                         }
415
416                         if (!l->e)
417                                 err |= (1<<18);
418                         if (!l->v)
419                                 err |= (1<<19);
420                         if (!BM_Vert_In_Edge(l->e, l->v) || !BM_Vert_In_Edge(l->e, l->next->v)) {
421                                 err |= (1<<20);
422                         }
423
424                         if (!bmesh_radial_validate(bmesh_radial_length(l), l))
425                                 err |= (1<<21);
426
427                         if (!bmesh_disk_count(l->v) || !bmesh_disk_count(l->next->v))
428                                 err |= (1<<22);
429
430                         len++;
431                         l = l->next;
432                 } while (l != bm_firstfaceloop(f));
433
434                 if (len != f->len)
435                         err |= (1<<23);
436         }
437         }
438
439         if (err) {
440                 bmesh_error();
441         }
442
443         return err;
444 }
445
446 static void bmesh_kill_loop(BMesh *bm, BMLoop *l)
447 {
448         bm->totloop--;
449         if (l->head.data)
450                 CustomData_bmesh_free_block(&bm->ldata, &l->head.data);
451
452         if (l->head.flags)
453                 BLI_mempool_free(bm->toolflagpool, l->head.flags);
454         BLI_mempool_free(bm->lpool, l);
455 }
456
457 void BM_Kill_Face_Edges(BMesh *bm, BMFace *f)
458 {
459         BMEdge **edges = NULL;
460         BLI_array_staticdeclare(edges, 256);
461         BMLoop *l;
462         int i;
463         
464         l = bm_firstfaceloop(f);
465         do {
466                 BLI_array_append(edges, l->e);
467                 l = l->next;
468         } while (l != bm_firstfaceloop(f));
469         
470         for (i=0; i<BLI_array_count(edges); i++) {
471                 BM_Kill_Edge(bm, edges[i]);
472         }
473         
474         BLI_array_free(edges);
475 }
476
477 void BM_Kill_Face_Verts(BMesh *bm, BMFace *f)
478 {
479         BMVert**verts = NULL;
480         BLI_array_staticdeclare(verts, 256);
481         BMLoop *l;
482         int i;
483         
484         l = bm_firstfaceloop(f);
485         do {
486                 BLI_array_append(verts, l->v);
487                 l = l->next;
488         } while (l != bm_firstfaceloop(f));
489         
490         for (i=0; i<BLI_array_count(verts); i++) {
491                 BM_Kill_Vert(bm, verts[i]);
492         }
493         
494         BLI_array_free(verts);
495 }
496
497 void BM_Kill_Face(BMesh *bm, BMFace *f)
498 {
499         BMLoopList *ls, *lsnext;
500
501         BM_CHECK_ELEMENT(bm, f);
502
503         for (ls=f->loops.first; ls; ls=lsnext) {
504                 BMLoop *l, *lnext;
505
506                 lsnext = ls->next;
507                 l = ls->first;
508                 do {
509                         lnext = l->next;
510
511                         bmesh_radial_remove_loop(l, l->e);
512                         bmesh_kill_loop(bm, l);
513
514                         l = lnext;
515                 } while (l != ls->first);
516                 
517                 BLI_mempool_free(bm->looplistpool, ls);
518         }
519         
520         if (bm->act_face == f)
521                 bm->act_face = NULL;
522         
523         bm->totface--;
524         bm->elem_index_dirty |= BM_FACE;
525         BM_remove_selection(bm, f);
526         if (f->head.data)
527                 CustomData_bmesh_free_block(&bm->pdata, &f->head.data);
528
529         BLI_mempool_free(bm->toolflagpool, f->head.flags);
530
531         BLI_mempool_free(bm->fpool, f);
532 }
533
534 void BM_Kill_Edge(BMesh *bm, BMEdge *e)
535 {
536
537         bmesh_disk_remove_edge(e, e->v1);
538         bmesh_disk_remove_edge(e, e->v2);
539                 
540         if (e->l) {
541                 BMLoop *l = e->l, *lnext, *startl=e->l;
542                         
543                 do {
544                         lnext = l->radial_next;
545                         if (lnext->f == l->f) {
546                                 BM_Kill_Face(bm, l->f);
547                                 break;                                  
548                         }
549                         
550                         BM_Kill_Face(bm, l->f);
551                 
552                         if (l == lnext)
553                                 break;
554                         l = lnext;
555                 } while (l != startl);
556         }
557         
558         bm->totedge--;
559         bm->elem_index_dirty |= BM_EDGE;
560         BM_remove_selection(bm, e);
561         if (e->head.data)
562                 CustomData_bmesh_free_block(&bm->edata, &e->head.data);
563
564         BLI_mempool_free(bm->toolflagpool, e->head.flags);
565         BLI_mempool_free(bm->epool, e);
566 }
567
568 void BM_Kill_Vert(BMesh *bm, BMVert *v)
569 {
570         if (v->e) {
571                 BMEdge *e, *nexte;
572                 
573                 e = v->e;
574                 while (v->e) {
575                         nexte=bmesh_disk_nextedge(e, v);
576                         BM_Kill_Edge(bm, e);
577                         e = nexte;
578                 }
579         }
580
581         bm->totvert--;
582         bm->elem_index_dirty |= BM_VERT;
583         BM_remove_selection(bm, v);
584         if (v->head.data)
585                 CustomData_bmesh_free_block(&bm->vdata, &v->head.data);
586
587         BLI_mempool_free(bm->toolflagpool, v->head.flags);
588         BLI_mempool_free(bm->vpool, v);
589 }
590
591 /********** private disk and radial cycle functions ************/
592
593 /**
594  *                      bmesh_loop_reverse
595  *
596  *      FLIP FACE EULER
597  *
598  *      Changes the winding order of a face from CW to CCW or vice versa.
599  *      This euler is a bit peculiar in compairson to others as it is its
600  *      own inverse.
601  *
602  *      BMESH_TODO: reinsert validation code.
603  *
604  *  Returns -
605  *      1 for success, 0 for failure.
606  */
607
608 static int bmesh_loop_length(BMLoop *l)
609 {
610         BMLoop *ol = l;
611         int i = 0;
612
613         do {
614                 l = l->next;
615                 i++;
616         } while (l != ol);
617
618         return i;
619 }
620
621 static int bmesh_loop_reverse_loop(BMesh *bm, BMFace *f, BMLoopList *lst)
622 {
623         BMLoop *l = lst->first, *curloop, *oldprev, *oldnext;
624         BMEdge **edar = NULL;
625         MDisps *md;
626         BLI_array_staticdeclare(edar, 64);
627         int i, j, edok, len = 0, do_disps = CustomData_has_layer(&bm->ldata, CD_MDISPS);
628
629         len = bmesh_loop_length(l);
630
631         for(i=0, curloop = l; i< len; i++, curloop= curloop->next) {
632                 BMEdge *curedge = curloop->e;
633                 bmesh_radial_remove_loop(curloop, curedge);
634                 BLI_array_append(edar, curedge);
635         }
636
637         /*actually reverse the loop.*/
638         for(i=0, curloop = l; i < len; i++){
639                 oldnext = curloop->next;
640                 oldprev = curloop->prev;
641                 curloop->next = oldprev;
642                 curloop->prev = oldnext;
643                 curloop = oldnext;
644                 
645                 if (do_disps) {
646                         float (*co)[3];
647                         int x, y, sides;
648                         
649                         md = CustomData_bmesh_get(&bm->ldata, curloop->head.data, CD_MDISPS);
650                         if (!md->totdisp || !md->disps)
651                                 continue;
652                                         
653                         sides= (int)sqrt(md->totdisp);
654                         co = md->disps;
655                         
656                         for (x=0; x<sides; x++) {
657                                 for (y=0; y<x; y++) {
658                                         swap_v3_v3(co[y*sides+x], co[sides*x + y]);
659                                 }
660                         }
661                 }
662         }
663
664         if(len == 2){ //two edged face
665                 //do some verification here!
666                 l->e = edar[1];
667                 l->next->e = edar[0];
668         }
669         else{
670                 for(i=0, curloop = l; i < len; i++, curloop = curloop->next) {
671                         edok = 0;
672                         for(j=0; j < len; j++){
673                                 edok = bmesh_verts_in_edge(curloop->v, curloop->next->v, edar[j]);
674                                 if(edok){
675                                         curloop->e = edar[j];
676                                         break;
677                                 }
678                         }
679                 }
680         }
681         /*rebuild radial*/
682         for(i=0, curloop = l; i < len; i++, curloop = curloop->next)
683                 bmesh_radial_append(curloop->e, curloop);
684
685         /*validate radial*/
686         for(i=0, curloop = l; i < len; i++, curloop = curloop->next) {
687                 BM_CHECK_ELEMENT(bm, curloop);
688                 BM_CHECK_ELEMENT(bm, curloop->e);
689                 BM_CHECK_ELEMENT(bm, curloop->v);
690                 BM_CHECK_ELEMENT(bm, curloop->f);
691         }
692
693         BLI_array_free(edar);
694
695         BM_CHECK_ELEMENT(bm, f);
696
697         return 1;
698 }
699
700 int bmesh_loop_reverse(BMesh *bm, BMFace *f)
701 {
702         return bmesh_loop_reverse_loop(bm, f, f->loops.first);
703 }
704
705 static void bmesh_systag_elements(BMesh *UNUSED(bm), void *veles, int tot, int flag)
706 {
707         BMHeader **eles = veles;
708         int i;
709
710         for (i=0; i<tot; i++) {
711                 bmesh_api_setflag(eles[i], flag);
712         }
713 }
714
715 static void bmesh_clear_systag_elements(BMesh *UNUSED(bm), void *veles, int tot, int flag)
716 {
717         BMHeader **eles = veles;
718         int i;
719
720         for (i=0; i<tot; i++) {
721                 bmesh_api_clearflag(eles[i], flag);
722         }
723 }
724
725 #define FACE_MARK       (1<<10)
726
727 static int count_flagged_radial(BMesh *bm, BMLoop *l, int flag)
728 {
729         BMLoop *l2 = l;
730         int i = 0, c=0;
731
732         do {
733                 if (!l2) {
734                         bmesh_error();
735                         goto error;
736                 }
737                 
738                 i += bmesh_api_getflag(l2->f, flag) ? 1 : 0;
739                 l2 = bmesh_radial_nextloop(l2);
740                 if (c >= 800000) {
741                         bmesh_error();
742                         goto error;
743                 }
744                 c++;
745         } while (l2 != l);
746
747         return i;
748
749 error:
750         BMO_RaiseError(bm, bm->currentop, BMERR_MESH_ERROR, NULL);
751         return 0;
752 }
753
754 static int UNUSED_FUNCTION(count_flagged_disk)(BMVert *v, int flag)
755 {
756         BMEdge *e = v->e;
757         int i=0;
758
759         if (!e)
760                 return 0;
761
762         do {
763                 i += bmesh_api_getflag(e, flag) ? 1 : 0;
764                 e = bmesh_disk_nextedge(e, v);
765         } while (e != v->e);
766
767         return i;
768 }
769
770 static int disk_is_flagged(BMVert *v, int flag)
771 {
772         BMEdge *e = v->e;
773
774         if (!e)
775                 return 0;
776
777         do {
778                 BMLoop *l = e->l;
779
780                 if (!l) {
781                         return 0;
782                 }
783                 
784                 if (bmesh_radial_length(l) == 1)
785                         return 0;
786                 
787                 do {
788                         if (!bmesh_api_getflag(l->f, flag))
789                                 return 0;
790
791                         l = l->radial_next;
792                 } while (l != e->l);
793
794                 e = bmesh_disk_nextedge(e, v);
795         } while (e != v->e);
796
797         return 1;
798 }
799
800 /* Midlevel Topology Manipulation Functions */
801
802 /*
803  * BM_Join_Faces
804  *
805  * Joins a collected group of faces into one. Only restriction on
806  * the input data is that the faces must be connected to each other.
807  *
808  * If a pair of faces share multiple edges, the pair of
809  * faces will be joined at every edge.
810  *
811  * Returns a pointer to the combined face.
812  */
813 BMFace *BM_Join_Faces(BMesh *bm, BMFace **faces, int totface)
814 {
815         BMFace *f, *newf;
816         BMLoopList *lst;
817         BMLoop *l;
818         BMEdge **edges = NULL;
819         BMEdge **deledges = NULL;
820         BMVert **delverts = NULL;
821         BLI_array_staticdeclare(edges, 64);
822         BLI_array_staticdeclare(deledges, 64);
823         BLI_array_staticdeclare(delverts, 64);
824         BMVert *v1=NULL, *v2=NULL;
825         ListBase holes = {NULL, NULL};
826         const char *err = NULL;
827         int i, tote=0;
828
829         if (!totface) {
830                 bmesh_error();
831                 return NULL;
832         }
833
834         if (totface == 1)
835                 return faces[0];
836
837         bmesh_systag_elements(bm, faces, totface, _FLAG_JF);
838
839         for (i=0; i<totface; i++) {
840                 f = faces[i];
841                 l = bm_firstfaceloop(f);
842                 do {
843                         int rlen = count_flagged_radial(bm, l, _FLAG_JF);
844
845                         if (rlen > 2) {
846                                 err = "Input faces do not form a contiguous manifold region";
847                                 goto error;
848                         } else if (rlen == 1) {
849                                 BLI_array_append(edges, l->e);
850
851                                 if (!v1) {
852                                         v1 = l->v;
853                                         v2 = BM_OtherEdgeVert(l->e, l->v);
854                                 }
855                                 tote++;
856                         } else if (rlen == 2) {
857                                 int d1, d2;
858
859                                 d1 = disk_is_flagged(l->e->v1, _FLAG_JF);
860                                 d2 = disk_is_flagged(l->e->v2, _FLAG_JF);
861
862                                 if (!d1 && !d2 && !bmesh_api_getflag(l->e, _FLAG_JF)) {
863                                         BLI_array_append(deledges, l->e);
864                                         bmesh_api_setflag(l->e, _FLAG_JF);
865                                 } else {
866                                         if (d1 && !bmesh_api_getflag(l->e->v1, _FLAG_JF)) {
867                                                 BLI_array_append(delverts, l->e->v1);
868                                                 bmesh_api_setflag(l->e->v1, _FLAG_JF);
869                                         }
870
871                                         if (d2 && !bmesh_api_getflag(l->e->v2, _FLAG_JF)) {
872                                                 BLI_array_append(delverts, l->e->v2);
873                                                 bmesh_api_setflag(l->e->v2, _FLAG_JF);
874                                         }
875                                 }
876                         }
877
878                         l = l->next;
879                 } while (l != bm_firstfaceloop(f));
880
881                 for (lst=f->loops.first; lst; lst=lst->next) {
882                         if (lst == f->loops.first) continue;
883                         
884                         BLI_remlink(&f->loops, lst);
885                         BLI_addtail(&holes, lst);
886                 }
887         }
888
889         /*create region face*/
890         newf = BM_Make_Ngon(bm, v1, v2, edges, tote, 0);
891         if (!newf || BMO_HasError(bm)) {
892                 if (!BMO_HasError(bm)) 
893                         err = "Invalid boundary region to join faces";
894                 goto error;
895         }
896
897         /*copy over loop data*/
898         l = bm_firstfaceloop(newf);
899         do {
900                 BMLoop *l2 = l->radial_next;
901
902                 do {
903                         if (bmesh_api_getflag(l2->f, _FLAG_JF))
904                                 break;
905                         l2 = l2->radial_next;
906                 } while (l2 != l);
907
908                 if (l2 != l) {
909                         /*I think this is correct?*/
910                         if (l2->v != l->v) {
911                                 l2 = l2->next;
912                         }
913
914                         BM_Copy_Attributes(bm, bm, l2, l);
915                 }
916
917                 l = l->next;
918         } while (l != bm_firstfaceloop(newf));
919         
920         BM_Copy_Attributes(bm, bm, faces[0], newf);
921
922         /*add holes*/
923         BLI_movelisttolist(&newf->loops, &holes);
924
925         /*update loop face pointers*/
926         for (lst=newf->loops.first; lst; lst=lst->next) {
927                 l = lst->first;
928                 do {
929                         l->f = newf;
930                         l = l->next;
931                 } while (l != lst->first);
932         }
933
934         bmesh_clear_systag_elements(bm, faces, totface, _FLAG_JF);
935         bmesh_api_clearflag(newf, _FLAG_JF);
936
937         /* handle multires data*/
938         if (CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
939                 l = bm_firstfaceloop(newf);
940                 do {
941                         for (i=0; i<totface; i++) {
942                                 BM_loop_interp_multires(bm, l, faces[i]);
943                         }
944                         
945                         l = l->next;
946                 } while (l != bm_firstfaceloop(newf));
947         }       
948
949         /*delete old geometry*/
950         for (i=0; i<BLI_array_count(deledges); i++) {
951                 BM_Kill_Edge(bm, deledges[i]);
952         }
953
954         for (i=0; i<BLI_array_count(delverts); i++) {
955                 BM_Kill_Vert(bm, delverts[i]);
956         }
957         
958         BLI_array_free(edges);
959         BLI_array_free(deledges);
960         BLI_array_free(delverts);
961
962         BM_CHECK_ELEMENT(bm, newf);
963         return newf;
964 error:
965         bmesh_clear_systag_elements(bm, faces, totface, _FLAG_JF);
966         BLI_array_free(edges);
967         BLI_array_free(deledges);
968         BLI_array_free(delverts);
969
970         if (err) {
971                 BMO_RaiseError(bm, bm->currentop, BMERR_DISSOLVEFACES_FAILED, err);
972         }
973         return NULL;
974 }
975
976 static BMFace *bmesh_addpolylist(BMesh *bm, BMFace *UNUSED(example))
977 {
978         BMFace *f;
979         BMLoopList *lst;
980
981         f = BLI_mempool_calloc(bm->fpool);
982         lst = BLI_mempool_calloc(bm->looplistpool);
983
984         f->head.htype = BM_FACE;
985         BLI_addtail(&f->loops, lst);
986
987 #ifdef USE_DEBUG_INDEX_MEMCHECK
988         DEBUG_MEMCHECK_INDEX_INVALIDATE(f)
989 #else
990         BM_SetIndex(f, -1); /* set_ok_invalid */
991 #endif
992
993         bm->elem_index_dirty |= BM_FACE; /* may add to middle of the pool */
994
995         bm->totface++;
996
997         /*allocate flags*/
998         f->head.flags = BLI_mempool_calloc(bm->toolflagpool);
999
1000         CustomData_bmesh_set_default(&bm->pdata, &f->head.data);
1001
1002         f->len = 0;
1003         f->totbounds = 1;
1004
1005         return (BMFace*) f;
1006 }
1007
1008 /**
1009  *                      bmesh_SFME
1010  *
1011  *      SPLIT FACE MAKE EDGE:
1012  *
1013  *      Takes as input two vertices in a single face. An edge is created which divides the original face
1014  *      into two distinct regions. One of the regions is assigned to the original face and it is closed off.
1015  *      The second region has a new face assigned to it.
1016  *
1017  *      Examples:
1018  *
1019  *     Before:               After:
1020  *       ----------           ----------
1021  *       |        |           |        |
1022  *       |        |           |   f1   |
1023  *      v1   f1   v2          v1======v2
1024  *       |        |           |   f2   |
1025  *       |        |           |        |
1026  *       ----------           ----------
1027  *
1028  *      Note that the input vertices can be part of the same edge. This will
1029  *  result in a two edged face. This is desirable for advanced construction
1030  *  tools and particularly essential for edge bevel. Because of this it is
1031  *  up to the caller to decide what to do with the extra edge.
1032  *
1033  *  If holes is NULL, then both faces will lose
1034  *  all holes from the original face.  Also, you cannot split between
1035  *  a hole vert and a boundary vert; that case is handled by higher-
1036  *  level wrapping functions (when holes are fully implemented, anyway).
1037  *
1038  *  Note that holes represents which holes goes to the new face, and of
1039  *  course this requires removing them from the exitsing face first, since
1040  *  you cannot have linked list links inside multiple lists.
1041  *
1042  *      Returns -
1043  *  A BMFace pointer
1044  */
1045 BMFace *bmesh_sfme(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2,
1046                                    BMLoop **rl, ListBase *holes)
1047 {
1048
1049         BMFace *f2;
1050         BMLoop *v1loop = NULL, *v2loop = NULL, *curloop, *f1loop=NULL, *f2loop=NULL;
1051         BMEdge *e;
1052         BMLoopList *lst, *lst2;
1053         int i, len, f1len, f2len;
1054
1055         /*verify that v1 and v2 are in face.*/
1056         len = f->len;
1057         for(i = 0, curloop = bm_firstfaceloop(f); i < len; i++, curloop = curloop->next) {
1058                 if(curloop->v == v1) v1loop = curloop;
1059                 else if(curloop->v == v2) v2loop = curloop;
1060         }
1061
1062         if(!v1loop || !v2loop) return NULL;
1063
1064         /*allocate new edge between v1 and v2*/
1065         e = BM_Make_Edge(bm, v1, v2, NULL, 0);
1066
1067         f2 = bmesh_addpolylist(bm,f);
1068         f1loop = bmesh_create_loop(bm,v2,e,f,v2loop);
1069         f2loop = bmesh_create_loop(bm,v1,e,f2,v1loop);
1070
1071         f1loop->prev = v2loop->prev;
1072         f2loop->prev = v1loop->prev;
1073         v2loop->prev->next = f1loop;
1074         v1loop->prev->next = f2loop;
1075
1076         f1loop->next = v1loop;
1077         f2loop->next = v2loop;
1078         v1loop->prev = f1loop;
1079         v2loop->prev = f2loop;
1080
1081         lst = f->loops.first;
1082         lst2 = f2->loops.first;
1083
1084         lst2->first = lst2->last = f2loop;
1085         lst->first = lst->last = f1loop;
1086
1087         /*validate both loops*/
1088         /*I dont know how many loops are supposed to be in each face at this point! FIXME!*/
1089
1090         /*go through all of f2's loops and make sure they point to it properly.*/
1091         curloop = lst2->first;
1092         f2len = 0;
1093         do {
1094                 curloop->f = f2;
1095
1096                 curloop = curloop->next;
1097                 f2len++;
1098         } while (curloop != lst2->first);
1099
1100         /*link up the new loops into the new edges radial*/
1101         bmesh_radial_append(e, f1loop);
1102         bmesh_radial_append(e, f2loop);
1103
1104         f2->len = f2len;
1105
1106         f1len = 0;
1107         curloop = lst->first;
1108         do {
1109                 f1len++;
1110                 curloop = curloop->next;
1111         } while (curloop != lst->first);
1112
1113         f->len = f1len;
1114
1115         if(rl) *rl = f2loop;
1116
1117         if (holes) {
1118                 BLI_movelisttolist(&f2->loops, holes);
1119         } else {
1120                 /*this code is not significant until holes actually work ;) */
1121                 //printf("warning: call to split face euler without holes argument; holes will be tossed.\n");
1122                 for (lst=f->loops.last; lst != f->loops.first; lst=lst2) {
1123                         lst2 = lst->prev;
1124                         BLI_mempool_free(bm->looplistpool, lst);
1125                 }
1126         }
1127
1128         BM_CHECK_ELEMENT(bm, e);
1129         BM_CHECK_ELEMENT(bm, f);
1130         BM_CHECK_ELEMENT(bm, f2);
1131         
1132         return f2;
1133 }
1134
1135 /**
1136  *                      bmesh_SEMV
1137  *
1138  *      SPLIT EDGE MAKE VERT:
1139  *      Takes a given edge and splits it into two, creating a new vert.
1140  *
1141  *
1142  *              Before: OV---------TV
1143  *              After:  OV----NV---TV
1144  *
1145  *  Returns -
1146  *      BMVert pointer.
1147  *
1148 */
1149
1150 BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **re){
1151         BMLoop *nextl;
1152         BMEdge *ne;
1153         BMVert *nv, *ov;
1154         int i, edok, valence1=0, valence2=0;
1155
1156         if(bmesh_vert_in_edge(e,tv) == 0) return NULL;
1157         ov = bmesh_edge_getothervert(e,tv);
1158
1159         /*count valence of v1*/
1160         valence1 = bmesh_disk_count(ov);
1161
1162         /*count valence of v2*/
1163         valence2 = bmesh_disk_count(tv);
1164
1165         nv = BM_Make_Vert(bm, tv->co, tv);
1166         ne = BM_Make_Edge(bm, nv, tv, e, 0);
1167
1168         bmesh_disk_remove_edge(ne, tv);
1169         bmesh_disk_remove_edge(ne, nv);
1170
1171         /*remove e from v2's disk cycle*/
1172         bmesh_disk_remove_edge(e, tv);
1173
1174         /*swap out tv for nv in e*/
1175         bmesh_edge_swapverts(e, tv, nv);
1176
1177         /*add e to nv's disk cycle*/
1178         bmesh_disk_append_edge(e, nv);
1179
1180         /*add ne to nv's disk cycle*/
1181         bmesh_disk_append_edge(ne, nv);
1182
1183         /*add ne to tv's disk cycle*/
1184         bmesh_disk_append_edge(ne, tv);
1185
1186         /*verify disk cycles*/
1187         edok = bmesh_disk_validate(valence1, ov->e, ov);
1188         if(!edok) bmesh_error();
1189         edok = bmesh_disk_validate(valence2, tv->e, tv);
1190         if(!edok) bmesh_error();
1191         edok = bmesh_disk_validate(2, nv->e, nv);
1192         if(!edok) bmesh_error();
1193
1194         /*Split the radial cycle if present*/
1195         nextl = e->l;
1196         e->l = NULL;
1197         if(nextl) {
1198                 BMLoop *nl, *l;
1199                 int radlen = bmesh_radial_length(nextl);
1200                 int first1=0, first2=0;
1201
1202                 /*Take the next loop. Remove it from radial. Split it. Append to appropriate radials.*/
1203                 while(nextl) {
1204                         l=nextl;
1205                         l->f->len++;
1206                         nextl = nextl!=nextl->radial_next ? nextl->radial_next : NULL;
1207                         bmesh_radial_remove_loop(l, NULL);
1208
1209                         nl = bmesh_create_loop(bm,NULL,NULL,l->f,l);
1210                         nl->prev = l;
1211                         nl->next = (l->next);
1212                         nl->prev->next = nl;
1213                         nl->next->prev = nl;
1214                         nl->v = nv;
1215
1216                         /*assign the correct edge to the correct loop*/
1217                         if(bmesh_verts_in_edge(nl->v, nl->next->v, e)) {
1218                                 nl->e = e;
1219                                 l->e = ne;
1220
1221                                 /*append l into ne's rad cycle*/
1222                                 if(!first1) {
1223                                         first1 = 1;
1224                                         l->radial_next = l->radial_prev = NULL;
1225                                 }
1226
1227                                 if(!first2) {
1228                                         first2 = 1;
1229                                         l->radial_next = l->radial_prev = NULL;
1230                                 }
1231                                 
1232                                 bmesh_radial_append(nl->e, nl);
1233                                 bmesh_radial_append(l->e, l);
1234                         }
1235                         else if(bmesh_verts_in_edge(nl->v, nl->next->v, ne)){
1236                                 nl->e = ne;
1237                                 l->e = e;
1238
1239                                 /*append l into ne's rad cycle*/
1240                                 if(!first1) {
1241                                         first1 = 1;
1242                                         l->radial_next = l->radial_prev = NULL;
1243                                 }
1244
1245                                 if(!first2) {
1246                                         first2 = 1;
1247                                         l->radial_next = l->radial_prev = NULL;
1248                                 }
1249
1250                                 bmesh_radial_append(nl->e, nl);
1251                                 bmesh_radial_append(l->e, l);
1252                         }
1253
1254                 }
1255
1256                 /*verify length of radial cycle*/
1257                 edok = bmesh_radial_validate(radlen, e->l);
1258                 if(!edok) bmesh_error();
1259                 edok = bmesh_radial_validate(radlen, ne->l);
1260                 if(!edok) bmesh_error();
1261
1262                 /*verify loop->v and loop->next->v pointers for e*/
1263                 for(i=0,l=e->l; i < radlen; i++, l = l->radial_next){
1264                         if(!(l->e == e)) bmesh_error();
1265                         //if(!(l->radial_next == l)) bmesh_error();
1266                         if(l->prev->e != ne && l->next->e != ne) bmesh_error();
1267                         edok = bmesh_verts_in_edge(l->v, l->next->v, e);
1268                         if(!edok) bmesh_error();
1269                         if(l->v == l->next->v) bmesh_error();
1270                         if(l->e == l->next->e) bmesh_error();
1271
1272                         /*verify loop cycle for kloop->f*/
1273                         BM_CHECK_ELEMENT(bm, l);
1274                         BM_CHECK_ELEMENT(bm, l->v);
1275                         BM_CHECK_ELEMENT(bm, l->e);
1276                         BM_CHECK_ELEMENT(bm, l->f);
1277                 }
1278                 /*verify loop->v and loop->next->v pointers for ne*/
1279                 for(i=0,l=ne->l; i < radlen; i++, l = l->radial_next){
1280                         if(!(l->e == ne)) bmesh_error();
1281                         //if(!(l->radial_next == l)) bmesh_error();
1282                         if( l->prev->e != e && l->next->e != e) bmesh_error();
1283                         edok = bmesh_verts_in_edge(l->v, l->next->v, ne);
1284                         if(!edok) bmesh_error();
1285                         if(l->v == l->next->v) bmesh_error();
1286                         if(l->e == l->next->e) bmesh_error();
1287
1288                         BM_CHECK_ELEMENT(bm, l);
1289                         BM_CHECK_ELEMENT(bm, l->v);
1290                         BM_CHECK_ELEMENT(bm, l->e);
1291                         BM_CHECK_ELEMENT(bm, l->f);
1292                 }
1293         }
1294
1295         BM_CHECK_ELEMENT(bm, ne);
1296         BM_CHECK_ELEMENT(bm, nv);
1297         BM_CHECK_ELEMENT(bm, ov);
1298         BM_CHECK_ELEMENT(bm, e);
1299         BM_CHECK_ELEMENT(bm, tv);
1300
1301         if(re) *re = ne;
1302         return nv;
1303 }
1304
1305 /**
1306  *                      bmesh_JEKV
1307  *
1308  *      JOIN EDGE KILL VERT:
1309  *      Takes a an edge and pointer to one of its vertices and collapses
1310  *      the edge on that vertex.
1311  *      
1312  *      Before:    OE      KE
1313  *               ------- -------
1314  *               |     ||      |
1315  *              OV     KV      TV
1316  *
1317  *
1318  *   After:             OE      
1319  *               ---------------
1320  *               |             |
1321  *              OV             TV
1322  *
1323  *
1324  *      Restrictions:
1325  *      KV is a vertex that must have a valance of exactly two. Furthermore
1326  *  both edges in KV's disk cycle (OE and KE) must be unique (no double
1327  *  edges).
1328  *
1329  *      It should also be noted that this euler has the possibility of creating
1330  *      faces with just 2 edges. It is up to the caller to decide what to do with
1331  *  these faces.
1332  *
1333  *  Returns -
1334  *      1 for success, 0 for failure.
1335  */
1336 int bmesh_jekv(BMesh *bm, BMEdge *ke, BMVert *kv)
1337 {
1338         BMEdge *oe;
1339         BMVert *ov, *tv;
1340         BMLoop *killoop, *l;
1341         int len,radlen=0, halt = 0, i, valence1, valence2,edok;
1342         BMLoop **loops = NULL;
1343         BLI_array_staticdeclare(loops, 256);
1344
1345         if(bmesh_vert_in_edge(ke,kv) == 0) return 0;
1346         len = bmesh_disk_count(kv);
1347         
1348         if(len == 2){
1349                 oe = bmesh_disk_nextedge(ke, kv);
1350                 tv = bmesh_edge_getothervert(ke, kv);
1351                 ov = bmesh_edge_getothervert(oe, kv);           
1352                 halt = bmesh_verts_in_edge(kv, tv, oe); /*check for double edges*/
1353                 
1354                 if(halt) return 0;
1355                 else{
1356                         /*For verification later, count valence of ov and tv*/
1357                         valence1 = bmesh_disk_count(ov);
1358                         valence2 = bmesh_disk_count(tv);
1359                         
1360                         /*remove oe from kv's disk cycle*/
1361                         bmesh_disk_remove_edge(oe,kv);
1362                         /*relink oe->kv to be oe->tv*/
1363                         bmesh_edge_swapverts(oe, kv, tv);
1364                         /*append oe to tv's disk cycle*/
1365                         bmesh_disk_append_edge(oe, tv);
1366                         /*remove ke from tv's disk cycle*/
1367                         bmesh_disk_remove_edge(ke, tv);
1368                 
1369                         /*deal with radial cycle of ke*/
1370                         radlen = bmesh_radial_length(ke->l);
1371                         if(ke->l){
1372                                 /*first step, fix the neighboring loops of all loops in ke's radial cycle*/
1373                                 for(i=0,killoop = ke->l; i<radlen; i++, killoop = bmesh_radial_nextloop(killoop)){
1374                                         /*relink loops and fix vertex pointer*/
1375                                         if( killoop->next->v == kv ) killoop->next->v = tv;
1376
1377                                         killoop->next->prev = killoop->prev;
1378                                         killoop->prev->next = killoop->next;
1379                                         if (bm_firstfaceloop(killoop->f) == killoop)
1380                                                 bm_firstfaceloop(killoop->f) = killoop->next;
1381                                         killoop->next = NULL;
1382                                         killoop->prev = NULL;
1383
1384                                         /*fix len attribute of face*/
1385                                         killoop->f->len--;
1386                                 }
1387                                 /*second step, remove all the hanging loops attached to ke*/
1388                                 killoop = ke->l;
1389                                 radlen = bmesh_radial_length(ke->l);
1390                                 /*this should be wrapped into a bme_free_radial function to be used by bmesh_KF as well...*/
1391                                 for (i=0;i<radlen;i++) {
1392                                         BLI_array_growone(loops);
1393                                         loops[BLI_array_count(loops)-1] = killoop;
1394                                         killoop = bmesh_radial_nextloop(killoop);
1395                                 }
1396                                 for (i=0;i<radlen;i++) {
1397                                         bm->totloop--;
1398                                         BLI_mempool_free(bm->lpool, loops[i]);
1399                                 }
1400                                 /*Validate radial cycle of oe*/
1401                                 edok = bmesh_radial_validate(radlen,oe->l);
1402                                 if(!edok) bmesh_error();
1403                         }
1404
1405                         /*deallocate edge*/
1406                         BM_remove_selection(bm, ke);
1407                         BLI_mempool_free(bm->toolflagpool, ke->head.flags);
1408                         BLI_mempool_free(bm->epool, ke);
1409                         bm->totedge--;
1410                         /*deallocate vertex*/
1411                         BM_remove_selection(bm, kv);
1412                         BLI_mempool_free(bm->toolflagpool, kv->head.flags);
1413                         BLI_mempool_free(bm->vpool, kv);
1414                         bm->totvert--;
1415                         /* account for both above */
1416                         bm->elem_index_dirty |= BM_VERT | BM_EDGE;
1417
1418                         /*Validate disk cycle lengths of ov,tv are unchanged*/
1419                         edok = bmesh_disk_validate(valence1, ov->e, ov);
1420                         if(!edok) bmesh_error();
1421                         edok = bmesh_disk_validate(valence2, tv->e, tv);
1422                         if(!edok) bmesh_error();
1423
1424                         /*Validate loop cycle of all faces attached to oe*/
1425                         for(i=0,l = oe->l; i<radlen; i++, l = bmesh_radial_nextloop(l)){
1426                                 if(l->e != oe) bmesh_error();
1427                                 edok = bmesh_verts_in_edge(l->v, l->next->v, oe);
1428                                 if(!edok) bmesh_error();
1429                                 edok = bmesh_loop_validate(l->f);
1430                                 if(!edok) bmesh_error();
1431
1432                                 BM_CHECK_ELEMENT(bm, l);
1433                                 BM_CHECK_ELEMENT(bm, l->v);
1434                                 BM_CHECK_ELEMENT(bm, l->e);
1435                                 BM_CHECK_ELEMENT(bm, l->f);
1436                         }
1437
1438                         BM_CHECK_ELEMENT(bm, ov);
1439                         BM_CHECK_ELEMENT(bm, tv);
1440                         BM_CHECK_ELEMENT(bm, oe);
1441
1442                         return 1;
1443                 }
1444         }
1445         return 0;
1446 }
1447
1448 /**
1449  *                      bmesh_JFKE
1450  *
1451  *      JOIN FACE KILL EDGE:
1452  *      
1453  *      Takes two faces joined by a single 2-manifold edge and fuses them togather.
1454  *      The edge shared by the faces must not be connected to any other edges which have
1455  *      Both faces in its radial cycle
1456  *
1457  *      Examples:
1458  *      
1459  *        A                   B
1460  *       ----------           ----------
1461  *       |        |           |        | 
1462  *       |   f1   |           |   f1   |
1463  *      v1========v2 = Ok!    v1==V2==v3 == Wrong!
1464  *       |   f2   |           |   f2   |
1465  *       |        |           |        |
1466  *       ----------           ---------- 
1467  *
1468  *      In the example A, faces f1 and f2 are joined by a single edge, and the euler can safely be used.
1469  *      In example B however, f1 and f2 are joined by multiple edges and will produce an error. The caller
1470  *      in this case should call bmesh_JEKV on the extra edges before attempting to fuse f1 and f2.
1471  *
1472  *      Also note that the order of arguments decides whether or not certain per-face attributes are present
1473  *      in the resultant face. For instance vertex winding, material index, smooth flags, ect are inherited
1474  *      from f1, not f2.
1475  *
1476  *  Returns -
1477  *      A BMFace pointer
1478 */
1479 BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e)
1480 {
1481         BMLoop *curloop, *f1loop=NULL, *f2loop=NULL;
1482         int newlen = 0,i, f1len=0, f2len=0, radlen=0, edok, shared;
1483         BMIter iter;
1484
1485         /*can't join a face to itself*/
1486         if(f1 == f2) return NULL;
1487         /*verify that e is in both f1 and f2*/
1488         f1len = f1->len;
1489         f2len = f2->len;
1490         BM_ITER(curloop, &iter, bm, BM_LOOPS_OF_FACE, f1) {
1491                 if(curloop->e == e){ 
1492                         f1loop = curloop;
1493                         break;
1494                 }
1495         }
1496         BM_ITER(curloop, &iter, bm, BM_LOOPS_OF_FACE, f2) {
1497                 if(curloop->e == e){
1498                         f2loop = curloop;
1499                         break;
1500                 }
1501         }
1502         if (!(f1loop && f2loop)) return NULL;
1503         
1504         /*validate that edge is 2-manifold edge*/
1505         radlen = bmesh_radial_length(f1loop);
1506         if(radlen != 2) return NULL;
1507
1508         /*validate direction of f2's loop cycle is compatible.*/
1509         if(f1loop->v == f2loop->v) return NULL;
1510
1511         /*
1512                 validate that for each face, each vertex has another edge in its disk cycle that is 
1513                 not e, and not shared.
1514         */
1515         if(bmesh_radial_find_face(f1loop->next->e,f2)) return NULL;
1516         if(bmesh_radial_find_face(f1loop->prev->e,f2)) return NULL;
1517         if(bmesh_radial_find_face(f2loop->next->e,f1)) return NULL;
1518         if(bmesh_radial_find_face(f2loop->prev->e,f1)) return NULL;
1519         
1520         /*validate only one shared edge*/
1521         shared = BM_Face_Share_Edges(f1,f2);
1522         if(shared > 1) return NULL;
1523
1524         /*validate no internal joins*/
1525         for(i=0, curloop = bm_firstfaceloop(f1); i < f1len; i++, curloop = curloop->next)
1526                 bmesh_api_setindex(curloop->v, 0);
1527         for(i=0, curloop = bm_firstfaceloop(f2); i < f2len; i++, curloop = curloop->next)
1528                 bmesh_api_setindex(curloop->v, 0);
1529
1530         for(i=0, curloop = bm_firstfaceloop(f1); i < f1len; i++, curloop = curloop->next) {
1531                 if (curloop != f1loop)
1532                         bmesh_api_setindex(curloop->v, bmesh_api_getindex(curloop->v) + 1);
1533         }
1534         for(i=0, curloop = bm_firstfaceloop(f2); i < f2len; i++, curloop = curloop->next) {
1535                 if (curloop != f2loop)
1536                         bmesh_api_setindex(curloop->v, bmesh_api_getindex(curloop->v) + 1);
1537         }
1538
1539         for(i=0, curloop = bm_firstfaceloop(f1); i < f1len; i++, curloop = curloop->next) {
1540                 if (bmesh_api_getindex(curloop->v) > 1)
1541                         return NULL;
1542         }
1543         
1544         for(i=0, curloop = bm_firstfaceloop(f2); i < f2len; i++, curloop = curloop->next) {
1545                 if (bmesh_api_getindex(curloop->v) > 1)
1546                         return NULL;
1547         }
1548
1549         /*join the two loops*/
1550         f1loop->prev->next = f2loop->next;
1551         f2loop->next->prev = f1loop->prev;
1552         
1553         f1loop->next->prev = f2loop->prev;
1554         f2loop->prev->next = f1loop->next;
1555         
1556         /*if f1loop was baseloop, make f1loop->next the base.*/
1557         if(bm_firstfaceloop(f1) == f1loop)
1558                 bm_firstfaceloop(f1) = f1loop->next;
1559
1560         /*increase length of f1*/
1561         f1->len += (f2->len - 2);
1562
1563         /*make sure each loop points to the proper face*/
1564         newlen = f1->len;
1565         for(i = 0, curloop = bm_firstfaceloop(f1); i < newlen; i++, curloop = curloop->next)
1566                 curloop->f = f1;
1567         
1568         /*remove edge from the disk cycle of its two vertices.*/
1569         bmesh_disk_remove_edge(f1loop->e, f1loop->e->v1);
1570         bmesh_disk_remove_edge(f1loop->e, f1loop->e->v2);
1571         
1572         /*deallocate edge and its two loops as well as f2*/
1573         BLI_mempool_free(bm->toolflagpool, f1loop->e->head.flags);
1574         BLI_mempool_free(bm->epool, f1loop->e);
1575         bm->totedge--;
1576         BLI_mempool_free(bm->lpool, f1loop);
1577         bm->totloop--;
1578         BLI_mempool_free(bm->lpool, f2loop);
1579         bm->totloop--;
1580         BLI_mempool_free(bm->toolflagpool, f2->head.flags);
1581         BLI_mempool_free(bm->fpool, f2);
1582         bm->totface--;
1583         /* account for both above */
1584         bm->elem_index_dirty |= BM_EDGE | BM_FACE;
1585
1586         BM_CHECK_ELEMENT(bm, f1);
1587
1588         /*validate the new loop cycle*/
1589         edok = bmesh_loop_validate(f1);
1590         if(!edok) bmesh_error();
1591         
1592         return f1;
1593 }
1594
1595 /*
1596  * BMESH SPLICE VERT
1597  *
1598  * merges two verts into one (v into vtarget).
1599  */
1600 static int bmesh_splicevert(BMesh *bm, BMVert *v, BMVert *vtarget)
1601 {
1602         BMEdge *e;
1603         BMLoop *l;
1604         BMIter liter;
1605
1606         /* verts already spliced */
1607         if (v == vtarget) {
1608                 return 0;
1609         }
1610
1611         /* retarget all the loops of v to vtarget */
1612         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
1613                 l->v = vtarget;
1614         }
1615
1616         /* move all the edges from v's disk to vtarget's disk */
1617         e = v->e;
1618         while (e != NULL) {
1619                 bmesh_disk_remove_edge(e, v);
1620                 bmesh_edge_swapverts(e, v, vtarget);
1621                 bmesh_disk_append_edge(e, vtarget);
1622                 e = v->e;
1623         }
1624
1625         BM_CHECK_ELEMENT(bm, v);
1626         BM_CHECK_ELEMENT(bm, vtarget);
1627
1628         /* v is unused now, and can be killed */
1629         BM_Kill_Vert(bm, v);
1630
1631         return 1;
1632 }
1633
1634 /* BMESH CUT VERT
1635  *
1636  * cut all disjoint fans that meet at a vertex, making a unique
1637  * vertex for each region. returns an array of all resulting
1638  * vertices.
1639  */
1640 static int bmesh_cutvert(BMesh *bm, BMVert *v, BMVert ***vout, int *len)
1641 {
1642         BMEdge **stack = NULL;
1643         BLI_array_declare(stack);
1644         BMVert **verts = NULL;
1645         GHash *visithash;
1646         BMIter eiter, liter;
1647         BMLoop *l;
1648         BMEdge *e;
1649         int i, maxindex;
1650         BMLoop *nl;
1651
1652         visithash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "bmesh_cutvert visithash");
1653
1654         maxindex = 0;
1655         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
1656                 if (BLI_ghash_haskey(visithash, e)) {
1657                         continue;
1658                 }
1659
1660                 /* Prime the stack with this unvisited edge */
1661                 BLI_array_append(stack, e);
1662
1663                 /* Considering only edges and faces incident on vertex v, walk
1664                    the edges & faces and assign an index to each connected set */
1665                 while ((e = BLI_array_pop(stack))) {
1666                         BLI_ghash_insert(visithash, e, SET_INT_IN_POINTER(maxindex));
1667
1668                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
1669                                 nl = (l->v == v) ? l->prev : l->next;
1670                                 if (!BLI_ghash_haskey(visithash, nl->e)) {
1671                                         BLI_array_append(stack, nl->e);
1672                                 }
1673                         }
1674                 }
1675
1676                 maxindex++;
1677         }
1678
1679         /* Make enough verts to split v for each group */
1680         verts = MEM_callocN(sizeof(BMVert *) * maxindex, "bmesh_cutvert");
1681         verts[0] = v;
1682         for (i = 1; i < maxindex; i++) {
1683                 verts[i] = BM_Make_Vert(bm, v->co, v);
1684         }
1685
1686         /* Replace v with the new verts in each group */
1687         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
1688                 i = GET_INT_FROM_POINTER(BLI_ghash_lookup(visithash, l->e));
1689                 if (i == 0) {
1690                         continue;
1691                 }
1692
1693                 /* Loops here should alway refer to an edge that has v as an
1694                    endpoint. For each appearance of this vert in a face, there
1695                    will actually be two iterations: one for the loop heading
1696                    towards vertex v, and another for the loop heading out from
1697                    vertex v. Only need to swap the vertex on one of those times,
1698                    on the outgoing loop. */
1699                 if (l->v == v) {
1700                         l->v = verts[i];
1701                 }
1702         }
1703
1704         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
1705                 i = GET_INT_FROM_POINTER(BLI_ghash_lookup(visithash, e));
1706                 if (i == 0) {
1707                         continue;
1708                 }
1709
1710                 BLI_assert(e->v1 == v || e->v2 == v);
1711                 bmesh_disk_remove_edge(e, v);
1712                 bmesh_edge_swapverts(e, v, verts[i]);
1713                 bmesh_disk_append_edge(e, verts[i]);
1714         }
1715
1716         BLI_ghash_free(visithash, NULL, NULL);
1717         BLI_array_free(stack);
1718
1719         for (i = 0; i < maxindex; i++) {
1720                 BM_CHECK_ELEMENT(bm, verts[i]);
1721         }
1722
1723         if (len != NULL) {
1724                 *len = maxindex;
1725         }
1726
1727         if (vout != NULL) {
1728                 *vout = verts;
1729         }
1730         else {
1731                 MEM_freeN(verts);
1732         }
1733
1734         return 1;
1735 }
1736
1737 /* BMESH SPLICE EDGE
1738  *
1739  * splice two unique edges which share the same two vertices into one edge.
1740  *
1741  * edges must already have the same vertices
1742  */
1743 static int UNUSED_FUNCTION(bmesh_spliceedge)(BMesh *bm, BMEdge *e, BMEdge *etarget)
1744 {
1745         BMLoop *l;
1746
1747         if (!BM_Vert_In_Edge(e, etarget->v1) || !BM_Vert_In_Edge(e, etarget->v2)) {
1748                 /* not the same vertices can't splice */
1749                 return 0;
1750         }
1751
1752         while (e->l) {
1753                 l = e->l;
1754                 BLI_assert(BM_Vert_In_Edge(etarget, l->v));
1755                 BLI_assert(BM_Vert_In_Edge(etarget, l->next->v));
1756                 bmesh_radial_remove_loop(l, e);
1757                 bmesh_radial_append(etarget, l);
1758         }
1759
1760         BLI_assert(bmesh_radial_length(e->l) == 0);
1761
1762         BM_CHECK_ELEMENT(bm, e);
1763         BM_CHECK_ELEMENT(bm, etarget);
1764
1765         BM_Kill_Edge(bm, e);
1766
1767         return 1;
1768 }
1769
1770 /*
1771  * BMESH CUT EDGE
1772  *
1773  * Cuts a single edge into two edge: the original edge and
1774  * a new edge that has only "cutl" in its radial.
1775  *
1776  * Does nothing if cutl is already the only loop in the
1777  * edge radial.
1778  */
1779 static int bmesh_cutedge(BMesh *bm, BMEdge *e, BMLoop *cutl)
1780 {
1781         BMEdge *ne;
1782         int radlen;
1783
1784         BLI_assert(cutl->e == e);
1785         BLI_assert(e->l);
1786         
1787         radlen = bmesh_radial_length(e->l);
1788         if (radlen < 2) {
1789                 /* no cut required */
1790                 return 1;
1791         }
1792
1793         if (cutl == e->l) {
1794                 e->l = cutl->radial_next;
1795         }
1796
1797         ne = BM_Make_Edge(bm, e->v1, e->v2, e, 0);
1798         bmesh_radial_remove_loop(cutl, e);
1799         bmesh_radial_append(ne, cutl);
1800         cutl->e = ne;
1801
1802         BLI_assert(bmesh_radial_length(e->l) == radlen - 1);
1803         BLI_assert(bmesh_radial_length(ne->l) == 1);
1804
1805         BM_CHECK_ELEMENT(bm, ne);
1806         BM_CHECK_ELEMENT(bm, e);
1807
1808         return 1;
1809 }
1810
1811 /*
1812  * BMESH UNGLUE REGION MAKE VERT
1813  *
1814  * Disconnects a face from its vertex fan at loop sl.
1815  */
1816 static BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *sl)
1817 {
1818         BMVert **vtar;
1819         int len, i;
1820         BMVert *nv = NULL;
1821         BMVert *sv = sl->v;
1822
1823         /* peel the face from the edge radials on both sides of the
1824            loop vert, disconnecting the face from its fan */
1825         bmesh_cutedge(bm, sl->e, sl);
1826         bmesh_cutedge(bm, sl->prev->e, sl->prev);
1827
1828         if (bmesh_disk_count(sv) == 2) {
1829                 /* If there are still only two edges out of sv, then
1830                    this whole URMV was just a no-op, so exit now. */
1831                 return sv;
1832         }
1833
1834         /* Update the disk start, so that v->e points to an edge
1835            not touching the split loop. This is so that bmesh_cutvert
1836            will leave the original sv on some *other* fan (not the
1837            one-face fan that holds the unglue face). */
1838         while (sv->e == sl->e || sv->e == sl->prev->e) {
1839                 sv->e = bmesh_disk_nextedge(sv->e, sv);
1840         }
1841
1842         /* Split all fans connected to the vert, duplicating it for
1843            each fans. */
1844         bmesh_cutvert(bm, sv, &vtar, &len);
1845
1846         /* There should have been at least two fans cut apart here,
1847            otherwise the early exit would have kicked in. */
1848         BLI_assert(len >= 2);
1849
1850         nv = sl->v;
1851
1852         /* Desired result here is that a new vert should always be
1853            created for the unglue face. This is so we can glue any
1854            extras back into the original vert. */
1855         BLI_assert(nv != sv);
1856         BLI_assert(sv == vtar[0]);
1857
1858         /* If there are more than two verts as a result, glue together
1859            all the verts except the one this URMV intended to create */
1860         if (len > 2) {
1861                 for (i = 0; i < len; i++) {
1862                         if (vtar[i] == nv) {
1863                                 break;
1864                         }
1865                 }
1866
1867                 if (i != len) {
1868                         /* Swap the single vert that was needed for the
1869                            unglue into the last array slot */
1870                         SWAP(BMVert *, vtar[i], vtar[len - 1]);
1871
1872                         /* And then glue the rest back together */
1873                         for (i = 1; i < len - 1; i++) {
1874                                 bmesh_splicevert(bm, vtar[i], vtar[0]);
1875                         }
1876                 }
1877         }
1878
1879         MEM_freeN(vtar);
1880
1881         return nv;
1882 }
1883
1884 /*
1885  * BMESH UNGLUE REGION MAKE VERT
1886  *
1887  * Disconnects sf from the vertex fan at sv
1888  */
1889 BMVert *bmesh_urmv(BMesh *bm, BMFace *sf, BMVert *sv)
1890 {
1891         BMLoop *hl, *sl;
1892
1893         hl = sl = bm_firstfaceloop(sf);
1894         do {
1895                 if (sl->v == sv) break;
1896                 sl = sl->next;
1897         } while (sl != hl);
1898                 
1899         if (sl->v != sv) {
1900                 /* sv is not part of sf */
1901                 return NULL;
1902         }
1903
1904         return bmesh_urmv_loop(bm, sl);
1905 }