Triangulate Modifier: using different ngon and quad methods

Quads: Beauty, Fixed, Fixed Alternate, Shortest Diagonal
Ngons: Beauty, Scanfill

* Shortest Diagonal is the default method in the modifier (popular
  elsewhere), but beauty is the default in Ctrl+T).

* Remove the need for output slot and beauty operator to be called
after Clt+T

Patch with collaborations and reviewed by Campbell Barton

8 files changed, 100 insertions, 23 deletions

diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c
index 775cb24b8c9..ea533837b04 100644
--- a/source/blender/bmesh/intern/bmesh_opdefines.c
+++ b/source/blender/bmesh/intern/bmesh_opdefines.c
@@ -1028,7 +1028,8 @@ static BMOpDefine bmo_triangulate_def = {
 	"triangulate",
 	/* slots_in */
 	{{"faces", BMO_OP_SLOT_ELEMENT_BUF, {BM_FACE}},
-	 {"use_beauty", BMO_OP_SLOT_BOOL},
+	 {"quad_method", BMO_OP_SLOT_INT},
+	 {"ngon_method", BMO_OP_SLOT_INT},
 	 {{'\0'}},
 	},
 	/* slots_out */
diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index 12ec3da9b69..e88fdb8a7e8 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -29,6 +29,7 @@
  */
 
 #include "DNA_listBase.h"
+#include "DNA_modifier_types.h"
 
 #include "BLI_alloca.h"
 #include "BLI_math.h"
@@ -817,7 +818,9 @@ bool BM_face_point_inside_test(BMFace *f, const float co[3])
 void BM_face_triangulate(BMesh *bm, BMFace *f,
                          BMFace **r_faces_new,
                          MemArena *sf_arena,
-                         const bool use_beauty, const bool use_tag)
+                         const int quad_method,
+                         const int ngon_method,
+                         const bool use_tag)
 {
 	BMLoop *l_iter, *l_first, *l_new;
 	BMFace *f_new;
@@ -825,6 +828,7 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
 	int nf_i = 0;
 	BMEdge **edge_array;
 	int edge_array_len;
+	bool use_beauty = (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY);
 
 #define SF_EDGE_IS_BOUNDARY 0xff
 
@@ -832,9 +836,67 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
 
 
 	if (f->len == 4) {
+		BMVert *v1, *v2;
 		l_first = BM_FACE_FIRST_LOOP(f);
 
-		f_new = BM_face_split(bm, f, l_first->v, l_first->next->next->v, &l_new, NULL, false);
+		switch (quad_method) {
+			case MOD_TRIANGULATE_QUAD_FIXED:
+			{
+				v1 = l_first->v;
+				v2 = l_first->next->next->v;
+				break;
+			}
+			case MOD_TRIANGULATE_QUAD_ALTERNATE:
+			{
+				v1 = l_first->next->v;
+				v2 = l_first->prev->v;
+				break;
+			}
+			case MOD_TRIANGULATE_QUAD_SHORTEDGE:
+			{
+				BMVert *v3, *v4;
+				float d1, d2;
+
+				v1 = l_first->v;
+				v2 = l_first->next->next->v;
+				v3 = l_first->next->v;
+				v4 = l_first->prev->v;
+
+				d1 = len_squared_v3v3(v1->co, v2->co);
+				d2 = len_squared_v3v3(v3->co, v4->co);
+
+				if (d2 < d1) {
+					v1 = v3;
+					v2 = v4;
+				}
+				break;
+			}
+			case MOD_TRIANGULATE_QUAD_BEAUTY:
+			default:
+			{
+				BMVert *v3, *v4;
+				float cost;
+
+				v1 = l_first->next->v;
+				v2 = l_first->next->next->v;
+				v3 = l_first->prev->v;
+				v4 = l_first->v;
+
+				cost = BM_verts_calc_rotate_beauty(v1, v2, v3, v4, 0, 0);
+
+				if (cost < 0.0f) {
+					v1 = v4;
+					//v2 = v2;
+				}
+				else {
+					//v1 = v1;
+					v2 = v3;
+				}
+				break;
+			}
+		}
+
+		f_new = BM_face_split(bm, f, v1, v2, &l_new, NULL, false);
 		copy_v3_v3(f_new->no, f->no);
 
 		if (use_tag) {
diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h
index b7117621273..4759c73cb4d 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.h
+++ b/source/blender/bmesh/intern/bmesh_polygon.h
@@ -54,7 +54,8 @@ bool  BM_face_point_inside_test(BMFace *f, const float co[3]) ATTR_WARN_UNUSED_R
 
 void  BM_face_triangulate(BMesh *bm, BMFace *f, BMFace **newfaces,
                           struct MemArena *sf_arena,
-                          const bool use_beauty, const bool use_tag) ATTR_NONNULL(1, 2);
+                          const int quad_method, const int ngon_method,
+                          const bool use_tag) ATTR_NONNULL(1, 2);
 
 void  BM_face_legal_splits(BMFace *f, BMLoop *(*loops)[2], int len) ATTR_NONNULL();
 
diff --git a/source/blender/bmesh/operators/bmo_triangulate.c b/source/blender/bmesh/operators/bmo_triangulate.c
index ca45289520b..a1de265bc56 100644
--- a/source/blender/bmesh/operators/bmo_triangulate.c
+++ b/source/blender/bmesh/operators/bmo_triangulate.c
@@ -42,13 +42,15 @@
 
 void bmo_triangulate_exec(BMesh *bm, BMOperator *op)
 {
-	const bool use_beauty = BMO_slot_bool_get(op->slots_in, "use_beauty");
+	const int quad_method = BMO_slot_int_get(op->slots_in, "quad_method");
+	const int ngon_method = BMO_slot_int_get(op->slots_in, "ngon_method");
+
 	BMOpSlot *slot_facemap_out = BMO_slot_get(op->slots_out, "face_map.out");
 
 	BM_mesh_elem_hflag_disable_all(bm, BM_FACE | BM_EDGE, BM_ELEM_TAG, false);
 	BMO_slot_buffer_hflag_enable(bm, op->slots_in, "faces", BM_FACE, BM_ELEM_TAG, false);
 
-	BM_mesh_triangulate(bm, use_beauty, true, op, slot_facemap_out);
+	BM_mesh_triangulate(bm, quad_method, ngon_method, true, op, slot_facemap_out);
 
 	BMO_slot_buffer_from_enabled_hflag(bm, op, op->slots_out, "edges.out", BM_EDGE, BM_ELEM_TAG);
 	BMO_slot_buffer_from_enabled_hflag(bm, op, op->slots_out, "faces.out", BM_FACE, BM_ELEM_TAG);
diff --git a/source/blender/bmesh/tools/bmesh_beautify.c b/source/blender/bmesh/tools/bmesh_beautify.c
index af9345b903c..1a1201c015e 100644
--- a/source/blender/bmesh/tools/bmesh_beautify.c
+++ b/source/blender/bmesh/tools/bmesh_beautify.c
@@ -252,19 +252,13 @@ static float bm_edge_calc_rotate_beauty__angle(
 	return FLT_MAX;
 }
 
-static float bm_edge_calc_rotate_beauty(const BMEdge *e, const short flag, const short method)
+float BM_verts_calc_rotate_beauty(
+const BMVert *v1, const BMVert *v2, const BMVert *v3, const BMVert *v4, const short flag, const short method)
 {
 	/* not a loop (only to be able to break out) */
 	do {
-		const float *v1, *v2, *v3, *v4;
-
-		v1 = e->l->prev->v->co;               /* first face co */
-		v2 = e->l->v->co;                     /* e->v1 or e->v2*/
-		v3 = e->l->radial_next->prev->v->co;  /* second face co */
-		v4 = e->l->next->v->co;               /* e->v1 or e->v2*/
-
 		if (flag & VERT_RESTRICT_TAG) {
-			BMVert *v_a = e->l->prev->v, *v_b = e->l->radial_next->prev->v;
+			const BMVert *v_a = v1, *v_b = v3;
 			if (BM_elem_flag_test(v_a, BM_ELEM_TAG) ==  BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
 				break;
 			}
@@ -277,15 +271,26 @@ static float bm_edge_calc_rotate_beauty(const BMEdge *e, const short flag, const
 
 		switch (method) {
 			case 0:
-				return bm_edge_calc_rotate_beauty__area(v1, v2, v3, v4);
+				return bm_edge_calc_rotate_beauty__area(v1->co, v2->co, v3->co, v4->co);
 			default:
-				return bm_edge_calc_rotate_beauty__angle(v1, v2, v3, v4);
+				return bm_edge_calc_rotate_beauty__angle(v1->co, v2->co, v3->co, v4->co);
 		}
 	} while (false);
 
 	return FLT_MAX;
 }
 
+static float bm_edge_calc_rotate_beauty(const BMEdge *e, const short flag, const short method)
+{
+	const BMVert *v1, *v2, *v3, *v4;
+	v1 = e->l->prev->v;               /* first vert co */
+	v2 = e->l->v;                     /* e->v1 or e->v2*/
+	v3 = e->l->radial_next->prev->v;  /* second vert co */
+	v4 = e->l->next->v;               /* e->v1 or e->v2*/
+
+	return BM_verts_calc_rotate_beauty(v1, v2, v3, v4, flag, method);
+}
+
 /* -------------------------------------------------------------------- */
 /* Update the edge cost of rotation in the heap */
 
diff --git a/source/blender/bmesh/tools/bmesh_beautify.h b/source/blender/bmesh/tools/bmesh_beautify.h
index 210e265d706..7cc17008b50 100644
--- a/source/blender/bmesh/tools/bmesh_beautify.h
+++ b/source/blender/bmesh/tools/bmesh_beautify.h
@@ -35,4 +35,8 @@ void BM_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge_array_
                            const short flag, const short method,
                            const short oflag_edge, const short oflag_face);
 
+float BM_verts_calc_rotate_beauty(const BMVert *v1, const BMVert *v2,
+                                  const BMVert *v3, const BMVert *v4,
+                                  const short flag, const short method);
+
 #endif /* __BMESH_BEAUTIFY_H__ */
diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c
index 34ff493a026..59c2aa4331d 100644
--- a/source/blender/bmesh/tools/bmesh_triangulate.c
+++ b/source/blender/bmesh/tools/bmesh_triangulate.c
@@ -42,14 +42,16 @@
 /**
  * a version of #BM_face_triangulate that maps to #BMOpSlot
  */
-static void bm_face_triangulate_mapping(BMesh *bm, BMFace *face, MemArena *sf_arena, const bool use_beauty, const bool use_tag,
+static void bm_face_triangulate_mapping(BMesh *bm, BMFace *face, MemArena *sf_arena,
+                                        const int quad_method, const int ngon_method,
+                                        const bool use_tag,
                                         BMOperator *op, BMOpSlot *slot_facemap_out)
 {
 	const int faces_array_tot = face->len - 3;
 	BMFace  **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
 	BLI_assert(face->len > 3);
 
-	BM_face_triangulate(bm, face, faces_array, sf_arena, use_beauty, use_tag);
+	BM_face_triangulate(bm, face, faces_array, sf_arena, quad_method, ngon_method, use_tag);
 
 	if (faces_array) {
 		int i;
@@ -61,7 +63,7 @@ static void bm_face_triangulate_mapping(BMesh *bm, BMFace *face, MemArena *sf_ar
 }
 
 
-void BM_mesh_triangulate(BMesh *bm, const bool use_beauty, const bool tag_only,
+void BM_mesh_triangulate(BMesh *bm, const int quad_method, const int ngon_method, const bool tag_only,
                          BMOperator *op, BMOpSlot *slot_facemap_out)
 {
 	BMIter iter;
@@ -75,7 +77,7 @@ void BM_mesh_triangulate(BMesh *bm, const bool use_beauty, const bool tag_only,
 		BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) {
 			if (face->len > 3) {
 				if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) {
-					bm_face_triangulate_mapping(bm, face, sf_arena, use_beauty, tag_only,
+					bm_face_triangulate_mapping(bm, face, sf_arena, quad_method, ngon_method, tag_only,
 					                            op, slot_facemap_out);
 				}
 			}
@@ -85,7 +87,7 @@ void BM_mesh_triangulate(BMesh *bm, const bool use_beauty, const bool tag_only,
 		BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) {
 			if (face->len > 3) {
 				if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) {
-					BM_face_triangulate(bm, face, NULL, sf_arena, use_beauty, tag_only);
+					BM_face_triangulate(bm, face, NULL, sf_arena, quad_method, ngon_method, tag_only);
 				}
 			}
 		}
diff --git a/source/blender/bmesh/tools/bmesh_triangulate.h b/source/blender/bmesh/tools/bmesh_triangulate.h
index 141aa2f82b4..550109ffef9 100644
--- a/source/blender/bmesh/tools/bmesh_triangulate.h
+++ b/source/blender/bmesh/tools/bmesh_triangulate.h
@@ -30,7 +30,7 @@
 #ifndef __BMESH_TRIANGULATE_H__
 #define __BMESH_TRIANGULATE_H__
 
-void BM_mesh_triangulate(BMesh *bm, const bool use_beauty, const bool tag_only,
+void BM_mesh_triangulate(BMesh *bm, const int quad_method, const int ngon_method, const bool tag_only,
                          BMOperator *op, BMOpSlot *slot_facemap_out);
 
 #endif  /* __BMESH_TRIANGULATE_H__ */