BMesh: face-flip, no need for temporary edge-array
[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  * Core BMesh functions for adding, removing BMesh elements.
27  */
28
29 #include "MEM_guardedalloc.h"
30
31 #include "BLI_math_vector.h"
32 #include "BLI_array.h"
33 #include "BLI_alloca.h"
34 #include "BLI_linklist_stack.h"
35 #include "BLI_stackdefines.h"
36
37 #include "BLT_translation.h"
38
39 #include "BKE_DerivedMesh.h"
40 #include "BKE_mesh.h"
41
42 #include "bmesh.h"
43 #include "intern/bmesh_private.h"
44
45 /* use so valgrinds memcheck alerts us when undefined index is used.
46  * TESTING ONLY! */
47 // #define USE_DEBUG_INDEX_MEMCHECK
48
49 #ifdef USE_DEBUG_INDEX_MEMCHECK
50 #define DEBUG_MEMCHECK_INDEX_INVALIDATE(ele)                                  \
51         {                                                                         \
52                 int undef_idx;                                                        \
53                 BM_elem_index_set(ele, undef_idx); /* set_ok_invalid */               \
54         } (void)0
55
56 #endif
57
58 /**
59  * \brief Main function for creating a new vertex.
60  */
61 BMVert *BM_vert_create(
62         BMesh *bm, const float co[3],
63         const BMVert *v_example, const eBMCreateFlag create_flag)
64 {
65         BMVert *v = BLI_mempool_alloc(bm->vpool);
66
67         BLI_assert((v_example == NULL) || (v_example->head.htype == BM_VERT));
68         BLI_assert(!(create_flag & 1));
69
70         /* --- assign all members --- */
71         v->head.data = NULL;
72
73 #ifdef USE_DEBUG_INDEX_MEMCHECK
74         DEBUG_MEMCHECK_INDEX_INVALIDATE(v)
75 #else
76         BM_elem_index_set(v, -1); /* set_ok_invalid */
77 #endif
78
79         v->head.htype = BM_VERT;
80         v->head.hflag = 0;
81         v->head.api_flag = 0;
82
83         /* allocate flags */
84         if (bm->use_toolflags) {
85                 ((BMVert_OFlag *)v)->oflags = bm->vtoolflagpool ? BLI_mempool_calloc(bm->vtoolflagpool) : NULL;
86         }
87
88         /* 'v->no' is handled by BM_elem_attrs_copy */
89         if (co) {
90                 copy_v3_v3(v->co, co);
91         }
92         else {
93                 zero_v3(v->co);
94         }
95         /* 'v->no' set below */
96
97         v->e = NULL;
98         /* --- done --- */
99
100
101         /* disallow this flag for verts - its meaningless */
102         BLI_assert((create_flag & BM_CREATE_NO_DOUBLE) == 0);
103
104         /* may add to middle of the pool */
105         bm->elem_index_dirty |= BM_VERT;
106         bm->elem_table_dirty |= BM_VERT;
107
108         bm->totvert++;
109
110         if (!(create_flag & BM_CREATE_SKIP_CD)) {
111                 if (v_example) {
112                         int *keyi;
113
114                         /* handles 'v->no' too */
115                         BM_elem_attrs_copy(bm, bm, v_example, v);
116
117                         /* exception: don't copy the original shapekey index */
118                         keyi = CustomData_bmesh_get(&bm->vdata, v->head.data, CD_SHAPE_KEYINDEX);
119                         if (keyi) {
120                                 *keyi = ORIGINDEX_NONE;
121                         }
122                 }
123                 else {
124                         CustomData_bmesh_set_default(&bm->vdata, &v->head.data);
125                         zero_v3(v->no);
126                 }
127         }
128         else {
129                 if (v_example) {
130                         copy_v3_v3(v->no, v_example->no);
131                 }
132                 else {
133                         zero_v3(v->no);
134                 }
135         }
136
137         BM_CHECK_ELEMENT(v);
138
139         return v;
140 }
141
142 /**
143  * \brief Main function for creating a new edge.
144  *
145  * \note Duplicate edges are supported by the API however users should _never_ see them.
146  * so unless you need a unique edge or know the edge won't exist, you should call with \a no_double = true
147  */
148 BMEdge *BM_edge_create(
149         BMesh *bm, BMVert *v1, BMVert *v2,
150         const BMEdge *e_example, const eBMCreateFlag create_flag)
151 {
152         BMEdge *e;
153
154         BLI_assert(v1 != v2);
155         BLI_assert(v1->head.htype == BM_VERT && v2->head.htype == BM_VERT);
156         BLI_assert((e_example == NULL) || (e_example->head.htype == BM_EDGE));
157         BLI_assert(!(create_flag & 1));
158
159         if ((create_flag & BM_CREATE_NO_DOUBLE) && (e = BM_edge_exists(v1, v2)))
160                 return e;
161         
162         e = BLI_mempool_alloc(bm->epool);
163
164
165         /* --- assign all members --- */
166         e->head.data = NULL;
167
168 #ifdef USE_DEBUG_INDEX_MEMCHECK
169         DEBUG_MEMCHECK_INDEX_INVALIDATE(e)
170 #else
171         BM_elem_index_set(e, -1); /* set_ok_invalid */
172 #endif
173
174         e->head.htype = BM_EDGE;
175         e->head.hflag = BM_ELEM_SMOOTH | BM_ELEM_DRAW;
176         e->head.api_flag = 0;
177
178         /* allocate flags */
179         if (bm->use_toolflags) {
180                 ((BMEdge_OFlag *)e)->oflags = bm->etoolflagpool ? BLI_mempool_calloc(bm->etoolflagpool) : NULL;
181         }
182
183         e->v1 = v1;
184         e->v2 = v2;
185         e->l = NULL;
186
187         memset(&e->v1_disk_link, 0, sizeof(BMDiskLink) * 2);
188         /* --- done --- */
189
190
191         bmesh_disk_edge_append(e, e->v1);
192         bmesh_disk_edge_append(e, e->v2);
193
194         /* may add to middle of the pool */
195         bm->elem_index_dirty |= BM_EDGE;
196         bm->elem_table_dirty |= BM_EDGE;
197
198         bm->totedge++;
199
200         if (!(create_flag & BM_CREATE_SKIP_CD)) {
201                 if (e_example) {
202                         BM_elem_attrs_copy(bm, bm, e_example, e);
203                 }
204                 else {
205                         CustomData_bmesh_set_default(&bm->edata, &e->head.data);
206                 }
207         }
208
209         BM_CHECK_ELEMENT(e);
210
211         return e;
212 }
213
214 /**
215  * \note In most cases a \a l_example should be NULL,
216  * since this is a low level API and we shouldn't attempt to be clever and guess whats intended.
217  * In cases where copying adjacent loop-data is useful, see #BM_face_copy_shared.
218  */
219 static BMLoop *bm_loop_create(
220         BMesh *bm, BMVert *v, BMEdge *e, BMFace *f,
221         const BMLoop *l_example, const eBMCreateFlag create_flag)
222 {
223         BMLoop *l = NULL;
224
225         l = BLI_mempool_alloc(bm->lpool);
226
227         BLI_assert((l_example == NULL) || (l_example->head.htype == BM_LOOP));
228         BLI_assert(!(create_flag & 1));
229
230 #ifndef NDEBUG
231         if (l_example) {
232                 /* ensure passing a loop is either sharing the same vertex, or entirely disconnected
233                  * use to catch mistake passing in loop offset-by-one. */
234                 BLI_assert((v == l_example->v) || !ELEM(v, l_example->prev->v, l_example->next->v));
235         }
236 #endif
237
238         /* --- assign all members --- */
239         l->head.data = NULL;
240
241 #ifdef USE_DEBUG_INDEX_MEMCHECK
242         DEBUG_MEMCHECK_INDEX_INVALIDATE(l)
243 #else
244         BM_elem_index_set(l, -1); /* set_ok_invalid */
245 #endif
246
247         l->head.htype = BM_LOOP;
248         l->head.hflag = 0;
249         l->head.api_flag = 0;
250
251         l->v = v;
252         l->e = e;
253         l->f = f;
254
255         l->radial_next = NULL;
256         l->radial_prev = NULL;
257         l->next = NULL;
258         l->prev = NULL;
259         /* --- done --- */
260
261         /* may add to middle of the pool */
262         bm->elem_index_dirty |= BM_LOOP;
263
264         bm->totloop++;
265
266         if (!(create_flag & BM_CREATE_SKIP_CD)) {
267                 if (l_example) {
268                         /* no need to copy attrs, just handle customdata */
269                         // BM_elem_attrs_copy(bm, bm, l_example, l);
270                         CustomData_bmesh_free_block_data(&bm->ldata, l->head.data);
271                         CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, l_example->head.data, &l->head.data);
272                 }
273                 else {
274                         CustomData_bmesh_set_default(&bm->ldata, &l->head.data);
275                 }
276         }
277
278         return l;
279 }
280
281 static BMLoop *bm_face_boundary_add(
282         BMesh *bm, BMFace *f, BMVert *startv, BMEdge *starte,
283         const eBMCreateFlag create_flag)
284 {
285 #ifdef USE_BMESH_HOLES
286         BMLoopList *lst = BLI_mempool_calloc(bm->looplistpool);
287 #endif
288         BMLoop *l = bm_loop_create(bm, startv, starte, f, NULL /* starte->l */, create_flag);
289         
290         bmesh_radial_loop_append(starte, l);
291
292 #ifdef USE_BMESH_HOLES
293         lst->first = lst->last = l;
294         BLI_addtail(&f->loops, lst);
295 #else
296         f->l_first = l;
297 #endif
298         
299         return l;
300 }
301
302 BMFace *BM_face_copy(
303         BMesh *bm_dst, BMesh *bm_src, BMFace *f,
304         const bool copy_verts, const bool copy_edges)
305 {
306         BMVert **verts = BLI_array_alloca(verts, f->len);
307         BMEdge **edges = BLI_array_alloca(edges, f->len);
308         BMLoop *l_iter;
309         BMLoop *l_first;
310         BMLoop *l_copy;
311         BMFace *f_copy;
312         int i;
313
314         BLI_assert((bm_dst == bm_src) || (copy_verts && copy_edges));
315
316         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
317         i = 0;
318         do {
319                 if (copy_verts) {
320                         verts[i] = BM_vert_create(bm_dst, l_iter->v->co, l_iter->v, BM_CREATE_NOP);
321                 }
322                 else {
323                         verts[i] = l_iter->v;
324                 }
325                 i++;
326         } while ((l_iter = l_iter->next) != l_first);
327
328         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
329         i = 0;
330         do {
331                 if (copy_edges) {
332                         BMVert *v1, *v2;
333                         
334                         if (l_iter->e->v1 == verts[i]) {
335                                 v1 = verts[i];
336                                 v2 = verts[(i + 1) % f->len];
337                         }
338                         else {
339                                 v2 = verts[i];
340                                 v1 = verts[(i + 1) % f->len];
341                         }
342                         
343                         edges[i] = BM_edge_create(bm_dst, v1, v2, l_iter->e, BM_CREATE_NOP);
344                 }
345                 else {
346                         edges[i] = l_iter->e;
347                 }
348                 i++;
349         } while ((l_iter = l_iter->next) != l_first);
350         
351         f_copy = BM_face_create(bm_dst, verts, edges, f->len, NULL, BM_CREATE_SKIP_CD);
352         
353         BM_elem_attrs_copy(bm_src, bm_dst, f, f_copy);
354         
355         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
356         l_copy = BM_FACE_FIRST_LOOP(f_copy);
357         do {
358                 BM_elem_attrs_copy(bm_src, bm_dst, l_iter, l_copy);
359                 l_copy = l_copy->next;
360         } while ((l_iter = l_iter->next) != l_first);
361
362         return f_copy;
363 }
364
365 /**
366  * only create the face, since this calloc's the length is initialized to 0,
367  * leave adding loops to the caller.
368  *
369  * \note, caller needs to handle customdata.
370  */
371 BLI_INLINE BMFace *bm_face_create__internal(BMesh *bm)
372 {
373         BMFace *f;
374
375         f = BLI_mempool_alloc(bm->fpool);
376
377
378         /* --- assign all members --- */
379         f->head.data = NULL;
380 #ifdef USE_DEBUG_INDEX_MEMCHECK
381         DEBUG_MEMCHECK_INDEX_INVALIDATE(f)
382 #else
383         BM_elem_index_set(f, -1); /* set_ok_invalid */
384 #endif
385
386         f->head.htype = BM_FACE;
387         f->head.hflag = 0;
388         f->head.api_flag = 0;
389
390         /* allocate flags */
391         if (bm->use_toolflags) {
392                 ((BMFace_OFlag *)f)->oflags = bm->ftoolflagpool ? BLI_mempool_calloc(bm->ftoolflagpool) : NULL;
393         }
394
395 #ifdef USE_BMESH_HOLES
396         BLI_listbase_clear(&f->loops);
397 #else
398         f->l_first = NULL;
399 #endif
400         f->len = 0;
401         /* caller must initialize */
402         // zero_v3(f->no);
403         f->mat_nr = 0;
404         /* --- done --- */
405
406
407         /* may add to middle of the pool */
408         bm->elem_index_dirty |= BM_FACE;
409         bm->elem_table_dirty |= BM_FACE;
410
411         bm->totface++;
412
413 #ifdef USE_BMESH_HOLES
414         f->totbounds = 0;
415 #endif
416
417         return f;
418 }
419
420 /**
421  * Main face creation function
422  *
423  * \param bm  The mesh
424  * \param verts  A sorted array of verts size of len
425  * \param edges  A sorted array of edges size of len
426  * \param len  Length of the face
427  * \param create_flag  Options for creating the face
428  */
429 BMFace *BM_face_create(
430         BMesh *bm, BMVert **verts, BMEdge **edges, const int len,
431         const BMFace *f_example, const eBMCreateFlag create_flag)
432 {
433         BMFace *f = NULL;
434         BMLoop *l, *startl, *lastl;
435         int i;
436
437         BLI_assert((f_example == NULL) || (f_example->head.htype == BM_FACE));
438         BLI_assert(!(create_flag & 1));
439
440         if (len == 0) {
441                 /* just return NULL for now */
442                 return NULL;
443         }
444
445         if (create_flag & BM_CREATE_NO_DOUBLE) {
446                 /* Check if face already exists */
447                 const bool is_overlap = BM_face_exists(verts, len, &f);
448                 if (is_overlap) {
449                         return f;
450                 }
451                 else {
452                         BLI_assert(f == NULL);
453                 }
454         }
455
456         f = bm_face_create__internal(bm);
457
458         startl = lastl = bm_face_boundary_add(bm, f, verts[0], edges[0], create_flag);
459
460         for (i = 1; i < len; i++) {
461                 l = bm_loop_create(bm, verts[i], edges[i], f, NULL /* edges[i]->l */, create_flag);
462
463                 bmesh_radial_loop_append(edges[i], l);
464
465                 l->prev = lastl;
466                 lastl->next = l;
467                 lastl = l;
468         }
469         
470         startl->prev = lastl;
471         lastl->next = startl;
472         
473         f->len = len;
474         
475         if (!(create_flag & BM_CREATE_SKIP_CD)) {
476                 if (f_example) {
477                         BM_elem_attrs_copy(bm, bm, f_example, f);
478                 }
479                 else {
480                         CustomData_bmesh_set_default(&bm->pdata, &f->head.data);
481                         zero_v3(f->no);
482                 }
483         }
484         else {
485                 if (f_example) {
486                         copy_v3_v3(f->no, f_example->no);
487                 }
488                 else {
489                         zero_v3(f->no);
490                 }
491         }
492
493         BM_CHECK_ELEMENT(f);
494
495         return f;
496 }
497
498 /**
499  * Wrapper for #BM_face_create when you don't have an edge array
500  */
501 BMFace *BM_face_create_verts(
502         BMesh *bm, BMVert **vert_arr, const int len,
503         const BMFace *f_example, const eBMCreateFlag create_flag, const bool create_edges)
504 {
505         BMEdge **edge_arr = BLI_array_alloca(edge_arr, len);
506
507         if (create_edges) {
508                 BM_edges_from_verts_ensure(bm, edge_arr, vert_arr, len);
509         }
510         else {
511                 if (BM_edges_from_verts(edge_arr, vert_arr, len) == false) {
512                         return NULL;
513                 }
514         }
515
516         return BM_face_create(bm, vert_arr, edge_arr, len, f_example, create_flag);
517 }
518
519 #ifndef NDEBUG
520
521 /**
522  * Check the element is valid.
523  *
524  * BMESH_TODO, when this raises an error the output is incredibly confusing.
525  * need to have some nice way to print/debug what the heck's going on.
526  */
527 int bmesh_elem_check(void *element, const char htype)
528 {
529         BMHeader *head = element;
530         enum {
531                 IS_NULL                                     = (1 << 0),
532                 IS_WRONG_TYPE                               = (1 << 1),
533
534                 IS_VERT_WRONG_EDGE_TYPE                     = (1 << 2),
535
536                 IS_EDGE_NULL_DISK_LINK                      = (1 << 3),
537                 IS_EDGE_WRONG_LOOP_TYPE                     = (1 << 4),
538                 IS_EDGE_WRONG_FACE_TYPE                     = (1 << 5),
539                 IS_EDGE_NULL_RADIAL_LINK                    = (1 << 6),
540                 IS_EDGE_ZERO_FACE_LENGTH                    = (1 << 7),
541
542                 IS_LOOP_WRONG_FACE_TYPE                     = (1 << 8),
543                 IS_LOOP_WRONG_EDGE_TYPE                     = (1 << 9),
544                 IS_LOOP_WRONG_VERT_TYPE                     = (1 << 10),
545                 IS_LOOP_VERT_NOT_IN_EDGE                    = (1 << 11),
546                 IS_LOOP_NULL_CYCLE_LINK                     = (1 << 12),
547                 IS_LOOP_ZERO_FACE_LENGTH                    = (1 << 13),
548                 IS_LOOP_WRONG_FACE_LENGTH                   = (1 << 14),
549                 IS_LOOP_WRONG_RADIAL_LENGTH                 = (1 << 15),
550
551                 IS_FACE_NULL_LOOP                           = (1 << 16),
552                 IS_FACE_WRONG_LOOP_FACE                     = (1 << 17),
553                 IS_FACE_NULL_EDGE                           = (1 << 18),
554                 IS_FACE_NULL_VERT                           = (1 << 19),
555                 IS_FACE_LOOP_VERT_NOT_IN_EDGE               = (1 << 20),
556                 IS_FACE_LOOP_WRONG_RADIAL_LENGTH            = (1 << 21),
557                 IS_FACE_LOOP_WRONG_DISK_LENGTH              = (1 << 22),
558                 IS_FACE_LOOP_DUPE_LOOP                      = (1 << 23),
559                 IS_FACE_LOOP_DUPE_VERT                      = (1 << 24),
560                 IS_FACE_LOOP_DUPE_EDGE                      = (1 << 25),
561                 IS_FACE_WRONG_LENGTH                        = (1 << 26),
562         } err = 0;
563
564         if (!element)
565                 return IS_NULL;
566
567         if (head->htype != htype)
568                 return IS_WRONG_TYPE;
569         
570         switch (htype) {
571                 case BM_VERT:
572                 {
573                         BMVert *v = element;
574                         if (v->e && v->e->head.htype != BM_EDGE) {
575                                 err |= IS_VERT_WRONG_EDGE_TYPE;
576                         }
577                         break;
578                 }
579                 case BM_EDGE:
580                 {
581                         BMEdge *e = element;
582                         if (e->v1_disk_link.prev == NULL ||
583                             e->v2_disk_link.prev == NULL ||
584                             e->v1_disk_link.next == NULL ||
585                             e->v2_disk_link.next == NULL)
586                         {
587                                 err |= IS_EDGE_NULL_DISK_LINK;
588                         }
589
590                         if (e->l && e->l->head.htype != BM_LOOP) {
591                                 err |= IS_EDGE_WRONG_LOOP_TYPE;
592                         }
593                         if (e->l && e->l->f->head.htype != BM_FACE) {
594                                 err |= IS_EDGE_WRONG_FACE_TYPE;
595                         }
596                         if (e->l && (e->l->radial_next == NULL || e->l->radial_prev == NULL)) {
597                                 err |= IS_EDGE_NULL_RADIAL_LINK;
598                         }
599                         if (e->l && e->l->f->len <= 0) {
600                                 err |= IS_EDGE_ZERO_FACE_LENGTH;
601                         }
602                         break;
603                 }
604                 case BM_LOOP:
605                 {
606                         BMLoop *l = element, *l2;
607                         int i;
608
609                         if (l->f->head.htype != BM_FACE) {
610                                 err |= IS_LOOP_WRONG_FACE_TYPE;
611                         }
612                         if (l->e->head.htype != BM_EDGE) {
613                                 err |= IS_LOOP_WRONG_EDGE_TYPE;
614                         }
615                         if (l->v->head.htype != BM_VERT) {
616                                 err |= IS_LOOP_WRONG_VERT_TYPE;
617                         }
618                         if (!BM_vert_in_edge(l->e, l->v)) {
619                                 fprintf(stderr, "%s: fatal bmesh error (vert not in edge)! (bmesh internal error)\n", __func__);
620                                 err |= IS_LOOP_VERT_NOT_IN_EDGE;
621                         }
622
623                         if (l->radial_next == NULL || l->radial_prev == NULL) {
624                                 err |= IS_LOOP_NULL_CYCLE_LINK;
625                         }
626                         if (l->f->len <= 0) {
627                                 err |= IS_LOOP_ZERO_FACE_LENGTH;
628                         }
629
630                         /* validate boundary loop -- invalid for hole loops, of course,
631                          * but we won't be allowing those for a while yet */
632                         l2 = l;
633                         i = 0;
634                         do {
635                                 if (i >= BM_NGON_MAX) {
636                                         break;
637                                 }
638
639                                 i++;
640                         } while ((l2 = l2->next) != l);
641
642                         if (i != l->f->len || l2 != l) {
643                                 err |= IS_LOOP_WRONG_FACE_LENGTH;
644                         }
645
646                         if (!bmesh_radial_validate(bmesh_radial_length(l), l)) {
647                                 err |= IS_LOOP_WRONG_RADIAL_LENGTH;
648                         }
649
650                         break;
651                 }
652                 case BM_FACE:
653                 {
654                         BMFace *f = element;
655                         BMLoop *l_iter;
656                         BMLoop *l_first;
657                         int len = 0;
658
659 #ifdef USE_BMESH_HOLES
660                         if (!f->loops.first)
661 #else
662                         if (!f->l_first)
663 #endif
664                         {
665                                 err |= IS_FACE_NULL_LOOP;
666                         }
667                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
668                         do {
669                                 if (l_iter->f != f) {
670                                         fprintf(stderr, "%s: loop inside one face points to another! (bmesh internal error)\n", __func__);
671                                         err |= IS_FACE_WRONG_LOOP_FACE;
672                                 }
673
674                                 if (!l_iter->e) {
675                                         err |= IS_FACE_NULL_EDGE;
676                                 }
677                                 if (!l_iter->v) {
678                                         err |= IS_FACE_NULL_VERT;
679                                 }
680                                 if (l_iter->e && l_iter->v) {
681                                         if (!BM_vert_in_edge(l_iter->e, l_iter->v) ||
682                                             !BM_vert_in_edge(l_iter->e, l_iter->next->v))
683                                         {
684                                                 err |= IS_FACE_LOOP_VERT_NOT_IN_EDGE;
685                                         }
686
687                                         if (!bmesh_radial_validate(bmesh_radial_length(l_iter), l_iter)) {
688                                                 err |= IS_FACE_LOOP_WRONG_RADIAL_LENGTH;
689                                         }
690
691                                         if (bmesh_disk_count_ex(l_iter->v, 2) < 2) {
692                                                 err |= IS_FACE_LOOP_WRONG_DISK_LENGTH;
693                                         }
694                                 }
695
696                                 /* check for duplicates */
697                                 if (BM_ELEM_API_FLAG_TEST(l_iter, _FLAG_ELEM_CHECK)) {
698                                         err |= IS_FACE_LOOP_DUPE_LOOP;
699                                 }
700                                 BM_ELEM_API_FLAG_ENABLE(l_iter, _FLAG_ELEM_CHECK);
701                                 if (l_iter->v) {
702                                         if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_ELEM_CHECK)) {
703                                                 err |= IS_FACE_LOOP_DUPE_VERT;
704                                         }
705                                         BM_ELEM_API_FLAG_ENABLE(l_iter->v, _FLAG_ELEM_CHECK);
706                                 }
707                                 if (l_iter->e) {
708                                         if (BM_ELEM_API_FLAG_TEST(l_iter->e, _FLAG_ELEM_CHECK)) {
709                                                 err |= IS_FACE_LOOP_DUPE_EDGE;
710                                         }
711                                         BM_ELEM_API_FLAG_ENABLE(l_iter->e, _FLAG_ELEM_CHECK);
712                                 }
713
714                                 len++;
715                         } while ((l_iter = l_iter->next) != l_first);
716
717                         /* cleanup duplicates flag */
718                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
719                         do {
720                                 BM_ELEM_API_FLAG_DISABLE(l_iter, _FLAG_ELEM_CHECK);
721                                 if (l_iter->v) {
722                                         BM_ELEM_API_FLAG_DISABLE(l_iter->v, _FLAG_ELEM_CHECK);
723                                 }
724                                 if (l_iter->e) {
725                                         BM_ELEM_API_FLAG_DISABLE(l_iter->e, _FLAG_ELEM_CHECK);
726                                 }
727                         } while ((l_iter = l_iter->next) != l_first);
728
729                         if (len != f->len) {
730                                 err |= IS_FACE_WRONG_LENGTH;
731                         }
732                         break;
733                 }
734                 default:
735                         BLI_assert(0);
736                         break;
737         }
738
739         BMESH_ASSERT(err == 0);
740
741         return err;
742 }
743
744 #endif /* NDEBUG */
745
746 /**
747  * low level function, only frees the vert,
748  * doesn't change or adjust surrounding geometry
749  */
750 static void bm_kill_only_vert(BMesh *bm, BMVert *v)
751 {
752         bm->totvert--;
753         bm->elem_index_dirty |= BM_VERT;
754         bm->elem_table_dirty |= BM_VERT;
755
756         BM_select_history_remove(bm, v);
757
758         if (v->head.data)
759                 CustomData_bmesh_free_block(&bm->vdata, &v->head.data);
760
761         if (bm->vtoolflagpool) {
762                 BLI_mempool_free(bm->vtoolflagpool, ((BMVert_OFlag *)v)->oflags);
763         }
764         BLI_mempool_free(bm->vpool, v);
765 }
766
767 /**
768  * low level function, only frees the edge,
769  * doesn't change or adjust surrounding geometry
770  */
771 static void bm_kill_only_edge(BMesh *bm, BMEdge *e)
772 {
773         bm->totedge--;
774         bm->elem_index_dirty |= BM_EDGE;
775         bm->elem_table_dirty |= BM_EDGE;
776
777         BM_select_history_remove(bm, (BMElem *)e);
778
779         if (e->head.data)
780                 CustomData_bmesh_free_block(&bm->edata, &e->head.data);
781
782         if (bm->etoolflagpool) {
783                 BLI_mempool_free(bm->etoolflagpool, ((BMEdge_OFlag *)e)->oflags);
784         }
785         BLI_mempool_free(bm->epool, e);
786 }
787
788 /**
789  * low level function, only frees the face,
790  * doesn't change or adjust surrounding geometry
791  */
792 static void bm_kill_only_face(BMesh *bm, BMFace *f)
793 {
794         if (bm->act_face == f)
795                 bm->act_face = NULL;
796
797         bm->totface--;
798         bm->elem_index_dirty |= BM_FACE;
799         bm->elem_table_dirty |= BM_FACE;
800
801         BM_select_history_remove(bm, (BMElem *)f);
802
803         if (f->head.data)
804                 CustomData_bmesh_free_block(&bm->pdata, &f->head.data);
805
806         if (bm->ftoolflagpool) {
807                 BLI_mempool_free(bm->ftoolflagpool, ((BMFace_OFlag *)f)->oflags);
808         }
809         BLI_mempool_free(bm->fpool, f);
810 }
811
812 /**
813  * low level function, only frees the loop,
814  * doesn't change or adjust surrounding geometry
815  */
816 static void bm_kill_only_loop(BMesh *bm, BMLoop *l)
817 {
818         bm->totloop--;
819         bm->elem_index_dirty |= BM_LOOP;
820         if (l->head.data)
821                 CustomData_bmesh_free_block(&bm->ldata, &l->head.data);
822
823         BLI_mempool_free(bm->lpool, l);
824 }
825
826 /**
827  * kills all edges associated with \a f, along with any other faces containing
828  * those edges
829  */
830 void BM_face_edges_kill(BMesh *bm, BMFace *f)
831 {
832         BMEdge **edges = BLI_array_alloca(edges, f->len);
833         BMLoop *l_iter;
834         BMLoop *l_first;
835         int i = 0;
836         
837         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
838         do {
839                 edges[i++] = l_iter->e;
840         } while ((l_iter = l_iter->next) != l_first);
841         
842         for (i = 0; i < f->len; i++) {
843                 BM_edge_kill(bm, edges[i]);
844         }
845 }
846
847 /**
848  * kills all verts associated with \a f, along with any other faces containing
849  * those vertices
850  */
851 void BM_face_verts_kill(BMesh *bm, BMFace *f)
852 {
853         BMVert **verts = BLI_array_alloca(verts, f->len);
854         BMLoop *l_iter;
855         BMLoop *l_first;
856         int i = 0;
857         
858         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
859         do {
860                 verts[i++] = l_iter->v;
861         } while ((l_iter = l_iter->next) != l_first);
862         
863         for (i = 0; i < f->len; i++) {
864                 BM_vert_kill(bm, verts[i]);
865         }
866 }
867
868 /**
869  * Kills \a f and its loops.
870  */
871 void BM_face_kill(BMesh *bm, BMFace *f)
872 {
873 #ifdef USE_BMESH_HOLES
874         BMLoopList *ls, *ls_next;
875 #endif
876
877 #ifdef NDEBUG
878         /* check length since we may be removing degenerate faces */
879         if (f->len >= 3) {
880                 BM_CHECK_ELEMENT(f);
881         }
882 #endif
883
884 #ifdef USE_BMESH_HOLES
885         for (ls = f->loops.first; ls; ls = ls_next)
886 #else
887         if (f->l_first)
888 #endif
889         {
890                 BMLoop *l_iter, *l_next, *l_first;
891
892 #ifdef USE_BMESH_HOLES
893                 ls_next = ls->next;
894                 l_iter = l_first = ls->first;
895 #else
896                 l_iter = l_first = f->l_first;
897 #endif
898
899                 do {
900                         l_next = l_iter->next;
901
902                         bmesh_radial_loop_remove(l_iter->e, l_iter);
903                         bm_kill_only_loop(bm, l_iter);
904
905                 } while ((l_iter = l_next) != l_first);
906
907 #ifdef USE_BMESH_HOLES
908                 BLI_mempool_free(bm->looplistpool, ls);
909 #endif
910         }
911
912         bm_kill_only_face(bm, f);
913 }
914
915 /**
916  * A version of #BM_face_kill which removes edges and verts
917  * which have no remaining connected geometry.
918  */
919 void BM_face_kill_loose(BMesh *bm, BMFace *f)
920 {
921 #ifdef USE_BMESH_HOLES
922         BMLoopList *ls, *ls_next;
923 #endif
924
925         BM_CHECK_ELEMENT(f);
926
927 #ifdef USE_BMESH_HOLES
928         for (ls = f->loops.first; ls; ls = ls_next)
929 #else
930         if (f->l_first)
931 #endif
932         {
933                 BMLoop *l_iter, *l_next, *l_first;
934
935 #ifdef USE_BMESH_HOLES
936                 ls_next = ls->next;
937                 l_iter = l_first = ls->first;
938 #else
939                 l_iter = l_first = f->l_first;
940 #endif
941
942                 do {
943                         BMEdge *e;
944                         l_next = l_iter->next;
945
946                         e = l_iter->e;
947                         bmesh_radial_loop_remove(e, l_iter);
948                         bm_kill_only_loop(bm, l_iter);
949
950                         if (e->l == NULL) {
951                                 BMVert *v1 = e->v1, *v2 = e->v2;
952
953                                 bmesh_disk_edge_remove(e, e->v1);
954                                 bmesh_disk_edge_remove(e, e->v2);
955                                 bm_kill_only_edge(bm, e);
956
957                                 if (v1->e == NULL) {
958                                         bm_kill_only_vert(bm, v1);
959                                 }
960                                 if (v2->e == NULL) {
961                                         bm_kill_only_vert(bm, v2);
962                                 }
963                         }
964                 } while ((l_iter = l_next) != l_first);
965
966 #ifdef USE_BMESH_HOLES
967                 BLI_mempool_free(bm->looplistpool, ls);
968 #endif
969         }
970
971         bm_kill_only_face(bm, f);
972 }
973
974 /**
975  * kills \a e and all faces that use it.
976  */
977 void BM_edge_kill(BMesh *bm, BMEdge *e)
978 {
979         while (e->l) {
980                 BM_face_kill(bm, e->l->f);
981         }
982
983         bmesh_disk_edge_remove(e, e->v1);
984         bmesh_disk_edge_remove(e, e->v2);
985         
986         bm_kill_only_edge(bm, e);
987 }
988
989 /**
990  * kills \a v and all edges that use it.
991  */
992 void BM_vert_kill(BMesh *bm, BMVert *v)
993 {
994         while (v->e) {
995                 BM_edge_kill(bm, v->e);
996         }
997
998         bm_kill_only_vert(bm, v);
999 }
1000
1001 /********** private disk and radial cycle functions ********** */
1002
1003 /**
1004  * return the length of the face, should always equal \a l->f->len
1005  */
1006 static int UNUSED_FUNCTION(bm_loop_length)(BMLoop *l)
1007 {
1008         BMLoop *l_first = l;
1009         int i = 0;
1010
1011         do {
1012                 i++;
1013         } while ((l = l->next) != l_first);
1014
1015         return i;
1016 }
1017
1018 /**
1019  * \brief Loop Reverse
1020  *
1021  * Changes the winding order of a face from CW to CCW or vice versa.
1022  *
1023  * \param cd_loop_mdisp_offset: Cached result of `CustomData_get_offset(&bm->ldata, CD_MDISPS)`.
1024  * \param use_loop_mdisp_flip: When set, flip the Z-depth of the mdisp,
1025  * (use when flipping normals, disable when mirroring, eg: symmetrize).
1026  */
1027 static void bm_loop_reverse_loop(
1028         BMesh *bm, BMFace *f,
1029 #ifdef USE_BMESH_HOLES
1030         BMLoopList *lst,
1031 #endif
1032         const int cd_loop_mdisp_offset, const bool use_loop_mdisp_flip)
1033 {
1034
1035 #ifdef USE_BMESH_HOLES
1036         BMLoop *l_first = lst->first;
1037 #else
1038         BMLoop *l_first = f->l_first;
1039 #endif
1040
1041         /* track previous cycles radial state */
1042         BMEdge *e_prev = l_first->prev->e;
1043         BMLoop *l_prev_radial_next = l_first->prev->radial_next;
1044         BMLoop *l_prev_radial_prev = l_first->prev->radial_prev;
1045         bool is_prev_boundary = l_prev_radial_next == l_prev_radial_next->radial_next;
1046
1047         BMLoop *l_iter = l_first;
1048         do {
1049                 BMEdge *e_iter = l_iter->e;
1050                 BMLoop *l_iter_radial_next = l_iter->radial_next;
1051                 BMLoop *l_iter_radial_prev = l_iter->radial_prev;
1052                 bool is_iter_boundary = l_iter_radial_next == l_iter_radial_next->radial_next;
1053
1054 #if 0
1055                 bmesh_radial_loop_remove(e_curr, l_iter);
1056                 bmesh_radial_loop_append(e_prev, l_iter);
1057 #else
1058                 /* inline loop reversal */
1059                 if (is_prev_boundary) {
1060                         /* boundary */
1061                         l_iter->radial_next = l_iter;
1062                         l_iter->radial_prev = l_iter;
1063                 }
1064                 else {
1065                         /* non-boundary, replace radial links */
1066                         l_iter->radial_next = l_prev_radial_next;
1067                         l_iter->radial_prev = l_prev_radial_prev;
1068                         l_prev_radial_next->radial_prev = l_iter;
1069                         l_prev_radial_prev->radial_next = l_iter;
1070                 }
1071
1072                 if (e_iter->l == l_iter) {
1073                         e_iter->l = l_iter->next;
1074                 }
1075                 l_iter->e = e_prev;
1076 #endif
1077
1078                 SWAP(BMLoop *, l_iter->next, l_iter->prev);
1079
1080                 if (cd_loop_mdisp_offset != -1) {
1081                         MDisps *md = BM_ELEM_CD_GET_VOID_P(l_iter, cd_loop_mdisp_offset);
1082                         BKE_mesh_mdisp_flip(md, use_loop_mdisp_flip);
1083                 }
1084
1085                 e_prev = e_iter;
1086                 l_prev_radial_next = l_iter_radial_next;
1087                 l_prev_radial_prev = l_iter_radial_prev;
1088                 is_prev_boundary = is_iter_boundary;
1089
1090                 /* step to next (now swapped) */
1091         } while ((l_iter = l_iter->prev) != l_first);
1092
1093 #ifndef NDEBUG
1094         /* validate radial */
1095         int i;
1096         for (i = 0, l_iter = l_first; i < f->len; i++, l_iter = l_iter->next) {
1097                 BM_CHECK_ELEMENT(l_iter);
1098                 BM_CHECK_ELEMENT(l_iter->e);
1099                 BM_CHECK_ELEMENT(l_iter->v);
1100                 BM_CHECK_ELEMENT(l_iter->f);
1101         }
1102
1103         BM_CHECK_ELEMENT(f);
1104 #endif
1105
1106         /* Loop indices are no more valid! */
1107         bm->elem_index_dirty |= BM_LOOP;
1108 }
1109
1110 /**
1111  * \brief Flip the faces direction
1112  */
1113 void bmesh_loop_reverse(
1114         BMesh *bm, BMFace *f,
1115         const int cd_loop_mdisp_offset, const bool use_loop_mdisp_flip)
1116 {
1117 #ifdef USE_BMESH_HOLES
1118         bm_loop_reverse_loop(bm, f, f->loops.first, cd_loop_mdisp_offset, use_loop_mdisp_flip);
1119 #else
1120         bm_loop_reverse_loop(bm, f, cd_loop_mdisp_offset, use_loop_mdisp_flip);
1121 #endif
1122 }
1123
1124 static void bm_elements_systag_enable(void *veles, int tot, const char api_flag)
1125 {
1126         BMHeader **eles = veles;
1127         int i;
1128
1129         for (i = 0; i < tot; i++) {
1130                 BM_ELEM_API_FLAG_ENABLE((BMElemF *)eles[i], api_flag);
1131         }
1132 }
1133
1134 static void bm_elements_systag_disable(void *veles, int tot, const char api_flag)
1135 {
1136         BMHeader **eles = veles;
1137         int i;
1138
1139         for (i = 0; i < tot; i++) {
1140                 BM_ELEM_API_FLAG_DISABLE((BMElemF *)eles[i], api_flag);
1141         }
1142 }
1143
1144 static int bm_loop_systag_count_radial(BMLoop *l, const char api_flag)
1145 {
1146         BMLoop *l_iter = l;
1147         int i = 0;
1148         do {
1149                 i += BM_ELEM_API_FLAG_TEST(l_iter->f, api_flag) ? 1 : 0;
1150         } while ((l_iter = l_iter->radial_next) != l);
1151
1152         return i;
1153 }
1154
1155 static int UNUSED_FUNCTION(bm_vert_systag_count_disk)(BMVert *v, const char api_flag)
1156 {
1157         BMEdge *e = v->e;
1158         int i = 0;
1159
1160         if (!e)
1161                 return 0;
1162
1163         do {
1164                 i += BM_ELEM_API_FLAG_TEST(e, api_flag) ? 1 : 0;
1165         } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
1166
1167         return i;
1168 }
1169
1170 /**
1171  * Return true when the vertex is manifold,
1172  * attached to faces which are all flagged.
1173  */
1174 static bool bm_vert_is_manifold_flagged(BMVert *v, const char api_flag)
1175 {
1176         BMEdge *e = v->e;
1177
1178         if (!e)
1179                 return false;
1180
1181         do {
1182                 BMLoop *l = e->l;
1183
1184                 if (!l) {
1185                         return false;
1186                 }
1187                 
1188                 if (BM_edge_is_boundary(l->e)) {
1189                         return false;
1190                 }
1191                 
1192                 do {
1193                         if (!BM_ELEM_API_FLAG_TEST(l->f, api_flag))
1194                                 return false;
1195                 } while ((l = l->radial_next) != e->l);
1196         } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
1197
1198         return true;
1199 }
1200
1201 /* Mid-level Topology Manipulation Functions */
1202
1203 /**
1204  * \brief Join Connected Faces
1205  *
1206  * Joins a collected group of faces into one. Only restriction on
1207  * the input data is that the faces must be connected to each other.
1208  *
1209  * \return The newly created combine BMFace.
1210  *
1211  * \note If a pair of faces share multiple edges,
1212  * the pair of faces will be joined at every edge.
1213  *
1214  * \note this is a generic, flexible join faces function,
1215  * almost everything uses this, including #BM_faces_join_pair
1216  */
1217 BMFace *BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del)
1218 {
1219         BMFace *f, *f_new;
1220 #ifdef USE_BMESH_HOLES
1221         BMLoopList *lst;
1222         ListBase holes = {NULL, NULL};
1223 #endif
1224         BMLoop *l_iter;
1225         BMLoop *l_first;
1226         BMEdge **edges = NULL;
1227         BMEdge **deledges = NULL;
1228         BMVert **delverts = NULL;
1229         BLI_array_staticdeclare(edges,    BM_DEFAULT_NGON_STACK_SIZE);
1230         BLI_array_staticdeclare(deledges, BM_DEFAULT_NGON_STACK_SIZE);
1231         BLI_array_staticdeclare(delverts, BM_DEFAULT_NGON_STACK_SIZE);
1232         BMVert *v1 = NULL, *v2 = NULL;
1233         int i;
1234         const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
1235
1236         if (UNLIKELY(!totface)) {
1237                 BMESH_ASSERT(0);
1238                 return NULL;
1239         }
1240
1241         if (totface == 1)
1242                 return faces[0];
1243
1244         bm_elements_systag_enable(faces, totface, _FLAG_JF);
1245
1246         for (i = 0; i < totface; i++) {
1247                 f = faces[i];
1248                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1249                 do {
1250                         int rlen = bm_loop_systag_count_radial(l_iter, _FLAG_JF);
1251
1252                         if (rlen > 2) {
1253                                 /* Input faces do not form a contiguous manifold region */
1254                                 goto error;
1255                         }
1256                         else if (rlen == 1) {
1257                                 BLI_array_append(edges, l_iter->e);
1258
1259                                 if (!v1) {
1260                                         v1 = l_iter->v;
1261                                         v2 = BM_edge_other_vert(l_iter->e, l_iter->v);
1262                                 }
1263                         }
1264                         else if (rlen == 2) {
1265                                 const bool d1 = bm_vert_is_manifold_flagged(l_iter->e->v1, _FLAG_JF);
1266                                 const bool d2 = bm_vert_is_manifold_flagged(l_iter->e->v2, _FLAG_JF);
1267
1268                                 if (!d1 && !d2 && !BM_ELEM_API_FLAG_TEST(l_iter->e, _FLAG_JF)) {
1269                                         /* don't remove an edge it makes up the side of another face
1270                                          * else this will remove the face as well - campbell */
1271                                         if (!BM_edge_face_count_is_over(l_iter->e, 2)) {
1272                                                 if (do_del) {
1273                                                         BLI_array_append(deledges, l_iter->e);
1274                                                 }
1275                                                 BM_ELEM_API_FLAG_ENABLE(l_iter->e, _FLAG_JF);
1276                                         }
1277                                 }
1278                                 else {
1279                                         if (d1 && !BM_ELEM_API_FLAG_TEST(l_iter->e->v1, _FLAG_JF)) {
1280                                                 if (do_del) {
1281                                                         BLI_array_append(delverts, l_iter->e->v1);
1282                                                 }
1283                                                 BM_ELEM_API_FLAG_ENABLE(l_iter->e->v1, _FLAG_JF);
1284                                         }
1285
1286                                         if (d2 && !BM_ELEM_API_FLAG_TEST(l_iter->e->v2, _FLAG_JF)) {
1287                                                 if (do_del) {
1288                                                         BLI_array_append(delverts, l_iter->e->v2);
1289                                                 }
1290                                                 BM_ELEM_API_FLAG_ENABLE(l_iter->e->v2, _FLAG_JF);
1291                                         }
1292                                 }
1293                         }
1294                 } while ((l_iter = l_iter->next) != l_first);
1295
1296 #ifdef USE_BMESH_HOLES
1297                 for (lst = f->loops.first; lst; lst = lst->next) {
1298                         if (lst == f->loops.first) {
1299                                 continue;
1300                         }
1301
1302                         BLI_remlink(&f->loops, lst);
1303                         BLI_addtail(&holes, lst);
1304                 }
1305 #endif
1306
1307         }
1308
1309         /* create region face */
1310         f_new = BLI_array_count(edges) ?
1311                 BM_face_create_ngon(bm, v1, v2, edges, BLI_array_count(edges), faces[0], BM_CREATE_NOP) : NULL;
1312         if (UNLIKELY(f_new == NULL)) {
1313                 /* Invalid boundary region to join faces */
1314                 goto error;
1315         }
1316
1317         /* copy over loop data */
1318         l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
1319         do {
1320                 BMLoop *l2 = l_iter->radial_next;
1321
1322                 do {
1323                         if (BM_ELEM_API_FLAG_TEST(l2->f, _FLAG_JF))
1324                                 break;
1325                         l2 = l2->radial_next;
1326                 } while (l2 != l_iter);
1327
1328                 if (l2 != l_iter) {
1329                         /* loops share an edge, shared vert depends on winding */
1330                         if (l2->v != l_iter->v) {
1331                                 l2 = l2->next;
1332                         }
1333                         BLI_assert(l_iter->v == l2->v);
1334
1335                         BM_elem_attrs_copy(bm, bm, l2, l_iter);
1336                 }
1337         } while ((l_iter = l_iter->next) != l_first);
1338
1339 #ifdef USE_BMESH_HOLES
1340         /* add holes */
1341         BLI_movelisttolist(&f_new->loops, &holes);
1342 #endif
1343
1344         /* update loop face pointer */
1345 #ifdef USE_BMESH_HOLES
1346         for (lst = f_new->loops.first; lst; lst = lst->next)
1347 #endif
1348         {
1349 #ifdef USE_BMESH_HOLES
1350                 l_iter = l_first = lst->first;
1351 #else
1352                 l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
1353 #endif
1354                 do {
1355                         l_iter->f = f_new;
1356                 } while ((l_iter = l_iter->next) != l_first);
1357         }
1358
1359         bm_elements_systag_disable(faces, totface, _FLAG_JF);
1360         BM_ELEM_API_FLAG_DISABLE(f_new, _FLAG_JF);
1361
1362         /* handle multi-res data */
1363         if (cd_loop_mdisp_offset != -1) {
1364                 float f_center[3];
1365                 float (*faces_center)[3] = BLI_array_alloca(faces_center, totface);
1366
1367                 BM_face_calc_center_mean(f_new, f_center);
1368                 for (i = 0; i < totface; i++) {
1369                         BM_face_calc_center_mean(faces[i], faces_center[i]);
1370                 }
1371
1372                 l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
1373                 do {
1374                         for (i = 0; i < totface; i++) {
1375                                 BM_loop_interp_multires_ex(bm, l_iter, faces[i], f_center, faces_center[i], cd_loop_mdisp_offset);
1376                         }
1377                 } while ((l_iter = l_iter->next) != l_first);
1378         }
1379
1380         /* delete old geometry */
1381         if (do_del) {
1382                 for (i = 0; i < BLI_array_count(deledges); i++) {
1383                         BM_edge_kill(bm, deledges[i]);
1384                 }
1385
1386                 for (i = 0; i < BLI_array_count(delverts); i++) {
1387                         BM_vert_kill(bm, delverts[i]);
1388                 }
1389         }
1390         else {
1391                 /* otherwise we get both old and new faces */
1392                 for (i = 0; i < totface; i++) {
1393                         BM_face_kill(bm, faces[i]);
1394                 }
1395         }
1396         
1397         BLI_array_free(edges);
1398         BLI_array_free(deledges);
1399         BLI_array_free(delverts);
1400
1401         BM_CHECK_ELEMENT(f_new);
1402         return f_new;
1403
1404 error:
1405         bm_elements_systag_disable(faces, totface, _FLAG_JF);
1406         BLI_array_free(edges);
1407         BLI_array_free(deledges);
1408         BLI_array_free(delverts);
1409
1410         return NULL;
1411 }
1412
1413 static BMFace *bm_face_create__sfme(BMesh *bm, BMFace *f_example)
1414 {
1415         BMFace *f;
1416 #ifdef USE_BMESH_HOLES
1417         BMLoopList *lst;
1418 #endif
1419
1420         f = bm_face_create__internal(bm);
1421
1422 #ifdef USE_BMESH_HOLES
1423         lst = BLI_mempool_calloc(bm->looplistpool);
1424         BLI_addtail(&f->loops, lst);
1425 #endif
1426
1427 #ifdef USE_BMESH_HOLES
1428         f->totbounds = 1;
1429 #endif
1430
1431         BM_elem_attrs_copy(bm, bm, f_example, f);
1432
1433         return f;
1434 }
1435
1436 /**
1437  * \brief Split Face Make Edge (SFME)
1438  *
1439  * \warning this is a low level function, most likely you want to use #BM_face_split()
1440  *
1441  * Takes as input two vertices in a single face. An edge is created which divides the original face
1442  * into two distinct regions. One of the regions is assigned to the original face and it is closed off.
1443  * The second region has a new face assigned to it.
1444  *
1445  * \par Examples:
1446  * <pre>
1447  *     Before:               After:
1448  *      +--------+           +--------+
1449  *      |        |           |        |
1450  *      |        |           |   f1   |
1451  *     v1   f1   v2          v1======v2
1452  *      |        |           |   f2   |
1453  *      |        |           |        |
1454  *      +--------+           +--------+
1455  * </pre>
1456  *
1457  * \note the input vertices can be part of the same edge. This will
1458  * result in a two edged face. This is desirable for advanced construction
1459  * tools and particularly essential for edge bevel. Because of this it is
1460  * up to the caller to decide what to do with the extra edge.
1461  *
1462  * \note If \a holes is NULL, then both faces will lose
1463  * all holes from the original face.  Also, you cannot split between
1464  * a hole vert and a boundary vert; that case is handled by higher-
1465  * level wrapping functions (when holes are fully implemented, anyway).
1466  *
1467  * \note that holes represents which holes goes to the new face, and of
1468  * course this requires removing them from the existing face first, since
1469  * you cannot have linked list links inside multiple lists.
1470  *
1471  * \return A BMFace pointer
1472  */
1473 BMFace *bmesh_sfme(
1474         BMesh *bm, BMFace *f, BMLoop *l_v1, BMLoop *l_v2,
1475         BMLoop **r_l,
1476 #ifdef USE_BMESH_HOLES
1477         ListBase *holes,
1478 #endif
1479         BMEdge *e_example,
1480         const bool no_double)
1481 {
1482 #ifdef USE_BMESH_HOLES
1483         BMLoopList *lst, *lst2;
1484 #else
1485         int first_loop_f1;
1486 #endif
1487
1488         BMFace *f2;
1489         BMLoop *l_iter, *l_first;
1490         BMLoop *l_f1 = NULL, *l_f2 = NULL;
1491         BMEdge *e;
1492         BMVert *v1 = l_v1->v, *v2 = l_v2->v;
1493         int f1len, f2len;
1494
1495         BLI_assert(f == l_v1->f && f == l_v2->f);
1496
1497         /* allocate new edge between v1 and v2 */
1498         e = BM_edge_create(bm, v1, v2, e_example, no_double ? BM_CREATE_NO_DOUBLE : BM_CREATE_NOP);
1499
1500         f2 = bm_face_create__sfme(bm, f);
1501         l_f1 = bm_loop_create(bm, v2, e, f, l_v2, 0);
1502         l_f2 = bm_loop_create(bm, v1, e, f2, l_v1, 0);
1503
1504         l_f1->prev = l_v2->prev;
1505         l_f2->prev = l_v1->prev;
1506         l_v2->prev->next = l_f1;
1507         l_v1->prev->next = l_f2;
1508
1509         l_f1->next = l_v1;
1510         l_f2->next = l_v2;
1511         l_v1->prev = l_f1;
1512         l_v2->prev = l_f2;
1513
1514 #ifdef USE_BMESH_HOLES
1515         lst = f->loops.first;
1516         lst2 = f2->loops.first;
1517
1518         lst2->first = lst2->last = l_f2;
1519         lst->first = lst->last = l_f1;
1520 #else
1521         /* find which of the faces the original first loop is in */
1522         l_iter = l_first = l_f1;
1523         first_loop_f1 = 0;
1524         do {
1525                 if (l_iter == f->l_first)
1526                         first_loop_f1 = 1;
1527         } while ((l_iter = l_iter->next) != l_first);
1528
1529         if (first_loop_f1) {
1530                 /* original first loop was in f1, find a suitable first loop for f2
1531                  * which is as similar as possible to f1. the order matters for tools
1532                  * such as duplifaces. */
1533                 if (f->l_first->prev == l_f1)
1534                         f2->l_first = l_f2->prev;
1535                 else if (f->l_first->next == l_f1)
1536                         f2->l_first = l_f2->next;
1537                 else
1538                         f2->l_first = l_f2;
1539         }
1540         else {
1541                 /* original first loop was in f2, further do same as above */
1542                 f2->l_first = f->l_first;
1543
1544                 if (f->l_first->prev == l_f2)
1545                         f->l_first = l_f1->prev;
1546                 else if (f->l_first->next == l_f2)
1547                         f->l_first = l_f1->next;
1548                 else
1549                         f->l_first = l_f1;
1550         }
1551 #endif
1552
1553         /* validate both loop */
1554         /* I don't know how many loops are supposed to be in each face at this point! FIXME */
1555
1556         /* go through all of f2's loops and make sure they point to it properly */
1557         l_iter = l_first = BM_FACE_FIRST_LOOP(f2);
1558         f2len = 0;
1559         do {
1560                 l_iter->f = f2;
1561                 f2len++;
1562         } while ((l_iter = l_iter->next) != l_first);
1563
1564         /* link up the new loops into the new edges radial */
1565         bmesh_radial_loop_append(e, l_f1);
1566         bmesh_radial_loop_append(e, l_f2);
1567
1568         f2->len = f2len;
1569
1570         f1len = 0;
1571         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1572         do {
1573                 f1len++;
1574         } while ((l_iter = l_iter->next) != l_first);
1575
1576         f->len = f1len;
1577
1578         if (r_l) *r_l = l_f2;
1579
1580 #ifdef USE_BMESH_HOLES
1581         if (holes) {
1582                 BLI_movelisttolist(&f2->loops, holes);
1583         }
1584         else {
1585                 /* this code is not significant until holes actually work */
1586                 //printf("warning: call to split face euler without holes argument; holes will be tossed.\n");
1587                 for (lst = f->loops.last; lst != f->loops.first; lst = lst2) {
1588                         lst2 = lst->prev;
1589                         BLI_mempool_free(bm->looplistpool, lst);
1590                 }
1591         }
1592 #endif
1593
1594         BM_CHECK_ELEMENT(e);
1595         BM_CHECK_ELEMENT(f);
1596         BM_CHECK_ELEMENT(f2);
1597         
1598         return f2;
1599 }
1600
1601 /**
1602  * \brief Split Edge Make Vert (SEMV)
1603  *
1604  * Takes \a e edge and splits it into two, creating a new vert.
1605  * \a tv should be one end of \a e : the newly created edge
1606  * will be attached to that end and is returned in \a r_e.
1607  *
1608  * \par Examples:
1609  *
1610  * <pre>
1611  *                     E
1612  *     Before: OV-------------TV
1613  *                 E       RE
1614  *     After:  OV------NV-----TV
1615  * </pre>
1616  *
1617  * \return The newly created BMVert pointer.
1618  */
1619 BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **r_e)
1620 {
1621         BMLoop *l_next;
1622         BMEdge *e_new;
1623         BMVert *v_new, *v_old;
1624 #ifndef NDEBUG
1625         int valence1, valence2;
1626         bool edok;
1627         int i;
1628 #endif
1629
1630         BLI_assert(BM_vert_in_edge(e, tv) != false);
1631
1632         v_old = BM_edge_other_vert(e, tv);
1633
1634 #ifndef NDEBUG
1635         valence1 = bmesh_disk_count(v_old);
1636         valence2 = bmesh_disk_count(tv);
1637 #endif
1638
1639         /* order of 'e_new' verts should match 'e'
1640          * (so extruded faces don't flip) */
1641         v_new = BM_vert_create(bm, tv->co, tv, BM_CREATE_NOP);
1642         e_new = BM_edge_create(bm, tv, v_new, e, BM_CREATE_NOP);
1643
1644         bmesh_disk_edge_remove(e_new, tv);
1645         bmesh_disk_edge_remove(e_new, v_new);
1646
1647         bmesh_disk_vert_replace(e, v_new, tv);
1648
1649         /* add e_new to v_new's disk cycle */
1650         bmesh_disk_edge_append(e_new, v_new);
1651
1652         /* add e_new to tv's disk cycle */
1653         bmesh_disk_edge_append(e_new, tv);
1654
1655 #ifndef NDEBUG
1656         /* verify disk cycles */
1657         edok = bmesh_disk_validate(valence1, v_old->e, v_old);
1658         BMESH_ASSERT(edok != false);
1659         edok = bmesh_disk_validate(valence2, tv->e, tv);
1660         BMESH_ASSERT(edok != false);
1661         edok = bmesh_disk_validate(2, v_new->e, v_new);
1662         BMESH_ASSERT(edok != false);
1663 #endif
1664
1665         /* Split the radial cycle if present */
1666         l_next = e->l;
1667         e->l = NULL;
1668         if (l_next) {
1669                 BMLoop *l_new, *l;
1670 #ifndef NDEBUG
1671                 int radlen = bmesh_radial_length(l_next);
1672 #endif
1673                 bool is_first = true;
1674
1675                 /* Take the next loop. Remove it from radial. Split it. Append to appropriate radials */
1676                 while (l_next) {
1677                         l = l_next;
1678                         l->f->len++;
1679                         l_next = l_next != l_next->radial_next ? l_next->radial_next : NULL;
1680                         bmesh_radial_loop_unlink(l);
1681
1682                         l_new = bm_loop_create(bm, NULL, NULL, l->f, l, 0);
1683                         l_new->prev = l;
1684                         l_new->next = l->next;
1685                         l_new->prev->next = l_new;
1686                         l_new->next->prev = l_new;
1687                         l_new->v = v_new;
1688
1689                         /* assign the correct edge to the correct loop */
1690                         if (BM_verts_in_edge(l_new->v, l_new->next->v, e)) {
1691                                 l_new->e = e;
1692                                 l->e = e_new;
1693
1694                                 /* append l into e_new's rad cycle */
1695                                 if (is_first) {
1696                                         is_first = false;
1697                                         l->radial_next = l->radial_prev = NULL;
1698                                 }
1699                                 
1700                                 bmesh_radial_loop_append(l_new->e, l_new);
1701                                 bmesh_radial_loop_append(l->e, l);
1702                         }
1703                         else if (BM_verts_in_edge(l_new->v, l_new->next->v, e_new)) {
1704                                 l_new->e = e_new;
1705                                 l->e = e;
1706
1707                                 /* append l into e_new's rad cycle */
1708                                 if (is_first) {
1709                                         is_first = false;
1710                                         l->radial_next = l->radial_prev = NULL;
1711                                 }
1712
1713                                 bmesh_radial_loop_append(l_new->e, l_new);
1714                                 bmesh_radial_loop_append(l->e, l);
1715                         }
1716
1717                 }
1718
1719 #ifndef NDEBUG
1720                 /* verify length of radial cycle */
1721                 edok = bmesh_radial_validate(radlen, e->l);
1722                 BMESH_ASSERT(edok != false);
1723                 edok = bmesh_radial_validate(radlen, e_new->l);
1724                 BMESH_ASSERT(edok != false);
1725
1726                 /* verify loop->v and loop->next->v pointers for e */
1727                 for (i = 0, l = e->l; i < radlen; i++, l = l->radial_next) {
1728                         BMESH_ASSERT(l->e == e);
1729                         //BMESH_ASSERT(l->radial_next == l);
1730                         BMESH_ASSERT(!(l->prev->e != e_new && l->next->e != e_new));
1731
1732                         edok = BM_verts_in_edge(l->v, l->next->v, e);
1733                         BMESH_ASSERT(edok != false);
1734                         BMESH_ASSERT(l->v != l->next->v);
1735                         BMESH_ASSERT(l->e != l->next->e);
1736
1737                         /* verify loop cycle for kloop->f */
1738                         BM_CHECK_ELEMENT(l);
1739                         BM_CHECK_ELEMENT(l->v);
1740                         BM_CHECK_ELEMENT(l->e);
1741                         BM_CHECK_ELEMENT(l->f);
1742                 }
1743                 /* verify loop->v and loop->next->v pointers for e_new */
1744                 for (i = 0, l = e_new->l; i < radlen; i++, l = l->radial_next) {
1745                         BMESH_ASSERT(l->e == e_new);
1746                         // BMESH_ASSERT(l->radial_next == l);
1747                         BMESH_ASSERT(!(l->prev->e != e && l->next->e != e));
1748                         edok = BM_verts_in_edge(l->v, l->next->v, e_new);
1749                         BMESH_ASSERT(edok != false);
1750                         BMESH_ASSERT(l->v != l->next->v);
1751                         BMESH_ASSERT(l->e != l->next->e);
1752
1753                         BM_CHECK_ELEMENT(l);
1754                         BM_CHECK_ELEMENT(l->v);
1755                         BM_CHECK_ELEMENT(l->e);
1756                         BM_CHECK_ELEMENT(l->f);
1757                 }
1758 #endif
1759         }
1760
1761         BM_CHECK_ELEMENT(e_new);
1762         BM_CHECK_ELEMENT(v_new);
1763         BM_CHECK_ELEMENT(v_old);
1764         BM_CHECK_ELEMENT(e);
1765         BM_CHECK_ELEMENT(tv);
1766
1767         if (r_e) *r_e = e_new;
1768         return v_new;
1769 }
1770
1771 /**
1772  * \brief Join Edge Kill Vert (JEKV)
1773  *
1774  * Takes an edge \a e_kill and pointer to one of its vertices \a v_kill
1775  * and collapses the edge on that vertex.
1776  *
1777  * \par Examples:
1778  *
1779  * <pre>
1780  *     Before:    e_old  e_kill
1781  *              +-------+-------+
1782  *              |       |       |
1783  *              v_old   v_kill  v_target
1784  *
1785  *     After:           e_old
1786  *              +---------------+
1787  *              |               |
1788  *              v_old           v_target
1789  * </pre>
1790  *
1791  * \par Restrictions:
1792  * KV is a vertex that must have a valance of exactly two. Furthermore
1793  * both edges in KV's disk cycle (OE and KE) must be unique (no double edges).
1794  *
1795  * \return The resulting edge, NULL for failure.
1796  *
1797  * \note This euler has the possibility of creating
1798  * faces with just 2 edges. It is up to the caller to decide what to do with
1799  * these faces.
1800  */
1801 BMEdge *bmesh_jekv(
1802         BMesh *bm, BMEdge *e_kill, BMVert *v_kill,
1803         const bool do_del, const bool check_edge_double,
1804         const bool kill_degenerate_faces)
1805 {
1806         BMEdge *e_old;
1807         BMVert *v_old, *v_target;
1808         BMLoop *l_kill;
1809 #ifndef NDEBUG
1810         int radlen, i;
1811         bool edok;
1812 #endif
1813
1814         BLI_assert(BM_vert_in_edge(e_kill, v_kill));
1815
1816         if (BM_vert_in_edge(e_kill, v_kill) == 0) {
1817                 return NULL;
1818         }
1819         
1820         if (bmesh_disk_count_ex(v_kill, 3) == 2) {
1821 #ifndef NDEBUG
1822                 int valence1, valence2;
1823                 BMLoop *l;
1824 #endif
1825
1826                 e_old = bmesh_disk_edge_next(e_kill, v_kill);
1827                 v_target = BM_edge_other_vert(e_kill, v_kill);
1828                 v_old = BM_edge_other_vert(e_old, v_kill);
1829
1830                 /* check for double edges */
1831                 if (BM_verts_in_edge(v_kill, v_target, e_old)) {
1832                         return NULL;
1833                 }
1834                 else {
1835                         BMEdge *e_splice;
1836                         BLI_SMALLSTACK_DECLARE(faces_degenerate, BMFace *);
1837                         BMLoop *l_kill_next;
1838
1839 #ifndef NDEBUG
1840                         /* For verification later, count valence of 'v_old' and 'v_target' */
1841                         valence1 = bmesh_disk_count(v_old);
1842                         valence2 = bmesh_disk_count(v_target);
1843 #endif
1844
1845                         if (check_edge_double) {
1846                                 e_splice = BM_edge_exists(v_target, v_old);
1847                         }
1848
1849                         bmesh_disk_vert_replace(e_old, v_target, v_kill);
1850
1851                         /* remove e_kill from 'v_target's disk cycle */
1852                         bmesh_disk_edge_remove(e_kill, v_target);
1853
1854 #ifndef NDEBUG
1855                         /* deal with radial cycle of e_kill */
1856                         radlen = bmesh_radial_length(e_kill->l);
1857 #endif
1858                         if (e_kill->l) {
1859
1860
1861                                 /* fix the neighboring loops of all loops in e_kill's radial cycle */
1862                                 l_kill = e_kill->l;
1863                                 do {
1864                                         /* relink loops and fix vertex pointer */
1865                                         if (l_kill->next->v == v_kill) {
1866                                                 l_kill->next->v = v_target;
1867                                         }
1868
1869                                         l_kill->next->prev = l_kill->prev;
1870                                         l_kill->prev->next = l_kill->next;
1871                                         if (BM_FACE_FIRST_LOOP(l_kill->f) == l_kill) {
1872                                                 BM_FACE_FIRST_LOOP(l_kill->f) = l_kill->next;
1873                                         }
1874
1875                                         /* fix len attribute of face */
1876                                         l_kill->f->len--;
1877                                         if (kill_degenerate_faces) {
1878                                                 if (l_kill->f->len < 3) {
1879                                                         BLI_SMALLSTACK_PUSH(faces_degenerate, l_kill->f);
1880                                                 }
1881                                         }
1882                                         l_kill_next = l_kill->radial_next;
1883
1884                                         bm_kill_only_loop(bm, l_kill);
1885
1886                                 } while ((l_kill = l_kill_next) != e_kill->l);
1887                                 /* `e_kill->l` is invalid but the edge is freed next. */
1888 #ifndef NDEBUG
1889                                 /* Validate radial cycle of e_old */
1890                                 edok = bmesh_radial_validate(radlen, e_old->l);
1891                                 BMESH_ASSERT(edok != false);
1892 #endif
1893                         }
1894                         /* deallocate edge */
1895                         bm_kill_only_edge(bm, e_kill);
1896
1897                         /* deallocate vertex */
1898                         if (do_del) {
1899                                 bm_kill_only_vert(bm, v_kill);
1900                         }
1901                         else {
1902                                 v_kill->e = NULL;
1903                         }
1904
1905 #ifndef NDEBUG
1906                         /* Validate disk cycle lengths of 'v_old', 'v_target' are unchanged */
1907                         edok = bmesh_disk_validate(valence1, v_old->e, v_old);
1908                         BMESH_ASSERT(edok != false);
1909                         edok = bmesh_disk_validate(valence2, v_target->e, v_target);
1910                         BMESH_ASSERT(edok != false);
1911
1912                         /* Validate loop cycle of all faces attached to 'e_old' */
1913                         for (i = 0, l = e_old->l; i < radlen; i++, l = l->radial_next) {
1914                                 BMESH_ASSERT(l->e == e_old);
1915                                 edok = BM_verts_in_edge(l->v, l->next->v, e_old);
1916                                 BMESH_ASSERT(edok != false);
1917                                 edok = bmesh_loop_validate(l->f);
1918                                 BMESH_ASSERT(edok != false);
1919
1920                                 BM_CHECK_ELEMENT(l);
1921                                 BM_CHECK_ELEMENT(l->v);
1922                                 BM_CHECK_ELEMENT(l->e);
1923                                 BM_CHECK_ELEMENT(l->f);
1924                         }
1925 #endif
1926                         if (check_edge_double) {
1927                                 if (e_splice) {
1928                                         /* removes e_splice */
1929                                         BM_edge_splice(bm, e_old, e_splice);
1930                                 }
1931                         }
1932
1933                         if (kill_degenerate_faces) {
1934                                 BMFace *f_kill;
1935                                 while ((f_kill = BLI_SMALLSTACK_POP(faces_degenerate))) {
1936                                         BM_face_kill(bm, f_kill);
1937                                 }
1938                         }
1939
1940                         BM_CHECK_ELEMENT(v_old);
1941                         BM_CHECK_ELEMENT(v_target);
1942                         BM_CHECK_ELEMENT(e_old);
1943
1944                         return e_old;
1945                 }
1946         }
1947         return NULL;
1948 }
1949
1950 /**
1951  * \brief Join Vert Kill Edge (JVKE)
1952  *
1953  * Collapse an edge, merging surrounding data.
1954  *
1955  * Unlike #BM_vert_collapse_edge & #bmesh_jekv which only handle 2 valence verts,
1956  * this can handle any number of connected edges/faces.
1957  *
1958  * <pre>
1959  * Before: -> After:
1960  * +-+-+-+    +-+-+-+
1961  * | | | |    | \ / |
1962  * +-+-+-+    +--+--+
1963  * | | | |    | / \ |
1964  * +-+-+-+    +-+-+-+
1965  * </pre>
1966  */
1967 BMVert *bmesh_jvke(
1968         BMesh *bm, BMEdge *e_kill, BMVert *v_kill,
1969         const bool do_del, const bool check_edge_double,
1970         const bool kill_degenerate_faces)
1971 {
1972         BLI_SMALLSTACK_DECLARE(faces_degenerate, BMFace *);
1973         BMVert *v_target = BM_edge_other_vert(e_kill, v_kill);
1974
1975         BLI_assert(BM_vert_in_edge(e_kill, v_kill));
1976
1977         if (e_kill->l) {
1978                 BMLoop *l_kill, *l_first, *l_kill_next;
1979                 l_kill = l_first = e_kill->l;
1980                 do {
1981                         /* relink loops and fix vertex pointer */
1982                         if (l_kill->next->v == v_kill) {
1983                                 l_kill->next->v = v_target;
1984                         }
1985
1986                         l_kill->next->prev = l_kill->prev;
1987                         l_kill->prev->next = l_kill->next;
1988                         if (BM_FACE_FIRST_LOOP(l_kill->f) == l_kill) {
1989                                 BM_FACE_FIRST_LOOP(l_kill->f) = l_kill->next;
1990                         }
1991
1992                         /* fix len attribute of face */
1993                         l_kill->f->len--;
1994                         if (kill_degenerate_faces) {
1995                                 if (l_kill->f->len < 3) {
1996                                         BLI_SMALLSTACK_PUSH(faces_degenerate, l_kill->f);
1997                                 }
1998                         }
1999                         l_kill_next = l_kill->radial_next;
2000
2001                         bm_kill_only_loop(bm, l_kill);
2002
2003                 } while ((l_kill = l_kill_next) != l_first);
2004
2005                 e_kill->l = NULL;
2006         }
2007
2008         BM_edge_kill(bm, e_kill);
2009         BM_CHECK_ELEMENT(v_kill);
2010         BM_CHECK_ELEMENT(v_target);
2011
2012         if (v_target->e && v_kill->e) {
2013                 /* inline BM_vert_splice(bm, v_target, v_kill); */
2014                 BMEdge *e;
2015                 while ((e = v_kill->e)) {
2016                         BMEdge *e_target;
2017
2018                         if (check_edge_double) {
2019                                 e_target = BM_edge_exists(v_target, BM_edge_other_vert(e, v_kill));
2020                         }
2021
2022                         bmesh_edge_vert_swap(e, v_target, v_kill);
2023                         BLI_assert(e->v1 != e->v2);
2024
2025                         if (check_edge_double) {
2026                                 if (e_target) {
2027                                         BM_edge_splice(bm, e_target, e);
2028                                 }
2029                         }
2030                 }
2031         }
2032
2033         if (kill_degenerate_faces) {
2034                 BMFace *f_kill;
2035                 while ((f_kill = BLI_SMALLSTACK_POP(faces_degenerate))) {
2036                         BM_face_kill(bm, f_kill);
2037                 }
2038         }
2039
2040         if (do_del) {
2041                 BLI_assert(v_kill->e == NULL);
2042                 bm_kill_only_vert(bm, v_kill);
2043         }
2044
2045         return v_target;
2046 }
2047
2048 /**
2049  * \brief Join Face Kill Edge (JFKE)
2050  *
2051  * Takes two faces joined by a single 2-manifold edge and fuses them together.
2052  * The edge shared by the faces must not be connected to any other edges which have
2053  * Both faces in its radial cycle
2054  *
2055  * \par Examples:
2056  * <pre>
2057  *           A                   B
2058  *      +--------+           +--------+
2059  *      |        |           |        |
2060  *      |   f1   |           |   f1   |
2061  *     v1========v2 = Ok!    v1==V2==v3 == Wrong!
2062  *      |   f2   |           |   f2   |
2063  *      |        |           |        |
2064  *      +--------+           +--------+
2065  * </pre>
2066  *
2067  * In the example A, faces \a f1 and \a f2 are joined by a single edge,
2068  * and the euler can safely be used.
2069  * In example B however, \a f1 and \a f2 are joined by multiple edges and will produce an error.
2070  * The caller in this case should call #bmesh_jekv on the extra edges
2071  * before attempting to fuse \a f1 and \a f2.
2072  *
2073  * \note The order of arguments decides whether or not certain per-face attributes are present
2074  * in the resultant face. For instance vertex winding, material index, smooth flags, etc are inherited
2075  * from \a f1, not \a f2.
2076  *
2077  * \return A BMFace pointer
2078  */
2079 BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e)
2080 {
2081         BMLoop *l_iter, *l_f1 = NULL, *l_f2 = NULL;
2082         int newlen = 0, i, f1len = 0, f2len = 0;
2083         bool edok;
2084         /* can't join a face to itself */
2085         if (f1 == f2) {
2086                 return NULL;
2087         }
2088
2089         /* validate that edge is 2-manifold edge */
2090         if (!BM_edge_is_manifold(e)) {
2091                 return NULL;
2092         }
2093
2094         /* verify that e is in both f1 and f2 */
2095         f1len = f1->len;
2096         f2len = f2->len;
2097
2098         if (!((l_f1 = BM_face_edge_share_loop(f1, e)) &&
2099               (l_f2 = BM_face_edge_share_loop(f2, e))))
2100         {
2101                 return NULL;
2102         }
2103
2104         /* validate direction of f2's loop cycle is compatible */
2105         if (l_f1->v == l_f2->v) {
2106                 return NULL;
2107         }
2108
2109         /* validate that for each face, each vertex has another edge in its disk cycle that is
2110          * not e, and not shared. */
2111         if (BM_edge_in_face(l_f1->next->e, f2) ||
2112             BM_edge_in_face(l_f1->prev->e, f2) ||
2113             BM_edge_in_face(l_f2->next->e, f1) ||
2114             BM_edge_in_face(l_f2->prev->e, f1) )
2115         {
2116                 return NULL;
2117         }
2118
2119         /* validate only one shared edge */
2120         if (BM_face_share_edge_count(f1, f2) > 1) {
2121                 return NULL;
2122         }
2123
2124         /* validate no internal join */
2125         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < f1len; i++, l_iter = l_iter->next) {
2126                 BM_elem_flag_disable(l_iter->v, BM_ELEM_INTERNAL_TAG);
2127         }
2128         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f2); i < f2len; i++, l_iter = l_iter->next) {
2129                 BM_elem_flag_disable(l_iter->v, BM_ELEM_INTERNAL_TAG);
2130         }
2131
2132         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < f1len; i++, l_iter = l_iter->next) {
2133                 if (l_iter != l_f1) {
2134                         BM_elem_flag_enable(l_iter->v, BM_ELEM_INTERNAL_TAG);
2135                 }
2136         }
2137         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f2); i < f2len; i++, l_iter = l_iter->next) {
2138                 if (l_iter != l_f2) {
2139                         /* as soon as a duplicate is found, bail out */
2140                         if (BM_elem_flag_test(l_iter->v, BM_ELEM_INTERNAL_TAG)) {
2141                                 return NULL;
2142                         }
2143                 }
2144         }
2145
2146         /* join the two loop */
2147         l_f1->prev->next = l_f2->next;
2148         l_f2->next->prev = l_f1->prev;
2149         
2150         l_f1->next->prev = l_f2->prev;
2151         l_f2->prev->next = l_f1->next;
2152         
2153         /* if l_f1 was baseloop, make l_f1->next the base. */
2154         if (BM_FACE_FIRST_LOOP(f1) == l_f1)
2155                 BM_FACE_FIRST_LOOP(f1) = l_f1->next;
2156
2157         /* increase length of f1 */
2158         f1->len += (f2->len - 2);
2159
2160         /* make sure each loop points to the proper face */
2161         newlen = f1->len;
2162         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < newlen; i++, l_iter = l_iter->next)
2163                 l_iter->f = f1;
2164         
2165         /* remove edge from the disk cycle of its two vertices */
2166         bmesh_disk_edge_remove(l_f1->e, l_f1->e->v1);
2167         bmesh_disk_edge_remove(l_f1->e, l_f1->e->v2);
2168         
2169         /* deallocate edge and its two loops as well as f2 */
2170         if (bm->etoolflagpool) {
2171                 BLI_mempool_free(bm->etoolflagpool, ((BMEdge_OFlag *)l_f1->e)->oflags);
2172         }
2173         BLI_mempool_free(bm->epool, l_f1->e);
2174         bm->totedge--;
2175         BLI_mempool_free(bm->lpool, l_f1);
2176         bm->totloop--;
2177         BLI_mempool_free(bm->lpool, l_f2);
2178         bm->totloop--;
2179         if (bm->ftoolflagpool) {
2180                 BLI_mempool_free(bm->ftoolflagpool, ((BMFace_OFlag *)f2)->oflags);
2181         }
2182         BLI_mempool_free(bm->fpool, f2);
2183         bm->totface--;
2184         /* account for both above */
2185         bm->elem_index_dirty |= BM_EDGE | BM_LOOP | BM_FACE;
2186
2187         BM_CHECK_ELEMENT(f1);
2188
2189         /* validate the new loop cycle */
2190         edok = bmesh_loop_validate(f1);
2191         BMESH_ASSERT(edok != false);
2192         
2193         return f1;
2194 }
2195
2196 /**
2197  * Check if splicing vertices would create any double edges.
2198  *
2199  * \note assume caller will handle case where verts share an edge.
2200  */
2201 bool BM_vert_splice_check_double(BMVert *v_a, BMVert *v_b)
2202 {
2203         bool is_double = false;
2204
2205         BLI_assert(BM_edge_exists(v_a, v_b) == false);
2206
2207         if (v_a->e && v_b->e) {
2208                 BMEdge *e, *e_first;
2209
2210 #define VERT_VISIT _FLAG_WALK
2211
2212                 /* tag 'v_a' */
2213                 e = e_first = v_a->e;
2214                 do {
2215                         BMVert *v_other = BM_edge_other_vert(e, v_a);
2216                         BLI_assert(!BM_ELEM_API_FLAG_TEST(v_other, VERT_VISIT));
2217                         BM_ELEM_API_FLAG_ENABLE(v_other, VERT_VISIT);
2218                 } while ((e = BM_DISK_EDGE_NEXT(e, v_a)) != e_first);
2219
2220                 /* check 'v_b' connects to 'v_a' edges */
2221                 e = e_first = v_b->e;
2222                 do {
2223                         BMVert *v_other = BM_edge_other_vert(e, v_b);
2224                         if (BM_ELEM_API_FLAG_TEST(v_other, VERT_VISIT)) {
2225                                 is_double = true;
2226                                 break;
2227                         }
2228                 } while ((e = BM_DISK_EDGE_NEXT(e, v_b)) != e_first);
2229
2230                 /* cleanup */
2231                 e = e_first = v_a->e;
2232                 do {
2233                         BMVert *v_other = BM_edge_other_vert(e, v_a);
2234                         BLI_assert(BM_ELEM_API_FLAG_TEST(v_other, VERT_VISIT));
2235                         BM_ELEM_API_FLAG_DISABLE(v_other, VERT_VISIT);
2236                 } while ((e = BM_DISK_EDGE_NEXT(e, v_a)) != e_first);
2237
2238 #undef VERT_VISIT
2239
2240         }
2241
2242         return is_double;
2243 }
2244
2245 /**
2246  * \brief Splice Vert
2247  *
2248  * Merges two verts into one
2249  * (\a v_src into \a v_dst, removing \a v_src).
2250  *
2251  * \return Success
2252  *
2253  * \warning This doesn't work for collapsing edges,
2254  * where \a v and \a vtarget are connected by an edge
2255  * (assert checks for this case).
2256  */
2257 bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src)
2258 {
2259         BMEdge *e;
2260
2261         /* verts already spliced */
2262         if (v_src == v_dst) {
2263                 return false;
2264         }
2265
2266         BLI_assert(BM_vert_pair_share_face_check(v_src, v_dst) == false);
2267
2268         /* move all the edges from 'v_src' disk to 'v_dst' */
2269         while ((e = v_src->e)) {
2270                 bmesh_edge_vert_swap(e, v_dst, v_src);
2271                 BLI_assert(e->v1 != e->v2);
2272         }
2273
2274         BM_CHECK_ELEMENT(v_src);
2275         BM_CHECK_ELEMENT(v_dst);
2276
2277         /* 'v_src' is unused now, and can be killed */
2278         BM_vert_kill(bm, v_src);
2279
2280         return true;
2281 }
2282
2283
2284 /** \name BM_vert_separate, bmesh_vert_separate and friends
2285  * \{ */
2286
2287 /* BM_edge_face_count(e) >= 1 */
2288 BLI_INLINE bool bm_edge_supports_separate(const BMEdge *e)
2289 {
2290         return (e->l && e->l->radial_next != e->l);
2291 }
2292
2293 /**
2294  * \brief Separate Vert
2295  *
2296  * Separates all disjoint fans that meet at a vertex, making a unique
2297  * vertex for each region. returns an array of all resulting vertices.
2298  *
2299  * \note this is a low level function, bm_edge_separate needs to run on edges first
2300  * or, the faces sharing verts must not be sharing edges for them to split at least.
2301  *
2302  * \return Success
2303  */
2304 void bmesh_vert_separate(
2305         BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len,
2306         const bool copy_select)
2307 {
2308         int v_edges_num = 0;
2309
2310         /* Detailed notes on array use since this is stack memory, we have to be careful */
2311
2312         /* newly created vertices, only use when 'r_vout' is set
2313          * (total size will be number of fans) */
2314         BLI_SMALLSTACK_DECLARE(verts_new, BMVert *);
2315         /* fill with edges from the face-fan, clearing on completion
2316          * (total size will be max fan edge count) */
2317         BLI_SMALLSTACK_DECLARE(edges, BMEdge *);
2318         /* temp store edges to walk over when filling 'edges',
2319          * (total size will be max radial edges of any edge) */
2320         BLI_SMALLSTACK_DECLARE(edges_search, BMEdge *);
2321
2322         /* number of resulting verts, include self */
2323         int verts_num = 1;
2324         /* track the total number of edges handled, so we know when we've found the last fan */
2325         int edges_found = 0;
2326
2327 #define EDGE_VISIT _FLAG_WALK
2328
2329         /* count and flag at once */
2330         if (v->e) {
2331                 BMEdge *e_first, *e_iter;
2332                 e_iter = e_first = v->e;
2333                 do {
2334                         v_edges_num += 1;
2335
2336                         BLI_assert(!BM_ELEM_API_FLAG_TEST(e_iter, EDGE_VISIT));
2337                         BM_ELEM_API_FLAG_ENABLE(e_iter, EDGE_VISIT);
2338                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
2339         }
2340
2341         while (true) {
2342                 /* Considering only edges and faces incident on vertex v, walk
2343                  * the edges & collect in the 'edges' list for splitting */
2344
2345                 BMEdge *e = v->e;
2346                 BM_ELEM_API_FLAG_DISABLE(e, EDGE_VISIT);
2347
2348                 do {
2349                         BLI_assert(!BM_ELEM_API_FLAG_TEST(e, EDGE_VISIT));
2350                         BLI_SMALLSTACK_PUSH(edges, e);
2351                         edges_found += 1;
2352
2353                         if (e->l) {
2354                                 BMLoop *l_iter, *l_first;
2355                                 l_iter = l_first = e->l;
2356                                 do {
2357                                         BMLoop *l_adjacent = (l_iter->v == v) ? l_iter->prev : l_iter->next;
2358                                         BLI_assert(BM_vert_in_edge(l_adjacent->e, v));
2359                                         if (BM_ELEM_API_FLAG_TEST(l_adjacent->e, EDGE_VISIT)) {
2360                                                 BM_ELEM_API_FLAG_DISABLE(l_adjacent->e, EDGE_VISIT);
2361                                                 BLI_SMALLSTACK_PUSH(edges_search, l_adjacent->e);
2362                                         }
2363                                 } while ((l_iter = l_iter->radial_next) != l_first);
2364                         }
2365                 } while ((e = BLI_SMALLSTACK_POP(edges_search)));
2366
2367                 /* now we have all edges connected to 'v->e' */
2368
2369                 BLI_assert(edges_found <= v_edges_num);
2370
2371                 if (edges_found == v_edges_num) {
2372                         /* We're done! The remaining edges in 'edges' form the last fan,
2373                          * which can be left as is.
2374                          * if 'edges' were alloc'd it'd be freed here. */
2375                         break;
2376                 }
2377                 else {
2378                         BMVert *v_new;
2379
2380                         v_new = BM_vert_create(bm, v->co, v, BM_CREATE_NOP);
2381                         if (copy_select) {
2382                                 BM_elem_select_copy(bm, bm, v_new, v);
2383                         }
2384
2385                         while ((e = BLI_SMALLSTACK_POP(edges))) {
2386                                 bmesh_edge_vert_swap(e, v_new, v);
2387                         }
2388
2389                         if (r_vout) {
2390                                 BLI_SMALLSTACK_PUSH(verts_new, v_new);
2391                         }
2392                         verts_num += 1;
2393                 }
2394         }
2395
2396 #undef EDGE_VISIT
2397
2398         /* flags are clean now, handle return values */
2399
2400         if (r_vout_len != NULL) {
2401                 *r_vout_len = verts_num;
2402         }
2403
2404         if (r_vout != NULL) {
2405                 BMVert **verts;
2406
2407                 verts = MEM_mallocN(sizeof(BMVert *) * verts_num, __func__);
2408                 *r_vout = verts;
2409
2410                 verts[0] = v;
2411                 BLI_SMALLSTACK_AS_TABLE(verts_new, &verts[1]);
2412         }
2413 }
2414
2415 /**
2416  * Utility function for #BM_vert_separate
2417  *
2418  * Takes a list of edges, which have been split from their original.
2419  *
2420  * Any edges which failed to split off in #bmesh_vert_separate will be merged back into the original edge.
2421  *
2422  * \param edges_separate
2423  * A list-of-lists, each list is from a single original edge (the first edge is the original),
2424  * Check for duplicates (not just with the first) but between all.
2425  * This is O(n2) but radial edges are very rarely >2 and almost never >~10.
2426  *
2427  * \note typically its best to avoid creating the data in the first place,
2428  * but inspecting all loops connectivity is quite involved.
2429  *
2430  * \note this function looks like it could become slow,
2431  * but in common cases its only going to iterate a few times.
2432  */
2433 static void bmesh_vert_separate__cleanup(BMesh *bm, LinkNode *edges_separate)
2434 {
2435         do {
2436                 LinkNode *n_orig = edges_separate->link;
2437                 do {
2438                         BMEdge *e_orig = n_orig->link;
2439                         LinkNode *n_step = n_orig->next;
2440                         LinkNode *n_prev = n_orig;
2441                         do {
2442                                 BMEdge *e = n_step->link;
2443                                 BLI_assert(e != e_orig);
2444                                 if ((e->v1 == e_orig->v1) && (e->v2 == e_orig->v2)) {
2445                                         BM_edge_splice(bm, e_orig, e);
2446                                         n_prev->next = n_step->next;
2447                                         n_step = n_prev;
2448                                 }
2449                         } while ((void)
2450                                  (n_prev = n_step),
2451                                  (n_step = n_step->next));
2452
2453                 } while ((n_orig = n_orig->next) && n_orig->next);
2454         } while ((edges_separate = edges_separate->next));
2455 }
2456
2457 /**
2458  * High level function which wraps both #bmesh_vert_separate and #bmesh_edge_separate
2459  */
2460 void BM_vert_separate(
2461         BMesh *bm, BMVert *v,
2462         BMEdge **e_in, int e_in_len,
2463         const bool copy_select,
2464         BMVert ***r_vout, int *r_vout_len)
2465 {
2466         LinkNode *edges_separate = NULL;
2467         int i;
2468
2469         for (i = 0; i < e_in_len; i++) {
2470                 BMEdge *e = e_in[i];
2471                 if (bm_edge_supports_separate(e)) {
2472                         LinkNode *edges_orig = NULL;
2473                         do {
2474                                 BMLoop *l_sep = e->l;
2475                                 bmesh_edge_separate(bm, e, l_sep, copy_select);
2476                                 BLI_linklist_prepend_alloca(&edges_orig, l_sep->e);
2477                                 BLI_assert(e != l_sep->e);
2478                         } while (bm_edge_supports_separate(e));
2479                         BLI_linklist_prepend_alloca(&edges_orig, e);
2480                         BLI_linklist_prepend_alloca(&edges_separate, edges_orig);
2481                 }
2482         }
2483
2484         bmesh_vert_separate(bm, v, r_vout, r_vout_len, copy_select);
2485
2486         if (edges_separate) {
2487                 bmesh_vert_separate__cleanup(bm, edges_separate);
2488         }
2489 }
2490
2491
2492 /**
2493  * A version of #BM_vert_separate which takes a flag.
2494  */
2495 void BM_vert_separate_hflag(
2496         BMesh *bm, BMVert *v,
2497         const char hflag,
2498         const bool copy_select,
2499         BMVert ***r_vout, int *r_vout_len)
2500 {
2501         LinkNode *edges_separate = NULL;
2502         BMEdge *e_iter, *e_first;
2503
2504         e_iter = e_first = v->e;
2505         do {
2506                 if (BM_elem_flag_test(e_iter, hflag)) {
2507                         BMEdge *e = e_iter;
2508                         if (bm_edge_supports_separate(e)) {
2509                                 LinkNode *edges_orig = NULL;
2510                                 do {
2511                                         BMLoop *l_sep = e->l;
2512                                         bmesh_edge_separate(bm, e, l_sep, copy_select);
2513                                         /* trick to avoid looping over separated edges */
2514                                         if (edges_separate == NULL && edges_orig == NULL) {
2515                                                 e_first = l_sep->e;
2516                                         }
2517                                         BLI_linklist_prepend_alloca(&edges_orig, l_sep->e);
2518                                         BLI_assert(e != l_sep->e);
2519                                 } while (bm_edge_supports_separate(e));
2520                                 BLI_linklist_prepend_alloca(&edges_orig, e);
2521                                 BLI_linklist_prepend_alloca(&edges_separate, edges_orig);
2522                         }
2523                 }
2524         } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != e_first);
2525
2526         bmesh_vert_separate(bm, v, r_vout, r_vout_len, copy_select);
2527
2528         if (edges_separate) {
2529                 bmesh_vert_separate__cleanup(bm, edges_separate);
2530         }
2531 }
2532
2533 void BM_vert_separate_wire_hflag(
2534         BMesh *UNUSED(bm), BMVert *v_dst, BMVert *v_src,
2535         const char hflag)
2536 {
2537         LinkNode *edges_hflag = NULL;
2538         BMEdge *e_iter, *e_first;
2539
2540         e_iter = e_first = v_src->e;
2541         do {
2542                 if (BM_elem_flag_test(e_iter, hflag)) {
2543                         if (BM_edge_is_wire(e_iter)) {
2544                                 BLI_linklist_prepend_alloca(&edges_hflag, e_iter);
2545                         }
2546                 }
2547         } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_src)) != e_first);
2548
2549         if (edges_hflag) {
2550                 do {
2551                         e_iter = edges_hflag->link;
2552                         bmesh_disk_vert_replace(e_iter, v_dst, v_src);
2553                 } while ((edges_hflag = edges_hflag->next));
2554         }
2555 }
2556
2557 /** \} */
2558
2559
2560 /**
2561  * \brief Splice Edge
2562  *
2563  * Splice two unique edges which share the same two vertices into one edge.
2564  *  (\a e_src into \a e_dst, removing e_src).
2565  *
2566  * \return Success
2567  *
2568  * \note Edges must already have the same vertices.
2569  */
2570 bool BM_edge_splice(BMesh *bm, BMEdge *e_dst, BMEdge *e_src)
2571 {
2572         BMLoop *l;
2573
2574         if (!BM_vert_in_edge(e_src, e_dst->v1) || !BM_vert_in_edge(e_src, e_dst->v2)) {
2575                 /* not the same vertices can't splice */
2576
2577                 /* the caller should really make sure this doesn't happen ever
2578                  * so assert on release builds */
2579                 BLI_assert(0);
2580
2581                 return false;
2582         }
2583
2584         while (e_src->l) {
2585                 l = e_src->l;
2586                 BLI_assert(BM_vert_in_edge(e_dst, l->v));
2587                 BLI_assert(BM_vert_in_edge(e_dst, l->next->v));
2588                 bmesh_radial_loop_remove(e_src, l);
2589                 bmesh_radial_loop_append(e_dst, l);
2590         }
2591
2592         BLI_assert(bmesh_radial_length(e_src->l) == 0);
2593
2594         BM_CHECK_ELEMENT(e_src);
2595         BM_CHECK_ELEMENT(e_dst);
2596
2597         /* removes from disks too */
2598         BM_edge_kill(bm, e_src);
2599
2600         return true;
2601 }
2602
2603 /**
2604  * \brief Separate Edge
2605  *
2606  * Separates a single edge into two edge: the original edge and
2607  * a new edge that has only \a l_sep in its radial.
2608  *
2609  * \return Success
2610  *
2611  * \note Does nothing if \a l_sep is already the only loop in the
2612  * edge radial.
2613  */
2614 void bmesh_edge_separate(
2615         BMesh *bm, BMEdge *e, BMLoop *l_sep,
2616         const bool copy_select)
2617 {
2618         BMEdge *e_new;
2619 #ifndef NDEBUG
2620         const int radlen = bmesh_radial_length(e->l);
2621 #endif
2622
2623         BLI_assert(l_sep->e == e);
2624         BLI_assert(e->l);
2625         
2626         if (BM_edge_is_boundary(e)) {
2627                 BLI_assert(0); /* no cut required */
2628                 return;
2629         }
2630
2631         if (l_sep == e->l) {
2632                 e->l = l_sep->radial_next;
2633         }
2634
2635         e_new = BM_edge_create(bm, e->v1, e->v2, e, BM_CREATE_NOP);
2636         bmesh_radial_loop_remove(e, l_sep);
2637         bmesh_radial_loop_append(e_new, l_sep);
2638         l_sep->e = e_new;
2639
2640         if (copy_select) {
2641                 BM_elem_select_copy(bm, bm, e_new, e);
2642         }
2643
2644         BLI_assert(bmesh_radial_length(e->l) == radlen - 1);
2645         BLI_assert(bmesh_radial_length(e_new->l) == 1);
2646
2647         BM_CHECK_ELEMENT(e_new);
2648         BM_CHECK_ELEMENT(e);
2649 }
2650
2651 /**
2652  * \brief Un-glue Region Make Vert (URMV)
2653  *
2654  * Disconnects a face from its vertex fan at loop \a l_sep
2655  *
2656  * \return The newly created BMVert
2657  *
2658  * \note Will be a no-op and return original vertex if only two edges at that vertex.
2659  */
2660 BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *l_sep)
2661 {
2662         BMVert *v_new = NULL;
2663         BMVert *v_sep = l_sep->v;
2664         BMEdge *e_iter;
2665         BMEdge *edges[2];
2666         int i;
2667
2668         /* peel the face from the edge radials on both sides of the
2669          * loop vert, disconnecting the face from its fan */
2670         if (!BM_edge_is_boundary(l_sep->e))
2671                 bmesh_edge_separate(bm, l_sep->e, l_sep, false);
2672         if (!BM_edge_is_boundary(l_sep->prev->e))
2673                 bmesh_edge_separate(bm, l_sep->prev->e, l_sep->prev, false);
2674
2675         /* do inline, below */
2676 #if 0
2677         if (BM_vert_edge_count_is_equal(v_sep, 2)) {
2678                 return v_sep;
2679         }
2680 #endif
2681
2682         /* Search for an edge unattached to this loop */
2683         e_iter = v_sep->e;
2684         while (!ELEM(e_iter, l_sep->e, l_sep->prev->e)) {
2685                 e_iter = bmesh_disk_edge_next(e_iter, v_sep);
2686
2687                 /* We've come back around to the initial edge, all touch this loop.
2688                  * If there are still only two edges out of v_sep,
2689                  * then this whole URMV was just a no-op, so exit now. */
2690                 if (e_iter == v_sep->e) {
2691                         BLI_assert(BM_vert_edge_count_is_equal(v_sep, 2));
2692                         return v_sep;
2693                 }
2694         }
2695
2696         v_sep->e = l_sep->e;
2697
2698         v_new = BM_vert_create(bm, v_sep->co, v_sep, BM_CREATE_NOP);
2699
2700         edges[0] = l_sep->e;
2701         edges[1] = l_sep->prev->e;
2702
2703         for (i = 0; i < ARRAY_SIZE(edges); i++) {
2704                 BMEdge *e = edges[i];
2705                 bmesh_edge_vert_swap(e, v_new, v_sep);
2706         }
2707
2708         BLI_assert(v_sep != l_sep->v);
2709         BLI_assert(v_sep->e != l_sep->v->e);
2710
2711         BM_CHECK_ELEMENT(l_sep);
2712         BM_CHECK_ELEMENT(v_sep);
2713         BM_CHECK_ELEMENT(edges[0]);
2714         BM_CHECK_ELEMENT(edges[1]);
2715         BM_CHECK_ELEMENT(v_new);
2716
2717         return v_new;
2718 }
2719
2720 /**
2721  * A version of #bmesh_urmv_loop that disconnects multiple loops at once.
2722  *
2723  * Handles the task of finding fans boundaries.
2724  */
2725 BMVert *bmesh_urmv_loop_multi(
2726         BMesh *bm, BMLoop **larr, int larr_len)
2727 {
2728         BMVert *v_sep = larr[0]->v;
2729         BMVert *v_new;
2730         int i;
2731         bool is_mixed_any = false;
2732
2733         BLI_SMALLSTACK_DECLARE(edges, BMEdge *);
2734
2735 #define LOOP_VISIT _FLAG_WALK
2736 #define EDGE_VISIT _FLAG_WALK
2737
2738         for (i = 0; i < larr_len; i++) {
2739                 BMLoop *l_sep = larr[i];
2740
2741                 /* all must be from the same vert! */
2742                 BLI_assert(v_sep == l_sep->v);
2743
2744                 BLI_assert(!BM_ELEM_API_FLAG_TEST(l_sep, LOOP_VISIT));
2745                 BM_ELEM_API_FLAG_ENABLE(l_sep, LOOP_VISIT);
2746
2747                 /* weak! but it makes it simpler to check for edges to split
2748                  * while doing a radial loop (where loops may be adjacent) */
2749                 BM_ELEM_API_FLAG_ENABLE(l_sep->next, LOOP_VISIT);
2750                 BM_ELEM_API_FLAG_ENABLE(l_sep->prev, LOOP_VISIT);
2751         }
2752
2753         for (i = 0; i < larr_len; i++) {
2754                 BMLoop *l_sep = larr[i];
2755
2756                 BMLoop *loop_pair[2] = {l_sep, l_sep->prev};
2757                 int j;
2758                 for (j = 0; j < ARRAY_SIZE(loop_pair); j++) {
2759                         BMEdge *e = loop_pair[j]->e;
2760                         if (!BM_ELEM_API_FLAG_TEST(e, EDGE_VISIT)) {
2761                                 BMLoop *l_iter, *l_first;
2762                                 bool is_mixed = false;
2763
2764                                 BM_ELEM_API_FLAG_ENABLE(e, EDGE_VISIT);
2765
2766                                 l_iter = l_first = e->l;
2767                                 do {
2768                                         if (!BM_ELEM_API_FLAG_TEST(l_iter, LOOP_VISIT)) {
2769                                                 is_mixed = true;
2770                                                 is_mixed_any = true;
2771                                                 break;
2772                                         }
2773                                 } while ((l_iter = l_iter->radial_next) != l_first);
2774
2775                                 if (is_mixed) {
2776                                         /* ensure the first loop is one we don't own so we can do a quick check below
2777                                          * on the edge's loop-flag to see if the edge is mixed or not. */
2778                                         e->l = l_iter;
2779                                 }
2780                                 BLI_SMALLSTACK_PUSH(edges, e);
2781                         }
2782                 }
2783         }
2784
2785         if (is_mixed_any == false) {
2786                 /* all loops in 'larr' are the sole owners of their edges.
2787                  * nothing to split away from, this is a no-op */
2788                 v_new = v_sep;
2789         }
2790         else {
2791                 BMEdge *e;
2792
2793                 BLI_assert(!BLI_SMALLSTACK_IS_EMPTY(edges));
2794
2795                 v_new = BM_vert_create(bm, v_sep->co, v_sep, BM_CREATE_NOP);
2796                 while ((e = BLI_SMALLSTACK_POP(edges))) {
2797                         BMLoop *l_iter, *l_first, *l_next;
2798                         BMEdge *e_new;
2799
2800                         /* disable so copied edge isn't left dirty (loop edges are cleared last too) */
2801                         BM_ELEM_API_FLAG_DISABLE(e, EDGE_VISIT);
2802
2803                         if (!BM_ELEM_API_FLAG_TEST(e->l, LOOP_VISIT)) {
2804                                 /* edge has some loops owned by us, some owned by other loops */
2805                                 BMVert *e_new_v_pair[2];
2806
2807                                 if (e->v1 == v_sep) {
2808                                         e_new_v_pair[0] = v_new;
2809                                         e_new_v_pair[1] = e->v2;
2810                                 }
2811                                 else {
2812                                         BLI_assert(v_sep == e->v2);
2813                                         e_new_v_pair[0] = e->v1;
2814                                         e_new_v_pair[1] = v_new;
2815                                 }
2816
2817                                 e_new = BM_edge_create(bm, UNPACK2(e_new_v_pair), e, BM_CREATE_NOP);
2818
2819                                 /* now moved all loops from 'larr' to this newly created edge */
2820                                 l_iter = l_first = e->l;
2821                                 do {
2822                                         l_next = l_iter->radial_next;
2823                                         if (BM_ELEM_API_FLAG_TEST(l_iter, LOOP_VISIT)) {
2824                                                 bmesh_radial_loop_remove(e, l_iter);
2825                                                 bmesh_radial_loop_append(e_new, l_iter);
2826                                                 l_iter->e = e_new;
2827                                         }
2828                                 } while ((l_iter = l_next) != l_first);
2829                         }
2830                         else {
2831                                 /* we own the edge entirely, replace the vert */
2832                                 bmesh_disk_vert_replace(e, v_new, v_sep);
2833                         }
2834
2835                         /* loop vert is handled last! */
2836                 }
2837         }
2838
2839         for (i = 0; i < larr_len; i++) {
2840                 BMLoop *l_sep = larr[i];
2841
2842                 l_sep->v = v_new;
2843
2844                 BLI_assert(BM_ELEM_API_FLAG_TEST(l_sep, LOOP_VISIT));
2845                 BLI_assert(BM_ELEM_API_FLAG_TEST(l_sep->prev, LOOP_VISIT));
2846                 BLI_assert(BM_ELEM_API_FLAG_TEST(l_sep->next, LOOP_VISIT));
2847                 BM_ELEM_API_FLAG_DISABLE(l_sep, LOOP_VISIT);
2848                 BM_ELEM_API_FLAG_DISABLE(l_sep->prev, LOOP_VISIT);
2849                 BM_ELEM_API_FLAG_DISABLE(l_sep->next, LOOP_VISIT);
2850
2851
2852                 BM_ELEM_API_FLAG_DISABLE(l_sep->prev->e, EDGE_VISIT);
2853                 BM_ELEM_API_FLAG_DISABLE(l_sep->e, EDGE_VISIT);
2854         }
2855
2856 #undef LOOP_VISIT
2857 #undef EDGE_VISIT
2858
2859         return v_new;
2860 }
2861
2862 static void bmesh_edge_vert_swap__recursive(BMEdge *e, BMVert *v_dst, BMVert *v_src)
2863 {
2864         BMLoop *l_iter, *l_first;
2865
2866         BLI_assert(ELEM(v_src, e->v1, e->v2));
2867         bmesh_disk_vert_replace(e, v_dst, v_src);
2868
2869         l_iter = l_first = e->l;
2870         do {
2871                 if (l_iter->v == v_src) {
2872                         l_iter->v = v_dst;
2873                         if (BM_vert_in_edge(l_iter->prev->e, v_src)) {
2874                                 bmesh_edge_vert_swap__recursive(l_iter->prev->e, v_dst, v_src);
2875                         }
2876                 }
2877                 else if (l_iter->next->v == v_src) {
2878                         l_iter->next->v = v_dst;
2879                         if (BM_vert_in_edge(l_iter->next->e, v_src)) {
2880                                 bmesh_edge_vert_swap__recursive(l_iter->next->e, v_dst, v_src);
2881                         }
2882                 }
2883                 else {
2884                         BLI_assert(l_iter->prev->v != v_src);
2885                 }
2886         } while ((l_iter = l_iter->radial_next) != l_first);
2887 }
2888
2889 /**
2890  * This function assumes l_sep is apart of a larger fan which has already been
2891  * isolated by calling bmesh_edge_separate to segregate it radially.
2892  */
2893 BMVert *bmesh_urmv_loop_region(BMesh *bm, BMLoop *l_sep)
2894 {
2895         BMVert *v_new = BM_vert_create(bm, l_sep->v->co, l_sep->v, BM_CREATE_NOP);
2896         /* passing either 'l_sep->e', 'l_sep->prev->e' will work */
2897         bmesh_edge_vert_swap__recursive(l_sep->e, v_new, l_sep->v);
2898         BLI_assert(l_sep->v == v_new);
2899         return v_new;
2900 }
2901
2902
2903 /**
2904  * \brief Unglue Region Make Vert (URMV)
2905  *
2906  * Disconnects f_sep from the vertex fan at \a v_sep
2907  *
2908  * \return The newly created BMVert
2909  */
2910 BMVert *bmesh_urmv(BMesh *bm, BMFace *f_sep, BMVert *v_sep)
2911 {
2912         BMLoop *l = BM_face_vert_share_loop(f_sep, v_sep);
2913         return bmesh_urmv_loop(bm, l);
2914 }
2915
2916 /**
2917  * Avoid calling this where possible,
2918  * low level function so both face pointers remain intact but point to swapped data.
2919  * \note must be from the same bmesh.
2920  */
2921 void bmesh_face_swap_data(BMFace *f_a, BMFace *f_b)
2922 {
2923         BMLoop *l_iter, *l_first;
2924
2925         BLI_assert(f_a != f_b);
2926
2927         l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
2928         do {
2929                 l_iter->f = f_b;
2930         } while ((l_iter = l_iter->next) != l_first);
2931
2932         l_iter = l_first = BM_FACE_FIRST_LOOP(f_b);
2933         do {
2934                 l_iter->f = f_a;
2935         } while ((l_iter = l_iter->next) != l_first);
2936
2937         SWAP(BMFace, (*f_a), (*f_b));
2938
2939         /* swap back */
2940         SWAP(void *, f_a->head.data, f_b->head.data);
2941         SWAP(int, f_a->head.index, f_b->head.index);
2942 }