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