Improvements to bmesh edge rotate

On a user level, edge rotate now works better with multiple edges selected, it wont make zero area faces or rotate edges into existing ones.

With a single edge selected - rotate is less strict and will allow ugly resulting faces but still checks on duplicate edges.

API:
* BM_edge_rotate now takes a flag, to optionally...
** check for existing edge
** splice edge (rotate and merge)
** check for degenerate resulting faces (overlapping geometry, zero area)
** beauty - only rotate to a better fit.
... this allows it to still be used as a low level API function since all checks can be skipped.

* BM_edge_rotate() now works a bit different, it find the new edge rotation before joining the faces - exposed by BM_edge_rotate_calc().

* Added api call bmesh_radial_faceloop_find_vert() - Radial Find a Vertex Loop in Face

8 files changed, 261 insertions, 32 deletions

diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c
index dd5edcae583..97a7cb41eaa 100644
--- a/source/blender/bmesh/intern/bmesh_core.c
+++ b/source/blender/bmesh/intern/bmesh_core.c
@@ -41,7 +41,7 @@
  * TESTING ONLY! */
 // #define USE_DEBUG_INDEX_MEMCHECK
 
-static int bm_edge_splice(BMesh *bm, BMEdge *e, BMEdge *etarget);
+int BM_edge_splice(BMesh *bm, BMEdge *e, BMEdge *etarget);
 
 #ifdef USE_DEBUG_INDEX_MEMCHECK
 #define DEBUG_MEMCHECK_INDEX_INVALIDATE(ele)               \
@@ -1523,7 +1523,7 @@ BMEdge *bmesh_jekv(BMesh *bm, BMEdge *ke, BMVert *kv, const short check_edge_dou
 			if (check_edge_double) {
 				if (e_splice) {
 					/* removes e_splice */
-					bm_edge_splice(bm, e_splice, oe);
+					BM_edge_splice(bm, e_splice, oe);
 				}
 			}
 
@@ -1845,7 +1845,7 @@ static int bm_vert_cut(BMesh *bm, BMVert *v, BMVert ***vout, int *len)
  *
  * \note Edges must already have the same vertices.
  */
-static int bm_edge_splice(BMesh *bm, BMEdge *e, BMEdge *etarget)
+int BM_edge_splice(BMesh *bm, BMEdge *e, BMEdge *etarget)
 {
 	BMLoop *l;
 
diff --git a/source/blender/bmesh/intern/bmesh_core.h b/source/blender/bmesh/intern/bmesh_core.h
index bfdb17e2a1e..82731c11cf4 100644
--- a/source/blender/bmesh/intern/bmesh_core.h
+++ b/source/blender/bmesh/intern/bmesh_core.h
@@ -40,6 +40,8 @@ void BM_face_kill(BMesh *bm, BMFace *f);
 void BM_edge_kill(BMesh *bm, BMEdge *e);
 void BM_vert_kill(BMesh *bm, BMVert *v);
 
+int  BM_edge_splice(BMesh *bm, BMEdge *e, BMEdge *etarget);
+
 int  bmesh_loop_reverse(BMesh *bm, BMFace *f);
 
 BMFace *BM_faces_join(BMesh *bm, BMFace **faces, int totface);
diff --git a/source/blender/bmesh/intern/bmesh_mods.c b/source/blender/bmesh/intern/bmesh_mods.c
index 3a4264575f0..462b0cc2369 100644
--- a/source/blender/bmesh/intern/bmesh_mods.c
+++ b/source/blender/bmesh/intern/bmesh_mods.c
@@ -708,6 +708,50 @@ int BM_face_validate(BMesh *bm, BMFace *face, FILE *err)
 	return ret;
 }
 
+
+/**
+ * Calculate the 2 loops which _would_ make up the newly rotated Edge
+ * but don't actually change anything.
+ *
+ * Use this to further inspect if the loops to be connected have issues:
+ *
+ * Examples:
+ * - the newly formed edge already exists
+ * - the new face would be degenerate (zero area / concav /  bow-tie)
+ * - may want to measure if the new edge gives improved results topology.
+ *   over the old one, as with beauty fill.
+ *
+ * \note #BM_edge_rotate_check must have already run.
+ */
+void BM_edge_rotate_calc(BMesh *bm, BMEdge *e, int ccw,
+                         BMLoop **r_l1, BMLoop **r_l2)
+{
+	BMVert *v1, *v2;
+	BMFace *fa, *fb;
+
+	/* this should have already run */
+	BLI_assert(BM_edge_rotate_check(bm, e) == TRUE);
+
+	/* we know this will work */
+	BM_edge_face_pair(e, &fa, &fb);
+
+	/* so we can use ccw variable correctly,
+	 * otherwise we could use the egdes verts direct */
+	BM_edge_ordered_verts(e, &v1, &v2);
+
+	/* we could swap the verts _or_ the faces, swapping faces
+	 * gives more pradictable resuts since that way the next vert
+	 * just sitches from face fa / fb */
+	if (ccw) {
+		SWAP(BMFace *, fa, fb);
+	}
+
+
+
+	*r_l1 = BM_face_other_vert_loop(fb, v2, v1);
+	*r_l2 = BM_face_other_vert_loop(fa, v1, v2);
+}
+
 /**
  * \brief Check if Rotate Edge is OK
  *
@@ -746,6 +790,115 @@ int BM_edge_rotate_check(BMesh *UNUSED(bm), BMEdge *e)
 }
 
 /**
+ * \brief Check if Edge Rotate Gives Degenerate Faces
+ *
+ * Check 2 cases
+ * 1) does the newly forms edge form a flipped face (compare with previous cross product)
+ * 2) does the newly formed edge caise a zero area corner (or close enough to be almost zero)
+ *
+ * \param l1,l2 are the loops of the proposed verts to rotate too and should
+ * be the result of calling #BM_edge_rotate_calc
+ */
+int BM_edge_rotate_check_degenerate(BMesh *bm, BMEdge *e,
+                                    BMLoop *l1, BMLoop *l2)
+{
+	/* note: for these vars 'old' just means initial edge state. */
+
+	float ed_dir_old[3]; /* edge vector */
+	float ed_dir_new[3]; /* edge vector */
+	float ed_dir_new_flip[3]; /* edge vector */
+
+	float ed_dir_v1_old[3];
+	float ed_dir_v2_old[3];
+
+	float ed_dir_v1_new[3];
+	float ed_dir_v2_new[3];
+
+	float cross_old[3];
+	float cross_new[3];
+
+	/* original verts - these will be in the edge 'e' */
+	BMVert *v1_old, *v2_old;
+
+	/* verts from the loops passed */
+
+	BMVert *v1, *v2;
+	/* these are the opposite verts - the verts that _would_ be used if 'ccw' was inverted*/
+	BMVert *v1_alt, *v2_alt;
+
+	/* this should have already run */
+	BLI_assert(BM_edge_rotate_check(bm, e) == TRUE);
+
+	BM_edge_ordered_verts(e, &v1_old, &v2_old);
+
+	v1 = l1->v;
+	v2 = l2->v;
+
+	/* get the next vert along */
+	v1_alt = BM_face_other_vert_loop(l1->f, v1_old, v1)->v;
+	v2_alt = BM_face_other_vert_loop(l2->f, v2_old, v2)->v;
+
+	/* normalize all so comparisons are scale independent */
+
+	BLI_assert(BM_edge_exists(v1_old, v1));
+	BLI_assert(BM_edge_exists(v1, v1_alt));
+
+	BLI_assert(BM_edge_exists(v2_old, v2));
+	BLI_assert(BM_edge_exists(v2, v2_alt));
+
+	/* old and new edge vecs */
+	sub_v3_v3v3(ed_dir_old, v1_old->co, v2_old->co);
+	sub_v3_v3v3(ed_dir_new, v1->co, v2->co);
+	normalize_v3(ed_dir_old);
+	normalize_v3(ed_dir_new);
+
+	/* old edge corner vecs */
+	sub_v3_v3v3(ed_dir_v1_old, v1_old->co, v1->co);
+	sub_v3_v3v3(ed_dir_v2_old, v2_old->co, v2->co);
+	normalize_v3(ed_dir_v1_old);
+	normalize_v3(ed_dir_v2_old);
+
+	/* old edge corner vecs */
+	sub_v3_v3v3(ed_dir_v1_new, v1->co, v1_alt->co);
+	sub_v3_v3v3(ed_dir_v2_new, v2->co, v2_alt->co);
+	normalize_v3(ed_dir_v1_new);
+	normalize_v3(ed_dir_v2_new);
+
+	/* compare */
+	cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v1_old);
+	cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v1_new);
+	if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
+		return FALSE;
+	}
+	cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v2_old);
+	cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v2_new);
+	if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
+		return FALSE;
+	}
+
+	negate_v3_v3(ed_dir_new_flip, ed_dir_new);
+
+	/* result is zero area corner */
+	if ((dot_v3v3(ed_dir_new,      ed_dir_v1_new) > 0.999f) ||
+	    (dot_v3v3(ed_dir_new_flip, ed_dir_v2_new) > 0.999f))
+	{
+		return FALSE;
+	}
+
+	return TRUE;
+}
+
+int BM_edge_rotate_check_beauty(BMesh *UNUSED(bm), BMEdge *e,
+                                BMLoop *l1, BMLoop *l2)
+{
+	/* Stupid check for now:
+	 * Could compare angles of surrounding edges
+	 * before & after, but this is OK.*/
+	return (len_squared_v3v3(e->v1->co, e->v2->co) >
+	        len_squared_v3v3(l1->v->co, l2->v->co));
+}
+
+/**
  * \brief Rotate Edge
  *
  * Spins an edge topologically,
@@ -756,45 +909,77 @@ int BM_edge_rotate_check(BMesh *UNUSED(bm), BMEdge *e)
  *
  * \note This works by dissolving the edge then re-creating it,
  * so the returned edge won't have the same pointer address as the original one.
+ *
+ * \see header definition for \a check_flag enum.
  */
-BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, int ccw)
+BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const short ccw, const short check_flag)
 {
 	BMVert *v1, *v2;
-	BMLoop *l, *l1, *l2, *nl;
+	BMLoop *l1, *l2, *nl;
 	BMFace *f;
-	BMIter liter;
+	BMEdge *e_splice = NULL;
 
 	if (!BM_edge_rotate_check(bm, e)) {
 		return NULL;
 	}
 
-	v1 = e->v1;
-	v2 = e->v2;
+	BM_edge_rotate_calc(bm, e, ccw, &l1, &l2);
 
-	f = BM_faces_join_pair(bm, e->l->f, e->l->radial_next->f, e);
+	/* the loops will be freed so assign verts */
+	v1 = l1->v;
+	v2 = l2->v;
 
-	if (f == NULL)
-		return NULL;
 
-	BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
-		if (l->v == v1)
-			l1 = l;
-		else if (l->v == v2)
-			l2 = l;
+
+	/* --------------------------------------- */
+	/* Checking Code - make sure we can rotate */
+
+	if (check_flag & BM_EDGEROT_CHECK_BEAUTY) {
+		if (!BM_edge_rotate_check_beauty(bm, e, l1, l2)) {
+			return NULL;
+		}
 	}
-	
-	if (ccw) {
-		l1 = l1->prev;
-		l2 = l2->prev;
+
+	/* check before applying */
+	if (check_flag & BM_EDGEROT_CHECK_SPLICE) {
+		e_splice = BM_edge_exists(v1, v2);
 	}
-	else {
-		l1 = l1->next;
-		l2 = l2->next;
+	else if (check_flag & BM_EDGEROT_CHECK_EXISTS) {
+		if (BM_edge_exists(v1, v2)) {
+			return NULL;
+		}
+	}
+
+	/* slowest, check last */
+	if (check_flag & BM_EDGEROT_CHECK_DEGENERATE) {
+		if (!BM_edge_rotate_check_degenerate(bm, e, l1, l2)) {
+			return NULL;
+		}
+	}
+	/* Done Checking */
+	/* ------------- */
+
+
+
+	/* rotate the edge */
+	f = BM_faces_join_pair(bm, l1->f, l2->f, e);
+
+	if (f == NULL) {
+		return NULL;
 	}
 
-	if (!BM_face_split(bm, f, l1->v, l2->v, &nl, NULL))
+	/* 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, &nl, NULL))
 		return NULL;
 
+	/* replace existing edge (kill e_splice) */
+	if (e_splice) {
+		BM_edge_splice(bm, e_splice, nl->e);
+	}
+
 	return nl->e;
 }
 
diff --git a/source/blender/bmesh/intern/bmesh_mods.h b/source/blender/bmesh/intern/bmesh_mods.h
index d530e9d8666..f3344f2d687 100644
--- a/source/blender/bmesh/intern/bmesh_mods.h
+++ b/source/blender/bmesh/intern/bmesh_mods.h
@@ -53,8 +53,23 @@ BMVert *BM_edge_split_n(BMesh *bm, BMEdge *e, int numcuts);
 
 int     BM_face_validate(BMesh *bm, BMFace *face, FILE *err);
 
+void    BM_edge_rotate_calc(BMesh *bm, BMEdge *e, int ccw,
+                                   BMLoop **r_l1, BMLoop **r_l2);
 int     BM_edge_rotate_check(BMesh *UNUSED(bm), BMEdge *e);
-BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, int ccw);
+int     BM_edge_rotate_check_degenerate(BMesh *bm, BMEdge *e,
+                                        BMLoop *l1, BMLoop *l2);
+int     BM_edge_rotate_check_beauty(BMesh *bm, BMEdge *e,
+                                    BMLoop *l1, BMLoop *l2);
+BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const short ccw, const short check_flag);
+
+/* flags for BM_edge_rotate */
+enum {
+	BM_EDGEROT_CHECK_EXISTS     = (1 << 0), /* disallow to rotate when the new edge matches an existing one */
+	BM_EDGEROT_CHECK_SPLICE     = (1 << 1), /* overrides existing check, if the edge already, rotate and merge them */
+	BM_EDGEROT_CHECK_DEGENERATE = (1 << 2), /* disallow creating bow-tie, concave or zero area faces */
+	BM_EDGEROT_CHECK_BEAUTY     = (1 << 3)  /* disallow to rotate into ugly topology */
+};
+
 
 BMVert *BM_vert_rip(BMesh *bm, BMFace *sf, BMVert *sv);
 
diff --git a/source/blender/bmesh/intern/bmesh_structure.c b/source/blender/bmesh/intern/bmesh_structure.c
index ad6a8a615e3..abce7780e79 100644
--- a/source/blender/bmesh/intern/bmesh_structure.c
+++ b/source/blender/bmesh/intern/bmesh_structure.c
@@ -201,15 +201,13 @@ void bmesh_disk_edge_remove(BMEdge *e, BMVert *v)
 	dl1->next = dl1->prev = NULL;
 }
 
-/*
- *			bmesh_disk_edge_next
+/**
+ * \brief Next Disk Edge
  *
  *	Find the next edge in a disk cycle
  *
- *  Returns -
- *	Pointer to the next edge in the disk cycle for the vertex v.
+ *	\return Pointer to the next edge in the disk cycle for the vertex v.
  */
-
 BMEdge *bmesh_disk_edge_next(BMEdge *e, BMVert *v)
 {
 	if (v == e->v1)
@@ -453,6 +451,27 @@ BMLoop *bmesh_radial_faceloop_find_next(BMLoop *l, BMVert *v)
 	return l;
 }
 
+/* NOTE: this function has not been used or tested - so take care but it should work ok,
+ * I wrote it for some tool that ended up not using it, however this seems like a reasonable
+ * thing to be able to find the loop between a vertex and a face so keeping - campbell */
+/**
+ * \brief Radial Find a Vertex Loop in Face
+ *
+ * Finds the loop used which uses \a v in face loop \a l
+ */
+BMLoop *bmesh_radial_faceloop_find_vert(BMFace *f, BMVert *v) /* name is a bit awkward */
+{
+	BMLoop *l_iter, *l_first;
+	if (v->e && (l_iter = l_first = v->e->l)) {
+		do {
+			if (l_iter->v == v && l_iter->f == f) {
+				return l_iter;
+			}
+		} while ((l_iter = l_iter->radial_next) != l_first);
+	}
+	return NULL;
+}
+
 int bmesh_radial_length(BMLoop *l)
 {
 	BMLoop *l_iter = l;
diff --git a/source/blender/bmesh/intern/bmesh_structure.h b/source/blender/bmesh/intern/bmesh_structure.h
index c3780a5dede..8b43f72c725 100644
--- a/source/blender/bmesh/intern/bmesh_structure.h
+++ b/source/blender/bmesh/intern/bmesh_structure.h
@@ -64,6 +64,7 @@ int     bmesh_radial_face_find(BMEdge *e, BMFace *f);
 int     bmesh_radial_facevert_count(BMLoop *l, BMVert *v);
 BMLoop *bmesh_radial_faceloop_find_first(BMLoop *l, BMVert *v);
 BMLoop *bmesh_radial_faceloop_find_next(BMLoop *l, BMVert *v);
+BMLoop *bmesh_radial_faceloop_find_vert(BMFace *f, BMVert *v);
 int     bmesh_radial_validate(int radlen, BMLoop *l);
 
 /* EDGE UTILITIES */
diff --git a/source/blender/bmesh/operators/bmo_triangulate.c b/source/blender/bmesh/operators/bmo_triangulate.c
index 2029d595af7..63837b7e087 100644
--- a/source/blender/bmesh/operators/bmo_triangulate.c
+++ b/source/blender/bmesh/operators/bmo_triangulate.c
@@ -139,7 +139,7 @@ void bmo_beautify_fill_exec(BMesh *bm, BMOperator *op)
 				fac2 = opp1 / (len2 + len3 + len6) + opp2 / (len4 + len1 + len6);
 				
 				if (fac1 > fac2) {
-					e = BM_edge_rotate(bm, e, FALSE);
+					e = BM_edge_rotate(bm, e, FALSE, BM_EDGEROT_CHECK_EXISTS);
 					if (e) {
 						BMO_elem_flag_enable(bm, e, ELE_NEW);
 
diff --git a/source/blender/bmesh/operators/bmo_utils.c b/source/blender/bmesh/operators/bmo_utils.c
index 8e75d7880ee..9aed578dccc 100644
--- a/source/blender/bmesh/operators/bmo_utils.c
+++ b/source/blender/bmesh/operators/bmo_utils.c
@@ -124,6 +124,10 @@ void bmo_edgerotate_exec(BMesh *bm, BMOperator *op)
 	BMOIter siter;
 	BMEdge *e, *e2;
 	int ccw = BMO_slot_bool_get(op, "ccw");
+	int is_single = BMO_slot_buffer_count(bm, op, "edges") == 1;
+	short check_flag = is_single ?
+	            BM_EDGEROT_CHECK_EXISTS :
+	            BM_EDGEROT_CHECK_EXISTS | BM_EDGEROT_CHECK_DEGENERATE;
 
 #define EDGE_OUT   1
 #define FACE_TAINT 1
@@ -141,9 +145,12 @@ void bmo_edgerotate_exec(BMesh *bm, BMOperator *op)
 				    BMO_elem_flag_test(bm, fb, FACE_TAINT) == FALSE)
 				{
 
-					if (!(e2 = BM_edge_rotate(bm, e, ccw))) {
+					if (!(e2 = BM_edge_rotate(bm, e, ccw, check_flag))) {
+#if 0
 						BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, "Could not rotate edge");
 						return;
+#endif
+						continue;
 					}
 
 					BMO_elem_flag_enable(bm, e2, EDGE_OUT);