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