Merge remote-tracking branch 'origin/master' into blender2.8
[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 #include "BLI_linklist.h"
39 #include "BLI_stackdefines.h"
40
41 #include "BKE_customdata.h"
42
43 #include "bmesh.h"
44 #include "intern/bmesh_private.h"
45
46 /**
47  * \brief Other Loop in Face Sharing an Edge
48  *
49  * Finds the other loop that shares \a v with \a e loop in \a f.
50  * <pre>
51  *     +----------+
52  *     |          |
53  *     |    f     |
54  *     |          |
55  *     +----------+ <-- return the face loop of this vertex.
56  *     v --> e
57  *     ^     ^ <------- These vert args define direction
58  *                      in the face to check.
59  *                      The faces loop direction is ignored.
60  * </pre>
61  *
62  * \note caller must ensure \a e is used in \a f
63  */
64 BMLoop *BM_face_other_edge_loop(BMFace *f, BMEdge *e, BMVert *v)
65 {
66         BMLoop *l = BM_face_edge_share_loop(f, e);
67         BLI_assert(l != NULL);
68         return BM_loop_other_edge_loop(l, v);
69 }
70
71 /**
72  * See #BM_face_other_edge_loop This is the same functionality
73  * to be used when the edges loop is already known.
74  */
75 BMLoop *BM_loop_other_edge_loop(BMLoop *l, BMVert *v)
76 {
77         BLI_assert(BM_vert_in_edge(l->e, v));
78         return l->v == v ? l->prev : l->next;
79 }
80
81 /**
82  * \brief Other Loop in Face Sharing a Vertex
83  *
84  * Finds the other loop in a face.
85  *
86  * This function returns a loop in \a f that shares an edge with \a v
87  * The direction is defined by \a v_prev, where the return value is
88  * the loop of what would be 'v_next'
89  * <pre>
90  *     +----------+ <-- return the face loop of this vertex.
91  *     |          |
92  *     |    f     |
93  *     |          |
94  *     +----------+
95  *     v_prev --> v
96  *     ^^^^^^     ^ <-- These vert args define direction
97  *                      in the face to check.
98  *                      The faces loop direction is ignored.
99  * </pre>
100  *
101  * \note \a v_prev and \a v _implicitly_ define an edge.
102  */
103 BMLoop *BM_face_other_vert_loop(BMFace *f, BMVert *v_prev, BMVert *v)
104 {
105         BMIter liter;
106         BMLoop *l_iter;
107
108         BLI_assert(BM_edge_exists(v_prev, v) != NULL);
109
110         BM_ITER_ELEM (l_iter, &liter, v, BM_LOOPS_OF_VERT) {
111                 if (l_iter->f == f) {
112                         break;
113                 }
114         }
115
116         if (l_iter) {
117                 if (l_iter->prev->v == v_prev) {
118                         return l_iter->next;
119                 }
120                 else if (l_iter->next->v == v_prev) {
121                         return l_iter->prev;
122                 }
123                 else {
124                         /* invalid args */
125                         BLI_assert(0);
126                         return NULL;
127                 }
128         }
129         else {
130                 /* invalid args */
131                 BLI_assert(0);
132                 return NULL;
133         }
134 }
135
136 /**
137  * \brief Other Loop in Face Sharing a Vert
138  *
139  * Finds the other loop that shares \a v with \a e loop in \a f.
140  * <pre>
141  *     +----------+ <-- return the face loop of this vertex.
142  *     |          |
143  *     |          |
144  *     |          |
145  *     +----------+ <-- This vertex defines the direction.
146  *           l    v
147  *           ^ <------- This loop defines both the face to search
148  *                      and the edge, in combination with 'v'
149  *                      The faces loop direction is ignored.
150  * </pre>
151  */
152
153 BMLoop *BM_loop_other_vert_loop(BMLoop *l, BMVert *v)
154 {
155 #if 0 /* works but slow */
156         return BM_face_other_vert_loop(l->f, BM_edge_other_vert(l->e, v), v);
157 #else
158         BMEdge *e = l->e;
159         BMVert *v_prev = BM_edge_other_vert(e, v);
160         if (l->v == v) {
161                 if (l->prev->v == v_prev) {
162                         return l->next;
163                 }
164                 else {
165                         BLI_assert(l->next->v == v_prev);
166
167                         return l->prev;
168                 }
169         }
170         else {
171                 BLI_assert(l->v == v_prev);
172
173                 if (l->prev->v == v) {
174                         return l->prev->prev;
175                 }
176                 else {
177                         BLI_assert(l->next->v == v);
178                         return l->next->next;
179                 }
180         }
181
182
183
184 #endif
185 }
186
187 /**
188  * Check if verts share a face.
189  */
190 bool BM_vert_pair_share_face_check(
191         BMVert *v_a, BMVert *v_b)
192 {
193         if (v_a->e && v_b->e) {
194                 BMIter iter;
195                 BMFace *f;
196
197                 BM_ITER_ELEM (f, &iter, v_a, BM_FACES_OF_VERT) {
198                         if (BM_vert_in_face(v_b, f)) {
199                                 return true;
200                         }
201                 }
202         }
203
204         return false;
205 }
206
207 bool BM_vert_pair_share_face_check_cb(
208         BMVert *v_a, BMVert *v_b,
209         bool (*test_fn)(BMFace *, void *user_data), void *user_data)
210 {
211         if (v_a->e && v_b->e) {
212                 BMIter iter;
213                 BMFace *f;
214
215                 BM_ITER_ELEM (f, &iter, v_a, BM_FACES_OF_VERT) {
216                         if (test_fn(f, user_data)) {
217                                 if (BM_vert_in_face(v_b, f)) {
218                                         return true;
219                                 }
220                         }
221                 }
222         }
223
224         return false;
225 }
226
227 /**
228  * Given 2 verts, find the smallest face they share and give back both loops.
229  */
230 BMFace *BM_vert_pair_share_face_by_len(
231         BMVert *v_a, BMVert *v_b,
232         BMLoop **r_l_a, BMLoop **r_l_b,
233         const bool allow_adjacent)
234 {
235         BMLoop *l_cur_a = NULL, *l_cur_b = NULL;
236         BMFace *f_cur = NULL;
237
238         if (v_a->e && v_b->e) {
239                 BMIter iter;
240                 BMLoop *l_a, *l_b;
241
242                 BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
243                         if ((f_cur == NULL) || (l_a->f->len < f_cur->len)) {
244                                 l_b = BM_face_vert_share_loop(l_a->f, v_b);
245                                 if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
246                                         f_cur = l_a->f;
247                                         l_cur_a = l_a;
248                                         l_cur_b = l_b;
249                                 }
250                         }
251                 }
252         }
253
254         *r_l_a = l_cur_a;
255         *r_l_b = l_cur_b;
256
257         return f_cur;
258 }
259
260 BMFace *BM_edge_pair_share_face_by_len(
261         BMEdge *e_a, BMEdge *e_b,
262         BMLoop **r_l_a, BMLoop **r_l_b,
263         const bool allow_adjacent)
264 {
265         BMLoop *l_cur_a = NULL, *l_cur_b = NULL;
266         BMFace *f_cur = NULL;
267
268         if (e_a->l && e_b->l) {
269                 BMIter iter;
270                 BMLoop *l_a, *l_b;
271
272                 BM_ITER_ELEM (l_a, &iter, e_a, BM_LOOPS_OF_EDGE) {
273                         if ((f_cur == NULL) || (l_a->f->len < f_cur->len)) {
274                                 l_b = BM_face_edge_share_loop(l_a->f, e_b);
275                                 if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
276                                         f_cur = l_a->f;
277                                         l_cur_a = l_a;
278                                         l_cur_b = l_b;
279                                 }
280                         }
281                 }
282         }
283
284         *r_l_a = l_cur_a;
285         *r_l_b = l_cur_b;
286
287         return f_cur;
288 }
289
290 static float bm_face_calc_split_dot(BMLoop *l_a, BMLoop *l_b)
291 {
292         float no[2][3];
293
294         if ((BM_face_calc_normal_subset(l_a, l_b, no[0]) != 0.0f) &&
295             (BM_face_calc_normal_subset(l_b, l_a, no[1]) != 0.0f))
296         {
297                 return dot_v3v3(no[0], no[1]);
298         }
299         else {
300                 return -1.0f;
301         }
302 }
303
304 /**
305  * Check if a point is inside the corner defined by a loop
306  * (within the 2 planes defined by the loops corner & face normal).
307  *
308  * \return signed, squared distance to the loops planes, less than 0.0 when outside.
309  */
310 float BM_loop_point_side_of_loop_test(const BMLoop *l, const float co[3])
311 {
312         const float *axis = l->f->no;
313         return dist_signed_squared_to_corner_v3v3v3(co, l->prev->v->co, l->v->co, l->next->v->co, axis);
314 }
315
316 /**
317  * Check if a point is inside the edge defined by a loop
318  * (within the plane defined by the loops edge & face normal).
319  *
320  * \return signed, squared distance to the edge plane, less than 0.0 when outside.
321  */
322 float BM_loop_point_side_of_edge_test(const BMLoop *l, const float co[3])
323 {
324         const float *axis = l->f->no;
325         float dir[3];
326         float plane[4];
327
328         sub_v3_v3v3(dir, l->next->v->co, l->v->co);
329         cross_v3_v3v3(plane, axis, dir);
330
331         plane[3] = -dot_v3v3(plane, l->v->co);
332         return dist_signed_squared_to_plane_v3(co, plane);
333 }
334
335 /**
336  * Given 2 verts, find a face they share that has the lowest angle across these verts and give back both loops.
337  *
338  * This can be better then #BM_vert_pair_share_face_by_len because concave splits are ranked lowest.
339  */
340 BMFace *BM_vert_pair_share_face_by_angle(
341         BMVert *v_a, BMVert *v_b,
342         BMLoop **r_l_a, BMLoop **r_l_b,
343         const bool allow_adjacent)
344 {
345         BMLoop *l_cur_a = NULL, *l_cur_b = NULL;
346         BMFace *f_cur = NULL;
347
348         if (v_a->e && v_b->e) {
349                 BMIter iter;
350                 BMLoop *l_a, *l_b;
351                 float dot_best = -1.0f;
352
353                 BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
354                         l_b = BM_face_vert_share_loop(l_a->f, v_b);
355                         if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
356
357                                 if (f_cur == NULL) {
358                                         f_cur = l_a->f;
359                                         l_cur_a = l_a;
360                                         l_cur_b = l_b;
361                                 }
362                                 else {
363                                         /* avoid expensive calculations if we only ever find one face */
364                                         float dot;
365                                         if (dot_best == -1.0f) {
366                                                 dot_best = bm_face_calc_split_dot(l_cur_a, l_cur_b);
367                                         }
368
369                                         dot = bm_face_calc_split_dot(l_a, l_b);
370                                         if (dot > dot_best) {
371                                                 dot_best = dot;
372
373                                                 f_cur = l_a->f;
374                                                 l_cur_a = l_a;
375                                                 l_cur_b = l_b;
376                                         }
377                                 }
378                         }
379                 }
380         }
381
382         *r_l_a = l_cur_a;
383         *r_l_b = l_cur_b;
384
385         return f_cur;
386 }
387
388
389 /**
390  * Get the first loop of a vert. Uses the same initialization code for the first loop of the
391  * iterator API
392  */
393 BMLoop *BM_vert_find_first_loop(BMVert *v)
394 {
395         BMEdge *e;
396
397         if (!v->e)
398                 return NULL;
399
400         e = bmesh_disk_faceedge_find_first(v->e, v);
401
402         if (!e)
403                 return NULL;
404
405         return bmesh_radial_faceloop_find_first(e->l, v);
406 }
407
408 /**
409  * Returns true if the vertex is used in a given face.
410  */
411 bool BM_vert_in_face(BMVert *v, BMFace *f)
412 {
413         BMLoop *l_iter, *l_first;
414
415 #ifdef USE_BMESH_HOLES
416         BMLoopList *lst;
417         for (lst = f->loops.first; lst; lst = lst->next)
418 #endif
419         {
420 #ifdef USE_BMESH_HOLES
421                 l_iter = l_first = lst->first;
422 #else
423                 l_iter = l_first = f->l_first;
424 #endif
425                 do {
426                         if (l_iter->v == v) {
427                                 return true;
428                         }
429                 } while ((l_iter = l_iter->next) != l_first);
430         }
431
432         return false;
433 }
434
435 /**
436  * Compares the number of vertices in an array
437  * that appear in a given face
438  */
439 int BM_verts_in_face_count(BMVert **varr, int len, BMFace *f)
440 {
441         BMLoop *l_iter, *l_first;
442
443 #ifdef USE_BMESH_HOLES
444         BMLoopList *lst;
445 #endif
446
447         int i, count = 0;
448         
449         for (i = 0; i < len; i++) {
450                 BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
451         }
452
453 #ifdef USE_BMESH_HOLES
454         for (lst = f->loops.first; lst; lst = lst->next)
455 #endif
456         {
457
458 #ifdef USE_BMESH_HOLES
459                 l_iter = l_first = lst->first;
460 #else
461                 l_iter = l_first = f->l_first;
462 #endif
463
464                 do {
465                         if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
466                                 count++;
467                         }
468
469                 } while ((l_iter = l_iter->next) != l_first);
470         }
471
472         for (i = 0; i < len; i++) {
473                 BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
474         }
475
476         return count;
477 }
478
479
480 /**
481  * Return true if all verts are in the face.
482  */
483 bool BM_verts_in_face(BMVert **varr, int len, BMFace *f)
484 {
485         BMLoop *l_iter, *l_first;
486
487 #ifdef USE_BMESH_HOLES
488         BMLoopList *lst;
489 #endif
490
491         int i;
492         bool ok = true;
493
494         /* simple check, we know can't succeed */
495         if (f->len < len) {
496                 return false;
497         }
498
499         for (i = 0; i < len; i++) {
500                 BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
501         }
502
503 #ifdef USE_BMESH_HOLES
504         for (lst = f->loops.first; lst; lst = lst->next)
505 #endif
506         {
507
508 #ifdef USE_BMESH_HOLES
509                 l_iter = l_first = lst->first;
510 #else
511                 l_iter = l_first = f->l_first;
512 #endif
513
514                 do {
515                         if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
516                                 /* pass */
517                         }
518                         else {
519                                 ok = false;
520                                 break;
521                         }
522
523                 } while ((l_iter = l_iter->next) != l_first);
524         }
525
526         for (i = 0; i < len; i++) {
527                 BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
528         }
529
530         return ok;
531 }
532
533 /**
534  * Returns whether or not a given edge is part of a given face.
535  */
536 bool BM_edge_in_face(const BMEdge *e, const BMFace *f)
537 {
538         if (e->l) {
539                 const BMLoop *l_iter, *l_first;
540
541                 l_iter = l_first = e->l;
542                 do {
543                         if (l_iter->f == f) {
544                                 return true;
545                         }
546                 } while ((l_iter = l_iter->radial_next) != l_first);
547         }
548
549         return false;
550 }
551
552 /**
553  * Given a edge and a loop (assumes the edge is manifold). returns
554  * the other faces loop, sharing the same vertex.
555  *
556  * <pre>
557  * +-------------------+
558  * |                   |
559  * |                   |
560  * |l_other <-- return |
561  * +-------------------+ <-- A manifold edge between 2 faces
562  * |l    e  <-- edge   |
563  * |^ <-------- loop   |
564  * |                   |
565  * +-------------------+
566  * </pre>
567  */
568 BMLoop *BM_edge_other_loop(BMEdge *e, BMLoop *l)
569 {
570         BMLoop *l_other;
571
572         // BLI_assert(BM_edge_is_manifold(e));  // TOO strict, just check if we have another radial face
573         BLI_assert(e->l && e->l->radial_next != e->l);
574         BLI_assert(BM_vert_in_edge(e, l->v));
575
576         l_other = (l->e == e) ? l : l->prev;
577         l_other = l_other->radial_next;
578         BLI_assert(l_other->e == e);
579
580         if (l_other->v == l->v) {
581                 /* pass */
582         }
583         else if (l_other->next->v == l->v) {
584                 l_other = l_other->next;
585         }
586         else {
587                 BLI_assert(0);
588         }
589
590         return l_other;
591 }
592
593 /**
594  * Utility function to step around a fan of loops,
595  * using an edge to mark the previous side.
596  *
597  * \note all edges must be manifold,
598  * once a non manifold edge is hit, return NULL.
599  *
600  * <pre>
601  *                ,.,-->|
602  *            _,-'      |
603  *          ,'          | (notice how 'e_step'
604  *         /            |  and 'l' define the
605  *        /             |  direction the arrow
606  *       |     return   |  points).
607  *       |     loop --> |
608  * ---------------------+---------------------
609  *         ^      l --> |
610  *         |            |
611  *  assign e_step       |
612  *                      |
613  *   begin e_step ----> |
614  *                      |
615  * </pre>
616  */
617
618 BMLoop *BM_vert_step_fan_loop(BMLoop *l, BMEdge **e_step)
619 {
620         BMEdge *e_prev = *e_step;
621         BMEdge *e_next;
622         if (l->e == e_prev) {
623                 e_next = l->prev->e;
624         }
625         else if (l->prev->e == e_prev) {
626                 e_next = l->e;
627         }
628         else {
629                 BLI_assert(0);
630                 return NULL;
631         }
632
633         if (BM_edge_is_manifold(e_next)) {
634                 return BM_edge_other_loop((*e_step = e_next), l);
635         }
636         else {
637                 return NULL;
638         }
639 }
640
641
642
643 /**
644  * The function takes a vertex at the center of a fan and returns the opposite edge in the fan.
645  * All edges in the fan must be manifold, otherwise return NULL.
646  *
647  * \note This could (probably) be done more efficiently.
648  */
649 BMEdge *BM_vert_other_disk_edge(BMVert *v, BMEdge *e_first)
650 {
651         BMLoop *l_a;
652         int tot = 0;
653         int i;
654
655         BLI_assert(BM_vert_in_edge(e_first, v));
656
657         l_a = e_first->l;
658         do {
659                 l_a = BM_loop_other_vert_loop(l_a, v);
660                 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
661                 if (BM_edge_is_manifold(l_a->e)) {
662                         l_a = l_a->radial_next;
663                 }
664                 else {
665                         return NULL;
666                 }
667
668                 tot++;
669         } while (l_a != e_first->l);
670
671         /* we know the total, now loop half way */
672         tot /= 2;
673         i = 0;
674
675         l_a = e_first->l;
676         do {
677                 if (i == tot) {
678                         l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
679                         return l_a->e;
680                 }
681
682                 l_a = BM_loop_other_vert_loop(l_a, v);
683                 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
684                 if (BM_edge_is_manifold(l_a->e)) {
685                         l_a = l_a->radial_next;
686                 }
687                 /* this wont have changed from the previous loop */
688
689
690                 i++;
691         } while (l_a != e_first->l);
692
693         return NULL;
694 }
695
696 /**
697  * Returns edge length
698  */
699 float BM_edge_calc_length(const BMEdge *e)
700 {
701         return len_v3v3(e->v1->co, e->v2->co);
702 }
703
704 /**
705  * Returns edge length squared (for comparisons)
706  */
707 float BM_edge_calc_length_squared(const BMEdge *e)
708 {
709         return len_squared_v3v3(e->v1->co, e->v2->co);
710 }
711
712 /**
713  * Utility function, since enough times we have an edge
714  * and want to access 2 connected faces.
715  *
716  * \return true when only 2 faces are found.
717  */
718 bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
719 {
720         BMLoop *la, *lb;
721
722         if ((la = e->l) &&
723             (lb = la->radial_next) &&
724             (la != lb) &&
725             (lb->radial_next == la))
726         {
727                 *r_fa = la->f;
728                 *r_fb = lb->f;
729                 return true;
730         }
731         else {
732                 *r_fa = NULL;
733                 *r_fb = NULL;
734                 return false;
735         }
736 }
737
738 /**
739  * Utility function, since enough times we have an edge
740  * and want to access 2 connected loops.
741  *
742  * \return true when only 2 faces are found.
743  */
744 bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
745 {
746         BMLoop *la, *lb;
747
748         if ((la = e->l) &&
749             (lb = la->radial_next) &&
750             (la != lb) &&
751             (lb->radial_next == la))
752         {
753                 *r_la = la;
754                 *r_lb = lb;
755                 return true;
756         }
757         else {
758                 *r_la = NULL;
759                 *r_lb = NULL;
760                 return false;
761         }
762 }
763
764 /**
765  * Fast alternative to ``(BM_vert_edge_count(v) == 2)``
766  */
767 bool BM_vert_is_edge_pair(const BMVert *v)
768 {
769         const BMEdge *e = v->e;
770         if (e) {
771                 BMEdge *e_other = BM_DISK_EDGE_NEXT(e, v);
772                 return ((e_other != e) && (BM_DISK_EDGE_NEXT(e_other, v) == e));
773         }
774         return false;
775 }
776
777 /**
778  * Access a verts 2 connected edges.
779  *
780  * \return true when only 2 verts are found.
781  */
782 bool BM_vert_edge_pair(BMVert *v, BMEdge **r_e_a, BMEdge **r_e_b)
783 {
784         BMEdge *e_a = v->e;
785         if (e_a) {
786                 BMEdge *e_b = BM_DISK_EDGE_NEXT(e_a, v);
787                 if ((e_b != e_a) && (BM_DISK_EDGE_NEXT(e_b, v) == e_a)) {
788                         *r_e_a = e_a;
789                         *r_e_b = e_b;
790                         return true;
791                 }
792         }
793
794         *r_e_a = NULL;
795         *r_e_b = NULL;
796         return false;
797 }
798
799 /**
800  *      Returns the number of edges around this vertex.
801  */
802 int BM_vert_edge_count(const BMVert *v)
803 {
804         return bmesh_disk_count(v);
805 }
806
807 int BM_vert_edge_count_ex(const BMVert *v, const int count_max)
808 {
809         return bmesh_disk_count_ex(v, count_max);
810 }
811
812 int BM_vert_edge_count_nonwire(const BMVert *v)
813 {
814         int count = 0;
815         BMIter eiter;
816         BMEdge *edge;
817         BM_ITER_ELEM (edge, &eiter, (BMVert *)v, BM_EDGES_OF_VERT) {
818                 if (edge->l) {
819                         count++;
820                 }
821         }
822         return count;
823 }
824 /**
825  *      Returns the number of faces around this edge
826  */
827 int BM_edge_face_count(const BMEdge *e)
828 {
829         int count = 0;
830
831         if (e->l) {
832                 BMLoop *l_iter, *l_first;
833
834                 l_iter = l_first = e->l;
835                 do {
836                         count++;
837                 } while ((l_iter = l_iter->radial_next) != l_first);
838         }
839
840         return count;
841 }
842
843 int BM_edge_face_count_ex(const BMEdge *e, const int count_max)
844 {
845         int count = 0;
846
847         if (e->l) {
848                 BMLoop *l_iter, *l_first;
849
850                 l_iter = l_first = e->l;
851                 do {
852                         count++;
853                         if (count == count_max) {
854                                 break;
855                         }
856                 } while ((l_iter = l_iter->radial_next) != l_first);
857         }
858
859         return count;
860 }
861
862 /**
863  * Returns the number of faces around this vert
864  * length matches #BM_LOOPS_OF_VERT iterator
865  */
866 int BM_vert_face_count(const BMVert *v)
867 {
868         return bmesh_disk_facevert_count(v);
869 }
870
871 int BM_vert_face_count_ex(const BMVert *v, int count_max)
872 {
873         return bmesh_disk_facevert_count_ex(v, count_max);
874 }
875
876 /**
877  * Return true if the vertex is connected to _any_ faces.
878  *
879  * same as ``BM_vert_face_count(v) != 0`` or ``BM_vert_find_first_loop(v) == NULL``
880  */
881 bool BM_vert_face_check(BMVert *v)
882 {
883         return v->e && (bmesh_disk_faceedge_find_first(v->e, v) != NULL);
884 }
885
886 /**
887  * Tests whether or not the vertex is part of a wire edge.
888  * (ie: has no faces attached to it)
889  */
890 bool BM_vert_is_wire(const BMVert *v)
891 {
892         if (v->e) {
893                 BMEdge *e_first, *e_iter;
894
895                 e_first = e_iter = v->e;
896                 do {
897                         if (e_iter->l) {
898                                 return false;
899                         }
900                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
901
902                 return true;
903         }
904         else {
905                 return false;
906         }
907 }
908
909 /**
910  * A vertex is non-manifold if it meets the following conditions:
911  * 1: Loose - (has no edges/faces incident upon it).
912  * 2: Joins two distinct regions - (two pyramids joined at the tip).
913  * 3: Is part of an edge with more than 2 faces.
914  * 4: Is part of a wire edge.
915  */
916 bool BM_vert_is_manifold(const BMVert *v)
917 {
918         BMEdge *e_iter, *e_first, *e_prev;
919         BMLoop *l_iter, *l_first;
920         int loop_num = 0, loop_num_region = 0, boundary_num = 0;
921
922         if (v->e == NULL) {
923                 /* loose vert */
924                 return false;
925         }
926
927         /* count edges while looking for non-manifold edges */
928         e_first = e_iter = v->e;
929         l_first = e_iter->l ? e_iter->l : NULL;
930         do {
931                 /* loose edge or edge shared by more than two faces,
932                  * edges with 1 face user are OK, otherwise we could
933                  * use BM_edge_is_manifold() here */
934                 if (e_iter->l == NULL || (e_iter->l != e_iter->l->radial_next->radial_next)) {
935                         return false;
936                 }
937
938                 /* count radial loops */
939                 if (e_iter->l->v == v) {
940                         loop_num += 1;
941                 }
942
943                 if (!BM_edge_is_boundary(e_iter)) {
944                         /* non boundary check opposite loop */
945                         if (e_iter->l->radial_next->v == v) {
946                                 loop_num += 1;
947                         }
948                 }
949                 else {
950                         /* start at the boundary */
951                         l_first = e_iter->l;
952                         boundary_num += 1;
953                         /* >2 boundaries cant be manifold */
954                         if (boundary_num == 3) {
955                                 return false;
956                         }
957                 }
958         } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
959
960         e_first = l_first->e;
961         l_first = (l_first->v == v) ? l_first : l_first->next;
962         BLI_assert(l_first->v == v);
963
964         l_iter = l_first;
965         e_prev = e_first;
966
967         do {
968                 loop_num_region += 1;
969         } while (((l_iter = BM_vert_step_fan_loop(l_iter, &e_prev)) != l_first) && (l_iter != NULL));
970
971         return (loop_num == loop_num_region);
972 }
973
974 #define LOOP_VISIT _FLAG_WALK
975 #define EDGE_VISIT _FLAG_WALK
976
977 static int bm_loop_region_count__recursive(BMEdge *e, BMVert *v)
978 {
979         BMLoop *l_iter, *l_first;
980         int count = 0;
981
982         BLI_assert(!BM_ELEM_API_FLAG_TEST(e, EDGE_VISIT));
983         BM_ELEM_API_FLAG_ENABLE(e, EDGE_VISIT);
984
985         l_iter = l_first = e->l;
986         do {
987                 if (l_iter->v == v) {
988                         BMEdge *e_other = l_iter->prev->e;
989                         if (!BM_ELEM_API_FLAG_TEST(l_iter, LOOP_VISIT)) {
990                                 BM_ELEM_API_FLAG_ENABLE(l_iter, LOOP_VISIT);
991                                 count += 1;
992                         }
993                         if (!BM_ELEM_API_FLAG_TEST(e_other, EDGE_VISIT)) {
994                                 count += bm_loop_region_count__recursive(e_other, v);
995                         }
996                 }
997                 else if (l_iter->next->v == v) {
998                         BMEdge *e_other = l_iter->next->e;
999                         if (!BM_ELEM_API_FLAG_TEST(l_iter->next, LOOP_VISIT)) {
1000                                 BM_ELEM_API_FLAG_ENABLE(l_iter->next, LOOP_VISIT);
1001                                 count += 1;
1002                         }
1003                         if (!BM_ELEM_API_FLAG_TEST(e_other, EDGE_VISIT)) {
1004                                 count += bm_loop_region_count__recursive(e_other, v);
1005                         }
1006                 }
1007                 else {
1008                         BLI_assert(0);
1009                 }
1010         } while ((l_iter = l_iter->radial_next) != l_first);
1011
1012         return count;
1013 }
1014
1015 static int bm_loop_region_count__clear(BMLoop *l)
1016 {
1017         int count = 0;
1018         BMEdge *e_iter, *e_first;
1019
1020         /* clear flags */
1021         e_iter = e_first = l->e;
1022         do {
1023                 BM_ELEM_API_FLAG_DISABLE(e_iter, EDGE_VISIT);
1024                 if (e_iter->l) {
1025                         BMLoop *l_iter, *l_first;
1026                         l_iter = l_first = e_iter->l;
1027                         do {
1028                                 if (l_iter->v == l->v) {
1029                                         BM_ELEM_API_FLAG_DISABLE(l_iter, LOOP_VISIT);
1030                                         count += 1;
1031                                 }
1032                         } while ((l_iter = l_iter->radial_next) != l_first);
1033                 }
1034         } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, l->v)) != e_first);
1035
1036         return count;
1037 }
1038
1039 /**
1040  * The number of loops connected to this loop (not including disconnected regions).
1041  */
1042 int BM_loop_region_loops_count_ex(BMLoop *l, int *r_loop_total)
1043 {
1044         const int count       = bm_loop_region_count__recursive(l->e, l->v);
1045         const int count_total = bm_loop_region_count__clear(l);
1046         if (r_loop_total) {
1047                 *r_loop_total = count_total;
1048         }
1049         return count;
1050 }
1051
1052 #undef LOOP_VISIT
1053 #undef EDGE_VISIT
1054
1055 int BM_loop_region_loops_count(BMLoop *l)
1056 {
1057         return BM_loop_region_loops_count_ex(l, NULL);
1058 }
1059
1060 /**
1061  * A version of #BM_vert_is_manifold
1062  * which only checks if we're connected to multiple isolated regions.
1063  */
1064 bool BM_vert_is_manifold_region(const BMVert *v)
1065 {
1066         BMLoop *l_first = BM_vert_find_first_loop((BMVert *)v);
1067         if (l_first) {
1068                 int count, count_total;
1069                 count = BM_loop_region_loops_count_ex(l_first, &count_total);
1070                 return (count == count_total);
1071         }
1072         return true;
1073 }
1074
1075 /**
1076  * Check if the edge is convex or concave
1077  * (depends on face winding)
1078  */
1079 bool BM_edge_is_convex(const BMEdge *e)
1080 {
1081         if (BM_edge_is_manifold(e)) {
1082                 BMLoop *l1 = e->l;
1083                 BMLoop *l2 = e->l->radial_next;
1084                 if (!equals_v3v3(l1->f->no, l2->f->no)) {
1085                         float cross[3];
1086                         float l_dir[3];
1087                         cross_v3_v3v3(cross, l1->f->no, l2->f->no);
1088                         /* we assume contiguous normals, otherwise the result isn't meaningful */
1089                         sub_v3_v3v3(l_dir, l1->next->v->co, l1->v->co);
1090                         return (dot_v3v3(l_dir, cross) > 0.0f);
1091                 }
1092         }
1093         return true;
1094 }
1095
1096 /**
1097  * \return true when loop customdata is contiguous.
1098  */
1099 bool BM_edge_is_contiguous_loop_cd(
1100         const BMEdge *e,
1101         const int cd_loop_type, const int cd_loop_offset)
1102 {
1103         BLI_assert(cd_loop_offset != -1);
1104
1105         if (e->l && e->l->radial_next != e->l) {
1106                 const BMLoop *l_base_v1 = e->l;
1107                 const BMLoop *l_base_v2 = e->l->next;
1108                 const void *l_base_cd_v1 = BM_ELEM_CD_GET_VOID_P(l_base_v1, cd_loop_offset);
1109                 const void *l_base_cd_v2 = BM_ELEM_CD_GET_VOID_P(l_base_v2, cd_loop_offset);
1110                 const BMLoop *l_iter = e->l->radial_next;
1111                 do {
1112                         const BMLoop *l_iter_v1;
1113                         const BMLoop *l_iter_v2;
1114                         const void *l_iter_cd_v1;
1115                         const void *l_iter_cd_v2;
1116
1117                         if (l_iter->v == l_base_v1->v) {
1118                                 l_iter_v1 = l_iter;
1119                                 l_iter_v2 = l_iter->next;
1120                         }
1121                         else {
1122                                 l_iter_v1 = l_iter->next;
1123                                 l_iter_v2 = l_iter;
1124                         }
1125                         BLI_assert((l_iter_v1->v == l_base_v1->v) &&
1126                                    (l_iter_v2->v == l_base_v2->v));
1127
1128                         l_iter_cd_v1 = BM_ELEM_CD_GET_VOID_P(l_iter_v1, cd_loop_offset);
1129                         l_iter_cd_v2 = BM_ELEM_CD_GET_VOID_P(l_iter_v2, cd_loop_offset);
1130
1131
1132                         if ((CustomData_data_equals(cd_loop_type, l_base_cd_v1, l_iter_cd_v1) == 0) ||
1133                             (CustomData_data_equals(cd_loop_type, l_base_cd_v2, l_iter_cd_v2) == 0))
1134                         {
1135                                 return false;
1136                         }
1137
1138                 } while ((l_iter = l_iter->radial_next) != e->l);
1139         }
1140         return true;
1141 }
1142
1143 bool BM_vert_is_boundary(const BMVert *v)
1144 {
1145         if (v->e) {
1146                 BMEdge *e_first, *e_iter;
1147
1148                 e_first = e_iter = v->e;
1149                 do {
1150                         if (BM_edge_is_boundary(e_iter)) {
1151                                 return true;
1152                         }
1153                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
1154
1155                 return false;
1156         }
1157         else {
1158                 return false;
1159         }
1160 }
1161
1162 /**
1163  * Returns the number of faces that are adjacent to both f1 and f2,
1164  * \note Could be sped up a bit by not using iterators and by tagging
1165  * faces on either side, then count the tags rather then searching.
1166  */
1167 int BM_face_share_face_count(BMFace *f1, BMFace *f2)
1168 {
1169         BMIter iter1, iter2;
1170         BMEdge *e;
1171         BMFace *f;
1172         int count = 0;
1173
1174         BM_ITER_ELEM (e, &iter1, f1, BM_EDGES_OF_FACE) {
1175                 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
1176                         if (f != f1 && f != f2 && BM_face_share_edge_check(f, f2))
1177                                 count++;
1178                 }
1179         }
1180
1181         return count;
1182 }
1183
1184 /**
1185  * same as #BM_face_share_face_count but returns a bool
1186  */
1187 bool BM_face_share_face_check(BMFace *f1, BMFace *f2)
1188 {
1189         BMIter iter1, iter2;
1190         BMEdge *e;
1191         BMFace *f;
1192
1193         BM_ITER_ELEM (e, &iter1, f1, BM_EDGES_OF_FACE) {
1194                 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
1195                         if (f != f1 && f != f2 && BM_face_share_edge_check(f, f2))
1196                                 return true;
1197                 }
1198         }
1199
1200         return false;
1201 }
1202
1203 /**
1204  *  Counts the number of edges two faces share (if any)
1205  */
1206 int BM_face_share_edge_count(BMFace *f_a, BMFace *f_b)
1207 {
1208         BMLoop *l_iter;
1209         BMLoop *l_first;
1210         int count = 0;
1211         
1212         l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
1213         do {
1214                 if (BM_edge_in_face(l_iter->e, f_b)) {
1215                         count++;
1216                 }
1217         } while ((l_iter = l_iter->next) != l_first);
1218
1219         return count;
1220 }
1221
1222 /**
1223  *  Returns true if the faces share an edge
1224  */
1225 bool BM_face_share_edge_check(BMFace *f1, BMFace *f2)
1226 {
1227         BMLoop *l_iter;
1228         BMLoop *l_first;
1229
1230         l_iter = l_first = BM_FACE_FIRST_LOOP(f1);
1231         do {
1232                 if (BM_edge_in_face(l_iter->e, f2)) {
1233                         return true;
1234                 }
1235         } while ((l_iter = l_iter->next) != l_first);
1236
1237         return false;
1238 }
1239
1240 /**
1241  *  Counts the number of verts two faces share (if any).
1242  */
1243 int BM_face_share_vert_count(BMFace *f_a, BMFace *f_b)
1244 {
1245         BMLoop *l_iter;
1246         BMLoop *l_first;
1247         int count = 0;
1248
1249         l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
1250         do {
1251                 if (BM_vert_in_face(l_iter->v, f_b)) {
1252                         count++;
1253                 }
1254         } while ((l_iter = l_iter->next) != l_first);
1255
1256         return count;
1257 }
1258
1259 /**
1260  *  Returns true if the faces share a vert.
1261  */
1262 bool BM_face_share_vert_check(BMFace *f_a, BMFace *f_b)
1263 {
1264         BMLoop *l_iter;
1265         BMLoop *l_first;
1266
1267         l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
1268         do {
1269                 if (BM_vert_in_face(l_iter->v, f_b)) {
1270                         return true;
1271                 }
1272         } while ((l_iter = l_iter->next) != l_first);
1273
1274         return false;
1275 }
1276
1277 /**
1278  * Returns true when 2 loops share an edge (are adjacent in the face-fan)
1279  */
1280 bool BM_loop_share_edge_check(BMLoop *l_a, BMLoop *l_b)
1281 {
1282         BLI_assert(l_a->v == l_b->v);
1283         return (ELEM(l_a->e, l_b->e, l_b->prev->e) ||
1284                 ELEM(l_b->e, l_a->e, l_a->prev->e));
1285 }
1286
1287 /**
1288  * Test if e1 shares any faces with e2
1289  */
1290 bool BM_edge_share_face_check(BMEdge *e1, BMEdge *e2)
1291 {
1292         BMLoop *l;
1293         BMFace *f;
1294
1295         if (e1->l && e2->l) {
1296                 l = e1->l;
1297                 do {
1298                         f = l->f;
1299                         if (BM_edge_in_face(e2, f)) {
1300                                 return true;
1301                         }
1302                         l = l->radial_next;
1303                 } while (l != e1->l);
1304         }
1305         return false;
1306 }
1307
1308 /**
1309  *      Test if e1 shares any quad faces with e2
1310  */
1311 bool BM_edge_share_quad_check(BMEdge *e1, BMEdge *e2)
1312 {
1313         BMLoop *l;
1314         BMFace *f;
1315
1316         if (e1->l && e2->l) {
1317                 l = e1->l;
1318                 do {
1319                         f = l->f;
1320                         if (f->len == 4) {
1321                                 if (BM_edge_in_face(e2, f)) {
1322                                         return true;
1323                                 }
1324                         }
1325                         l = l->radial_next;
1326                 } while (l != e1->l);
1327         }
1328         return false;
1329 }
1330
1331 /**
1332  *      Tests to see if e1 shares a vertex with e2
1333  */
1334 bool BM_edge_share_vert_check(BMEdge *e1, BMEdge *e2)
1335 {
1336         return (e1->v1 == e2->v1 ||
1337                 e1->v1 == e2->v2 ||
1338                 e1->v2 == e2->v1 ||
1339                 e1->v2 == e2->v2);
1340 }
1341
1342 /**
1343  *      Return the shared vertex between the two edges or NULL
1344  */
1345 BMVert *BM_edge_share_vert(BMEdge *e1, BMEdge *e2)
1346 {
1347         BLI_assert(e1 != e2);
1348         if (BM_vert_in_edge(e2, e1->v1)) {
1349                 return e1->v1;
1350         }
1351         else if (BM_vert_in_edge(e2, e1->v2)) {
1352                 return e1->v2;
1353         }
1354         else {
1355                 return NULL;
1356         }
1357 }
1358
1359 /**
1360  * \brief Return the Loop Shared by Edge and Vert
1361  *
1362  * Finds the loop used which uses \a  in face loop \a l
1363  *
1364  * \note this function takes a loop rather then an edge
1365  * so we can select the face that the loop should be from.
1366  */
1367 BMLoop *BM_edge_vert_share_loop(BMLoop *l, BMVert *v)
1368 {
1369         BLI_assert(BM_vert_in_edge(l->e, v));
1370         if (l->v == v) {
1371                 return l;
1372         }
1373         else {
1374                 return l->next;
1375         }
1376 }
1377
1378 /**
1379  * \brief Return the Loop Shared by Face and Vertex
1380  *
1381  * Finds the loop used which uses \a v in face loop \a l
1382  *
1383  * \note currently this just uses simple loop in future may be sped up
1384  * using radial vars
1385  */
1386 BMLoop *BM_face_vert_share_loop(BMFace *f, BMVert *v)
1387 {
1388         BMLoop *l_first;
1389         BMLoop *l_iter;
1390
1391         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1392         do {
1393                 if (l_iter->v == v) {
1394                         return l_iter;
1395                 }
1396         } while ((l_iter = l_iter->next) != l_first);
1397
1398         return NULL;
1399 }
1400
1401 /**
1402  * \brief Return the Loop Shared by Face and Edge
1403  *
1404  * Finds the loop used which uses \a e in face loop \a l
1405  *
1406  * \note currently this just uses simple loop in future may be sped up
1407  * using radial vars
1408  */
1409 BMLoop *BM_face_edge_share_loop(BMFace *f, BMEdge *e)
1410 {
1411         BMLoop *l_first;
1412         BMLoop *l_iter;
1413
1414         l_iter = l_first = e->l;
1415         do {
1416                 if (l_iter->f == f) {
1417                         return l_iter;
1418                 }
1419         } while ((l_iter = l_iter->radial_next) != l_first);
1420
1421         return NULL;
1422 }
1423
1424 /**
1425  * Returns the verts of an edge as used in a face
1426  * if used in a face at all, otherwise just assign as used in the edge.
1427  *
1428  * Useful to get a deterministic winding order when calling
1429  * BM_face_create_ngon() on an arbitrary array of verts,
1430  * though be sure to pick an edge which has a face.
1431  *
1432  * \note This is in fact quite a simple check, mainly include this function so the intent is more obvious.
1433  * We know these 2 verts will _always_ make up the loops edge
1434  */
1435 void BM_edge_ordered_verts_ex(
1436         const BMEdge *edge, BMVert **r_v1, BMVert **r_v2,
1437         const BMLoop *edge_loop)
1438 {
1439         BLI_assert(edge_loop->e == edge);
1440         (void)edge; /* quiet warning in release build */
1441         *r_v1 = edge_loop->v;
1442         *r_v2 = edge_loop->next->v;
1443 }
1444
1445 void BM_edge_ordered_verts(const BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
1446 {
1447         BM_edge_ordered_verts_ex(edge, r_v1, r_v2, edge->l);
1448 }
1449
1450 /**
1451  * \return The previous loop, over \a eps_sq distance from \a l (or \a NULL if l_stop is reached).
1452  */
1453 BMLoop *BM_loop_find_prev_nodouble(BMLoop *l, BMLoop *l_stop, const float eps_sq)
1454 {
1455         BMLoop *l_step = l->prev;
1456
1457         BLI_assert(!ELEM(l_stop, NULL, l));
1458
1459         while (UNLIKELY(len_squared_v3v3(l->v->co, l_step->v->co) < eps_sq)) {
1460                 l_step = l_step->prev;
1461                 BLI_assert(l_step != l);
1462                 if (UNLIKELY(l_step == l_stop)) {
1463                         return NULL;
1464                 }
1465         }
1466
1467         return l_step;
1468 }
1469
1470 /**
1471  * \return The next loop, over \a eps_sq distance from \a l (or \a NULL if l_stop is reached).
1472  */
1473 BMLoop *BM_loop_find_next_nodouble(BMLoop *l, BMLoop *l_stop, const float eps_sq)
1474 {
1475         BMLoop *l_step = l->next;
1476
1477         BLI_assert(!ELEM(l_stop, NULL, l));
1478
1479         while (UNLIKELY(len_squared_v3v3(l->v->co, l_step->v->co) < eps_sq)) {
1480                 l_step = l_step->next;
1481                 BLI_assert(l_step != l);
1482                 if (UNLIKELY(l_step == l_stop)) {
1483                         return NULL;
1484                 }
1485         }
1486
1487         return l_step;
1488 }
1489
1490 /**
1491  * Check if the loop is convex or concave
1492  * (depends on face normal)
1493  */
1494 bool BM_loop_is_convex(const BMLoop *l)
1495 {
1496         float e_dir_prev[3];
1497         float e_dir_next[3];
1498         float l_no[3];
1499
1500         sub_v3_v3v3(e_dir_prev, l->prev->v->co, l->v->co);
1501         sub_v3_v3v3(e_dir_next, l->next->v->co, l->v->co);
1502         cross_v3_v3v3(l_no, e_dir_next, e_dir_prev);
1503         return dot_v3v3(l_no, l->f->no) > 0.0f;
1504 }
1505
1506 /**
1507  * Calculates the angle between the previous and next loops
1508  * (angle at this loops face corner).
1509  *
1510  * \return angle in radians
1511  */
1512 float BM_loop_calc_face_angle(const BMLoop *l)
1513 {
1514         return angle_v3v3v3(l->prev->v->co,
1515                             l->v->co,
1516                             l->next->v->co);
1517 }
1518
1519 /**
1520  * \brief BM_loop_calc_face_normal
1521  *
1522  * Calculate the normal at this loop corner or fallback to the face normal on straight lines.
1523  *
1524  * \param l The loop to calculate the normal at
1525  * \param r_normal Resulting normal
1526  */
1527 void BM_loop_calc_face_normal(const BMLoop *l, float r_normal[3])
1528 {
1529         if (normal_tri_v3(r_normal,
1530                           l->prev->v->co,
1531                           l->v->co,
1532                           l->next->v->co) != 0.0f)
1533         {
1534                 /* pass */
1535         }
1536         else {
1537                 copy_v3_v3(r_normal, l->f->no);
1538         }
1539 }
1540
1541 /**
1542  * \brief BM_loop_calc_face_direction
1543  *
1544  * Calculate the direction a loop is pointing.
1545  *
1546  * \param l The loop to calculate the direction at
1547  * \param r_dir Resulting direction
1548  */
1549 void BM_loop_calc_face_direction(const BMLoop *l, float r_dir[3])
1550 {
1551         float v_prev[3];
1552         float v_next[3];
1553
1554         sub_v3_v3v3(v_prev, l->v->co, l->prev->v->co);
1555         sub_v3_v3v3(v_next, l->next->v->co, l->v->co);
1556
1557         normalize_v3(v_prev);
1558         normalize_v3(v_next);
1559
1560         add_v3_v3v3(r_dir, v_prev, v_next);
1561         normalize_v3(r_dir);
1562 }
1563
1564 /**
1565  * \brief BM_loop_calc_face_tangent
1566  *
1567  * Calculate the tangent at this loop corner or fallback to the face normal on straight lines.
1568  * This vector always points inward into the face.
1569  *
1570  * \param l The loop to calculate the tangent at
1571  * \param r_tangent Resulting tangent
1572  */
1573 void BM_loop_calc_face_tangent(const BMLoop *l, float r_tangent[3])
1574 {
1575         float v_prev[3];
1576         float v_next[3];
1577         float dir[3];
1578
1579         sub_v3_v3v3(v_prev, l->prev->v->co, l->v->co);
1580         sub_v3_v3v3(v_next, l->v->co, l->next->v->co);
1581
1582         normalize_v3(v_prev);
1583         normalize_v3(v_next);
1584         add_v3_v3v3(dir, v_prev, v_next);
1585
1586         if (compare_v3v3(v_prev, v_next, FLT_EPSILON * 10.0f) == false) {
1587                 float nor[3]; /* for this purpose doesn't need to be normalized */
1588                 cross_v3_v3v3(nor, v_prev, v_next);
1589                 /* concave face check */
1590                 if (UNLIKELY(dot_v3v3(nor, l->f->no) < 0.0f)) {
1591                         negate_v3(nor);
1592                 }
1593                 cross_v3_v3v3(r_tangent, dir, nor);
1594         }
1595         else {
1596                 /* prev/next are the same - compare with face normal since we don't have one */
1597                 cross_v3_v3v3(r_tangent, dir, l->f->no);
1598         }
1599
1600         normalize_v3(r_tangent);
1601 }
1602
1603 /**
1604  * \brief BMESH EDGE/FACE ANGLE
1605  *
1606  *  Calculates the angle between two faces.
1607  *  Assumes the face normals are correct.
1608  *
1609  * \return angle in radians
1610  */
1611 float BM_edge_calc_face_angle_ex(const BMEdge *e, const float fallback)
1612 {
1613         if (BM_edge_is_manifold(e)) {
1614                 const BMLoop *l1 = e->l;
1615                 const BMLoop *l2 = e->l->radial_next;
1616                 return angle_normalized_v3v3(l1->f->no, l2->f->no);
1617         }
1618         else {
1619                 return fallback;
1620         }
1621 }
1622 float BM_edge_calc_face_angle(const BMEdge *e)
1623 {
1624         return BM_edge_calc_face_angle_ex(e, DEG2RADF(90.0f));
1625 }
1626
1627 /**
1628  * \brief BMESH EDGE/FACE ANGLE
1629  *
1630  *  Calculates the angle between two faces.
1631  *  Assumes the face normals are correct.
1632  *
1633  * \return angle in radians
1634  */
1635 float BM_edge_calc_face_angle_signed_ex(const BMEdge *e, const float fallback)
1636 {
1637         if (BM_edge_is_manifold(e)) {
1638                 BMLoop *l1 = e->l;
1639                 BMLoop *l2 = e->l->radial_next;
1640                 const float angle = angle_normalized_v3v3(l1->f->no, l2->f->no);
1641                 return BM_edge_is_convex(e) ? angle : -angle;
1642         }
1643         else {
1644                 return fallback;
1645         }
1646 }
1647 float BM_edge_calc_face_angle_signed(const BMEdge *e)
1648 {
1649         return BM_edge_calc_face_angle_signed_ex(e, DEG2RADF(90.0f));
1650 }
1651
1652 /**
1653  * \brief BMESH EDGE/FACE TANGENT
1654  *
1655  * Calculate the tangent at this loop corner or fallback to the face normal on straight lines.
1656  * This vector always points inward into the face.
1657  *
1658  * \brief BM_edge_calc_face_tangent
1659  * \param e
1660  * \param e_loop The loop to calculate the tangent at,
1661  * used to get the face and winding direction.
1662  * \param r_tangent The loop corner tangent to set
1663  */
1664
1665 void BM_edge_calc_face_tangent(const BMEdge *e, const BMLoop *e_loop, float r_tangent[3])
1666 {
1667         float tvec[3];
1668         BMVert *v1, *v2;
1669         BM_edge_ordered_verts_ex(e, &v1, &v2, e_loop);
1670
1671         sub_v3_v3v3(tvec, v1->co, v2->co); /* use for temp storage */
1672         /* note, we could average the tangents of both loops,
1673          * for non flat ngons it will give a better direction */
1674         cross_v3_v3v3(r_tangent, tvec, e_loop->f->no);
1675         normalize_v3(r_tangent);
1676 }
1677
1678 /**
1679  * \brief BMESH VERT/EDGE ANGLE
1680  *
1681  * Calculates the angle a verts 2 edges.
1682  *
1683  * \returns the angle in radians
1684  */
1685 float BM_vert_calc_edge_angle_ex(const BMVert *v, const float fallback)
1686 {
1687         BMEdge *e1, *e2;
1688
1689         /* saves BM_vert_edge_count(v) and and edge iterator,
1690          * get the edges and count them both at once */
1691
1692         if ((e1 = v->e) &&
1693             (e2 =  bmesh_disk_edge_next(e1, v)) &&
1694             /* make sure we come full circle and only have 2 connected edges */
1695             (e1 == bmesh_disk_edge_next(e2, v)))
1696         {
1697                 BMVert *v1 = BM_edge_other_vert(e1, v);
1698                 BMVert *v2 = BM_edge_other_vert(e2, v);
1699
1700                 return (float)M_PI - angle_v3v3v3(v1->co, v->co, v2->co);
1701         }
1702         else {
1703                 return fallback;
1704         }
1705 }
1706
1707 float BM_vert_calc_edge_angle(const BMVert *v)
1708 {
1709         return BM_vert_calc_edge_angle_ex(v, DEG2RADF(90.0f));
1710 }
1711
1712 /**
1713  * \note this isn't optimal to run on an array of verts,
1714  * see 'solidify_add_thickness' for a function which runs on an array.
1715  */
1716 float BM_vert_calc_shell_factor(const BMVert *v)
1717 {
1718         BMIter iter;
1719         BMLoop *l;
1720         float accum_shell = 0.0f;
1721         float accum_angle = 0.0f;
1722
1723         BM_ITER_ELEM (l, &iter, (BMVert *)v, BM_LOOPS_OF_VERT) {
1724                 const float face_angle = BM_loop_calc_face_angle(l);
1725                 accum_shell += shell_v3v3_normalized_to_dist(v->no, l->f->no) * face_angle;
1726                 accum_angle += face_angle;
1727         }
1728
1729         if (accum_angle != 0.0f) {
1730                 return accum_shell / accum_angle;
1731         }
1732         else {
1733                 return 1.0f;
1734         }
1735 }
1736 /* alternate version of #BM_vert_calc_shell_factor which only
1737  * uses 'hflag' faces, but falls back to all if none found. */
1738 float BM_vert_calc_shell_factor_ex(const BMVert *v, const float no[3], const char hflag)
1739 {
1740         BMIter iter;
1741         const BMLoop *l;
1742         float accum_shell = 0.0f;
1743         float accum_angle = 0.0f;
1744         int tot_sel = 0, tot = 0;
1745
1746         BM_ITER_ELEM (l, &iter, (BMVert *)v, BM_LOOPS_OF_VERT) {
1747                 if (BM_elem_flag_test(l->f, hflag)) {  /* <-- main difference to BM_vert_calc_shell_factor! */
1748                         const float face_angle = BM_loop_calc_face_angle(l);
1749                         accum_shell += shell_v3v3_normalized_to_dist(no, l->f->no) * face_angle;
1750                         accum_angle += face_angle;
1751                         tot_sel++;
1752                 }
1753                 tot++;
1754         }
1755
1756         if (accum_angle != 0.0f) {
1757                 return accum_shell / accum_angle;
1758         }
1759         else {
1760                 /* other main difference from BM_vert_calc_shell_factor! */
1761                 if (tot != 0 && tot_sel == 0) {
1762                         /* none selected, so use all */
1763                         return BM_vert_calc_shell_factor(v);
1764                 }
1765                 else {
1766                         return 1.0f;
1767                 }
1768         }
1769 }
1770
1771 /**
1772  * \note quite an obscure function.
1773  * used in bmesh operators that have a relative scale options,
1774  */
1775 float BM_vert_calc_mean_tagged_edge_length(const BMVert *v)
1776 {
1777         BMIter iter;
1778         BMEdge *e;
1779         int tot;
1780         float length = 0.0f;
1781
1782         BM_ITER_ELEM_INDEX (e, &iter, (BMVert *)v, BM_EDGES_OF_VERT, tot) {
1783                 const BMVert *v_other = BM_edge_other_vert(e, v);
1784                 if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
1785                         length += BM_edge_calc_length(e);
1786                 }
1787         }
1788
1789         if (tot) {
1790                 return length / (float)tot;
1791         }
1792         else {
1793                 return 0.0f;
1794         }
1795 }
1796
1797
1798 /**
1799  * Returns the loop of the shortest edge in f.
1800  */
1801 BMLoop *BM_face_find_shortest_loop(BMFace *f)
1802 {
1803         BMLoop *shortest_loop = NULL;
1804         float shortest_len = FLT_MAX;
1805
1806         BMLoop *l_iter;
1807         BMLoop *l_first;
1808
1809         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1810
1811         do {
1812                 const float len_sq = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1813                 if (len_sq <= shortest_len) {
1814                         shortest_loop = l_iter;
1815                         shortest_len = len_sq;
1816                 }
1817         } while ((l_iter = l_iter->next) != l_first);
1818
1819         return shortest_loop;
1820 }
1821
1822 /**
1823  * Returns the loop of the longest edge in f.
1824  */
1825 BMLoop *BM_face_find_longest_loop(BMFace *f)
1826 {
1827         BMLoop *longest_loop = NULL;
1828         float len_max_sq = 0.0f;
1829
1830         BMLoop *l_iter;
1831         BMLoop *l_first;
1832
1833         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1834
1835         do {
1836                 const float len_sq = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1837                 if (len_sq >= len_max_sq) {
1838                         longest_loop = l_iter;
1839                         len_max_sq = len_sq;
1840                 }
1841         } while ((l_iter = l_iter->next) != l_first);
1842
1843         return longest_loop;
1844 }
1845
1846 /**
1847  * Returns the edge existing between \a v_a and \a v_b, or NULL if there isn't one.
1848  *
1849  * \note multiple edges may exist between any two vertices, and therefore
1850  * this function only returns the first one found.
1851  */
1852 #if 0
1853 BMEdge *BM_edge_exists(BMVert *v_a, BMVert *v_b)
1854 {
1855         BMIter iter;
1856         BMEdge *e;
1857
1858
1859         BLI_assert(v_a != v_b);
1860         BLI_assert(v_a->head.htype == BM_VERT && v_b->head.htype == BM_VERT);
1861
1862         BM_ITER_ELEM (e, &iter, v_a, BM_EDGES_OF_VERT) {
1863                 if (e->v1 == v_b || e->v2 == v_b)
1864                         return e;
1865         }
1866
1867         return NULL;
1868 }
1869 #else
1870 BMEdge *BM_edge_exists(BMVert *v_a, BMVert *v_b)
1871 {
1872         /* speedup by looping over both edges verts
1873          * where one vert may connect to many edges but not the other. */
1874
1875         BMEdge *e_a, *e_b;
1876
1877         BLI_assert(v_a != v_b);
1878         BLI_assert(v_a->head.htype == BM_VERT && v_b->head.htype == BM_VERT);
1879
1880         if ((e_a = v_a->e) && (e_b = v_b->e)) {
1881                 BMEdge *e_a_iter = e_a, *e_b_iter = e_b;
1882
1883                 do {
1884                         if (BM_vert_in_edge(e_a_iter, v_b)) {
1885                                 return e_a_iter;
1886                         }
1887                         if (BM_vert_in_edge(e_b_iter, v_a)) {
1888                                 return e_b_iter;
1889                         }
1890                 } while (((e_a_iter = bmesh_disk_edge_next(e_a_iter, v_a)) != e_a) &&
1891                          ((e_b_iter = bmesh_disk_edge_next(e_b_iter, v_b)) != e_b));
1892         }
1893
1894         return NULL;
1895 }
1896 #endif
1897
1898 /**
1899  * Returns an edge sharing the same vertices as this one.
1900  * This isn't an invalid state but tools should clean up these cases before
1901  * returning the mesh to the user.
1902  */
1903 BMEdge *BM_edge_find_double(BMEdge *e)
1904 {
1905         BMVert *v       = e->v1;
1906         BMVert *v_other = e->v2;
1907
1908         BMEdge *e_iter;
1909
1910         e_iter = e;
1911         while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e) {
1912                 if (UNLIKELY(BM_vert_in_edge(e_iter, v_other))) {
1913                         return e_iter;
1914                 }
1915         }
1916
1917         return NULL;
1918 }
1919
1920 /**
1921  * Given a set of vertices (varr), find out if
1922  * there is a face with exactly those vertices
1923  * (and only those vertices).
1924  *
1925  * \note there used to be a BM_face_exists_overlap function that checks for partial overlap.
1926  */
1927 bool BM_face_exists(BMVert **varr, int len, BMFace **r_existface)
1928 {
1929         if (varr[0]->e) {
1930                 BMEdge *e_iter, *e_first;
1931                 e_iter = e_first = varr[0]->e;
1932
1933                 /* would normally use BM_LOOPS_OF_VERT, but this runs so often,
1934                  * its faster to iterate on the data directly */
1935                 do {
1936                         if (e_iter->l) {
1937                                 BMLoop *l_iter_radial, *l_first_radial;
1938                                 l_iter_radial = l_first_radial = e_iter->l;
1939
1940                                 do {
1941                                         if ((l_iter_radial->v == varr[0]) &&
1942                                             (l_iter_radial->f->len == len))
1943                                         {
1944                                                 /* the fist 2 verts match, now check the remaining (len - 2) faces do too
1945                                                  * winding isn't known, so check in both directions */
1946                                                 int i_walk = 2;
1947
1948                                                 if (l_iter_radial->next->v == varr[1]) {
1949                                                         BMLoop *l_walk = l_iter_radial->next->next;
1950                                                         do {
1951                                                                 if (l_walk->v != varr[i_walk]) {
1952                                                                         break;
1953                                                                 }
1954                                                         } while ((void)(l_walk = l_walk->next), ++i_walk != len);
1955                                                 }
1956                                                 else if (l_iter_radial->prev->v == varr[1]) {
1957                                                         BMLoop *l_walk = l_iter_radial->prev->prev;
1958                                                         do {
1959                                                                 if (l_walk->v != varr[i_walk]) {
1960                                                                         break;
1961                                                                 }
1962                                                         } while ((void)(l_walk = l_walk->prev), ++i_walk != len);
1963                                                 }
1964
1965                                                 if (i_walk == len) {
1966                                                         if (r_existface) {
1967                                                                 *r_existface = l_iter_radial->f;
1968                                                         }
1969                                                         return true;
1970                                                 }
1971                                         }
1972                                 } while ((l_iter_radial = l_iter_radial->radial_next) != l_first_radial);
1973
1974                         }
1975                 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, varr[0])) != e_first);
1976         }
1977
1978         if (r_existface) {
1979                 *r_existface = NULL;
1980         }
1981         return false;
1982 }
1983
1984
1985 /**
1986  * Given a set of vertices and edges (\a varr, \a earr), find out if
1987  * all those vertices are filled in by existing faces that _only_ use those vertices.
1988  *
1989  * This is for use in cases where creating a face is possible but would result in
1990  * many overlapping faces.
1991  *
1992  * An example of how this is used: when 2 tri's are selected that share an edge,
1993  * pressing Fkey would make a new overlapping quad (without a check like this)
1994  *
1995  * \a earr and \a varr can be in any order, however they _must_ form a closed loop.
1996  */
1997 bool BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len)
1998 {
1999         BMFace *f;
2000         BMEdge *e;
2001         BMVert *v;
2002         bool ok;
2003         int tot_tag;
2004
2005         BMIter fiter;
2006         BMIter viter;
2007
2008         int i;
2009
2010         for (i = 0; i < len; i++) {
2011                 /* save some time by looping over edge faces rather then vert faces
2012                  * will still loop over some faces twice but not as many */
2013                 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
2014                         BM_elem_flag_disable(f, BM_ELEM_INTERNAL_TAG);
2015                         BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
2016                                 BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
2017                         }
2018                 }
2019
2020                 /* clear all edge tags */
2021                 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
2022                         BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
2023                 }
2024         }
2025
2026         /* now tag all verts and edges in the boundary array as true so
2027          * we can know if a face-vert is from our array */
2028         for (i = 0; i < len; i++) {
2029                 BM_elem_flag_enable(varr[i], BM_ELEM_INTERNAL_TAG);
2030                 BM_elem_flag_enable(earr[i], BM_ELEM_INTERNAL_TAG);
2031         }
2032
2033
2034         /* so! boundary is tagged, everything else cleared */
2035
2036
2037         /* 1) tag all faces connected to edges - if all their verts are boundary */
2038         tot_tag = 0;
2039         for (i = 0; i < len; i++) {
2040                 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
2041                         if (!BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
2042                                 ok = true;
2043                                 BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
2044                                         if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) {
2045                                                 ok = false;
2046                                                 break;
2047                                         }
2048                                 }
2049
2050                                 if (ok) {
2051                                         /* we only use boundary verts */
2052                                         BM_elem_flag_enable(f, BM_ELEM_INTERNAL_TAG);
2053                                         tot_tag++;
2054                                 }
2055                         }
2056                         else {
2057                                 /* we already found! */
2058                         }
2059                 }
2060         }
2061
2062         if (tot_tag == 0) {
2063                 /* no faces use only boundary verts, quit early */
2064                 return false;
2065         }
2066
2067         /* 2) loop over non-boundary edges that use boundary verts,
2068          *    check each have 2 tagged faces connected (faces that only use 'varr' verts) */
2069         ok = true;
2070         for (i = 0; i < len; i++) {
2071                 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
2072
2073                         if (/* non-boundary edge */
2074                             BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == false &&
2075                             /* ...using boundary verts */
2076                             BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) &&
2077                             BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG))
2078                         {
2079                                 int tot_face_tag = 0;
2080                                 BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
2081                                         if (BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
2082                                                 tot_face_tag++;
2083                                         }
2084                                 }
2085
2086                                 if (tot_face_tag != 2) {
2087                                         ok = false;
2088                                         break;
2089                                 }
2090
2091                         }
2092                 }
2093
2094                 if (ok == false) {
2095                         break;
2096                 }
2097         }
2098
2099         return ok;
2100 }
2101
2102 /* same as 'BM_face_exists_multi' but built vert array from edges */
2103 bool BM_face_exists_multi_edge(BMEdge **earr, int len)
2104 {
2105         BMVert **varr = BLI_array_alloca(varr, len);
2106
2107         /* first check if verts have edges, if not we can bail out early */
2108         if (!BM_verts_from_edges(varr, earr, len)) {
2109                 BMESH_ASSERT(0);
2110                 return false;
2111         }
2112
2113         return BM_face_exists_multi(varr, earr, len);
2114 }
2115
2116
2117 /**
2118  * Given a set of vertices (varr), find out if
2119  * all those vertices overlap an existing face.
2120  *
2121  * \note The face may contain other verts \b not in \a varr.
2122  *
2123  * \note Its possible there are more than one overlapping faces,
2124  * in this case the first one found will be assigned to \a r_f_overlap.
2125  *
2126  * \param varr  Array of unordered verts.
2127  * \param len  \a varr array length.
2128  * \param r_f_overlap  The overlapping face to return.
2129  * \return Success
2130  */
2131
2132 bool BM_face_exists_overlap(BMVert **varr, const int len, BMFace **r_f_overlap)
2133 {
2134         BMIter viter;
2135         BMFace *f;
2136         int i;
2137         bool is_overlap = false;
2138         LinkNode *f_lnk = NULL;
2139
2140         if (r_f_overlap) {
2141                 *r_f_overlap = NULL;
2142         }
2143
2144 #ifdef DEBUG
2145         /* check flag isn't already set */
2146         for (i = 0; i < len; i++) {
2147                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
2148                         BLI_assert(BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0);
2149                 }
2150         }
2151 #endif
2152
2153         for (i = 0; i < len; i++) {
2154                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
2155                         if (BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0) {
2156                                 if (len <= BM_verts_in_face_count(varr, len, f)) {
2157                                         if (r_f_overlap)
2158                                                 *r_f_overlap = f;
2159
2160                                         is_overlap = true;
2161                                         break;
2162                                 }
2163
2164                                 BM_ELEM_API_FLAG_ENABLE(f, _FLAG_OVERLAP);
2165                                 BLI_linklist_prepend_alloca(&f_lnk, f);
2166                         }
2167                 }
2168         }
2169
2170         for (; f_lnk; f_lnk = f_lnk->next) {
2171                 BM_ELEM_API_FLAG_DISABLE((BMFace *)f_lnk->link, _FLAG_OVERLAP);
2172         }
2173
2174         return is_overlap;
2175 }
2176
2177 /**
2178  * Given a set of vertices (varr), find out if
2179  * there is a face that uses vertices only from this list
2180  * (that the face is a subset or made from the vertices given).
2181  *
2182  * \param varr  Array of unordered verts.
2183  * \param len  varr array length.
2184  */
2185 bool BM_face_exists_overlap_subset(BMVert **varr, const int len)
2186 {
2187         BMIter viter;
2188         BMFace *f;
2189         bool is_init = false;
2190         bool is_overlap = false;
2191         LinkNode *f_lnk = NULL;
2192
2193 #ifdef DEBUG
2194         /* check flag isn't already set */
2195         for (int i = 0; i < len; i++) {
2196                 BLI_assert(BM_ELEM_API_FLAG_TEST(varr[i], _FLAG_OVERLAP) == 0);
2197                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
2198                         BLI_assert(BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0);
2199                 }
2200         }
2201 #endif
2202
2203         for (int i = 0; i < len; i++) {
2204                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
2205                         if ((f->len <= len) && (BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0)) {
2206                                 /* check if all vers in this face are flagged*/
2207                                 BMLoop *l_iter, *l_first;
2208
2209                                 if (is_init == false) {
2210                                         is_init = true;
2211                                         for (int j = 0; j < len; j++) {
2212                                                 BM_ELEM_API_FLAG_ENABLE(varr[j], _FLAG_OVERLAP);
2213                                         }
2214                                 }
2215
2216                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2217                                 is_overlap = true;
2218                                 do {
2219                                         if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP) == 0) {
2220                                                 is_overlap = false;
2221                                                 break;
2222                                         }
2223                                 } while ((l_iter = l_iter->next) != l_first);
2224
2225                                 if (is_overlap) {
2226                                         break;
2227                                 }
2228
2229                                 BM_ELEM_API_FLAG_ENABLE(f, _FLAG_OVERLAP);
2230                                 BLI_linklist_prepend_alloca(&f_lnk, f);
2231                         }
2232                 }
2233         }
2234
2235         if (is_init == true) {
2236                 for (int i = 0; i < len; i++) {
2237                         BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
2238                 }
2239         }
2240
2241         for (; f_lnk; f_lnk = f_lnk->next) {
2242                 BM_ELEM_API_FLAG_DISABLE((BMFace *)f_lnk->link, _FLAG_OVERLAP);
2243         }
2244
2245         return is_overlap;
2246 }
2247
2248 bool BM_vert_is_all_edge_flag_test(const BMVert *v, const char hflag, const bool respect_hide)
2249 {
2250         if (v->e) {
2251                 BMEdge *e_other;
2252                 BMIter eiter;
2253
2254                 BM_ITER_ELEM (e_other, &eiter, (BMVert *)v, BM_EDGES_OF_VERT) {
2255                         if (!respect_hide || !BM_elem_flag_test(e_other, BM_ELEM_HIDDEN)) {
2256                                 if (!BM_elem_flag_test(e_other, hflag)) {
2257                                         return false;
2258                                 }
2259                         }
2260                 }
2261         }
2262
2263         return true;
2264 }
2265
2266 bool BM_vert_is_all_face_flag_test(const BMVert *v, const char hflag, const bool respect_hide)
2267 {
2268         if (v->e) {
2269                 BMEdge *f_other;
2270                 BMIter fiter;
2271
2272                 BM_ITER_ELEM (f_other, &fiter, (BMVert *)v, BM_FACES_OF_VERT) {
2273                         if (!respect_hide || !BM_elem_flag_test(f_other, BM_ELEM_HIDDEN)) {
2274                                 if (!BM_elem_flag_test(f_other, hflag)) {
2275                                         return false;
2276                                 }
2277                         }
2278                 }
2279         }
2280
2281         return true;
2282 }
2283
2284
2285 bool BM_edge_is_all_face_flag_test(const BMEdge *e, const char hflag, const bool respect_hide)
2286 {
2287         if (e->l) {
2288                 BMLoop *l_iter, *l_first;
2289
2290                 l_iter = l_first = e->l;
2291                 do {
2292                         if (!respect_hide || !BM_elem_flag_test(l_iter->f, BM_ELEM_HIDDEN)) {
2293                                 if (!BM_elem_flag_test(l_iter->f, hflag)) {
2294                                         return false;
2295                                 }
2296                         }
2297                 } while ((l_iter = l_iter->radial_next) != l_first);
2298         }
2299
2300         return true;
2301 }
2302
2303 /* convenience functions for checking flags */
2304 bool BM_edge_is_any_vert_flag_test(const BMEdge *e, const char hflag)
2305 {
2306         return (BM_elem_flag_test(e->v1, hflag) ||
2307                 BM_elem_flag_test(e->v2, hflag));
2308 }
2309
2310 bool BM_face_is_any_vert_flag_test(const BMFace *f, const char hflag)
2311 {
2312         BMLoop *l_iter;
2313         BMLoop *l_first;
2314
2315         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2316         do {
2317                 if (BM_elem_flag_test(l_iter->v, hflag)) {
2318                         return true;
2319                 }
2320         } while ((l_iter = l_iter->next) != l_first);
2321         return false;
2322 }
2323
2324 bool BM_face_is_any_edge_flag_test(const BMFace *f, const char hflag)
2325 {
2326         BMLoop *l_iter;
2327         BMLoop *l_first;
2328
2329         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2330         do {
2331                 if (BM_elem_flag_test(l_iter->e, hflag)) {
2332                         return true;
2333                 }
2334         } while ((l_iter = l_iter->next) != l_first);
2335         return false;
2336 }
2337
2338 /**
2339  * Use within assert's to check normals are valid.
2340  */
2341 bool BM_face_is_normal_valid(const BMFace *f)
2342 {
2343         const float eps = 0.0001f;
2344         float no[3];
2345
2346         BM_face_calc_normal(f, no);
2347         return len_squared_v3v3(no, f->no) < (eps * eps);
2348 }
2349
2350 static void bm_mesh_calc_volume_face(const BMFace *f, float *r_vol)
2351 {
2352         const int tottri = f->len - 2;
2353         BMLoop **loops = BLI_array_alloca(loops, f->len);
2354         unsigned int (*index)[3] = BLI_array_alloca(index, tottri);
2355         int j;
2356
2357         BM_face_calc_tessellation(f, false, loops, index);
2358
2359         for (j = 0; j < tottri; j++) {
2360                 const float *p1 = loops[index[j][0]]->v->co;
2361                 const float *p2 = loops[index[j][1]]->v->co;
2362                 const float *p3 = loops[index[j][2]]->v->co;
2363
2364                 /* co1.dot(co2.cross(co3)) / 6.0 */
2365                 float cross[3];
2366                 cross_v3_v3v3(cross, p2, p3);
2367                 *r_vol += (1.0f / 6.0f) * dot_v3v3(p1, cross);
2368         }
2369 }
2370 float BM_mesh_calc_volume(BMesh *bm, bool is_signed)
2371 {
2372         /* warning, calls own tessellation function, may be slow */
2373         float vol = 0.0f;
2374         BMFace *f;
2375         BMIter fiter;
2376
2377         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
2378                 bm_mesh_calc_volume_face(f, &vol);
2379         }
2380
2381         if (is_signed == false) {
2382                 vol = fabsf(vol);
2383         }
2384
2385         return vol;
2386 }
2387
2388 /* note, almost duplicate of BM_mesh_calc_edge_groups, keep in sync */
2389 /**
2390  * Calculate isolated groups of faces with optional filtering.
2391  *
2392  * \param bm  the BMesh.
2393  * \param r_groups_array  Array of ints to fill in, length of bm->totface
2394  *        (or when hflag_test is set, the number of flagged faces).
2395  * \param r_group_index  index, length pairs into \a r_groups_array, size of return value
2396  *        int pairs: (array_start, array_length).
2397  * \param filter_fn  Filter the edge-loops or vert-loops we step over (depends on \a htype_step).
2398  * \param user_data  Optional user data for \a filter_fn, can be NULL.
2399  * \param hflag_test  Optional flag to test faces,
2400  *        use to exclude faces from the calculation, 0 for all faces.
2401  * \param htype_step  BM_VERT to walk over face-verts, BM_EDGE to walk over faces edges
2402  *        (having both set is supported too).
2403  * \return The number of groups found.
2404  */
2405 int BM_mesh_calc_face_groups(
2406         BMesh *bm, int *r_groups_array, int (**r_group_index)[2],
2407         BMLoopFilterFunc filter_fn, void *user_data,
2408         const char hflag_test, const char htype_step)
2409 {
2410 #ifdef DEBUG
2411         int group_index_len = 1;
2412 #else
2413         int group_index_len = 32;
2414 #endif
2415
2416         int (*group_index)[2] = MEM_mallocN(sizeof(*group_index) * group_index_len, __func__);
2417
2418         int *group_array = r_groups_array;
2419         STACK_DECLARE(group_array);
2420
2421         int group_curr = 0;
2422
2423         unsigned int tot_faces = 0;
2424         unsigned int tot_touch = 0;
2425
2426         BMFace **stack;
2427         STACK_DECLARE(stack);
2428
2429         BMIter iter;
2430         BMFace *f;
2431         int i;
2432
2433         STACK_INIT(group_array, bm->totface);
2434
2435         BLI_assert(((htype_step & ~(BM_VERT | BM_EDGE)) == 0) && (htype_step != 0));
2436
2437         /* init the array */
2438         BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
2439                 if ((hflag_test == 0) || BM_elem_flag_test(f, hflag_test)) {
2440                         tot_faces++;
2441                         BM_elem_flag_disable(f, BM_ELEM_TAG);
2442                 }
2443                 else {
2444                         /* never walk over tagged */
2445                         BM_elem_flag_enable(f, BM_ELEM_TAG);
2446                 }
2447
2448                 BM_elem_index_set(f, i); /* set_inline */
2449         }
2450         bm->elem_index_dirty &= ~BM_FACE;
2451
2452         /* detect groups */
2453         stack = MEM_mallocN(sizeof(*stack) * tot_faces, __func__);
2454
2455         while (tot_touch != tot_faces) {
2456                 int *group_item;
2457                 bool ok = false;
2458
2459                 BLI_assert(tot_touch < tot_faces);
2460
2461                 STACK_INIT(stack, tot_faces);
2462
2463                 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
2464                         if (BM_elem_flag_test(f, BM_ELEM_TAG) == false) {
2465                                 BM_elem_flag_enable(f, BM_ELEM_TAG);
2466                                 STACK_PUSH(stack, f);
2467                                 ok = true;
2468                                 break;
2469                         }
2470                 }
2471
2472                 BLI_assert(ok == true);
2473                 UNUSED_VARS_NDEBUG(ok);
2474
2475                 /* manage arrays */
2476                 if (group_index_len == group_curr) {
2477                         group_index_len *= 2;
2478                         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_index_len);
2479                 }
2480
2481                 group_item = group_index[group_curr];
2482                 group_item[0] = STACK_SIZE(group_array);
2483                 group_item[1] = 0;
2484
2485                 while ((f = STACK_POP(stack))) {
2486                         BMLoop *l_iter, *l_first;
2487
2488                         /* add face */
2489                         STACK_PUSH(group_array, BM_elem_index_get(f));
2490                         tot_touch++;
2491                         group_item[1]++;
2492                         /* done */
2493
2494                         if (htype_step & BM_EDGE) {
2495                                 /* search for other faces */
2496                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2497                                 do {
2498                                         BMLoop *l_radial_iter = l_iter->radial_next;
2499                                         if ((l_radial_iter != l_iter) &&
2500                                             ((filter_fn == NULL) || filter_fn(l_iter, user_data)))
2501                                         {
2502                                                 do {
2503                                                         BMFace *f_other = l_radial_iter->f;
2504                                                         if (BM_elem_flag_test(f_other, BM_ELEM_TAG) == false) {
2505                                                                 BM_elem_flag_enable(f_other, BM_ELEM_TAG);
2506                                                                 STACK_PUSH(stack, f_other);
2507                                                         }
2508                                                 } while ((l_radial_iter = l_radial_iter->radial_next) != l_iter);
2509                                         }
2510                                 } while ((l_iter = l_iter->next) != l_first);
2511                         }
2512
2513                         if (htype_step & BM_VERT) {
2514                                 BMIter liter;
2515                                 /* search for other faces */
2516                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2517                                 do {
2518                                         if ((filter_fn == NULL) || filter_fn(l_iter, user_data)) {
2519                                                 BMLoop *l_other;
2520                                                 BM_ITER_ELEM (l_other, &liter, l_iter, BM_LOOPS_OF_LOOP) {
2521                                                         BMFace *f_other = l_other->f;
2522                                                         if (BM_elem_flag_test(f_other, BM_ELEM_TAG) == false) {
2523                                                                 BM_elem_flag_enable(f_other, BM_ELEM_TAG);
2524                                                                 STACK_PUSH(stack, f_other);
2525                                                         }
2526                                                 }
2527                                         }
2528                                 } while ((l_iter = l_iter->next) != l_first);
2529                         }
2530                 }
2531
2532                 group_curr++;
2533         }
2534
2535         MEM_freeN(stack);
2536
2537         /* reduce alloc to required size */
2538         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_curr);
2539         *r_group_index = group_index;
2540
2541         return group_curr;
2542 }
2543
2544 /* note, almost duplicate of BM_mesh_calc_face_groups, keep in sync */
2545 /**
2546  * Calculate isolated groups of edges with optional filtering.
2547  *
2548  * \param bm  the BMesh.
2549  * \param r_groups_array  Array of ints to fill in, length of bm->totedge
2550  *        (or when hflag_test is set, the number of flagged edges).
2551  * \param r_group_index  index, length pairs into \a r_groups_array, size of return value
2552  *        int pairs: (array_start, array_length).
2553  * \param filter_fn  Filter the edges or verts we step over (depends on \a htype_step)
2554  *        as to which types we deal with.
2555  * \param user_data  Optional user data for \a filter_fn, can be NULL.
2556  * \param hflag_test  Optional flag to test edges,
2557  *        use to exclude edges from the calculation, 0 for all edges.
2558  * \return The number of groups found.
2559  *
2560  * \note Unlike #BM_mesh_calc_face_groups there is no 'htype_step' argument,
2561  *       since we always walk over verts.
2562  */
2563 int BM_mesh_calc_edge_groups(
2564         BMesh *bm, int *r_groups_array, int (**r_group_index)[2],
2565         BMVertFilterFunc filter_fn, void *user_data,
2566         const char hflag_test)
2567 {
2568 #ifdef DEBUG
2569         int group_index_len = 1;
2570 #else
2571         int group_index_len = 32;
2572 #endif
2573
2574         int (*group_index)[2] = MEM_mallocN(sizeof(*group_index) * group_index_len, __func__);
2575
2576         int *group_array = r_groups_array;
2577         STACK_DECLARE(group_array);
2578
2579         int group_curr = 0;
2580
2581         unsigned int tot_edges = 0;
2582         unsigned int tot_touch = 0;
2583
2584         BMEdge **stack;
2585         STACK_DECLARE(stack);
2586
2587         BMIter iter;
2588         BMEdge *e;
2589         int i;
2590
2591         STACK_INIT(group_array, bm->totedge);
2592
2593         /* init the array */
2594         BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
2595                 if ((hflag_test == 0) || BM_elem_flag_test(e, hflag_test)) {
2596                         tot_edges++;
2597                         BM_elem_flag_disable(e, BM_ELEM_TAG);
2598                 }
2599                 else {
2600                         /* never walk over tagged */
2601                         BM_elem_flag_enable(e, BM_ELEM_TAG);
2602                 }
2603
2604                 BM_elem_index_set(e, i); /* set_inline */
2605         }
2606         bm->elem_index_dirty &= ~BM_EDGE;
2607
2608         /* detect groups */
2609         stack = MEM_mallocN(sizeof(*stack) * tot_edges, __func__);
2610
2611         while (tot_touch != tot_edges) {
2612                 int *group_item;
2613                 bool ok = false;
2614
2615                 BLI_assert(tot_touch < tot_edges);
2616
2617                 STACK_INIT(stack, tot_edges);
2618
2619                 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
2620                         if (BM_elem_flag_test(e, BM_ELEM_TAG) == false) {
2621                                 BM_elem_flag_enable(e, BM_ELEM_TAG);
2622                                 STACK_PUSH(stack, e);
2623                                 ok = true;
2624                                 break;
2625                         }
2626                 }
2627
2628                 BLI_assert(ok == true);
2629                 UNUSED_VARS_NDEBUG(ok);
2630
2631                 /* manage arrays */
2632                 if (group_index_len == group_curr) {
2633                         group_index_len *= 2;
2634                         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_index_len);
2635                 }
2636
2637                 group_item = group_index[group_curr];
2638                 group_item[0] = STACK_SIZE(group_array);
2639                 group_item[1] = 0;
2640
2641                 while ((e = STACK_POP(stack))) {
2642                         BMIter viter;
2643                         BMIter eiter;
2644                         BMVert *v;
2645
2646                         /* add edge */
2647                         STACK_PUSH(group_array, BM_elem_index_get(e));
2648                         tot_touch++;
2649                         group_item[1]++;
2650                         /* done */
2651
2652                         /* search for other edges */
2653                         BM_ITER_ELEM (v, &viter, e, BM_VERTS_OF_EDGE) {
2654                                 if ((filter_fn == NULL) || filter_fn(v, user_data)) {
2655                                         BMEdge *e_other;
2656                                         BM_ITER_ELEM (e_other, &eiter, v, BM_EDGES_OF_VERT) {
2657                                                 if (BM_elem_flag_test(e_other, BM_ELEM_TAG) == false) {
2658                                                         BM_elem_flag_enable(e_other, BM_ELEM_TAG);
2659                                                         STACK_PUSH(stack, e_other);
2660                                                 }
2661                                         }
2662                                 }
2663                         }
2664                 }
2665
2666                 group_curr++;
2667         }
2668
2669         MEM_freeN(stack);
2670
2671         /* reduce alloc to required size */
2672         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_curr);
2673         *r_group_index = group_index;
2674
2675         return group_curr;
2676 }
2677
2678 float bmesh_subd_falloff_calc(const int falloff, float val)
2679 {
2680         switch (falloff) {
2681                 case SUBD_FALLOFF_SMOOTH:
2682                         val = 3.0f * val * val - 2.0f * val * val * val;
2683                         break;
2684                 case SUBD_FALLOFF_SPHERE:
2685                         val = sqrtf(2.0f * val - val * val);
2686                         break;
2687                 case SUBD_FALLOFF_ROOT:
2688                         val = sqrtf(val);
2689                         break;
2690                 case SUBD_FALLOFF_SHARP:
2691                         val = val * val;
2692                         break;
2693                 case SUBD_FALLOFF_LIN:
2694                         break;
2695                 case SUBD_FALLOFF_INVSQUARE:
2696                         val = val * (2.0f - val);
2697                         break;
2698                 default:
2699                         BLI_assert(0);
2700                         break;
2701         }
2702
2703         return val;
2704 }