bmesh py api, new functions:
[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  * \brief Radial Find a Vertex Loop in Face
561  *
562  * Finds the loop used which uses \a v in face loop \a l
563  *
564  * \note currenly this just uses simple loop in future may be speeded up
565  * using radial vars
566  */
567 BMLoop *BM_face_vert_share_loop(BMFace *f, BMVert *v)
568 {
569         BMLoop *l_first;
570         BMLoop *l_iter;
571
572         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
573         do {
574                 if (l_iter->v == v) {
575                         return l_iter;
576                 }
577         } while ((l_iter = l_iter->next) != l_first);
578
579         return NULL;
580 }
581
582 /**
583  * Returns the verts of an edge as used in a face
584  * if used in a face at all, otherwise just assign as used in the edge.
585  *
586  * Useful to get a determanistic winding order when calling
587  * BM_face_create_ngon() on an arbitrary array of verts,
588  * though be sure to pick an edge which has a face.
589  */
590 void BM_edge_ordered_verts(BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
591 {
592         if ((edge->l == NULL) ||
593             (((edge->l->prev->v == edge->v1) && (edge->l->v == edge->v2)) ||
594              ((edge->l->v == edge->v1) && (edge->l->next->v == edge->v2)))
595             )
596         {
597                 *r_v1 = edge->v1;
598                 *r_v2 = edge->v2;
599         }
600         else {
601                 *r_v1 = edge->v2;
602                 *r_v2 = edge->v1;
603         }
604 }
605
606 /**
607  * Calculates the angle between the previous and next loops
608  * (angle at this loops face corner).
609  *
610  * \return angle in radians
611  */
612 float BM_loop_face_angle(BMesh *UNUSED(bm), BMLoop *l)
613 {
614         return angle_v3v3v3(l->prev->v->co,
615                             l->v->co,
616                             l->next->v->co);
617 }
618
619 /**
620  * \brief BMESH EDGE/FACE ANGLE
621  *
622  *  Calculates the angle between two faces.
623  *  Assumes the face normals are correct.
624  *
625  * \return angle in radians
626  */
627 float BM_edge_face_angle(BMesh *UNUSED(bm), BMEdge *e)
628 {
629         if (BM_edge_face_count(e) == 2) {
630                 BMLoop *l1 = e->l;
631                 BMLoop *l2 = e->l->radial_next;
632                 return angle_normalized_v3v3(l1->f->no, l2->f->no);
633         }
634         else {
635                 return DEG2RADF(90.0f);
636         }
637 }
638
639 /**
640  * \brief BMESH VERT/EDGE ANGLE
641  *
642  * Calculates the angle a verts 2 edges.
643  *
644  * \returns the angle in radians
645  */
646 float BM_vert_edge_angle(BMesh *UNUSED(bm), BMVert *v)
647 {
648         BMEdge *e1, *e2;
649
650         /* saves BM_vert_edge_count(v) and and edge iterator,
651          * get the edges and count them both at once */
652
653         if ((e1 = v->e) &&
654                 (e2 =  bmesh_disk_edge_next(e1, v)) &&
655             /* make sure we come full circle and only have 2 connected edges */
656                 (e1 == bmesh_disk_edge_next(e2, v)))
657         {
658                 BMVert *v1 = BM_edge_other_vert(e1, v);
659                 BMVert *v2 = BM_edge_other_vert(e2, v);
660
661                 return M_PI - angle_v3v3v3(v1->co, v->co, v2->co);
662         }
663         else {
664                 return DEG2RADF(90.0f);
665         }
666 }
667
668 /**
669  * Returns the edge existing between v1 and v2, or NULL if there isn't one.
670  *
671  * \note multiple edges may exist between any two vertices, and therefore
672  * this function only returns the first one found.
673  */
674 BMEdge *BM_edge_exists(BMVert *v1, BMVert *v2)
675 {
676         BMIter iter;
677         BMEdge *e;
678
679         BM_ITER(e, &iter, NULL, BM_EDGES_OF_VERT, v1) {
680                 if (e->v1 == v2 || e->v2 == v2)
681                         return e;
682         }
683
684         return NULL;
685 }
686
687 /**
688  * Given a set of vertices \a varr, find out if
689  * all those vertices overlap an existing face.
690  *
691  * \note Making a face here is valid but in some cases you wont want to
692  * make a face thats part of another.
693  *
694  * \returns TRUE for overlap
695  *
696  */
697 int BM_face_exists_overlap(BMesh *bm, BMVert **varr, int len, BMFace **r_overlapface)
698 {
699         BMIter viter;
700         BMFace *f;
701         int i, amount;
702
703         for (i = 0; i < len; i++) {
704                 BM_ITER(f, &viter, bm, BM_FACES_OF_VERT, varr[i]) {
705                         amount = BM_verts_in_face(bm, f, varr, len);
706                         if (amount >= len) {
707                                 if (r_overlapface) {
708                                         *r_overlapface = f;
709                                 }
710                                 return TRUE;
711                         }
712                 }
713         }
714
715         if (r_overlapface) {
716                 *r_overlapface = NULL;
717         }
718
719         return FALSE;
720 }
721
722 /**
723  * Given a set of vertices (varr), find out if
724  * there is a face with exactly those vertices
725  * (and only those vertices).
726  */
727 int BM_face_exists(BMesh *bm, BMVert **varr, int len, BMFace **r_existface)
728 {
729         BMIter viter;
730         BMFace *f;
731         int i, amount;
732
733         for (i = 0; i < len; i++) {
734                 BM_ITER(f, &viter, bm, BM_FACES_OF_VERT, varr[i]) {
735                         amount = BM_verts_in_face(bm, f, varr, len);
736                         if (amount == len && amount == f->len) {
737                                 if (r_existface) {
738                                         *r_existface = f;
739                                 }
740                                 return TRUE;
741                         }
742                 }
743         }
744
745         if (r_existface) {
746                 *r_existface = NULL;
747         }
748         return FALSE;
749 }
750
751
752 /**
753  * Given a set of vertices and edges (\a varr, \a earr), find out if
754  * all those vertices are filled in by existing faces that _only_ use those vertices.
755  *
756  * This is for use in cases where creating a face is possible but would result in
757  * many overlapping faces.
758  *
759  * An example of how this is used: when 2 tri's are selected that share an edge,
760  * pressing Fkey would make a new overlapping quad (without a check like this)
761  *
762  * \a earr and \a varr can be in any order, however they _must_ form a closed loop.
763  */
764 int BM_face_exists_multi(BMesh *bm, BMVert **varr, BMEdge **earr, int len)
765 {
766         BMFace *f;
767         BMEdge *e;
768         BMVert *v;
769         int ok;
770         int tot_tag;
771
772         BMIter fiter;
773         BMIter viter;
774
775         int i;
776
777         for (i = 0; i < len; i++) {
778                 /* save some time by looping over edge faces rather then vert faces
779                  * will still loop over some faces twice but not as many */
780                 BM_ITER(f, &fiter, bm, BM_FACES_OF_EDGE, earr[i]) {
781                         BM_elem_flag_disable(f, BM_ELEM_INTERNAL_TAG);
782                         BM_ITER(v, &viter, bm, BM_VERTS_OF_FACE, f) {
783                                 BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
784                         }
785                 }
786
787                 /* clear all edge tags */
788                 BM_ITER(e, &fiter, bm, BM_EDGES_OF_VERT, varr[i]) {
789                         BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
790                 }
791         }
792
793         /* now tag all verts and edges in the boundry array as true so
794          * we can know if a face-vert is from our array */
795         for (i = 0; i < len; i++) {
796                 BM_elem_flag_enable(varr[i], BM_ELEM_INTERNAL_TAG);
797                 BM_elem_flag_enable(earr[i], BM_ELEM_INTERNAL_TAG);
798         }
799
800
801         /* so! boundry is tagged, everything else cleared */
802
803
804         /* 1) tag all faces connected to edges - if all their verts are boundry */
805         tot_tag = 0;
806         for (i = 0; i < len; i++) {
807                 BM_ITER(f, &fiter, bm, BM_FACES_OF_EDGE, earr[i]) {
808                         if (!BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
809                                 ok = TRUE;
810                                 BM_ITER(v, &viter, bm, BM_VERTS_OF_FACE, f) {
811                                         if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) {
812                                                 ok = FALSE;
813                                                 break;
814                                         }
815                                 }
816
817                                 if (ok) {
818                                         /* we only use boundry verts */
819                                         BM_elem_flag_enable(f, BM_ELEM_INTERNAL_TAG);
820                                         tot_tag++;
821                                 }
822                         }
823                         else {
824                                 /* we already found! */
825                         }
826                 }
827         }
828
829         if (tot_tag == 0) {
830                 /* no faces use only boundry verts, quit early */
831                 return FALSE;
832         }
833
834         /* 2) loop over non-boundry edges that use boundry verts,
835          *    check each have 2 tagges faces connected (faces that only use 'varr' verts) */
836         ok = TRUE;
837         for (i = 0; i < len; i++) {
838                 BM_ITER(e, &fiter, bm, BM_EDGES_OF_VERT, varr[i]) {
839
840                         if (/* non-boundry edge */
841                             BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == FALSE &&
842                             /* ...using boundry verts */
843                             BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) == TRUE &&
844                             BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG) == TRUE)
845                         {
846                                 int tot_face_tag = 0;
847                                 BM_ITER(f, &fiter, bm, BM_FACES_OF_EDGE, e) {
848                                         if (BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
849                                                 tot_face_tag++;
850                                         }
851                                 }
852
853                                 if (tot_face_tag != 2) {
854                                         ok = FALSE;
855                                         break;
856                                 }
857
858                         }
859                 }
860
861                 if (ok == FALSE) {
862                         break;
863                 }
864         }
865
866         return ok;
867 }
868
869 /* same as 'BM_face_exists_multi' but built vert array from edges */
870 int BM_face_exists_multi_edge(BMesh *bm, BMEdge **earr, int len)
871 {
872         BMVert **varr;
873         BLI_array_fixedstack_declare(varr, BM_NGON_STACK_SIZE, len, __func__);
874
875         int ok;
876         int i, i_next;
877
878         /* first check if verts have edges, if not we can bail out early */
879         ok = TRUE;
880         for (i = len - 1, i_next = 0; i_next < len; (i = i_next++)) {
881                 if (!(varr[i] = BM_edge_share_vert(earr[i], earr[i_next]))) {
882                         ok = FALSE;
883                         break;
884                 }
885         }
886
887         if (ok == FALSE) {
888                 BMESH_ASSERT(0);
889                 BLI_array_fixedstack_free(varr);
890                 return FALSE;
891         }
892
893         ok = BM_face_exists_multi(bm, varr, earr, len);
894
895         BLI_array_fixedstack_free(varr);
896
897         return ok;
898 }