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