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