1 files changed, 446 insertions, 152 deletions

diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c
index 685e5443583..1a8ea1e3a0d 100644
--- a/source/blender/bmesh/intern/bmesh_queries.c
+++ b/source/blender/bmesh/intern/bmesh_queries.c
@@ -38,6 +38,8 @@
 #include "BLI_linklist.h"
 #include "BLI_stackdefines.h"
 
+#include "BKE_customdata.h"
+
 #include "bmesh.h"
 #include "intern/bmesh_private.h"
 
@@ -193,7 +195,7 @@ bool BM_vert_pair_share_face_check(
 		BMFace *f;
 
 		BM_ITER_ELEM (f, &iter, v_a, BM_FACES_OF_VERT) {
-			if (BM_vert_in_face(f, v_b)) {
+			if (BM_vert_in_face(v_b, f)) {
 				return true;
 			}
 		}
@@ -202,6 +204,26 @@ bool BM_vert_pair_share_face_check(
 	return false;
 }
 
+bool BM_vert_pair_share_face_check_cb(
+        BMVert *v_a, BMVert *v_b,
+        bool (*test_fn)(BMFace *, void *user_data), void *user_data)
+{
+	if (v_a->e && v_b->e) {
+		BMIter iter;
+		BMFace *f;
+
+		BM_ITER_ELEM (f, &iter, v_a, BM_FACES_OF_VERT) {
+			if (test_fn(f, user_data)) {
+				if (BM_vert_in_face(v_b, f)) {
+					return true;
+				}
+			}
+		}
+	}
+
+	return false;
+}
+
 /**
  * Given 2 verts, find the smallest face they share and give back both loops.
  */
@@ -235,6 +257,36 @@ BMFace *BM_vert_pair_share_face_by_len(
 	return f_cur;
 }
 
+BMFace *BM_edge_pair_share_face_by_len(
+        BMEdge *e_a, BMEdge *e_b,
+        BMLoop **r_l_a, BMLoop **r_l_b,
+        const bool allow_adjacent)
+{
+	BMLoop *l_cur_a = NULL, *l_cur_b = NULL;
+	BMFace *f_cur = NULL;
+
+	if (e_a->l && e_b->l) {
+		BMIter iter;
+		BMLoop *l_a, *l_b;
+
+		BM_ITER_ELEM (l_a, &iter, e_a, BM_LOOPS_OF_EDGE) {
+			if ((f_cur == NULL) || (l_a->f->len < f_cur->len)) {
+				l_b = BM_face_edge_share_loop(l_a->f, e_b);
+				if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
+					f_cur = l_a->f;
+					l_cur_a = l_a;
+					l_cur_b = l_b;
+				}
+			}
+		}
+	}
+
+	*r_l_a = l_cur_a;
+	*r_l_b = l_cur_b;
+
+	return f_cur;
+}
+
 static float bm_face_calc_split_dot(BMLoop *l_a, BMLoop *l_b)
 {
 	float no[2][3];
@@ -250,6 +302,37 @@ static float bm_face_calc_split_dot(BMLoop *l_a, BMLoop *l_b)
 }
 
 /**
+ * Check if a point is inside the corner defined by a loop
+ * (within the 2 planes defined by the loops corner & face normal).
+ *
+ * \return signed, squared distance to the loops planes, less than 0.0 when outside.
+ */
+float BM_loop_point_side_of_loop_test(const BMLoop *l, const float co[3])
+{
+	const float *axis = l->f->no;
+	return dist_signed_squared_to_corner_v3v3v3(co, l->prev->v->co, l->v->co, l->next->v->co, axis);
+}
+
+/**
+ * Check if a point is inside the edge defined by a loop
+ * (within the plane defined by the loops edge & face normal).
+ *
+ * \return signed, squared distance to the edge plane, less than 0.0 when outside.
+ */
+float BM_loop_point_side_of_edge_test(const BMLoop *l, const float co[3])
+{
+	const float *axis = l->f->no;
+	float dir[3];
+	float plane[4];
+
+	sub_v3_v3v3(dir, l->next->v->co, l->v->co);
+	cross_v3_v3v3(plane, axis, dir);
+
+	plane[3] = -dot_v3v3(plane, l->v->co);
+	return dist_signed_squared_to_plane_v3(co, plane);
+}
+
+/**
  * Given 2 verts, find a face they share that has the lowest angle across these verts and give back both loops.
  *
  * This can be better then #BM_vert_pair_share_face_by_len because concave splits are ranked lowest.
@@ -311,7 +394,7 @@ BMLoop *BM_vert_find_first_loop(BMVert *v)
 {
 	BMEdge *e;
 
-	if (!v || !v->e)
+	if (!v->e)
 		return NULL;
 
 	e = bmesh_disk_faceedge_find_first(v->e, v);
@@ -325,7 +408,7 @@ BMLoop *BM_vert_find_first_loop(BMVert *v)
 /**
  * Returns true if the vertex is used in a given face.
  */
-bool BM_vert_in_face(BMFace *f, BMVert *v)
+bool BM_vert_in_face(BMVert *v, BMFace *f)
 {
 	BMLoop *l_iter, *l_first;
 
@@ -353,7 +436,7 @@ bool BM_vert_in_face(BMFace *f, BMVert *v)
  * Compares the number of vertices in an array
  * that appear in a given face
  */
-int BM_verts_in_face_count(BMFace *f, BMVert **varr, int len)
+int BM_verts_in_face_count(BMVert **varr, int len, BMFace *f)
 {
 	BMLoop *l_iter, *l_first;
 
@@ -397,7 +480,7 @@ int BM_verts_in_face_count(BMFace *f, BMVert **varr, int len)
 /**
  * Return true if all verts are in the face.
  */
-bool BM_verts_in_face(BMFace *f, BMVert **varr, int len)
+bool BM_verts_in_face(BMVert **varr, int len, BMFace *f)
 {
 	BMLoop *l_iter, *l_first;
 
@@ -448,12 +531,12 @@ bool BM_verts_in_face(BMFace *f, BMVert **varr, int len)
 }
 
 /**
- * Returns whether or not a given edge is is part of a given face.
+ * Returns whether or not a given edge is part of a given face.
  */
-bool BM_edge_in_face(BMEdge *e, BMFace *f)
+bool BM_edge_in_face(const BMEdge *e, const BMFace *f)
 {
 	if (e->l) {
-		BMLoop *l_iter, *l_first;
+		const BMLoop *l_iter, *l_first;
 
 		l_iter = l_first = e->l;
 		do {
@@ -613,7 +696,7 @@ BMEdge *BM_vert_other_disk_edge(BMVert *v, BMEdge *e_first)
 /**
  * Returns edge length
  */
-float BM_edge_calc_length(BMEdge *e)
+float BM_edge_calc_length(const BMEdge *e)
 {
 	return len_v3v3(e->v1->co, e->v2->co);
 }
@@ -621,7 +704,7 @@ float BM_edge_calc_length(BMEdge *e)
 /**
  * Returns edge length squared (for comparisons)
  */
-float BM_edge_calc_length_squared(BMEdge *e)
+float BM_edge_calc_length_squared(const BMEdge *e)
 {
 	return len_squared_v3v3(e->v1->co, e->v2->co);
 }
@@ -681,9 +764,9 @@ bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
 /**
  * Fast alternative to ``(BM_vert_edge_count(v) == 2)``
  */
-bool BM_vert_is_edge_pair(BMVert *v)
+bool BM_vert_is_edge_pair(const BMVert *v)
 {
-	BMEdge *e = v->e;
+	const BMEdge *e = v->e;
 	if (e) {
 		const BMDiskLink *dl = bmesh_disk_edge_link_from_vert(e, v);
 		return (dl->next == dl->prev);
@@ -694,17 +777,22 @@ bool BM_vert_is_edge_pair(BMVert *v)
 /**
  *	Returns the number of edges around this vertex.
  */
-int BM_vert_edge_count(BMVert *v)
+int BM_vert_edge_count(const BMVert *v)
 {
 	return bmesh_disk_count(v);
 }
 
-int BM_vert_edge_count_nonwire(BMVert *v)
+int BM_vert_edge_count_ex(const BMVert *v, const int count_max)
+{
+	return bmesh_disk_count_ex(v, count_max);
+}
+
+int BM_vert_edge_count_nonwire(const BMVert *v)
 {
 	int count = 0;
 	BMIter eiter;
 	BMEdge *edge;
-	BM_ITER_ELEM (edge, &eiter, v, BM_EDGES_OF_VERT) {
+	BM_ITER_ELEM (edge, &eiter, (BMVert *)v, BM_EDGES_OF_VERT) {
 		if (edge->l) {
 			count++;
 		}
@@ -714,18 +802,35 @@ int BM_vert_edge_count_nonwire(BMVert *v)
 /**
  *	Returns the number of faces around this edge
  */
-int BM_edge_face_count(BMEdge *e)
+int BM_edge_face_count(const BMEdge *e)
 {
 	int count = 0;
 
 	if (e->l) {
-		BMLoop *l_iter;
-		BMLoop *l_first;
+		BMLoop *l_iter, *l_first;
 
 		l_iter = l_first = e->l;
+		do {
+			count++;
+		} while ((l_iter = l_iter->radial_next) != l_first);
+	}
+
+	return count;
+}
+
+int BM_edge_face_count_ex(const BMEdge *e, const int count_max)
+{
+	int count = 0;
+
+	if (e->l) {
+		BMLoop *l_iter, *l_first;
 
+		l_iter = l_first = e->l;
 		do {
 			count++;
+			if (count == count_max) {
+				break;
+			}
 		} while ((l_iter = l_iter->radial_next) != l_first);
 	}
 
@@ -736,11 +841,26 @@ int BM_edge_face_count(BMEdge *e)
  * Returns the number of faces around this vert
  * length matches #BM_LOOPS_OF_VERT iterator
  */
-int BM_vert_face_count(BMVert *v)
+int BM_vert_face_count(const BMVert *v)
 {
 	return bmesh_disk_facevert_count(v);
 }
 
+int BM_vert_face_count_ex(const BMVert *v, int count_max)
+{
+	return bmesh_disk_facevert_count_ex(v, count_max);
+}
+
+/**
+ * Return true if the vertex is connected to _any_ faces.
+ *
+ * same as ``BM_vert_face_count(v) != 0`` or ``BM_vert_find_first_loop(v) == NULL``
+ */
+bool BM_vert_face_check(BMVert *v)
+{
+	return v->e && (bmesh_disk_faceedge_find_first(v->e, v) != NULL);
+}
+
 /**
  * Tests whether or not the vertex is part of a wire edge.
  * (ie: has no faces attached to it)
@@ -773,9 +893,9 @@ bool BM_vert_is_wire(const BMVert *v)
  */
 bool BM_vert_is_manifold(const BMVert *v)
 {
-	BMEdge *e, *e_old;
-	BMLoop *l;
-	int len, count, flag;
+	BMEdge *e_iter, *e_first, *e_prev;
+	BMLoop *l_iter, *l_first;
+	int loop_num = 0, loop_num_region = 0, boundary_num = 0;
 
 	if (v->e == NULL) {
 		/* loose vert */
@@ -783,50 +903,150 @@ bool BM_vert_is_manifold(const BMVert *v)
 	}
 
 	/* count edges while looking for non-manifold edges */
-	len = 0;
-	e_old = e = v->e;
+	e_first = e_iter = v->e;
+	l_first = e_iter->l ? e_iter->l : NULL;
 	do {
 		/* loose edge or edge shared by more than two faces,
 		 * edges with 1 face user are OK, otherwise we could
 		 * use BM_edge_is_manifold() here */
-		if (e->l == NULL || bmesh_radial_length(e->l) > 2) {
+		if (e_iter->l == NULL || (e_iter->l != e_iter->l->radial_next->radial_next)) {
 			return false;
 		}
-		len++;
-	} while ((e = bmesh_disk_edge_next(e, v)) != e_old);
-
-	count = 1;
-	flag = 1;
-	e = NULL;
-	e_old = v->e;
-	l = e_old->l;
-	while (e != e_old) {
-		l = (l->v == v) ? l->prev : l->next;
-		e = l->e;
-		count++; /* count the edges */
-
-		if (flag && l->radial_next == l) {
-			/* we've hit the edge of an open mesh, reset once */
-			flag = 0;
-			count = 1;
-			e_old = e;
-			e = NULL;
-			l = e_old->l;
-		}
-		else if (l->radial_next == l) {
-			/* break the loop */
-			e = e_old;
+
+		/* count radial loops */
+		if (e_iter->l->v == v) {
+			loop_num += 1;
+		}
+
+		if (!BM_edge_is_boundary(e_iter)) {
+			/* non boundary check opposite loop */
+			if (e_iter->l->radial_next->v == v) {
+				loop_num += 1;
+			}
+		}
+		else {
+			/* start at the boundary */
+			l_first = e_iter->l;
+			boundary_num += 1;
+			/* >2 boundaries cant be manifold */
+			if (boundary_num == 3) {
+				return false;
+			}
+		}
+	} while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
+
+	e_first = l_first->e;
+	l_first = (l_first->v == v) ? l_first : l_first->next;
+	BLI_assert(l_first->v == v);
+
+	l_iter = l_first;
+	e_prev = e_first;
+
+	do {
+		loop_num_region += 1;
+	} while (((l_iter = BM_vert_step_fan_loop(l_iter, &e_prev)) != l_first) && (l_iter != NULL));
+
+	return (loop_num == loop_num_region);
+}
+
+#define LOOP_VISIT _FLAG_WALK
+#define EDGE_VISIT _FLAG_WALK
+
+static int bm_loop_region_count__recursive(BMEdge *e, BMVert *v)
+{
+	BMLoop *l_iter, *l_first;
+	int count = 0;
+
+	BLI_assert(!BM_ELEM_API_FLAG_TEST(e, EDGE_VISIT));
+	BM_ELEM_API_FLAG_ENABLE(e, EDGE_VISIT);
+
+	l_iter = l_first = e->l;
+	do {
+		if (l_iter->v == v) {
+			BMEdge *e_other = l_iter->prev->e;
+			if (!BM_ELEM_API_FLAG_TEST(l_iter, LOOP_VISIT)) {
+				BM_ELEM_API_FLAG_ENABLE(l_iter, LOOP_VISIT);
+				count += 1;
+			}
+			if (!BM_ELEM_API_FLAG_TEST(e_other, EDGE_VISIT)) {
+				count += bm_loop_region_count__recursive(e_other, v);
+			}
+		}
+		else if (l_iter->next->v == v) {
+			BMEdge *e_other = l_iter->next->e;
+			if (!BM_ELEM_API_FLAG_TEST(l_iter->next, LOOP_VISIT)) {
+				BM_ELEM_API_FLAG_ENABLE(l_iter->next, LOOP_VISIT);
+				count += 1;
+			}
+			if (!BM_ELEM_API_FLAG_TEST(e_other, EDGE_VISIT)) {
+				count += bm_loop_region_count__recursive(e_other, v);
+			}
 		}
 		else {
-			l = l->radial_next;
+			BLI_assert(0);
 		}
-	}
+	} while ((l_iter = l_iter->radial_next) != l_first);
 
-	if (count < len) {
-		/* vert shared by multiple regions */
-		return false;
+	return count;
+}
+
+static int bm_loop_region_count__clear(BMLoop *l)
+{
+	int count = 0;
+	BMEdge *e_iter, *e_first;
+
+	/* clear flags */
+	e_iter = e_first = l->e;
+	do {
+		BM_ELEM_API_FLAG_DISABLE(e_iter, EDGE_VISIT);
+		if (e_iter->l) {
+			BMLoop *l_iter, *l_first;
+			l_iter = l_first = e_iter->l;
+			do {
+				if (l_iter->v == l->v) {
+					BM_ELEM_API_FLAG_DISABLE(l_iter, LOOP_VISIT);
+					count += 1;
+				}
+			} while ((l_iter = l_iter->radial_next) != l_first);
+		}
+	} while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, l->v)) != e_first);
+
+	return count;
+}
+
+/**
+ * The number of loops connected to this loop (not including disconnected regions).
+ */
+int BM_loop_region_loops_count_ex(BMLoop *l, int *r_loop_total)
+{
+	const int count       = bm_loop_region_count__recursive(l->e, l->v);
+	const int count_total = bm_loop_region_count__clear(l);
+	if (r_loop_total) {
+		*r_loop_total = count_total;
 	}
+	return count;
+}
+
+#undef LOOP_VISIT
+#undef EDGE_VISIT
 
+int BM_loop_region_loops_count(BMLoop *l)
+{
+	return BM_loop_region_loops_count_ex(l, NULL);
+}
+
+/**
+ * A version of #BM_vert_is_manifold
+ * which only checks if we're connected to multiple isolated regions.
+ */
+bool BM_vert_is_manifold_region(const BMVert *v)
+{
+	BMLoop *l_first = BM_vert_find_first_loop((BMVert *)v);
+	if (l_first) {
+		int count, count_total;
+		count = BM_loop_region_loops_count_ex(l_first, &count_total);
+		return (count == count_total);
+	}
 	return true;
 }
 
@@ -851,6 +1071,53 @@ bool BM_edge_is_convex(const BMEdge *e)
 	return true;
 }
 
+/**
+ * \return true when loop customdata is contiguous.
+ */
+bool BM_edge_is_contiguous_loop_cd(
+        const BMEdge *e,
+        const int cd_loop_type, const int cd_loop_offset)
+{
+	BLI_assert(cd_loop_offset != -1);
+
+	if (e->l && e->l->radial_next != e->l) {
+		const BMLoop *l_base_v1 = e->l;
+		const BMLoop *l_base_v2 = e->l->next;
+		const void *l_base_cd_v1 = BM_ELEM_CD_GET_VOID_P(l_base_v1, cd_loop_offset);
+		const void *l_base_cd_v2 = BM_ELEM_CD_GET_VOID_P(l_base_v2, cd_loop_offset);
+		const BMLoop *l_iter = e->l->radial_next;
+		do {
+			const BMLoop *l_iter_v1;
+			const BMLoop *l_iter_v2;
+			const void *l_iter_cd_v1;
+			const void *l_iter_cd_v2;
+
+			if (l_iter->v == l_base_v1->v) {
+				l_iter_v1 = l_iter;
+				l_iter_v2 = l_iter->next;
+			}
+			else {
+				l_iter_v1 = l_iter->next;
+				l_iter_v2 = l_iter;
+			}
+			BLI_assert((l_iter_v1->v == l_base_v1->v) &&
+			           (l_iter_v2->v == l_base_v2->v));
+
+			l_iter_cd_v1 = BM_ELEM_CD_GET_VOID_P(l_iter_v1, cd_loop_offset);
+			l_iter_cd_v2 = BM_ELEM_CD_GET_VOID_P(l_iter_v2, cd_loop_offset);
+
+
+			if ((CustomData_data_equals(cd_loop_type, l_base_cd_v1, l_iter_cd_v1) == 0) ||
+			    (CustomData_data_equals(cd_loop_type, l_base_cd_v2, l_iter_cd_v2) == 0))
+			{
+				return false;
+			}
+
+		} while ((l_iter = l_iter->radial_next) != e->l);
+	}
+	return true;
+}
+
 bool BM_vert_is_boundary(const BMVert *v)
 {
 	if (v->e) {
@@ -1096,8 +1363,9 @@ BMLoop *BM_face_edge_share_loop(BMFace *f, BMEdge *e)
  * \note This is in fact quite a simple check, mainly include this function so the intent is more obvious.
  * We know these 2 verts will _always_ make up the loops edge
  */
-void BM_edge_ordered_verts_ex(const BMEdge *edge, BMVert **r_v1, BMVert **r_v2,
-                              const BMLoop *edge_loop)
+void BM_edge_ordered_verts_ex(
+        const BMEdge *edge, BMVert **r_v1, BMVert **r_v2,
+        const BMLoop *edge_loop)
 {
 	BLI_assert(edge_loop->e == edge);
 	(void)edge; /* quiet warning in release build */
@@ -1111,6 +1379,46 @@ void BM_edge_ordered_verts(const BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
 }
 
 /**
+ * \return The previous loop, over \a eps_sq distance from \a l (or \a NULL if l_stop is reached).
+ */
+BMLoop *BM_loop_find_prev_nodouble(BMLoop *l, BMLoop *l_stop, const float eps_sq)
+{
+	BMLoop *l_step = l->prev;
+
+	BLI_assert(!ELEM(l_stop, NULL, l));
+
+	while (UNLIKELY(len_squared_v3v3(l->v->co, l_step->v->co) < eps_sq)) {
+		l_step = l_step->prev;
+		BLI_assert(l_step != l);
+		if (UNLIKELY(l_step == l_stop)) {
+			return NULL;
+		}
+	}
+
+	return l_step;
+}
+
+/**
+ * \return The next loop, over \a eps_sq distance from \a l (or \a NULL if l_stop is reached).
+ */
+BMLoop *BM_loop_find_next_nodouble(BMLoop *l, BMLoop *l_stop, const float eps_sq)
+{
+	BMLoop *l_step = l->next;
+
+	BLI_assert(!ELEM(l_stop, NULL, l));
+
+	while (UNLIKELY(len_squared_v3v3(l->v->co, l_step->v->co) < eps_sq)) {
+		l_step = l_step->next;
+		BLI_assert(l_step != l);
+		if (UNLIKELY(l_step == l_stop)) {
+			return NULL;
+		}
+	}
+
+	return l_step;
+}
+
+/**
  * Check if the loop is convex or concave
  * (depends on face normal)
  */
@@ -1132,7 +1440,7 @@ bool BM_loop_is_convex(const BMLoop *l)
  *
  * \return angle in radians
  */
-float BM_loop_calc_face_angle(BMLoop *l)
+float BM_loop_calc_face_angle(const BMLoop *l)
 {
 	return angle_v3v3v3(l->prev->v->co,
 	                    l->v->co,
@@ -1147,7 +1455,7 @@ float BM_loop_calc_face_angle(BMLoop *l)
  * \param l The loop to calculate the normal at
  * \param r_normal Resulting normal
  */
-void BM_loop_calc_face_normal(BMLoop *l, float r_normal[3])
+void BM_loop_calc_face_normal(const BMLoop *l, float r_normal[3])
 {
 	if (normal_tri_v3(r_normal,
 	                  l->prev->v->co,
@@ -1169,7 +1477,7 @@ void BM_loop_calc_face_normal(BMLoop *l, float r_normal[3])
  * \param l The loop to calculate the direction at
  * \param r_dir Resulting direction
  */
-void BM_loop_calc_face_direction(BMLoop *l, float r_dir[3])
+void BM_loop_calc_face_direction(const BMLoop *l, float r_dir[3])
 {
 	float v_prev[3];
 	float v_next[3];
@@ -1193,7 +1501,7 @@ void BM_loop_calc_face_direction(BMLoop *l, float r_dir[3])
  * \param l The loop to calculate the tangent at
  * \param r_tangent Resulting tangent
  */
-void BM_loop_calc_face_tangent(BMLoop *l, float r_tangent[3])
+void BM_loop_calc_face_tangent(const BMLoop *l, float r_tangent[3])
 {
 	float v_prev[3];
 	float v_next[3];
@@ -1305,7 +1613,7 @@ void BM_edge_calc_face_tangent(const BMEdge *e, const BMLoop *e_loop, float r_ta
  *
  * \returns the angle in radians
  */
-float BM_vert_calc_edge_angle(BMVert *v)
+float BM_vert_calc_edge_angle_ex(const BMVert *v, const float fallback)
 {
 	BMEdge *e1, *e2;
 
@@ -1323,22 +1631,27 @@ float BM_vert_calc_edge_angle(BMVert *v)
 		return (float)M_PI - angle_v3v3v3(v1->co, v->co, v2->co);
 	}
 	else {
-		return DEG2RADF(90.0f);
+		return fallback;
 	}
 }
 
+float BM_vert_calc_edge_angle(const BMVert *v)
+{
+	return BM_vert_calc_edge_angle_ex(v, DEG2RADF(90.0f));
+}
+
 /**
  * \note this isn't optimal to run on an array of verts,
  * see 'solidify_add_thickness' for a function which runs on an array.
  */
-float BM_vert_calc_shell_factor(BMVert *v)
+float BM_vert_calc_shell_factor(const BMVert *v)
 {
 	BMIter iter;
 	BMLoop *l;
 	float accum_shell = 0.0f;
 	float accum_angle = 0.0f;
 
-	BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
+	BM_ITER_ELEM (l, &iter, (BMVert *)v, BM_LOOPS_OF_VERT) {
 		const float face_angle = BM_loop_calc_face_angle(l);
 		accum_shell += shell_v3v3_normalized_to_dist(v->no, l->f->no) * face_angle;
 		accum_angle += face_angle;
@@ -1353,18 +1666,18 @@ float BM_vert_calc_shell_factor(BMVert *v)
 }
 /* alternate version of #BM_vert_calc_shell_factor which only
  * uses 'hflag' faces, but falls back to all if none found. */
-float BM_vert_calc_shell_factor_ex(BMVert *v, const char hflag)
+float BM_vert_calc_shell_factor_ex(const BMVert *v, const float no[3], const char hflag)
 {
 	BMIter iter;
-	BMLoop *l;
+	const BMLoop *l;
 	float accum_shell = 0.0f;
 	float accum_angle = 0.0f;
 	int tot_sel = 0, tot = 0;
 
-	BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
+	BM_ITER_ELEM (l, &iter, (BMVert *)v, BM_LOOPS_OF_VERT) {
 		if (BM_elem_flag_test(l->f, hflag)) {  /* <-- main difference to BM_vert_calc_shell_factor! */
 			const float face_angle = BM_loop_calc_face_angle(l);
-			accum_shell += shell_v3v3_normalized_to_dist(v->no, l->f->no) * face_angle;
+			accum_shell += shell_v3v3_normalized_to_dist(no, l->f->no) * face_angle;
 			accum_angle += face_angle;
 			tot_sel++;
 		}
@@ -1390,15 +1703,15 @@ float BM_vert_calc_shell_factor_ex(BMVert *v, const char hflag)
  * \note quite an obscure function.
  * used in bmesh operators that have a relative scale options,
  */
-float BM_vert_calc_mean_tagged_edge_length(BMVert *v)
+float BM_vert_calc_mean_tagged_edge_length(const BMVert *v)
 {
 	BMIter iter;
 	BMEdge *e;
 	int tot;
 	float length = 0.0f;
 
-	BM_ITER_ELEM_INDEX (e, &iter, v, BM_EDGES_OF_VERT, tot) {
-		BMVert *v_other = BM_edge_other_vert(e, v);
+	BM_ITER_ELEM_INDEX (e, &iter, (BMVert *)v, BM_EDGES_OF_VERT, tot) {
+		const BMVert *v_other = BM_edge_other_vert(e, v);
 		if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
 			length += BM_edge_calc_length(e);
 		}
@@ -1544,85 +1857,59 @@ BMEdge *BM_edge_find_double(BMEdge *e)
  */
 bool BM_face_exists(BMVert **varr, int len, BMFace **r_existface)
 {
-	BMVert *v_search = varr[0];  /* we can search any of the verts in the array */
-	BMIter liter;
-	BMLoop *l_search;
-
-
-#if 0
-	BM_ITER_ELEM (f, &viter, v_search, BM_FACES_OF_VERT) {
-		if (f->len == len) {
-			if (BM_verts_in_face(f, varr, len)) {
-				if (r_existface) {
-					*r_existface = f;
-				}
-				return true;
-			}
-		}
-	}
-
-	if (r_existface) {
-		*r_existface = NULL;
-	}
-	return false;
-
-#else
-
-	/* faster to do the flagging once, and inline */
-	bool is_init = false;
-	bool is_found = false;
-	int i;
-
-
-	BM_ITER_ELEM (l_search, &liter, v_search, BM_LOOPS_OF_VERT) {
-		if (l_search->f->len == len) {
-			if (is_init == false) {
-				is_init = true;
-				for (i = 0; i < len; i++) {
-					BLI_assert(!BM_ELEM_API_FLAG_TEST(varr[i], _FLAG_OVERLAP));
-					BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
-				}
-			}
-
-			is_found = true;
-
-			{
-				BMLoop *l_iter;
+	if (varr[0]->e) {
+		BMEdge *e_iter, *e_first;
+		e_iter = e_first = varr[0]->e;
 
-				/* skip ourselves */
-				l_iter  = l_search->next;
+		/* would normally use BM_LOOPS_OF_VERT, but this runs so often,
+		 * its faster to iterate on the data directly */
+		do {
+			if (e_iter->l) {
+				BMLoop *l_iter_radial, *l_first_radial;
+				l_iter_radial = l_first_radial = e_iter->l;
 
 				do {
-					if (!BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
-						is_found = false;
-						break;
+					if ((l_iter_radial->v == varr[0]) &&
+					    (l_iter_radial->f->len == len))
+					{
+						/* the fist 2 verts match, now check the remaining (len - 2) faces do too
+						 * winding isn't known, so check in both directions */
+						int i_walk = 2;
+
+						if (l_iter_radial->next->v == varr[1]) {
+							BMLoop *l_walk = l_iter_radial->next->next;
+							do {
+								if (l_walk->v != varr[i_walk]) {
+									break;
+								}
+							} while ((l_walk = l_walk->next), ++i_walk != len);
+						}
+						else if (l_iter_radial->prev->v == varr[1]) {
+							BMLoop *l_walk = l_iter_radial->prev->prev;
+							do {
+								if (l_walk->v != varr[i_walk]) {
+									break;
+								}
+							} while ((l_walk = l_walk->prev), ++i_walk != len);
+						}
+
+						if (i_walk == len) {
+							if (r_existface) {
+								*r_existface = l_iter_radial->f;
+							}
+							return true;
+						}
 					}
-				} while ((l_iter = l_iter->next) != l_search);
-			}
+				} while ((l_iter_radial = l_iter_radial->radial_next) != l_first_radial);
 
-			if (is_found) {
-				if (r_existface) {
-					*r_existface = l_search->f;
-				}
-				break;
 			}
-		}
-	}
-
-	if (is_found == false) {
-		if (r_existface) {
-			*r_existface = NULL;
-		}
+		} while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, varr[0])) != e_first);
 	}
 
-	if (is_init == true) {
-		for (i = 0; i < len; i++) {
-			BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
-		}
+	if (r_existface) {
+		*r_existface = NULL;
 	}
-
-	return is_found;
-#endif
+	return false;
 }
 
 
@@ -1717,8 +2004,8 @@ bool BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len)
 			if (/* non-boundary edge */
 			    BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == false &&
 			    /* ...using boundary verts */
-			    BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) == true &&
-			    BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG) == true)
+			    BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) &&
+			    BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG))
 			{
 				int tot_face_tag = 0;
 				BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
@@ -1777,7 +2064,7 @@ bool BM_face_exists_multi_edge(BMEdge **earr, int len)
  *
  * \note The face may contain other verts \b not in \a varr.
  *
- * \note Its possible there are more then one overlapping faces,
+ * \note Its possible there are more than one overlapping faces,
  * in this case the first one found will be assigned to \a r_f_overlap.
  *
  * \param varr  Array of unordered verts.
@@ -1810,7 +2097,7 @@ bool BM_face_exists_overlap(BMVert **varr, const int len, BMFace **r_f_overlap)
 	for (i = 0; i < len; i++) {
 		BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
 			if (BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0) {
-				if (len <= BM_verts_in_face_count(f, varr, len)) {
+				if (len <= BM_verts_in_face_count(varr, len, f)) {
 					if (r_f_overlap)
 						*r_f_overlap = f;
 
@@ -2061,9 +2348,10 @@ float BM_mesh_calc_volume(BMesh *bm, bool is_signed)
  *        (having both set is supported too).
  * \return The number of groups found.
  */
-int BM_mesh_calc_face_groups(BMesh *bm, int *r_groups_array, int (**r_group_index)[2],
-                             BMElemFilterFunc filter_fn, void *user_data,
-                             const char hflag_test, const char htype_step)
+int BM_mesh_calc_face_groups(
+        BMesh *bm, int *r_groups_array, int (**r_group_index)[2],
+        BMElemFilterFunc filter_fn, void *user_data,
+        const char hflag_test, const char htype_step)
 {
 #ifdef DEBUG
 	int group_index_len = 1;
@@ -2128,6 +2416,7 @@ int BM_mesh_calc_face_groups(BMesh *bm, int *r_groups_array, int (**r_group_inde
 		}
 
 		BLI_assert(ok == true);
+		UNUSED_VARS_NDEBUG(ok);
 
 		/* manage arrays */
 		if (group_index_len == group_curr) {
@@ -2217,9 +2506,10 @@ int BM_mesh_calc_face_groups(BMesh *bm, int *r_groups_array, int (**r_group_inde
  * \note Unlike #BM_mesh_calc_face_groups there is no 'htype_step' argument,
  *       since we always walk over verts.
  */
-int BM_mesh_calc_edge_groups(BMesh *bm, int *r_groups_array, int (**r_group_index)[2],
-                             BMElemFilterFunc filter_fn, void *user_data,
-                             const char hflag_test)
+int BM_mesh_calc_edge_groups(
+        BMesh *bm, int *r_groups_array, int (**r_group_index)[2],
+        BMElemFilterFunc filter_fn, void *user_data,
+        const char hflag_test)
 {
 #ifdef DEBUG
 	int group_index_len = 1;
@@ -2244,7 +2534,7 @@ int BM_mesh_calc_edge_groups(BMesh *bm, int *r_groups_array, int (**r_group_inde
 	BMEdge *e;
 	int i;
 
-	STACK_INIT(group_array, bm->totface);
+	STACK_INIT(group_array, bm->totedge);
 
 	/* init the array */
 	BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
@@ -2282,6 +2572,7 @@ int BM_mesh_calc_edge_groups(BMesh *bm, int *r_groups_array, int (**r_group_inde
 		}
 
 		BLI_assert(ok == true);
+		UNUSED_VARS_NDEBUG(ok);
 
 		/* manage arrays */
 		if (group_index_len == group_curr) {
@@ -2347,6 +2638,9 @@ float bmesh_subd_falloff_calc(const int falloff, float val)
 			break;
 		case SUBD_FALLOFF_LIN:
 			break;
+		case SUBD_FALLOFF_INVSQUARE:
+			val = val * (2.0f - val);
+			break;
 		default:
 			BLI_assert(0);
 			break;