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