BMesh optimize face splitting by taking loops rather then verts

- add BM_vert_pair_share_face
- add BM_loop_is_adjacent
- remove BM_verts_connect

8 files changed, 138 insertions, 110 deletions

diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c
index cbaffe2da1a..7b3ca898718 100644
--- a/source/blender/bmesh/intern/bmesh_core.c
+++ b/source/blender/bmesh/intern/bmesh_core.c
@@ -1258,7 +1258,7 @@ static BMFace *bm_face_create__sfme(BMesh *bm, BMFace *UNUSED(example))
  *
  * \return A BMFace pointer
  */
-BMFace *bmesh_sfme(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2,
+BMFace *bmesh_sfme(BMesh *bm, BMFace *f, BMLoop *l_v1, BMLoop *l_v2,
                    BMLoop **r_l,
 #ifdef USE_BMESH_HOLES
                    ListBase *holes,
@@ -1275,21 +1275,12 @@ BMFace *bmesh_sfme(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2,
 
 	BMFace *f2;
 	BMLoop *l_iter, *l_first;
-	BMLoop *l_v1 = NULL, *l_v2 = NULL, *l_f1 = NULL, *l_f2 = NULL;
+	BMLoop *l_f1 = NULL, *l_f2 = NULL;
 	BMEdge *e;
-	int i, len, f1len, f2len;
+	BMVert *v1 = l_v1->v, *v2 = l_v2->v;
+	int f1len, f2len;
 
-	/* verify that v1 and v2 are in face */
-	len = f->len;
-	for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f); i < len; i++, l_iter = l_iter->next) {
-		if (l_iter->v == v1) l_v1 = l_iter;
-		else if (l_iter->v == v2) l_v2 = l_iter;
-	}
-
-	if (!l_v1 || !l_v2) {
-		BLI_assert(0);
-		return NULL;
-	}
+	BLI_assert(f == l_v1->f && f == l_v2->f);
 
 	/* allocate new edge between v1 and v2 */
 	e = BM_edge_create(bm, v1, v2, example, no_double ? BM_CREATE_NO_DOUBLE : BM_CREATE_NOP);
diff --git a/source/blender/bmesh/intern/bmesh_core.h b/source/blender/bmesh/intern/bmesh_core.h
index e9fd4e650cb..654698da3c6 100644
--- a/source/blender/bmesh/intern/bmesh_core.h
+++ b/source/blender/bmesh/intern/bmesh_core.h
@@ -72,14 +72,15 @@ void    BM_vert_separate(BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len
                          BMEdge **e_in, int e_in_len);
 
 /* EULER API - For modifying structure */
-BMFace *bmesh_sfme(BMesh *bm, BMFace *f, BMVert *v1,
-                          BMVert *v2, BMLoop **r_l,
+BMFace *bmesh_sfme(BMesh *bm, BMFace *f,
+                   BMLoop *l1, BMLoop *l2,
+                   BMLoop **r_l,
 #ifdef USE_BMESH_HOLES
-                          ListBase *holes,
+                   ListBase *holes,
 #endif
-                          BMEdge *example,
-                          const bool no_double
-                          );
+                   BMEdge *example,
+                   const bool no_double
+                   );
 
 BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **r_e);
 BMEdge *bmesh_jekv(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool check_edge_splice);
diff --git a/source/blender/bmesh/intern/bmesh_mods.c b/source/blender/bmesh/intern/bmesh_mods.c
index 49c8c987956..6d8dc531a32 100644
--- a/source/blender/bmesh/intern/bmesh_mods.c
+++ b/source/blender/bmesh/intern/bmesh_mods.c
@@ -252,48 +252,6 @@ BMFace *BM_faces_join_pair(BMesh *bm, BMFace *f_a, BMFace *f_b, BMEdge *e, const
 }
 
 /**
- * \brief Connect Verts, Split Face
- *
- * connects two verts together, automatically (if very naively) finding the
- * face they both share (if there is one) and splitting it.  Use this at your
- * own risk, as it doesn't handle the many complex cases it should (like zero-area faces,
- * multiple faces, etc).
- *
- * this is really only meant for cases where you don't know before hand the face
- * the two verts belong to for splitting (e.g. the subdivision operator).
- *
- * \return The newly created edge.
- */
-BMEdge *BM_verts_connect(BMesh *bm, BMVert *v1, BMVert *v2, BMFace **r_f)
-{
-	BMIter fiter;
-	BMIter viter;
-	BMVert *v_iter;
-	BMFace *f_iter;
-
-	/* be warned: this can do weird things in some ngon situation, see BM_face_legal_splits */
-	BM_ITER_ELEM (f_iter, &fiter, v1, BM_FACES_OF_VERT) {
-		BM_ITER_ELEM (v_iter, &viter, f_iter, BM_FACES_OF_VERT) {
-			if (v_iter == v2) {
-				BMLoop *l_new;
-
-				f_iter = BM_face_split(bm, f_iter, v1, v2, &l_new, NULL, false);
-
-				if (r_f) {
-					*r_f = f_iter;
-				}
-				return l_new->e;
-			}
-		}
-	}
-
-	if (r_f) {
-		*r_f = NULL;
-	}
-	return NULL;
-}
-
-/**
  * \brief Face Split
  *
  * Split a face along two vertices. returns the newly made face, and sets
@@ -310,13 +268,26 @@ BMEdge *BM_verts_connect(BMesh *bm, BMVert *v1, BMVert *v2, BMFace **r_f)
  * if the split is successful (and the original original face will be the
  * other side). NULL if the split fails.
  */
-BMFace *BM_face_split(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, BMLoop **r_l,
-                      BMEdge *example, const bool no_double)
+BMFace *BM_face_split(BMesh *bm, BMFace *f,
+                      BMLoop *l_a, BMLoop *l_b,
+                      BMLoop **r_l, BMEdge *example,
+                      const bool no_double)
 {
 	const bool has_mdisp = CustomData_has_layer(&bm->ldata, CD_MDISPS);
 	BMFace *f_new, *f_tmp;
 
-	BLI_assert(v1 != v2);
+	BLI_assert(l_a != l_b);
+	BLI_assert(f == l_a->f && f == l_b->f);
+	BLI_assert(!BM_loop_is_adjacent(l_a, l_b));
+
+	/* could be an assert */
+	if (UNLIKELY(BM_loop_is_adjacent(l_a, l_b))) {
+		return NULL;
+	}
+
+	if (f != l_a->f || f != l_b->f) {
+		return NULL;
+	}
 
 	/* do we have a multires layer? */
 	if (has_mdisp) {
@@ -324,9 +295,9 @@ BMFace *BM_face_split(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, BMLoop **r_l
 	}
 	
 #ifdef USE_BMESH_HOLES
-	f_new = bmesh_sfme(bm, f, v1, v2, r_l, NULL, example, no_double);
+	f_new = bmesh_sfme(bm, f, l_a, l_b, r_l, NULL, example, no_double);
 #else
-	f_new = bmesh_sfme(bm, f, v1, v2, r_l, example, no_double);
+	f_new = bmesh_sfme(bm, f, l_a, l_b, r_l, example, no_double);
 #endif
 	
 	if (f_new) {
@@ -369,7 +340,7 @@ BMFace *BM_face_split(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, BMLoop **r_l
  *
  * \param bm The bmesh
  * \param f the original face
- * \param v1, v2 vertices which define the split edge, must be different
+ * \param l_a, l_b vertices which define the split edge, must be different
  * \param cos Array of coordinates for intermediate points
  * \param n Length of \a cos (must be > 0)
  * \param r_l pointer which will receive the BMLoop for the first split edge (from \a v1) in the new face
@@ -379,16 +350,31 @@ BMFace *BM_face_split(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, BMLoop **r_l
  * if the split is successful (and the original original face will be the
  * other side). NULL if the split fails.
  */
-BMFace *BM_face_split_n(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, float cos[][3], int n,
+BMFace *BM_face_split_n(BMesh *bm, BMFace *f,
+                        BMLoop *l_a, BMLoop *l_b,
+                        float cos[][3], int n,
                         BMLoop **r_l, BMEdge *example)
 {
 	BMFace *f_new, *f_tmp;
 	BMLoop *l_dummy;
 	BMEdge *e, *e_new;
 	BMVert *v_new;
+	// BMVert *v_a = l_a->v; /* UNUSED */
+	BMVert *v_b = l_b->v;
 	int i, j;
 
-	BLI_assert(v1 != v2);
+	BLI_assert(l_a != l_b);
+	BLI_assert(f == l_a->f && f == l_b->f);
+	BLI_assert(!BM_loop_is_adjacent(l_a, l_b));
+
+	/* could be an assert */
+	if (UNLIKELY(BM_loop_is_adjacent(l_a, l_b))) {
+		return NULL;
+	}
+
+	if (l_a->f != l_b->f) {
+		return NULL;
+	}
 
 	f_tmp = BM_face_copy(bm, bm, f, true, true);
 
@@ -396,12 +382,12 @@ BMFace *BM_face_split_n(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, float cos[
 		r_l = &l_dummy;
 	
 #ifdef USE_BMESH_HOLES
-	f_new = bmesh_sfme(bm, f, v1, v2, r_l, NULL, example, false);
+	f_new = bmesh_sfme(bm, f, l_a, l_b, r_l, NULL, example, false);
 #else
-	f_new = bmesh_sfme(bm, f, v1, v2, r_l, example, false);
+	f_new = bmesh_sfme(bm, f, l_a, l_b, r_l, example, false);
 #endif
-	/* bmesh_sfme returns in r_l a Loop for f_new going from v1 to v2.
-	 * The radial_next is for f and goes from v2 to v1  */
+	/* bmesh_sfme returns in r_l a Loop for f_new going from v_a to v_b.
+	 * The radial_next is for f and goes from v_b to v_a  */
 
 	if (f_new) {
 		BM_elem_attrs_copy(bm, bm, f, f_new);
@@ -409,7 +395,7 @@ BMFace *BM_face_split_n(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, float cos[
 
 		e = (*r_l)->e;
 		for (i = 0; i < n; i++) {
-			v_new = bmesh_semv(bm, v2, e, &e_new);
+			v_new = bmesh_semv(bm, v_b, e, &e_new);
 			BLI_assert(v_new != NULL);
 			/* bmesh_semv returns in e_new the edge going from v_new to tv */
 			copy_v3_v3(v_new->co, cos[i]);
@@ -510,8 +496,14 @@ BMEdge *BM_vert_collapse_faces(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, float
 			BMFace *f2 = BM_faces_join(bm, faces, BLI_array_count(faces), true);
 			if (f2) {
 				BMLoop *l_new = NULL;
-				if (BM_face_split(bm, f2, tv, tv2, &l_new, NULL, false)) {
-					e_new = l_new->e;
+				BMLoop *l_a, *l_b;
+
+				if ((l_a = BM_face_vert_share_loop(f2, tv)) &&
+				    (l_b = BM_face_vert_share_loop(f2, tv2)))
+				{
+					if (BM_face_split(bm, f2, l_a, l_b, &l_new, NULL, false)) {
+						e_new = l_new->e;
+					}
 				}
 			}
 		}
@@ -1058,10 +1050,10 @@ BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const bool ccw, const short check_f
 	/* note, this assumes joining the faces _didnt_ also remove the verts.
 	 * the #BM_edge_rotate_check will ensure this, but its possibly corrupt state or future edits
 	 * break this */
-	if (!BM_face_split(bm, f, v1, v2, NULL, NULL, true)) {
-		return NULL;
-	}
-	else {
+	if ((l1 = BM_face_vert_share_loop(f, v1)) &&
+	    (l2 = BM_face_vert_share_loop(f, v2)) &&
+	    BM_face_split(bm, f, l1, l2, NULL, NULL, true))
+	{
 		/* we should really be able to know the faces some other way,
 		 * rather then fetching them back from the edge, but this is predictable
 		 * where using the return values from face split isn't. - campbell */
@@ -1071,6 +1063,9 @@ BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const bool ccw, const short check_f
 			fb->head.hflag = f_hflag_prev_2;
 		}
 	}
+	else {
+		return NULL;
+	}
 
 	return e_new;
 }
diff --git a/source/blender/bmesh/intern/bmesh_mods.h b/source/blender/bmesh/intern/bmesh_mods.h
index ca281c13f21..f3ed99230d7 100644
--- a/source/blender/bmesh/intern/bmesh_mods.h
+++ b/source/blender/bmesh/intern/bmesh_mods.h
@@ -35,15 +35,13 @@ bool BM_disk_dissolve(BMesh *bm, BMVert *v);
 
 BMFace *BM_faces_join_pair(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e, const bool do_del);
 
-BMEdge *BM_verts_connect(BMesh *bm, BMVert *v1, BMVert *v2, BMFace **r_f);
-
 BMFace *BM_face_split(BMesh *bm, BMFace *f,
-                      BMVert *v1, BMVert *v2,
+                      BMLoop *l_a, BMLoop *l_b,
                       BMLoop **r_l,
                       BMEdge *example, const bool no_double);
 
 BMFace *BM_face_split_n(BMesh *bm, BMFace *f,
-                        BMVert *v1, BMVert *v2,
+                        BMLoop *l_a, BMLoop *l_b,
                         float cos[][3], int n,
                         BMLoop **r_l, BMEdge *example);
 
diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index 7a625840891..a3aaea9e257 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -800,67 +800,67 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
 	BLI_assert((r_faces_new == NULL) == (r_faces_new_tot == NULL));
 
 	if (f->len == 4) {
-		BMVert *v1, *v2;
+		BMLoop *l_v1, *l_v2;
 		l_first = BM_FACE_FIRST_LOOP(f);
 
 		switch (quad_method) {
 			case MOD_TRIANGULATE_QUAD_FIXED:
 			{
-				v1 = l_first->v;
-				v2 = l_first->next->next->v;
+				l_v1 = l_first;
+				l_v2 = l_first->next->next;
 				break;
 			}
 			case MOD_TRIANGULATE_QUAD_ALTERNATE:
 			{
-				v1 = l_first->next->v;
-				v2 = l_first->prev->v;
+				l_v1 = l_first->next;
+				l_v2 = l_first->prev;
 				break;
 			}
 			case MOD_TRIANGULATE_QUAD_SHORTEDGE:
 			{
-				BMVert *v3, *v4;
+				BMLoop *l_v3, *l_v4;
 				float d1, d2;
 
-				v1 = l_first->v;
-				v2 = l_first->next->next->v;
-				v3 = l_first->next->v;
-				v4 = l_first->prev->v;
+				l_v1 = l_first;
+				l_v2 = l_first->next->next;
+				l_v3 = l_first->next;
+				l_v4 = l_first->prev;
 
-				d1 = len_squared_v3v3(v1->co, v2->co);
-				d2 = len_squared_v3v3(v3->co, v4->co);
+				d1 = len_squared_v3v3(l_v1->v->co, l_v2->v->co);
+				d2 = len_squared_v3v3(l_v3->v->co, l_v4->v->co);
 
 				if (d2 < d1) {
-					v1 = v3;
-					v2 = v4;
+					l_v1 = l_v3;
+					l_v2 = l_v4;
 				}
 				break;
 			}
 			case MOD_TRIANGULATE_QUAD_BEAUTY:
 			default:
 			{
-				BMVert *v3, *v4;
+				BMLoop *l_v3, *l_v4;
 				float cost;
 
-				v1 = l_first->next->v;
-				v2 = l_first->next->next->v;
-				v3 = l_first->prev->v;
-				v4 = l_first->v;
+				l_v1 = l_first->next;
+				l_v2 = l_first->next->next;
+				l_v3 = l_first->prev;
+				l_v4 = l_first;
 
-				cost = BM_verts_calc_rotate_beauty(v1, v2, v3, v4, 0, 0);
+				cost = BM_verts_calc_rotate_beauty(l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0);
 
 				if (cost < 0.0f) {
-					v1 = v4;
-					//v2 = v2;
+					l_v1 = l_v4;
+					//l_v2 = l_v2;
 				}
 				else {
-					//v1 = v1;
-					v2 = v3;
+					//l_v1 = l_v1;
+					l_v2 = l_v3;
 				}
 				break;
 			}
 		}
 
-		f_new = BM_face_split(bm, f, v1, v2, &l_new, NULL, false);
+		f_new = BM_face_split(bm, f, l_v1, l_v2, &l_new, NULL, false);
 		copy_v3_v3(f_new->no, f->no);
 
 		if (use_tag) {
diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c
index 16785778883..968ca5f3102 100644
--- a/source/blender/bmesh/intern/bmesh_queries.c
+++ b/source/blender/bmesh/intern/bmesh_queries.c
@@ -182,6 +182,37 @@ 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)
+{
+	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;
+
+		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) {
+					f_cur = l_a->f;
+					l_cur_a = l_a;
+					l_cur_b = l_b;
+				}
+			}
+		}
+	}
+
+	if (r_l_a) *r_l_a = l_cur_a;
+	if (r_l_b) *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 17c14310191..d4b6cd0e061 100644
--- a/source/blender/bmesh/intern/bmesh_queries.h
+++ b/source/blender/bmesh/intern/bmesh_queries.h
@@ -49,6 +49,8 @@ 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);
 
 int     BM_vert_edge_count_nonwire(BMVert *v);
 int     BM_vert_edge_count(BMVert *v);
@@ -67,6 +69,7 @@ BLI_INLINE bool    BM_edge_is_contiguous(const BMEdge *e);
 bool    BM_edge_is_convex(const BMEdge *e);
 
 bool    BM_loop_is_convex(const BMLoop *l);
+BLI_INLINE bool BM_loop_is_adjacent(const BMLoop *l_a, const BMLoop *l_b);
 
 float   BM_loop_calc_face_angle(BMLoop *l);
 void    BM_loop_calc_face_normal(BMLoop *l, float r_normal[3]);
diff --git a/source/blender/bmesh/intern/bmesh_queries_inline.h b/source/blender/bmesh/intern/bmesh_queries_inline.h
index c3ee363f247..a2a0a15faad 100644
--- a/source/blender/bmesh/intern/bmesh_queries_inline.h
+++ b/source/blender/bmesh/intern/bmesh_queries_inline.h
@@ -127,5 +127,14 @@ BLI_INLINE int BM_edge_is_boundary(BMEdge *e)
 }
 #endif
 
+/**
+ * Tests whether one loop is next to another within the same face.
+ */
+BLI_INLINE bool BM_loop_is_adjacent(const BMLoop *l_a, const BMLoop *l_b)
+{
+	BLI_assert(l_a->f == l_b->f);
+	BLI_assert(l_a != l_b);
+	return (ELEM(l_b, l_a->next, l_a->prev));
+}
 
 #endif /* __BMESH_QUERIES_INLINE_H__ */