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