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