BMesh: add check to BM_vert_pair_share_face to allow adjacent loops

Add BM_vert_pair_share_face_by_angle to avoid selecting concave splits.

3 files changed, 92 insertions, 9 deletions

diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c
index 67f333215d9..61e1a15c605 100644
--- a/source/blender/bmesh/intern/bmesh_queries.c
+++ b/source/blender/bmesh/intern/bmesh_queries.c
@@ -184,8 +184,10 @@ BMLoop *BM_loop_other_vert_loop(BMLoop *l, BMVert *v)
 /**
  * Given 2 verts, find the smallest face they share and give back both loops.
  */
-BMFace *BM_vert_pair_share_face(BMVert *v_a, BMVert *v_b,
-                                BMLoop **r_l_a, BMLoop **r_l_b)
+BMFace *BM_vert_pair_share_face_by_len(
+        BMVert *v_a, BMVert *v_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;
@@ -197,7 +199,7 @@ BMFace *BM_vert_pair_share_face(BMVert *v_a, BMVert *v_b,
 		BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
 			if ((f_cur == NULL) || (l_a->f->len < f_cur->len)) {
 				l_b = BM_face_vert_share_loop(l_a->f, v_b);
-				if (l_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;
@@ -206,12 +208,80 @@ BMFace *BM_vert_pair_share_face(BMVert *v_a, BMVert *v_b,
 		}
 	}
 
-	if (r_l_a) *r_l_a = l_cur_a;
-	if (r_l_b) *r_l_b = l_cur_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];
+
+	if ((BM_face_calc_normal_subset(l_a, l_b, no[0]) != 0.0f) &&
+	    (BM_face_calc_normal_subset(l_b, l_a, no[1]) != 0.0f))
+	{
+		return dot_v3v3(no[0], no[1]);
+	}
+	else {
+		return -1.0f;
+	}
+}
+
+/**
+ * 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.
+ */
+BMFace *BM_vert_pair_share_face_by_angle(
+        BMVert *v_a, BMVert *v_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 (v_a->e && v_b->e) {
+		BMIter iter;
+		BMLoop *l_a, *l_b;
+		float dot_best = -1.0f;
+
+		BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
+			l_b = BM_face_vert_share_loop(l_a->f, v_b);
+			if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
+
+				if (f_cur == NULL) {
+					f_cur = l_a->f;
+					l_cur_a = l_a;
+					l_cur_b = l_b;
+				}
+				else {
+					/* avoid expensive calculations if we only ever find one face */
+					float dot;
+					if (dot_best == -1.0f) {
+						dot_best = bm_face_calc_split_dot(l_cur_a, l_cur_b);
+					}
+
+					dot = bm_face_calc_split_dot(l_a, l_b);
+					if (dot > dot_best) {
+						dot_best = dot;
+
+						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;
+}
+
+
 /**
  * Get the first loop of a vert. Uses the same initialization code for the first loop of the
  * iterator API
diff --git a/source/blender/bmesh/intern/bmesh_queries.h b/source/blender/bmesh/intern/bmesh_queries.h
index 36e67a73f1f..7db04a529eb 100644
--- a/source/blender/bmesh/intern/bmesh_queries.h
+++ b/source/blender/bmesh/intern/bmesh_queries.h
@@ -49,8 +49,15 @@ BMLoop *BM_face_other_vert_loop(BMFace *f, BMVert *v_prev, BMVert *v);
 BMLoop *BM_loop_other_vert_loop(BMLoop *l, BMVert *v);
 BMLoop *BM_vert_step_fan_loop(BMLoop *l, BMEdge **e_step);
 BMLoop *BM_vert_find_first_loop(BMVert *v);
-BMFace *BM_vert_pair_share_face(BMVert *v_a, BMVert *v_b,
-                                BMLoop **r_l_a, BMLoop **r_l_b);
+
+BMFace *BM_vert_pair_share_face_by_len(
+        BMVert *v_a, BMVert *v_b,
+        BMLoop **r_l_a, BMLoop **r_l_b,
+        const bool allow_adjacent) ATTR_NONNULL();
+BMFace *BM_vert_pair_share_face_by_angle(
+        BMVert *v_a, BMVert *v_b,
+        BMLoop **r_l_a, BMLoop **r_l_b,
+        const bool allow_adjacent) ATTR_NONNULL();
 
 int     BM_vert_edge_count_nonwire(BMVert *v);
 int     BM_vert_edge_count(BMVert *v);
diff --git a/source/blender/bmesh/operators/bmo_subdivide.c b/source/blender/bmesh/operators/bmo_subdivide.c
index e0c86564db4..8d948fbcc69 100644
--- a/source/blender/bmesh/operators/bmo_subdivide.c
+++ b/source/blender/bmesh/operators/bmo_subdivide.c
@@ -140,13 +140,19 @@ static BMEdge *connect_smallest_face(BMesh *bm, BMVert *v_a, BMVert *v_b, BMFace
 
 	/* this isn't the best thing in the world.  it doesn't handle cases where there's
 	 * multiple faces yet.  that might require a convexity test to figure out which
-	 * face is "best" and who knows what for non-manifold conditions. */
-	f = BM_vert_pair_share_face(v_a, v_b, &l_a, &l_b);
+	 * face is "best" and who knows what for non-manifold conditions.
+	 *
+	 * note: we allow adjacent here, since theres no chance this happens.
+	 */
+	f = BM_vert_pair_share_face_by_len(v_a, v_b, &l_a, &l_b, true);
+
 
 	if (f) {
 		BMFace *f_new;
 		BMLoop *l_new;
 
+		BLI_assert(!BM_loop_is_adjacent(l_a, l_b));
+
 		f_new = BM_face_split(bm, f, l_a, l_b, &l_new, NULL, false);
 		
 		if (r_f_new) *r_f_new = f_new;