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