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