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