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