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