b80d6fe6e47530ab3959776ddbe95bbac3fd0b7a
[blender.git] / source / blender / bmesh / intern / bmesh_queries.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_queries.c
24  *  \ingroup bmesh
25  *
26  * This file contains functions for answering common
27  * Topological and geometric queries about a mesh, such
28  * as, "What is the angle between these two faces?" or,
29  * "How many faces are incident upon this vertex?" Tool
30  * authors should use the functions in this file instead
31  * of inspecting the mesh structure directly.
32  */
33
34 #include "MEM_guardedalloc.h"
35
36 #include "BLI_array.h"
37 #include "BLI_math.h"
38
39 #include "bmesh.h"
40 #include "intern/bmesh_private.h"
41
42 #define BM_OVERLAP (1 << 13)
43
44 /**
45  * Return the amount of element of type 'type' in a given bmesh.
46  */
47 int BM_mesh_elem_count(BMesh *bm, const char htype)
48 {
49         if (htype == BM_VERT) return bm->totvert;
50         else if (htype == BM_EDGE) return bm->totedge;
51         else if (htype == BM_FACE) return bm->totface;
52
53         return 0;
54 }
55
56 /**
57  * Returns whether or not a given vertex is
58  * is part of a given edge.
59  */
60 int BM_vert_in_edge(BMEdge *e, BMVert *v)
61 {
62         return bmesh_vert_in_edge(e, v);
63 }
64
65 /**
66  * \brief Other Loop in Face Sharing an Edge
67  *
68  * Finds the other loop that shares \a v with \a e loop in \a f.
69  *
70  *     +----------+
71  *     |          |
72  *     |    f     |
73  *     |          |
74  *     +----------+ <-- return the face loop of this vertex.
75  *     v --> e
76  *     ^     ^ <------- These vert args define direction
77  *                      in the face to check.
78  *                      The faces loop direction is ignored.
79  *
80  */
81 BMLoop *BM_face_other_edge_loop(BMFace *f, BMEdge *e, BMVert *v)
82 {
83         BMLoop *l_iter;
84         BMLoop *l_first;
85
86         /* we could loop around the face too, but turns out this uses a lot
87          * more iterations (approx double with quads, many more with 5+ ngons) */
88         l_iter = l_first = e->l;
89
90         do {
91                 if (l_iter->e == e && l_iter->f == f) {
92                         break;
93                 }
94         } while ((l_iter = l_iter->radial_next) != l_first);
95         
96         return l_iter->v == v ? l_iter->prev : l_iter->next;
97 }
98
99 /**
100  * \brief Other Loop in Face Sharing a Vertex
101  *
102  * Finds the other loop in a face.
103  *
104  * This function returns a loop in \a f that shares an edge with \a v
105  * The direction is defined by \a v_prev, where the return value is
106  * the loop of what would be 'v_next'
107  *
108  *
109  *     +----------+ <-- return the face loop of this vertex.
110  *     |          |
111  *     |    f     |
112  *     |          |
113  *     +----------+
114  *     v_prev --> v
115  *     ^^^^^^     ^ <-- These vert args define direction
116  *                      in the face to check.
117  *                      The faces loop direction is ignored.
118  *
119  * \note \a v_prev and \a v _implicitly_ define an edge.
120  */
121 BMLoop *BM_face_other_vert_loop(BMFace *f, BMVert *v_prev, BMVert *v)
122 {
123         BMIter liter;
124         BMLoop *l_iter;
125
126         BLI_assert(BM_edge_exists(v_prev, v) != NULL);
127
128         BM_ITER(l_iter, &liter, NULL, BM_LOOPS_OF_VERT, v) {
129                 if (l_iter->f == f) {
130                         break;
131                 }
132         }
133
134         if (l_iter) {
135                 if (l_iter->prev->v == v_prev) {
136                         return l_iter->next;
137                 }
138                 else if (l_iter->next->v == v_prev) {
139                         return l_iter->prev;
140                 }
141                 else {
142                         /* invalid args */
143                         BLI_assert(0);
144                         return NULL;
145                 }
146         }
147         else {
148                 /* invalid args */
149                 BLI_assert(0);
150                 return NULL;
151         }
152 }
153
154 /**
155  * Returns TRUE if the vertex is used in a given face.
156  */
157
158 int BM_vert_in_face(BMFace *f, BMVert *v)
159 {
160         BMLoop *l_iter, *l_first;
161
162 #ifdef USE_BMESH_HOLES
163         BMLoopList *lst;
164         for (lst = f->loops.first; lst; lst = lst->next)
165 #endif
166         {
167 #ifdef USE_BMESH_HOLES
168                 l_iter = l_first = lst->first;
169 #else
170                 l_iter = l_first = f->l_first;
171 #endif
172                 do {
173                         if (l_iter->v == v) {
174                                 return TRUE;
175                         }
176                 } while ((l_iter = l_iter->next) != l_first);
177         }
178
179         return FALSE;
180 }
181
182 /**
183  * Compares the number of vertices in an array
184  * that appear in a given face
185  */
186 int BM_verts_in_face(BMesh *bm, BMFace *f, BMVert **varr, int len)
187 {
188         BMLoop *l_iter, *l_first;
189
190 #ifdef USE_BMESH_HOLES
191         BMLoopList *lst;
192 #endif
193
194         int i, count = 0;
195         
196         for (i = 0; i < len; i++) {
197                 BMO_elem_flag_enable(bm, varr[i], BM_OVERLAP);
198         }
199
200 #ifdef USE_BMESH_HOLES
201         for (lst = f->loops.first; lst; lst = lst->next)
202 #endif
203         {
204
205 #ifdef USE_BMESH_HOLES
206                 l_iter = l_first = lst->first;
207 #else
208                 l_iter = l_first = f->l_first;
209 #endif
210
211                 do {
212                         if (BMO_elem_flag_test(bm, l_iter->v, BM_OVERLAP)) {
213                                 count++;
214                         }
215
216                 } while ((l_iter = l_iter->next) != l_first);
217         }
218
219         for (i = 0; i < len; i++) BMO_elem_flag_disable(bm, varr[i], BM_OVERLAP);
220
221         return count;
222 }
223
224 /**
225  * Returns whether or not a given edge is is part of a given face.
226  */
227 int BM_edge_in_face(BMFace *f, BMEdge *e)
228 {
229         BMLoop *l_iter;
230         BMLoop *l_first;
231
232         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
233
234         do {
235                 if (l_iter->e == e) {
236                         return TRUE;
237                 }
238         } while ((l_iter = l_iter->next) != l_first);
239
240         return FALSE;
241 }
242
243 /**
244  * Returns whether or not two vertices are in
245  * a given edge
246  */
247 int BM_verts_in_edge(BMVert *v1, BMVert *v2, BMEdge *e)
248 {
249         return bmesh_verts_in_edge(v1, v2, e);
250 }
251
252 /**
253  * Given a edge and one of its vertices, returns
254  * the other vertex.
255  */
256 BMVert *BM_edge_other_vert(BMEdge *e, BMVert *v)
257 {
258         return bmesh_edge_other_vert_get(e, v);
259 }
260
261 /**
262  * Utility function, since enough times we have an edge
263  * and want to access 2 connected faces.
264  *
265  * \return TRUE when only 2 faces are found.
266  */
267 int BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
268 {
269         BMLoop *la, *lb;
270
271         if ((la = e->l) &&
272             (lb = la->radial_next) &&
273             (lb->radial_next == la))
274         {
275                 *r_fa = la->f;
276                 *r_fb = lb->f;
277                 return TRUE;
278         }
279         else {
280                 *r_fa = NULL;
281                 *r_fb = NULL;
282                 return FALSE;
283         }
284 }
285
286 /**
287  *      Returns the number of edges around this vertex.
288  */
289 int BM_vert_edge_count(BMVert *v)
290 {
291         return bmesh_disk_count(v);
292 }
293
294 /**
295  *      Returns the number of faces around this edge
296  */
297 int BM_edge_face_count(BMEdge *e)
298 {
299         int count = 0;
300
301         if (e->l) {
302                 BMLoop *l_iter;
303                 BMLoop *l_first;
304
305                 l_iter = l_first = e->l;
306
307                 do {
308                         count++;
309                 } while ((l_iter = l_iter->radial_next) != l_first);
310         }
311
312         return count;
313 }
314
315 /**
316  *      Returns the number of faces around this vert
317  */
318 int BM_vert_face_count(BMVert *v)
319 {
320         int count = 0;
321         BMLoop *l;
322         BMIter iter;
323
324         BM_ITER(l, &iter, NULL, BM_LOOPS_OF_VERT, v) {
325                 count++;
326         }
327
328         return count;
329 #if 0 //this code isn't working
330         BMEdge *curedge = NULL;
331
332         if (v->e) {
333                 curedge = v->e;
334                 do {
335                         if (curedge->l) count += BM_edge_face_count(curedge);
336                         curedge = bmesh_disk_edge_next(curedge, v);
337                 } while (curedge != v->e);
338         }
339         return count;
340 #endif
341 }
342
343 /**
344  * Tests whether or not the vertex is part of a wire edge.
345  * (ie: has no faces attached to it)
346  */
347 int BM_vert_is_wire(BMesh *UNUSED(bm), BMVert *v)
348 {
349         BMEdge *curedge;
350
351         if (v->e == NULL) {
352                 return FALSE;
353         }
354         
355         curedge = v->e;
356         do {
357                 if (curedge->l) {
358                         return FALSE;
359                 }
360
361                 curedge = bmesh_disk_edge_next(curedge, v);
362         } while (curedge != v->e);
363
364         return TRUE;
365 }
366
367 /**
368  * Tests whether or not the edge is part of a wire.
369  * (ie: has no faces attached to it)
370  */
371 int BM_edge_is_wire(BMesh *UNUSED(bm), BMEdge *e)
372 {
373         return (e->l) ? FALSE : TRUE;
374 }
375
376 /**
377  * A vertex is non-manifold if it meets the following conditions:
378  * 1: Loose - (has no edges/faces incident upon it)
379  * 2: Joins two distinct regions - (two pyramids joined at the tip)
380  * 3: Is part of a non-manifold edge (edge with more than 2 faces)
381  * 4: Is part of a wire edge
382  */
383 int BM_vert_is_manifold(BMesh *UNUSED(bm), BMVert *v)
384 {
385         BMEdge *e, *oe;
386         BMLoop *l;
387         int len, count, flag;
388
389         if (v->e == NULL) {
390                 /* loose vert */
391                 return FALSE;
392         }
393
394         /* count edges while looking for non-manifold edges */
395         oe = v->e;
396         for (len = 0, e = v->e; e != oe || (e == oe && len == 0); len++, e = bmesh_disk_edge_next(e, v)) {
397                 if (e->l == NULL) {
398                         /* loose edge */
399                         return FALSE;
400                 }
401
402                 if (bmesh_radial_length(e->l) > 2) {
403                         /* edge shared by more than two faces */
404                         return FALSE;
405                 }
406         }
407
408         count = 1;
409         flag = 1;
410         e = NULL;
411         oe = v->e;
412         l = oe->l;
413         while (e != oe) {
414                 l = (l->v == v) ? l->prev : l->next;
415                 e = l->e;
416                 count++; /* count the edges */
417
418                 if (flag && l->radial_next == l) {
419                         /* we've hit the edge of an open mesh, reset once */
420                         flag = 0;
421                         count = 1;
422                         oe = e;
423                         e = NULL;
424                         l = oe->l;
425                 }
426                 else if (l->radial_next == l) {
427                         /* break the loop */
428                         e = oe;
429                 }
430                 else {
431                         l = l->radial_next;
432                 }
433         }
434
435         if (count < len) {
436                 /* vert shared by multiple regions */
437                 return FALSE;
438         }
439
440         return TRUE;
441 }
442
443 /**
444  * Tests whether or not this edge is manifold.
445  * A manifold edge either has 1 or 2 faces attached to it.
446  */
447
448 #if 1 /* fast path for checking manifold */
449 int BM_edge_is_manifold(BMesh *UNUSED(bm), BMEdge *e)
450 {
451         const BMLoop *l = e->l;
452         return (l && ((l->radial_next == l) ||              /* 1 face user  */
453                       (l->radial_next->radial_next == l))); /* 2 face users */
454 }
455 #else
456 int BM_edge_is_manifold(BMesh *UNUSED(bm), BMEdge *e)
457 {
458         int count = BM_edge_face_count(e);
459         if (count == 2 || count == 1) {
460                 return TRUE;
461         }
462         else {
463                 return FALSE;
464         }
465 }
466 #endif
467
468 /**
469  * Tests whether or not an edge is on the boundary
470  * of a shell (has one face associated with it)
471  */
472
473 #if 1 /* fast path for checking boundry */
474 int BM_edge_is_boundary(BMEdge *e)
475 {
476         const BMLoop *l = e->l;
477         return (l && (l->radial_next == l));
478 }
479 #else
480 int BM_edge_is_boundary(BMEdge *e)
481 {
482         int count = BM_edge_face_count(e);
483         if (count == 1) {
484                 return TRUE;
485         }
486         else {
487                 return FALSE;
488         }
489 }
490 #endif
491
492 /**
493  *  Counts the number of edges two faces share (if any)
494  */
495 int BM_face_share_edge_count(BMFace *f1, BMFace *f2)
496 {
497         BMLoop *l_iter;
498         BMLoop *l_first;
499         int count = 0;
500         
501         l_iter = l_first = BM_FACE_FIRST_LOOP(f1);
502         do {
503                 if (bmesh_radial_face_find(l_iter->e, f2)) {
504                         count++;
505                 }
506         } while ((l_iter = l_iter->next) != l_first);
507
508         return count;
509 }
510
511 /**
512  *      Test if e1 shares any faces with e2
513  */
514 int BM_edge_share_face_count(BMEdge *e1, BMEdge *e2)
515 {
516         BMLoop *l;
517         BMFace *f;
518
519         if (e1->l && e2->l) {
520                 l = e1->l;
521                 do {
522                         f = l->f;
523                         if (bmesh_radial_face_find(e2, f)) {
524                                 return TRUE;
525                         }
526                         l = l->radial_next;
527                 } while (l != e1->l);
528         }
529         return FALSE;
530 }
531
532 /**
533  *      Tests to see if e1 shares a vertex with e2
534  */
535 int BM_edge_share_vert_count(BMEdge *e1, BMEdge *e2)
536 {
537         return (e1->v1 == e2->v1 ||
538                 e1->v1 == e2->v2 ||
539                 e1->v2 == e2->v1 ||
540                 e1->v2 == e2->v2);
541 }
542
543 /**
544  *      Return the shared vertex between the two edges or NULL
545  */
546 BMVert *BM_edge_share_vert(BMEdge *e1, BMEdge *e2)
547 {
548         if (BM_vert_in_edge(e2, e1->v1)) {
549                 return e1->v1;
550         }
551         else if (BM_vert_in_edge(e2, e1->v2)) {
552                 return e1->v2;
553         }
554         else {
555                 return NULL;
556         }
557 }
558
559 /**
560  * Returns the verts of an edge as used in a face
561  * if used in a face at all, otherwise just assign as used in the edge.
562  *
563  * Useful to get a determanistic winding order when calling
564  * BM_face_create_ngon() on an arbitrary array of verts,
565  * though be sure to pick an edge which has a face.
566  */
567 void BM_edge_ordered_verts(BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
568 {
569         if ((edge->l == NULL) ||
570             (((edge->l->prev->v == edge->v1) && (edge->l->v == edge->v2)) ||
571              ((edge->l->v == edge->v1) && (edge->l->next->v == edge->v2)))
572             )
573         {
574                 *r_v1 = edge->v1;
575                 *r_v2 = edge->v2;
576         }
577         else {
578                 *r_v1 = edge->v2;
579                 *r_v2 = edge->v1;
580         }
581 }
582
583 /**
584  * Calculates the angle between the previous and next loops
585  * (angle at this loops face corner).
586  *
587  * \return angle in radians
588  */
589 float BM_loop_face_angle(BMesh *UNUSED(bm), BMLoop *l)
590 {
591         return angle_v3v3v3(l->prev->v->co,
592                             l->v->co,
593                             l->next->v->co);
594 }
595
596 /**
597  * \brief BMESH EDGE/FACE ANGLE
598  *
599  *  Calculates the angle between two faces.
600  *  Assumes the face normals are correct.
601  *
602  * \return angle in radians
603  */
604 float BM_edge_face_angle(BMesh *UNUSED(bm), BMEdge *e)
605 {
606         if (BM_edge_face_count(e) == 2) {
607                 BMLoop *l1 = e->l;
608                 BMLoop *l2 = e->l->radial_next;
609                 return angle_normalized_v3v3(l1->f->no, l2->f->no);
610         }
611         else {
612                 return DEG2RADF(90.0f);
613         }
614 }
615
616 /**
617  * \brief BMESH VERT/EDGE ANGLE
618  *
619  * Calculates the angle a verts 2 edges.
620  *
621  * \returns the angle in radians
622  */
623 float BM_vert_edge_angle(BMesh *UNUSED(bm), BMVert *v)
624 {
625         BMEdge *e1, *e2;
626
627         /* saves BM_vert_edge_count(v) and and edge iterator,
628          * get the edges and count them both at once */
629
630         if ((e1 = v->e) &&
631                 (e2 =  bmesh_disk_edge_next(e1, v)) &&
632             /* make sure we come full circle and only have 2 connected edges */
633                 (e1 == bmesh_disk_edge_next(e2, v)))
634         {
635                 BMVert *v1 = BM_edge_other_vert(e1, v);
636                 BMVert *v2 = BM_edge_other_vert(e2, v);
637
638                 return M_PI - angle_v3v3v3(v1->co, v->co, v2->co);
639         }
640         else {
641                 return DEG2RADF(90.0f);
642         }
643 }
644
645 /**
646  * Returns the edge existing between v1 and v2, or NULL if there isn't one.
647  *
648  * \note multiple edges may exist between any two vertices, and therefore
649  * this function only returns the first one found.
650  */
651 BMEdge *BM_edge_exists(BMVert *v1, BMVert *v2)
652 {
653         BMIter iter;
654         BMEdge *e;
655
656         BM_ITER(e, &iter, NULL, BM_EDGES_OF_VERT, v1) {
657                 if (e->v1 == v2 || e->v2 == v2)
658                         return e;
659         }
660
661         return NULL;
662 }
663
664 /**
665  * Given a set of vertices \a varr, find out if
666  * all those vertices overlap an existing face.
667  *
668  * \note Making a face here is valid but in some cases you wont want to
669  * make a face thats part of another.
670  *
671  * \returns TRUE for overlap
672  *
673  */
674 int BM_face_exists_overlap(BMesh *bm, BMVert **varr, int len, BMFace **r_overlapface)
675 {
676         BMIter viter;
677         BMFace *f;
678         int i, amount;
679
680         for (i = 0; i < len; i++) {
681                 BM_ITER(f, &viter, bm, BM_FACES_OF_VERT, varr[i]) {
682                         amount = BM_verts_in_face(bm, f, varr, len);
683                         if (amount >= len) {
684                                 if (r_overlapface) {
685                                         *r_overlapface = f;
686                                 }
687                                 return TRUE;
688                         }
689                 }
690         }
691
692         if (r_overlapface) {
693                 *r_overlapface = NULL;
694         }
695
696         return FALSE;
697 }
698
699 /**
700  * Given a set of vertices (varr), find out if
701  * there is a face with exactly those vertices
702  * (and only those vertices).
703  */
704 int BM_face_exists(BMesh *bm, BMVert **varr, int len, BMFace **r_existface)
705 {
706         BMIter viter;
707         BMFace *f;
708         int i, amount;
709
710         for (i = 0; i < len; i++) {
711                 BM_ITER(f, &viter, bm, BM_FACES_OF_VERT, varr[i]) {
712                         amount = BM_verts_in_face(bm, f, varr, len);
713                         if (amount == len && amount == f->len) {
714                                 if (r_existface) {
715                                         *r_existface = f;
716                                 }
717                                 return TRUE;
718                         }
719                 }
720         }
721
722         if (r_existface) {
723                 *r_existface = NULL;
724         }
725         return FALSE;
726 }
727
728
729 /**
730  * Given a set of vertices and edges (\a varr, \a earr), find out if
731  * all those vertices are filled in by existing faces that _only_ use those vertices.
732  *
733  * This is for use in cases where creating a face is possible but would result in
734  * many overlapping faces.
735  *
736  * An example of how this is used: when 2 tri's are selected that share an edge,
737  * pressing Fkey would make a new overlapping quad (without a check like this)
738  *
739  * \a earr and \a varr can be in any order, however they _must_ form a closed loop.
740  */
741 int BM_face_exists_multi(BMesh *bm, BMVert **varr, BMEdge **earr, int len)
742 {
743         BMFace *f;
744         BMEdge *e;
745         BMVert *v;
746         int ok;
747         int tot_tag;
748
749         BMIter fiter;
750         BMIter viter;
751
752         int i;
753
754         for (i = 0; i < len; i++) {
755                 /* save some time by looping over edge faces rather then vert faces
756                  * will still loop over some faces twice but not as many */
757                 BM_ITER(f, &fiter, bm, BM_FACES_OF_EDGE, earr[i]) {
758                         BM_elem_flag_disable(f, BM_ELEM_INTERNAL_TAG);
759                         BM_ITER(v, &viter, bm, BM_VERTS_OF_FACE, f) {
760                                 BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
761                         }
762                 }
763
764                 /* clear all edge tags */
765                 BM_ITER(e, &fiter, bm, BM_EDGES_OF_VERT, varr[i]) {
766                         BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
767                 }
768         }
769
770         /* now tag all verts and edges in the boundry array as true so
771          * we can know if a face-vert is from our array */
772         for (i = 0; i < len; i++) {
773                 BM_elem_flag_enable(varr[i], BM_ELEM_INTERNAL_TAG);
774                 BM_elem_flag_enable(earr[i], BM_ELEM_INTERNAL_TAG);
775         }
776
777
778         /* so! boundry is tagged, everything else cleared */
779
780
781         /* 1) tag all faces connected to edges - if all their verts are boundry */
782         tot_tag = 0;
783         for (i = 0; i < len; i++) {
784                 BM_ITER(f, &fiter, bm, BM_FACES_OF_EDGE, earr[i]) {
785                         if (!BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
786                                 ok = TRUE;
787                                 BM_ITER(v, &viter, bm, BM_VERTS_OF_FACE, f) {
788                                         if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) {
789                                                 ok = FALSE;
790                                                 break;
791                                         }
792                                 }
793
794                                 if (ok) {
795                                         /* we only use boundry verts */
796                                         BM_elem_flag_enable(f, BM_ELEM_INTERNAL_TAG);
797                                         tot_tag++;
798                                 }
799                         }
800                         else {
801                                 /* we already found! */
802                         }
803                 }
804         }
805
806         if (tot_tag == 0) {
807                 /* no faces use only boundry verts, quit early */
808                 return FALSE;
809         }
810
811         /* 2) loop over non-boundry edges that use boundry verts,
812          *    check each have 2 tagges faces connected (faces that only use 'varr' verts) */
813         ok = TRUE;
814         for (i = 0; i < len; i++) {
815                 BM_ITER(e, &fiter, bm, BM_EDGES_OF_VERT, varr[i]) {
816
817                         if (/* non-boundry edge */
818                             BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == FALSE &&
819                             /* ...using boundry verts */
820                             BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) == TRUE &&
821                             BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG) == TRUE)
822                         {
823                                 int tot_face_tag = 0;
824                                 BM_ITER(f, &fiter, bm, BM_FACES_OF_EDGE, e) {
825                                         if (BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
826                                                 tot_face_tag++;
827                                         }
828                                 }
829
830                                 if (tot_face_tag != 2) {
831                                         ok = FALSE;
832                                         break;
833                                 }
834
835                         }
836                 }
837
838                 if (ok == FALSE) {
839                         break;
840                 }
841         }
842
843         return ok;
844 }
845
846 /* same as 'BM_face_exists_multi' but built vert array from edges */
847 int BM_face_exists_multi_edge(BMesh *bm, BMEdge **earr, int len)
848 {
849         BMVert **varr;
850         BLI_array_fixedstack_declare(varr, BM_NGON_STACK_SIZE, len, __func__);
851
852         int ok;
853         int i, i_next;
854
855         /* first check if verts have edges, if not we can bail out early */
856         ok = TRUE;
857         for (i = len - 1, i_next = 0; i_next < len; (i = i_next++)) {
858                 if (!(varr[i] = BM_edge_share_vert(earr[i], earr[i_next]))) {
859                         ok = FALSE;
860                         break;
861                 }
862         }
863
864         if (ok == FALSE) {
865                 BMESH_ASSERT(0);
866                 BLI_array_fixedstack_free(varr);
867                 return FALSE;
868         }
869
870         ok = BM_face_exists_multi(bm, varr, earr, len);
871
872         BLI_array_fixedstack_free(varr);
873
874         return ok;
875 }