b37a82c7228bd72528017cff6b689849f1117d36
[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  * Returns whether or not a given vertex is
46  * is part of a given edge.
47  */
48 int BM_vert_in_edge(BMEdge *e, BMVert *v)
49 {
50         return bmesh_vert_in_edge(e, v);
51 }
52
53 /**
54  * \brief Other Loop in Face Sharing an Edge
55  *
56  * Finds the other loop that shares \a v with \a e loop in \a f.
57  * <pre>
58  *     +----------+
59  *     |          |
60  *     |    f     |
61  *     |          |
62  *     +----------+ <-- return the face loop of this vertex.
63  *     v --> e
64  *     ^     ^ <------- These vert args define direction
65  *                      in the face to check.
66  *                      The faces loop direction is ignored.
67  * </pre>
68  */
69 BMLoop *BM_face_other_edge_loop(BMFace *f, BMEdge *e, BMVert *v)
70 {
71         BMLoop *l_iter;
72         BMLoop *l_first;
73
74         /* we could loop around the face too, but turns out this uses a lot
75          * more iterations (approx double with quads, many more with 5+ ngons) */
76         l_iter = l_first = e->l;
77
78         do {
79                 if (l_iter->e == e && l_iter->f == f) {
80                         break;
81                 }
82         } while ((l_iter = l_iter->radial_next) != l_first);
83         
84         return l_iter->v == v ? l_iter->prev : l_iter->next;
85 }
86
87 /**
88  * \brief Other Loop in Face Sharing a Vertex
89  *
90  * Finds the other loop in a face.
91  *
92  * This function returns a loop in \a f that shares an edge with \a v
93  * The direction is defined by \a v_prev, where the return value is
94  * the loop of what would be 'v_next'
95  * <pre>
96  *     +----------+ <-- return the face loop of this vertex.
97  *     |          |
98  *     |    f     |
99  *     |          |
100  *     +----------+
101  *     v_prev --> v
102  *     ^^^^^^     ^ <-- These vert args define direction
103  *                      in the face to check.
104  *                      The faces loop direction is ignored.
105  * </pre>
106  *
107  * \note \a v_prev and \a v _implicitly_ define an edge.
108  */
109 BMLoop *BM_face_other_vert_loop(BMFace *f, BMVert *v_prev, BMVert *v)
110 {
111         BMIter liter;
112         BMLoop *l_iter;
113
114         BLI_assert(BM_edge_exists(v_prev, v) != NULL);
115
116         BM_ITER_ELEM (l_iter, &liter, v, BM_LOOPS_OF_VERT) {
117                 if (l_iter->f == f) {
118                         break;
119                 }
120         }
121
122         if (l_iter) {
123                 if (l_iter->prev->v == v_prev) {
124                         return l_iter->next;
125                 }
126                 else if (l_iter->next->v == v_prev) {
127                         return l_iter->prev;
128                 }
129                 else {
130                         /* invalid args */
131                         BLI_assert(0);
132                         return NULL;
133                 }
134         }
135         else {
136                 /* invalid args */
137                 BLI_assert(0);
138                 return NULL;
139         }
140 }
141
142 /**
143  * \brief Other Loop in Face Sharing a Vert
144  *
145  * Finds the other loop that shares \a v with \a e loop in \a f.
146  * <pre>
147  *     +----------+ <-- return the face loop of this vertex.
148  *     |          |
149  *     |          |
150  *     |          |
151  *     +----------+ <-- This vertex defines the direction.
152  *           l    v
153  *           ^ <------- This loop defines both the face to search
154  *                      and the edge, in combination with 'v'
155  *                      The faces loop direction is ignored.
156  * </pre>
157  */
158
159 BMLoop *BM_loop_other_vert_loop(BMLoop *l, BMVert *v)
160 {
161 #if 0 /* works but slow */
162         return BM_face_other_vert_loop(l->f, BM_edge_other_vert(l->e, v), v);
163 #else
164         BMEdge *e = l->e;
165         BMVert *v_prev = BM_edge_other_vert(e, v);
166         if (l->v == v) {
167                 if (l->prev->v == v_prev) {
168                         return l->next;
169                 }
170                 else {
171                         BLI_assert(l->next->v == v_prev);
172
173                         return l->prev;
174                 }
175         }
176         else {
177                 BLI_assert(l->v == v_prev);
178
179                 if (l->prev->v == v) {
180                         return l->prev->prev;
181                 }
182                 else {
183                         BLI_assert(l->next->v == v);
184                         return l->next->next;
185                 }
186         }
187
188
189
190 #endif
191 }
192
193 /**
194  * Get the first loop of a vert. Uses the same initialization code for the first loop of the
195  * iterator API
196  */
197 BMLoop *BM_vert_find_first_loop(BMVert *v)
198 {
199         BMEdge *e;
200
201         if (!v || !v->e)
202                 return NULL;
203
204         e = bmesh_disk_faceedge_find_first(v->e, v);
205
206         if (!e)
207                 return NULL;
208
209         return bmesh_radial_faceloop_find_first(e->l, v);
210 }
211
212 /**
213  * Returns TRUE if the vertex is used in a given face.
214  */
215 int BM_vert_in_face(BMFace *f, BMVert *v)
216 {
217         BMLoop *l_iter, *l_first;
218
219 #ifdef USE_BMESH_HOLES
220         BMLoopList *lst;
221         for (lst = f->loops.first; lst; lst = lst->next)
222 #endif
223         {
224 #ifdef USE_BMESH_HOLES
225                 l_iter = l_first = lst->first;
226 #else
227                 l_iter = l_first = f->l_first;
228 #endif
229                 do {
230                         if (l_iter->v == v) {
231                                 return TRUE;
232                         }
233                 } while ((l_iter = l_iter->next) != l_first);
234         }
235
236         return FALSE;
237 }
238
239 /**
240  * Compares the number of vertices in an array
241  * that appear in a given face
242  */
243 int BM_verts_in_face(BMesh *bm, BMFace *f, BMVert **varr, int len)
244 {
245         BMLoop *l_iter, *l_first;
246
247 #ifdef USE_BMESH_HOLES
248         BMLoopList *lst;
249 #endif
250
251         int i, count = 0;
252         
253         for (i = 0; i < len; i++) {
254                 BMO_elem_flag_enable(bm, varr[i], BM_OVERLAP);
255         }
256
257 #ifdef USE_BMESH_HOLES
258         for (lst = f->loops.first; lst; lst = lst->next)
259 #endif
260         {
261
262 #ifdef USE_BMESH_HOLES
263                 l_iter = l_first = lst->first;
264 #else
265                 l_iter = l_first = f->l_first;
266 #endif
267
268                 do {
269                         if (BMO_elem_flag_test(bm, l_iter->v, BM_OVERLAP)) {
270                                 count++;
271                         }
272
273                 } while ((l_iter = l_iter->next) != l_first);
274         }
275
276         for (i = 0; i < len; i++) BMO_elem_flag_disable(bm, varr[i], BM_OVERLAP);
277
278         return count;
279 }
280
281 /**
282  * Returns whether or not a given edge is is part of a given face.
283  */
284 int BM_edge_in_face(BMFace *f, BMEdge *e)
285 {
286         BMLoop *l_iter;
287         BMLoop *l_first;
288
289         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
290
291         do {
292                 if (l_iter->e == e) {
293                         return TRUE;
294                 }
295         } while ((l_iter = l_iter->next) != l_first);
296
297         return FALSE;
298 }
299
300 /**
301  * Returns whether or not a given edge is is part of a given loop.
302  */
303 int BM_edge_in_loop(BMEdge *e, BMLoop *l)
304 {
305         return (l->e == e || l->prev->e == e);
306 }
307
308 /**
309  * Returns whether or not two vertices are in
310  * a given edge
311  */
312 int BM_verts_in_edge(BMVert *v1, BMVert *v2, BMEdge *e)
313 {
314         return bmesh_verts_in_edge(v1, v2, e);
315 }
316
317 /**
318  * Given a edge and one of its vertices, returns
319  * the other vertex.
320  */
321 BMVert *BM_edge_other_vert(BMEdge *e, BMVert *v)
322 {
323         return bmesh_edge_other_vert_get(e, v);
324 }
325
326 /**
327  * Given a edge and a loop (assumes the edge is manifold). returns
328  * the other faces loop, sharing the same vertex.
329  *
330  * <pre>
331  * +-------------------+
332  * |                   |
333  * |                   |
334  * |l_other <-- return |
335  * +-------------------+ <-- A manifold edge between 2 faces
336  * |l    e  <-- edge   |
337  * |^ <-------- loop   |
338  * |                   |
339  * +-------------------+
340  * </pre>
341  */
342 BMLoop *BM_edge_other_loop(BMEdge *e, BMLoop *l)
343 {
344         BMLoop *l_other;
345
346         // BLI_assert(BM_edge_is_manifold(e));  // TOO strict, just check if we have another radial face
347         BLI_assert(e->l && e->l->radial_next != e->l);
348         BLI_assert(BM_vert_in_edge(e, l->v));
349
350         l_other = (l->e == e) ? l : l->prev;
351         l_other = l_other->radial_next;
352         BLI_assert(l_other->e == e);
353
354         if (l_other->v == l->v) {
355                 /* pass */
356         }
357         else if (l_other->next->v == l->v) {
358                 l_other = l_other->next;
359         }
360         else {
361                 BLI_assert(0);
362         }
363
364         return l_other;
365 }
366
367 /**
368  * Utility function to step around a fan of loops,
369  * using an edge to mark the previous side.
370  *
371  * \note all edges must be manifold,
372  * once a non manifold edge is hit, return NULL.
373  *
374  * <pre>
375  *                ,.,-->|
376  *            _,-'      |
377  *          ,'          | (notice how 'e_step'
378  *         /            |  and 'l' define the
379  *        /             |  direction the arrow
380  *       |     return   |  points).
381  *       |     loop --> |
382  * ---------------------+---------------------
383  *         ^      l --> |
384  *         |            |
385  *  assign e_step       |
386  *                      |
387  *   begin e_step ----> |
388  *                      |
389  * </pre>
390  */
391
392 BMLoop *BM_vert_step_fan_loop(BMLoop *l, BMEdge **e_step)
393 {
394         BMEdge *e_prev = *e_step;
395         BMEdge *e_next;
396         if (l->e == e_prev) {
397                 e_next = l->prev->e;
398         }
399         else if (l->prev->e == e_prev) {
400                 e_next = l->e;
401         }
402         else {
403                 BLI_assert(0);
404                 return NULL;
405         }
406
407         if (BM_edge_is_manifold(e_next)) {
408                 return BM_edge_other_loop((*e_step = e_next), l);
409         }
410         else {
411                 return NULL;
412         }
413 }
414
415
416
417 /**
418  * The function takes a vertex at the center of a fan and returns the opposite edge in the fan.
419  * All edges in the fan must be manifold, otherwise return NULL.
420  *
421  * \note This could (probably) be done more effieiently.
422  */
423 BMEdge *BM_vert_other_disk_edge(BMVert *v, BMEdge *e_first)
424 {
425         BMLoop *l_a;
426         int tot = 0;
427         int i;
428
429         BLI_assert(BM_vert_in_edge(e_first, v));
430
431         l_a = e_first->l;
432         do {
433                 l_a = BM_loop_other_vert_loop(l_a, v);
434                 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
435                 if (BM_edge_is_manifold(l_a->e)) {
436                         l_a = l_a->radial_next;
437                 }
438                 else {
439                         return NULL;
440                 }
441
442                 tot++;
443         } while (l_a != e_first->l);
444
445         /* we know the total, now loop half way */
446         tot /= 2;
447         i = 0;
448
449         l_a = e_first->l;
450         do {
451                 if (i == tot) {
452                         l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
453                         return l_a->e;
454                 }
455
456                 l_a = BM_loop_other_vert_loop(l_a, v);
457                 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
458                 if (BM_edge_is_manifold(l_a->e)) {
459                         l_a = l_a->radial_next;
460                 }
461                 /* this wont have changed from the previous loop */
462
463
464                 i++;
465         } while (l_a != e_first->l);
466
467         return NULL;
468 }
469
470 /**
471  * Returms edge length
472  */
473 float BM_edge_calc_length(BMEdge *e)
474 {
475         return len_v3v3(e->v1->co, e->v2->co);
476 }
477
478 /**
479  * Utility function, since enough times we have an edge
480  * and want to access 2 connected faces.
481  *
482  * \return TRUE when only 2 faces are found.
483  */
484 int BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
485 {
486         BMLoop *la, *lb;
487
488         if ((la = e->l) &&
489             (lb = la->radial_next) &&
490             (la != lb) &&
491             (lb->radial_next == la))
492         {
493                 *r_fa = la->f;
494                 *r_fb = lb->f;
495                 return TRUE;
496         }
497         else {
498                 *r_fa = NULL;
499                 *r_fb = NULL;
500                 return FALSE;
501         }
502 }
503
504 /**
505  * Utility function, since enough times we have an edge
506  * and want to access 2 connected loops.
507  *
508  * \return TRUE when only 2 faces are found.
509  */
510 int BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
511 {
512         BMLoop *la, *lb;
513
514         if ((la = e->l) &&
515             (lb = la->radial_next) &&
516             (la != lb) &&
517             (lb->radial_next == la))
518         {
519                 *r_la = la;
520                 *r_lb = lb;
521                 return TRUE;
522         }
523         else {
524                 *r_la = NULL;
525                 *r_lb = NULL;
526                 return FALSE;
527         }
528 }
529
530 /**
531  *      Returns the number of edges around this vertex.
532  */
533 int BM_vert_edge_count(BMVert *v)
534 {
535         return bmesh_disk_count(v);
536 }
537
538 int BM_vert_edge_count_nonwire(BMVert *v)
539 {
540         int count = 0;
541         BMIter eiter;
542         BMEdge *edge;
543         BM_ITER_ELEM (edge, &eiter, v, BM_EDGES_OF_VERT) {
544                 if (edge->l) {
545                         count++;
546                 }
547         }
548         return count;
549 }
550 /**
551  *      Returns the number of faces around this edge
552  */
553 int BM_edge_face_count(BMEdge *e)
554 {
555         int count = 0;
556
557         if (e->l) {
558                 BMLoop *l_iter;
559                 BMLoop *l_first;
560
561                 l_iter = l_first = e->l;
562
563                 do {
564                         count++;
565                 } while ((l_iter = l_iter->radial_next) != l_first);
566         }
567
568         return count;
569 }
570
571 /**
572  * Returns the number of faces around this vert
573  * length matches #BM_LOOPS_OF_VERT iterator
574  */
575 int BM_vert_face_count(BMVert *v)
576 {
577         return bmesh_disk_facevert_count(v);
578 }
579
580 /**
581  * Tests whether or not the vertex is part of a wire edge.
582  * (ie: has no faces attached to it)
583  */
584 int BM_vert_is_wire(BMVert *v)
585 {
586         if (v->e) {
587                 BMEdge *e_first, *e_iter;
588
589                 e_first = e_iter = v->e;
590                 do {
591                         if (e_iter->l) {
592                                 return FALSE;
593                         }
594                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
595
596                 return TRUE;
597         }
598         else {
599                 return FALSE;
600         }
601 }
602
603 /**
604  * Tests whether or not the edge is part of a wire.
605  * (ie: has no faces attached to it)
606  */
607 int BM_edge_is_wire(BMEdge *e)
608 {
609         return (e->l) ? FALSE : TRUE;
610 }
611
612 /**
613  * A vertex is non-manifold if it meets the following conditions:
614  * 1: Loose - (has no edges/faces incident upon it).
615  * 2: Joins two distinct regions - (two pyramids joined at the tip).
616  * 3: Is part of a an edge with more than 2 faces.
617  * 4: Is part of a wire edge.
618  */
619 int BM_vert_is_manifold(BMVert *v)
620 {
621         BMEdge *e, *oe;
622         BMLoop *l;
623         int len, count, flag;
624
625         if (v->e == NULL) {
626                 /* loose vert */
627                 return FALSE;
628         }
629
630         /* count edges while looking for non-manifold edges */
631         len = 0;
632         oe = e = v->e;
633         do {
634                 /* loose edge or edge shared by more than two faces,
635                  * edges with 1 face user are OK, otherwise we could
636                  * use BM_edge_is_manifold() here */
637                 if (e->l == NULL || bmesh_radial_length(e->l) > 2) {
638                         return FALSE;
639                 }
640                 len++;
641         } while ((e = bmesh_disk_edge_next(e, v)) != oe);
642
643         count = 1;
644         flag = 1;
645         e = NULL;
646         oe = v->e;
647         l = oe->l;
648         while (e != oe) {
649                 l = (l->v == v) ? l->prev : l->next;
650                 e = l->e;
651                 count++; /* count the edges */
652
653                 if (flag && l->radial_next == l) {
654                         /* we've hit the edge of an open mesh, reset once */
655                         flag = 0;
656                         count = 1;
657                         oe = e;
658                         e = NULL;
659                         l = oe->l;
660                 }
661                 else if (l->radial_next == l) {
662                         /* break the loop */
663                         e = oe;
664                 }
665                 else {
666                         l = l->radial_next;
667                 }
668         }
669
670         if (count < len) {
671                 /* vert shared by multiple regions */
672                 return FALSE;
673         }
674
675         return TRUE;
676 }
677
678 /**
679  * Tests whether or not this edge is manifold.
680  * A manifold edge has exactly 2 faces attached to it.
681  */
682
683 #if 1 /* fast path for checking manifold */
684 int BM_edge_is_manifold(BMEdge *e)
685 {
686         const BMLoop *l = e->l;
687         return (l && (l->radial_next != l) &&             /* not 0 or 1 face users */
688                      (l->radial_next->radial_next == l)); /* 2 face users */
689 }
690 #else
691 int BM_edge_is_manifold(BMEdge *e)
692 {
693         int count = BM_edge_face_count(e);
694         if (count == 2) {
695                 return TRUE;
696         }
697         else {
698                 return FALSE;
699         }
700 }
701 #endif
702
703 /**
704  * Tests whether or not an edge is on the boundary
705  * of a shell (has one face associated with it)
706  */
707
708 #if 1 /* fast path for checking boundary */
709 int BM_edge_is_boundary(BMEdge *e)
710 {
711         const BMLoop *l = e->l;
712         return (l && (l->radial_next == l));
713 }
714 #else
715 int BM_edge_is_boundary(BMEdge *e)
716 {
717         int count = BM_edge_face_count(e);
718         if (count == 1) {
719                 return TRUE;
720         }
721         else {
722                 return FALSE;
723         }
724 }
725 #endif
726
727 /**
728  * Returns the number of faces that are adjacent to both f1 and f2,
729  * \note Could be sped up a bit by not using iterators and by tagging
730  * faces on either side, then count the tags rather then searching.
731  */
732 int BM_face_share_face_count(BMFace *f1, BMFace *f2)
733 {
734         BMIter iter1, iter2;
735         BMEdge *e;
736         BMFace *f;
737         int count = 0;
738
739         BM_ITER_ELEM (e, &iter1, f1, BM_EDGES_OF_FACE) {
740                 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
741                         if (f != f1 && f != f2 && BM_face_share_edge_check(f, f2))
742                                 count++;
743                 }
744         }
745
746         return count;
747 }
748
749 /**
750  * same as #BM_face_share_face_count but returns a bool
751  */
752 int BM_face_share_face_check(BMFace *f1, BMFace *f2)
753 {
754         BMIter iter1, iter2;
755         BMEdge *e;
756         BMFace *f;
757
758         BM_ITER_ELEM (e, &iter1, f1, BM_EDGES_OF_FACE) {
759                 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
760                         if (f != f1 && f != f2 && BM_face_share_edge_check(f, f2))
761                                 return TRUE;
762                 }
763         }
764
765         return FALSE;
766 }
767
768 /**
769  *  Counts the number of edges two faces share (if any)
770  */
771 int BM_face_share_edge_count(BMFace *f1, BMFace *f2)
772 {
773         BMLoop *l_iter;
774         BMLoop *l_first;
775         int count = 0;
776         
777         l_iter = l_first = BM_FACE_FIRST_LOOP(f1);
778         do {
779                 if (bmesh_radial_face_find(l_iter->e, f2)) {
780                         count++;
781                 }
782         } while ((l_iter = l_iter->next) != l_first);
783
784         return count;
785 }
786
787 /**
788  *  Returns TRUE if the faces share an edge
789  */
790 int BM_face_share_edge_check(BMFace *f1, BMFace *f2)
791 {
792         BMLoop *l_iter;
793         BMLoop *l_first;
794
795         l_iter = l_first = BM_FACE_FIRST_LOOP(f1);
796         do {
797                 if (bmesh_radial_face_find(l_iter->e, f2)) {
798                         return TRUE;
799                 }
800         } while ((l_iter = l_iter->next) != l_first);
801
802         return FALSE;
803 }
804
805 /**
806  *      Test if e1 shares any faces with e2
807  */
808 int BM_edge_share_face_check(BMEdge *e1, BMEdge *e2)
809 {
810         BMLoop *l;
811         BMFace *f;
812
813         if (e1->l && e2->l) {
814                 l = e1->l;
815                 do {
816                         f = l->f;
817                         if (bmesh_radial_face_find(e2, f)) {
818                                 return TRUE;
819                         }
820                         l = l->radial_next;
821                 } while (l != e1->l);
822         }
823         return FALSE;
824 }
825
826 /**
827  *      Tests to see if e1 shares a vertex with e2
828  */
829 int BM_edge_share_vert_check(BMEdge *e1, BMEdge *e2)
830 {
831         return (e1->v1 == e2->v1 ||
832                 e1->v1 == e2->v2 ||
833                 e1->v2 == e2->v1 ||
834                 e1->v2 == e2->v2);
835 }
836
837 /**
838  *      Return the shared vertex between the two edges or NULL
839  */
840 BMVert *BM_edge_share_vert(BMEdge *e1, BMEdge *e2)
841 {
842         if (BM_vert_in_edge(e2, e1->v1)) {
843                 return e1->v1;
844         }
845         else if (BM_vert_in_edge(e2, e1->v2)) {
846                 return e1->v2;
847         }
848         else {
849                 return NULL;
850         }
851 }
852
853 /**
854  * \brief Return the Loop Shared by Face and Vertex
855  *
856  * Finds the loop used which uses \a v in face loop \a l
857  *
858  * \note currently this just uses simple loop in future may be sped up
859  * using radial vars
860  */
861 BMLoop *BM_face_vert_share_loop(BMFace *f, BMVert *v)
862 {
863         BMLoop *l_first;
864         BMLoop *l_iter;
865
866         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
867         do {
868                 if (l_iter->v == v) {
869                         return l_iter;
870                 }
871         } while ((l_iter = l_iter->next) != l_first);
872
873         return NULL;
874 }
875
876 /**
877  * \brief Return the Loop Shared by Face and Edge
878  *
879  * Finds the loop used which uses \a e in face loop \a l
880  *
881  * \note currently this just uses simple loop in future may be sped up
882  * using radial vars
883  */
884 BMLoop *BM_face_edge_share_loop(BMFace *f, BMEdge *e)
885 {
886         BMLoop *l_first;
887         BMLoop *l_iter;
888
889         l_iter = l_first = e->l;
890         do {
891                 if (l_iter->f == f) {
892                         return l_iter;
893                 }
894         } while ((l_iter = l_iter->radial_next) != l_first);
895
896         return NULL;
897 }
898
899 /**
900  * Returns the verts of an edge as used in a face
901  * if used in a face at all, otherwise just assign as used in the edge.
902  *
903  * Useful to get a deterministic winding order when calling
904  * BM_face_create_ngon() on an arbitrary array of verts,
905  * though be sure to pick an edge which has a face.
906  *
907  * \note This is in fact quite a simple check, mainly include this function so the intent is more obvious.
908  * We know these 2 verts will _always_ make up the loops edge
909  */
910 void BM_edge_ordered_verts_ex(BMEdge *edge, BMVert **r_v1, BMVert **r_v2,
911                               BMLoop *edge_loop)
912 {
913         BLI_assert(edge_loop->e == edge);
914         (void)edge; /* quiet warning in release build */
915         *r_v1 = edge_loop->v;
916         *r_v2 = edge_loop->next->v;
917 }
918
919 void BM_edge_ordered_verts(BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
920 {
921         BM_edge_ordered_verts_ex(edge, r_v1, r_v2, edge->l);
922 }
923
924 /**
925  * Calculates the angle between the previous and next loops
926  * (angle at this loops face corner).
927  *
928  * \return angle in radians
929  */
930 float BM_loop_calc_face_angle(BMLoop *l)
931 {
932         return angle_v3v3v3(l->prev->v->co,
933                             l->v->co,
934                             l->next->v->co);
935 }
936
937 /**
938  * \brief BM_loop_calc_face_normal
939  *
940  * Calculate the normal at this loop corner or fallback to the face normal on straight lines.
941  *
942  * \param l The loop to calculate the normal at
943  * \param r_normal Resulting normal
944  */
945 void BM_loop_calc_face_normal(BMLoop *l, float r_normal[3])
946 {
947         if (normal_tri_v3(r_normal,
948                           l->prev->v->co,
949                           l->v->co,
950                           l->next->v->co) != 0.0f)
951         {
952                 return;
953         }
954         else {
955                 copy_v3_v3(r_normal, l->f->no);
956         }
957 }
958
959 /**
960  * \brief BM_loop_calc_face_tangent
961  *
962  * Calculate the tangent at this loop corner or fallback to the face normal on straight lines.
963  * This vector always points inward into the face.
964  *
965  * \param l The loop to calculate the tangent at
966  * \param r_tangent Resulting tangent
967  */
968 void BM_loop_calc_face_tangent(BMLoop *l, float r_tangent[3])
969 {
970         float v_prev[3];
971         float v_next[3];
972
973         sub_v3_v3v3(v_prev, l->prev->v->co, l->v->co);
974         sub_v3_v3v3(v_next, l->v->co, l->next->v->co);
975
976         normalize_v3(v_prev);
977         normalize_v3(v_next);
978
979         if (compare_v3v3(v_prev, v_next, FLT_EPSILON) == FALSE) {
980                 float dir[3];
981                 float nor[3]; /* for this purpose doesn't need to be normalized */
982                 add_v3_v3v3(dir, v_prev, v_next);
983                 cross_v3_v3v3(nor, v_prev, v_next);
984                 cross_v3_v3v3(r_tangent, dir, nor);
985         }
986         else {
987                 /* prev/next are the same - compare with face normal since we don't have one */
988                 cross_v3_v3v3(r_tangent, v_next, l->f->no);
989         }
990
991         normalize_v3(r_tangent);
992 }
993
994 /**
995  * \brief BMESH EDGE/FACE ANGLE
996  *
997  *  Calculates the angle between two faces.
998  *  Assumes the face normals are correct.
999  *
1000  * \return angle in radians
1001  */
1002 float BM_edge_calc_face_angle(BMEdge *e)
1003 {
1004         if (BM_edge_is_manifold(e)) {
1005                 BMLoop *l1 = e->l;
1006                 BMLoop *l2 = e->l->radial_next;
1007                 return angle_normalized_v3v3(l1->f->no, l2->f->no);
1008         }
1009         else {
1010                 return DEG2RADF(90.0f);
1011         }
1012 }
1013
1014 /**
1015  * \brief BMESH EDGE/FACE TANGENT
1016  *
1017  * Calculate the tangent at this loop corner or fallback to the face normal on straight lines.
1018  * This vector always points inward into the face.
1019  *
1020  * \brief BM_edge_calc_face_tangent
1021  * \param e
1022  * \param e_loop The loop to calculate the tangent at,
1023  * used to get the face and winding direction.
1024  * \param r_tangent The loop corner tangent to set
1025  */
1026
1027 void BM_edge_calc_face_tangent(BMEdge *e, BMLoop *e_loop, float r_tangent[3])
1028 {
1029         float tvec[3];
1030         BMVert *v1, *v2;
1031         BM_edge_ordered_verts_ex(e, &v1, &v2, e_loop);
1032
1033         sub_v3_v3v3(tvec, v1->co, v2->co); /* use for temp storage */
1034         /* note, we could average the tangents of both loops,
1035          * for non flat ngons it will give a better direction */
1036         cross_v3_v3v3(r_tangent, tvec, e_loop->f->no);
1037         normalize_v3(r_tangent);
1038 }
1039
1040 /**
1041  * \brief BMESH VERT/EDGE ANGLE
1042  *
1043  * Calculates the angle a verts 2 edges.
1044  *
1045  * \returns the angle in radians
1046  */
1047 float BM_vert_calc_edge_angle(BMVert *v)
1048 {
1049         BMEdge *e1, *e2;
1050
1051         /* saves BM_vert_edge_count(v) and and edge iterator,
1052          * get the edges and count them both at once */
1053
1054         if ((e1 = v->e) &&
1055             (e2 =  bmesh_disk_edge_next(e1, v)) &&
1056             /* make sure we come full circle and only have 2 connected edges */
1057             (e1 == bmesh_disk_edge_next(e2, v)))
1058         {
1059                 BMVert *v1 = BM_edge_other_vert(e1, v);
1060                 BMVert *v2 = BM_edge_other_vert(e2, v);
1061
1062                 return (float)M_PI - angle_v3v3v3(v1->co, v->co, v2->co);
1063         }
1064         else {
1065                 return DEG2RADF(90.0f);
1066         }
1067 }
1068
1069 /**
1070  * \note this isn't optimal to run on an array of verts,
1071  * see 'solidify_add_thickness' for a function which runs on an array.
1072  */
1073 float BM_vert_calc_shell_factor(BMVert *v)
1074 {
1075         BMIter iter;
1076         BMLoop *l;
1077         float accum_shell = 0.0f;
1078         float accum_angle = 0.0f;
1079
1080         BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
1081                 const float face_angle = BM_loop_calc_face_angle(l);
1082                 accum_shell += shell_angle_to_dist(angle_normalized_v3v3(v->no, l->f->no)) * face_angle;
1083                 accum_angle += face_angle;
1084         }
1085
1086         if (accum_angle != 0.0f) {
1087                 return accum_shell / accum_angle;
1088         }
1089         else {
1090                 return 1.0f;
1091         }
1092 }
1093
1094 /**
1095  * \note quite an obscure function.
1096  * used in bmesh operators that have a relative scale options,
1097  */
1098 float BM_vert_calc_mean_tagged_edge_length(BMVert *v)
1099 {
1100         BMIter iter;
1101         BMEdge *e;
1102         int tot;
1103         float length = 0.0f;
1104
1105         BM_ITER_ELEM_INDEX (e, &iter, v, BM_EDGES_OF_VERT, tot) {
1106                 BMVert *v_other = BM_edge_other_vert(e, v);
1107                 if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
1108                         length += BM_edge_calc_length(e);
1109                 }
1110         }
1111
1112         if (tot) {
1113                 return length / (float)tot;
1114         }
1115         else {
1116                 return 0.0f;
1117         }
1118 }
1119
1120
1121 /**
1122  * Returns the loop of the shortest edge in f.
1123  */
1124 BMLoop *BM_face_find_shortest_loop(BMFace *f)
1125 {
1126         BMLoop *shortest_loop = NULL;
1127         float shortest_len = FLT_MAX;
1128
1129         BMLoop *l_iter;
1130         BMLoop *l_first;
1131
1132         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1133
1134         do {
1135                 const float len = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1136                 if (len <= shortest_len) {
1137                         shortest_loop = l_iter;
1138                         shortest_len = len;
1139                 }
1140         } while ((l_iter = l_iter->next) != l_first);
1141
1142         return shortest_loop;
1143 }
1144
1145 /**
1146  * Returns the loop of the longest edge in f.
1147  */
1148 BMLoop *BM_face_find_longest_loop(BMFace *f)
1149 {
1150         BMLoop *longest_loop = NULL;
1151         float longest_len = 0.0f;
1152
1153         BMLoop *l_iter;
1154         BMLoop *l_first;
1155
1156         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1157
1158         do {
1159                 const float len = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1160                 if (len >= longest_len) {
1161                         longest_loop = l_iter;
1162                         longest_len = len;
1163                 }
1164         } while ((l_iter = l_iter->next) != l_first);
1165
1166         return longest_loop;
1167 }
1168
1169 /**
1170  * Returns the edge existing between v1 and v2, or NULL if there isn't one.
1171  *
1172  * \note multiple edges may exist between any two vertices, and therefore
1173  * this function only returns the first one found.
1174  */
1175 BMEdge *BM_edge_exists(BMVert *v1, BMVert *v2)
1176 {
1177         BMIter iter;
1178         BMEdge *e;
1179
1180         BM_ITER_ELEM (e, &iter, v1, BM_EDGES_OF_VERT) {
1181                 if (e->v1 == v2 || e->v2 == v2)
1182                         return e;
1183         }
1184
1185         return NULL;
1186 }
1187
1188 /**
1189  * Returns an edge sharing the same vertices as this one.
1190  * This isn't an invalid state but tools should clean up these cases before
1191  * returning the mesh to the user.
1192  */
1193 BMEdge *BM_edge_find_double(BMEdge *e)
1194 {
1195         BMVert *v       = e->v1;
1196         BMVert *v_other = e->v2;
1197
1198         BMEdge *e_iter;
1199
1200         e_iter = e;
1201         while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e) {
1202                 if (UNLIKELY(BM_vert_in_edge(e_iter, v_other))) {
1203                         return e_iter;
1204                 }
1205         }
1206
1207         return NULL;
1208 }
1209
1210 /**
1211  * Given a set of vertices \a varr, find out if
1212  * all those vertices overlap an existing face.
1213  *
1214  * \note Making a face here is valid but in some cases you wont want to
1215  * make a face thats part of another.
1216  *
1217  * \returns TRUE for overlap
1218  *
1219  */
1220 int BM_face_exists_overlap(BMesh *bm, BMVert **varr, int len, BMFace **r_overlapface)
1221 {
1222         BMIter viter;
1223         BMFace *f;
1224         int i, amount;
1225
1226         for (i = 0; i < len; i++) {
1227                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
1228                         amount = BM_verts_in_face(bm, f, varr, len);
1229                         if (amount >= len) {
1230                                 if (r_overlapface) {
1231                                         *r_overlapface = f;
1232                                 }
1233                                 return TRUE;
1234                         }
1235                 }
1236         }
1237
1238         if (r_overlapface) {
1239                 *r_overlapface = NULL;
1240         }
1241
1242         return FALSE;
1243 }
1244
1245 /**
1246  * Given a set of vertices (varr), find out if
1247  * there is a face with exactly those vertices
1248  * (and only those vertices).
1249  */
1250 int BM_face_exists(BMesh *bm, BMVert **varr, int len, BMFace **r_existface)
1251 {
1252         BMIter viter;
1253         BMFace *f;
1254         int i, amount;
1255
1256         for (i = 0; i < len; i++) {
1257                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
1258                         amount = BM_verts_in_face(bm, f, varr, len);
1259                         if (amount == len && amount == f->len) {
1260                                 if (r_existface) {
1261                                         *r_existface = f;
1262                                 }
1263                                 return TRUE;
1264                         }
1265                 }
1266         }
1267
1268         if (r_existface) {
1269                 *r_existface = NULL;
1270         }
1271         return FALSE;
1272 }
1273
1274
1275 /**
1276  * Given a set of vertices and edges (\a varr, \a earr), find out if
1277  * all those vertices are filled in by existing faces that _only_ use those vertices.
1278  *
1279  * This is for use in cases where creating a face is possible but would result in
1280  * many overlapping faces.
1281  *
1282  * An example of how this is used: when 2 tri's are selected that share an edge,
1283  * pressing Fkey would make a new overlapping quad (without a check like this)
1284  *
1285  * \a earr and \a varr can be in any order, however they _must_ form a closed loop.
1286  */
1287 int BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len)
1288 {
1289         BMFace *f;
1290         BMEdge *e;
1291         BMVert *v;
1292         int ok;
1293         int tot_tag;
1294
1295         BMIter fiter;
1296         BMIter viter;
1297
1298         int i;
1299
1300         for (i = 0; i < len; i++) {
1301                 /* save some time by looping over edge faces rather then vert faces
1302                  * will still loop over some faces twice but not as many */
1303                 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
1304                         BM_elem_flag_disable(f, BM_ELEM_INTERNAL_TAG);
1305                         BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
1306                                 BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
1307                         }
1308                 }
1309
1310                 /* clear all edge tags */
1311                 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
1312                         BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
1313                 }
1314         }
1315
1316         /* now tag all verts and edges in the boundary array as true so
1317          * we can know if a face-vert is from our array */
1318         for (i = 0; i < len; i++) {
1319                 BM_elem_flag_enable(varr[i], BM_ELEM_INTERNAL_TAG);
1320                 BM_elem_flag_enable(earr[i], BM_ELEM_INTERNAL_TAG);
1321         }
1322
1323
1324         /* so! boundary is tagged, everything else cleared */
1325
1326
1327         /* 1) tag all faces connected to edges - if all their verts are boundary */
1328         tot_tag = 0;
1329         for (i = 0; i < len; i++) {
1330                 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
1331                         if (!BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
1332                                 ok = TRUE;
1333                                 BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
1334                                         if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) {
1335                                                 ok = FALSE;
1336                                                 break;
1337                                         }
1338                                 }
1339
1340                                 if (ok) {
1341                                         /* we only use boundary verts */
1342                                         BM_elem_flag_enable(f, BM_ELEM_INTERNAL_TAG);
1343                                         tot_tag++;
1344                                 }
1345                         }
1346                         else {
1347                                 /* we already found! */
1348                         }
1349                 }
1350         }
1351
1352         if (tot_tag == 0) {
1353                 /* no faces use only boundary verts, quit early */
1354                 return FALSE;
1355         }
1356
1357         /* 2) loop over non-boundary edges that use boundary verts,
1358          *    check each have 2 tagges faces connected (faces that only use 'varr' verts) */
1359         ok = TRUE;
1360         for (i = 0; i < len; i++) {
1361                 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
1362
1363                         if (/* non-boundary edge */
1364                             BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == FALSE &&
1365                             /* ...using boundary verts */
1366                             BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) == TRUE &&
1367                             BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG) == TRUE)
1368                         {
1369                                 int tot_face_tag = 0;
1370                                 BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
1371                                         if (BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
1372                                                 tot_face_tag++;
1373                                         }
1374                                 }
1375
1376                                 if (tot_face_tag != 2) {
1377                                         ok = FALSE;
1378                                         break;
1379                                 }
1380
1381                         }
1382                 }
1383
1384                 if (ok == FALSE) {
1385                         break;
1386                 }
1387         }
1388
1389         return ok;
1390 }
1391
1392 /* same as 'BM_face_exists_multi' but built vert array from edges */
1393 int BM_face_exists_multi_edge(BMEdge **earr, int len)
1394 {
1395         BMVert **varr;
1396         BLI_array_fixedstack_declare(varr, BM_NGON_STACK_SIZE, len, __func__);
1397
1398         int ok;
1399         int i, i_next;
1400
1401         /* first check if verts have edges, if not we can bail out early */
1402         ok = TRUE;
1403         for (i = len - 1, i_next = 0; i_next < len; (i = i_next++)) {
1404                 if (!(varr[i] = BM_edge_share_vert(earr[i], earr[i_next]))) {
1405                         ok = FALSE;
1406                         break;
1407                 }
1408         }
1409
1410         if (ok == FALSE) {
1411                 BMESH_ASSERT(0);
1412                 BLI_array_fixedstack_free(varr);
1413                 return FALSE;
1414         }
1415
1416         ok = BM_face_exists_multi(varr, earr, len);
1417
1418         BLI_array_fixedstack_free(varr);
1419
1420         return ok;
1421 }
1422
1423 /* convenience functiosn for checking flags */
1424 int BM_edge_is_any_vert_flag_test(BMEdge *e, const char hflag)
1425 {
1426         return (BM_elem_flag_test(e->v1, hflag) ||
1427                 BM_elem_flag_test(e->v2, hflag));
1428 }
1429
1430 int BM_face_is_any_vert_flag_test(BMFace *f, const char hflag)
1431 {
1432         BMLoop *l_iter;
1433         BMLoop *l_first;
1434
1435         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1436         do {
1437                 if (BM_elem_flag_test(l_iter->v, hflag)) {
1438                         return TRUE;
1439                 }
1440         } while ((l_iter = l_iter->next) != l_first);
1441         return FALSE;
1442 }
1443
1444 int BM_face_is_any_edge_flag_test(BMFace *f, const char hflag)
1445 {
1446         BMLoop *l_iter;
1447         BMLoop *l_first;
1448
1449         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1450         do {
1451                 if (BM_elem_flag_test(l_iter->e, hflag)) {
1452                         return TRUE;
1453                 }
1454         } while ((l_iter = l_iter->next) != l_first);
1455         return FALSE;
1456 }