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