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