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