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