Merging r58475 through r58700 from trunk into soc-2013-depsgraph_mt
[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_math.h"
37 #include "BLI_alloca.h"
38
39 #include "bmesh.h"
40 #include "intern/bmesh_private.h"
41
42 /**
43  * Returns whether or not a given vertex is
44  * is part of a given edge.
45  */
46 bool BM_vert_in_edge(const BMEdge *e, const BMVert *v)
47 {
48         return bmesh_vert_in_edge(e, v);
49 }
50
51 /**
52  * \brief Other Loop in Face Sharing an Edge
53  *
54  * Finds the other loop that shares \a v with \a e loop in \a f.
55  * <pre>
56  *     +----------+
57  *     |          |
58  *     |    f     |
59  *     |          |
60  *     +----------+ <-- return the face loop of this vertex.
61  *     v --> e
62  *     ^     ^ <------- These vert args define direction
63  *                      in the face to check.
64  *                      The faces loop direction is ignored.
65  * </pre>
66  *
67  * \note caller must ensure \a e is used in \a f
68  */
69 BMLoop *BM_face_other_edge_loop(BMFace *f, BMEdge *e, BMVert *v)
70 {
71         BMLoop *l = BM_face_edge_share_loop(f, e);
72         BLI_assert(l != NULL);
73         return BM_loop_other_edge_loop(l, v);
74 }
75
76 /**
77  * See #BM_face_other_edge_loop This is the same functionality
78  * to be used when the edges loop is already known.
79  */
80 BMLoop *BM_loop_other_edge_loop(BMLoop *l, BMVert *v)
81 {
82         BLI_assert(BM_vert_in_edge(l->e, v));
83         return l->v == v ? l->prev : l->next;
84 }
85
86 /**
87  * \brief Other Loop in Face Sharing a Vertex
88  *
89  * Finds the other loop in a face.
90  *
91  * This function returns a loop in \a f that shares an edge with \a v
92  * The direction is defined by \a v_prev, where the return value is
93  * the loop of what would be 'v_next'
94  * <pre>
95  *     +----------+ <-- return the face loop of this vertex.
96  *     |          |
97  *     |    f     |
98  *     |          |
99  *     +----------+
100  *     v_prev --> v
101  *     ^^^^^^     ^ <-- These vert args define direction
102  *                      in the face to check.
103  *                      The faces loop direction is ignored.
104  * </pre>
105  *
106  * \note \a v_prev and \a v _implicitly_ define an edge.
107  */
108 BMLoop *BM_face_other_vert_loop(BMFace *f, BMVert *v_prev, BMVert *v)
109 {
110         BMIter liter;
111         BMLoop *l_iter;
112
113         BLI_assert(BM_edge_exists(v_prev, v) != NULL);
114
115         BM_ITER_ELEM (l_iter, &liter, v, BM_LOOPS_OF_VERT) {
116                 if (l_iter->f == f) {
117                         break;
118                 }
119         }
120
121         if (l_iter) {
122                 if (l_iter->prev->v == v_prev) {
123                         return l_iter->next;
124                 }
125                 else if (l_iter->next->v == v_prev) {
126                         return l_iter->prev;
127                 }
128                 else {
129                         /* invalid args */
130                         BLI_assert(0);
131                         return NULL;
132                 }
133         }
134         else {
135                 /* invalid args */
136                 BLI_assert(0);
137                 return NULL;
138         }
139 }
140
141 /**
142  * \brief Other Loop in Face Sharing a Vert
143  *
144  * Finds the other loop that shares \a v with \a e loop in \a f.
145  * <pre>
146  *     +----------+ <-- return the face loop of this vertex.
147  *     |          |
148  *     |          |
149  *     |          |
150  *     +----------+ <-- This vertex defines the direction.
151  *           l    v
152  *           ^ <------- This loop defines both the face to search
153  *                      and the edge, in combination with 'v'
154  *                      The faces loop direction is ignored.
155  * </pre>
156  */
157
158 BMLoop *BM_loop_other_vert_loop(BMLoop *l, BMVert *v)
159 {
160 #if 0 /* works but slow */
161         return BM_face_other_vert_loop(l->f, BM_edge_other_vert(l->e, v), v);
162 #else
163         BMEdge *e = l->e;
164         BMVert *v_prev = BM_edge_other_vert(e, v);
165         if (l->v == v) {
166                 if (l->prev->v == v_prev) {
167                         return l->next;
168                 }
169                 else {
170                         BLI_assert(l->next->v == v_prev);
171
172                         return l->prev;
173                 }
174         }
175         else {
176                 BLI_assert(l->v == v_prev);
177
178                 if (l->prev->v == v) {
179                         return l->prev->prev;
180                 }
181                 else {
182                         BLI_assert(l->next->v == v);
183                         return l->next->next;
184                 }
185         }
186
187
188
189 #endif
190 }
191
192 /**
193  * Get the first loop of a vert. Uses the same initialization code for the first loop of the
194  * iterator API
195  */
196 BMLoop *BM_vert_find_first_loop(BMVert *v)
197 {
198         BMEdge *e;
199
200         if (!v || !v->e)
201                 return NULL;
202
203         e = bmesh_disk_faceedge_find_first(v->e, v);
204
205         if (!e)
206                 return NULL;
207
208         return bmesh_radial_faceloop_find_first(e->l, v);
209 }
210
211 /**
212  * Returns true if the vertex is used in a given face.
213  */
214 bool BM_vert_in_face(BMFace *f, BMVert *v)
215 {
216         BMLoop *l_iter, *l_first;
217
218 #ifdef USE_BMESH_HOLES
219         BMLoopList *lst;
220         for (lst = f->loops.first; lst; lst = lst->next)
221 #endif
222         {
223 #ifdef USE_BMESH_HOLES
224                 l_iter = l_first = lst->first;
225 #else
226                 l_iter = l_first = f->l_first;
227 #endif
228                 do {
229                         if (l_iter->v == v) {
230                                 return true;
231                         }
232                 } while ((l_iter = l_iter->next) != l_first);
233         }
234
235         return false;
236 }
237
238 /**
239  * Compares the number of vertices in an array
240  * that appear in a given face
241  */
242 int BM_verts_in_face_count(BMFace *f, BMVert **varr, int len)
243 {
244         BMLoop *l_iter, *l_first;
245
246 #ifdef USE_BMESH_HOLES
247         BMLoopList *lst;
248 #endif
249
250         int i, count = 0;
251         
252         for (i = 0; i < len; i++) {
253                 BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
254         }
255
256 #ifdef USE_BMESH_HOLES
257         for (lst = f->loops.first; lst; lst = lst->next)
258 #endif
259         {
260
261 #ifdef USE_BMESH_HOLES
262                 l_iter = l_first = lst->first;
263 #else
264                 l_iter = l_first = f->l_first;
265 #endif
266
267                 do {
268                         if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
269                                 count++;
270                         }
271
272                 } while ((l_iter = l_iter->next) != l_first);
273         }
274
275         for (i = 0; i < len; i++) {
276                 BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
277         }
278
279         return count;
280 }
281
282
283 /**
284  * Return true if all verts are in the face.
285  */
286 bool BM_verts_in_face(BMFace *f, BMVert **varr, int len)
287 {
288         BMLoop *l_iter, *l_first;
289
290 #ifdef USE_BMESH_HOLES
291         BMLoopList *lst;
292 #endif
293
294         int i;
295         bool ok = true;
296
297         /* simple check, we know can't succeed */
298         if (f->len < len) {
299                 return false;
300         }
301
302         for (i = 0; i < len; i++) {
303                 BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
304         }
305
306 #ifdef USE_BMESH_HOLES
307         for (lst = f->loops.first; lst; lst = lst->next)
308 #endif
309         {
310
311 #ifdef USE_BMESH_HOLES
312                 l_iter = l_first = lst->first;
313 #else
314                 l_iter = l_first = f->l_first;
315 #endif
316
317                 do {
318                         if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
319                                 /* pass */
320                         }
321                         else {
322                                 ok = false;
323                                 break;
324                         }
325
326                 } while ((l_iter = l_iter->next) != l_first);
327         }
328
329         for (i = 0; i < len; i++) {
330                 BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
331         }
332
333         return ok;
334 }
335
336 /**
337  * Returns whether or not a given edge is is part of a given face.
338  */
339 bool BM_edge_in_face(BMFace *f, BMEdge *e)
340 {
341         if (e->l) {
342                 BMLoop *l_iter, *l_first;
343
344                 l_iter = l_first = e->l;
345                 do {
346                         if (l_iter->f == f) {
347                                 return true;
348                         }
349                 } while ((l_iter = l_iter->radial_next) != l_first);
350         }
351
352         return false;
353 }
354
355 /**
356  * Returns whether or not a given edge is is part of a given loop.
357  */
358 bool BM_edge_in_loop(BMEdge *e, BMLoop *l)
359 {
360         return (l->e == e || l->prev->e == e);
361 }
362
363 /**
364  * Returns whether or not two vertices are in
365  * a given edge
366  */
367 bool BM_verts_in_edge(BMVert *v1, BMVert *v2, BMEdge *e)
368 {
369         return bmesh_verts_in_edge(v1, v2, e);
370 }
371
372 /**
373  * Given a edge and one of its vertices, returns
374  * the other vertex.
375  */
376 BMVert *BM_edge_other_vert(BMEdge *e, BMVert *v)
377 {
378         return bmesh_edge_other_vert_get(e, v);
379 }
380
381 /**
382  * Given a edge and a loop (assumes the edge is manifold). returns
383  * the other faces loop, sharing the same vertex.
384  *
385  * <pre>
386  * +-------------------+
387  * |                   |
388  * |                   |
389  * |l_other <-- return |
390  * +-------------------+ <-- A manifold edge between 2 faces
391  * |l    e  <-- edge   |
392  * |^ <-------- loop   |
393  * |                   |
394  * +-------------------+
395  * </pre>
396  */
397 BMLoop *BM_edge_other_loop(BMEdge *e, BMLoop *l)
398 {
399         BMLoop *l_other;
400
401         // BLI_assert(BM_edge_is_manifold(e));  // TOO strict, just check if we have another radial face
402         BLI_assert(e->l && e->l->radial_next != e->l);
403         BLI_assert(BM_vert_in_edge(e, l->v));
404
405         l_other = (l->e == e) ? l : l->prev;
406         l_other = l_other->radial_next;
407         BLI_assert(l_other->e == e);
408
409         if (l_other->v == l->v) {
410                 /* pass */
411         }
412         else if (l_other->next->v == l->v) {
413                 l_other = l_other->next;
414         }
415         else {
416                 BLI_assert(0);
417         }
418
419         return l_other;
420 }
421
422 /**
423  * Utility function to step around a fan of loops,
424  * using an edge to mark the previous side.
425  *
426  * \note all edges must be manifold,
427  * once a non manifold edge is hit, return NULL.
428  *
429  * <pre>
430  *                ,.,-->|
431  *            _,-'      |
432  *          ,'          | (notice how 'e_step'
433  *         /            |  and 'l' define the
434  *        /             |  direction the arrow
435  *       |     return   |  points).
436  *       |     loop --> |
437  * ---------------------+---------------------
438  *         ^      l --> |
439  *         |            |
440  *  assign e_step       |
441  *                      |
442  *   begin e_step ----> |
443  *                      |
444  * </pre>
445  */
446
447 BMLoop *BM_vert_step_fan_loop(BMLoop *l, BMEdge **e_step)
448 {
449         BMEdge *e_prev = *e_step;
450         BMEdge *e_next;
451         if (l->e == e_prev) {
452                 e_next = l->prev->e;
453         }
454         else if (l->prev->e == e_prev) {
455                 e_next = l->e;
456         }
457         else {
458                 BLI_assert(0);
459                 return NULL;
460         }
461
462         if (BM_edge_is_manifold(e_next)) {
463                 return BM_edge_other_loop((*e_step = e_next), l);
464         }
465         else {
466                 return NULL;
467         }
468 }
469
470
471
472 /**
473  * The function takes a vertex at the center of a fan and returns the opposite edge in the fan.
474  * All edges in the fan must be manifold, otherwise return NULL.
475  *
476  * \note This could (probably) be done more efficiently.
477  */
478 BMEdge *BM_vert_other_disk_edge(BMVert *v, BMEdge *e_first)
479 {
480         BMLoop *l_a;
481         int tot = 0;
482         int i;
483
484         BLI_assert(BM_vert_in_edge(e_first, v));
485
486         l_a = e_first->l;
487         do {
488                 l_a = BM_loop_other_vert_loop(l_a, v);
489                 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
490                 if (BM_edge_is_manifold(l_a->e)) {
491                         l_a = l_a->radial_next;
492                 }
493                 else {
494                         return NULL;
495                 }
496
497                 tot++;
498         } while (l_a != e_first->l);
499
500         /* we know the total, now loop half way */
501         tot /= 2;
502         i = 0;
503
504         l_a = e_first->l;
505         do {
506                 if (i == tot) {
507                         l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
508                         return l_a->e;
509                 }
510
511                 l_a = BM_loop_other_vert_loop(l_a, v);
512                 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
513                 if (BM_edge_is_manifold(l_a->e)) {
514                         l_a = l_a->radial_next;
515                 }
516                 /* this wont have changed from the previous loop */
517
518
519                 i++;
520         } while (l_a != e_first->l);
521
522         return NULL;
523 }
524
525 /**
526  * Returns edge length
527  */
528 float BM_edge_calc_length(BMEdge *e)
529 {
530         return len_v3v3(e->v1->co, e->v2->co);
531 }
532
533 /**
534  * Returns edge length squared (for comparisons)
535  */
536 float BM_edge_calc_length_squared(BMEdge *e)
537 {
538         return len_squared_v3v3(e->v1->co, e->v2->co);
539 }
540
541 /**
542  * Utility function, since enough times we have an edge
543  * and want to access 2 connected faces.
544  *
545  * \return true when only 2 faces are found.
546  */
547 bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
548 {
549         BMLoop *la, *lb;
550
551         if ((la = e->l) &&
552             (lb = la->radial_next) &&
553             (la != lb) &&
554             (lb->radial_next == la))
555         {
556                 *r_fa = la->f;
557                 *r_fb = lb->f;
558                 return true;
559         }
560         else {
561                 *r_fa = NULL;
562                 *r_fb = NULL;
563                 return false;
564         }
565 }
566
567 /**
568  * Utility function, since enough times we have an edge
569  * and want to access 2 connected loops.
570  *
571  * \return true when only 2 faces are found.
572  */
573 bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
574 {
575         BMLoop *la, *lb;
576
577         if ((la = e->l) &&
578             (lb = la->radial_next) &&
579             (la != lb) &&
580             (lb->radial_next == la))
581         {
582                 *r_la = la;
583                 *r_lb = lb;
584                 return true;
585         }
586         else {
587                 *r_la = NULL;
588                 *r_lb = NULL;
589                 return false;
590         }
591 }
592
593 /**
594  *      Returns the number of edges around this vertex.
595  */
596 int BM_vert_edge_count(BMVert *v)
597 {
598         return bmesh_disk_count(v);
599 }
600
601 int BM_vert_edge_count_nonwire(BMVert *v)
602 {
603         int count = 0;
604         BMIter eiter;
605         BMEdge *edge;
606         BM_ITER_ELEM (edge, &eiter, v, BM_EDGES_OF_VERT) {
607                 if (edge->l) {
608                         count++;
609                 }
610         }
611         return count;
612 }
613 /**
614  *      Returns the number of faces around this edge
615  */
616 int BM_edge_face_count(BMEdge *e)
617 {
618         int count = 0;
619
620         if (e->l) {
621                 BMLoop *l_iter;
622                 BMLoop *l_first;
623
624                 l_iter = l_first = e->l;
625
626                 do {
627                         count++;
628                 } while ((l_iter = l_iter->radial_next) != l_first);
629         }
630
631         return count;
632 }
633
634 /**
635  * Returns the number of faces around this vert
636  * length matches #BM_LOOPS_OF_VERT iterator
637  */
638 int BM_vert_face_count(BMVert *v)
639 {
640         return bmesh_disk_facevert_count(v);
641 }
642
643 /**
644  * Tests whether or not the vertex is part of a wire edge.
645  * (ie: has no faces attached to it)
646  */
647 bool BM_vert_is_wire(BMVert *v)
648 {
649         if (v->e) {
650                 BMEdge *e_first, *e_iter;
651
652                 e_first = e_iter = v->e;
653                 do {
654                         if (e_iter->l) {
655                                 return false;
656                         }
657                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
658
659                 return true;
660         }
661         else {
662                 return false;
663         }
664 }
665
666 /**
667  * Tests whether or not the edge is part of a wire.
668  * (ie: has no faces attached to it)
669  */
670 bool BM_edge_is_wire(BMEdge *e)
671 {
672         return (e->l == NULL);
673 }
674
675 /**
676  * A vertex is non-manifold if it meets the following conditions:
677  * 1: Loose - (has no edges/faces incident upon it).
678  * 2: Joins two distinct regions - (two pyramids joined at the tip).
679  * 3: Is part of a an edge with more than 2 faces.
680  * 4: Is part of a wire edge.
681  */
682 bool BM_vert_is_manifold(BMVert *v)
683 {
684         BMEdge *e, *e_old;
685         BMLoop *l;
686         int len, count, flag;
687
688         if (v->e == NULL) {
689                 /* loose vert */
690                 return false;
691         }
692
693         /* count edges while looking for non-manifold edges */
694         len = 0;
695         e_old = e = v->e;
696         do {
697                 /* loose edge or edge shared by more than two faces,
698                  * edges with 1 face user are OK, otherwise we could
699                  * use BM_edge_is_manifold() here */
700                 if (e->l == NULL || bmesh_radial_length(e->l) > 2) {
701                         return false;
702                 }
703                 len++;
704         } while ((e = bmesh_disk_edge_next(e, v)) != e_old);
705
706         count = 1;
707         flag = 1;
708         e = NULL;
709         e_old = v->e;
710         l = e_old->l;
711         while (e != e_old) {
712                 l = (l->v == v) ? l->prev : l->next;
713                 e = l->e;
714                 count++; /* count the edges */
715
716                 if (flag && l->radial_next == l) {
717                         /* we've hit the edge of an open mesh, reset once */
718                         flag = 0;
719                         count = 1;
720                         e_old = e;
721                         e = NULL;
722                         l = e_old->l;
723                 }
724                 else if (l->radial_next == l) {
725                         /* break the loop */
726                         e = e_old;
727                 }
728                 else {
729                         l = l->radial_next;
730                 }
731         }
732
733         if (count < len) {
734                 /* vert shared by multiple regions */
735                 return false;
736         }
737
738         return true;
739 }
740
741 /**
742  * Tests whether or not this edge is manifold.
743  * A manifold edge has exactly 2 faces attached to it.
744  */
745
746 #if 1 /* fast path for checking manifold */
747 bool BM_edge_is_manifold(BMEdge *e)
748 {
749         const BMLoop *l = e->l;
750         return (l && (l->radial_next != l) &&             /* not 0 or 1 face users */
751                      (l->radial_next->radial_next == l)); /* 2 face users */
752 }
753 #else
754 int BM_edge_is_manifold(BMEdge *e)
755 {
756         int count = BM_edge_face_count(e);
757         if (count == 2) {
758                 return true;
759         }
760         else {
761                 return false;
762         }
763 }
764 #endif
765
766 /**
767  * Tests that the edge is manifold and
768  * that both its faces point the same way.
769  */
770 bool BM_edge_is_contiguous(BMEdge *e)
771 {
772         const BMLoop *l = e->l;
773         const BMLoop *l_other;
774         return (l && ((l_other = l->radial_next) != l) &&  /* not 0 or 1 face users */
775                      (l_other->radial_next == l) &&        /* 2 face users */
776                      (l_other->v != l->v));
777 }
778
779 /**
780  * Check if the edge is convex or concave
781  * (depends on face winding)
782  */
783 bool BM_edge_is_convex(BMEdge *e)
784 {
785         if (BM_edge_is_manifold(e)) {
786                 BMLoop *l1 = e->l;
787                 BMLoop *l2 = e->l->radial_next;
788                 if (!equals_v3v3(l1->f->no, l2->f->no)) {
789                         float cross[3];
790                         float l_dir[3];
791                         cross_v3_v3v3(cross, l1->f->no, l2->f->no);
792                         /* we assume contiguous normals, otherwise the result isn't meaningful */
793                         sub_v3_v3v3(l_dir, l1->next->v->co, l1->v->co);
794                         return (dot_v3v3(l_dir, cross) > 0.0f);
795                 }
796         }
797         return true;
798 }
799
800 /**
801  * Tests whether or not an edge is on the boundary
802  * of a shell (has one face associated with it)
803  */
804
805 #if 1 /* fast path for checking boundary */
806 bool BM_edge_is_boundary(BMEdge *e)
807 {
808         const BMLoop *l = e->l;
809         return (l && (l->radial_next == l));
810 }
811 #else
812 int BM_edge_is_boundary(BMEdge *e)
813 {
814         int count = BM_edge_face_count(e);
815         if (count == 1) {
816                 return true;
817         }
818         else {
819                 return false;
820         }
821 }
822 #endif
823
824 bool BM_vert_is_boundary(BMVert *v)
825 {
826         if (v->e) {
827                 BMEdge *e_first, *e_iter;
828
829                 e_first = e_iter = v->e;
830                 do {
831                         if (BM_edge_is_boundary(e_iter)) {
832                                 return true;
833                         }
834                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
835
836                 return false;
837         }
838         else {
839                 return false;
840         }
841 }
842
843 /**
844  * Returns the number of faces that are adjacent to both f1 and f2,
845  * \note Could be sped up a bit by not using iterators and by tagging
846  * faces on either side, then count the tags rather then searching.
847  */
848 int BM_face_share_face_count(BMFace *f1, BMFace *f2)
849 {
850         BMIter iter1, iter2;
851         BMEdge *e;
852         BMFace *f;
853         int count = 0;
854
855         BM_ITER_ELEM (e, &iter1, f1, BM_EDGES_OF_FACE) {
856                 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
857                         if (f != f1 && f != f2 && BM_face_share_edge_check(f, f2))
858                                 count++;
859                 }
860         }
861
862         return count;
863 }
864
865 /**
866  * same as #BM_face_share_face_count but returns a bool
867  */
868 bool BM_face_share_face_check(BMFace *f1, BMFace *f2)
869 {
870         BMIter iter1, iter2;
871         BMEdge *e;
872         BMFace *f;
873
874         BM_ITER_ELEM (e, &iter1, f1, BM_EDGES_OF_FACE) {
875                 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
876                         if (f != f1 && f != f2 && BM_face_share_edge_check(f, f2))
877                                 return true;
878                 }
879         }
880
881         return false;
882 }
883
884 /**
885  *  Counts the number of edges two faces share (if any)
886  */
887 int BM_face_share_edge_count(BMFace *f1, BMFace *f2)
888 {
889         BMLoop *l_iter;
890         BMLoop *l_first;
891         int count = 0;
892         
893         l_iter = l_first = BM_FACE_FIRST_LOOP(f1);
894         do {
895                 if (bmesh_radial_face_find(l_iter->e, f2)) {
896                         count++;
897                 }
898         } while ((l_iter = l_iter->next) != l_first);
899
900         return count;
901 }
902
903 /**
904  *  Returns true if the faces share an edge
905  */
906 bool BM_face_share_edge_check(BMFace *f1, BMFace *f2)
907 {
908         BMLoop *l_iter;
909         BMLoop *l_first;
910
911         l_iter = l_first = BM_FACE_FIRST_LOOP(f1);
912         do {
913                 if (bmesh_radial_face_find(l_iter->e, f2)) {
914                         return true;
915                 }
916         } while ((l_iter = l_iter->next) != l_first);
917
918         return false;
919 }
920
921 /**
922  * Test if e1 shares any faces with e2
923  */
924 bool BM_edge_share_face_check(BMEdge *e1, BMEdge *e2)
925 {
926         BMLoop *l;
927         BMFace *f;
928
929         if (e1->l && e2->l) {
930                 l = e1->l;
931                 do {
932                         f = l->f;
933                         if (bmesh_radial_face_find(e2, f)) {
934                                 return true;
935                         }
936                         l = l->radial_next;
937                 } while (l != e1->l);
938         }
939         return false;
940 }
941
942 /**
943  *      Test if e1 shares any quad faces with e2
944  */
945 bool BM_edge_share_quad_check(BMEdge *e1, BMEdge *e2)
946 {
947         BMLoop *l;
948         BMFace *f;
949
950         if (e1->l && e2->l) {
951                 l = e1->l;
952                 do {
953                         f = l->f;
954                         if (f->len == 4) {
955                                 if (bmesh_radial_face_find(e2, f)) {
956                                         return true;
957                                 }
958                         }
959                         l = l->radial_next;
960                 } while (l != e1->l);
961         }
962         return false;
963 }
964
965 /**
966  *      Tests to see if e1 shares a vertex with e2
967  */
968 bool BM_edge_share_vert_check(BMEdge *e1, BMEdge *e2)
969 {
970         return (e1->v1 == e2->v1 ||
971                 e1->v1 == e2->v2 ||
972                 e1->v2 == e2->v1 ||
973                 e1->v2 == e2->v2);
974 }
975
976 /**
977  *      Return the shared vertex between the two edges or NULL
978  */
979 BMVert *BM_edge_share_vert(BMEdge *e1, BMEdge *e2)
980 {
981         BLI_assert(e1 != e2);
982         if (BM_vert_in_edge(e2, e1->v1)) {
983                 return e1->v1;
984         }
985         else if (BM_vert_in_edge(e2, e1->v2)) {
986                 return e1->v2;
987         }
988         else {
989                 return NULL;
990         }
991 }
992
993 /**
994  * \brief Return the Loop Shared by Face and Vertex
995  *
996  * Finds the loop used which uses \a v in face loop \a l
997  *
998  * \note currently this just uses simple loop in future may be sped up
999  * using radial vars
1000  */
1001 BMLoop *BM_face_vert_share_loop(BMFace *f, BMVert *v)
1002 {
1003         BMLoop *l_first;
1004         BMLoop *l_iter;
1005
1006         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1007         do {
1008                 if (l_iter->v == v) {
1009                         return l_iter;
1010                 }
1011         } while ((l_iter = l_iter->next) != l_first);
1012
1013         return NULL;
1014 }
1015
1016 /**
1017  * \brief Return the Loop Shared by Face and Edge
1018  *
1019  * Finds the loop used which uses \a e in face loop \a l
1020  *
1021  * \note currently this just uses simple loop in future may be sped up
1022  * using radial vars
1023  */
1024 BMLoop *BM_face_edge_share_loop(BMFace *f, BMEdge *e)
1025 {
1026         BMLoop *l_first;
1027         BMLoop *l_iter;
1028
1029         l_iter = l_first = e->l;
1030         do {
1031                 if (l_iter->f == f) {
1032                         return l_iter;
1033                 }
1034         } while ((l_iter = l_iter->radial_next) != l_first);
1035
1036         return NULL;
1037 }
1038
1039 /**
1040  * Returns the verts of an edge as used in a face
1041  * if used in a face at all, otherwise just assign as used in the edge.
1042  *
1043  * Useful to get a deterministic winding order when calling
1044  * BM_face_create_ngon() on an arbitrary array of verts,
1045  * though be sure to pick an edge which has a face.
1046  *
1047  * \note This is in fact quite a simple check, mainly include this function so the intent is more obvious.
1048  * We know these 2 verts will _always_ make up the loops edge
1049  */
1050 void BM_edge_ordered_verts_ex(BMEdge *edge, BMVert **r_v1, BMVert **r_v2,
1051                               BMLoop *edge_loop)
1052 {
1053         BLI_assert(edge_loop->e == edge);
1054         (void)edge; /* quiet warning in release build */
1055         *r_v1 = edge_loop->v;
1056         *r_v2 = edge_loop->next->v;
1057 }
1058
1059 void BM_edge_ordered_verts(BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
1060 {
1061         BM_edge_ordered_verts_ex(edge, r_v1, r_v2, edge->l);
1062 }
1063
1064 /**
1065  * Check if the loop is convex or concave
1066  * (depends on face normal)
1067  */
1068 bool BM_loop_is_convex(BMLoop *l)
1069 {
1070         float e_dir_prev[3];
1071         float e_dir_next[3];
1072         float l_no[3];
1073
1074         sub_v3_v3v3(e_dir_prev, l->prev->v->co, l->v->co);
1075         sub_v3_v3v3(e_dir_next, l->next->v->co, l->v->co);
1076         cross_v3_v3v3(l_no, e_dir_next, e_dir_prev);
1077         return dot_v3v3(l_no, l->f->no) > 0.0f;
1078 }
1079
1080 /**
1081  * Calculates the angle between the previous and next loops
1082  * (angle at this loops face corner).
1083  *
1084  * \return angle in radians
1085  */
1086 float BM_loop_calc_face_angle(BMLoop *l)
1087 {
1088         return angle_v3v3v3(l->prev->v->co,
1089                             l->v->co,
1090                             l->next->v->co);
1091 }
1092
1093 /**
1094  * \brief BM_loop_calc_face_normal
1095  *
1096  * Calculate the normal at this loop corner or fallback to the face normal on straight lines.
1097  *
1098  * \param l The loop to calculate the normal at
1099  * \param r_normal Resulting normal
1100  */
1101 void BM_loop_calc_face_normal(BMLoop *l, float r_normal[3])
1102 {
1103         if (normal_tri_v3(r_normal,
1104                           l->prev->v->co,
1105                           l->v->co,
1106                           l->next->v->co) != 0.0f)
1107         {
1108                 /* pass */
1109         }
1110         else {
1111                 copy_v3_v3(r_normal, l->f->no);
1112         }
1113 }
1114
1115 /**
1116  * \brief BM_loop_calc_face_direction
1117  *
1118  * Calculate the direction a loop is pointing.
1119  *
1120  * \param l The loop to calculate the direction at
1121  * \param r_dir Resulting direction
1122  */
1123 void BM_loop_calc_face_direction(BMLoop *l, float r_dir[3])
1124 {
1125         float v_prev[3];
1126         float v_next[3];
1127
1128         sub_v3_v3v3(v_prev, l->v->co, l->prev->v->co);
1129         sub_v3_v3v3(v_next, l->next->v->co, l->v->co);
1130
1131         normalize_v3(v_prev);
1132         normalize_v3(v_next);
1133
1134         add_v3_v3v3(r_dir, v_prev, v_next);
1135         normalize_v3(r_dir);
1136 }
1137
1138 /**
1139  * \brief BM_loop_calc_face_tangent
1140  *
1141  * Calculate the tangent at this loop corner or fallback to the face normal on straight lines.
1142  * This vector always points inward into the face.
1143  *
1144  * \param l The loop to calculate the tangent at
1145  * \param r_tangent Resulting tangent
1146  */
1147 void BM_loop_calc_face_tangent(BMLoop *l, float r_tangent[3])
1148 {
1149         float v_prev[3];
1150         float v_next[3];
1151         float dir[3];
1152
1153         sub_v3_v3v3(v_prev, l->prev->v->co, l->v->co);
1154         sub_v3_v3v3(v_next, l->v->co, l->next->v->co);
1155
1156         normalize_v3(v_prev);
1157         normalize_v3(v_next);
1158         add_v3_v3v3(dir, v_prev, v_next);
1159
1160         if (compare_v3v3(v_prev, v_next, FLT_EPSILON * 10.0f) == false) {
1161                 float nor[3]; /* for this purpose doesn't need to be normalized */
1162                 cross_v3_v3v3(nor, v_prev, v_next);
1163                 /* concave face check */
1164                 if (UNLIKELY(dot_v3v3(nor, l->f->no) < 0.0f)) {
1165                         negate_v3(nor);
1166                 }
1167                 cross_v3_v3v3(r_tangent, dir, nor);
1168         }
1169         else {
1170                 /* prev/next are the same - compare with face normal since we don't have one */
1171                 cross_v3_v3v3(r_tangent, dir, l->f->no);
1172         }
1173
1174         normalize_v3(r_tangent);
1175 }
1176
1177 /**
1178  * \brief BMESH EDGE/FACE ANGLE
1179  *
1180  *  Calculates the angle between two faces.
1181  *  Assumes the face normals are correct.
1182  *
1183  * \return angle in radians
1184  */
1185 float BM_edge_calc_face_angle(BMEdge *e)
1186 {
1187         if (BM_edge_is_manifold(e)) {
1188                 BMLoop *l1 = e->l;
1189                 BMLoop *l2 = e->l->radial_next;
1190                 return angle_normalized_v3v3(l1->f->no, l2->f->no);
1191         }
1192         else {
1193                 return DEG2RADF(90.0f);
1194         }
1195 }
1196
1197 /**
1198  * \brief BMESH EDGE/FACE ANGLE
1199  *
1200  *  Calculates the angle between two faces.
1201  *  Assumes the face normals are correct.
1202  *
1203  * \return angle in radians
1204  */
1205 float BM_edge_calc_face_angle_signed(BMEdge *e)
1206 {
1207         if (BM_edge_is_manifold(e)) {
1208                 BMLoop *l1 = e->l;
1209                 BMLoop *l2 = e->l->radial_next;
1210                 const float angle = angle_normalized_v3v3(l1->f->no, l2->f->no);
1211                 return BM_edge_is_convex(e) ? angle : -angle;
1212         }
1213         else {
1214                 return DEG2RADF(90.0f);
1215         }
1216 }
1217
1218 /**
1219  * \brief BMESH EDGE/FACE TANGENT
1220  *
1221  * Calculate the tangent at this loop corner or fallback to the face normal on straight lines.
1222  * This vector always points inward into the face.
1223  *
1224  * \brief BM_edge_calc_face_tangent
1225  * \param e
1226  * \param e_loop The loop to calculate the tangent at,
1227  * used to get the face and winding direction.
1228  * \param r_tangent The loop corner tangent to set
1229  */
1230
1231 void BM_edge_calc_face_tangent(BMEdge *e, BMLoop *e_loop, float r_tangent[3])
1232 {
1233         float tvec[3];
1234         BMVert *v1, *v2;
1235         BM_edge_ordered_verts_ex(e, &v1, &v2, e_loop);
1236
1237         sub_v3_v3v3(tvec, v1->co, v2->co); /* use for temp storage */
1238         /* note, we could average the tangents of both loops,
1239          * for non flat ngons it will give a better direction */
1240         cross_v3_v3v3(r_tangent, tvec, e_loop->f->no);
1241         normalize_v3(r_tangent);
1242 }
1243
1244 /**
1245  * \brief BMESH VERT/EDGE ANGLE
1246  *
1247  * Calculates the angle a verts 2 edges.
1248  *
1249  * \returns the angle in radians
1250  */
1251 float BM_vert_calc_edge_angle(BMVert *v)
1252 {
1253         BMEdge *e1, *e2;
1254
1255         /* saves BM_vert_edge_count(v) and and edge iterator,
1256          * get the edges and count them both at once */
1257
1258         if ((e1 = v->e) &&
1259             (e2 =  bmesh_disk_edge_next(e1, v)) &&
1260             /* make sure we come full circle and only have 2 connected edges */
1261             (e1 == bmesh_disk_edge_next(e2, v)))
1262         {
1263                 BMVert *v1 = BM_edge_other_vert(e1, v);
1264                 BMVert *v2 = BM_edge_other_vert(e2, v);
1265
1266                 return (float)M_PI - angle_v3v3v3(v1->co, v->co, v2->co);
1267         }
1268         else {
1269                 return DEG2RADF(90.0f);
1270         }
1271 }
1272
1273 /**
1274  * \note this isn't optimal to run on an array of verts,
1275  * see 'solidify_add_thickness' for a function which runs on an array.
1276  */
1277 float BM_vert_calc_shell_factor(BMVert *v)
1278 {
1279         BMIter iter;
1280         BMLoop *l;
1281         float accum_shell = 0.0f;
1282         float accum_angle = 0.0f;
1283
1284         BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
1285                 const float face_angle = BM_loop_calc_face_angle(l);
1286                 accum_shell += shell_angle_to_dist(angle_normalized_v3v3(v->no, l->f->no)) * face_angle;
1287                 accum_angle += face_angle;
1288         }
1289
1290         if (accum_angle != 0.0f) {
1291                 return accum_shell / accum_angle;
1292         }
1293         else {
1294                 return 1.0f;
1295         }
1296 }
1297 /* alternate version of #BM_vert_calc_shell_factor which only
1298  * uses 'hflag' faces, but falls back to all if none found. */
1299 float BM_vert_calc_shell_factor_ex(BMVert *v, const char hflag)
1300 {
1301         BMIter iter;
1302         BMLoop *l;
1303         float accum_shell = 0.0f;
1304         float accum_angle = 0.0f;
1305         int tot_sel = 0, tot = 0;
1306
1307         BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
1308                 if (BM_elem_flag_test(l->f, hflag)) {  /* <-- main difference to BM_vert_calc_shell_factor! */
1309                         const float face_angle = BM_loop_calc_face_angle(l);
1310                         accum_shell += shell_angle_to_dist(angle_normalized_v3v3(v->no, l->f->no)) * face_angle;
1311                         accum_angle += face_angle;
1312                         tot_sel++;
1313                 }
1314                 tot++;
1315         }
1316
1317         if (accum_angle != 0.0f) {
1318                 return accum_shell / accum_angle;
1319         }
1320         else {
1321                 /* other main difference from BM_vert_calc_shell_factor! */
1322                 if (tot != 0 && tot_sel == 0) {
1323                         /* none selected, so use all */
1324                         return BM_vert_calc_shell_factor(v);
1325                 }
1326                 else {
1327                         return 1.0f;
1328                 }
1329         }
1330 }
1331
1332 /**
1333  * \note quite an obscure function.
1334  * used in bmesh operators that have a relative scale options,
1335  */
1336 float BM_vert_calc_mean_tagged_edge_length(BMVert *v)
1337 {
1338         BMIter iter;
1339         BMEdge *e;
1340         int tot;
1341         float length = 0.0f;
1342
1343         BM_ITER_ELEM_INDEX (e, &iter, v, BM_EDGES_OF_VERT, tot) {
1344                 BMVert *v_other = BM_edge_other_vert(e, v);
1345                 if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
1346                         length += BM_edge_calc_length(e);
1347                 }
1348         }
1349
1350         if (tot) {
1351                 return length / (float)tot;
1352         }
1353         else {
1354                 return 0.0f;
1355         }
1356 }
1357
1358
1359 /**
1360  * Returns the loop of the shortest edge in f.
1361  */
1362 BMLoop *BM_face_find_shortest_loop(BMFace *f)
1363 {
1364         BMLoop *shortest_loop = NULL;
1365         float shortest_len = FLT_MAX;
1366
1367         BMLoop *l_iter;
1368         BMLoop *l_first;
1369
1370         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1371
1372         do {
1373                 const float len = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1374                 if (len <= shortest_len) {
1375                         shortest_loop = l_iter;
1376                         shortest_len = len;
1377                 }
1378         } while ((l_iter = l_iter->next) != l_first);
1379
1380         return shortest_loop;
1381 }
1382
1383 /**
1384  * Returns the loop of the longest edge in f.
1385  */
1386 BMLoop *BM_face_find_longest_loop(BMFace *f)
1387 {
1388         BMLoop *longest_loop = NULL;
1389         float longest_len = 0.0f;
1390
1391         BMLoop *l_iter;
1392         BMLoop *l_first;
1393
1394         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1395
1396         do {
1397                 const float len = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1398                 if (len >= longest_len) {
1399                         longest_loop = l_iter;
1400                         longest_len = len;
1401                 }
1402         } while ((l_iter = l_iter->next) != l_first);
1403
1404         return longest_loop;
1405 }
1406
1407 /**
1408  * Returns the edge existing between v1 and v2, or NULL if there isn't one.
1409  *
1410  * \note multiple edges may exist between any two vertices, and therefore
1411  * this function only returns the first one found.
1412  */
1413 BMEdge *BM_edge_exists(BMVert *v1, BMVert *v2)
1414 {
1415         BMIter iter;
1416         BMEdge *e;
1417
1418         BLI_assert(v1 != v2);
1419         BLI_assert(v1->head.htype == BM_VERT && v2->head.htype == BM_VERT);
1420
1421         BM_ITER_ELEM (e, &iter, v1, BM_EDGES_OF_VERT) {
1422                 if (e->v1 == v2 || e->v2 == v2)
1423                         return e;
1424         }
1425
1426         return NULL;
1427 }
1428
1429 /**
1430  * Returns an edge sharing the same vertices as this one.
1431  * This isn't an invalid state but tools should clean up these cases before
1432  * returning the mesh to the user.
1433  */
1434 BMEdge *BM_edge_find_double(BMEdge *e)
1435 {
1436         BMVert *v       = e->v1;
1437         BMVert *v_other = e->v2;
1438
1439         BMEdge *e_iter;
1440
1441         e_iter = e;
1442         while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e) {
1443                 if (UNLIKELY(BM_vert_in_edge(e_iter, v_other))) {
1444                         return e_iter;
1445                 }
1446         }
1447
1448         return NULL;
1449 }
1450
1451 /**
1452  * Given a set of vertices (varr), find out if
1453  * there is a face with exactly those vertices
1454  * (and only those vertices).
1455  *
1456  * \note there used to be a BM_face_exists_overlap function that checked for partial overlap,
1457  * however this is no longer used, simple to add back.
1458  */
1459 bool BM_face_exists(BMVert **varr, int len, BMFace **r_existface)
1460 {
1461         BMVert *v_search = varr[0];  /* we can search any of the verts in the array */
1462         BMIter viter;
1463         BMFace *f;
1464
1465
1466 #if 0
1467         BM_ITER_ELEM (f, &viter, v_search, BM_FACES_OF_VERT) {
1468                 if (f->len == len) {
1469                         if (BM_verts_in_face(f, varr, len)) {
1470                                 if (r_existface) {
1471                                         *r_existface = f;
1472                                 }
1473                                 return true;
1474                         }
1475                 }
1476         }
1477
1478         if (r_existface) {
1479                 *r_existface = NULL;
1480         }
1481         return false;
1482
1483 #else
1484
1485         /* faster to do the flagging once, and inline */
1486         bool is_init = false;
1487         bool is_found = false;
1488         int i;
1489
1490
1491         BM_ITER_ELEM (f, &viter, v_search, BM_FACES_OF_VERT) {
1492                 if (f->len == len) {
1493                         if (is_init == false) {
1494                                 is_init = true;
1495                                 for (i = 0; i < len; i++) {
1496                                         BLI_assert(!BM_ELEM_API_FLAG_TEST(varr[i], _FLAG_OVERLAP));
1497                                         BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
1498                                 }
1499                         }
1500
1501                         is_found = true;
1502
1503                         {
1504                                 BMLoop *l_iter;
1505                                 BMLoop *l_first;
1506
1507                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1508
1509                                 do {
1510                                         if (!BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
1511                                                 is_found = false;
1512                                                 break;
1513                                         }
1514                                 } while ((l_iter = l_iter->next) != l_first);
1515                         }
1516
1517                         if (is_found) {
1518                                 if (r_existface) {
1519                                         *r_existface = f;
1520                                 }
1521                                 break;
1522                         }
1523                 }
1524         }
1525
1526         if (is_found == false) {
1527                 if (r_existface) {
1528                         *r_existface = NULL;
1529                 }
1530         }
1531
1532         if (is_init == true) {
1533                 for (i = 0; i < len; i++) {
1534                         BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
1535                 }
1536         }
1537
1538         return is_found;
1539 #endif
1540 }
1541
1542
1543 /**
1544  * Given a set of vertices and edges (\a varr, \a earr), find out if
1545  * all those vertices are filled in by existing faces that _only_ use those vertices.
1546  *
1547  * This is for use in cases where creating a face is possible but would result in
1548  * many overlapping faces.
1549  *
1550  * An example of how this is used: when 2 tri's are selected that share an edge,
1551  * pressing Fkey would make a new overlapping quad (without a check like this)
1552  *
1553  * \a earr and \a varr can be in any order, however they _must_ form a closed loop.
1554  */
1555 bool BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len)
1556 {
1557         BMFace *f;
1558         BMEdge *e;
1559         BMVert *v;
1560         bool ok;
1561         int tot_tag;
1562
1563         BMIter fiter;
1564         BMIter viter;
1565
1566         int i;
1567
1568         for (i = 0; i < len; i++) {
1569                 /* save some time by looping over edge faces rather then vert faces
1570                  * will still loop over some faces twice but not as many */
1571                 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
1572                         BM_elem_flag_disable(f, BM_ELEM_INTERNAL_TAG);
1573                         BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
1574                                 BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
1575                         }
1576                 }
1577
1578                 /* clear all edge tags */
1579                 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
1580                         BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
1581                 }
1582         }
1583
1584         /* now tag all verts and edges in the boundary array as true so
1585          * we can know if a face-vert is from our array */
1586         for (i = 0; i < len; i++) {
1587                 BM_elem_flag_enable(varr[i], BM_ELEM_INTERNAL_TAG);
1588                 BM_elem_flag_enable(earr[i], BM_ELEM_INTERNAL_TAG);
1589         }
1590
1591
1592         /* so! boundary is tagged, everything else cleared */
1593
1594
1595         /* 1) tag all faces connected to edges - if all their verts are boundary */
1596         tot_tag = 0;
1597         for (i = 0; i < len; i++) {
1598                 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
1599                         if (!BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
1600                                 ok = true;
1601                                 BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
1602                                         if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) {
1603                                                 ok = false;
1604                                                 break;
1605                                         }
1606                                 }
1607
1608                                 if (ok) {
1609                                         /* we only use boundary verts */
1610                                         BM_elem_flag_enable(f, BM_ELEM_INTERNAL_TAG);
1611                                         tot_tag++;
1612                                 }
1613                         }
1614                         else {
1615                                 /* we already found! */
1616                         }
1617                 }
1618         }
1619
1620         if (tot_tag == 0) {
1621                 /* no faces use only boundary verts, quit early */
1622                 return false;
1623         }
1624
1625         /* 2) loop over non-boundary edges that use boundary verts,
1626          *    check each have 2 tagges faces connected (faces that only use 'varr' verts) */
1627         ok = true;
1628         for (i = 0; i < len; i++) {
1629                 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
1630
1631                         if (/* non-boundary edge */
1632                             BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == false &&
1633                             /* ...using boundary verts */
1634                             BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) == true &&
1635                             BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG) == true)
1636                         {
1637                                 int tot_face_tag = 0;
1638                                 BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
1639                                         if (BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
1640                                                 tot_face_tag++;
1641                                         }
1642                                 }
1643
1644                                 if (tot_face_tag != 2) {
1645                                         ok = false;
1646                                         break;
1647                                 }
1648
1649                         }
1650                 }
1651
1652                 if (ok == false) {
1653                         break;
1654                 }
1655         }
1656
1657         return ok;
1658 }
1659
1660 /* same as 'BM_face_exists_multi' but built vert array from edges */
1661 bool BM_face_exists_multi_edge(BMEdge **earr, int len)
1662 {
1663         BMVert **varr = BLI_array_alloca(varr, len);
1664
1665         bool ok;
1666         int i, i_next;
1667
1668         /* first check if verts have edges, if not we can bail out early */
1669         ok = true;
1670         for (i = len - 1, i_next = 0; i_next < len; (i = i_next++)) {
1671                 if (!(varr[i] = BM_edge_share_vert(earr[i], earr[i_next]))) {
1672                         ok = false;
1673                         break;
1674                 }
1675         }
1676
1677         if (ok == false) {
1678                 BMESH_ASSERT(0);
1679                 return false;
1680         }
1681
1682         ok = BM_face_exists_multi(varr, earr, len);
1683
1684         return ok;
1685 }
1686
1687 /* convenience functions for checking flags */
1688 bool BM_edge_is_any_vert_flag_test(BMEdge *e, const char hflag)
1689 {
1690         return (BM_elem_flag_test(e->v1, hflag) ||
1691                 BM_elem_flag_test(e->v2, hflag));
1692 }
1693
1694 bool BM_face_is_any_vert_flag_test(BMFace *f, const char hflag)
1695 {
1696         BMLoop *l_iter;
1697         BMLoop *l_first;
1698
1699         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1700         do {
1701                 if (BM_elem_flag_test(l_iter->v, hflag)) {
1702                         return true;
1703                 }
1704         } while ((l_iter = l_iter->next) != l_first);
1705         return false;
1706 }
1707
1708 bool BM_face_is_any_edge_flag_test(BMFace *f, const char hflag)
1709 {
1710         BMLoop *l_iter;
1711         BMLoop *l_first;
1712
1713         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1714         do {
1715                 if (BM_elem_flag_test(l_iter->e, hflag)) {
1716                         return true;
1717                 }
1718         } while ((l_iter = l_iter->next) != l_first);
1719         return false;
1720 }
1721
1722 static void bm_mesh_calc_volume_face(BMFace *f, float *r_vol)
1723 {
1724         int tottri = f->len - 2;
1725         BMLoop **loops     = BLI_array_alloca(loops, f->len);
1726         int    (*index)[3] = BLI_array_alloca(index, tottri);
1727         int j;
1728
1729         tottri = BM_face_calc_tessellation(f, loops, index);
1730         BLI_assert(tottri <= f->len - 2);
1731
1732         for (j = 0; j < tottri; j++) {
1733                 const float *p1 = loops[index[j][0]]->v->co;
1734                 const float *p2 = loops[index[j][1]]->v->co;
1735                 const float *p3 = loops[index[j][2]]->v->co;
1736
1737                 /* co1.dot(co2.cross(co3)) / 6.0 */
1738                 float cross[3];
1739                 cross_v3_v3v3(cross, p2, p3);
1740                 *r_vol += (1.0f / 6.0f) * dot_v3v3(p1, cross);
1741         }
1742 }
1743 float BM_mesh_calc_volume(BMesh *bm, bool is_signed)
1744 {
1745         /* warning, calls own tessellation function, may be slow */
1746         float vol = 0.0f;
1747         BMFace *f;
1748         BMIter fiter;
1749
1750         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
1751                 bm_mesh_calc_volume_face(f, &vol);
1752         }
1753
1754         if (is_signed == false) {
1755                 vol = fabsf(vol);
1756         }
1757
1758         return vol;
1759 }
1760
1761 /* note, almost duplicate of BM_mesh_calc_edge_groups, keep in sync */
1762 /**
1763  * Calculate isolated groups of faces with optional filtering.
1764  *
1765  * \param bm  the BMesh.
1766  * \param r_groups_array  Array of ints to fill in, length of bm->totface
1767  *        (or when hflag_test is set, the number of flagged faces).
1768  * \param r_group_index  index, length pairs into \a r_groups_array, size of return value
1769  *        int pairs: (array_start, array_length).
1770  * \param filter_fn  Filter the edges or verts we step over (depends on \a htype_step)
1771  *        as to which types we deal with.
1772  * \param user_data  Optional user data for \a filter_fn, can be NULL.
1773  * \param hflag_test  Optional flag to test faces,
1774  *        use to exclude faces from the calculation, 0 for all faces.
1775  * \param htype_step  BM_VERT to walk over face-verts, BM_EDGE to walk over faces edges
1776  *        (having both set is supported too).
1777  * \return The number of groups found.
1778  */
1779 int BM_mesh_calc_face_groups(BMesh *bm, int *r_groups_array, int (**r_group_index)[2],
1780                              BMElemFilterFunc filter_fn, void *user_data,
1781                              const char hflag_test, const char htype_step)
1782 {
1783 #ifdef DEBUG
1784         int group_index_len = 1;
1785 #else
1786         int group_index_len = 32;
1787 #endif
1788
1789         int (*group_index)[2] = MEM_mallocN(sizeof(*group_index) * group_index_len, __func__);
1790
1791         int *group_array = r_groups_array;
1792         STACK_DECLARE(group_array);
1793
1794         int group_curr = 0;
1795
1796         unsigned int tot_faces = 0;
1797         unsigned int tot_touch = 0;
1798
1799         BMFace **stack;
1800         STACK_DECLARE(stack);
1801
1802         BMIter iter;
1803         BMFace *f;
1804         int i;
1805
1806         STACK_INIT(group_array);
1807
1808         BLI_assert(((htype_step & ~(BM_VERT | BM_EDGE)) == 0) && (htype_step != 0));
1809
1810         /* init the array */
1811         BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
1812                 if ((hflag_test == 0) || BM_elem_flag_test(f, hflag_test)) {
1813                         tot_faces++;
1814                         BM_elem_flag_disable(f, BM_ELEM_TAG);
1815                 }
1816                 else {
1817                         /* never walk over tagged */
1818                         BM_elem_flag_enable(f, BM_ELEM_TAG);
1819                 }
1820
1821                 BM_elem_index_set(f, i); /* set_inline */
1822         }
1823         bm->elem_index_dirty &= ~BM_FACE;
1824
1825         /* detect groups */
1826         stack = MEM_mallocN(sizeof(*stack) * tot_faces, __func__);
1827
1828         while (tot_touch != tot_faces) {
1829                 int *group_item;
1830                 bool ok = false;
1831
1832                 BLI_assert(tot_touch < tot_faces);
1833
1834                 STACK_INIT(stack);
1835
1836                 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
1837                         if (BM_elem_flag_test(f, BM_ELEM_TAG) == false) {
1838                                 BM_elem_flag_enable(f, BM_ELEM_TAG);
1839                                 STACK_PUSH(stack, f);
1840                                 ok = true;
1841                                 break;
1842                         }
1843                 }
1844
1845                 BLI_assert(ok == true);
1846
1847                 /* manage arrays */
1848                 if (group_index_len == group_curr) {
1849                         group_index_len *= 2;
1850                         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_index_len);
1851                 }
1852
1853                 group_item = group_index[group_curr];
1854                 group_item[0] = STACK_SIZE(group_array);
1855                 group_item[1] = 0;
1856
1857                 while ((f = STACK_POP(stack))) {
1858                         BMLoop *l_iter, *l_first;
1859
1860                         /* add face */
1861                         STACK_PUSH(group_array, BM_elem_index_get(f));
1862                         tot_touch++;
1863                         group_item[1]++;
1864                         /* done */
1865
1866                         if (htype_step & BM_EDGE) {
1867                                 /* search for other faces */
1868                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1869                                 do {
1870                                         BMLoop *l_radial_iter = l_iter->radial_next;
1871                                         if ((l_radial_iter != l_iter) &&
1872                                             ((filter_fn == NULL) || filter_fn((BMElem *)l_iter->e, user_data)))
1873                                         {
1874                                                 do {
1875                                                         BMFace *f_other = l_radial_iter->f;
1876                                                         if (BM_elem_flag_test(f_other, BM_ELEM_TAG) == false) {
1877                                                                 BM_elem_flag_enable(f_other, BM_ELEM_TAG);
1878                                                                 STACK_PUSH(stack, f_other);
1879                                                         }
1880                                                 } while ((l_radial_iter = l_radial_iter->radial_next) != l_iter);
1881                                         }
1882                                 } while ((l_iter = l_iter->next) != l_first);
1883                         }
1884
1885                         if (htype_step & BM_VERT) {
1886                                 BMIter liter;
1887                                 /* search for other faces */
1888                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1889                                 do {
1890                                         if ((filter_fn == NULL) || filter_fn((BMElem *)l_iter->v, user_data)) {
1891                                                 BMLoop *l_other;
1892                                                 BM_ITER_ELEM (l_other, &liter, l_iter, BM_LOOPS_OF_LOOP) {
1893                                                         BMFace *f_other = l_other->f;
1894                                                         if (BM_elem_flag_test(f_other, BM_ELEM_TAG) == false) {
1895                                                                 BM_elem_flag_enable(f_other, BM_ELEM_TAG);
1896                                                                 STACK_PUSH(stack, f_other);
1897                                                         }
1898                                                 }
1899                                         }
1900                                 } while ((l_iter = l_iter->next) != l_first);
1901                         }
1902                 }
1903
1904                 group_curr++;
1905         }
1906
1907         MEM_freeN(stack);
1908
1909         /* reduce alloc to required size */
1910         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_curr);
1911         *r_group_index = group_index;
1912
1913         return group_curr;
1914 }
1915
1916 /* note, almost duplicate of BM_mesh_calc_face_groups, keep in sync */
1917 /**
1918  * Calculate isolated groups of edges with optional filtering.
1919  *
1920  * \param bm  the BMesh.
1921  * \param r_groups_array  Array of ints to fill in, length of bm->totedge
1922  *        (or when hflag_test is set, the number of flagged edges).
1923  * \param r_group_index  index, length pairs into \a r_groups_array, size of return value
1924  *        int pairs: (array_start, array_length).
1925  * \param filter_fn  Filter the edges or verts we step over (depends on \a htype_step)
1926  *        as to which types we deal with.
1927  * \param user_data  Optional user data for \a filter_fn, can be NULL.
1928  * \param hflag_test  Optional flag to test edges,
1929  *        use to exclude edges from the calculation, 0 for all edges.
1930  * \return The number of groups found.
1931  *
1932  * \note Unlike #BM_mesh_calc_face_groups there is no 'htype_step' argument,
1933  *       since we always walk over verts.
1934  */
1935 int BM_mesh_calc_edge_groups(BMesh *bm, int *r_groups_array, int (**r_group_index)[2],
1936                              BMElemFilterFunc filter_fn, void *user_data,
1937                              const char hflag_test)
1938 {
1939 #ifdef DEBUG
1940         int group_index_len = 1;
1941 #else
1942         int group_index_len = 32;
1943 #endif
1944
1945         int (*group_index)[2] = MEM_mallocN(sizeof(*group_index) * group_index_len, __func__);
1946
1947         int *group_array = r_groups_array;
1948         STACK_DECLARE(group_array);
1949
1950         int group_curr = 0;
1951
1952         unsigned int tot_edges = 0;
1953         unsigned int tot_touch = 0;
1954
1955         BMEdge **stack;
1956         STACK_DECLARE(stack);
1957
1958         BMIter iter;
1959         BMEdge *e;
1960         int i;
1961
1962         STACK_INIT(group_array);
1963
1964         /* init the array */
1965         BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
1966                 if ((hflag_test == 0) || BM_elem_flag_test(e, hflag_test)) {
1967                         tot_edges++;
1968                         BM_elem_flag_disable(e, BM_ELEM_TAG);
1969                 }
1970                 else {
1971                         /* never walk over tagged */
1972                         BM_elem_flag_enable(e, BM_ELEM_TAG);
1973                 }
1974
1975                 BM_elem_index_set(e, i); /* set_inline */
1976         }
1977         bm->elem_index_dirty &= ~BM_FACE;
1978
1979         /* detect groups */
1980         stack = MEM_mallocN(sizeof(*stack) * tot_edges, __func__);
1981
1982         while (tot_touch != tot_edges) {
1983                 int *group_item;
1984                 bool ok = false;
1985
1986                 BLI_assert(tot_touch < tot_edges);
1987
1988                 STACK_INIT(stack);
1989
1990                 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
1991                         if (BM_elem_flag_test(e, BM_ELEM_TAG) == false) {
1992                                 BM_elem_flag_enable(e, BM_ELEM_TAG);
1993                                 STACK_PUSH(stack, e);
1994                                 ok = true;
1995                                 break;
1996                         }
1997                 }
1998
1999                 BLI_assert(ok == true);
2000
2001                 /* manage arrays */
2002                 if (group_index_len == group_curr) {
2003                         group_index_len *= 2;
2004                         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_index_len);
2005                 }
2006
2007                 group_item = group_index[group_curr];
2008                 group_item[0] = STACK_SIZE(group_array);
2009                 group_item[1] = 0;
2010
2011                 while ((e = STACK_POP(stack))) {
2012                         BMIter viter;
2013                         BMIter eiter;
2014                         BMVert *v;
2015
2016                         /* add edge */
2017                         STACK_PUSH(group_array, BM_elem_index_get(e));
2018                         tot_touch++;
2019                         group_item[1]++;
2020                         /* done */
2021
2022                         /* search for other edges */
2023                         BM_ITER_ELEM (v, &viter, e, BM_VERTS_OF_EDGE) {
2024                                 if ((filter_fn == NULL) || filter_fn((BMElem *)v, user_data)) {
2025                                         BMEdge *e_other;
2026                                         BM_ITER_ELEM (e_other, &eiter, v, BM_EDGES_OF_VERT) {
2027                                                 if (BM_elem_flag_test(e_other, BM_ELEM_TAG) == false) {
2028                                                         BM_elem_flag_enable(e_other, BM_ELEM_TAG);
2029                                                         STACK_PUSH(stack, e_other);
2030                                                 }
2031                                         }
2032                                 }
2033                         }
2034                 }
2035
2036                 group_curr++;
2037         }
2038
2039         MEM_freeN(stack);
2040
2041         /* reduce alloc to required size */
2042         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_curr);
2043         *r_group_index = group_index;
2044
2045         return group_curr;
2046 }
2047
2048 float bmesh_subd_falloff_calc(const int falloff, float val)
2049 {
2050         switch (falloff) {
2051                 case SUBD_FALLOFF_SMOOTH:
2052                         val = 3.0f * val * val - 2.0f * val * val * val;
2053                         break;
2054                 case SUBD_FALLOFF_SPHERE:
2055                         val = sqrtf(2.0f * val - val * val);
2056                         break;
2057                 case SUBD_FALLOFF_ROOT:
2058                         val = sqrtf(val);
2059                         break;
2060                 case SUBD_FALLOFF_SHARP:
2061                         val = val * val;
2062                         break;
2063                 case SUBD_FALLOFF_LIN:
2064                         break;
2065                 default:
2066                         BLI_assert(0);
2067                         break;
2068         }
2069
2070         return val;
2071 }