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