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