remove BM_ITER, BM_ITER_INDEX macros, use ELEM or MESH variants only (the maceros...
[blender-staging.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_ELEM (l_iter, &liter, v, BM_LOOPS_OF_VERT) {
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  * \brief Other Loop in Face Sharing a Vert
156  *
157  * Finds the other loop that shares \a v with \a e loop in \a f.
158  *
159  *     +----------+ <-- return the face loop of this vertex.
160  *     |          |
161  *     |          |
162  *     |          |
163  *     +----------+ <-- This vertex defines the direction.
164  *           l    v
165  *           ^ <------- This loop defines both the face to search
166  *                      and the edge, in combination with 'v'
167  *                      The faces loop direction is ignored.
168  */
169
170 BMLoop *BM_loop_other_vert_loop(BMLoop *l, BMVert *v)
171 {
172 #if 0 /* works but slow */
173         return BM_face_other_vert_loop(l->f, BM_edge_other_vert(l->e, v), v);
174 #else
175         BMEdge *e = l->e;
176         BMVert *v_prev = BM_edge_other_vert(e, v);
177         if (l->v == v) {
178                 if (l->prev->v == v_prev) {
179                         return l->next;
180                 }
181                 else {
182                         BLI_assert(l->next->v == v_prev);
183
184                         return l->prev;
185                 }
186         }
187         else {
188                 BLI_assert(l->v == v_prev);
189
190                 if (l->prev->v == v) {
191                         return l->prev->prev;
192                 }
193                 else {
194                         BLI_assert(l->next->v == v);
195                         return l->next->next;
196                 }
197         }
198
199
200
201 #endif
202 }
203
204 /**
205  * Returns TRUE if the vertex is used in a given face.
206  */
207
208 int BM_vert_in_face(BMFace *f, BMVert *v)
209 {
210         BMLoop *l_iter, *l_first;
211
212 #ifdef USE_BMESH_HOLES
213         BMLoopList *lst;
214         for (lst = f->loops.first; lst; lst = lst->next)
215 #endif
216         {
217 #ifdef USE_BMESH_HOLES
218                 l_iter = l_first = lst->first;
219 #else
220                 l_iter = l_first = f->l_first;
221 #endif
222                 do {
223                         if (l_iter->v == v) {
224                                 return TRUE;
225                         }
226                 } while ((l_iter = l_iter->next) != l_first);
227         }
228
229         return FALSE;
230 }
231
232 /**
233  * Compares the number of vertices in an array
234  * that appear in a given face
235  */
236 int BM_verts_in_face(BMesh *bm, BMFace *f, BMVert **varr, int len)
237 {
238         BMLoop *l_iter, *l_first;
239
240 #ifdef USE_BMESH_HOLES
241         BMLoopList *lst;
242 #endif
243
244         int i, count = 0;
245         
246         for (i = 0; i < len; i++) {
247                 BMO_elem_flag_enable(bm, varr[i], BM_OVERLAP);
248         }
249
250 #ifdef USE_BMESH_HOLES
251         for (lst = f->loops.first; lst; lst = lst->next)
252 #endif
253         {
254
255 #ifdef USE_BMESH_HOLES
256                 l_iter = l_first = lst->first;
257 #else
258                 l_iter = l_first = f->l_first;
259 #endif
260
261                 do {
262                         if (BMO_elem_flag_test(bm, l_iter->v, BM_OVERLAP)) {
263                                 count++;
264                         }
265
266                 } while ((l_iter = l_iter->next) != l_first);
267         }
268
269         for (i = 0; i < len; i++) BMO_elem_flag_disable(bm, varr[i], BM_OVERLAP);
270
271         return count;
272 }
273
274 /**
275  * Returns whether or not a given edge is is part of a given face.
276  */
277 int BM_edge_in_face(BMFace *f, BMEdge *e)
278 {
279         BMLoop *l_iter;
280         BMLoop *l_first;
281
282         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
283
284         do {
285                 if (l_iter->e == e) {
286                         return TRUE;
287                 }
288         } while ((l_iter = l_iter->next) != l_first);
289
290         return FALSE;
291 }
292
293 /**
294  * Returns whether or not two vertices are in
295  * a given edge
296  */
297 int BM_verts_in_edge(BMVert *v1, BMVert *v2, BMEdge *e)
298 {
299         return bmesh_verts_in_edge(v1, v2, e);
300 }
301
302 /**
303  * Given a edge and one of its vertices, returns
304  * the other vertex.
305  */
306 BMVert *BM_edge_other_vert(BMEdge *e, BMVert *v)
307 {
308         return bmesh_edge_other_vert_get(e, v);
309 }
310
311 /**
312  * Returms edge length
313  */
314 float BM_edge_length_calc(BMEdge *e)
315 {
316         return len_v3v3(e->v1->co, e->v2->co);
317 }
318
319 /**
320  * Utility function, since enough times we have an edge
321  * and want to access 2 connected faces.
322  *
323  * \return TRUE when only 2 faces are found.
324  */
325 int BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
326 {
327         BMLoop *la, *lb;
328
329         if ((la = e->l) &&
330             (lb = la->radial_next) &&
331             (lb->radial_next == la))
332         {
333                 *r_fa = la->f;
334                 *r_fb = lb->f;
335                 return TRUE;
336         }
337         else {
338                 *r_fa = NULL;
339                 *r_fb = NULL;
340                 return FALSE;
341         }
342 }
343
344 /**
345  * Utility function, since enough times we have an edge
346  * and want to access 2 connected loops.
347  *
348  * \return TRUE when only 2 faces are found.
349  */
350 int BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
351 {
352         BMLoop *la, *lb;
353
354         if ((la = e->l) &&
355             (lb = la->radial_next) &&
356             (lb->radial_next == la))
357         {
358                 *r_la = la;
359                 *r_lb = lb;
360                 return TRUE;
361         }
362         else {
363                 *r_la = NULL;
364                 *r_lb = NULL;
365                 return FALSE;
366         }
367 }
368
369 /**
370  *      Returns the number of edges around this vertex.
371  */
372 int BM_vert_edge_count(BMVert *v)
373 {
374         return bmesh_disk_count(v);
375 }
376
377 int BM_vert_edge_count_nonwire(BMVert *v)
378 {
379         int count = 0;
380         BMIter eiter;
381         BMEdge *edge;
382         BM_ITER_ELEM (edge, &eiter, v, BM_EDGES_OF_VERT) {
383                 if (edge->l) {
384                         count++;
385                 }
386         }
387         return count;
388 }
389 /**
390  *      Returns the number of faces around this edge
391  */
392 int BM_edge_face_count(BMEdge *e)
393 {
394         int count = 0;
395
396         if (e->l) {
397                 BMLoop *l_iter;
398                 BMLoop *l_first;
399
400                 l_iter = l_first = e->l;
401
402                 do {
403                         count++;
404                 } while ((l_iter = l_iter->radial_next) != l_first);
405         }
406
407         return count;
408 }
409
410 /**
411  *      Returns the number of faces around this vert
412  */
413 int BM_vert_face_count(BMVert *v)
414 {
415         int count = 0;
416         BMLoop *l;
417         BMIter iter;
418
419         BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
420                 count++;
421         }
422
423         return count;
424 #if 0 //this code isn't working
425         BMEdge *curedge = NULL;
426
427         if (v->e) {
428                 curedge = v->e;
429                 do {
430                         if (curedge->l) count += BM_edge_face_count(curedge);
431                         curedge = bmesh_disk_edge_next(curedge, v);
432                 } while (curedge != v->e);
433         }
434         return count;
435 #endif
436 }
437
438 /**
439  * Tests whether or not the vertex is part of a wire edge.
440  * (ie: has no faces attached to it)
441  */
442 int BM_vert_is_wire(BMVert *v)
443 {
444         BMEdge *curedge;
445
446         if (v->e == NULL) {
447                 return FALSE;
448         }
449         
450         curedge = v->e;
451         do {
452                 if (curedge->l) {
453                         return FALSE;
454                 }
455
456                 curedge = bmesh_disk_edge_next(curedge, v);
457         } while (curedge != v->e);
458
459         return TRUE;
460 }
461
462 /**
463  * Tests whether or not the edge is part of a wire.
464  * (ie: has no faces attached to it)
465  */
466 int BM_edge_is_wire(BMEdge *e)
467 {
468         return (e->l) ? FALSE : TRUE;
469 }
470
471 /**
472  * A vertex is non-manifold if it meets the following conditions:
473  * 1: Loose - (has no edges/faces incident upon it).
474  * 2: Joins two distinct regions - (two pyramids joined at the tip).
475  * 3: Is part of a an edge with more than 2 faces.
476  * 4: Is part of a wire edge.
477  */
478 int BM_vert_is_manifold(BMVert *v)
479 {
480         BMEdge *e, *oe;
481         BMLoop *l;
482         int len, count, flag;
483
484         if (v->e == NULL) {
485                 /* loose vert */
486                 return FALSE;
487         }
488
489         /* count edges while looking for non-manifold edges */
490         len = 0;
491         oe = e = v->e;
492         do {
493                 /* loose edge or edge shared by more than two faces,
494                  * edges with 1 face user are OK, otherwise we could
495                  * use BM_edge_is_manifold() here */
496                 if (e->l == NULL || bmesh_radial_length(e->l) > 2) {
497                         return FALSE;
498                 }
499                 len++;
500         } while((e = bmesh_disk_edge_next(e, v)) != oe);
501
502         count = 1;
503         flag = 1;
504         e = NULL;
505         oe = v->e;
506         l = oe->l;
507         while (e != oe) {
508                 l = (l->v == v) ? l->prev : l->next;
509                 e = l->e;
510                 count++; /* count the edges */
511
512                 if (flag && l->radial_next == l) {
513                         /* we've hit the edge of an open mesh, reset once */
514                         flag = 0;
515                         count = 1;
516                         oe = e;
517                         e = NULL;
518                         l = oe->l;
519                 }
520                 else if (l->radial_next == l) {
521                         /* break the loop */
522                         e = oe;
523                 }
524                 else {
525                         l = l->radial_next;
526                 }
527         }
528
529         if (count < len) {
530                 /* vert shared by multiple regions */
531                 return FALSE;
532         }
533
534         return TRUE;
535 }
536
537 /**
538  * Tests whether or not this edge is manifold.
539  * A manifold edge has exactly 2 faces attached to it.
540  */
541
542 #if 1 /* fast path for checking manifold */
543 int BM_edge_is_manifold(BMEdge *e)
544 {
545         const BMLoop *l = e->l;
546         return (l && (l->radial_next != l) &&             /* not 0 or 1 face users */
547                      (l->radial_next->radial_next == l)); /* 2 face users */
548 }
549 #else
550 int BM_edge_is_manifold(BMEdge *e)
551 {
552         int count = BM_edge_face_count(e);
553         if (count == 2) {
554                 return TRUE;
555         }
556         else {
557                 return FALSE;
558         }
559 }
560 #endif
561
562 /**
563  * Tests whether or not an edge is on the boundary
564  * of a shell (has one face associated with it)
565  */
566
567 #if 1 /* fast path for checking boundary */
568 int BM_edge_is_boundary(BMEdge *e)
569 {
570         const BMLoop *l = e->l;
571         return (l && (l->radial_next == l));
572 }
573 #else
574 int BM_edge_is_boundary(BMEdge *e)
575 {
576         int count = BM_edge_face_count(e);
577         if (count == 1) {
578                 return TRUE;
579         }
580         else {
581                 return FALSE;
582         }
583 }
584 #endif
585
586 /**
587  *  Counts the number of edges two faces share (if any)
588  */
589 int BM_face_share_edge_count(BMFace *f1, BMFace *f2)
590 {
591         BMLoop *l_iter;
592         BMLoop *l_first;
593         int count = 0;
594         
595         l_iter = l_first = BM_FACE_FIRST_LOOP(f1);
596         do {
597                 if (bmesh_radial_face_find(l_iter->e, f2)) {
598                         count++;
599                 }
600         } while ((l_iter = l_iter->next) != l_first);
601
602         return count;
603 }
604
605 /**
606  *      Test if e1 shares any faces with e2
607  */
608 int BM_edge_share_face_count(BMEdge *e1, BMEdge *e2)
609 {
610         BMLoop *l;
611         BMFace *f;
612
613         if (e1->l && e2->l) {
614                 l = e1->l;
615                 do {
616                         f = l->f;
617                         if (bmesh_radial_face_find(e2, f)) {
618                                 return TRUE;
619                         }
620                         l = l->radial_next;
621                 } while (l != e1->l);
622         }
623         return FALSE;
624 }
625
626 /**
627  *      Tests to see if e1 shares a vertex with e2
628  */
629 int BM_edge_share_vert_count(BMEdge *e1, BMEdge *e2)
630 {
631         return (e1->v1 == e2->v1 ||
632                 e1->v1 == e2->v2 ||
633                 e1->v2 == e2->v1 ||
634                 e1->v2 == e2->v2);
635 }
636
637 /**
638  *      Return the shared vertex between the two edges or NULL
639  */
640 BMVert *BM_edge_share_vert(BMEdge *e1, BMEdge *e2)
641 {
642         if (BM_vert_in_edge(e2, e1->v1)) {
643                 return e1->v1;
644         }
645         else if (BM_vert_in_edge(e2, e1->v2)) {
646                 return e1->v2;
647         }
648         else {
649                 return NULL;
650         }
651 }
652
653 /**
654  * \brief Return the Loop Shared by Face and Vertex
655  *
656  * Finds the loop used which uses \a v in face loop \a l
657  *
658  * \note currenly this just uses simple loop in future may be speeded up
659  * using radial vars
660  */
661 BMLoop *BM_face_vert_share_loop(BMFace *f, BMVert *v)
662 {
663         BMLoop *l_first;
664         BMLoop *l_iter;
665
666         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
667         do {
668                 if (l_iter->v == v) {
669                         return l_iter;
670                 }
671         } while ((l_iter = l_iter->next) != l_first);
672
673         return NULL;
674 }
675
676 /**
677  * \brief Return the Loop Shared by Face and Edge
678  *
679  * Finds the loop used which uses \a e in face loop \a l
680  *
681  * \note currenly this just uses simple loop in future may be speeded up
682  * using radial vars
683  */
684 BMLoop *BM_face_edge_share_loop(BMFace *f, BMEdge *e)
685 {
686         BMLoop *l_first;
687         BMLoop *l_iter;
688
689         l_iter = l_first = e->l;
690         do {
691                 if (l_iter->f == f) {
692                         return l_iter;
693                 }
694         } while ((l_iter = l_iter->radial_next) != l_first);
695
696         return NULL;
697 }
698
699 /**
700  * Returns the verts of an edge as used in a face
701  * if used in a face at all, otherwise just assign as used in the edge.
702  *
703  * Useful to get a deterministic winding order when calling
704  * BM_face_create_ngon() on an arbitrary array of verts,
705  * though be sure to pick an edge which has a face.
706  *
707  * \note This is infact quite a simple check, mainly include this function so the intent is more obvious.
708  * We know these 2 verts will _always_ make up the loops edge
709  */
710 void BM_edge_ordered_verts_ex(BMEdge *edge, BMVert **r_v1, BMVert **r_v2,
711                               BMLoop *edge_loop)
712 {
713         BLI_assert(edge_loop->e == edge);
714         *r_v1 = edge_loop->v;
715         *r_v2 = edge_loop->next->v;
716 }
717
718 void BM_edge_ordered_verts(BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
719 {
720         BM_edge_ordered_verts_ex(edge, r_v1, r_v2, edge->l);
721 }
722
723 /**
724  * Calculates the angle between the previous and next loops
725  * (angle at this loops face corner).
726  *
727  * \return angle in radians
728  */
729 float BM_loop_face_angle(BMLoop *l)
730 {
731         return angle_v3v3v3(l->prev->v->co,
732                             l->v->co,
733                             l->next->v->co);
734 }
735
736 /**
737  * \brief BM_loop_face_normal
738  *
739  * Calculate the normal at this loop corner or fallback to the face normal on straignt lines.
740  *
741  * \param bm The BMesh
742  * \param l The loop to calculate the normal at
743  * \param r_normal Resulting normal
744  */
745 void BM_loop_face_normal(BMLoop *l, float r_normal[3])
746 {
747         if (normal_tri_v3(r_normal,
748                           l->prev->v->co,
749                           l->v->co,
750                           l->next->v->co) != 0.0f)
751         {
752                 return;
753         }
754         else {
755                 copy_v3_v3(r_normal, l->f->no);
756         }
757 }
758
759 /**
760  * \brief BM_loop_face_tangent
761  *
762  * Calculate the tangent at this loop corner or fallback to the face normal on straignt lines.
763  * This vector always points inward into the face.
764  *
765  * \param bm The BMesh
766  * \param l The loop to calculate the tangent at
767  * \param r_tangent Resulting tangent
768  */
769 void BM_loop_face_tangent(BMLoop *l, float r_tangent[3])
770 {
771         float v_prev[3];
772         float v_next[3];
773
774         sub_v3_v3v3(v_prev, l->prev->v->co, l->v->co);
775         sub_v3_v3v3(v_next, l->v->co, l->next->v->co);
776
777         normalize_v3(v_prev);
778         normalize_v3(v_next);
779
780         if (compare_v3v3(v_prev, v_next, FLT_EPSILON) == FALSE) {
781                 float dir[3];
782                 float nor[3]; /* for this purpose doesn't need to be normalized */
783                 add_v3_v3v3(dir, v_prev, v_next);
784                 cross_v3_v3v3(nor, v_prev, v_next);
785                 cross_v3_v3v3(r_tangent, dir, nor);
786         }
787         else {
788                 /* prev/next are the same - compare with face normal since we don't have one */
789                 cross_v3_v3v3(r_tangent, v_next, l->f->no);
790         }
791
792         normalize_v3(r_tangent);
793 }
794
795 /**
796  * \brief BMESH EDGE/FACE ANGLE
797  *
798  *  Calculates the angle between two faces.
799  *  Assumes the face normals are correct.
800  *
801  * \return angle in radians
802  */
803 float BM_edge_face_angle(BMEdge *e)
804 {
805         if (BM_edge_is_manifold(e)) {
806                 BMLoop *l1 = e->l;
807                 BMLoop *l2 = e->l->radial_next;
808                 return angle_normalized_v3v3(l1->f->no, l2->f->no);
809         }
810         else {
811                 return DEG2RADF(90.0f);
812         }
813 }
814
815 /**
816  * \brief BMESH EDGE/FACE TANGENT
817  *
818  * Calculate the tangent at this loop corner or fallback to the face normal on straignt lines.
819  * This vector always points inward into the face.
820  *
821  * \brief BM_edge_face_tangent
822  * \param e
823  * \param e_loop The loop to calculate the tangent at,
824  * used to get the face and winding direction.
825  */
826
827 void BM_edge_face_tangent(BMEdge *e, BMLoop *e_loop, float r_tangent[3])
828 {
829         float tvec[3];
830         BMVert *v1, *v2;
831         BM_edge_ordered_verts_ex(e, &v1, &v2, e_loop);
832
833         sub_v3_v3v3(tvec, v1->co, v2->co); /* use for temp storage */
834         /* note, we could average the tangents of both loops,
835          * for non flat ngons it will give a better direction */
836         cross_v3_v3v3(r_tangent, tvec, e_loop->f->no);
837         normalize_v3(r_tangent);
838 }
839
840 /**
841  * \brief BMESH VERT/EDGE ANGLE
842  *
843  * Calculates the angle a verts 2 edges.
844  *
845  * \returns the angle in radians
846  */
847 float BM_vert_edge_angle(BMVert *v)
848 {
849         BMEdge *e1, *e2;
850
851         /* saves BM_vert_edge_count(v) and and edge iterator,
852          * get the edges and count them both at once */
853
854         if ((e1 = v->e) &&
855                 (e2 =  bmesh_disk_edge_next(e1, v)) &&
856             /* make sure we come full circle and only have 2 connected edges */
857                 (e1 == bmesh_disk_edge_next(e2, v)))
858         {
859                 BMVert *v1 = BM_edge_other_vert(e1, v);
860                 BMVert *v2 = BM_edge_other_vert(e2, v);
861
862                 return M_PI - angle_v3v3v3(v1->co, v->co, v2->co);
863         }
864         else {
865                 return DEG2RADF(90.0f);
866         }
867 }
868
869 /**
870  * Returns the edge existing between v1 and v2, or NULL if there isn't one.
871  *
872  * \note multiple edges may exist between any two vertices, and therefore
873  * this function only returns the first one found.
874  */
875 BMEdge *BM_edge_exists(BMVert *v1, BMVert *v2)
876 {
877         BMIter iter;
878         BMEdge *e;
879
880         BM_ITER_ELEM (e, &iter, v1, BM_EDGES_OF_VERT) {
881                 if (e->v1 == v2 || e->v2 == v2)
882                         return e;
883         }
884
885         return NULL;
886 }
887
888 /**
889  * Given a set of vertices \a varr, find out if
890  * all those vertices overlap an existing face.
891  *
892  * \note Making a face here is valid but in some cases you wont want to
893  * make a face thats part of another.
894  *
895  * \returns TRUE for overlap
896  *
897  */
898 int BM_face_exists_overlap(BMesh *bm, BMVert **varr, int len, BMFace **r_overlapface)
899 {
900         BMIter viter;
901         BMFace *f;
902         int i, amount;
903
904         for (i = 0; i < len; i++) {
905                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
906                         amount = BM_verts_in_face(bm, f, varr, len);
907                         if (amount >= len) {
908                                 if (r_overlapface) {
909                                         *r_overlapface = f;
910                                 }
911                                 return TRUE;
912                         }
913                 }
914         }
915
916         if (r_overlapface) {
917                 *r_overlapface = NULL;
918         }
919
920         return FALSE;
921 }
922
923 /**
924  * Given a set of vertices (varr), find out if
925  * there is a face with exactly those vertices
926  * (and only those vertices).
927  */
928 int BM_face_exists(BMesh *bm, BMVert **varr, int len, BMFace **r_existface)
929 {
930         BMIter viter;
931         BMFace *f;
932         int i, amount;
933
934         for (i = 0; i < len; i++) {
935                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
936                         amount = BM_verts_in_face(bm, f, varr, len);
937                         if (amount == len && amount == f->len) {
938                                 if (r_existface) {
939                                         *r_existface = f;
940                                 }
941                                 return TRUE;
942                         }
943                 }
944         }
945
946         if (r_existface) {
947                 *r_existface = NULL;
948         }
949         return FALSE;
950 }
951
952
953 /**
954  * Given a set of vertices and edges (\a varr, \a earr), find out if
955  * all those vertices are filled in by existing faces that _only_ use those vertices.
956  *
957  * This is for use in cases where creating a face is possible but would result in
958  * many overlapping faces.
959  *
960  * An example of how this is used: when 2 tri's are selected that share an edge,
961  * pressing Fkey would make a new overlapping quad (without a check like this)
962  *
963  * \a earr and \a varr can be in any order, however they _must_ form a closed loop.
964  */
965 int BM_face_exists_multi(BMesh *bm, BMVert **varr, BMEdge **earr, int len)
966 {
967         BMFace *f;
968         BMEdge *e;
969         BMVert *v;
970         int ok;
971         int tot_tag;
972
973         BMIter fiter;
974         BMIter viter;
975
976         int i;
977
978         for (i = 0; i < len; i++) {
979                 /* save some time by looping over edge faces rather then vert faces
980                  * will still loop over some faces twice but not as many */
981                 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
982                         BM_elem_flag_disable(f, BM_ELEM_INTERNAL_TAG);
983                         BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
984                                 BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
985                         }
986                 }
987
988                 /* clear all edge tags */
989                 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
990                         BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
991                 }
992         }
993
994         /* now tag all verts and edges in the boundary array as true so
995          * we can know if a face-vert is from our array */
996         for (i = 0; i < len; i++) {
997                 BM_elem_flag_enable(varr[i], BM_ELEM_INTERNAL_TAG);
998                 BM_elem_flag_enable(earr[i], BM_ELEM_INTERNAL_TAG);
999         }
1000
1001
1002         /* so! boundary is tagged, everything else cleared */
1003
1004
1005         /* 1) tag all faces connected to edges - if all their verts are boundary */
1006         tot_tag = 0;
1007         for (i = 0; i < len; i++) {
1008                 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
1009                         if (!BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
1010                                 ok = TRUE;
1011                                 BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
1012                                         if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) {
1013                                                 ok = FALSE;
1014                                                 break;
1015                                         }
1016                                 }
1017
1018                                 if (ok) {
1019                                         /* we only use boundary verts */
1020                                         BM_elem_flag_enable(f, BM_ELEM_INTERNAL_TAG);
1021                                         tot_tag++;
1022                                 }
1023                         }
1024                         else {
1025                                 /* we already found! */
1026                         }
1027                 }
1028         }
1029
1030         if (tot_tag == 0) {
1031                 /* no faces use only boundary verts, quit early */
1032                 return FALSE;
1033         }
1034
1035         /* 2) loop over non-boundary edges that use boundary verts,
1036          *    check each have 2 tagges faces connected (faces that only use 'varr' verts) */
1037         ok = TRUE;
1038         for (i = 0; i < len; i++) {
1039                 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
1040
1041                         if (/* non-boundary edge */
1042                             BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == FALSE &&
1043                             /* ...using boundary verts */
1044                             BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) == TRUE &&
1045                             BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG) == TRUE)
1046                         {
1047                                 int tot_face_tag = 0;
1048                                 BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
1049                                         if (BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
1050                                                 tot_face_tag++;
1051                                         }
1052                                 }
1053
1054                                 if (tot_face_tag != 2) {
1055                                         ok = FALSE;
1056                                         break;
1057                                 }
1058
1059                         }
1060                 }
1061
1062                 if (ok == FALSE) {
1063                         break;
1064                 }
1065         }
1066
1067         return ok;
1068 }
1069
1070 /* same as 'BM_face_exists_multi' but built vert array from edges */
1071 int BM_face_exists_multi_edge(BMesh *bm, BMEdge **earr, int len)
1072 {
1073         BMVert **varr;
1074         BLI_array_fixedstack_declare(varr, BM_NGON_STACK_SIZE, len, __func__);
1075
1076         int ok;
1077         int i, i_next;
1078
1079         /* first check if verts have edges, if not we can bail out early */
1080         ok = TRUE;
1081         for (i = len - 1, i_next = 0; i_next < len; (i = i_next++)) {
1082                 if (!(varr[i] = BM_edge_share_vert(earr[i], earr[i_next]))) {
1083                         ok = FALSE;
1084                         break;
1085                 }
1086         }
1087
1088         if (ok == FALSE) {
1089                 BMESH_ASSERT(0);
1090                 BLI_array_fixedstack_free(varr);
1091                 return FALSE;
1092         }
1093
1094         ok = BM_face_exists_multi(bm, varr, earr, len);
1095
1096         BLI_array_fixedstack_free(varr);
1097
1098         return ok;
1099 }