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