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