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