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