BLI_stackdefines
[blender.git] / source / blender / bmesh / intern / bmesh_core.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Joseph Eagar, Geoffrey Bantle, Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/intern/bmesh_core.c
24  *  \ingroup bmesh
25  *
26  * Core BMesh functions for adding, removing BMesh elements.
27  */
28
29 #include "MEM_guardedalloc.h"
30
31 #include "BLI_math_vector.h"
32 #include "BLI_array.h"
33 #include "BLI_alloca.h"
34 #include "BLI_smallhash.h"
35 #include "BLI_stackdefines.h"
36
37 #include "BLF_translation.h"
38
39 #include "BKE_DerivedMesh.h"
40
41 #include "bmesh.h"
42 #include "intern/bmesh_private.h"
43
44 /* use so valgrinds memcheck alerts us when undefined index is used.
45  * TESTING ONLY! */
46 // #define USE_DEBUG_INDEX_MEMCHECK
47
48 #ifdef USE_DEBUG_INDEX_MEMCHECK
49 #define DEBUG_MEMCHECK_INDEX_INVALIDATE(ele)                                  \
50         {                                                                         \
51                 int undef_idx;                                                        \
52                 BM_elem_index_set(ele, undef_idx); /* set_ok_invalid */               \
53         } (void)0
54
55 #endif
56
57 /**
58  * \brief Main function for creating a new vertex.
59  */
60 BMVert *BM_vert_create(BMesh *bm, const float co[3],
61                        const BMVert *v_example, const eBMCreateFlag create_flag)
62 {
63         BMVert *v = BLI_mempool_alloc(bm->vpool);
64
65
66         /* --- assign all members --- */
67         v->head.data = NULL;
68
69 #ifdef USE_DEBUG_INDEX_MEMCHECK
70         DEBUG_MEMCHECK_INDEX_INVALIDATE(v)
71 #else
72         BM_elem_index_set(v, -1); /* set_ok_invalid */
73 #endif
74
75         v->head.htype = BM_VERT;
76         v->head.hflag = 0;
77         v->head.api_flag = 0;
78
79         /* allocate flags */
80         v->oflags = bm->vtoolflagpool ? BLI_mempool_calloc(bm->vtoolflagpool) : NULL;
81
82         /* 'v->no' is handled by BM_elem_attrs_copy */
83         if (co) {
84                 copy_v3_v3(v->co, co);
85         }
86         else {
87                 zero_v3(v->co);
88         }
89         zero_v3(v->no);
90
91         v->e = NULL;
92         /* --- done --- */
93
94
95         /* disallow this flag for verts - its meaningless */
96         BLI_assert((create_flag & BM_CREATE_NO_DOUBLE) == 0);
97
98         /* may add to middle of the pool */
99         bm->elem_index_dirty |= BM_VERT;
100         bm->elem_table_dirty |= BM_VERT;
101
102         bm->totvert++;
103
104         if (!(create_flag & BM_CREATE_SKIP_CD)) {
105                 if (v_example) {
106                         int *keyi;
107
108                         BM_elem_attrs_copy(bm, bm, v_example, v);
109
110                         /* exception: don't copy the original shapekey index */
111                         keyi = CustomData_bmesh_get(&bm->vdata, v->head.data, CD_SHAPE_KEYINDEX);
112                         if (keyi) {
113                                 *keyi = ORIGINDEX_NONE;
114                         }
115                 }
116                 else {
117                         CustomData_bmesh_set_default(&bm->vdata, &v->head.data);
118                 }
119         }
120
121         BM_CHECK_ELEMENT(v);
122
123         return v;
124 }
125
126 /**
127  * \brief Main function for creating a new edge.
128  *
129  * \note Duplicate edges are supported by the API however users should _never_ see them.
130  * so unless you need a unique edge or know the edge won't exist, you should call with \a no_double = true
131  */
132 BMEdge *BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2,
133                        const BMEdge *e_example, const eBMCreateFlag create_flag)
134 {
135         BMEdge *e;
136
137         BLI_assert(v1 != v2);
138         BLI_assert(v1->head.htype == BM_VERT && v2->head.htype == BM_VERT);
139
140         if ((create_flag & BM_CREATE_NO_DOUBLE) && (e = BM_edge_exists(v1, v2)))
141                 return e;
142         
143         e = BLI_mempool_alloc(bm->epool);
144
145
146         /* --- assign all members --- */
147         e->head.data = NULL;
148
149 #ifdef USE_DEBUG_INDEX_MEMCHECK
150         DEBUG_MEMCHECK_INDEX_INVALIDATE(e)
151 #else
152         BM_elem_index_set(e, -1); /* set_ok_invalid */
153 #endif
154
155         e->head.htype = BM_EDGE;
156         e->head.hflag = BM_ELEM_SMOOTH | BM_ELEM_DRAW;
157         e->head.api_flag = 0;
158
159         /* allocate flags */
160         e->oflags = bm->etoolflagpool ? BLI_mempool_calloc(bm->etoolflagpool) : NULL;
161
162         e->v1 = v1;
163         e->v2 = v2;
164         e->l = NULL;
165
166         memset(&e->v1_disk_link, 0, sizeof(BMDiskLink) * 2);
167         /* --- done --- */
168
169
170         bmesh_disk_edge_append(e, e->v1);
171         bmesh_disk_edge_append(e, e->v2);
172
173         /* may add to middle of the pool */
174         bm->elem_index_dirty |= BM_EDGE;
175         bm->elem_table_dirty |= BM_EDGE;
176
177         bm->totedge++;
178
179         if (!(create_flag & BM_CREATE_SKIP_CD)) {
180                 if (e_example) {
181                         BM_elem_attrs_copy(bm, bm, e_example, e);
182                 }
183                 else {
184                         CustomData_bmesh_set_default(&bm->edata, &e->head.data);
185                 }
186         }
187
188         BM_CHECK_ELEMENT(e);
189
190         return e;
191 }
192
193 static BMLoop *bm_loop_create(BMesh *bm, BMVert *v, BMEdge *e, BMFace *f,
194                               const BMLoop *example, const eBMCreateFlag create_flag)
195 {
196         BMLoop *l = NULL;
197
198         l = BLI_mempool_alloc(bm->lpool);
199
200         /* --- assign all members --- */
201         l->head.data = NULL;
202
203 #ifdef USE_DEBUG_INDEX_MEMCHECK
204         DEBUG_MEMCHECK_INDEX_INVALIDATE(l)
205 #else
206         BM_elem_index_set(l, -1); /* set_ok_invalid */
207 #endif
208
209         l->head.hflag = 0;
210         l->head.htype = BM_LOOP;
211         l->head.api_flag = 0;
212
213         l->v = v;
214         l->e = e;
215         l->f = f;
216
217         l->radial_next = NULL;
218         l->radial_prev = NULL;
219         l->next = NULL;
220         l->prev = NULL;
221         /* --- done --- */
222
223         /* may add to middle of the pool */
224         bm->elem_index_dirty |= BM_LOOP;
225
226         bm->totloop++;
227
228         if (!(create_flag & BM_CREATE_SKIP_CD)) {
229                 if (example) {
230                         CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, example->head.data, &l->head.data);
231                 }
232                 else {
233                         CustomData_bmesh_set_default(&bm->ldata, &l->head.data);
234                 }
235         }
236
237         return l;
238 }
239
240 static BMLoop *bm_face_boundary_add(BMesh *bm, BMFace *f, BMVert *startv, BMEdge *starte,
241                                     const eBMCreateFlag create_flag)
242 {
243 #ifdef USE_BMESH_HOLES
244         BMLoopList *lst = BLI_mempool_calloc(bm->looplistpool);
245 #endif
246         BMLoop *l = bm_loop_create(bm, startv, starte, f, starte->l, create_flag);
247         
248         bmesh_radial_append(starte, l);
249
250 #ifdef USE_BMESH_HOLES
251         lst->first = lst->last = l;
252         BLI_addtail(&f->loops, lst);
253 #else
254         f->l_first = l;
255 #endif
256
257         l->f = f;
258         
259         return l;
260 }
261
262 BMFace *BM_face_copy(BMesh *bm_dst, BMesh *bm_src, BMFace *f,
263                      const bool copy_verts, const bool copy_edges)
264 {
265         BMVert **verts = BLI_array_alloca(verts, f->len);
266         BMEdge **edges = BLI_array_alloca(edges, f->len);
267         BMLoop *l_iter;
268         BMLoop *l_first;
269         BMLoop *l_copy;
270         BMFace *f_copy;
271         int i;
272
273         BLI_assert((bm_dst == bm_src) || (copy_verts && copy_edges));
274
275         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
276         i = 0;
277         do {
278                 if (copy_verts) {
279                         verts[i] = BM_vert_create(bm_dst, l_iter->v->co, l_iter->v, BM_CREATE_NOP);
280                 }
281                 else {
282                         verts[i] = l_iter->v;
283                 }
284                 i++;
285         } while ((l_iter = l_iter->next) != l_first);
286
287         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
288         i = 0;
289         do {
290                 if (copy_edges) {
291                         BMVert *v1, *v2;
292                         
293                         if (l_iter->e->v1 == verts[i]) {
294                                 v1 = verts[i];
295                                 v2 = verts[(i + 1) % f->len];
296                         }
297                         else {
298                                 v2 = verts[i];
299                                 v1 = verts[(i + 1) % f->len];
300                         }
301                         
302                         edges[i] = BM_edge_create(bm_dst, v1, v2, l_iter->e, BM_CREATE_NOP);
303                 }
304                 else {
305                         edges[i] = l_iter->e;
306                 }
307                 i++;
308         } while ((l_iter = l_iter->next) != l_first);
309         
310         f_copy = BM_face_create(bm_dst, verts, edges, f->len, NULL, BM_CREATE_SKIP_CD);
311         
312         BM_elem_attrs_copy(bm_src, bm_dst, f, f_copy);
313         
314         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
315         l_copy = BM_FACE_FIRST_LOOP(f_copy);
316         do {
317                 BM_elem_attrs_copy(bm_src, bm_dst, l_iter, l_copy);
318                 l_copy = l_copy->next;
319         } while ((l_iter = l_iter->next) != l_first);
320
321         return f_copy;
322 }
323
324 /**
325  * only create the face, since this calloc's the length is initialized to 0,
326  * leave adding loops to the caller.
327  *
328  * \note, caller needs to handle customdata.
329  */
330 BLI_INLINE BMFace *bm_face_create__internal(BMesh *bm)
331 {
332         BMFace *f;
333
334         f = BLI_mempool_alloc(bm->fpool);
335
336
337         /* --- assign all members --- */
338         f->head.data = NULL;
339 #ifdef USE_DEBUG_INDEX_MEMCHECK
340         DEBUG_MEMCHECK_INDEX_INVALIDATE(f)
341 #else
342         BM_elem_index_set(f, -1); /* set_ok_invalid */
343 #endif
344
345         f->head.htype = BM_FACE;
346         f->head.hflag = 0;
347         f->head.api_flag = 0;
348
349         /* allocate flags */
350         f->oflags = bm->ftoolflagpool ? BLI_mempool_calloc(bm->ftoolflagpool) : NULL;
351
352 #ifdef USE_BMESH_HOLES
353         BLI_listbase_clear(&f->loops);
354 #else
355         f->l_first = NULL;
356 #endif
357         f->len = 0;
358         zero_v3(f->no);
359         f->mat_nr = 0;
360         /* --- done --- */
361
362
363         /* may add to middle of the pool */
364         bm->elem_index_dirty |= BM_FACE;
365         bm->elem_table_dirty |= BM_FACE;
366
367         bm->totface++;
368
369 #ifdef USE_BMESH_HOLES
370         f->totbounds = 0;
371 #endif
372
373         return f;
374 }
375
376 /**
377  * Main face creation function
378  *
379  * \param bm  The mesh
380  * \param verts  A sorted array of verts size of len
381  * \param edges  A sorted array of edges size of len
382  * \param len  Length of the face
383  * \param create_flag  Options for creating the face
384  */
385 BMFace *BM_face_create(BMesh *bm, BMVert **verts, BMEdge **edges, const int len,
386                        const BMFace *f_example, const eBMCreateFlag create_flag)
387 {
388         BMFace *f = NULL;
389         BMLoop *l, *startl, *lastl;
390         int i;
391         
392         if (len == 0) {
393                 /* just return NULL for now */
394                 return NULL;
395         }
396
397         if (create_flag & BM_CREATE_NO_DOUBLE) {
398                 /* Check if face already exists */
399                 const bool is_overlap = BM_face_exists(verts, len, &f);
400                 if (is_overlap) {
401                         return f;
402                 }
403                 else {
404                         BLI_assert(f == NULL);
405                 }
406         }
407
408         f = bm_face_create__internal(bm);
409
410         startl = lastl = bm_face_boundary_add(bm, f, verts[0], edges[0], create_flag);
411         
412         startl->v = verts[0];
413         startl->e = edges[0];
414         for (i = 1; i < len; i++) {
415                 l = bm_loop_create(bm, verts[i], edges[i], f, edges[i]->l, create_flag);
416                 
417                 l->f = f;
418                 bmesh_radial_append(edges[i], l);
419
420                 l->prev = lastl;
421                 lastl->next = l;
422                 lastl = l;
423         }
424         
425         startl->prev = lastl;
426         lastl->next = startl;
427         
428         f->len = len;
429         
430         if (!(create_flag & BM_CREATE_SKIP_CD)) {
431                 if (f_example) {
432                         BM_elem_attrs_copy(bm, bm, f_example, f);
433                 }
434                 else {
435                         CustomData_bmesh_set_default(&bm->pdata, &f->head.data);
436                 }
437         }
438
439         BM_CHECK_ELEMENT(f);
440
441         return f;
442 }
443
444 /**
445  * Wrapper for #BM_face_create when you don't have an edge array
446  */
447 BMFace *BM_face_create_verts(BMesh *bm, BMVert **vert_arr, const int len,
448                              const BMFace *f_example, const eBMCreateFlag create_flag, const bool create_edges)
449 {
450         BMEdge **edge_arr = BLI_array_alloca(edge_arr, len);
451         int i, i_prev = len - 1;
452
453         if (create_edges) {
454                 for (i = 0; i < len; i++) {
455                         edge_arr[i_prev] = BM_edge_create(bm, vert_arr[i_prev], vert_arr[i], NULL, BM_CREATE_NO_DOUBLE);
456                         i_prev = i;
457                 }
458         }
459         else {
460                 for (i = 0; i < len; i++) {
461                         edge_arr[i_prev] = BM_edge_exists(vert_arr[i_prev], vert_arr[i]);
462                         if (edge_arr[i_prev] == NULL) {
463                                 return NULL;
464                         }
465                         i_prev = i;
466                 }
467         }
468
469         return BM_face_create(bm, vert_arr, edge_arr, len, f_example, create_flag);
470 }
471
472 #ifndef NDEBUG
473
474 /**
475  * Check the element is valid.
476  *
477  * BMESH_TODO, when this raises an error the output is incredible confusing.
478  * need to have some nice way to print/debug what the hecks going on.
479  */
480 int bmesh_elem_check(void *element, const char htype)
481 {
482         BMHeader *head = element;
483         int err = 0;
484
485         if (!element)
486                 return 1;
487
488         if (head->htype != htype)
489                 return 2;
490         
491         switch (htype) {
492                 case BM_VERT:
493                 {
494                         BMVert *v = element;
495                         if (v->e && v->e->head.htype != BM_EDGE) {
496                                 err |= 4;
497                         }
498                         break;
499                 }
500                 case BM_EDGE:
501                 {
502                         BMEdge *e = element;
503                         if (e->l && e->l->head.htype != BM_LOOP)
504                                 err |= 8;
505                         if (e->l && e->l->f->head.htype != BM_FACE)
506                                 err |= 16;
507                         if (e->v1_disk_link.prev == NULL ||
508                             e->v2_disk_link.prev == NULL ||
509                             e->v1_disk_link.next == NULL ||
510                             e->v2_disk_link.next == NULL)
511                         {
512                                 err |= 32;
513                         }
514                         if (e->l && (e->l->radial_next == NULL || e->l->radial_prev == NULL))
515                                 err |= 64;
516                         if (e->l && e->l->f->len <= 0)
517                                 err |= 128;
518                         break;
519                 }
520                 case BM_LOOP:
521                 {
522                         BMLoop *l = element, *l2;
523                         int i;
524
525                         if (l->f->head.htype != BM_FACE)
526                                 err |= 256;
527                         if (l->e->head.htype != BM_EDGE)
528                                 err |= 512;
529                         if (l->v->head.htype != BM_VERT)
530                                 err |= 1024;
531                         if (!BM_vert_in_edge(l->e, l->v)) {
532                                 fprintf(stderr, "%s: fatal bmesh error (vert not in edge)! (bmesh internal error)\n", __func__);
533                                 err |= 2048;
534                         }
535
536                         if (l->radial_next == NULL || l->radial_prev == NULL)
537                                 err |= (1 << 12);
538                         if (l->f->len <= 0)
539                                 err |= (1 << 13);
540
541                         /* validate boundary loop -- invalid for hole loops, of course,
542                          * but we won't be allowing those for a while yet */
543                         l2 = l;
544                         i = 0;
545                         do {
546                                 if (i >= BM_NGON_MAX) {
547                                         break;
548                                 }
549
550                                 i++;
551                         } while ((l2 = l2->next) != l);
552
553                         if (i != l->f->len || l2 != l)
554                                 err |= (1 << 14);
555
556                         if (!bmesh_radial_validate(bmesh_radial_length(l), l))
557                                 err |= (1 << 15);
558
559                         break;
560                 }
561                 case BM_FACE:
562                 {
563                         BMFace *f = element;
564                         BMLoop *l_iter;
565                         BMLoop *l_first;
566                         int len = 0;
567
568 #ifdef USE_BMESH_HOLES
569                         if (!f->loops.first)
570 #else
571                         if (!f->l_first)
572 #endif
573                         {
574                                 err |= (1 << 16);
575                         }
576                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
577                         do {
578                                 if (l_iter->f != f) {
579                                         fprintf(stderr, "%s: loop inside one face points to another! (bmesh internal error)\n", __func__);
580                                         err |= (1 << 17);
581                                 }
582
583                                 if (!l_iter->e)
584                                         err |= (1 << 18);
585                                 if (!l_iter->v)
586                                         err |= (1 << 19);
587                                 if (!BM_vert_in_edge(l_iter->e, l_iter->v) || !BM_vert_in_edge(l_iter->e, l_iter->next->v)) {
588                                         err |= (1 << 20);
589                                 }
590
591                                 if (!bmesh_radial_validate(bmesh_radial_length(l_iter), l_iter))
592                                         err |= (1 << 21);
593
594                                 if (!bmesh_disk_count(l_iter->v) || !bmesh_disk_count(l_iter->next->v))
595                                         err |= (1 << 22);
596
597                                 len++;
598                         } while ((l_iter = l_iter->next) != l_first);
599
600                         if (len != f->len)
601                                 err |= (1 << 23);
602                         break;
603                 }
604                 default:
605                         BLI_assert(0);
606                         break;
607         }
608
609         BMESH_ASSERT(err == 0);
610
611         return err;
612 }
613
614 #endif /* NDEBUG */
615
616 /**
617  * low level function, only frees the vert,
618  * doesn't change or adjust surrounding geometry
619  */
620 static void bm_kill_only_vert(BMesh *bm, BMVert *v)
621 {
622         bm->totvert--;
623         bm->elem_index_dirty |= BM_VERT;
624         bm->elem_table_dirty |= BM_VERT;
625
626         BM_select_history_remove(bm, v);
627
628         if (v->head.data)
629                 CustomData_bmesh_free_block(&bm->vdata, &v->head.data);
630
631         if (bm->vtoolflagpool) {
632                 BLI_mempool_free(bm->vtoolflagpool, v->oflags);
633         }
634         BLI_mempool_free(bm->vpool, v);
635 }
636
637 /**
638  * low level function, only frees the edge,
639  * doesn't change or adjust surrounding geometry
640  */
641 static void bm_kill_only_edge(BMesh *bm, BMEdge *e)
642 {
643         bm->totedge--;
644         bm->elem_index_dirty |= BM_EDGE;
645         bm->elem_table_dirty |= BM_EDGE;
646
647         BM_select_history_remove(bm, (BMElem *)e);
648
649         if (e->head.data)
650                 CustomData_bmesh_free_block(&bm->edata, &e->head.data);
651
652         if (bm->etoolflagpool) {
653                 BLI_mempool_free(bm->etoolflagpool, e->oflags);
654         }
655         BLI_mempool_free(bm->epool, e);
656 }
657
658 /**
659  * low level function, only frees the face,
660  * doesn't change or adjust surrounding geometry
661  */
662 static void bm_kill_only_face(BMesh *bm, BMFace *f)
663 {
664         if (bm->act_face == f)
665                 bm->act_face = NULL;
666
667         bm->totface--;
668         bm->elem_index_dirty |= BM_FACE;
669         bm->elem_table_dirty |= BM_FACE;
670
671         BM_select_history_remove(bm, (BMElem *)f);
672
673         if (f->head.data)
674                 CustomData_bmesh_free_block(&bm->pdata, &f->head.data);
675
676         if (bm->ftoolflagpool) {
677                 BLI_mempool_free(bm->ftoolflagpool, f->oflags);
678         }
679         BLI_mempool_free(bm->fpool, f);
680 }
681
682 /**
683  * low level function, only frees the loop,
684  * doesn't change or adjust surrounding geometry
685  */
686 static void bm_kill_only_loop(BMesh *bm, BMLoop *l)
687 {
688         bm->totloop--;
689         bm->elem_index_dirty |= BM_LOOP;
690         if (l->head.data)
691                 CustomData_bmesh_free_block(&bm->ldata, &l->head.data);
692
693         BLI_mempool_free(bm->lpool, l);
694 }
695
696 /**
697  * kills all edges associated with \a f, along with any other faces containing
698  * those edges
699  */
700 void BM_face_edges_kill(BMesh *bm, BMFace *f)
701 {
702         BMEdge **edges = BLI_array_alloca(edges, f->len);
703         BMLoop *l_iter;
704         BMLoop *l_first;
705         int i = 0;
706         
707         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
708         do {
709                 edges[i++] = l_iter->e;
710         } while ((l_iter = l_iter->next) != l_first);
711         
712         for (i = 0; i < f->len; i++) {
713                 BM_edge_kill(bm, edges[i]);
714         }
715 }
716
717 /**
718  * kills all verts associated with \a f, along with any other faces containing
719  * those vertices
720  */
721 void BM_face_verts_kill(BMesh *bm, BMFace *f)
722 {
723         BMVert **verts = BLI_array_alloca(verts, f->len);
724         BMLoop *l_iter;
725         BMLoop *l_first;
726         int i = 0;
727         
728         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
729         do {
730                 verts[i++] = l_iter->v;
731         } while ((l_iter = l_iter->next) != l_first);
732         
733         for (i = 0; i < f->len; i++) {
734                 BM_vert_kill(bm, verts[i]);
735         }
736 }
737
738 /**
739  * Kills \a f and its loops.
740  */
741 void BM_face_kill(BMesh *bm, BMFace *f)
742 {
743 #ifdef USE_BMESH_HOLES
744         BMLoopList *ls, *ls_next;
745 #endif
746
747         BM_CHECK_ELEMENT(f);
748
749 #ifdef USE_BMESH_HOLES
750         for (ls = f->loops.first; ls; ls = ls_next)
751 #else
752         if (f->l_first)
753 #endif
754         {
755                 BMLoop *l_iter, *l_next, *l_first;
756
757 #ifdef USE_BMESH_HOLES
758                 ls_next = ls->next;
759                 l_iter = l_first = ls->first;
760 #else
761                 l_iter = l_first = f->l_first;
762 #endif
763
764                 do {
765                         l_next = l_iter->next;
766
767                         bmesh_radial_loop_remove(l_iter, l_iter->e);
768                         bm_kill_only_loop(bm, l_iter);
769
770                 } while ((l_iter = l_next) != l_first);
771
772 #ifdef USE_BMESH_HOLES
773                 BLI_mempool_free(bm->looplistpool, ls);
774 #endif
775         }
776
777         bm_kill_only_face(bm, f);
778 }
779 /**
780  * kills \a e and all faces that use it.
781  */
782 void BM_edge_kill(BMesh *bm, BMEdge *e)
783 {
784
785         bmesh_disk_edge_remove(e, e->v1);
786         bmesh_disk_edge_remove(e, e->v2);
787
788         if (e->l) {
789                 BMLoop *l = e->l, *lnext, *startl = e->l;
790
791                 do {
792                         lnext = l->radial_next;
793                         if (lnext->f == l->f) {
794                                 BM_face_kill(bm, l->f);
795                                 break;
796                         }
797                         
798                         BM_face_kill(bm, l->f);
799
800                         if (l == lnext)
801                                 break;
802                         l = lnext;
803                 } while (l != startl);
804         }
805         
806         bm_kill_only_edge(bm, e);
807 }
808
809 /**
810  * kills \a v and all edges that use it.
811  */
812 void BM_vert_kill(BMesh *bm, BMVert *v)
813 {
814         if (v->e) {
815                 BMEdge *e, *e_next;
816                 
817                 e = v->e;
818                 while (v->e) {
819                         e_next = bmesh_disk_edge_next(e, v);
820                         BM_edge_kill(bm, e);
821                         e = e_next;
822                 }
823         }
824
825         bm_kill_only_vert(bm, v);
826 }
827
828 /********** private disk and radial cycle functions ********** */
829
830 /**
831  * return the length of the face, should always equal \a l->f->len
832  */
833 static int UNUSED_FUNCTION(bm_loop_length)(BMLoop *l)
834 {
835         BMLoop *l_first = l;
836         int i = 0;
837
838         do {
839                 i++;
840         } while ((l = l->next) != l_first);
841
842         return i;
843 }
844
845 /**
846  * \brief Loop Reverse
847  *
848  * Changes the winding order of a face from CW to CCW or vice versa.
849  * This euler is a bit peculiar in comparison to others as it is its
850  * own inverse.
851  *
852  * BMESH_TODO: reinsert validation code.
853  *
854  * \return Success
855  */
856 static bool bm_loop_reverse_loop(BMesh *bm, BMFace *f
857 #ifdef USE_BMESH_HOLES
858                                 , BMLoopList *lst
859 #endif
860                                 )
861 {
862
863 #ifdef USE_BMESH_HOLES
864         BMLoop *l_first = lst->first;
865 #else
866         BMLoop *l_first = f->l_first;
867 #endif
868
869         const int len = f->len;
870         const bool do_disps = CustomData_has_layer(&bm->ldata, CD_MDISPS);
871         BMLoop *l_iter, *oldprev, *oldnext;
872         BMEdge **edar = BLI_array_alloca(edar, len);
873         int i, j, edok;
874
875         for (i = 0, l_iter = l_first; i < len; i++, l_iter = l_iter->next) {
876                 bmesh_radial_loop_remove(l_iter, (edar[i] = l_iter->e));
877         }
878
879         /* actually reverse the loop */
880         for (i = 0, l_iter = l_first; i < len; i++) {
881                 oldnext = l_iter->next;
882                 oldprev = l_iter->prev;
883                 l_iter->next = oldprev;
884                 l_iter->prev = oldnext;
885                 l_iter = oldnext;
886                 
887                 if (do_disps) {
888                         float (*co)[3];
889                         int x, y, sides;
890                         MDisps *md;
891                         
892                         md = CustomData_bmesh_get(&bm->ldata, l_iter->head.data, CD_MDISPS);
893                         if (!md->totdisp || !md->disps)
894                                 continue;
895
896                         sides = (int)sqrt(md->totdisp);
897                         co = md->disps;
898                         
899                         for (x = 0; x < sides; x++) {
900                                 for (y = 0; y < x; y++) {
901                                         swap_v3_v3(co[y * sides + x], co[sides * x + y]);
902                                         SWAP(float, co[y * sides + x][0], co[y * sides + x][1]);
903                                         SWAP(float, co[x * sides + y][0], co[x * sides + y][1]);
904                                 }
905                                 SWAP(float, co[x * sides + x][0], co[x * sides + x][1]);
906                         }
907                 }
908         }
909
910         if (len == 2) { /* two edged face */
911                 /* do some verification here! */
912                 l_first->e = edar[1];
913                 l_first->next->e = edar[0];
914         }
915         else {
916                 for (i = 0, l_iter = l_first; i < len; i++, l_iter = l_iter->next) {
917                         edok = 0;
918                         for (j = 0; j < len; j++) {
919                                 edok = BM_verts_in_edge(l_iter->v, l_iter->next->v, edar[j]);
920                                 if (edok) {
921                                         l_iter->e = edar[j];
922                                         break;
923                                 }
924                         }
925                 }
926         }
927         /* rebuild radial */
928         for (i = 0, l_iter = l_first; i < len; i++, l_iter = l_iter->next)
929                 bmesh_radial_append(l_iter->e, l_iter);
930
931         /* validate radial */
932         for (i = 0, l_iter = l_first; i < len; i++, l_iter = l_iter->next) {
933                 BM_CHECK_ELEMENT(l_iter);
934                 BM_CHECK_ELEMENT(l_iter->e);
935                 BM_CHECK_ELEMENT(l_iter->v);
936                 BM_CHECK_ELEMENT(l_iter->f);
937         }
938
939         BM_CHECK_ELEMENT(f);
940
941         /* Loop indices are no more valid! */
942         bm->elem_index_dirty |= BM_LOOP;
943
944         return true;
945 }
946
947 /**
948  * \brief Flip the faces direction
949  */
950 bool bmesh_loop_reverse(BMesh *bm, BMFace *f)
951 {
952 #ifdef USE_BMESH_HOLES
953         return bm_loop_reverse_loop(bm, f, f->loops.first);
954 #else
955         return bm_loop_reverse_loop(bm, f);
956 #endif
957 }
958
959 static void bm_elements_systag_enable(void *veles, int tot, int flag)
960 {
961         BMHeader **eles = veles;
962         int i;
963
964         for (i = 0; i < tot; i++) {
965                 BM_ELEM_API_FLAG_ENABLE((BMElemF *)eles[i], flag);
966         }
967 }
968
969 static void bm_elements_systag_disable(void *veles, int tot, int flag)
970 {
971         BMHeader **eles = veles;
972         int i;
973
974         for (i = 0; i < tot; i++) {
975                 BM_ELEM_API_FLAG_DISABLE((BMElemF *)eles[i], flag);
976         }
977 }
978
979 static int count_flagged_radial(BMesh *bm, BMLoop *l, int flag)
980 {
981         BMLoop *l2 = l;
982         int i = 0, c = 0;
983
984         do {
985                 if (UNLIKELY(!l2)) {
986                         BMESH_ASSERT(0);
987                         goto error;
988                 }
989                 
990                 i += BM_ELEM_API_FLAG_TEST(l2->f, flag) ? 1 : 0;
991                 l2 = l2->radial_next;
992                 if (UNLIKELY(c >= BM_LOOP_RADIAL_MAX)) {
993                         BMESH_ASSERT(0);
994                         goto error;
995                 }
996                 c++;
997         } while (l2 != l);
998
999         return i;
1000
1001 error:
1002         BMO_error_raise(bm, bm->currentop, BMERR_MESH_ERROR, NULL);
1003         return 0;
1004 }
1005
1006 static int UNUSED_FUNCTION(count_flagged_disk)(BMVert *v, int flag)
1007 {
1008         BMEdge *e = v->e;
1009         int i = 0;
1010
1011         if (!e)
1012                 return 0;
1013
1014         do {
1015                 i += BM_ELEM_API_FLAG_TEST(e, flag) ? 1 : 0;
1016         } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
1017
1018         return i;
1019 }
1020
1021 static bool disk_is_flagged(BMVert *v, int flag)
1022 {
1023         BMEdge *e = v->e;
1024
1025         if (!e)
1026                 return false;
1027
1028         do {
1029                 BMLoop *l = e->l;
1030
1031                 if (!l) {
1032                         return false;
1033                 }
1034                 
1035                 if (bmesh_radial_length(l) == 1)
1036                         return false;
1037                 
1038                 do {
1039                         if (!BM_ELEM_API_FLAG_TEST(l->f, flag))
1040                                 return false;
1041                 } while ((l = l->radial_next) != e->l);
1042         } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
1043
1044         return true;
1045 }
1046
1047 /* Mid-level Topology Manipulation Functions */
1048
1049 /**
1050  * \brief Join Connected Faces
1051  *
1052  * Joins a collected group of faces into one. Only restriction on
1053  * the input data is that the faces must be connected to each other.
1054  *
1055  * \return The newly created combine BMFace.
1056  *
1057  * \note If a pair of faces share multiple edges,
1058  * the pair of faces will be joined at every edge.
1059  *
1060  * \note this is a generic, flexible join faces function,
1061  * almost everything uses this, including #BM_faces_join_pair
1062  */
1063 BMFace *BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del)
1064 {
1065         BMFace *f, *f_new;
1066 #ifdef USE_BMESH_HOLES
1067         BMLoopList *lst;
1068         ListBase holes = {NULL, NULL};
1069 #endif
1070         BMLoop *l_iter;
1071         BMLoop *l_first;
1072         BMEdge **edges = NULL;
1073         BMEdge **deledges = NULL;
1074         BMVert **delverts = NULL;
1075         BLI_array_staticdeclare(edges,    BM_DEFAULT_NGON_STACK_SIZE);
1076         BLI_array_staticdeclare(deledges, BM_DEFAULT_NGON_STACK_SIZE);
1077         BLI_array_staticdeclare(delverts, BM_DEFAULT_NGON_STACK_SIZE);
1078         BMVert *v1 = NULL, *v2 = NULL;
1079         const char *err = NULL;
1080         int i, tote = 0;
1081
1082         if (UNLIKELY(!totface)) {
1083                 BMESH_ASSERT(0);
1084                 return NULL;
1085         }
1086
1087         if (totface == 1)
1088                 return faces[0];
1089
1090         bm_elements_systag_enable(faces, totface, _FLAG_JF);
1091
1092         for (i = 0; i < totface; i++) {
1093                 f = faces[i];
1094                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1095                 do {
1096                         int rlen = count_flagged_radial(bm, l_iter, _FLAG_JF);
1097
1098                         if (rlen > 2) {
1099                                 err = N_("Input faces do not form a contiguous manifold region");
1100                                 goto error;
1101                         }
1102                         else if (rlen == 1) {
1103                                 BLI_array_append(edges, l_iter->e);
1104
1105                                 if (!v1) {
1106                                         v1 = l_iter->v;
1107                                         v2 = BM_edge_other_vert(l_iter->e, l_iter->v);
1108                                 }
1109                                 tote++;
1110                         }
1111                         else if (rlen == 2) {
1112                                 int d1, d2;
1113
1114                                 d1 = disk_is_flagged(l_iter->e->v1, _FLAG_JF);
1115                                 d2 = disk_is_flagged(l_iter->e->v2, _FLAG_JF);
1116
1117                                 if (!d1 && !d2 && !BM_ELEM_API_FLAG_TEST(l_iter->e, _FLAG_JF)) {
1118                                         /* don't remove an edge it makes up the side of another face
1119                                          * else this will remove the face as well - campbell */
1120                                         if (BM_edge_face_count(l_iter->e) <= 2) {
1121                                                 if (do_del) {
1122                                                         BLI_array_append(deledges, l_iter->e);
1123                                                 }
1124                                                 BM_ELEM_API_FLAG_ENABLE(l_iter->e, _FLAG_JF);
1125                                         }
1126                                 }
1127                                 else {
1128                                         if (d1 && !BM_ELEM_API_FLAG_TEST(l_iter->e->v1, _FLAG_JF)) {
1129                                                 if (do_del) {
1130                                                         BLI_array_append(delverts, l_iter->e->v1);
1131                                                 }
1132                                                 BM_ELEM_API_FLAG_ENABLE(l_iter->e->v1, _FLAG_JF);
1133                                         }
1134
1135                                         if (d2 && !BM_ELEM_API_FLAG_TEST(l_iter->e->v2, _FLAG_JF)) {
1136                                                 if (do_del) {
1137                                                         BLI_array_append(delverts, l_iter->e->v2);
1138                                                 }
1139                                                 BM_ELEM_API_FLAG_ENABLE(l_iter->e->v2, _FLAG_JF);
1140                                         }
1141                                 }
1142                         }
1143                 } while ((l_iter = l_iter->next) != l_first);
1144
1145 #ifdef USE_BMESH_HOLES
1146                 for (lst = f->loops.first; lst; lst = lst->next) {
1147                         if (lst == f->loops.first) {
1148                                 continue;
1149                         }
1150
1151                         BLI_remlink(&f->loops, lst);
1152                         BLI_addtail(&holes, lst);
1153                 }
1154 #endif
1155
1156         }
1157
1158         /* create region face */
1159         f_new = tote ? BM_face_create_ngon(bm, v1, v2, edges, tote, faces[0], BM_CREATE_NOP) : NULL;
1160         if (UNLIKELY(!f_new || BMO_error_occurred(bm))) {
1161                 if (!BMO_error_occurred(bm))
1162                         err = N_("Invalid boundary region to join faces");
1163                 goto error;
1164         }
1165
1166         /* copy over loop data */
1167         l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
1168         do {
1169                 BMLoop *l2 = l_iter->radial_next;
1170
1171                 do {
1172                         if (BM_ELEM_API_FLAG_TEST(l2->f, _FLAG_JF))
1173                                 break;
1174                         l2 = l2->radial_next;
1175                 } while (l2 != l_iter);
1176
1177                 if (l2 != l_iter) {
1178                         /* I think this is correct? */
1179                         if (l2->v != l_iter->v) {
1180                                 l2 = l2->next;
1181                         }
1182
1183                         BM_elem_attrs_copy(bm, bm, l2, l_iter);
1184                 }
1185         } while ((l_iter = l_iter->next) != l_first);
1186
1187 #ifdef USE_BMESH_HOLES
1188         /* add holes */
1189         BLI_movelisttolist(&f_new->loops, &holes);
1190 #endif
1191
1192         /* update loop face pointer */
1193 #ifdef USE_BMESH_HOLES
1194         for (lst = f_new->loops.first; lst; lst = lst->next)
1195 #endif
1196         {
1197 #ifdef USE_BMESH_HOLES
1198                 l_iter = l_first = lst->first;
1199 #else
1200                 l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
1201 #endif
1202                 do {
1203                         l_iter->f = f_new;
1204                 } while ((l_iter = l_iter->next) != l_first);
1205         }
1206
1207         bm_elements_systag_disable(faces, totface, _FLAG_JF);
1208         BM_ELEM_API_FLAG_DISABLE(f_new, _FLAG_JF);
1209
1210         /* handle multi-res data */
1211         if (CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
1212                 l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
1213                 do {
1214                         for (i = 0; i < totface; i++) {
1215                                 BM_loop_interp_multires(bm, l_iter, faces[i]);
1216                         }
1217                 } while ((l_iter = l_iter->next) != l_first);
1218         }
1219
1220         /* delete old geometry */
1221         if (do_del) {
1222                 for (i = 0; i < BLI_array_count(deledges); i++) {
1223                         BM_edge_kill(bm, deledges[i]);
1224                 }
1225
1226                 for (i = 0; i < BLI_array_count(delverts); i++) {
1227                         BM_vert_kill(bm, delverts[i]);
1228                 }
1229         }
1230         else {
1231                 /* otherwise we get both old and new faces */
1232                 for (i = 0; i < totface; i++) {
1233                         BM_face_kill(bm, faces[i]);
1234                 }
1235         }
1236         
1237         BLI_array_free(edges);
1238         BLI_array_free(deledges);
1239         BLI_array_free(delverts);
1240
1241         BM_CHECK_ELEMENT(f_new);
1242         return f_new;
1243
1244 error:
1245         bm_elements_systag_disable(faces, totface, _FLAG_JF);
1246         BLI_array_free(edges);
1247         BLI_array_free(deledges);
1248         BLI_array_free(delverts);
1249
1250         if (err) {
1251                 BMO_error_raise(bm, bm->currentop, BMERR_DISSOLVEFACES_FAILED, err);
1252         }
1253         return NULL;
1254 }
1255
1256 static BMFace *bm_face_create__sfme(BMesh *bm, BMFace *f_example)
1257 {
1258         BMFace *f;
1259 #ifdef USE_BMESH_HOLES
1260         BMLoopList *lst;
1261 #endif
1262
1263         f = bm_face_create__internal(bm);
1264
1265 #ifdef USE_BMESH_HOLES
1266         lst = BLI_mempool_calloc(bm->looplistpool);
1267         BLI_addtail(&f->loops, lst);
1268 #endif
1269
1270 #ifdef USE_BMESH_HOLES
1271         f->totbounds = 1;
1272 #endif
1273
1274         BM_elem_attrs_copy(bm, bm, f_example, f);
1275
1276         return f;
1277 }
1278
1279 /**
1280  * \brief Split Face Make Edge (SFME)
1281  *
1282  * \warning this is a low level function, most likely you want to use #BM_face_split()
1283  *
1284  * Takes as input two vertices in a single face. An edge is created which divides the original face
1285  * into two distinct regions. One of the regions is assigned to the original face and it is closed off.
1286  * The second region has a new face assigned to it.
1287  *
1288  * \par Examples:
1289  * <pre>
1290  *     Before:               After:
1291  *      +--------+           +--------+
1292  *      |        |           |        |
1293  *      |        |           |   f1   |
1294  *     v1   f1   v2          v1======v2
1295  *      |        |           |   f2   |
1296  *      |        |           |        |
1297  *      +--------+           +--------+
1298  * </pre>
1299  *
1300  * \note the input vertices can be part of the same edge. This will
1301  * result in a two edged face. This is desirable for advanced construction
1302  * tools and particularly essential for edge bevel. Because of this it is
1303  * up to the caller to decide what to do with the extra edge.
1304  *
1305  * \note If \a holes is NULL, then both faces will lose
1306  * all holes from the original face.  Also, you cannot split between
1307  * a hole vert and a boundary vert; that case is handled by higher-
1308  * level wrapping functions (when holes are fully implemented, anyway).
1309  *
1310  * \note that holes represents which holes goes to the new face, and of
1311  * course this requires removing them from the existing face first, since
1312  * you cannot have linked list links inside multiple lists.
1313  *
1314  * \return A BMFace pointer
1315  */
1316 BMFace *bmesh_sfme(BMesh *bm, BMFace *f, BMLoop *l_v1, BMLoop *l_v2,
1317                    BMLoop **r_l,
1318 #ifdef USE_BMESH_HOLES
1319                    ListBase *holes,
1320 #endif
1321                    BMEdge *example,
1322                    const bool no_double
1323                    )
1324 {
1325 #ifdef USE_BMESH_HOLES
1326         BMLoopList *lst, *lst2;
1327 #else
1328         int first_loop_f1;
1329 #endif
1330
1331         BMFace *f2;
1332         BMLoop *l_iter, *l_first;
1333         BMLoop *l_f1 = NULL, *l_f2 = NULL;
1334         BMEdge *e;
1335         BMVert *v1 = l_v1->v, *v2 = l_v2->v;
1336         int f1len, f2len;
1337
1338         BLI_assert(f == l_v1->f && f == l_v2->f);
1339
1340         /* allocate new edge between v1 and v2 */
1341         e = BM_edge_create(bm, v1, v2, example, no_double ? BM_CREATE_NO_DOUBLE : BM_CREATE_NOP);
1342
1343         f2 = bm_face_create__sfme(bm, f);
1344         l_f1 = bm_loop_create(bm, v2, e, f, l_v2, 0);
1345         l_f2 = bm_loop_create(bm, v1, e, f2, l_v1, 0);
1346
1347         l_f1->prev = l_v2->prev;
1348         l_f2->prev = l_v1->prev;
1349         l_v2->prev->next = l_f1;
1350         l_v1->prev->next = l_f2;
1351
1352         l_f1->next = l_v1;
1353         l_f2->next = l_v2;
1354         l_v1->prev = l_f1;
1355         l_v2->prev = l_f2;
1356
1357 #ifdef USE_BMESH_HOLES
1358         lst = f->loops.first;
1359         lst2 = f2->loops.first;
1360
1361         lst2->first = lst2->last = l_f2;
1362         lst->first = lst->last = l_f1;
1363 #else
1364         /* find which of the faces the original first loop is in */
1365         l_iter = l_first = l_f1;
1366         first_loop_f1 = 0;
1367         do {
1368                 if (l_iter == f->l_first)
1369                         first_loop_f1 = 1;
1370         } while ((l_iter = l_iter->next) != l_first);
1371
1372         if (first_loop_f1) {
1373                 /* original first loop was in f1, find a suitable first loop for f2
1374                  * which is as similar as possible to f1. the order matters for tools
1375                  * such as duplifaces. */
1376                 if (f->l_first->prev == l_f1)
1377                         f2->l_first = l_f2->prev;
1378                 else if (f->l_first->next == l_f1)
1379                         f2->l_first = l_f2->next;
1380                 else
1381                         f2->l_first = l_f2;
1382         }
1383         else {
1384                 /* original first loop was in f2, further do same as above */
1385                 f2->l_first = f->l_first;
1386
1387                 if (f->l_first->prev == l_f2)
1388                         f->l_first = l_f1->prev;
1389                 else if (f->l_first->next == l_f2)
1390                         f->l_first = l_f1->next;
1391                 else
1392                         f->l_first = l_f1;
1393         }
1394 #endif
1395
1396         /* validate both loop */
1397         /* I don't know how many loops are supposed to be in each face at this point! FIXME */
1398
1399         /* go through all of f2's loops and make sure they point to it properly */
1400         l_iter = l_first = BM_FACE_FIRST_LOOP(f2);
1401         f2len = 0;
1402         do {
1403                 l_iter->f = f2;
1404                 f2len++;
1405         } while ((l_iter = l_iter->next) != l_first);
1406
1407         /* link up the new loops into the new edges radial */
1408         bmesh_radial_append(e, l_f1);
1409         bmesh_radial_append(e, l_f2);
1410
1411         f2->len = f2len;
1412
1413         f1len = 0;
1414         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1415         do {
1416                 f1len++;
1417         } while ((l_iter = l_iter->next) != l_first);
1418
1419         f->len = f1len;
1420
1421         if (r_l) *r_l = l_f2;
1422
1423 #ifdef USE_BMESH_HOLES
1424         if (holes) {
1425                 BLI_movelisttolist(&f2->loops, holes);
1426         }
1427         else {
1428                 /* this code is not significant until holes actually work */
1429                 //printf("warning: call to split face euler without holes argument; holes will be tossed.\n");
1430                 for (lst = f->loops.last; lst != f->loops.first; lst = lst2) {
1431                         lst2 = lst->prev;
1432                         BLI_mempool_free(bm->looplistpool, lst);
1433                 }
1434         }
1435 #endif
1436
1437         BM_CHECK_ELEMENT(e);
1438         BM_CHECK_ELEMENT(f);
1439         BM_CHECK_ELEMENT(f2);
1440         
1441         return f2;
1442 }
1443
1444 /**
1445  * \brief Split Edge Make Vert (SEMV)
1446  *
1447  * Takes \a e edge and splits it into two, creating a new vert.
1448  * \a tv should be one end of \a e : the newly created edge
1449  * will be attached to that end and is returned in \a r_e.
1450  *
1451  * \par Examples:
1452  *
1453  * <pre>
1454  *                     E
1455  *     Before: OV-------------TV
1456  *                 E       RE
1457  *     After:  OV------NV-----TV
1458  * </pre>
1459  *
1460  * \return The newly created BMVert pointer.
1461  */
1462 BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **r_e)
1463 {
1464         BMLoop *l_next;
1465         BMEdge *e_new;
1466         BMVert *v_new, *v_old;
1467 #ifndef NDEBUG
1468         int valence1, valence2;
1469         bool edok;
1470         int i;
1471 #endif
1472
1473         BLI_assert(BM_vert_in_edge(e, tv) != false);
1474
1475         v_old = BM_edge_other_vert(e, tv);
1476
1477 #ifndef NDEBUG
1478         valence1 = bmesh_disk_count(v_old);
1479         valence2 = bmesh_disk_count(tv);
1480 #endif
1481
1482         v_new = BM_vert_create(bm, tv->co, tv, BM_CREATE_NOP);
1483         e_new = BM_edge_create(bm, v_new, tv, e, BM_CREATE_NOP);
1484
1485         bmesh_disk_edge_remove(e_new, tv);
1486         bmesh_disk_edge_remove(e_new, v_new);
1487
1488         /* remove e from tv's disk cycle */
1489         bmesh_disk_edge_remove(e, tv);
1490
1491         /* swap out tv for v_new in e */
1492         bmesh_edge_swapverts(e, tv, v_new);
1493
1494         /* add e to v_new's disk cycle */
1495         bmesh_disk_edge_append(e, v_new);
1496
1497         /* add e_new to v_new's disk cycle */
1498         bmesh_disk_edge_append(e_new, v_new);
1499
1500         /* add e_new to tv's disk cycle */
1501         bmesh_disk_edge_append(e_new, tv);
1502
1503 #ifndef NDEBUG
1504         /* verify disk cycles */
1505         edok = bmesh_disk_validate(valence1, v_old->e, v_old);
1506         BMESH_ASSERT(edok != false);
1507         edok = bmesh_disk_validate(valence2, tv->e, tv);
1508         BMESH_ASSERT(edok != false);
1509         edok = bmesh_disk_validate(2, v_new->e, v_new);
1510         BMESH_ASSERT(edok != false);
1511 #endif
1512
1513         /* Split the radial cycle if present */
1514         l_next = e->l;
1515         e->l = NULL;
1516         if (l_next) {
1517                 BMLoop *l_new, *l;
1518 #ifndef NDEBUG
1519                 int radlen = bmesh_radial_length(l_next);
1520 #endif
1521                 int first1 = 0, first2 = 0;
1522
1523                 /* Take the next loop. Remove it from radial. Split it. Append to appropriate radials */
1524                 while (l_next) {
1525                         l = l_next;
1526                         l->f->len++;
1527                         l_next = l_next != l_next->radial_next ? l_next->radial_next : NULL;
1528                         bmesh_radial_loop_remove(l, NULL);
1529
1530                         l_new = bm_loop_create(bm, NULL, NULL, l->f, l, 0);
1531                         l_new->prev = l;
1532                         l_new->next = (l->next);
1533                         l_new->prev->next = l_new;
1534                         l_new->next->prev = l_new;
1535                         l_new->v = v_new;
1536
1537                         /* assign the correct edge to the correct loop */
1538                         if (BM_verts_in_edge(l_new->v, l_new->next->v, e)) {
1539                                 l_new->e = e;
1540                                 l->e = e_new;
1541
1542                                 /* append l into e_new's rad cycle */
1543                                 if (!first1) {
1544                                         first1 = 1;
1545                                         l->radial_next = l->radial_prev = NULL;
1546                                 }
1547
1548                                 if (!first2) {
1549                                         first2 = 1;
1550                                         l->radial_next = l->radial_prev = NULL;
1551                                 }
1552                                 
1553                                 bmesh_radial_append(l_new->e, l_new);
1554                                 bmesh_radial_append(l->e, l);
1555                         }
1556                         else if (BM_verts_in_edge(l_new->v, l_new->next->v, e_new)) {
1557                                 l_new->e = e_new;
1558                                 l->e = e;
1559
1560                                 /* append l into e_new's rad cycle */
1561                                 if (!first1) {
1562                                         first1 = 1;
1563                                         l->radial_next = l->radial_prev = NULL;
1564                                 }
1565
1566                                 if (!first2) {
1567                                         first2 = 1;
1568                                         l->radial_next = l->radial_prev = NULL;
1569                                 }
1570
1571                                 bmesh_radial_append(l_new->e, l_new);
1572                                 bmesh_radial_append(l->e, l);
1573                         }
1574
1575                 }
1576
1577 #ifndef NDEBUG
1578                 /* verify length of radial cycle */
1579                 edok = bmesh_radial_validate(radlen, e->l);
1580                 BMESH_ASSERT(edok != false);
1581                 edok = bmesh_radial_validate(radlen, e_new->l);
1582                 BMESH_ASSERT(edok != false);
1583
1584                 /* verify loop->v and loop->next->v pointers for e */
1585                 for (i = 0, l = e->l; i < radlen; i++, l = l->radial_next) {
1586                         BMESH_ASSERT(l->e == e);
1587                         //BMESH_ASSERT(l->radial_next == l);
1588                         BMESH_ASSERT(!(l->prev->e != e_new && l->next->e != e_new));
1589
1590                         edok = BM_verts_in_edge(l->v, l->next->v, e);
1591                         BMESH_ASSERT(edok != false);
1592                         BMESH_ASSERT(l->v != l->next->v);
1593                         BMESH_ASSERT(l->e != l->next->e);
1594
1595                         /* verify loop cycle for kloop->f */
1596                         BM_CHECK_ELEMENT(l);
1597                         BM_CHECK_ELEMENT(l->v);
1598                         BM_CHECK_ELEMENT(l->e);
1599                         BM_CHECK_ELEMENT(l->f);
1600                 }
1601                 /* verify loop->v and loop->next->v pointers for e_new */
1602                 for (i = 0, l = e_new->l; i < radlen; i++, l = l->radial_next) {
1603                         BMESH_ASSERT(l->e == e_new);
1604                         // BMESH_ASSERT(l->radial_next == l);
1605                         BMESH_ASSERT(!(l->prev->e != e && l->next->e != e));
1606                         edok = BM_verts_in_edge(l->v, l->next->v, e_new);
1607                         BMESH_ASSERT(edok != false);
1608                         BMESH_ASSERT(l->v != l->next->v);
1609                         BMESH_ASSERT(l->e != l->next->e);
1610
1611                         BM_CHECK_ELEMENT(l);
1612                         BM_CHECK_ELEMENT(l->v);
1613                         BM_CHECK_ELEMENT(l->e);
1614                         BM_CHECK_ELEMENT(l->f);
1615                 }
1616 #endif
1617         }
1618
1619         BM_CHECK_ELEMENT(e_new);
1620         BM_CHECK_ELEMENT(v_new);
1621         BM_CHECK_ELEMENT(v_old);
1622         BM_CHECK_ELEMENT(e);
1623         BM_CHECK_ELEMENT(tv);
1624
1625         if (r_e) *r_e = e_new;
1626         return v_new;
1627 }
1628
1629 /**
1630  * \brief Join Edge Kill Vert (JEKV)
1631  *
1632  * Takes an edge \a e_kill and pointer to one of its vertices \a v_kill
1633  * and collapses the edge on that vertex.
1634  *
1635  * \par Examples:
1636  *
1637  * <pre>
1638  *     Before:         OE      KE
1639  *                   ------- -------
1640  *                   |     ||      |
1641  *                  OV     KV      TV
1642  *
1643  *
1644  *     After:              OE
1645  *                   ---------------
1646  *                   |             |
1647  *                  OV             TV
1648  * </pre>
1649  *
1650  * \par Restrictions:
1651  * KV is a vertex that must have a valance of exactly two. Furthermore
1652  * both edges in KV's disk cycle (OE and KE) must be unique (no double edges).
1653  *
1654  * \return The resulting edge, NULL for failure.
1655  *
1656  * \note This euler has the possibility of creating
1657  * faces with just 2 edges. It is up to the caller to decide what to do with
1658  * these faces.
1659  */
1660 BMEdge *bmesh_jekv(BMesh *bm, BMEdge *e_kill, BMVert *v_kill,
1661                    const bool do_del, const bool check_edge_double)
1662 {
1663         BMEdge *e_old;
1664         BMVert *v_old, *tv;
1665         BMLoop *l_kill;
1666         int len, radlen = 0, i;
1667         bool halt = false;
1668 #ifndef NDEBUG
1669         bool edok;
1670 #endif
1671
1672         BLI_assert(BM_vert_in_edge(e_kill, v_kill));
1673
1674         if (BM_vert_in_edge(e_kill, v_kill) == 0) {
1675                 return NULL;
1676         }
1677
1678         len = bmesh_disk_count(v_kill);
1679         
1680         if (len == 2) {
1681 #ifndef NDEBUG
1682                 int valence1, valence2;
1683                 BMLoop *l;
1684 #endif
1685
1686                 e_old = bmesh_disk_edge_next(e_kill, v_kill);
1687                 tv = BM_edge_other_vert(e_kill, v_kill);
1688                 v_old = BM_edge_other_vert(e_old, v_kill);
1689                 halt = BM_verts_in_edge(v_kill, tv, e_old); /* check for double edges */
1690                 
1691                 if (halt) {
1692                         return NULL;
1693                 }
1694                 else {
1695                         BMEdge *e_splice;
1696
1697 #ifndef NDEBUG
1698                         /* For verification later, count valence of v_old and tv */
1699                         valence1 = bmesh_disk_count(v_old);
1700                         valence2 = bmesh_disk_count(tv);
1701 #endif
1702
1703                         if (check_edge_double) {
1704                                 e_splice = BM_edge_exists(tv, v_old);
1705                         }
1706
1707                         /* remove e_old from v_kill's disk cycle */
1708                         bmesh_disk_edge_remove(e_old, v_kill);
1709                         /* relink e_old->v_kill to be e_old->tv */
1710                         bmesh_edge_swapverts(e_old, v_kill, tv);
1711                         /* append e_old to tv's disk cycle */
1712                         bmesh_disk_edge_append(e_old, tv);
1713                         /* remove e_kill from tv's disk cycle */
1714                         bmesh_disk_edge_remove(e_kill, tv);
1715
1716                         /* deal with radial cycle of e_kill */
1717                         radlen = bmesh_radial_length(e_kill->l);
1718                         if (e_kill->l) {
1719                                 /* first step, fix the neighboring loops of all loops in e_kill's radial cycle */
1720                                 for (i = 0, l_kill = e_kill->l; i < radlen; i++, l_kill = l_kill->radial_next) {
1721                                         /* relink loops and fix vertex pointer */
1722                                         if (l_kill->next->v == v_kill) {
1723                                                 l_kill->next->v = tv;
1724                                         }
1725
1726                                         l_kill->next->prev = l_kill->prev;
1727                                         l_kill->prev->next = l_kill->next;
1728                                         if (BM_FACE_FIRST_LOOP(l_kill->f) == l_kill) {
1729                                                 BM_FACE_FIRST_LOOP(l_kill->f) = l_kill->next;
1730                                         }
1731                                         l_kill->next = NULL;
1732                                         l_kill->prev = NULL;
1733
1734                                         /* fix len attribute of face */
1735                                         l_kill->f->len--;
1736                                 }
1737                                 /* second step, remove all the hanging loops attached to e_kill */
1738                                 radlen = bmesh_radial_length(e_kill->l);
1739
1740                                 if (LIKELY(radlen)) {
1741                                         BMLoop **loops = BLI_array_alloca(loops, radlen);
1742
1743                                         l_kill = e_kill->l;
1744
1745                                         /* this should be wrapped into a bme_free_radial function to be used by bmesh_KF as well... */
1746                                         for (i = 0; i < radlen; i++) {
1747                                                 loops[i] = l_kill;
1748                                                 l_kill = l_kill->radial_next;
1749                                         }
1750                                         for (i = 0; i < radlen; i++) {
1751                                                 bm->totloop--;
1752                                                 BLI_mempool_free(bm->lpool, loops[i]);
1753                                         }
1754                                 }
1755 #ifndef NDEBUG
1756                                 /* Validate radial cycle of e_old */
1757                                 edok = bmesh_radial_validate(radlen, e_old->l);
1758                                 BMESH_ASSERT(edok != false);
1759 #endif
1760                         }
1761                         /* deallocate edge */
1762                         bm_kill_only_edge(bm, e_kill);
1763
1764                         /* deallocate vertex */
1765                         if (do_del) {
1766                                 bm_kill_only_vert(bm, v_kill);
1767                         }
1768                         else {
1769                                 v_kill->e = NULL;
1770                         }
1771
1772 #ifndef NDEBUG
1773                         /* Validate disk cycle lengths of v_old, tv are unchanged */
1774                         edok = bmesh_disk_validate(valence1, v_old->e, v_old);
1775                         BMESH_ASSERT(edok != false);
1776                         edok = bmesh_disk_validate(valence2, tv->e, tv);
1777                         BMESH_ASSERT(edok != false);
1778
1779                         /* Validate loop cycle of all faces attached to 'e_old' */
1780                         for (i = 0, l = e_old->l; i < radlen; i++, l = l->radial_next) {
1781                                 BMESH_ASSERT(l->e == e_old);
1782                                 edok = BM_verts_in_edge(l->v, l->next->v, e_old);
1783                                 BMESH_ASSERT(edok != false);
1784                                 edok = bmesh_loop_validate(l->f);
1785                                 BMESH_ASSERT(edok != false);
1786
1787                                 BM_CHECK_ELEMENT(l);
1788                                 BM_CHECK_ELEMENT(l->v);
1789                                 BM_CHECK_ELEMENT(l->e);
1790                                 BM_CHECK_ELEMENT(l->f);
1791                         }
1792 #endif
1793
1794                         if (check_edge_double) {
1795                                 if (e_splice) {
1796                                         /* removes e_splice */
1797                                         BM_edge_splice(bm, e_splice, e_old);
1798                                 }
1799                         }
1800
1801                         BM_CHECK_ELEMENT(v_old);
1802                         BM_CHECK_ELEMENT(tv);
1803                         BM_CHECK_ELEMENT(e_old);
1804
1805                         return e_old;
1806                 }
1807         }
1808         return NULL;
1809 }
1810
1811 /**
1812  * \brief Join Face Kill Edge (JFKE)
1813  *
1814  * Takes two faces joined by a single 2-manifold edge and fuses them together.
1815  * The edge shared by the faces must not be connected to any other edges which have
1816  * Both faces in its radial cycle
1817  *
1818  * \par Examples:
1819  * <pre>
1820  *           A                   B
1821  *      +--------+           +--------+
1822  *      |        |           |        |
1823  *      |   f1   |           |   f1   |
1824  *     v1========v2 = Ok!    v1==V2==v3 == Wrong!
1825  *      |   f2   |           |   f2   |
1826  *      |        |           |        |
1827  *      +--------+           +--------+
1828  * </pre>
1829  *
1830  * In the example A, faces \a f1 and \a f2 are joined by a single edge,
1831  * and the euler can safely be used.
1832  * In example B however, \a f1 and \a f2 are joined by multiple edges and will produce an error.
1833  * The caller in this case should call #bmesh_jekv on the extra edges
1834  * before attempting to fuse \a f1 and \a f2.
1835  *
1836  * \note The order of arguments decides whether or not certain per-face attributes are present
1837  * in the resultant face. For instance vertex winding, material index, smooth flags, etc are inherited
1838  * from \a f1, not \a f2.
1839  *
1840  * \return A BMFace pointer
1841  */
1842 BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e)
1843 {
1844         BMLoop *l_iter, *l_f1 = NULL, *l_f2 = NULL;
1845         int newlen = 0, i, f1len = 0, f2len = 0;
1846         bool edok;
1847         /* can't join a face to itself */
1848         if (f1 == f2) {
1849                 return NULL;
1850         }
1851
1852         /* validate that edge is 2-manifold edge */
1853         if (!BM_edge_is_manifold(e)) {
1854                 return NULL;
1855         }
1856
1857         /* verify that e is in both f1 and f2 */
1858         f1len = f1->len;
1859         f2len = f2->len;
1860
1861         if (!((l_f1 = BM_face_edge_share_loop(f1, e)) &&
1862               (l_f2 = BM_face_edge_share_loop(f2, e))))
1863         {
1864                 return NULL;
1865         }
1866
1867         /* validate direction of f2's loop cycle is compatible */
1868         if (l_f1->v == l_f2->v) {
1869                 return NULL;
1870         }
1871
1872         /* validate that for each face, each vertex has another edge in its disk cycle that is
1873          * not e, and not shared. */
1874         if (BM_edge_in_face(l_f1->next->e, f2) ||
1875             BM_edge_in_face(l_f1->prev->e, f2) ||
1876             BM_edge_in_face(l_f2->next->e, f1) ||
1877             BM_edge_in_face(l_f2->prev->e, f1) )
1878         {
1879                 return NULL;
1880         }
1881
1882         /* validate only one shared edge */
1883         if (BM_face_share_edge_count(f1, f2) > 1) {
1884                 return NULL;
1885         }
1886
1887         /* validate no internal join */
1888         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < f1len; i++, l_iter = l_iter->next) {
1889                 BM_elem_flag_disable(l_iter->v, BM_ELEM_INTERNAL_TAG);
1890         }
1891         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f2); i < f2len; i++, l_iter = l_iter->next) {
1892                 BM_elem_flag_disable(l_iter->v, BM_ELEM_INTERNAL_TAG);
1893         }
1894
1895         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < f1len; i++, l_iter = l_iter->next) {
1896                 if (l_iter != l_f1) {
1897                         BM_elem_flag_enable(l_iter->v, BM_ELEM_INTERNAL_TAG);
1898                 }
1899         }
1900         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f2); i < f2len; i++, l_iter = l_iter->next) {
1901                 if (l_iter != l_f2) {
1902                         /* as soon as a duplicate is found, bail out */
1903                         if (BM_elem_flag_test(l_iter->v, BM_ELEM_INTERNAL_TAG)) {
1904                                 return NULL;
1905                         }
1906                 }
1907         }
1908
1909         /* join the two loop */
1910         l_f1->prev->next = l_f2->next;
1911         l_f2->next->prev = l_f1->prev;
1912         
1913         l_f1->next->prev = l_f2->prev;
1914         l_f2->prev->next = l_f1->next;
1915         
1916         /* if l_f1 was baseloop, make l_f1->next the base. */
1917         if (BM_FACE_FIRST_LOOP(f1) == l_f1)
1918                 BM_FACE_FIRST_LOOP(f1) = l_f1->next;
1919
1920         /* increase length of f1 */
1921         f1->len += (f2->len - 2);
1922
1923         /* make sure each loop points to the proper face */
1924         newlen = f1->len;
1925         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < newlen; i++, l_iter = l_iter->next)
1926                 l_iter->f = f1;
1927         
1928         /* remove edge from the disk cycle of its two vertices */
1929         bmesh_disk_edge_remove(l_f1->e, l_f1->e->v1);
1930         bmesh_disk_edge_remove(l_f1->e, l_f1->e->v2);
1931         
1932         /* deallocate edge and its two loops as well as f2 */
1933         if (bm->etoolflagpool) {
1934                 BLI_mempool_free(bm->etoolflagpool, l_f1->e->oflags);
1935         }
1936         BLI_mempool_free(bm->epool, l_f1->e);
1937         bm->totedge--;
1938         BLI_mempool_free(bm->lpool, l_f1);
1939         bm->totloop--;
1940         BLI_mempool_free(bm->lpool, l_f2);
1941         bm->totloop--;
1942         if (bm->ftoolflagpool) {
1943                 BLI_mempool_free(bm->ftoolflagpool, f2->oflags);
1944         }
1945         BLI_mempool_free(bm->fpool, f2);
1946         bm->totface--;
1947         /* account for both above */
1948         bm->elem_index_dirty |= BM_EDGE | BM_LOOP | BM_FACE;
1949
1950         BM_CHECK_ELEMENT(f1);
1951
1952         /* validate the new loop cycle */
1953         edok = bmesh_loop_validate(f1);
1954         BMESH_ASSERT(edok != false);
1955         
1956         return f1;
1957 }
1958
1959 /**
1960  * \brief Splice Vert
1961  *
1962  * Merges two verts into one (\a v into \a vtarget).
1963  *
1964  * \return Success
1965  *
1966  * \warning This does't work for collapsing edges,
1967  * where \a v and \a vtarget are connected by an edge
1968  * (assert checks for this case).
1969  */
1970 bool BM_vert_splice(BMesh *bm, BMVert *v, BMVert *v_target)
1971 {
1972         void *loops_stack[BM_DEFAULT_ITER_STACK_SIZE];
1973         BMLoop **loops;
1974         int i, loops_tot;
1975
1976         BMEdge *e;
1977
1978         /* verts already spliced */
1979         if (v == v_target) {
1980                 return false;
1981         }
1982
1983         /* we can't modify the vert while iterating so first allocate an array of loops */
1984         loops = BM_iter_as_arrayN(bm, BM_LOOPS_OF_VERT, v, &loops_tot,
1985                                   loops_stack, BM_DEFAULT_ITER_STACK_SIZE);
1986
1987         if (LIKELY(loops != NULL)) {
1988                 for (i = 0; i < loops_tot; i++) {
1989                         loops[i]->v = v_target;
1990                 }
1991                 if (loops != (BMLoop **)loops_stack) {
1992                         MEM_freeN(loops);
1993                 }
1994         }
1995
1996         /* move all the edges from v's disk to vtarget's disk */
1997         while ((e = v->e)) {
1998                 bmesh_disk_edge_remove(e, v);
1999                 bmesh_edge_swapverts(e, v, v_target);
2000                 bmesh_disk_edge_append(e, v_target);
2001                 BLI_assert(e->v1 != e->v2);
2002         }
2003
2004         BM_CHECK_ELEMENT(v);
2005         BM_CHECK_ELEMENT(v_target);
2006
2007         /* v is unused now, and can be killed */
2008         BM_vert_kill(bm, v);
2009
2010         return true;
2011 }
2012
2013 /**
2014  * \brief Separate Vert
2015  *
2016  * Separates all disjoint fans that meet at a vertex, making a unique
2017  * vertex for each region. returns an array of all resulting vertices.
2018  *
2019  * \note this is a low level function, bm_edge_separate needs to run on edges first
2020  * or, the faces sharing verts must not be sharing edges for them to split at least.
2021  *
2022  * \return Success
2023  */
2024 void bmesh_vert_separate(BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len,
2025                          const bool copy_select)
2026 {
2027         const int v_edgetot = BM_vert_face_count(v);
2028         BMEdge **stack = BLI_array_alloca(stack, v_edgetot);
2029         STACK_DECLARE(stack);
2030
2031         SmallHash visithash;
2032         BMVert **verts = NULL;
2033         BMIter eiter, liter;
2034         BMLoop *l;
2035         BMEdge *e;
2036         int i, maxindex;
2037         BMLoop *l_new;
2038
2039         BLI_smallhash_init_ex(&visithash, v_edgetot);
2040
2041         STACK_INIT(stack, v_edgetot);
2042
2043         maxindex = 0;
2044         BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
2045                 if (BLI_smallhash_haskey(&visithash, (uintptr_t)e)) {
2046                         continue;
2047                 }
2048
2049                 /* Considering only edges and faces incident on vertex v, walk
2050                  * the edges & faces and assign an index to each connected set */
2051                 do {
2052                         BLI_smallhash_insert(&visithash, (uintptr_t)e, SET_INT_IN_POINTER(maxindex));
2053
2054                         if (e->l) {
2055                                 BMLoop *l_iter, *l_first;
2056                                 l_iter = l_first = e->l;
2057                                 do {
2058                                         l_new = (l_iter->v == v) ? l_iter->prev : l_iter->next;
2059                                         if (!BLI_smallhash_haskey(&visithash, (uintptr_t)l_new->e)) {
2060                                                 STACK_PUSH(stack, l_new->e);
2061                                         }
2062                                 } while ((l_iter = l_iter->radial_next) != l_first);
2063                         }
2064                 } while ((e = STACK_POP(stack)));
2065
2066                 maxindex++;
2067         }
2068
2069         /* Make enough verts to split v for each group */
2070         if (r_vout != NULL) {
2071                 verts = MEM_callocN(sizeof(BMVert *) * maxindex, __func__);
2072         }
2073         else {
2074                 verts = BLI_array_alloca(verts, maxindex);
2075         }
2076
2077         verts[0] = v;
2078         for (i = 1; i < maxindex; i++) {
2079                 verts[i] = BM_vert_create(bm, v->co, v, BM_CREATE_NOP);
2080                 if (copy_select) {
2081                         BM_elem_select_copy(bm, bm, verts[i], v);
2082                 }
2083         }
2084
2085         /* Replace v with the new verts in each group */
2086 #if 0
2087         BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
2088                 /* call first since its faster then a hash lookup */
2089                 if (l->v != v) {
2090                         continue;
2091                 }
2092                 i = GET_INT_FROM_POINTER(BLI_ghash_lookup(visithash, l->e));
2093                 if (i == 0) {
2094                         continue;
2095                 }
2096
2097                 /* Loops here should always refer to an edge that has v as an
2098                  * endpoint. For each appearance of this vert in a face, there
2099                  * will actually be two iterations: one for the loop heading
2100                  * towards vertex v, and another for the loop heading out from
2101                  * vertex v. Only need to swap the vertex on one of those times,
2102                  * on the outgoing loop. */
2103
2104                 /* XXX - because this clobbers the iterator, this *whole* block is commented, see below */
2105                 l->v = verts[i];
2106         }
2107 #else
2108         /* note: this is the same as the commented code above *except* that it doesn't break iterator
2109          * by modifying data it loops over [#30632], this re-uses the 'stack' variable which is a bit
2110          * bad practice but save alloc'ing a new array - note, the comment above is useful, keep it
2111          * if you are tidying up code - campbell */
2112         STACK_INIT(stack, v_edgetot);
2113         BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
2114                 if (l->v == v) {
2115                         STACK_PUSH(stack, (BMEdge *)l);
2116                 }
2117         }
2118         while ((l = (BMLoop *)(STACK_POP(stack)))) {
2119                 if ((i = GET_INT_FROM_POINTER(BLI_smallhash_lookup(&visithash, (uintptr_t)l->e)))) {
2120                         l->v = verts[i];
2121                 }
2122         }
2123 #endif
2124
2125         BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
2126                 i = GET_INT_FROM_POINTER(BLI_smallhash_lookup(&visithash, (uintptr_t)e));
2127                 if (i == 0) {
2128                         continue;
2129                 }
2130
2131                 BLI_assert(e->v1 == v || e->v2 == v);
2132                 bmesh_disk_edge_remove(e, v);
2133                 bmesh_edge_swapverts(e, v, verts[i]);
2134                 bmesh_disk_edge_append(e, verts[i]);
2135         }
2136
2137         BLI_smallhash_release(&visithash);
2138
2139         for (i = 0; i < maxindex; i++) {
2140                 BM_CHECK_ELEMENT(verts[i]);
2141         }
2142
2143         if (r_vout_len != NULL) {
2144                 *r_vout_len = maxindex;
2145         }
2146
2147         if (r_vout != NULL) {
2148                 *r_vout = verts;
2149         }
2150 }
2151
2152 /**
2153  * High level function which wraps both #bmesh_vert_separate and #bmesh_edge_separate
2154  */
2155 void BM_vert_separate(BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len,
2156                      BMEdge **e_in, int e_in_len)
2157 {
2158         int i;
2159
2160         for (i = 0; i < e_in_len; i++) {
2161                 BMEdge *e = e_in[i];
2162                 if (e->l && BM_vert_in_edge(e, v)) {
2163                         bmesh_edge_separate(bm, e, e->l, false);
2164                 }
2165         }
2166
2167         bmesh_vert_separate(bm, v, r_vout, r_vout_len, false);
2168 }
2169
2170 /**
2171  * \brief Splice Edge
2172  *
2173  * Splice two unique edges which share the same two vertices into one edge.
2174  *
2175  * \return Success
2176  *
2177  * \note Edges must already have the same vertices.
2178  */
2179 bool BM_edge_splice(BMesh *bm, BMEdge *e, BMEdge *e_target)
2180 {
2181         BMLoop *l;
2182
2183         if (!BM_vert_in_edge(e, e_target->v1) || !BM_vert_in_edge(e, e_target->v2)) {
2184                 /* not the same vertices can't splice */
2185
2186                 /* the caller should really make sure this doesn't happen ever
2187                  * so assert on release builds */
2188                 BLI_assert(0);
2189
2190                 return false;
2191         }
2192
2193         while (e->l) {
2194                 l = e->l;
2195                 BLI_assert(BM_vert_in_edge(e_target, l->v));
2196                 BLI_assert(BM_vert_in_edge(e_target, l->next->v));
2197                 bmesh_radial_loop_remove(l, e);
2198                 bmesh_radial_append(e_target, l);
2199         }
2200
2201         BLI_assert(bmesh_radial_length(e->l) == 0);
2202
2203         BM_CHECK_ELEMENT(e);
2204         BM_CHECK_ELEMENT(e_target);
2205
2206         /* removes from disks too */
2207         BM_edge_kill(bm, e);
2208
2209         return true;
2210 }
2211
2212 /**
2213  * \brief Separate Edge
2214  *
2215  * Separates a single edge into two edge: the original edge and
2216  * a new edge that has only \a l_sep in its radial.
2217  *
2218  * \return Success
2219  *
2220  * \note Does nothing if \a l_sep is already the only loop in the
2221  * edge radial.
2222  */
2223 void bmesh_edge_separate(BMesh *bm, BMEdge *e, BMLoop *l_sep,
2224                          const bool copy_select)
2225 {
2226         BMEdge *e_new;
2227 #ifndef NDEBUG
2228         const int radlen = bmesh_radial_length(e->l);
2229 #endif
2230
2231         BLI_assert(l_sep->e == e);
2232         BLI_assert(e->l);
2233         
2234         if (BM_edge_is_boundary(e)) {
2235                 /* no cut required */
2236                 return;
2237         }
2238
2239         if (l_sep == e->l) {
2240                 e->l = l_sep->radial_next;
2241         }
2242
2243         e_new = BM_edge_create(bm, e->v1, e->v2, e, BM_CREATE_NOP);
2244         bmesh_radial_loop_remove(l_sep, e);
2245         bmesh_radial_append(e_new, l_sep);
2246         l_sep->e = e_new;
2247
2248         if (copy_select) {
2249                 BM_elem_select_copy(bm, bm, e_new, e);
2250         }
2251
2252         BLI_assert(bmesh_radial_length(e->l) == radlen - 1);
2253         BLI_assert(bmesh_radial_length(e_new->l) == 1);
2254
2255         BM_CHECK_ELEMENT(e_new);
2256         BM_CHECK_ELEMENT(e);
2257 }
2258
2259 /**
2260  * \brief Un-glue Region Make Vert (URMV)
2261  *
2262  * Disconnects a face from its vertex fan at loop \a l_sep
2263  *
2264  * \return The newly created BMVert
2265  */
2266 BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *l_sep)
2267 {
2268         BMVert **vtar;
2269         int len, i;
2270         BMVert *v_new = NULL;
2271         BMVert *v_sep = l_sep->v;
2272
2273         /* peel the face from the edge radials on both sides of the
2274          * loop vert, disconnecting the face from its fan */
2275         bmesh_edge_separate(bm, l_sep->e, l_sep, false);
2276         bmesh_edge_separate(bm, l_sep->prev->e, l_sep->prev, false);
2277
2278         if (bmesh_disk_count(v_sep) == 2) {
2279                 /* If there are still only two edges out of v_sep, then
2280                  * this whole URMV was just a no-op, so exit now. */
2281                 return v_sep;
2282         }
2283
2284         /* Update the disk start, so that v->e points to an edge
2285          * not touching the split loop. This is so that BM_vert_split
2286          * will leave the original v_sep on some *other* fan (not the
2287          * one-face fan that holds the unglue face). */
2288         while (v_sep->e == l_sep->e || v_sep->e == l_sep->prev->e) {
2289                 v_sep->e = bmesh_disk_edge_next(v_sep->e, v_sep);
2290         }
2291
2292         /* Split all fans connected to the vert, duplicating it for
2293          * each fans. */
2294         bmesh_vert_separate(bm, v_sep, &vtar, &len, false);
2295
2296         /* There should have been at least two fans cut apart here,
2297          * otherwise the early exit would have kicked in. */
2298         BLI_assert(len >= 2);
2299
2300         v_new = l_sep->v;
2301
2302         /* Desired result here is that a new vert should always be
2303          * created for the unglue face. This is so we can glue any
2304          * extras back into the original vert. */
2305         BLI_assert(v_new != v_sep);
2306         BLI_assert(v_sep == vtar[0]);
2307
2308         /* If there are more than two verts as a result, glue together
2309          * all the verts except the one this URMV intended to create */
2310         if (len > 2) {
2311                 for (i = 0; i < len; i++) {
2312                         if (vtar[i] == v_new) {
2313                                 break;
2314                         }
2315                 }
2316
2317                 if (i != len) {
2318                         /* Swap the single vert that was needed for the
2319                          * unglue into the last array slot */
2320                         SWAP(BMVert *, vtar[i], vtar[len - 1]);
2321
2322                         /* And then glue the rest back together */
2323                         for (i = 1; i < len - 1; i++) {
2324                                 BM_vert_splice(bm, vtar[i], vtar[0]);
2325                         }
2326                 }
2327         }
2328
2329         MEM_freeN(vtar);
2330
2331         return v_new;
2332 }
2333
2334 /**
2335  * \brief Unglue Region Make Vert (URMV)
2336  *
2337  * Disconnects f_sep from the vertex fan at \a v_sep
2338  *
2339  * \return The newly created BMVert
2340  */
2341 BMVert *bmesh_urmv(BMesh *bm, BMFace *f_sep, BMVert *v_sep)
2342 {
2343         BMLoop *l = BM_face_vert_share_loop(f_sep, v_sep);
2344         return bmesh_urmv_loop(bm, l);
2345 }
2346
2347 /**
2348  * Avoid calling this where possible,
2349  * low level function so both face pointers remain intact but point to swapped data.
2350  * \note must be from the same bmesh.
2351  */
2352 void bmesh_face_swap_data(BMFace *f_a, BMFace *f_b)
2353 {
2354         BMLoop *l_iter, *l_first;
2355
2356         BLI_assert(f_a != f_b);
2357
2358         l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
2359         do {
2360                 l_iter->f = f_b;
2361         } while ((l_iter = l_iter->next) != l_first);
2362
2363         l_iter = l_first = BM_FACE_FIRST_LOOP(f_b);
2364         do {
2365                 l_iter->f = f_a;
2366         } while ((l_iter = l_iter->next) != l_first);
2367
2368         SWAP(BMFace, (*f_a), (*f_b));
2369
2370         /* swap back */
2371         SWAP(void *, f_a->head.data, f_b->head.data);
2372         SWAP(int, f_a->head.index, f_b->head.index);
2373 }