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