540888ac0b961ee669df21e5b5b43aab75c28158
[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.
1684  * Assumes the face normals are correct.
1685  *
1686  * \return angle in radians
1687  */
1688 float BM_edge_calc_face_angle_signed_ex(const BMEdge *e, const float fallback)
1689 {
1690         if (BM_edge_is_manifold(e)) {
1691                 BMLoop *l1 = e->l;
1692                 BMLoop *l2 = e->l->radial_next;
1693                 const float angle = angle_normalized_v3v3(l1->f->no, l2->f->no);
1694                 return BM_edge_is_convex(e) ? angle : -angle;
1695         }
1696         else {
1697                 return fallback;
1698         }
1699 }
1700 float BM_edge_calc_face_angle_signed(const BMEdge *e)
1701 {
1702         return BM_edge_calc_face_angle_signed_ex(e, DEG2RADF(90.0f));
1703 }
1704
1705 /**
1706  * \brief BMESH EDGE/FACE TANGENT
1707  *
1708  * Calculate the tangent at this loop corner or fallback to the face normal on straight lines.
1709  * This vector always points inward into the face.
1710  *
1711  * \brief BM_edge_calc_face_tangent
1712  * \param e
1713  * \param e_loop The loop to calculate the tangent at,
1714  * used to get the face and winding direction.
1715  * \param r_tangent The loop corner tangent to set
1716  */
1717
1718 void BM_edge_calc_face_tangent(const BMEdge *e, const BMLoop *e_loop, float r_tangent[3])
1719 {
1720         float tvec[3];
1721         BMVert *v1, *v2;
1722         BM_edge_ordered_verts_ex(e, &v1, &v2, e_loop);
1723
1724         sub_v3_v3v3(tvec, v1->co, v2->co); /* use for temp storage */
1725         /* note, we could average the tangents of both loops,
1726          * for non flat ngons it will give a better direction */
1727         cross_v3_v3v3(r_tangent, tvec, e_loop->f->no);
1728         normalize_v3(r_tangent);
1729 }
1730
1731 /**
1732  * \brief BMESH VERT/EDGE ANGLE
1733  *
1734  * Calculates the angle a verts 2 edges.
1735  *
1736  * \returns the angle in radians
1737  */
1738 float BM_vert_calc_edge_angle_ex(const BMVert *v, const float fallback)
1739 {
1740         BMEdge *e1, *e2;
1741
1742         /* saves BM_vert_edge_count(v) and and edge iterator,
1743          * get the edges and count them both at once */
1744
1745         if ((e1 = v->e) &&
1746             (e2 =  bmesh_disk_edge_next(e1, v)) &&
1747             (e1 != e2) &&
1748             /* make sure we come full circle and only have 2 connected edges */
1749             (e1 == bmesh_disk_edge_next(e2, v)))
1750         {
1751                 BMVert *v1 = BM_edge_other_vert(e1, v);
1752                 BMVert *v2 = BM_edge_other_vert(e2, v);
1753
1754                 return (float)M_PI - angle_v3v3v3(v1->co, v->co, v2->co);
1755         }
1756         else {
1757                 return fallback;
1758         }
1759 }
1760
1761 float BM_vert_calc_edge_angle(const BMVert *v)
1762 {
1763         return BM_vert_calc_edge_angle_ex(v, DEG2RADF(90.0f));
1764 }
1765
1766 /**
1767  * \note this isn't optimal to run on an array of verts,
1768  * see 'solidify_add_thickness' for a function which runs on an array.
1769  */
1770 float BM_vert_calc_shell_factor(const BMVert *v)
1771 {
1772         BMIter iter;
1773         BMLoop *l;
1774         float accum_shell = 0.0f;
1775         float accum_angle = 0.0f;
1776
1777         BM_ITER_ELEM (l, &iter, (BMVert *)v, BM_LOOPS_OF_VERT) {
1778                 const float face_angle = BM_loop_calc_face_angle(l);
1779                 accum_shell += shell_v3v3_normalized_to_dist(v->no, l->f->no) * face_angle;
1780                 accum_angle += face_angle;
1781         }
1782
1783         if (accum_angle != 0.0f) {
1784                 return accum_shell / accum_angle;
1785         }
1786         else {
1787                 return 1.0f;
1788         }
1789 }
1790 /* alternate version of #BM_vert_calc_shell_factor which only
1791  * uses 'hflag' faces, but falls back to all if none found. */
1792 float BM_vert_calc_shell_factor_ex(const BMVert *v, const float no[3], const char hflag)
1793 {
1794         BMIter iter;
1795         const BMLoop *l;
1796         float accum_shell = 0.0f;
1797         float accum_angle = 0.0f;
1798         int tot_sel = 0, tot = 0;
1799
1800         BM_ITER_ELEM (l, &iter, (BMVert *)v, BM_LOOPS_OF_VERT) {
1801                 if (BM_elem_flag_test(l->f, hflag)) {  /* <-- main difference to BM_vert_calc_shell_factor! */
1802                         const float face_angle = BM_loop_calc_face_angle(l);
1803                         accum_shell += shell_v3v3_normalized_to_dist(no, l->f->no) * face_angle;
1804                         accum_angle += face_angle;
1805                         tot_sel++;
1806                 }
1807                 tot++;
1808         }
1809
1810         if (accum_angle != 0.0f) {
1811                 return accum_shell / accum_angle;
1812         }
1813         else {
1814                 /* other main difference from BM_vert_calc_shell_factor! */
1815                 if (tot != 0 && tot_sel == 0) {
1816                         /* none selected, so use all */
1817                         return BM_vert_calc_shell_factor(v);
1818                 }
1819                 else {
1820                         return 1.0f;
1821                 }
1822         }
1823 }
1824
1825 /**
1826  * \note quite an obscure function.
1827  * used in bmesh operators that have a relative scale options,
1828  */
1829 float BM_vert_calc_mean_tagged_edge_length(const BMVert *v)
1830 {
1831         BMIter iter;
1832         BMEdge *e;
1833         int tot;
1834         float length = 0.0f;
1835
1836         BM_ITER_ELEM_INDEX (e, &iter, (BMVert *)v, BM_EDGES_OF_VERT, tot) {
1837                 const BMVert *v_other = BM_edge_other_vert(e, v);
1838                 if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
1839                         length += BM_edge_calc_length(e);
1840                 }
1841         }
1842
1843         if (tot) {
1844                 return length / (float)tot;
1845         }
1846         else {
1847                 return 0.0f;
1848         }
1849 }
1850
1851
1852 /**
1853  * Returns the loop of the shortest edge in f.
1854  */
1855 BMLoop *BM_face_find_shortest_loop(BMFace *f)
1856 {
1857         BMLoop *shortest_loop = NULL;
1858         float shortest_len = FLT_MAX;
1859
1860         BMLoop *l_iter;
1861         BMLoop *l_first;
1862
1863         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1864
1865         do {
1866                 const float len_sq = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1867                 if (len_sq <= shortest_len) {
1868                         shortest_loop = l_iter;
1869                         shortest_len = len_sq;
1870                 }
1871         } while ((l_iter = l_iter->next) != l_first);
1872
1873         return shortest_loop;
1874 }
1875
1876 /**
1877  * Returns the loop of the longest edge in f.
1878  */
1879 BMLoop *BM_face_find_longest_loop(BMFace *f)
1880 {
1881         BMLoop *longest_loop = NULL;
1882         float len_max_sq = 0.0f;
1883
1884         BMLoop *l_iter;
1885         BMLoop *l_first;
1886
1887         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1888
1889         do {
1890                 const float len_sq = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1891                 if (len_sq >= len_max_sq) {
1892                         longest_loop = l_iter;
1893                         len_max_sq = len_sq;
1894                 }
1895         } while ((l_iter = l_iter->next) != l_first);
1896
1897         return longest_loop;
1898 }
1899
1900 /**
1901  * Returns the edge existing between \a v_a and \a v_b, or NULL if there isn't one.
1902  *
1903  * \note multiple edges may exist between any two vertices, and therefore
1904  * this function only returns the first one found.
1905  */
1906 #if 0
1907 BMEdge *BM_edge_exists(BMVert *v_a, BMVert *v_b)
1908 {
1909         BMIter iter;
1910         BMEdge *e;
1911
1912
1913         BLI_assert(v_a != v_b);
1914         BLI_assert(v_a->head.htype == BM_VERT && v_b->head.htype == BM_VERT);
1915
1916         BM_ITER_ELEM (e, &iter, v_a, BM_EDGES_OF_VERT) {
1917                 if (e->v1 == v_b || e->v2 == v_b)
1918                         return e;
1919         }
1920
1921         return NULL;
1922 }
1923 #else
1924 BMEdge *BM_edge_exists(BMVert *v_a, BMVert *v_b)
1925 {
1926         /* speedup by looping over both edges verts
1927          * where one vert may connect to many edges but not the other. */
1928
1929         BMEdge *e_a, *e_b;
1930
1931         BLI_assert(v_a != v_b);
1932         BLI_assert(v_a->head.htype == BM_VERT && v_b->head.htype == BM_VERT);
1933
1934         if ((e_a = v_a->e) && (e_b = v_b->e)) {
1935                 BMEdge *e_a_iter = e_a, *e_b_iter = e_b;
1936
1937                 do {
1938                         if (BM_vert_in_edge(e_a_iter, v_b)) {
1939                                 return e_a_iter;
1940                         }
1941                         if (BM_vert_in_edge(e_b_iter, v_a)) {
1942                                 return e_b_iter;
1943                         }
1944                 } while (((e_a_iter = bmesh_disk_edge_next(e_a_iter, v_a)) != e_a) &&
1945                          ((e_b_iter = bmesh_disk_edge_next(e_b_iter, v_b)) != e_b));
1946         }
1947
1948         return NULL;
1949 }
1950 #endif
1951
1952 /**
1953  * Returns an edge sharing the same vertices as this one.
1954  * This isn't an invalid state but tools should clean up these cases before
1955  * returning the mesh to the user.
1956  */
1957 BMEdge *BM_edge_find_double(BMEdge *e)
1958 {
1959         BMVert *v       = e->v1;
1960         BMVert *v_other = e->v2;
1961
1962         BMEdge *e_iter;
1963
1964         e_iter = e;
1965         while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e) {
1966                 if (UNLIKELY(BM_vert_in_edge(e_iter, v_other))) {
1967                         return e_iter;
1968                 }
1969         }
1970
1971         return NULL;
1972 }
1973
1974 /**
1975  * Given a set of vertices (varr), find out if
1976  * there is a face with exactly those vertices
1977  * (and only those vertices).
1978  *
1979  * \note there used to be a BM_face_exists_overlap function that checks for partial overlap.
1980  */
1981 BMFace *BM_face_exists(BMVert **varr, int len)
1982 {
1983         if (varr[0]->e) {
1984                 BMEdge *e_iter, *e_first;
1985                 e_iter = e_first = varr[0]->e;
1986
1987                 /* would normally use BM_LOOPS_OF_VERT, but this runs so often,
1988                  * its faster to iterate on the data directly */
1989                 do {
1990                         if (e_iter->l) {
1991                                 BMLoop *l_iter_radial, *l_first_radial;
1992                                 l_iter_radial = l_first_radial = e_iter->l;
1993
1994                                 do {
1995                                         if ((l_iter_radial->v == varr[0]) &&
1996                                             (l_iter_radial->f->len == len))
1997                                         {
1998                                                 /* the fist 2 verts match, now check the remaining (len - 2) faces do too
1999                                                  * winding isn't known, so check in both directions */
2000                                                 int i_walk = 2;
2001
2002                                                 if (l_iter_radial->next->v == varr[1]) {
2003                                                         BMLoop *l_walk = l_iter_radial->next->next;
2004                                                         do {
2005                                                                 if (l_walk->v != varr[i_walk]) {
2006                                                                         break;
2007                                                                 }
2008                                                         } while ((void)(l_walk = l_walk->next), ++i_walk != len);
2009                                                 }
2010                                                 else if (l_iter_radial->prev->v == varr[1]) {
2011                                                         BMLoop *l_walk = l_iter_radial->prev->prev;
2012                                                         do {
2013                                                                 if (l_walk->v != varr[i_walk]) {
2014                                                                         break;
2015                                                                 }
2016                                                         } while ((void)(l_walk = l_walk->prev), ++i_walk != len);
2017                                                 }
2018
2019                                                 if (i_walk == len) {
2020                                                         return l_iter_radial->f;
2021                                                 }
2022                                         }
2023                                 } while ((l_iter_radial = l_iter_radial->radial_next) != l_first_radial);
2024
2025                         }
2026                 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, varr[0])) != e_first);
2027         }
2028
2029         return NULL;
2030 }
2031
2032
2033 /**
2034  * Given a set of vertices and edges (\a varr, \a earr), find out if
2035  * all those vertices are filled in by existing faces that _only_ use those vertices.
2036  *
2037  * This is for use in cases where creating a face is possible but would result in
2038  * many overlapping faces.
2039  *
2040  * An example of how this is used: when 2 tri's are selected that share an edge,
2041  * pressing Fkey would make a new overlapping quad (without a check like this)
2042  *
2043  * \a earr and \a varr can be in any order, however they _must_ form a closed loop.
2044  */
2045 bool BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len)
2046 {
2047         BMFace *f;
2048         BMEdge *e;
2049         BMVert *v;
2050         bool ok;
2051         int tot_tag;
2052
2053         BMIter fiter;
2054         BMIter viter;
2055
2056         int i;
2057
2058         for (i = 0; i < len; i++) {
2059                 /* save some time by looping over edge faces rather then vert faces
2060                  * will still loop over some faces twice but not as many */
2061                 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
2062                         BM_elem_flag_disable(f, BM_ELEM_INTERNAL_TAG);
2063                         BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
2064                                 BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
2065                         }
2066                 }
2067
2068                 /* clear all edge tags */
2069                 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
2070                         BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
2071                 }
2072         }
2073
2074         /* now tag all verts and edges in the boundary array as true so
2075          * we can know if a face-vert is from our array */
2076         for (i = 0; i < len; i++) {
2077                 BM_elem_flag_enable(varr[i], BM_ELEM_INTERNAL_TAG);
2078                 BM_elem_flag_enable(earr[i], BM_ELEM_INTERNAL_TAG);
2079         }
2080
2081
2082         /* so! boundary is tagged, everything else cleared */
2083
2084
2085         /* 1) tag all faces connected to edges - if all their verts are boundary */
2086         tot_tag = 0;
2087         for (i = 0; i < len; i++) {
2088                 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
2089                         if (!BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
2090                                 ok = true;
2091                                 BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
2092                                         if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) {
2093                                                 ok = false;
2094                                                 break;
2095                                         }
2096                                 }
2097
2098                                 if (ok) {
2099                                         /* we only use boundary verts */
2100                                         BM_elem_flag_enable(f, BM_ELEM_INTERNAL_TAG);
2101                                         tot_tag++;
2102                                 }
2103                         }
2104                         else {
2105                                 /* we already found! */
2106                         }
2107                 }
2108         }
2109
2110         if (tot_tag == 0) {
2111                 /* no faces use only boundary verts, quit early */
2112                 ok = false;
2113                 goto finally;
2114         }
2115
2116         /* 2) loop over non-boundary edges that use boundary verts,
2117          *    check each have 2 tagged faces connected (faces that only use 'varr' verts) */
2118         ok = true;
2119         for (i = 0; i < len; i++) {
2120                 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
2121
2122                         if (/* non-boundary edge */
2123                             BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == false &&
2124                             /* ...using boundary verts */
2125                             BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) &&
2126                             BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG))
2127                         {
2128                                 int tot_face_tag = 0;
2129                                 BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
2130                                         if (BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
2131                                                 tot_face_tag++;
2132                                         }
2133                                 }
2134
2135                                 if (tot_face_tag != 2) {
2136                                         ok = false;
2137                                         break;
2138                                 }
2139
2140                         }
2141                 }
2142
2143                 if (ok == false) {
2144                         break;
2145                 }
2146         }
2147
2148 finally:
2149         /* Cleanup */
2150         for (i = 0; i < len; i++) {
2151                 BM_elem_flag_disable(varr[i], BM_ELEM_INTERNAL_TAG);
2152                 BM_elem_flag_disable(earr[i], BM_ELEM_INTERNAL_TAG);
2153         }
2154         return ok;
2155 }
2156
2157 /* same as 'BM_face_exists_multi' but built vert array from edges */
2158 bool BM_face_exists_multi_edge(BMEdge **earr, int len)
2159 {
2160         BMVert **varr = BLI_array_alloca(varr, len);
2161
2162         /* first check if verts have edges, if not we can bail out early */
2163         if (!BM_verts_from_edges(varr, earr, len)) {
2164                 BMESH_ASSERT(0);
2165                 return false;
2166         }
2167
2168         return BM_face_exists_multi(varr, earr, len);
2169 }
2170
2171
2172 /**
2173  * Given a set of vertices (varr), find out if
2174  * all those vertices overlap an existing face.
2175  *
2176  * \note The face may contain other verts \b not in \a varr.
2177  *
2178  * \note Its possible there are more than one overlapping faces,
2179  * in this case the first one found will be returned.
2180  *
2181  * \param varr  Array of unordered verts.
2182  * \param len  \a varr array length.
2183  * \return The face or NULL.
2184  */
2185
2186 BMFace *BM_face_exists_overlap(BMVert **varr, const int len)
2187 {
2188         BMIter viter;
2189         BMFace *f;
2190         int i;
2191         BMFace *f_overlap = NULL;
2192         LinkNode *f_lnk = NULL;
2193
2194 #ifdef DEBUG
2195         /* check flag isn't already set */
2196         for (i = 0; i < len; i++) {
2197                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
2198                         BLI_assert(BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0);
2199                 }
2200         }
2201 #endif
2202
2203         for (i = 0; i < len; i++) {
2204                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
2205                         if (BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0) {
2206                                 if (len <= BM_verts_in_face_count(varr, len, f)) {
2207                                         f_overlap = f;
2208                                         break;
2209                                 }
2210
2211                                 BM_ELEM_API_FLAG_ENABLE(f, _FLAG_OVERLAP);
2212                                 BLI_linklist_prepend_alloca(&f_lnk, f);
2213                         }
2214                 }
2215         }
2216
2217         for (; f_lnk; f_lnk = f_lnk->next) {
2218                 BM_ELEM_API_FLAG_DISABLE((BMFace *)f_lnk->link, _FLAG_OVERLAP);
2219         }
2220
2221         return f_overlap;
2222 }
2223
2224 /**
2225  * Given a set of vertices (varr), find out if
2226  * there is a face that uses vertices only from this list
2227  * (that the face is a subset or made from the vertices given).
2228  *
2229  * \param varr  Array of unordered verts.
2230  * \param len  varr array length.
2231  */
2232 bool BM_face_exists_overlap_subset(BMVert **varr, const int len)
2233 {
2234         BMIter viter;
2235         BMFace *f;
2236         bool is_init = false;
2237         bool is_overlap = false;
2238         LinkNode *f_lnk = NULL;
2239
2240 #ifdef DEBUG
2241         /* check flag isn't already set */
2242         for (int i = 0; i < len; i++) {
2243                 BLI_assert(BM_ELEM_API_FLAG_TEST(varr[i], _FLAG_OVERLAP) == 0);
2244                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
2245                         BLI_assert(BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0);
2246                 }
2247         }
2248 #endif
2249
2250         for (int i = 0; i < len; i++) {
2251                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
2252                         if ((f->len <= len) && (BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0)) {
2253                                 /* check if all vers in this face are flagged*/
2254                                 BMLoop *l_iter, *l_first;
2255
2256                                 if (is_init == false) {
2257                                         is_init = true;
2258                                         for (int j = 0; j < len; j++) {
2259                                                 BM_ELEM_API_FLAG_ENABLE(varr[j], _FLAG_OVERLAP);
2260                                         }
2261                                 }
2262
2263                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2264                                 is_overlap = true;
2265                                 do {
2266                                         if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP) == 0) {
2267                                                 is_overlap = false;
2268                                                 break;
2269                                         }
2270                                 } while ((l_iter = l_iter->next) != l_first);
2271
2272                                 if (is_overlap) {
2273                                         break;
2274                                 }
2275
2276                                 BM_ELEM_API_FLAG_ENABLE(f, _FLAG_OVERLAP);
2277                                 BLI_linklist_prepend_alloca(&f_lnk, f);
2278                         }
2279                 }
2280         }
2281
2282         if (is_init == true) {
2283                 for (int i = 0; i < len; i++) {
2284                         BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
2285                 }
2286         }
2287
2288         for (; f_lnk; f_lnk = f_lnk->next) {
2289                 BM_ELEM_API_FLAG_DISABLE((BMFace *)f_lnk->link, _FLAG_OVERLAP);
2290         }
2291
2292         return is_overlap;
2293 }
2294
2295 bool BM_vert_is_all_edge_flag_test(const BMVert *v, const char hflag, const bool respect_hide)
2296 {
2297         if (v->e) {
2298                 BMEdge *e_other;
2299                 BMIter eiter;
2300
2301                 BM_ITER_ELEM (e_other, &eiter, (BMVert *)v, BM_EDGES_OF_VERT) {
2302                         if (!respect_hide || !BM_elem_flag_test(e_other, BM_ELEM_HIDDEN)) {
2303                                 if (!BM_elem_flag_test(e_other, hflag)) {
2304                                         return false;
2305                                 }
2306                         }
2307                 }
2308         }
2309
2310         return true;
2311 }
2312
2313 bool BM_vert_is_all_face_flag_test(const BMVert *v, const char hflag, const bool respect_hide)
2314 {
2315         if (v->e) {
2316                 BMEdge *f_other;
2317                 BMIter fiter;
2318
2319                 BM_ITER_ELEM (f_other, &fiter, (BMVert *)v, BM_FACES_OF_VERT) {
2320                         if (!respect_hide || !BM_elem_flag_test(f_other, BM_ELEM_HIDDEN)) {
2321                                 if (!BM_elem_flag_test(f_other, hflag)) {
2322                                         return false;
2323                                 }
2324                         }
2325                 }
2326         }
2327
2328         return true;
2329 }
2330
2331
2332 bool BM_edge_is_all_face_flag_test(const BMEdge *e, const char hflag, const bool respect_hide)
2333 {
2334         if (e->l) {
2335                 BMLoop *l_iter, *l_first;
2336
2337                 l_iter = l_first = e->l;
2338                 do {
2339                         if (!respect_hide || !BM_elem_flag_test(l_iter->f, BM_ELEM_HIDDEN)) {
2340                                 if (!BM_elem_flag_test(l_iter->f, hflag)) {
2341                                         return false;
2342                                 }
2343                         }
2344                 } while ((l_iter = l_iter->radial_next) != l_first);
2345         }
2346
2347         return true;
2348 }
2349
2350 /* convenience functions for checking flags */
2351 bool BM_edge_is_any_vert_flag_test(const BMEdge *e, const char hflag)
2352 {
2353         return (BM_elem_flag_test(e->v1, hflag) ||
2354                 BM_elem_flag_test(e->v2, hflag));
2355 }
2356
2357 bool BM_face_is_any_vert_flag_test(const BMFace *f, const char hflag)
2358 {
2359         BMLoop *l_iter;
2360         BMLoop *l_first;
2361
2362         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2363         do {
2364                 if (BM_elem_flag_test(l_iter->v, hflag)) {
2365                         return true;
2366                 }
2367         } while ((l_iter = l_iter->next) != l_first);
2368         return false;
2369 }
2370
2371 bool BM_face_is_any_edge_flag_test(const BMFace *f, const char hflag)
2372 {
2373         BMLoop *l_iter;
2374         BMLoop *l_first;
2375
2376         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2377         do {
2378                 if (BM_elem_flag_test(l_iter->e, hflag)) {
2379                         return true;
2380                 }
2381         } while ((l_iter = l_iter->next) != l_first);
2382         return false;
2383 }
2384
2385 /**
2386  * Use within assert's to check normals are valid.
2387  */
2388 bool BM_face_is_normal_valid(const BMFace *f)
2389 {
2390         const float eps = 0.0001f;
2391         float no[3];
2392
2393         BM_face_calc_normal(f, no);
2394         return len_squared_v3v3(no, f->no) < (eps * eps);
2395 }
2396
2397 static void bm_mesh_calc_volume_face(const BMFace *f, float *r_vol)
2398 {
2399         const int tottri = f->len - 2;
2400         BMLoop **loops = BLI_array_alloca(loops, f->len);
2401         uint (*index)[3] = BLI_array_alloca(index, tottri);
2402         int j;
2403
2404         BM_face_calc_tessellation(f, false, loops, index);
2405
2406         for (j = 0; j < tottri; j++) {
2407                 const float *p1 = loops[index[j][0]]->v->co;
2408                 const float *p2 = loops[index[j][1]]->v->co;
2409                 const float *p3 = loops[index[j][2]]->v->co;
2410
2411                 /* co1.dot(co2.cross(co3)) / 6.0 */
2412                 float cross[3];
2413                 cross_v3_v3v3(cross, p2, p3);
2414                 *r_vol += (1.0f / 6.0f) * dot_v3v3(p1, cross);
2415         }
2416 }
2417 float BM_mesh_calc_volume(BMesh *bm, bool is_signed)
2418 {
2419         /* warning, calls own tessellation function, may be slow */
2420         float vol = 0.0f;
2421         BMFace *f;
2422         BMIter fiter;
2423
2424         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
2425                 bm_mesh_calc_volume_face(f, &vol);
2426         }
2427
2428         if (is_signed == false) {
2429                 vol = fabsf(vol);
2430         }
2431
2432         return vol;
2433 }
2434
2435 /* note, almost duplicate of BM_mesh_calc_edge_groups, keep in sync */
2436 /**
2437  * Calculate isolated groups of faces with optional filtering.
2438  *
2439  * \param bm  the BMesh.
2440  * \param r_groups_array  Array of ints to fill in, length of bm->totface
2441  *        (or when hflag_test is set, the number of flagged faces).
2442  * \param r_group_index  index, length pairs into \a r_groups_array, size of return value
2443  *        int pairs: (array_start, array_length).
2444  * \param filter_fn  Filter the edge-loops or vert-loops we step over (depends on \a htype_step).
2445  * \param user_data  Optional user data for \a filter_fn, can be NULL.
2446  * \param hflag_test  Optional flag to test faces,
2447  *        use to exclude faces from the calculation, 0 for all faces.
2448  * \param htype_step  BM_VERT to walk over face-verts, BM_EDGE to walk over faces edges
2449  *        (having both set is supported too).
2450  * \return The number of groups found.
2451  */
2452 int BM_mesh_calc_face_groups(
2453         BMesh *bm, int *r_groups_array, int (**r_group_index)[2],
2454         BMLoopFilterFunc filter_fn, void *user_data,
2455         const char hflag_test, const char htype_step)
2456 {
2457 #ifdef DEBUG
2458         int group_index_len = 1;
2459 #else
2460         int group_index_len = 32;
2461 #endif
2462
2463         int (*group_index)[2] = MEM_mallocN(sizeof(*group_index) * group_index_len, __func__);
2464
2465         int *group_array = r_groups_array;
2466         STACK_DECLARE(group_array);
2467
2468         int group_curr = 0;
2469
2470         uint tot_faces = 0;
2471         uint tot_touch = 0;
2472
2473         BMFace **stack;
2474         STACK_DECLARE(stack);
2475
2476         BMIter iter;
2477         BMFace *f;
2478         int i;
2479
2480         STACK_INIT(group_array, bm->totface);
2481
2482         BLI_assert(((htype_step & ~(BM_VERT | BM_EDGE)) == 0) && (htype_step != 0));
2483
2484         /* init the array */
2485         BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
2486                 if ((hflag_test == 0) || BM_elem_flag_test(f, hflag_test)) {
2487                         tot_faces++;
2488                         BM_elem_flag_disable(f, BM_ELEM_TAG);
2489                 }
2490                 else {
2491                         /* never walk over tagged */
2492                         BM_elem_flag_enable(f, BM_ELEM_TAG);
2493                 }
2494
2495                 BM_elem_index_set(f, i); /* set_inline */
2496         }
2497         bm->elem_index_dirty &= ~BM_FACE;
2498
2499         /* detect groups */
2500         stack = MEM_mallocN(sizeof(*stack) * tot_faces, __func__);
2501
2502         while (tot_touch != tot_faces) {
2503                 int *group_item;
2504                 bool ok = false;
2505
2506                 BLI_assert(tot_touch < tot_faces);
2507
2508                 STACK_INIT(stack, tot_faces);
2509
2510                 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
2511                         if (BM_elem_flag_test(f, BM_ELEM_TAG) == false) {
2512                                 BM_elem_flag_enable(f, BM_ELEM_TAG);
2513                                 STACK_PUSH(stack, f);
2514                                 ok = true;
2515                                 break;
2516                         }
2517                 }
2518
2519                 BLI_assert(ok == true);
2520                 UNUSED_VARS_NDEBUG(ok);
2521
2522                 /* manage arrays */
2523                 if (group_index_len == group_curr) {
2524                         group_index_len *= 2;
2525                         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_index_len);
2526                 }
2527
2528                 group_item = group_index[group_curr];
2529                 group_item[0] = STACK_SIZE(group_array);
2530                 group_item[1] = 0;
2531
2532                 while ((f = STACK_POP(stack))) {
2533                         BMLoop *l_iter, *l_first;
2534
2535                         /* add face */
2536                         STACK_PUSH(group_array, BM_elem_index_get(f));
2537                         tot_touch++;
2538                         group_item[1]++;
2539                         /* done */
2540
2541                         if (htype_step & BM_EDGE) {
2542                                 /* search for other faces */
2543                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2544                                 do {
2545                                         BMLoop *l_radial_iter = l_iter->radial_next;
2546                                         if ((l_radial_iter != l_iter) &&
2547                                             ((filter_fn == NULL) || filter_fn(l_iter, user_data)))
2548                                         {
2549                                                 do {
2550                                                         BMFace *f_other = l_radial_iter->f;
2551                                                         if (BM_elem_flag_test(f_other, BM_ELEM_TAG) == false) {
2552                                                                 BM_elem_flag_enable(f_other, BM_ELEM_TAG);
2553                                                                 STACK_PUSH(stack, f_other);
2554                                                         }
2555                                                 } while ((l_radial_iter = l_radial_iter->radial_next) != l_iter);
2556                                         }
2557                                 } while ((l_iter = l_iter->next) != l_first);
2558                         }
2559
2560                         if (htype_step & BM_VERT) {
2561                                 BMIter liter;
2562                                 /* search for other faces */
2563                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2564                                 do {
2565                                         if ((filter_fn == NULL) || filter_fn(l_iter, user_data)) {
2566                                                 BMLoop *l_other;
2567                                                 BM_ITER_ELEM (l_other, &liter, l_iter, BM_LOOPS_OF_LOOP) {
2568                                                         BMFace *f_other = l_other->f;
2569                                                         if (BM_elem_flag_test(f_other, BM_ELEM_TAG) == false) {
2570                                                                 BM_elem_flag_enable(f_other, BM_ELEM_TAG);
2571                                                                 STACK_PUSH(stack, f_other);
2572                                                         }
2573                                                 }
2574                                         }
2575                                 } while ((l_iter = l_iter->next) != l_first);
2576                         }
2577                 }
2578
2579                 group_curr++;
2580         }
2581
2582         MEM_freeN(stack);
2583
2584         /* reduce alloc to required size */
2585         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_curr);
2586         *r_group_index = group_index;
2587
2588         return group_curr;
2589 }
2590
2591 /* note, almost duplicate of BM_mesh_calc_face_groups, keep in sync */
2592 /**
2593  * Calculate isolated groups of edges with optional filtering.
2594  *
2595  * \param bm  the BMesh.
2596  * \param r_groups_array  Array of ints to fill in, length of bm->totedge
2597  *        (or when hflag_test is set, the number of flagged edges).
2598  * \param r_group_index  index, length pairs into \a r_groups_array, size of return value
2599  *        int pairs: (array_start, array_length).
2600  * \param filter_fn  Filter the edges or verts we step over (depends on \a htype_step)
2601  *        as to which types we deal with.
2602  * \param user_data  Optional user data for \a filter_fn, can be NULL.
2603  * \param hflag_test  Optional flag to test edges,
2604  *        use to exclude edges from the calculation, 0 for all edges.
2605  * \return The number of groups found.
2606  *
2607  * \note Unlike #BM_mesh_calc_face_groups there is no 'htype_step' argument,
2608  *       since we always walk over verts.
2609  */
2610 int BM_mesh_calc_edge_groups(
2611         BMesh *bm, int *r_groups_array, int (**r_group_index)[2],
2612         BMVertFilterFunc filter_fn, void *user_data,
2613         const char hflag_test)
2614 {
2615 #ifdef DEBUG
2616         int group_index_len = 1;
2617 #else
2618         int group_index_len = 32;
2619 #endif
2620
2621         int (*group_index)[2] = MEM_mallocN(sizeof(*group_index) * group_index_len, __func__);
2622
2623         int *group_array = r_groups_array;
2624         STACK_DECLARE(group_array);
2625
2626         int group_curr = 0;
2627
2628         uint tot_edges = 0;
2629         uint tot_touch = 0;
2630
2631         BMEdge **stack;
2632         STACK_DECLARE(stack);
2633
2634         BMIter iter;
2635         BMEdge *e;
2636         int i;
2637
2638         STACK_INIT(group_array, bm->totedge);
2639
2640         /* init the array */
2641         BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
2642                 if ((hflag_test == 0) || BM_elem_flag_test(e, hflag_test)) {
2643                         tot_edges++;
2644                         BM_elem_flag_disable(e, BM_ELEM_TAG);
2645                 }
2646                 else {
2647                         /* never walk over tagged */
2648                         BM_elem_flag_enable(e, BM_ELEM_TAG);
2649                 }
2650
2651                 BM_elem_index_set(e, i); /* set_inline */
2652         }
2653         bm->elem_index_dirty &= ~BM_EDGE;
2654
2655         /* detect groups */
2656         stack = MEM_mallocN(sizeof(*stack) * tot_edges, __func__);
2657
2658         while (tot_touch != tot_edges) {
2659                 int *group_item;
2660                 bool ok = false;
2661
2662                 BLI_assert(tot_touch < tot_edges);
2663
2664                 STACK_INIT(stack, tot_edges);
2665
2666                 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
2667                         if (BM_elem_flag_test(e, BM_ELEM_TAG) == false) {
2668                                 BM_elem_flag_enable(e, BM_ELEM_TAG);
2669                                 STACK_PUSH(stack, e);
2670                                 ok = true;
2671                                 break;
2672                         }
2673                 }
2674
2675                 BLI_assert(ok == true);
2676                 UNUSED_VARS_NDEBUG(ok);
2677
2678                 /* manage arrays */
2679                 if (group_index_len == group_curr) {
2680                         group_index_len *= 2;
2681                         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_index_len);
2682                 }
2683
2684                 group_item = group_index[group_curr];
2685                 group_item[0] = STACK_SIZE(group_array);
2686                 group_item[1] = 0;
2687
2688                 while ((e = STACK_POP(stack))) {
2689                         BMIter viter;
2690                         BMIter eiter;
2691                         BMVert *v;
2692
2693                         /* add edge */
2694                         STACK_PUSH(group_array, BM_elem_index_get(e));
2695                         tot_touch++;
2696                         group_item[1]++;
2697                         /* done */
2698
2699                         /* search for other edges */
2700                         BM_ITER_ELEM (v, &viter, e, BM_VERTS_OF_EDGE) {
2701                                 if ((filter_fn == NULL) || filter_fn(v, user_data)) {
2702                                         BMEdge *e_other;
2703                                         BM_ITER_ELEM (e_other, &eiter, v, BM_EDGES_OF_VERT) {
2704                                                 if (BM_elem_flag_test(e_other, BM_ELEM_TAG) == false) {
2705                                                         BM_elem_flag_enable(e_other, BM_ELEM_TAG);
2706                                                         STACK_PUSH(stack, e_other);
2707                                                 }
2708                                         }
2709                                 }
2710                         }
2711                 }
2712
2713                 group_curr++;
2714         }
2715
2716         MEM_freeN(stack);
2717
2718         /* reduce alloc to required size */
2719         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_curr);
2720         *r_group_index = group_index;
2721
2722         return group_curr;
2723 }
2724
2725 float bmesh_subd_falloff_calc(const int falloff, float val)
2726 {
2727         switch (falloff) {
2728                 case SUBD_FALLOFF_SMOOTH:
2729                         val = 3.0f * val * val - 2.0f * val * val * val;
2730                         break;
2731                 case SUBD_FALLOFF_SPHERE:
2732                         val = sqrtf(2.0f * val - val * val);
2733                         break;
2734                 case SUBD_FALLOFF_ROOT:
2735                         val = sqrtf(val);
2736                         break;
2737                 case SUBD_FALLOFF_SHARP:
2738                         val = val * val;
2739                         break;
2740                 case SUBD_FALLOFF_LIN:
2741                         break;
2742                 case SUBD_FALLOFF_INVSQUARE:
2743                         val = val * (2.0f - val);
2744                         break;
2745                 default:
2746                         BLI_assert(0);
2747                         break;
2748         }
2749
2750         return val;
2751 }