- add BM_NGON_STACK_SIZE define to use wherever ngon stack arrays are used.
[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, BM_NGON_STACK_SIZE);
206         BLI_array_staticdeclare(verts, BM_NGON_STACK_SIZE);
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, BM_NGON_STACK_SIZE);
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, BM_NGON_STACK_SIZE);
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, BM_NGON_STACK_SIZE);
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,    BM_NGON_STACK_SIZE);
822         BLI_array_staticdeclare(deledges, BM_NGON_STACK_SIZE);
823         BLI_array_staticdeclare(delverts, BM_NGON_STACK_SIZE);
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 {
1152         BMLoop *nextl;
1153         BMEdge *ne;
1154         BMVert *nv, *ov;
1155         int i, edok, valence1=0, valence2=0;
1156
1157         if(bmesh_vert_in_edge(e,tv) == 0) return NULL;
1158         ov = bmesh_edge_getothervert(e,tv);
1159
1160         /*count valence of v1*/
1161         valence1 = bmesh_disk_count(ov);
1162
1163         /*count valence of v2*/
1164         valence2 = bmesh_disk_count(tv);
1165
1166         nv = BM_Make_Vert(bm, tv->co, tv);
1167         ne = BM_Make_Edge(bm, nv, tv, e, 0);
1168
1169         bmesh_disk_remove_edge(ne, tv);
1170         bmesh_disk_remove_edge(ne, nv);
1171
1172         /*remove e from v2's disk cycle*/
1173         bmesh_disk_remove_edge(e, tv);
1174
1175         /*swap out tv for nv in e*/
1176         bmesh_edge_swapverts(e, tv, nv);
1177
1178         /*add e to nv's disk cycle*/
1179         bmesh_disk_append_edge(e, nv);
1180
1181         /*add ne to nv's disk cycle*/
1182         bmesh_disk_append_edge(ne, nv);
1183
1184         /*add ne to tv's disk cycle*/
1185         bmesh_disk_append_edge(ne, tv);
1186
1187         /*verify disk cycles*/
1188         edok = bmesh_disk_validate(valence1, ov->e, ov);
1189         if(!edok) bmesh_error();
1190         edok = bmesh_disk_validate(valence2, tv->e, tv);
1191         if(!edok) bmesh_error();
1192         edok = bmesh_disk_validate(2, nv->e, nv);
1193         if(!edok) bmesh_error();
1194
1195         /*Split the radial cycle if present*/
1196         nextl = e->l;
1197         e->l = NULL;
1198         if(nextl) {
1199                 BMLoop *nl, *l;
1200                 int radlen = bmesh_radial_length(nextl);
1201                 int first1=0, first2=0;
1202
1203                 /*Take the next loop. Remove it from radial. Split it. Append to appropriate radials.*/
1204                 while(nextl) {
1205                         l=nextl;
1206                         l->f->len++;
1207                         nextl = nextl!=nextl->radial_next ? nextl->radial_next : NULL;
1208                         bmesh_radial_remove_loop(l, NULL);
1209
1210                         nl = bmesh_create_loop(bm,NULL,NULL,l->f,l);
1211                         nl->prev = l;
1212                         nl->next = (l->next);
1213                         nl->prev->next = nl;
1214                         nl->next->prev = nl;
1215                         nl->v = nv;
1216
1217                         /*assign the correct edge to the correct loop*/
1218                         if(bmesh_verts_in_edge(nl->v, nl->next->v, e)) {
1219                                 nl->e = e;
1220                                 l->e = ne;
1221
1222                                 /*append l into ne's rad cycle*/
1223                                 if(!first1) {
1224                                         first1 = 1;
1225                                         l->radial_next = l->radial_prev = NULL;
1226                                 }
1227
1228                                 if(!first2) {
1229                                         first2 = 1;
1230                                         l->radial_next = l->radial_prev = NULL;
1231                                 }
1232                                 
1233                                 bmesh_radial_append(nl->e, nl);
1234                                 bmesh_radial_append(l->e, l);
1235                         }
1236                         else if(bmesh_verts_in_edge(nl->v, nl->next->v, ne)){
1237                                 nl->e = ne;
1238                                 l->e = e;
1239
1240                                 /*append l into ne's rad cycle*/
1241                                 if(!first1) {
1242                                         first1 = 1;
1243                                         l->radial_next = l->radial_prev = NULL;
1244                                 }
1245
1246                                 if(!first2) {
1247                                         first2 = 1;
1248                                         l->radial_next = l->radial_prev = NULL;
1249                                 }
1250
1251                                 bmesh_radial_append(nl->e, nl);
1252                                 bmesh_radial_append(l->e, l);
1253                         }
1254
1255                 }
1256
1257                 /*verify length of radial cycle*/
1258                 edok = bmesh_radial_validate(radlen, e->l);
1259                 if(!edok) bmesh_error();
1260                 edok = bmesh_radial_validate(radlen, ne->l);
1261                 if(!edok) bmesh_error();
1262
1263                 /*verify loop->v and loop->next->v pointers for e*/
1264                 for(i=0,l=e->l; i < radlen; i++, l = l->radial_next){
1265                         if(!(l->e == e)) bmesh_error();
1266                         //if(!(l->radial_next == l)) bmesh_error();
1267                         if(l->prev->e != ne && l->next->e != ne) bmesh_error();
1268                         edok = bmesh_verts_in_edge(l->v, l->next->v, e);
1269                         if(!edok) bmesh_error();
1270                         if(l->v == l->next->v) bmesh_error();
1271                         if(l->e == l->next->e) bmesh_error();
1272
1273                         /*verify loop cycle for kloop->f*/
1274                         BM_CHECK_ELEMENT(bm, l);
1275                         BM_CHECK_ELEMENT(bm, l->v);
1276                         BM_CHECK_ELEMENT(bm, l->e);
1277                         BM_CHECK_ELEMENT(bm, l->f);
1278                 }
1279                 /*verify loop->v and loop->next->v pointers for ne*/
1280                 for(i=0,l=ne->l; i < radlen; i++, l = l->radial_next){
1281                         if(!(l->e == ne)) bmesh_error();
1282                         //if(!(l->radial_next == l)) bmesh_error();
1283                         if( l->prev->e != e && l->next->e != e) bmesh_error();
1284                         edok = bmesh_verts_in_edge(l->v, l->next->v, ne);
1285                         if(!edok) bmesh_error();
1286                         if(l->v == l->next->v) bmesh_error();
1287                         if(l->e == l->next->e) bmesh_error();
1288
1289                         BM_CHECK_ELEMENT(bm, l);
1290                         BM_CHECK_ELEMENT(bm, l->v);
1291                         BM_CHECK_ELEMENT(bm, l->e);
1292                         BM_CHECK_ELEMENT(bm, l->f);
1293                 }
1294         }
1295
1296         BM_CHECK_ELEMENT(bm, ne);
1297         BM_CHECK_ELEMENT(bm, nv);
1298         BM_CHECK_ELEMENT(bm, ov);
1299         BM_CHECK_ELEMENT(bm, e);
1300         BM_CHECK_ELEMENT(bm, tv);
1301
1302         if(re) *re = ne;
1303         return nv;
1304 }
1305
1306 /**
1307  *                      bmesh_JEKV
1308  *
1309  *      JOIN EDGE KILL VERT:
1310  *      Takes a an edge and pointer to one of its vertices and collapses
1311  *      the edge on that vertex.
1312  *      
1313  *      Before:    OE      KE
1314  *               ------- -------
1315  *               |     ||      |
1316  *              OV     KV      TV
1317  *
1318  *
1319  *   After:             OE      
1320  *               ---------------
1321  *               |             |
1322  *              OV             TV
1323  *
1324  *
1325  *      Restrictions:
1326  *      KV is a vertex that must have a valance of exactly two. Furthermore
1327  *  both edges in KV's disk cycle (OE and KE) must be unique (no double
1328  *  edges).
1329  *
1330  *      It should also be noted that this euler has the possibility of creating
1331  *      faces with just 2 edges. It is up to the caller to decide what to do with
1332  *  these faces.
1333  *
1334  *  Returns -
1335  *      1 for success, 0 for failure.
1336  */
1337 int bmesh_jekv(BMesh *bm, BMEdge *ke, BMVert *kv)
1338 {
1339         BMEdge *oe;
1340         BMVert *ov, *tv;
1341         BMLoop *killoop, *l;
1342         int len,radlen=0, halt = 0, i, valence1, valence2,edok;
1343         BMLoop **loops = NULL;
1344         BLI_array_staticdeclare(loops, BM_NGON_STACK_SIZE);
1345
1346         if(bmesh_vert_in_edge(ke,kv) == 0) return 0;
1347         len = bmesh_disk_count(kv);
1348         
1349         if(len == 2){
1350                 oe = bmesh_disk_nextedge(ke, kv);
1351                 tv = bmesh_edge_getothervert(ke, kv);
1352                 ov = bmesh_edge_getothervert(oe, kv);           
1353                 halt = bmesh_verts_in_edge(kv, tv, oe); /*check for double edges*/
1354                 
1355                 if(halt) return 0;
1356                 else{
1357                         /*For verification later, count valence of ov and tv*/
1358                         valence1 = bmesh_disk_count(ov);
1359                         valence2 = bmesh_disk_count(tv);
1360                         
1361                         /*remove oe from kv's disk cycle*/
1362                         bmesh_disk_remove_edge(oe,kv);
1363                         /*relink oe->kv to be oe->tv*/
1364                         bmesh_edge_swapverts(oe, kv, tv);
1365                         /*append oe to tv's disk cycle*/
1366                         bmesh_disk_append_edge(oe, tv);
1367                         /*remove ke from tv's disk cycle*/
1368                         bmesh_disk_remove_edge(ke, tv);
1369                 
1370                         /*deal with radial cycle of ke*/
1371                         radlen = bmesh_radial_length(ke->l);
1372                         if(ke->l){
1373                                 /*first step, fix the neighboring loops of all loops in ke's radial cycle*/
1374                                 for(i=0,killoop = ke->l; i<radlen; i++, killoop = bmesh_radial_nextloop(killoop)){
1375                                         /*relink loops and fix vertex pointer*/
1376                                         if( killoop->next->v == kv ) killoop->next->v = tv;
1377
1378                                         killoop->next->prev = killoop->prev;
1379                                         killoop->prev->next = killoop->next;
1380                                         if (bm_firstfaceloop(killoop->f) == killoop)
1381                                                 bm_firstfaceloop(killoop->f) = killoop->next;
1382                                         killoop->next = NULL;
1383                                         killoop->prev = NULL;
1384
1385                                         /*fix len attribute of face*/
1386                                         killoop->f->len--;
1387                                 }
1388                                 /*second step, remove all the hanging loops attached to ke*/
1389                                 killoop = ke->l;
1390                                 radlen = bmesh_radial_length(ke->l);
1391                                 /*this should be wrapped into a bme_free_radial function to be used by bmesh_KF as well...*/
1392                                 for (i=0;i<radlen;i++) {
1393                                         BLI_array_growone(loops);
1394                                         loops[BLI_array_count(loops)-1] = killoop;
1395                                         killoop = bmesh_radial_nextloop(killoop);
1396                                 }
1397                                 for (i=0;i<radlen;i++) {
1398                                         bm->totloop--;
1399                                         BLI_mempool_free(bm->lpool, loops[i]);
1400                                 }
1401                                 /*Validate radial cycle of oe*/
1402                                 edok = bmesh_radial_validate(radlen,oe->l);
1403                                 if(!edok) bmesh_error();
1404                         }
1405
1406                         /*deallocate edge*/
1407                         BM_remove_selection(bm, ke);
1408                         BLI_mempool_free(bm->toolflagpool, ke->head.flags);
1409                         BLI_mempool_free(bm->epool, ke);
1410                         bm->totedge--;
1411                         /*deallocate vertex*/
1412                         BM_remove_selection(bm, kv);
1413                         BLI_mempool_free(bm->toolflagpool, kv->head.flags);
1414                         BLI_mempool_free(bm->vpool, kv);
1415                         bm->totvert--;
1416                         /* account for both above */
1417                         bm->elem_index_dirty |= BM_VERT | BM_EDGE;
1418
1419                         /*Validate disk cycle lengths of ov,tv are unchanged*/
1420                         edok = bmesh_disk_validate(valence1, ov->e, ov);
1421                         if(!edok) bmesh_error();
1422                         edok = bmesh_disk_validate(valence2, tv->e, tv);
1423                         if(!edok) bmesh_error();
1424
1425                         /*Validate loop cycle of all faces attached to oe*/
1426                         for(i=0,l = oe->l; i<radlen; i++, l = bmesh_radial_nextloop(l)){
1427                                 if(l->e != oe) bmesh_error();
1428                                 edok = bmesh_verts_in_edge(l->v, l->next->v, oe);
1429                                 if(!edok) bmesh_error();
1430                                 edok = bmesh_loop_validate(l->f);
1431                                 if(!edok) bmesh_error();
1432
1433                                 BM_CHECK_ELEMENT(bm, l);
1434                                 BM_CHECK_ELEMENT(bm, l->v);
1435                                 BM_CHECK_ELEMENT(bm, l->e);
1436                                 BM_CHECK_ELEMENT(bm, l->f);
1437                         }
1438
1439                         BM_CHECK_ELEMENT(bm, ov);
1440                         BM_CHECK_ELEMENT(bm, tv);
1441                         BM_CHECK_ELEMENT(bm, oe);
1442
1443                         return 1;
1444                 }
1445         }
1446         return 0;
1447 }
1448
1449 /**
1450  *                      bmesh_JFKE
1451  *
1452  *      JOIN FACE KILL EDGE:
1453  *      
1454  *      Takes two faces joined by a single 2-manifold edge and fuses them togather.
1455  *      The edge shared by the faces must not be connected to any other edges which have
1456  *      Both faces in its radial cycle
1457  *
1458  *      Examples:
1459  *      
1460  *        A                   B
1461  *       ----------           ----------
1462  *       |        |           |        | 
1463  *       |   f1   |           |   f1   |
1464  *      v1========v2 = Ok!    v1==V2==v3 == Wrong!
1465  *       |   f2   |           |   f2   |
1466  *       |        |           |        |
1467  *       ----------           ---------- 
1468  *
1469  *      In the example A, faces f1 and f2 are joined by a single edge, and the euler can safely be used.
1470  *      In example B however, f1 and f2 are joined by multiple edges and will produce an error. The caller
1471  *      in this case should call bmesh_JEKV on the extra edges before attempting to fuse f1 and f2.
1472  *
1473  *      Also note that the order of arguments decides whether or not certain per-face attributes are present
1474  *      in the resultant face. For instance vertex winding, material index, smooth flags, ect are inherited
1475  *      from f1, not f2.
1476  *
1477  *  Returns -
1478  *      A BMFace pointer
1479 */
1480 BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e)
1481 {
1482         BMLoop *curloop, *f1loop=NULL, *f2loop=NULL;
1483         int newlen = 0,i, f1len=0, f2len=0, radlen=0, edok, shared;
1484         BMIter iter;
1485
1486         /*can't join a face to itself*/
1487         if(f1 == f2) return NULL;
1488         /*verify that e is in both f1 and f2*/
1489         f1len = f1->len;
1490         f2len = f2->len;
1491         BM_ITER(curloop, &iter, bm, BM_LOOPS_OF_FACE, f1) {
1492                 if(curloop->e == e){ 
1493                         f1loop = curloop;
1494                         break;
1495                 }
1496         }
1497         BM_ITER(curloop, &iter, bm, BM_LOOPS_OF_FACE, f2) {
1498                 if(curloop->e == e){
1499                         f2loop = curloop;
1500                         break;
1501                 }
1502         }
1503         if (!(f1loop && f2loop)) return NULL;
1504         
1505         /*validate that edge is 2-manifold edge*/
1506         radlen = bmesh_radial_length(f1loop);
1507         if(radlen != 2) return NULL;
1508
1509         /*validate direction of f2's loop cycle is compatible.*/
1510         if(f1loop->v == f2loop->v) return NULL;
1511
1512         /*
1513                 validate that for each face, each vertex has another edge in its disk cycle that is 
1514                 not e, and not shared.
1515         */
1516         if(bmesh_radial_find_face(f1loop->next->e,f2)) return NULL;
1517         if(bmesh_radial_find_face(f1loop->prev->e,f2)) return NULL;
1518         if(bmesh_radial_find_face(f2loop->next->e,f1)) return NULL;
1519         if(bmesh_radial_find_face(f2loop->prev->e,f1)) return NULL;
1520         
1521         /*validate only one shared edge*/
1522         shared = BM_Face_Share_Edges(f1,f2);
1523         if(shared > 1) return NULL;
1524
1525         /*validate no internal joins*/
1526         for(i=0, curloop = bm_firstfaceloop(f1); i < f1len; i++, curloop = curloop->next)
1527                 bmesh_api_setindex(curloop->v, 0);
1528         for(i=0, curloop = bm_firstfaceloop(f2); i < f2len; i++, curloop = curloop->next)
1529                 bmesh_api_setindex(curloop->v, 0);
1530
1531         for(i=0, curloop = bm_firstfaceloop(f1); i < f1len; i++, curloop = curloop->next) {
1532                 if (curloop != f1loop)
1533                         bmesh_api_setindex(curloop->v, bmesh_api_getindex(curloop->v) + 1);
1534         }
1535         for(i=0, curloop = bm_firstfaceloop(f2); i < f2len; i++, curloop = curloop->next) {
1536                 if (curloop != f2loop)
1537                         bmesh_api_setindex(curloop->v, bmesh_api_getindex(curloop->v) + 1);
1538         }
1539
1540         for(i=0, curloop = bm_firstfaceloop(f1); i < f1len; i++, curloop = curloop->next) {
1541                 if (bmesh_api_getindex(curloop->v) > 1)
1542                         return NULL;
1543         }
1544         
1545         for(i=0, curloop = bm_firstfaceloop(f2); i < f2len; i++, curloop = curloop->next) {
1546                 if (bmesh_api_getindex(curloop->v) > 1)
1547                         return NULL;
1548         }
1549
1550         /*join the two loops*/
1551         f1loop->prev->next = f2loop->next;
1552         f2loop->next->prev = f1loop->prev;
1553         
1554         f1loop->next->prev = f2loop->prev;
1555         f2loop->prev->next = f1loop->next;
1556         
1557         /*if f1loop was baseloop, make f1loop->next the base.*/
1558         if(bm_firstfaceloop(f1) == f1loop)
1559                 bm_firstfaceloop(f1) = f1loop->next;
1560
1561         /*increase length of f1*/
1562         f1->len += (f2->len - 2);
1563
1564         /*make sure each loop points to the proper face*/
1565         newlen = f1->len;
1566         for(i = 0, curloop = bm_firstfaceloop(f1); i < newlen; i++, curloop = curloop->next)
1567                 curloop->f = f1;
1568         
1569         /*remove edge from the disk cycle of its two vertices.*/
1570         bmesh_disk_remove_edge(f1loop->e, f1loop->e->v1);
1571         bmesh_disk_remove_edge(f1loop->e, f1loop->e->v2);
1572         
1573         /*deallocate edge and its two loops as well as f2*/
1574         BLI_mempool_free(bm->toolflagpool, f1loop->e->head.flags);
1575         BLI_mempool_free(bm->epool, f1loop->e);
1576         bm->totedge--;
1577         BLI_mempool_free(bm->lpool, f1loop);
1578         bm->totloop--;
1579         BLI_mempool_free(bm->lpool, f2loop);
1580         bm->totloop--;
1581         BLI_mempool_free(bm->toolflagpool, f2->head.flags);
1582         BLI_mempool_free(bm->fpool, f2);
1583         bm->totface--;
1584         /* account for both above */
1585         bm->elem_index_dirty |= BM_EDGE | BM_FACE;
1586
1587         BM_CHECK_ELEMENT(bm, f1);
1588
1589         /*validate the new loop cycle*/
1590         edok = bmesh_loop_validate(f1);
1591         if(!edok) bmesh_error();
1592         
1593         return f1;
1594 }
1595
1596 /*
1597  * BMESH SPLICE VERT
1598  *
1599  * merges two verts into one (v into vtarget).
1600  */
1601 static int bmesh_splicevert(BMesh *bm, BMVert *v, BMVert *vtarget)
1602 {
1603         BMEdge *e;
1604         BMLoop *l;
1605         BMIter liter;
1606
1607         /* verts already spliced */
1608         if (v == vtarget) {
1609                 return 0;
1610         }
1611
1612         /* retarget all the loops of v to vtarget */
1613         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
1614                 l->v = vtarget;
1615         }
1616
1617         /* move all the edges from v's disk to vtarget's disk */
1618         e = v->e;
1619         while (e != NULL) {
1620                 bmesh_disk_remove_edge(e, v);
1621                 bmesh_edge_swapverts(e, v, vtarget);
1622                 bmesh_disk_append_edge(e, vtarget);
1623                 e = v->e;
1624         }
1625
1626         BM_CHECK_ELEMENT(bm, v);
1627         BM_CHECK_ELEMENT(bm, vtarget);
1628
1629         /* v is unused now, and can be killed */
1630         BM_Kill_Vert(bm, v);
1631
1632         return 1;
1633 }
1634
1635 /* BMESH CUT VERT
1636  *
1637  * cut all disjoint fans that meet at a vertex, making a unique
1638  * vertex for each region. returns an array of all resulting
1639  * vertices.
1640  */
1641 static int bmesh_cutvert(BMesh *bm, BMVert *v, BMVert ***vout, int *len)
1642 {
1643         BMEdge **stack = NULL;
1644         BLI_array_declare(stack);
1645         BMVert **verts = NULL;
1646         GHash *visithash;
1647         BMIter eiter, liter;
1648         BMLoop *l;
1649         BMEdge *e;
1650         int i, maxindex;
1651         BMLoop *nl;
1652
1653         visithash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "bmesh_cutvert visithash");
1654
1655         maxindex = 0;
1656         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
1657                 if (BLI_ghash_haskey(visithash, e)) {
1658                         continue;
1659                 }
1660
1661                 /* Prime the stack with this unvisited edge */
1662                 BLI_array_append(stack, e);
1663
1664                 /* Considering only edges and faces incident on vertex v, walk
1665                    the edges & faces and assign an index to each connected set */
1666                 while ((e = BLI_array_pop(stack))) {
1667                         BLI_ghash_insert(visithash, e, SET_INT_IN_POINTER(maxindex));
1668
1669                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
1670                                 nl = (l->v == v) ? l->prev : l->next;
1671                                 if (!BLI_ghash_haskey(visithash, nl->e)) {
1672                                         BLI_array_append(stack, nl->e);
1673                                 }
1674                         }
1675                 }
1676
1677                 maxindex++;
1678         }
1679
1680         /* Make enough verts to split v for each group */
1681         verts = MEM_callocN(sizeof(BMVert *) * maxindex, "bmesh_cutvert");
1682         verts[0] = v;
1683         for (i = 1; i < maxindex; i++) {
1684                 verts[i] = BM_Make_Vert(bm, v->co, v);
1685         }
1686
1687         /* Replace v with the new verts in each group */
1688         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
1689                 i = GET_INT_FROM_POINTER(BLI_ghash_lookup(visithash, l->e));
1690                 if (i == 0) {
1691                         continue;
1692                 }
1693
1694                 /* Loops here should alway refer to an edge that has v as an
1695                    endpoint. For each appearance of this vert in a face, there
1696                    will actually be two iterations: one for the loop heading
1697                    towards vertex v, and another for the loop heading out from
1698                    vertex v. Only need to swap the vertex on one of those times,
1699                    on the outgoing loop. */
1700                 if (l->v == v) {
1701                         l->v = verts[i];
1702                 }
1703         }
1704
1705         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
1706                 i = GET_INT_FROM_POINTER(BLI_ghash_lookup(visithash, e));
1707                 if (i == 0) {
1708                         continue;
1709                 }
1710
1711                 BLI_assert(e->v1 == v || e->v2 == v);
1712                 bmesh_disk_remove_edge(e, v);
1713                 bmesh_edge_swapverts(e, v, verts[i]);
1714                 bmesh_disk_append_edge(e, verts[i]);
1715         }
1716
1717         BLI_ghash_free(visithash, NULL, NULL);
1718         BLI_array_free(stack);
1719
1720         for (i = 0; i < maxindex; i++) {
1721                 BM_CHECK_ELEMENT(bm, verts[i]);
1722         }
1723
1724         if (len != NULL) {
1725                 *len = maxindex;
1726         }
1727
1728         if (vout != NULL) {
1729                 *vout = verts;
1730         }
1731         else {
1732                 MEM_freeN(verts);
1733         }
1734
1735         return 1;
1736 }
1737
1738 /* BMESH SPLICE EDGE
1739  *
1740  * splice two unique edges which share the same two vertices into one edge.
1741  *
1742  * edges must already have the same vertices
1743  */
1744 static int UNUSED_FUNCTION(bmesh_spliceedge)(BMesh *bm, BMEdge *e, BMEdge *etarget)
1745 {
1746         BMLoop *l;
1747
1748         if (!BM_Vert_In_Edge(e, etarget->v1) || !BM_Vert_In_Edge(e, etarget->v2)) {
1749                 /* not the same vertices can't splice */
1750                 return 0;
1751         }
1752
1753         while (e->l) {
1754                 l = e->l;
1755                 BLI_assert(BM_Vert_In_Edge(etarget, l->v));
1756                 BLI_assert(BM_Vert_In_Edge(etarget, l->next->v));
1757                 bmesh_radial_remove_loop(l, e);
1758                 bmesh_radial_append(etarget, l);
1759         }
1760
1761         BLI_assert(bmesh_radial_length(e->l) == 0);
1762
1763         BM_CHECK_ELEMENT(bm, e);
1764         BM_CHECK_ELEMENT(bm, etarget);
1765
1766         BM_Kill_Edge(bm, e);
1767
1768         return 1;
1769 }
1770
1771 /*
1772  * BMESH CUT EDGE
1773  *
1774  * Cuts a single edge into two edge: the original edge and
1775  * a new edge that has only "cutl" in its radial.
1776  *
1777  * Does nothing if cutl is already the only loop in the
1778  * edge radial.
1779  */
1780 static int bmesh_cutedge(BMesh *bm, BMEdge *e, BMLoop *cutl)
1781 {
1782         BMEdge *ne;
1783         int radlen;
1784
1785         BLI_assert(cutl->e == e);
1786         BLI_assert(e->l);
1787         
1788         radlen = bmesh_radial_length(e->l);
1789         if (radlen < 2) {
1790                 /* no cut required */
1791                 return 1;
1792         }
1793
1794         if (cutl == e->l) {
1795                 e->l = cutl->radial_next;
1796         }
1797
1798         ne = BM_Make_Edge(bm, e->v1, e->v2, e, 0);
1799         bmesh_radial_remove_loop(cutl, e);
1800         bmesh_radial_append(ne, cutl);
1801         cutl->e = ne;
1802
1803         BLI_assert(bmesh_radial_length(e->l) == radlen - 1);
1804         BLI_assert(bmesh_radial_length(ne->l) == 1);
1805
1806         BM_CHECK_ELEMENT(bm, ne);
1807         BM_CHECK_ELEMENT(bm, e);
1808
1809         return 1;
1810 }
1811
1812 /*
1813  * BMESH UNGLUE REGION MAKE VERT
1814  *
1815  * Disconnects a face from its vertex fan at loop sl.
1816  */
1817 static BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *sl)
1818 {
1819         BMVert **vtar;
1820         int len, i;
1821         BMVert *nv = NULL;
1822         BMVert *sv = sl->v;
1823
1824         /* peel the face from the edge radials on both sides of the
1825            loop vert, disconnecting the face from its fan */
1826         bmesh_cutedge(bm, sl->e, sl);
1827         bmesh_cutedge(bm, sl->prev->e, sl->prev);
1828
1829         if (bmesh_disk_count(sv) == 2) {
1830                 /* If there are still only two edges out of sv, then
1831                    this whole URMV was just a no-op, so exit now. */
1832                 return sv;
1833         }
1834
1835         /* Update the disk start, so that v->e points to an edge
1836            not touching the split loop. This is so that bmesh_cutvert
1837            will leave the original sv on some *other* fan (not the
1838            one-face fan that holds the unglue face). */
1839         while (sv->e == sl->e || sv->e == sl->prev->e) {
1840                 sv->e = bmesh_disk_nextedge(sv->e, sv);
1841         }
1842
1843         /* Split all fans connected to the vert, duplicating it for
1844            each fans. */
1845         bmesh_cutvert(bm, sv, &vtar, &len);
1846
1847         /* There should have been at least two fans cut apart here,
1848            otherwise the early exit would have kicked in. */
1849         BLI_assert(len >= 2);
1850
1851         nv = sl->v;
1852
1853         /* Desired result here is that a new vert should always be
1854            created for the unglue face. This is so we can glue any
1855            extras back into the original vert. */
1856         BLI_assert(nv != sv);
1857         BLI_assert(sv == vtar[0]);
1858
1859         /* If there are more than two verts as a result, glue together
1860            all the verts except the one this URMV intended to create */
1861         if (len > 2) {
1862                 for (i = 0; i < len; i++) {
1863                         if (vtar[i] == nv) {
1864                                 break;
1865                         }
1866                 }
1867
1868                 if (i != len) {
1869                         /* Swap the single vert that was needed for the
1870                            unglue into the last array slot */
1871                         SWAP(BMVert *, vtar[i], vtar[len - 1]);
1872
1873                         /* And then glue the rest back together */
1874                         for (i = 1; i < len - 1; i++) {
1875                                 bmesh_splicevert(bm, vtar[i], vtar[0]);
1876                         }
1877                 }
1878         }
1879
1880         MEM_freeN(vtar);
1881
1882         return nv;
1883 }
1884
1885 /*
1886  * BMESH UNGLUE REGION MAKE VERT
1887  *
1888  * Disconnects sf from the vertex fan at sv
1889  */
1890 BMVert *bmesh_urmv(BMesh *bm, BMFace *sf, BMVert *sv)
1891 {
1892         BMLoop *hl, *sl;
1893
1894         hl = sl = bm_firstfaceloop(sf);
1895         do {
1896                 if (sl->v == sv) break;
1897                 sl = sl->next;
1898         } while (sl != hl);
1899                 
1900         if (sl->v != sv) {
1901                 /* sv is not part of sf */
1902                 return NULL;
1903         }
1904
1905         return bmesh_urmv_loop(bm, sl);
1906 }