Fix connect-vertices failing for concave ngons

Also add:
- generic callback for bmesh elements.
- ability to pass an existing array to a bmesh operator.

1 files changed, 77 insertions, 70 deletions

diff --git a/source/blender/bmesh/operators/bmo_connect_pair.c b/source/blender/bmesh/operators/bmo_connect_pair.c
index cfffb6021cf..916ea3ebcd9 100644
--- a/source/blender/bmesh/operators/bmo_connect_pair.c
+++ b/source/blender/bmesh/operators/bmo_connect_pair.c
@@ -230,23 +230,45 @@ static PathLinkState *state_dupe_add(
 static PathLinkState *state_step__face_edges(
         PathContext *pc,
         PathLinkState *state, const PathLinkState *state_orig,
-        BMLoop *l_iter, BMLoop *l_last)
+        BMLoop *l_iter, BMLoop *l_last,
+        float *r_dist_best)
 {
+	BMLoop *l_iter_best = NULL;
+	float dist_best = *r_dist_best;
+
 	do {
 		if (state_isect_co_pair(pc, l_iter->v->co, l_iter->next->v->co)) {
-			BMElem *ele_next      = (BMElem *)l_iter->e;
-			BMElem *ele_next_from = (BMElem *)l_iter->f;
+			float dist_test;
+			float co_isect[3];
 
-			if (FACE_WALK_TEST((BMFace *)ele_next_from) &&
-			    (state_link_find(state, ele_next) == false))
-			{
-				if (state_orig->link_last != state->link_last) {
-					state = state_dupe_add(pc, state, state_orig);
+			state_calc_co_pair(pc, l_iter->v->co, l_iter->next->v->co, co_isect);
+			dist_test = len_squared_v3v3(state->co_prev, co_isect);
+			if (dist_test < dist_best) {
+				BMElem *ele_next      = (BMElem *)l_iter->e;
+				BMElem *ele_next_from = (BMElem *)l_iter->f;
+
+				if (FACE_WALK_TEST((BMFace *)ele_next_from) &&
+				    (state_link_find(state, ele_next) == false))
+				{
+					dist_best = dist_test;
+					l_iter_best = l_iter;
 				}
-				state_link_add(pc, state, ele_next, ele_next_from);
 			}
 		}
 	} while ((l_iter = l_iter->next) != l_last);
+
+	if ((l_iter = l_iter_best)) {
+		BMElem *ele_next      = (BMElem *)l_iter->e;
+		BMElem *ele_next_from = (BMElem *)l_iter->f;
+
+		if (state_orig->link_last != state->link_last) {
+			state = state_dupe_add(pc, state, state_orig);
+		}
+		state_link_add(pc, state, ele_next, ele_next_from);
+	}
+
+	*r_dist_best = dist_best;
+
 	return state;
 }
 
@@ -254,23 +276,40 @@ static PathLinkState *state_step__face_edges(
 static PathLinkState *state_step__face_verts(
         PathContext *pc,
         PathLinkState *state, const PathLinkState *state_orig,
-        BMLoop *l_iter, BMLoop *l_last)
+        BMLoop *l_iter, BMLoop *l_last, float *r_dist_best)
 {
+	BMLoop *l_iter_best = NULL;
+	float dist_best = *r_dist_best;
+
 	do {
 		if (state_isect_co_exact(pc, l_iter->v->co)) {
-			BMElem *ele_next      = (BMElem *)l_iter->v;
-			BMElem *ele_next_from = (BMElem *)l_iter->f;
+			const float dist_test = len_squared_v3v3(state->co_prev, l_iter->v->co);
+			if (dist_test < dist_best) {
+				BMElem *ele_next      = (BMElem *)l_iter->v;
+				BMElem *ele_next_from = (BMElem *)l_iter->f;
 
-			if (FACE_WALK_TEST((BMFace *)ele_next_from) &&
-			    state_link_find(state, ele_next) == false)
-			{
-				if (state_orig->link_last != state->link_last) {
-					state = state_dupe_add(pc, state, state_orig);
+				if (FACE_WALK_TEST((BMFace *)ele_next_from) &&
+				    state_link_find(state, ele_next) == false)
+				{
+					dist_best = dist_test;
+					l_iter_best = l_iter;
 				}
-				state_link_add(pc, state, ele_next, ele_next_from);
 			}
 		}
 	} while ((l_iter = l_iter->next) != l_last);
+
+	if ((l_iter = l_iter_best)) {
+		BMElem *ele_next      = (BMElem *)l_iter->v;
+		BMElem *ele_next_from = (BMElem *)l_iter->f;
+
+		if (state_orig->link_last != state->link_last) {
+			state = state_dupe_add(pc, state, state_orig);
+		}
+		state_link_add(pc, state, ele_next, ele_next_from);
+	}
+
+	*r_dist_best = dist_best;
+
 	return state;
 }
 
@@ -290,20 +329,12 @@ static bool state_step(PathContext *pc, PathLinkState *state)
 			if ((l_start->f != ele_from) &&
 			    FACE_WALK_TEST(l_start->f))
 			{
+				float dist_best = FLT_MAX;
 				/* very similar to block below */
-				if (BM_vert_in_face(l_start->f, pc->v_b)) {
-					if (state_orig.link_last != state->link_last) {
-						state = state_dupe_add(pc, state, &state_orig);
-					}
-
-					state_link_add(pc, state, (BMElem *)pc->v_b, (BMElem *)l_start->f);
-				}
-				else {
-					state = state_step__face_edges(pc, state, &state_orig,
-					                               l_start->next, l_start);
-					state = state_step__face_verts(pc, state, &state_orig,
-					                               l_start->next->next, l_start);
-				}
+				state = state_step__face_edges(pc, state, &state_orig,
+				                               l_start->next, l_start, &dist_best);
+				state = state_step__face_verts(pc, state, &state_orig,
+				                               l_start->next->next, l_start, &dist_best);
 			}
 		}
 	}
@@ -319,24 +350,14 @@ static bool state_step(PathContext *pc, PathLinkState *state)
 				if ((l_start->f != ele_from) &&
 				    FACE_WALK_TEST(l_start->f))
 				{
+					float dist_best = FLT_MAX;
 					/* very similar to block above */
-					if (BM_vert_in_face(l_start->f, pc->v_b)) {
-						BMElem *ele_next      = (BMElem *)pc->v_b;
-						BMElem *ele_next_from = (BMElem *)l_start->f;
-
-						if (state_orig.link_last != state->link_last) {
-							state = state_dupe_add(pc, state, &state_orig);
-						}
-						state_link_add(pc, state, ele_next, ele_next_from);
-					}
-					else {
-						state = state_step__face_edges(pc, state, &state_orig,
-						                               l_start->next, l_start->prev);
-						if (l_start->f->len > 3) {
-							/* adjacent verts are handled in state_step__vert_edges */
-							state = state_step__face_verts(pc, state, &state_orig,
-							                               l_start->next->next, l_start->prev);
-						}
+					state = state_step__face_edges(pc, state, &state_orig,
+					                               l_start->next, l_start->prev, &dist_best);
+					if (l_start->f->len > 3) {
+						/* adjacent verts are handled in state_step__vert_edges */
+						state = state_step__face_verts(pc, state, &state_orig,
+						                               l_start->next->next, l_start->prev, &dist_best);
 					}
 				}
 			}
@@ -351,31 +372,19 @@ static bool state_step(PathContext *pc, PathLinkState *state)
 				if (((BMElem *)e != ele_from) &&
 				    VERT_WALK_TEST(v_other))
 				{
-					if (v_other == pc->v_b) {
-						BMElem *ele_next      = (BMElem *)pc->v_b;
+					if (state_isect_co_exact(pc, v_other->co)) {
+						BMElem *ele_next      = (BMElem *)v_other;
 						BMElem *ele_next_from = (BMElem *)e;
-
-						if (state_orig.link_last != state->link_last) {
-							state = state_dupe_add(pc, state, &state_orig);
-						}
-						state_link_add(pc, state, ele_next, ele_next_from);
-					}
-					else {
-						if (state_isect_co_exact(pc, v_other->co)) {
-							BMElem *ele_next      = (BMElem *)v_other;
-							BMElem *ele_next_from = (BMElem *)e;
-							if (state_link_find(state, ele_next) == false) {
-								if (state_orig.link_last != state->link_last) {
-									state = state_dupe_add(pc, state, &state_orig);
-								}
-								state_link_add(pc, state, ele_next, ele_next_from);
+						if (state_link_find(state, ele_next) == false) {
+							if (state_orig.link_last != state->link_last) {
+								state = state_dupe_add(pc, state, &state_orig);
 							}
+							state_link_add(pc, state, ele_next, ele_next_from);
 						}
 					}
 				}
 			}
 		}
-
 	}
 	else {
 		BLI_assert(0);
@@ -562,12 +571,10 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op)
 
 #if 1
 	if (found_all) {
-		/* leave 'check_degenerate' off, if a user tries to cut with 2 verts,
-		 * always connect even when resulting faces are degenerate [#39418] */
 		BMOperator op_sub;
 		BMO_op_initf(bm, &op_sub, 0,
-		             "connect_verts verts=%fv faces_exclude=%s",
-		             VERT_OUT, op, "faces_exclude");
+		             "connect_verts verts=%fv faces_exclude=%s check_degenerate=%b",
+		             VERT_OUT, op, "faces_exclude", true);
 		BMO_op_exec(bm, &op_sub);
 		BMO_slot_copy(&op_sub, slots_out, "edges.out",
 		              op,      slots_out, "edges.out");