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