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