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