BMesh: tool to ensure all faces are convex

Access from Mesh -> Cleanup

10 files changed, 281 insertions, 2 deletions

diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt
index 23737866bf2..80adb595ac9 100644
--- a/source/blender/bmesh/CMakeLists.txt
+++ b/source/blender/bmesh/CMakeLists.txt
@@ -43,6 +43,7 @@ set(SRC
 	operators/bmo_bisect_plane.c
 	operators/bmo_bridge.c
 	operators/bmo_connect.c
+	operators/bmo_connect_concave.c
 	operators/bmo_connect_nonplanar.c
 	operators/bmo_connect_pair.c
 	operators/bmo_create.c
diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c
index 114358884b7..d0679b9919a 100644
--- a/source/blender/bmesh/intern/bmesh_opdefines.c
+++ b/source/blender/bmesh/intern/bmesh_opdefines.c
@@ -933,6 +933,28 @@ static BMOpDefine bmo_connect_verts_def = {
 };
 
 /*
+ * Connect Verts to form Convex Faces.
+ *
+ * Ensures all faces are convex **faces**.
+ */
+static BMOpDefine bmo_connect_verts_concave_def = {
+	"connect_verts_concave",
+	/* slots_in */
+	{{"faces", BMO_OP_SLOT_ELEMENT_BUF, {BM_FACE}},
+	 {{'\0'}},
+	},
+	/* slots_out */
+	{{"edges.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_EDGE}},
+	 {"faces.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_FACE}},
+	 {{'\0'}},
+	},
+	bmo_connect_verts_concave_exec,
+	(BMO_OPTYPE_FLAG_UNTAN_MULTIRES |
+	 BMO_OPTYPE_FLAG_NORMALS_CALC |
+	 BMO_OPTYPE_FLAG_SELECT_FLUSH),
+};
+
+/*
  * Connect Verts Across non Planer Faces.
  *
  * Split faces by connecting edges along non planer **faces**.
@@ -1950,6 +1972,7 @@ const BMOpDefine *bmo_opdefines[] = {
 	&bmo_collapse_def,
 	&bmo_collapse_uvs_def,
 	&bmo_connect_verts_def,
+	&bmo_connect_verts_concave_def,
 	&bmo_connect_verts_nonplanar_def,
 	&bmo_connect_vert_pair_def,
 	&bmo_contextual_create_def,
diff --git a/source/blender/bmesh/intern/bmesh_operators_private.h b/source/blender/bmesh/intern/bmesh_operators_private.h
index 9c1b7085835..979f7d2640a 100644
--- a/source/blender/bmesh/intern/bmesh_operators_private.h
+++ b/source/blender/bmesh/intern/bmesh_operators_private.h
@@ -41,6 +41,7 @@ void bmo_bridge_loops_exec(BMesh *bm, BMOperator *op);
 void bmo_collapse_exec(BMesh *bm, BMOperator *op);
 void bmo_collapse_uvs_exec(BMesh *bm, BMOperator *op);
 void bmo_connect_verts_exec(BMesh *bm, BMOperator *op);
+void bmo_connect_verts_concave_exec(BMesh *bm, BMOperator *op);
 void bmo_connect_verts_nonplanar_exec(BMesh *bm, BMOperator *op);
 void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op);
 void bmo_contextual_create_exec(BMesh *bm, BMOperator *op);
diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h
index b25a7dbaa55..9980b59a298 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.h
+++ b/source/blender/bmesh/intern/bmesh_polygon.h
@@ -63,6 +63,8 @@ void  BM_face_triangulate(
         BMesh *bm, BMFace *f,
         BMFace **r_faces_new,
         int     *r_faces_new_tot,
+        BMEdge **r_edges_new,
+        int     *r_edges_new_tot,
         const int quad_method, const int ngon_method,
         const bool use_tag,
         struct MemArena *pf_arena,
diff --git a/source/blender/bmesh/intern/bmesh_queries.h b/source/blender/bmesh/intern/bmesh_queries.h
index abff55719f5..535b752d4f2 100644
--- a/source/blender/bmesh/intern/bmesh_queries.h
+++ b/source/blender/bmesh/intern/bmesh_queries.h
@@ -143,6 +143,7 @@ bool BM_face_is_any_vert_flag_test(const BMFace *f, const char hflag) ATTR_WARN_
 bool BM_face_is_any_edge_flag_test(const BMFace *f, const char hflag) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
 
 bool BM_face_is_normal_valid(const BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
+bool BM_face_is_convex(const BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
 
 float BM_mesh_calc_volume(BMesh *bm, bool is_signed) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
 
diff --git a/source/blender/bmesh/operators/bmo_connect_concave.c b/source/blender/bmesh/operators/bmo_connect_concave.c
new file mode 100644
index 00000000000..aec8119d421
--- /dev/null
+++ b/source/blender/bmesh/operators/bmo_connect_concave.c
@@ -0,0 +1,211 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/bmesh/operators/bmo_connect_concave.c
+ *  \ingroup bmesh
+ *
+ * Connect vertices so all resulting faces are convex.
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_math.h"
+#include "BLI_utildefines.h"
+#include "BLI_alloca.h"
+#include "BLI_memarena.h"
+#include "BLI_heap.h"
+#include "BLI_polyfill2d.h"
+#include "BLI_polyfill2d_beautify.h"
+#include "BLI_edgehash.h"
+
+#include "bmesh.h"
+
+#include "intern/bmesh_operators_private.h" /* own include */
+
+#define EDGE_OUT	(1 << 0)
+#define FACE_OUT	(1 << 1)
+
+static int bm_edge_length_cmp(const void *a_, const void *b_)
+{
+	const BMEdge *e_a = *(const void **)a_;
+	const BMEdge *e_b = *(const void **)b_;
+
+	int e_a_concave = ((BM_elem_flag_test(e_a->v1, BM_ELEM_TAG)) && (BM_elem_flag_test(e_a->v2, BM_ELEM_TAG)));
+	int e_b_concave = ((BM_elem_flag_test(e_b->v1, BM_ELEM_TAG)) && (BM_elem_flag_test(e_b->v2, BM_ELEM_TAG)));
+
+	/* merge edges between concave edges last since these
+	 * are most likely to remain and be the main dividers */
+	if      (e_a_concave < e_b_concave) return -1;
+	else if (e_a_concave > e_b_concave) return  1;
+	else
+	{
+		const float e_a_len = BM_edge_calc_length_squared(e_a);
+		const float e_b_len = BM_edge_calc_length_squared(e_b);
+		if      (e_a_len < e_b_len) return  1;
+		else if (e_a_len > e_b_len) return -1;
+		else                    return  0;
+	}
+}
+
+static bool bm_face_split_by_concave(
+        BMesh *bm, BMFace *f_base, const float eps,
+
+        MemArena *pf_arena,
+        struct Heap *pf_heap, struct EdgeHash *pf_ehash)
+{
+	const int f_base_len = f_base->len;
+	int faces_array_tot = f_base->len - 3;
+	int edges_array_tot = f_base->len - 3;
+	BMFace  **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
+	BMEdge  **edges_array = BLI_array_alloca(edges_array, edges_array_tot);
+	const int quad_method = 0, ngon_method = 0;  /* beauty */
+
+	float normal[3];
+	BLI_assert(f_base->len > 3);
+
+	copy_v3_v3(normal, f_base->no);
+
+	BM_face_triangulate(
+	        bm, f_base,
+	        faces_array, &faces_array_tot,
+	        edges_array, &edges_array_tot,
+	        quad_method, ngon_method, false,
+	        pf_arena,
+	        pf_heap, pf_ehash);
+
+	BLI_assert(edges_array_tot <= f_base_len - 3);
+
+	if (faces_array_tot) {
+		int i;
+		for (i = 0; i < faces_array_tot; i++) {
+			BMFace *f = faces_array[i];
+			BMO_elem_flag_enable(bm, f, FACE_OUT);
+		}
+	}
+	BMO_elem_flag_enable(bm, f_base, FACE_OUT);
+
+	if (edges_array_tot) {
+		int i;
+
+		qsort(edges_array, edges_array_tot, sizeof(*edges_array), bm_edge_length_cmp);
+
+		for (i = 0; i < edges_array_tot; i++) {
+			BMLoop *l_pair[2];
+			BMEdge *e = edges_array[i];
+			BMO_elem_flag_enable(bm, e, EDGE_OUT);
+
+			if (BM_edge_is_contiguous(e) &&
+			    BM_edge_loop_pair(e, &l_pair[0], &l_pair[1]))
+			{
+				bool ok = true;
+				int j;
+				for (j = 0; j < 2; j++) {
+					BMLoop *l = l_pair[j];
+
+					/* check that merging the edge (on this side)
+					 * wouldn't result in a convex face-loop.
+					 *
+					 * This is the (l->next, l->prev) we would have once joined.
+					 */
+					float cross[3];
+					cross_tri_v3(
+					        cross,
+					        l->v->co,
+					        l->radial_next->next->next->v->co,
+					        l->prev->v->co
+					        );
+
+					if (dot_v3v3(cross, normal) <= eps) {
+						ok = false;
+						break;
+					}
+				}
+
+				if (ok) {
+					BMFace *f_new, *f_pair[2] = {l_pair[0]->f, l_pair[1]->f};
+					f_new = BM_faces_join(bm, f_pair, 2, true);
+					if (f_new) {
+						BMO_elem_flag_enable(bm, f_new, FACE_OUT);
+					}
+				}
+			}
+		}
+	}
+
+	BLI_heap_clear(pf_heap, NULL);
+	BLI_edgehash_clear_ex(pf_ehash, NULL, BLI_POLYFILL_ALLOC_NGON_RESERVE);
+
+	return true;
+}
+
+static bool bm_face_convex_tag_verts(BMFace *f)
+{
+	bool is_concave = false;
+	if (f->len > 3) {
+		const BMLoop *l_iter, *l_first;
+
+		l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+		do {
+			if (BM_loop_is_convex(l_iter) == false) {
+				is_concave = true;
+				BM_elem_flag_enable(l_iter->v, BM_ELEM_TAG);
+			}
+			else {
+				BM_elem_flag_disable(l_iter->v, BM_ELEM_TAG);
+			}
+		} while ((l_iter = l_iter->next) != l_first);
+	}
+	return is_concave;
+}
+
+void bmo_connect_verts_concave_exec(BMesh *bm, BMOperator *op)
+{
+	BMOIter siter;
+	BMFace *f;
+	bool changed = false;
+
+	MemArena *pf_arena;
+	Heap *pf_heap;
+	EdgeHash *pf_ehash;
+
+	pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__);
+	pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE);
+	pf_ehash = BLI_edgehash_new_ex(__func__, BLI_POLYFILL_ALLOC_NGON_RESERVE);
+
+	BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
+		if (f->len > 3 && bm_face_convex_tag_verts(f)) {
+			if (bm_face_split_by_concave(
+			        bm, f, FLT_EPSILON,
+			        pf_arena, pf_heap, pf_ehash))
+			{
+				changed = true;
+			}
+		}
+	}
+
+	if (changed) {
+		BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
+		BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT);
+	}
+
+	BLI_memarena_free(pf_arena);
+	BLI_heap_free(pf_heap, NULL);
+	BLI_edgehash_free(pf_ehash, NULL);
+}
diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c
index b76054f270f..404776a0769 100644
--- a/source/blender/bmesh/tools/bmesh_triangulate.c
+++ b/source/blender/bmesh/tools/bmesh_triangulate.c
@@ -64,7 +64,9 @@ static void bm_face_triangulate_mapping(
 	BLI_assert(face->len > 3);
 
 	BM_face_triangulate(
-	        bm, face, faces_array, &faces_array_tot,
+	        bm, face,
+	        faces_array, &faces_array_tot,
+	        NULL, NULL,
 	        quad_method, ngon_method, use_tag,
 	        pf_arena,
 	        pf_heap, pf_ehash);
@@ -121,7 +123,9 @@ void BM_mesh_triangulate(
 			if (face->len > 3) {
 				if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) {
 					BM_face_triangulate(
-					        bm, face, NULL, NULL,
+					        bm, face,
+					        NULL, NULL,
+					        NULL, NULL,
 					        quad_method, ngon_method, tag_only,
 					        pf_arena,
 					        pf_heap, pf_ehash);
diff --git a/source/blender/editors/mesh/editmesh_tools.c b/source/blender/editors/mesh/editmesh_tools.c
index 1e301e09837..3a9e366fe37 100644
--- a/source/blender/editors/mesh/editmesh_tools.c
+++ b/source/blender/editors/mesh/editmesh_tools.c
@@ -964,6 +964,40 @@ void MESH_OT_vert_connect(wmOperatorType *ot)
 	ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
 }
 
+static int edbm_vert_connect_concave_exec(bContext *C, wmOperator *op)
+{
+	Object *obedit = CTX_data_edit_object(C);
+	BMEditMesh *em = BKE_editmesh_from_object(obedit);
+
+	if (!EDBM_op_call_and_selectf(
+	             em, op,
+	             "faces.out", true,
+	             "connect_verts_concave faces=%hf",
+	             BM_ELEM_SELECT))
+	{
+		return OPERATOR_CANCELLED;
+	}
+
+
+	EDBM_update_generic(em, true, true);
+	return OPERATOR_FINISHED;
+}
+
+void MESH_OT_vert_connect_concave(wmOperatorType *ot)
+{
+	/* identifiers */
+	ot->name = "Split Concave Faces";
+	ot->idname = "MESH_OT_vert_connect_concave";
+	ot->description = "Makes all faces convex";
+
+	/* api callbacks */
+	ot->exec = edbm_vert_connect_concave_exec;
+	ot->poll = ED_operator_editmesh;
+
+	/* flags */
+	ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
+}
+
 
 static int edbm_vert_connect_nonplaner_exec(bContext *C, wmOperator *op)
 {
diff --git a/source/blender/editors/mesh/mesh_intern.h b/source/blender/editors/mesh/mesh_intern.h
index 6ba91097ec4..a794db62e3e 100644
--- a/source/blender/editors/mesh/mesh_intern.h
+++ b/source/blender/editors/mesh/mesh_intern.h
@@ -175,6 +175,7 @@ void MESH_OT_normals_make_consistent(struct wmOperatorType *ot);
 void MESH_OT_vertices_smooth(struct wmOperatorType *ot);
 void MESH_OT_vertices_smooth_laplacian(struct wmOperatorType *ot);
 void MESH_OT_vert_connect(struct wmOperatorType *ot);
+void MESH_OT_vert_connect_concave(struct wmOperatorType *ot);
 void MESH_OT_vert_connect_nonplanar(struct wmOperatorType *ot);
 void MESH_OT_edge_split(struct wmOperatorType *ot);
 void MESH_OT_bridge_edge_loops(struct wmOperatorType *ot);
diff --git a/source/blender/editors/mesh/mesh_ops.c b/source/blender/editors/mesh/mesh_ops.c
index e7dc5a69d53..8146be7ee47 100644
--- a/source/blender/editors/mesh/mesh_ops.c
+++ b/source/blender/editors/mesh/mesh_ops.c
@@ -161,6 +161,7 @@ void ED_operatortypes_mesh(void)
 	WM_operatortype_append(MESH_OT_solidify);
 	WM_operatortype_append(MESH_OT_select_nth);
 	WM_operatortype_append(MESH_OT_vert_connect);
+	WM_operatortype_append(MESH_OT_vert_connect_concave);
 	WM_operatortype_append(MESH_OT_vert_connect_nonplanar);
 	WM_operatortype_append(MESH_OT_knife_tool);
 	WM_operatortype_append(MESH_OT_knife_project);