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